ONI 1997, Finala, Timisoara 1997
Clasa XII

Problema 1 (Alfabet)
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 stergerea de simboluri dintr-un cuvant nu este posibila obtinerea unor
cuvinte de forma abab (a 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 cuv(nt 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
4
1
2
3
2
Fisierul de iesire va fi:
DA
5
1
2
1
3
1
Timp maxim de executie: 5 secunde per test.
Nota:
Datele de intrare sunt corecte.
Punctaj: 40 puncte.
=========================================
Solutie (Manuela Mateescu)
Spunem ca o litera este de speta I daca ea intervine o singura data in 
cuvant. Altfel, ea se numeste de speta a II-a.
Observatii:
1.  Literele alaturate unei litere de speta a II-a trebuie sa fie distincte 
(altfel este incalcata proprietatea 2.)
2.  Intr-un cuvant exista intotdeauna o litera de speta I. (tot din 
proprietatea 2.)
3.  Lungimea maxima a unui cuvant care indeplineste conditiile 1. si 2. este 2n-1.
Demonstratie:
Vom proceda prin inductie completa dupa numarul de litere din alfabet.
P(1): Lungimea maxima a unui cuvant corect peste un alfabet cu o 
singura litera este 1= 2*1-1. (altfel este ncalcata proprietatea 1.)

Presupunem ca lungimea maxima a unui cuvant peste un alfabet Ah cu h litere 
este 2h - 1, pentru h si k arbitrare.
Demonstram ca lungimea maxima a unui cuvant peste un alfabet A k+1 
cu k+1 litere este 2k + 1. 

Fie C k+1 un cuvant peste Ak+1.
Fie a o litera de speta I din Ck+1. Fie b litera alaturata lui a (in stanga 
sau in dreapta).
Daca b este de speta I, eliminnd b din cuvnt obtinem un cuvnt 
corect peste alfabetul Ak, deci lungimea maxima a acestuia este 2k-1. 
Deducem ca lungimea maxima a lui Ck+1 este 2k-1+1 < 2k+1.
Daca b este de speta a II-a, atunci fie x si y vecinii perechii ab (daca 
acestia exista): xaby.
Din proprietatea 2. deducem ca x<=y, deci putem elimina din Ck+1 
perechea ab, fara a incalca proprietatea a. Eliminand perechea ab din 
Ck+1, obtinem un cuvant peste Ak, lungimea maxima a acestuia fiind 
2k-1, rezulta ca lungimea maxima a lui Ck+1 este 2k-1 + 2 = 2k+1.
Q.E.D.
Un exemplu de cuvant de lungime maxima:
1 2 3 .. n-1 n n-1 n-2 .. 2 1
Observatie:
Numarul cuvintelor de lungime maxima peste An este de O(n!).

Reprezentarea informatiilor:
n - numarul de litere din alfabet.
NrAp un vector de dimensiune n in care pentru fiecare litera din alfabet retinem 
numarul de aparitii in cuvant.
C un vector de dimensiune maxima 2n - 1, in care vom retine cuvantul.

Algoritm:
1.  Citesc din fisier cuvantul memorandu-l in vectorul C si verificand 
in acelasi timp daca oricare doua litere consecutive sunt distincte si 
calculand numarul de aparitii ale fiecarei litere in cuvant. Daca 
lungimea cuvantului citit este mai mare decat 2n-1, stop! cuvant eronat.
2.  Se repeta cat timp lungimea cuvantului C este mai mare decat 1 si nu am gasit erori:
2.1.  Caut a, prima litera de speta I. Daca nu am gasit: stop!  eroare!
2.2.  Cat timp vecinul din dreapta este de speta  I, il elimin.
2.3.  Construiesc (daca este posibil) perechea ab, unde b este un vecin al lui 
a (din stanga sau din dreapta) de speta a II-a.
2.4.  Verific daca eventualii vecinii ai perechii ab sunt diferiti. 
Daca nu, stop! eroare!
2.5.  Elimin perechea ab din cuvant.
====================================
program TestAlfabetizare;
uses dos;
Const NMaxLitere = 5000;
      LgMaxCuvant = 2 * NMaxLitere - 1;
type  Litera = 1 .. NMaxLitere;
      Lungime = 0..LgMaxCuvant;
      Cuvant = array [Lungime] of Litera;
var   n, a, b: Litera;
      C: Cuvant;  LgMax, Lg, i: Lungime;
      NrAp, FirstAp, LastAp: array [ Litera] of Lungime;
      Eroare: boolean;
      h, h1, m, m1, s, s1, ss, ss1: word;

procedure Initializare;
label 1;
var fin, fout, fMyOut, frez: text; nume: string;
    i : word;
    p1, p2, ptotal: word;
    MyLgMax : Lungime;
    answer, MyAnswer: string;
begin
assign (fin, 'input.txt'); reset (fin);          { fisier i.*           }
assign (fout, 'output.txt'); reset (fout);       { fisier iesire elev   }
assign (frez, 'rez.txt'); rewrite (frez);        { fisier rezultate eval}
assign (fmyout, 'o.10'); reset (fmyout);    {<----- fisierul nostru o.* }

readln (fin, n);            { citesc din fin }
MyLgMax := 2 * n - 1;
close(fin);

readln (fmyout, myanswer); {citesc din fmyout }
readln (fmyout, p1, p2);
ptotal := 0;
close (fmyout);

readln (fout, answer);
if answer <> myanswer then
   writeln ('Validare defecta')
   else
   inc (ptotal, p1);
readln (fout, lgmax);
eroare := false;
if LgMax = MyLgMax then
   begin
   for i:=1 to lgMax do
       begin
       readln (fout, C[i]);
       inc (NrAp[C[i]]);
       if NrAp[C[i]] = 1 then
          FirstAp[C[i]]:=i;
       LastAp[C[i]] := i;
       if C[i] = C[i - 1] then
               begin
               eroare := true;
               WriteLn('Cuvnt de lungime maxima incorect');
               goto 1;
               end;
       end;
       for a:=1 to n do
              if NrAp[a] > 1 then
                 for b:=1 to n do
                     if (a<>b) and (NrAp[b] > 1) then
                        begin
                i := FirstAp[a];
                while (i <= LastAp[a]) and (C[i]<>a) do inc (i);
                if i < LastAp[a] then
                 begin
                 while (i <= LastAp[b]) and (C[i]<>b) do inc (i);
                 if i<LastAp[b] then
                  begin
                  while (i <= LastAp[a]) and (C[i]<>a) do inc (i);
                   if i<=LastAp[a] then
                    begin
                    while (i <= LastAp[b]) and (C[i]<>b) do inc (i);
                    if i <= LastAp[b] then
                      begin
                        WriteLn('Cuvnt de lungime maxima incorect');
                        Eroare := true;
                        goto 1
                      end
                    end
                  end
                 end
                end;
       end
   else begin
     Eroare := true;
     WriteLn('Lungime maxima eronata');
   end;
1:
 if Not Eroare then inc(ptotal, p2);
 WriteLn('Punctaj total ',ptotal);
 Writeln (fRez, ptotal);
close(fout);
end;
begin {program principal}
Initializare;
end.
==================================
Teste intrare:
testul 1:
2
4
1
2
1
2
----------------------
Testul 2:
2
3
1
2
1
-----------------------
testul 3:
4
7
1
4
3
2
2
3
1
--------------------
testul 4:
4
8
1
2
3
4
3
2
1
4
-------------------
testul 5:
8
16
8
1
8
2
8
3
8
4
8
5
8
6
8
7
8
4
---------------------
testul 6:
8
15
1
2
3
4
5
6
7
8
7
6
5
4
3
2
1
------------------
Testul 7:
100
199
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
99
98
97
96
95
94
93
92
91
90
89
88
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
99
------------------------
Testul 8:
100
199
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
99
98
97
96
95
94
93
92
91
90
89
88
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
----------------------
testul 9:
200
399
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
199
198
197
196
195
194
193
192
191
190
189
188
187
186
185
184
183
182
181
180
179
178
177
176
175
174
173
172
171
170
169
168
167
166
165
164
163
162
161
160
159
158
157
156
155
154
153
152
151
150
149
148
147
146
145
144
143
142
141
140
139
138
137
136
135
134
133
132
131
130
129
128
127
126
125
124
123
122
121
120
119
118
117
116
115
114
113
112
111
110
109
108
107
106
105
104
103
102
101
100
99
98
97
96
95
94
93
92
91
90
89
88
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
---------------------
testul 10:
200
399
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
199
198
200
196
195
194
193
192
191
190
189
188
187
186
185
184
183
182
181
180
179
178
177
176
175
174
173
172
171
170
169
168
167
166
165
164
163
162
161
160
159
158
157
156
155
154
153
152
151
150
149
148
147
146
145
144
143
142
141
140
139
138
137
136
135
134
133
132
131
130
129
128
127
126
125
124
123
122
121
120
119
118
117
116
115
114
113
112
111
110
109
108
107
106
105
104
103
102
101
100
99
98
97
96
95
94
93
92
91
90
89
88
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
================================
Teste iesire:
Iesire 1:
NU
1 1
3
1
2
1
-------------------
Iesire 2:
DA
1 1
3
1
2
1
---------------------
Iesire 3:
NU
1 1
7
1
2
3
4
3
2
1
----------------------
Iesire 4:
NU
2 2
7
1
2
3
4
3
2
1
-----------------------
Iesire 5:
NU
2 2
15
1
2
3
4
5
6
7
8
7
6
5
4
3
2
1
--------------------
Iesire 6:
DA
2 2
15
1
2
3
4
5
6
7
8
7
6
5
4
3
2
1
---------------------
Iesire 7:
NU
2 3
199
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
99
98
97
96
95
94
93
92
91
90
89
88
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
-----------------
Iesire 8:
DA
2 3
199
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
99
98
97
96
95
94
93
92
91
90
89
88
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
-------------------
Iesire 9:
DA
3 3
399
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
199
198
197
196
195
194
193
192
191
190
189
188
187
186
185
184
183
182
181
180
179
178
177
176
175
174
173
172
171
170
169
168
167
166
165
164
163
162
161
160
159
158
157
156
155
154
153
152
151
150
149
148
147
146
145
144
143
142
141
140
139
138
137
136
135
134
133
132
131
130
129
128
127
126
125
124
123
122
121
120
119
118
117
116
115
114
113
112
111
110
109
108
107
106
105
104
103
102
101
100
99
98
97
96
95
94
93
92
91
90
89
88
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
------------------
Iesire 10:
NU
3 3
399
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
199
198
197
196
195
194
193
192
191
190
189
188
187
186
185
184
183
182
181
180
179
178
177
176
175
174
173
172
171
170
169
168
167
166
165
164
163
162
161
160
159
158
157
156
155
154
153
152
151
150
149
148
147
146
145
144
143
142
141
140
139
138
137
136
135
134
133
132
131
130
129
128
127
126
125
124
123
122
121
120
119
118
117
116
115
114
113
112
111
110
109
108
107
106
105
104
103
102
101
100
99
98
97
96
95
94
93
92
91
90
89
88
87
86
85
84
83
82
81
80
79
78
77
76
75
74
73
72
71
70
69
68
67
66
65
64
63
62
61
60
59
58
57
56
55
54
53
52
51
50
49
48
47
46
45
44
43
42
41
40
39
38
37
36
35
34
33
32
31
30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
====================
