Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2016-09-23 21:45:32.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:fifty.in, fifty.outSursăFinala ONIS 2016
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Fifty

În vremurile de graţie ale TopCoder-ului majoritatea restricţiilor din probleme erau egale cu 50. Din cauza asta, propunătorii găseau uneori metode neortodoxe de a cere rezolvarea a multe query-uri prin input de dimensiuni mici. Spre exemplu, să presupunem că dorim să producem multe query-uri care implică două numere naturale X şi Y. O soluţie este să oferim un şir de caractere 'a' şi 'b' şi să considerăm că fiecare subsecvenţă a sa reprezintă un query în care X este egal cu numărul de 'a'-uri din subsecvenţă, iar Y este egal cu numărul de 'b'-uri din subsecvenţă. Astfel, putem "stoca" O(N ^ 2) query-uri în spaţiu O(N).

În această problemă vi se dau M query-uri care trebuie neaparat să "apară" în input, iar voi trebuie să produceţi un şir de caractere de lungime exact N care să codeze aceste query-uri.

Spre exemplu, dacă N = 7, M = 2 iar cele două query-uri care trebuie incluse sunt X = 4, Y = 2, respectiv X = 3, Y = 3, atunci şirul "abaabab" este un răspuns valid, deoarece conţine subsecvenţele "abaaba" şi "baabab" care codifică aceste două query-uri.

Date de intrare

Fişierul de intrare fifty.in va conţine pe prima sa linie numărul T, semnificând numărul de teste. Structura unui test este următoarea: pe prima linie se vor afla numerele N şi M. Următoarele M linii vor conţine câte o pereche de numere X Y, semnificând valorile query-ului respectiv.

Date de ieşire

În fişierul de ieşire fifty.out va conţine exact T linii, fiecare conţinând un şir de caractere 'a' şi 'b' sau valoarea -1, în caz că nu există soluţie.

Restricţii

  • 1 ≤ T ≤ 100
  • 1 ≤ N ≤ 50
  • 1 ≤ M ≤ 500
  • Se acceptă orice soluţie corectă.
  • Dacă nu există soluţie, se va afişa -1.

Exemplu

fifty.infifty.out
1
4 2
3 3
abaabab
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?