Az S. 90. feladat (2014. május)

S. 90. 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: \(\displaystyle 1\ge N\ge 200\;000\) ü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 \(\displaystyle i\)-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 \(\displaystyle N\)-et, majd a következő \(\displaystyle N-1\) sorból a barlang alaprajzát: \(\displaystyle a_i\), \(\displaystyle b_i\) egészeket, melyek az \(\displaystyle a_i\)-edik és \(\displaystyle b_i\)-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 \(\displaystyle N\le 200\)-ra megoldást ad;

- a program \(\displaystyle N\le 5000\)-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ó.

(10 pont)

A beküldési határidő 2014. június 10-én LEJÁRT.

Statisztika:

9 dolgozat érkezett.
10 pontot kapott:	Makk László.
7 pontot kapott:	1 versenyző.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	1 versenyző.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2014. májusi informatika feladatai