Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | shopping.in, shopping.out | Sursă | Junior Challenge 2020 |
| Autor | Alexa Tudose | Adăugată de |  Comisia •JuniorChallenge2020 |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Shopping
Kokalaru47 a intrat într-o nouă încurcătură! Prietenul său, Marele Anonim, şi-a cumpărat de curând o permutare p de o frumuseţe nemaiauzită. Curios din fire, Kokalaru47 vrea să afle permutarea. Marele Anonim i-a zis doar că are lungimea N şi că 1 apare înaintea lui 2 în permutarea p, şi a decis să nu dezvăluie în mod direct alte informaţii. În schimb, îi va răspunde la mai multe întrebări.
Într-o întrebare, Kokalaru47 îi dă Marelui Anonim două stringuri A şi B de lungime N. Marele Anonim creează apoi alte două stringuri C şi D astfel încât A=Cp1Cp2Cp3...CpN şi B=Dp1Dp2Dp3...DpN. În final, Marele Anonim răspunde la întrebare cu lungimea prefixului maximal comun dintre C şi D în care există cel mult o nepotrivire.
Înainte de a-i pune Marelui Anonim o întrebare, Kokalaru47 trebuie să cumpere ingredientele pentru întrebarea respectivă. El merge, aşadar, la Magazinul de Stringuri şi achizitionează 2*N litere mici ale alfabetului englez (N pentru stringul A şi N pentru stringul B). Se ştie că litera care apare pe pozitia c în alfabet costă c-1 parai. De asemenea, ingredientele folosite la o întrebare nu pot fi refolosite la o altă întrebare ulterioară.
Cerinţă
Ajutaţi-l pe Kokalaru47 să afle permutarea misterioasă fară să-şi depăşească bugetul de P parai.
Interacţiune
Prima dată se va citi valoarea T, ce reprezintă numărul testelor ce trebuie rezolvate. Pentru fiecare test, se va citi apoi N, reprezentând lungimea permutării căutate.
După aceea, programul vostru poate pune întrebări sub forma "? A B", unde A si B sunt stringuri de lungime N. Aceste intrebari vor fi scrise in stdout. Răspunsul la o întrebare va putea fi citit apoi din stdin.
Când aţi găsit permutarea căutată p, afişaţi "! p1 p2 p3 ... pN".
Precizări
- Citirea şi afişarea se vor face cu standard input/output.
- După fiecare operaţie trebuie afişat caracterul newline ('\n' sau endl) şi trebuie dat flush la bufferul de ieşire (folosind cout.flush() sau fflush(stdout)).
- Dacă la o întrebare primiţi răspunsul -1, înseamnă că întrebarea nu a respectat formatul descris mai sus. În acest caz, trebuie să întrerupeţi interacţiunea imediat.
Restricţii şi punctare
| Nr test | T | N | P | Punctaj |
|---|---|---|---|---|
| 1 | 5 | 8 | 101000 | 10p |
| 2 | 5 | 50 | 101000 | 10p |
| 3 | 5 | 200 | 2000 | 30p |
| 4 | 5 | 200 | 840 | 20p |
| 5 | 5 | 200 | 440 | 30p |
Exemplu
| standard input (cin) | standard output (cout) |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
