Skaitļu spēle - Programme.lv

Stāsts

Valters ir izdomājis smalku skaitļu spēli un piedāvā saviem draugiem Adriānam un Matīsam to izmēģināt. Valters ir izveidojis rūtiņu tabulu ar divām rindām un $K$ kolonnām, kuras katrā rūtiņā ierakstīts kāds vesels skaitlis. Adriāns spēlēs ar augšējās rindas skaitļiem, bet Matīss - ar apakšējās. Spēlētāji gājienus izdarīs pēc kārtas, un spēli sāks Adriāns.

Spēles sākumā visas tabulas kolonnas ir neizsvītrotas un katra spēlētāja skaitļu summa ir $0$ . Katrā gājienā spēlētājs izvēlas kādu vēl neizsvītrotu kolonnu, skaitli no savas rindas pieskaita savai skaitļu summai un kolonnu izsvītro - šīs kolonnas skaitļi turpmāk spēlē vairs nebūs izmantojami.

Spēlētājs ir uzvarējis, ja spēles beigās skaitļu summa pārsniedz pretinieka skaitļu summu. Ja skaitļu summas ir vienādas, tad spēle ir beigusies neizšķirti.

Uzrakstiet datorprogrammu, kas izvēlas, vai spēlēt spēli kā Adriānam vai Matīsam, un spēlē šo spēli, beigās uzvarot, vai nospēlējot neizšķirti, ja nevienam no spēlētājiem nav drošas uzvarošas stratēģijas!

Komunikācija

Šis ir interaktīvs uzdevums.

Sākot darbu, jūsu programmas pirmā ievaddatu rinda satur tabulas kolonnu skaitu - naturālu skaitli $K$ ( $1 \leq K \leq 10^5$ ). Ievaddatu otrajā rindā doti $K$ ar tukšumzīmēm atdalīti veseli skaitļi $A_i$ ( $-10^9 \leq A_i \leq 10^9$ ) - tabulas pirmajā rindā rūtiņās ierakstīto skaitļu vērtības. Ievaddatu trešajā rindā doti $K$ ar tukšumzīmēm atdalīti veseli skaitļi $M_i$ ( $-10^9 \leq M_i \leq 10^9$ ) - tabulas otrajā rindā rūtiņās ierakstīto skaitļu vērtības.

Tad jūsu programmai jāpaziņo par spēlētāja, kura vietā tā spēlēs, izvēli.

Ja programma izvēlas spēlēt kā Adriāns, tad izvadā pirmajā rindā jāizvada burts $A$ un otrajā - viens naturāls skaitlis - pirmajā gājienā izvēlētās kolonnas numurs. Vērtēšanas sistēma izdos atbildi - Matīsa izvēlētās kolonnas numuru.

Ja programma izvēlas spēlēt kā Matīss, tad izvadā vienīgajā rindā jāizvada burts $M$ un vērtēšanas sistēma izdos atbildi - Adriāna izvēlētās kolonnas numuru.

Tad jūsu programma var veikt gājienus, rakstot izvadā iepriekš neizmantotas kolonnas numuru $i$ . Vērtēšanas sistēma nākamajā ievada rindā izdod atbildi - pretinieka izvēlētās kolonnas numuru $j$ . Kad jūs esat izvadījis informāciju par visiem jūsu izvēlētā spēlētāja gājieniem, vērtēšanas sistēma neatbildēs uz šo izvadu un nepieņems sekojošus vaicājumus.

Ja tiks izmantots nederīgs kolonnas numurs, tiks izdots kļūdas paziņojums “Izvaddati nav pareizi”.

Apakšuzdevumi un to vērtēšana

#	Apakšuzdevuma apraksts	Punkti
1.	$0 \leq A_i, M_i \leq 1$	18
2.	$A_i = M_i$	21
3.	$K \leq 2000$	25
4.	Bez papildu ierobežojumiem	36

Apakšuzdevumu punktu summa = 100.

Piemēri

Vērtēšanas sistēma

Jūsu programma

Vērtēšanas sistēma:
```
6
5 3 4 1 2 6
2 5 1 4 3 6
```
Jūsu programma:
```
A
6
```
Vērtēšanas sistēma:
```
2
```
Jūsu programma:
```
1
```
Vērtēšanas sistēma:
```
4
```
Jūsu programma:
```
3
```
Vērtēšanas sistēma:
```
5
```

Piezīme

Šajā piemērā jūsu programma spēlēja kā Adriāns un uzvarēja, jo programmas izvēlēto skaitļu summa bija $15$ $(6+5+4)$ , bet Matīsa - $12$ $(5+4+3)$ .

Vērtēšanas sistēma

Jūsu programma

Vērtēšanas sistēma:
```
7
1 2 3 4 5 6 11
7 7 7 7 7 7 7
```
Jūsu programma:
```
M
```
Vērtēšanas sistēma:
```
7
```
Jūsu programma:
```
6
```
Vērtēšanas sistēma:
```
5
```
Jūsu programma:
```
4
```
Vērtēšanas sistēma:
```
3
```
Jūsu programma:
```
2
```
Vērtēšanas sistēma:
```
1
```

Piezīme

Šajā piemērā jūsu programma spēlēja kā Matīss un uzvarēja, jo programmas izvēlēto skaitļu summa bija $21$ $(7+7+7)$ , bet Adriāna - $20$ $(11+5+3+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.