|
Problema 1 Punctaj: 40 puncte.
Fie A un alfabet care consta din n (1<=n<=200) simboluri, numerotate de
la 1 la n. Un cuvant peste alfabetul A este considerat corect daca:
* oricare doua simboluri consecutive sunt distincte;
* prin atergerea de simboluri dintr-un cuvant nu este posibila obtinerea unor
cuvinte de forma abab aa si b simboluri distincte oarecare, din alfabetul A.
Intrare:
Din fisierul de intrare INPUT.TXT se citeste de pe prima linie numarul n;
de pe linia a doua - numarul m (1<=m<=1000) al simbolurilor din cuvant,
iar de pe urmatoarele m linii o succesiune de numere naturale, fiecare pe o
linie separata, reprezentand simbolurile cuvantului.
Iesire:
Se cere sa verificati daca succesiunea de numere citite din fisierul de
intrare reprezinta un cuvant corect peste alfabetul A = {1, 2, ..., n}.
In fisierul de iesire OUTPUT.TXT veti afisa:
* pe prima linie: mesajul DA, in cazul in care cuvantul citit a fost corect
sau NU in caz contrar;
* pe a doua linie: lungimea maxima a unui cuvant corect peste alfabetul
A = {1, 2, ..., n};
* pe urmatoarele linii o succesiune de numere naturale (cate un numar pe
fiecare linie), care sa reprezinte un cuvant corect de lungime maxima
peste alfabetul A = {1, 2, ..., n}.
Exemplu:
Pentru fisierul de intrare
3
1
2
3
2
Fisierul de iesire va fi:
DA
5
1
2
1
3
1
Nota: Datele de intrare sunt corecte.
Timp maxim de executie: 5 secunde per test.
Problema 2
Conducerea Liceului de Informatica "Grigore Moisil" din Timisoara
intentioneaza sa organizeze o excursie la Sherbrooke in Canada. Deoarece
sunt multi amatori, a fost initiata o triere pe baza unui joc Timtris.
Jocul consta in construirea unui zid dreptunghiular, compact (fara gauri)
din piese care apar intr-o anumita ordine impusa.
Regulile jocului:
(Exista 5 piese de forme diferite; acestea pot fi rotite cu 0~, 90~, 180~,
270~. In tabelul de mai jos sunt prezentate piesele si orientarile lor
posibile.)
| | Orientare1 | Orientare2 | Orientare3 | Orientare4 |
| Piesa1 | 
| | | |
| Piesa2 |
| | | |
| Piesa3 |
 |
| | |
| Piesa4 |
|
| | |
| Piesa5 |
|
|
|
|
* La construirea zidului trebuie sa plasati rand pe rand toate piesele, in
ordinea aparitiei lor.
* Odata aleasa orientarea piesei si coloana in care o veti plasa, se lasa sa
cada (de sus in jos).
* Odata ce o piesa atinge baza sau a cazut pe o alta piesa din zid ea este
plasata in acel loc.
* Piesele trebuie plasate astfel incat sa nu creeze nici o gaura in zid.
* Fiecare piesa trebuie plasata astfel incat sa nu depaseasca latimea impusa
a zidului.
* Un rand de zid completat (fara gauri) nu dispare.
Intrare:
Fisierul de intrare input.txt va contine:
- pe prima linie, latimea L (1<=L<=15) a zidului de construit;
- pe a doua linie, numarul N (1<=N<=50) de piese;
- pe fiecare din urmatoarele N linii, numarul piesei care urmeaza sa
fie plasata. Tabelul anterior asociaza fiecarei piese un numar. Lista
impune in acest fel ordinea de sosire.
Iesire:
Fisierul de iesire output.txt trebuie sa contina:
- daca nu poate fi construit un zid compact, in fisier se va afisa NU;
- daca zidul poate fi construit, fisierul trebuie sa contina N linii cu
urmatoarea structura:
a b unde a reprezinta orientare piesei,
iar b reprezinta coloana in care este plasata
extremitatea stanga a piesei.
Exemple:
1. pentru fisierul de intrare: fisierul de iesire contine:
6
12 2 1
2 1 5
1 2 4
3 1 1
5 1 1
2 3 2
5 1 6
2 1 2
5 2 4
4 3 1
5 1 5
1 2 1
2
(poza)
2. pentru fisierul de intrare: fisierul de iesire trebuie sa contina:
5 NU
3
5
5
5
NOTA:
Timp de executie: 30 secunde/test
Punctaj: 50 puncte
|
