Fişierul intrare/ieşire:abba.in, abba.outSursăJunior Challenge 2019
AutorMircea DonciuAdăugată deJuniorChallenge2019Junior Challenge 2019 JuniorChallenge2019
Timp execuţie pe test0.25 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Abba

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:

  1. Primul copil: a___________________________________________________b
  2. Al 2-lea copil: a_________________________ab________________________b
  3. Al 3-lea copil: a__________aab____________ab___________abb__________b
  4. 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 modulo 109 + 7, 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.
  • Raspunsul trebuie afisat modulo 109 + 7.

Subtaskuri

  1. 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)
  2. 20 puncte: toate cuvintele apar, si apar pentru prima data in primele 14 propozitii. (testele 2 şi 3)
  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)
  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)
  5. 30 de puncte: se aplică restricţiile iniţiale (testele 8-10)

Exemplu

abba.inabba.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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?