Az eredeti feladat itt.

A tűzijáték helyét szeretnénk megkeresni, azaz az x-tengely egy (p,0) pontját. Rögzített pont súlyát, azaz a sétálandó össztávolságot könnyű kiszámolni N lépésben: minden lakosról konstans időben meghatározhatjuk, hogy ő mennyit gyalogol, majd ezeket összeadjuk. Ezt azonban nem játszhatjuk el az x-tengely összes szóba jövő pontjára, hiszen az négymilliárd pontot jelent, négymilliárdszor N lépésre pedig nincs idő. Ilyenkor hasznos trükk az úgynevezett seprés, jelen esetben vizuálisan úgy képzelhetjük, hogy balról jobbra végigseprünk (ha úgy tetszik, egy függőleges egyenest) a szóba jövő pontokon, magyarul ilyen sorrendben haladunk végig rajtuk. Így tehát elég a súlyváltozást számolnunk, ezáltal megspórolhatjuk, hogy minden alkalommal végigmenjünk az N lakoson.

Ez egy kezdőlökés a megoldás felé, de távolról sem vagyunk készen. Ugyanis ez így nem fog működni: még kell egy kicsit gondolkodni.

A bejegyzés trackback címe:

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.