shopping

Shopping

== 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. $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.

$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$ ş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*.

Î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 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ă.
 

Î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

* 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++ un template care se ocupă direct de interacţiuni pe care le puteti gasi AICI.*

* *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