== include(page="template/taskheader" task_id="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, însă $Marele Anonim$ i-a zis doar că are lungimea $N$ şi a decis să nu dezvăluie în mod direct alte informaţii. În schimb, îi va răspunde la mai multe întrebări.
$K0kalaru47$ 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, $K0kalaru47$ 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 = A{~p{~1~}~}A{~p{~2~}~}A{~p{~3~}~}...A{~p{~N~}~}$ şi $D = B{~p{~1~}~}B{~p{~2~}~}B{~p{~3~}~}...B{~p{~N~}~}$. În final, $Marele Anonim$ răspunde la întrebare cu lungimea prefixului maximal comun dintre $C$ şi $D$ în care există *cel mult o nepotrivire*.
Într-o întrebare, $K0kalaru47$ î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=C{~p{~1~}~}C{~p{~2~}~}C{~p{~3~}~}...C{~p{~N~}~}$ şi $B=D{~p{~1~}~}D{~p{~2~}~}D{~p{~3~}~}...D{~p{~N~}~}$. Î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ă.
Înainte de a-i pune $Marelui Anonim$ o întrebare, $K0kalaru47$ trebuie să cumpere ingredientele pentru întrebarea respectivă. El merge, aşadar, la String Shopping City ş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ă.
h2. Cerinţă
Ajutaţi-l pe Kokalaru47 să afle permutarea misterioasă fară să-şi depăşească bugetul de $P$ parai.
Ajutaţi-l pe K0kalaru47 să afle permutarea misterioasă fară să-şi depăşească bugetul de $P$ parai.
h2. 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.
Programul vostru poate pune apoi î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 din stdin.
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 *$"! p{~1~} p{~2~} p{~3~} ... p{~N~}"$*.
Când aţi găsit permutarea căutată $p$, afişaţi $"! p{~1~} p{~2~} p{~3~} ... p{~N~}"$.
h2. 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)).
* 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.
* 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.
* *Infoarena oferă pentru limbajele C/C++ şi Rust câte un template care se ocupă direct de interacţiuni, pe care le puteţi găsi* "AICI":https://infoarena.ro/template_shopping.
* *Dacă se afişează permutarea greşită interactorul returnează $-1$ şi opreşte interacţiunea.*
h2. Restricţii şi punctare
table(example). |_. $N$ |_. $P$ |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
table(example). |_. Nr test |_. $T$ |_. $N$ |_. $P$ |_. Punctaj |
| 1
| 5
| 8
| $10^1000^$
| 10p
|
| 2
| 5
| 50
| $10^1000^$
| 10p
|
| 3
| 5
| 200
| 2000
| 30p
|
| 4
| 5
| 200
| 840
| 20p
|
| 5
| 5
| 200
| 440
| 30p
|
h2. Exemplu
table(example). |_. standard input (cin) |_. standard output (cout) |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|2
4
3
1
1
4
4
1
|  
 
? zzzz zzab
? abcd efca
? cacf cbdz
! 3 1 4 2
? aqqq azqq
? abcc bacc
! 1 2 3 4
|
h3. Explicaţie
...
În primul test, permutarea căutată este $p = (3 1 4 2)$. Interacţiunea începe prin citirea valorii $N = 4$.
În prima întrebare, $A = zzzz$ şi $B = zzab$. Avem $C = zzzz$ şi $D = zbza$. Cel mai lung prefix comun dintre $C$ şi $D$ în care există cel mult o nepotrivire este cel de lungime $3$. Costul acestei întrebări este costul pentru a cumpăra literele $z$, $z$, $z$, $z$, $z$, $z$, $a$ şi $b$, deci este $25+25+25+25+25+25+0+1=151$.
În a doua întrebare, $A = abcd$ şi $B = efca$. Avem $C = bdac$ şi $D = faec$. Cel mai lung prefix comun dintre $C$ şi $D$ în care există cel mult o nepotrivire este cel de lungime $1$. Costul acestei întrebări este costul pentru a cumpăra literele $a$, $b$, $c$, $d$, $e$, $f$, $c$ şi $a$, deci este $0+1+2+3+4+5+2+0=17$.
În a treia întrebare, $A = cacf$ şi $B = cbdz$. Avem $C = afcc$ şi $D = bzcd$. Cel mai lung prefix comun dintre $C$ şi $D$ în care există cel mult o nepotrivire este cel de lungime $1$. Costul acestei întrebări este costul pentru a cumpăra literele $c$, $a$, $c$, $f$, $c$, $b$, $d$ şi $z$, deci este $2+0+2+5+2+1+3+25=40$.
Costul total pentru rezolvarea primului test este $151 + 17 + 40 = 208$.
Interacţiunea va continua prin citirea valorii $N = 4$ corespunzătoare următorului test.
== include(page="template/taskfooter" task_id="shopping") ==
