Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | abba.in, abba.out | Sursă | Junior Challenge 2019 |
| Autor | Mircea Donciu | Adăugată de |  Junior Challenge 2019 •JuniorChallenge2019 |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Abba
Va rugam nu trimiteti surse la problema aceasta pentru urmatoarea scurta perioada de timp! Testele si enuntul vor fi putin modificate. Detalii pe forum!
X isi petrecea cei 4 ani in Institutia Teoretica de Informatica in asteptarea unei diplome ca ar fi absolvit "liceul".
In timpul sau liber (practic tot timplul sau era liber), a dat de scena urmatoare:
Copiii de la uman se jucau cu niste cuvinte, dar fara sa inteleaga foarte bine despre ce e vorba (daca stiau mai bine poate nu s-ar fi dus la uman).
Fiecare copil spune la randul sau o propozitie (un sir de cuvinte), dupa urmatoarea regula:
- Primul copil: a___________________________________________________b
- Al 2-lea copil: a_________________________ab________________________b
- Al 3-lea copil: a__________aab____________ab___________abb__________b
- Al 4-lea copil: a___aaab___aab____aabab___ab___ababb___abb___abbb__b
Altfel spus, primul copil spune cuvintele 'a' si 'b', si dupa el fiecare copil repeta ce a zis cel dinaintea lui, adaugand intre fiecare doua cuvinte concatenarea acestora.
X isi pune mai multe intrebari, care pot fi formulate informatic sub forma de mai jos.
Intrebarea este un cuvant, si raspunsul pentru aceasta este al catelea copil spune acel cuvant pentru prima data, si al catelea cuvant este din propozitia lui, respectiv -1 daca acel cuvant nu apare deloc.
Date de intrare
Prima linie contine Q, numarul de cuvinte la care se gandeste X.
Urmatoarele Q linii contin fiecare cate un cuvant.
Date de ieşire
Pentru fiecare din cele Q cuvinte, pe cate o linie, se afiseaza fie x y insemnand ca prima aparitie a cuvantului este la al x-lea copil, si cuvantul este al y-lea din lista copilului x, fie -1 daca nu apare deloc.
Restricţii
- 1 ≤ Q ≤ 104
- Suma lungimilor celor Q cuvinte la care se gandeste X nu depaseste 106.
- Cuvintele la care se gandeste X sunt formate din literele mici ale alfabetului englez.
Subtaskuri
- 10 puncte: suma lungimilor este cel mult 1000, se garanteaza ca toate cuvintele apar, si apar pentru prima data in primele 10 propozitii. (testul 1)
- 20 puncte: toate cuvintele apar, si apar pentru prima data in primele 14 propozitii. (testele 2 şi 3)
- 10 puncte: toate cuvintele apar, si apar pentru prima data in primele 100 de propozitii, in primele 100 cuvinte ale acelei propozitii si au lungimea cel mult 100. (testul 4)
- 30 de puncte: cuvintele la care se gandeste X sunt alese pseudo-aleator: oricare doua cuvinte existente de aceasi lungime au aceasi probabilitate sa fie alese, si oricare doua cuvinte neexistente de aceasi lungime au aceasi probabilitate sa fie alese. (testele 5-7)
- 30 de puncte: se aplică restricţiile iniţiale (testele 8-10)
Exemplu
| abba.in | abba.out |
|---|---|
| 10 a b aab ab ba abc aaaaabaaaabaaaaabaaaabaaaab abbbbabbbbabbbbbabbbbabbbbbabbbbabbbbb abbbbabbbbabbaaaaaabbbbbbbbbbbbaaababbbaabbbbb aabaababaababaabaababaababaabaababaababaababaabaababaababaabaababaababaabab | 1 1 1 2 3 2 2 2 -1 -1 9 14 10 488 -1 10 180 |
Explicaţie
- Uitandu-ne pe diagrama de mai sus, observam ca primele aparitii ale cuvintelor 1-4 sunt (1, 1), (1, 2), (3, 2) respectiv (2, 2)
- Se poate demonstra ca nu o sa apara niciodata cuvantul 'ba' nici 'abc', deci raspunsul este -1.
