Kurmju hipocentrs - Programme.lv

Stāsts

Artim dārzā iemitinājušies lieli kurmji. Tie bojā skaisto, zaļo mauriņu, tāpēc vēlams tos aizvest prom. Artis ir ievērojis, ka šie kurmji darbojas tikai naktī, un katru rītu ir atrodams jauns kurmju rakums. Arta draugs, kurmju eksperts Vējonis gan apgalvo: "Tie nav kurmji, bet gan matainās sakņu žurkas!"

Šie interesantie kurmji (vai žurkas?) veido pazemes tuneļu sistēmu, kas savieno $N$ dobumus (sanumurētus no $1$ līdz $N$ ), kur no katra dobuma var aizrāpot uz katru citu dobumu tieši vienā vienīgā veidā. Tieši vienā no $N$ dobumiem ir galvenais midzenis - šo kurmju "hipocentrs"¹. Tuneļu sistēmas struktūru Vējonis jau ir noskaidrojis, bet nav vēl zināms, kur tajā atrodas hipocentrs.

Artis ir nolēmis atrast šo kurmju hipocentru. Zināms, ka katrs virszemē redzamais kurmju rakums vienmēr atrodas virs kāda no dobumiem, un, ja kādu dobumu aizbērs ciet, tad nākamajā rīta būs izrakts jauns kurmju rakums virs dobuma, kurš atradīsies hipocentram tuvāk nekā aizbērtais. Artis grib atrast hipocentru laicīgi. Kad Artis bērs ciet hipocentru, viņš sapratīs, ka tas ir hipocentrs. Ja Artis $22$ . rakšanas reizē nebūs atradis hipocentru, viņš padosies.

Kurmji nevar pārvietoties uz un caur aizbērtu dobumu. Kurmju rakums var pārādīties tikai virs dobuma, uz kuru var aizrāpot no hipocentra.

Tuneļu sistēmas piemērs: zemāk redzamajā attēlā attēlota tuneļu sistēma ar $N=12$ dobumiem, kur ceturtajā atrodas hipocentrs. Pirmajā dienā Artis aizber $10$ . dobumu, un nākamajā rītā ir jauns kurmju rakums virs $3$ . dobuma. Tas varēja būt arī, piemēram, virs $2$ . dobuma, bet ne virs $12$ ., jo $12$ . dobums nav tuvāk² hipocentram nekā $10$ . dobums. Ja Artis otrajā dienā izvēlēsies aizbērt 4. dobumu, viņš atklās hipocentru. Jāpiemin arī, ka, kopš $10$ . dobums ir aizbērts, kurmju rakums nevar parādīties virs tā un $5$ . dobuma.

Uzrakstiet datorprogrammu, kas katru dienu palīdz Artim izvēlēties, kuru vienu dobumu aizbērt. Artis, savukārt, katru dienu ieteikto dobumu aizber un nākamajā rītā datorprogrammā ieraksta jaunā kurmju rakuma atrašanās vietu - dobuma kārtas numuru, virs kura atrodas jaunais kurmju rakums. Datorprogramma ir pareiza, ja Artis ne vēlāk kā pēc $22$ . rakšanas reizes atklās hipocentru.

Footnotes

Tipiski vārda “hipocentrs” nozīme ir zemestrīces centrs Zemes garozā, bet šajā uzdevumā tas ir kurmju midzenis. ↩
Dobums $A$ ir tuvāk hipocentram $H$ nekā $B$ , ja starp $A$ un $H$ ir mazāks dobumu skaits nekā starp $B$ un $H$ . ↩

Komunikācija

Šis ir interaktīvs uzdevums. Sākot darbu, jūsu programmai pirmajā ievaddatu rindā būs dots naturāls skaitlis $N$ ( $1 \leq N \leq 10^5$ ) -- tuneļu sistēmas dobumu skaits. Nākamajās $N-1$ rindās dots dobumu savienojumu apraksts -- savienoto dobumu kārtas numuri $d_1, d_2$ ( $1 \leq d_1 < d_2 \leq N$ ).

Tad jūsu programmai jāsniedz norādes Artim. Katrā norādē izvadā jāraksta viens skaitlis $x$ -- kārtējā dienā aizberamā dobuma kārtas numurs. $i$ -tā izvadītā rinda atbilst dobumam, ko Artis aizber $i$ -tajā dienā.

Vērtēšanas sistēma atbild uz norādēm. Pēc katra aizbērtā dobuma vērtēšanas sistēma sniedz atbildi, nākamajā ievaddatu rindā to rakstot formātā « $1$ », ja $x$ ir hipocentrs, vai « $0$ $y$ », kur $y$ -- jaunā kurmju rakuma pozīcija, kas ir tuvāk hipocentram. Sistēma izpildes laikā tur (fiksētu) hipocentra atrašanās vietu slepenībā.

Jūsu programma katrā testā var sniegt ne vairāk kā $22$ norādes. Kad jūsu programma saņem no sistēmas atbildi « $1$ », tad tai darbība ir jābeidz.

Apakšuzdevumi un to vērtēšana

#	Apakšuzdevuma apraksts	Punkti
1.	$N = 20$	5
2.	$N = 40$	10
3.	$50 \leq N \leq 100$	15
4.	$i$ -tais dobums savienots tikai ar $i-1$ (ja $i-1 \geq 1$ ) un $i+1$ (ja $i+1 \leq N$ )	20
5.	$500 \leq N \leq 1000$	30
6.	Bez papildu ierobežojumiem	20

Apakšuzdevumu punktu summa = 100.

Piemērs

Vērtēšanas sistēma

Jūsu programma

Jūsu programma:
```
10
```
Vērtēšanas sistēma:
```
0 3
```
Jūsu programma:
```
11
```
Vērtēšanas sistēma:
```
0 3
```
Jūsu programma:
```
3
```
Vērtēšanas sistēma:
```
0 4
```
Jūsu programma:
```
4
```
Vērtēšanas sistēma:
```
1
```

Piezīmes

Lai garantētu, ka jūsu programmas "vaicājumus" saņem vērtēšanas sistēma, jums ir "jāsinhronizē" (flush) izvaddatu plūsma (stdout) pēc katra vaicājuma. Vairāk par datu ievadi un izvadi interaktīvajos uzdevumos lasiet šeit.