Fişierul intrare/ieşire:shopping.in, shopping.outSursăJunior Challenge 2020
AutorAlexa TudoseAdăugată deJuniorChallenge2020Comisia •JuniorChallenge2020
Timp execuţie pe test0.2 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Shopping

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, 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=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, 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ă.

Cerinţă

Ajutaţi-l pe K0kalaru47 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.
  • 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.
  • Dacă se afişează permutarea greşită interactorul returnează -1 şi opreşte interacţiunea.

Restricţii şi punctare

Nr testTNPPunctaj
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)
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

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?