Fișierul intrare/ieșire | cuvant.in, cuvant.out | Sursă | OJI 2010 clasa a 7-a |
---|---|---|---|
Autor | Roxana Tîmplaru | Adăugată de | Cristian Frâncu • francu |
Timp de execuție pe test | 0.1 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Cuvant (clasa a 7-a)
Se consideră un șir de cuvinte separate două câte două printr-un spațiu. Fiecare cuvânt este caracterizat prin numărul de ordine care reprezintă poziția lui în șirul de cuvinte (primul cuvânt are numărul de ordine 1). Unui cuvânt i se pot aplica în mod repetat următoarele transformări: primul caracter al cuvântului (cel mai din stânga) se șterge de acolo și se adaugă după ultimul caracter din cuvânt. Astfel, dintr-un cuvânt s cu k caractere se pot obține alte k-1 cuvinte pe care le numim cuvinte obținute din transformarea cuvântului s. De exemplu, dintr-un cuvânt format din 4 caractere c1c2c3c4, cuvintele obținute prin transformarea lui sunt: c2c3c4c1, c3c4c1c2, c4c1c2c3.
Se caută în șirul de cuvinte prima pereche de cuvinte vecine (a,b), în care al doilea cuvânt din pereche (cuvântul b) este identic cu un cuvânt obținut din transformarea lui a. Dacă există o astfel de pereche, se șterge cuvântul b din șir. Prin ștergerea cuvântului b din șir, acesta va avea mai puțin cu un cuvânt! Se repetă operația de căutare de mai sus până când în șirul rămas nu mai există o pereche (a,b) de cuvinte vecine, astfel încât b să fie obținut prin transformarea lui a.
Se știe că pe parcursul modificărilor, cuvintele nu-și schimbă numerele de ordine pe care le-au avut inițial.
Cerință
Scrieți un program care să citească șirul de cuvinte și să afișeze:
a) numărul de ordine al primului cuvânt șters sau valoarea 0 în cazul în care nu se șterge niciun cuvânt
b) numerele de ordine ale cuvintelor rămase după finalizarea operațiilor de modificare.
Date de intrare
Fișierul de intrare cuvant.in conține o singură linie pe care se află șirul de cuvinte separate două câte două printr-un spațiu.
Date de ieșire
Fișierul de ieșire cuvant.out va conține pe prima linie numărul de ordine al primului cuvânt șters sau valoarea 0 în cazul în care nu se șterge niciun cuvânt. Pe a doua linie vor fi scrise numerele de ordine ale cuvintelor rămase în final în șirul de cuvinte, separate prin câte un spațiu.
Restricții
- După ultimul cuvânt din șirul inițial există caracterul !
- Fiecare cuvânt are maxim 10 caractere, iar în șirul inițial nu există mai mult de 25 cuvinte.
- Șirul de cuvinte inițial este format din cel puțin un cuvânt. O pereche de cuvinte vecine (a,b), din șirul de cuvinte este caracterizată prin faptul că, după cuvântul a se afla imediat cuvântul b.
Exemplu
cuvant.in | cuvant.out | Explicații |
---|---|---|
alfa faal alfa fala lafa afal calfa calfa! |
2 1 3 4 7 8 |
Cuvintele obținute prin transformarea cuvântului alfa sunt: : lfaa, faal, aalf. Prima pereche de cuvinte vecine care îndeplinesc cerințele sunt cuvintele cu numerele de ordine 1 și 2. Va fi șters cuvântul cu numărul de ordine 2. Șirul rezultat este format din următoarele 7 cuvinte: alfa alfa fala lafa afal calfa calfa. Prima pereche care îndeplinește cerințele din noul șir este perechea formată din cuvintele fala și lafa, având numerele de ordine 4 și 5, pentru că lista de cuvinte obținute prin transformarea cuvântului fala sunt: alaf, lafa, afal. Se va șterge cuvântul cu numărul de ordine 5. Șirul rezultat după ștergere este: alfa alfa fala afal calfa calfa. Prima pereche care îndeplinește cerințele problemei în noul șir este fala și afal. Se șterge afal cu numărul de ordine 6. Șirul rezultat după ștergere este: alfa alfa fala calfa calfa. În acest șir nu se mai găsește nicio pereche care să îndeplinească cerințele. Au rămas deci cuvintele: alfa, alfa, fala, calfa, calfa care au numerele de ordine 1, 3, 4, 7, 8. |