Cele mai bune solutii
pentru problema "Mincinosi"
(ziua1, problema2)
Autorul problemei " Mincinosi" este prof. Mihaela Giurgea, Liceul de Informatica Cluj
Punctaj Maxim : 30 puncte
Solutii :
Leu Tudor- Vrancea - 27 puncte
Filip Lucian - Bistrita Nasaud- 27 puncte;
Stefan Radu - Brasov- 24 puncte;
Prorocu Angel - Prahova- 22 puncte;
Mihai Florin - Botosani- 22 puncte.
Comisia Centrala
Fisierele de teste
Program realizat de elevul Leu Tudor - rezultat final : premiu II - 152 puncte
{$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y+}
{$M 65520,0,655360}
const ni='input.txt';
no='output.txt';
type nod=^art;
art=record
i:word;
t:byte;
urm:nod;
end;
var i,j,k,l,n:word;
a:array[1..4000] of byte;
ct:array[1..2] of word;
l1,l2:array[1..4000] of nod;
p,q,r:nod;
c:char;
procedure explore(j:word);
var p:nod;
begin
p:=l1[j];
while p<>nil do begin
if a[p^.i]=0 then begin a[p^.i]:=a[j];
k:=k+1;
if p^.t=0 then writeln(j,' c ',p^.i)
else writeln(p^.i,' c ',j);
explore(p^.i)
end;
p:=p^.urm;
end;
p:=l2[j];
while p<>nil do begin
if a[p^.i]=0 then begin a[p^.i]:=3-a[j];
k:=k+1;
if p^.t=0 then writeln(j,' m ',p^.i)
else writeln(p^.i,' m ',j);
explore(p^.i)
end;
p:=p^.urm;
end;
end;
procedure curata(i:word);
begin
p:=l1[i];
while p<>nil do begin
q:=p;p:=p^.urm;dispose(q);
end;
p:=l2[i];
while p<>nil do begin
q:=p;p:=p^.urm;dispose(q);
end;
end;
procedure citeste_rezolva_si_scrie;
begin
assign(input,ni);reset(input);
assign(output,no);rewrite(output);
readln(n);
writeln(n-1);
fillchar(a,sizeof(a),0);
for i:=1 to n do begin l1[i]:=nil;l2[i]:=nil end;
if seekeof(input) then begin writeln('Date insuficiente');halt end;
k:=1;
readln(i,c,c,j);
a[i]:=1;
if c='c' then a[j]:=1
else a[j]:=2;
writeln(i,' ',c,' ',j);
while not seekeof(input) do begin
readln(i,c,c,j);
if ([a[i],a[j]]<=[1,2]) then
else
if (a[j]=0) and (a[i] in [1,2]) then begin
k:=k+1;
writeln(i,' ',c,' ',j);
if c='c' then a[j]:=a[i]
else a[j]:=3-a[i];
explore(j);
end
else
if (a[i]=0) and (a[j] in [1,2]) then begin
k:=k+1;
writeln(i,' ',c,' ',j);
if c='c' then a[i]:=a[j]
else a[i]:=3-a[j];
explore(i);
end
else begin
if c='c' then begin
new(p);p^.i:=j;p^.t:=0;p^.urm:=l1[i];l1[i]:=p;
new(p);p^.i:=i;p^.t:=1;p^.urm:=l1[j];l1[j]:=p
end
else begin
new(p);p^.i:=j;p^.t:=0;p^.urm:=l2[i];l2[i]:=p;
new(p);p^.i:=i;p^.t:=1;p^.urm:=l2[j];l2[j]:=p;
end;
end;
end;
if k<n-1 then begin rewrite(output);
writeln('Date insuficiente');
exit;
end;
ct[1]:=0;ct[2]:=0;
for i:=1 to n do ct[a[i]]:=ct[a[i]]+1;
if ct[1]>ct[2] then k:=1 else k:=2;
j:=0;
for i:=1 to n do
if a[i]=k then begin
if (j<>0) and (j mod 40=0) then writeln;
write(i,' ');
j:=j+1;
end;
writeln;writeln;
j:=0;k:=3-k;
for i:=1 to n do
if a[i]=k then begin
if (j<>0) and (j mod 40=0) then writeln;
write(i,' ');
j:=j+1;
end;
for i:=1 to n do begin
curata(i);
end;
end;
begin
citeste_rezolva_si_scrie
end.
Program realizat de Comisia Centrala a Olimpiadei Nationale de Informatica
{$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q-,R+,S+,T-,V+,X+,Y+}
{$M 16384,0,655360}
uses crt;
var a: array [1..8000,1..2] of integer;
b: array [1..8000,1..2] of -1..1;
c:array[1..4000] of -1..1;
k,n,i,j,x1,x2,nr1,nr2:integer;
f,g: text;
cc:string[3];
cinste:-1..1;
gata:boolean;
begin
{clrscr;}
assign(f,'input.txt');
reset (f);
assign(g,'output.txt');
rewrite(g);
read(f,n);
k:=0; {nr. de raspunsuri}
while not seekeof(f) do
begin
readln(f,x1,cc,x2);
inc(k);
a[k,1]:=x1;
a[k,2]:=x2;
if pos('c',cc)<>0 then b[k,1]:=1
else b[k,1]:=-1;
end;
for i:=1 to k do b[i,2]:=-1;
for i:=1 to n do c[i]:=0;
c[1]:=1;
repeat
gata:=true;
for i:=1 to k do if b[i,2]=-1 then
if (c[a[i,2]]=0) and (c[a[i,1]]<>0) then
begin b[i,2]:=1;
c[a[i,2]]:=b[i,1]* c[a[i,1]];
gata:=false;
end else
if (c[a[i,2]]<>0) and (c[a[i,1]]=0) then
begin b[i,2]:=1;
c[a[i,1]]:=b[i,1]* c[a[i,2]];
gata:=false;
end
until gata;
nr1:=0;
nr2:=0;
for i:=1 to n do if c[i]=1 then inc(nr1)
else if c[i]=-1 then inc(nr2);
if nr1+nr2<>n then write(g,'Date insuficiente')
else
begin writeln(g,n-1);
for i:=1 to k do
if b[i,2]=1 then if b[i,1]=1 then writeln(g,a[i,1],' c ',a[i,2])
else writeln(g,a[i,1],' m ',a[i,2]);
if nr1> nr2 then cinste:=1
else cinste:=-1;
nr1:=1;
for i:=1 to n do if c[i]=cinste then begin
write(g,i,' ');
if nr1 mod 40 =0 then writeln(g);
inc(nr1);
{write(g,i,' ');}
end;
if (nr1-1) mod 40 <>0 then writeln(g);
writeln(g);
nr1:=1;
for i:=1 to n do if c[i]<>cinste then begin
write(g,i,' ');
if nr1 mod 40 =0 then writeln(g);
inc(nr1);
{write(g,i,' ');}
end;
end;
close(f);
close(g);
end.
Fisierele de teste :
Test 1 :
8
1 c 2
3 c 4
2 c 3
1 c 3
4 c 5
6 c 7
8 c 7
7 c 8
Test 2 :
10
1 m 8
1 m 6
1 c 3
1 c 5
2 c 7
5 m 8
4 c 10
1 c 7
9 m 4
10 m 1
5 m 4
Test 3 :
10
1 m 8
1 m 6
1 c 3
1 c 5
2 c 7
1 c 7
9 m 4
10 m 1
Test 4 :
50
1 c 3
48 c 46
46 c 44
44 c 42
42 c 40
40 c 38
38 c 36
40 c 36
36 c 34
34 c 32
32 c 30
30 c 28
28 c 26
2 c 4
4 c 6
6 c 8
8 c 10
10 c 12
12 c 14
14 c 16
16 c 18
35 c 24
18 c 20
31 c 33
33 c 35
35 c 37
37 c 39
39 c 41
43 c 41
45 c 47
49 c 47
20 c 22
22 c 24
24 c 26
9 m 20
45 m 10
2 c 1
1 c 5
20 c 3
7 c 9
17 c 19
9 c 11
11 c 13
13 c 15
17 m 2
21 c 19
3 c 50
23 c 21
25 c 23
27 c 29
50 c 3
27 m 4
Test 5 :
3
1 c 2
2 c 3
1 c 3
3 c 1
Test 6 :
200
1 c 2
2 c 3
3 c 4
4 c 5
5 c 6
6 c 7
7 c 8
8 c 9
9 c 10
10 c 11
11 c 12
12 c 13
13 c 14
14 c 15
15 c 16
16 c 17
17 c 18
18 c 19
19 c 20
20 c 21
21 c 22
22 c 23
23 c 24
24 c 25
25 c 26
26 c 27
27 c 28
28 c 29
29 c 30
30 c 31
31 c 32
32 c 33
33 c 34
34 c 35
35 c 36
36 c 37
37 c 38
38 c 39
39 c 40
40 c 41
41 c 42
42 c 43
43 c 44
44 c 45
45 c 46
46 c 47
47 c 48
48 c 49
49 c 50
50 c 51
51 c 52
52 c 53
53 c 54
54 c 55
55 c 56
56 c 57
57 c 58
58 c 59
59 c 60
60 c 61
61 c 62
62 c 63
63 c 64
64 c 65
65 c 66
66 c 67
67 c 68
68 c 69
69 c 70
70 c 71
71 c 72
72 c 73
73 c 74
74 c 75
75 c 76
76 c 77
77 c 78
78 c 79
79 c 80
80 c 81
81 c 82
82 c 83
83 c 84
84 c 85
85 c 86
86 c 87
87 c 88
88 c 89
89 c 90
90 c 91
91 c 92
92 c 93
93 c 94
94 c 95
95 c 96
96 c 97
97 c 98
98 c 99
99 c 100
100 c 101
101 c 102
102 c 103
103 c 104
104 c 105
105 c 106
106 c 107
107 c 108
108 c 109
109 c 110
110 c 111
111 c 112
112 c 113
113 c 114
114 c 115
115 c 116
116 c 117
117 c 118
118 c 119
119 c 120
120 c 121
121 c 122
122 c 123
123 c 124
124 c 125
125 c 126
126 c 127
127 c 128
128 c 129
129 c 130
130 c 131
131 c 132
132 c 133
133 c 134
134 c 135
135 c 136
136 c 137
137 c 138
138 c 139
139 c 140
140 c 141
141 c 142
142 c 143
143 c 144
144 c 145
145 c 146
146 c 147
147 c 148
148 c 149
149 c 150
150 c 151
151 c 152
152 c 153
153 c 154
154 c 155
155 c 156
156 c 157
157 c 158
158 c 159
159 c 160
160 c 161
161 c 162
162 c 163
163 c 164
164 c 165
165 c 166
166 c 167
167 c 168
168 c 169
169 c 170
170 c 171
171 c 172
172 c 173
173 c 174
174 c 175
175 c 176
176 c 177
177 c 178
178 c 179
179 c 180
180 c 181
182 c 183
183 c 184
184 c 185
185 c 186
186 c 187
187 c 188
188 c 189
189 c 190
190 c 191
191 c 192
192 c 193
193 c 194
194 c 195
195 c 196
196 c 197
197 c 198
198 c 199
199 c 200
2 m 185
5 c 10
195 c 198
Test 7 :
8
1 c 2
3 c 4
2 c 3
1 c 3
4 c 5
6 c 7
8 c 7
7 c 8
5 c 6