A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. Egy barlang több üregből, és az üregeket összekötő járatokból áll. Egy titkos ügynök elrejtett egy nagy értékű kincset a barlang egyik üregében, mi ezt szeretnénk megtalálni. Ismerjük a barlang felépítését: üregből áll, és bármely két üreget választva pontosan egyféleképp tudunk eljutni az egyikből a másikba. Ráadásul úgy szeretnénk megtalálni a kincset, hogy be sem tesszük a lábunkat a barlangba. Kérdéseket tehetünk fel az ügynöknek, méghozzá a következő formában: ,,A kincs az -edik üregben van?'' Erre az ügynök megmondja a helyes választ, és ha nem találtuk el, akkor azt is, hogy az üregből melyik irányban keressük a kincset. A probléma abban rejlik, hogy az ügynök nem szereti a fölöslegesen hosszú kérdezősködést. Emiatt az a feladat, hogy minél kevesebb kérdéssel meg tudjuk mondani, hogy hol van a kincs. Teljes pontszámot csak az a program kaphat, amely a minimális számú kérdés feltevésével megoldja a feladatot, akkor is, ha a legtöbb kérdés feltevését igénylő üregben van a kincs. A programnak tehát azt a kérdésmennyiséget kell megadni, ami a lehető legkisebb, de ennyivel garantáljuk, hogy mindenképp kitalálható, hol van a kincs. A program olvassa be a standard input első sorából -et, majd a következő sorból a barlang alaprajzát: , egészeket, melyek az -edik és -edik üreg közti járatot jelzik. Megoldásként a program írja a standard output első és egyetlen sorába a kérdések számát.
Pontozás és korlátok: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a további 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül. A programot több tesztesetre futtatjuk. Nagyon súlyos hibának számít, ha valahol olyan kérdésszámot ír ki, amennyivel nem oldható meg a feladat. Ha több kérdést ír ki, mint az optimális, akkor arra részpontszám kapható. Tehát amit a program kiír, annyi kérdésből mindenképp ki kell, hogy tudjuk találni a kincs helyét. Részpontszámok a következőkre kaphatóak: ‐ a program -ra megoldást ad; ‐ a program -re megoldást ad. Beküldendő egy tömörített s90.zip állományban a program forráskódja (s90.pas, s90.cpp, ) az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s90.txt, s90.pdf, ), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható. |