Cele mai bune solutii
pentru problema "Ciocniri"
(ziua1, problema2)
Punctaj Maxim : 40 puncte
Solutii :
Carstoiu Catalin - Gorj - 15 puncte
Danila Mihai - Suceava- 15 puncte;
Cerba Dan - Salaj- 15 puncte;
Andronic Ovidiu Ioan - Neamt- 15 puncte;
Grigoras Costin - Constanta- 15 puncte;
Prodan Victor - Galati- 15 puncte;
Reghis Ovidiu - Timis- 15 puncte;
Szasz Janos - Covasna- 15 puncte;
Stroe Mihai - Bucuresti- 15 puncte;
Ivan Cristian - Dambovita- 15 puncte.
Comisia Centrala
Fisierele de teste
Program realizat de elevul Cristoiu Ctalin - rezultat final : premiu II - 153 puncte
{$A+,B-,D+,E-,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y+}
{$M 16384,0,655360}
program p2;
uses crt;
const
max=250;
numein='input.txt';
numeout='output.txt';
dx:array[1..4]of shortint=(1,-1,-1,1);
dy:array[1..4]of shortint=(1,1,-1,-1);
pow:array[1..4,1..4]of byte=((1,0,0,0),(1,1,0,0),(0,1,1,1),(1,0,0,1));
type
bila=record
x,y:integer;
d:byte;
end;
var
b,b1,b2:array[1..max]of bila;
n,m,k,k1:byte;
t,timp:word;
procedure citire;
var
f:text;
begin
assign(f,numein);
reset(f);
readln(f,m,n);
readln(f,t);
k:=0;
while not seekeof(f) do
begin
inc(k);
read(f,b[k].x,b[k].y,b[k].d);
end;
close(f);
end;
procedure calcnewcoords;
var
i,xc,yc,d:byte;
begin
for i:=1 to k do
begin
xc:=b[i].x; yc:=b[i].y; d:=b[i].d;
if (yc=0) then
if d=3 then d:=2
else
if d=4 then d:=1;
if xc=0 then
if d=2 then d:=1
else
if d=3 then d:=4;
if yc=n then
if d=1 then d:=4
else
if d=2 then d:=3;
if xc=m then
if d=1 then d:=2
else
if d=4 then d:=3;
inc(xc,dx[d]);
inc(yc,dy[d]);
b1[i].x:=xc; b1[i].y:=yc; b1[i].d:=d;
end;
end;
procedure scoatebum;
var
i,j,di,dj:byte;
ok:boolean;
begin
k1:=0;
for i:=1 to k do
begin
ok:=true;
for j:=1 to k do
if i<>j then
if (b1[i].x=b1[j].x)and(b1[i].y=b1[j].y)then
begin
di:=b1[i].d; dj:=b1[j].d;
ok:=pow[di,dj]=1;
if not ok then break;
end;
if ok then
begin
inc(k1);
b2[k1]:=b1[i];
end;
end;
end;
procedure scrie;
var
f:text;
i:byte;
begin
assign(f,numeout);
rewrite(f);
writeln(f,k);
for i:=1 to k do
writeln(f,b[i].x,' ',b[i].y);
close(f);
end;
begin
citire;
for timp:=1 to t do
begin
calcnewcoords;
scoatebum;
move(b2,b,k1*sizeof(bila));
k:=k1;
end;
scrie;
end.
Program realizat de Comisia Centrala a Olimpiadei Nationale de Informatica
program ciocniri_fatale;
uses dos;
type bila=record
x,y,d,p:byte;
end;
var a,ultima:array[1..250] of bila;
r:array[1..4] of byte;
f,g:text;
m,n,k,i,j,s,nr,contor:byte;
t,timp,tu,perioada:word;
nrp:longint;
min,sec,ss,h:word;
function SeRepetaConfiguratia:boolean;
var q:byte;
ok:boolean;
begin
ok:=true; q:=1;
while (ok) and (q<=k) do
begin
if a[q].p=0
then if (a[q].x<>ultima[q].x)or (a[q].y<>ultima[q].y) or
(a[q].d<>ultima[q].d)
then ok:=false;
q:=q+1;
end;
SeRepetaConfiguratia:=ok;
end;
begin
gettime(h,min,sec,ss);
writeln(h,' ',min,' ',sec,' ',ss);
assign(f,'t44.');
reset(f);
readln(f,m,n);
readln(f,t);
k:=0; perioada:=1;
repeat
k:=k+1;
readln(f,a[k].x,a[k].y,a[k].d);
until seekeof(f);
close(f);
assign(f,'output.txt'); rewrite(f);
timp:=0; nr:=1; nrp:=0;
contor:=k;
ultima:=a; tu:=0;
while timp<t do
begin
for i:=1 to k do
if a[i].p=0 then
case a[i].d of
1: begin
a[i].x:=a[i].x+1;
a[i].y:=a[i].y+1;
end;
2: begin
a[i].x:=a[i].x-1;
a[i].y:=a[i].y+1;
end;
3: begin
a[i].x:=a[i].x-1;
a[i].y:=a[i].y-1;
end;
4: begin
a[i].x:=a[i].x+1;
a[i].y:=a[i].y-1;
end;
end;
for i:=1 to k-1 do
if a[i].p=0 then
begin
s:=0;
for j:=i+1 to k do
if (a[i].x=a[j].x) and (a[i].y=a[j].y) and
(a[i].p=0) and (a[j].p=0) then
begin
s:=s+1;
r[s]:=j;
end;
case s of
1: begin
if a[i].d+a[r[1]].d in [4,6] then
begin
a[i].p:=1; dec(contor);
a[r[1]].p:=1;
end
else
begin
if a[i].d=3 then
a[r[1]].p:=1;
if a[r[1]].d=3 then
a[i].p:=1;
if a[i].d=2 then
a[r[1]].p:=1;
if a[r[1]].d=2 then
a[i].p:=1;
if a[i].d=4 then
a[r[1]].p:=1;
if a[r[1]].d=4 then
a[i].p:=1;
dec(contor);
end;
ultima:=a; tu:=timp;
end;
2: begin
dec(contor,2);
if a[i].d+a[r[1]].d in [4,6] then
begin
a[i].p:=1;
a[r[1]].p:=1;
end
else
if a[i].d+a[r[2]].d in [4,6] then
begin
a[i].p:=1;
a[r[2]].p:=1;
end
else
if a[r[1]].d+a[r[2]].d in [4,6] then
begin
a[r[1]].p:=1;
a[r[2]].p:=1;
end;
ultima:=a; tu:=timp;
end;
3: begin
a[i].p:=1;
for j:=1 to 3 do
a[r[j]].p:=1;
ultima:=a; tu:=timp; dec(contor,4);
end;
end;
end;
for i:=1 to k do
if a[i].p=0 then
begin
if a[i].y=0 then
a[i].d:=5-a[i].d;
if a[i].x=m then
begin
if a[i].d=1 then
a[i].d:=2;
if a[i].d=4 then
a[i].d:=3;
end;
if a[i].y=n then
begin
if a[i].d=1 then
a[i].d:=4;
if a[i].d=2 then
a[i].d:=3;
end;
if a[i].x=0 then
begin
if a[i].d=3 then
a[i].d:=4;
if a[i].d=2 then
a[i].d:=1;
end;
end;
if (SeRepetaConfiguratia)
then perioada:=timp+1-tu;
if perioada>1
then
timp:=timp+perioada*((t-timp) div perioada);
timp:=timp+1;
inc(nrp);
if contor=0 then timp:=t;
for i:=1 to k do
if a[i].p=0 then
write(f,a[i].x,'-',a[i].y,'-',a[i].d,' ');
writeln(f);
end;
s:=0;
for i:=1 to k do
if a[i].p=0 then
s:=s+1;
writeln(f,s);
if s>0 then
for i:=1 to k do
if a[i].p=0 then
writeln(f,a[i].x,' ',a[i].y);
gettime(h,min,sec,ss);
writeln(h,' ',min,' ',sec,' ',ss);
writeln(nrp);
close(f);
end.
Fisierele de teste :
Test 1 :
3 3
13
2 1 4
2 2 1
Test 3 :
3 3
10
0 1 1
1 2 1
2 3 4
3 2 3
2 1 3
1 0 2
Test 4 :
3 3
60000
0 0 1
0 2 4
2 2 3
2 0 2
Test 5 :
6 7
100
1 1 1
3 1 2
5 1 2
1 3 4
3 3 4
5 3 3
1 4 1
3 4 1
5 4 2
1 6 4
3 6 3
5 6 3
2 5 4
Test 6 :
250 250
65000
231 88 3
247 96 3
21 170 1
205 62 1
175 82 1
189 28 1
169 10 3
195 20 4
108 187 1
59 173 3
26 44 2
16 198 2
156 28 1
57 43 1
36 160 4
17 128 2
217 230 3
143 168 2
90 226 4
158 67 3
63 197 3
21 220 2
173 212 1
5 54 3
37 90 4
23 117 2
110 57 3
101 46 3
174 230 4
89 140 4
37 162 1
46 206 2
173 210 2
118 147 3
37 214 2
2 205 2
192 116 3
27 61 3
198 123 4
76 241 4
232 248 3
157 97 1
161 147 1
150 28 4
233 93 1
228 10 2
31 90 2
27 70 3
28 114 3
125 220 3
103 51 1
45 91 3
129 190 2
92 213 3
134 225 2
175 78 3
127 155 3
218 206 2
14 94 1
130 180 1
68 169 3
187 94 2
179 159 1
118 28 2
199 215 2
59 42 2
225 157 1
150 121 4
59 96 1
156 117 1
231 51 1
150 189 4
218 100 4
196 197 3
92 99 2
162 68 4
226 66 1
154 187 1
9 176 3
26 144 3
229 176 4
89 130 1
60 31 4
185 229 1
176 52 2
44 143 2
114 15 1
121 79 1
196 112 1
144 131 3
164 107 2
229 59 3
205 158 2
113 77 4
188 121 4
217 0 2
181 6 1
233 246 1
245 81 1
233 153 1
69 9 3
47 225 3
50 243 2
194 164 1
94 165 2
1 12 4
111 133 4
124 83 4
96 30 4
179 192 2
25 221 3
108 216 4
29 9 4
184 44 4
162 202 4
38 205 3
116 115 2
245 2 2
217 144 4
155 23 2
174 134 2
177 179 4
201 94 4
159 149 1
225 189 1
167 234 3
1 26 1
30 214 4
46 243 2
145 209 2
212 101 4
216 31 2
125 159 4
87 215 2
211 246 4
179 173 2
65 243 4
124 195 1
90 137 2
112 109 4
41 7 3
180 71 4
26 247 2
179 234 2
195 213 2
153 96 3
68 133 4
199 136 3
222 27 4
221 85 3
69 17 3
29 80 1
163 21 4
167 243 2
101 214 2
186 180 4
8 190 3
180 134 2
205 71 4
64 97 1
19 85 1
155 123 1
202 120 3
196 137 4
245 162 1
70 217 2
34 202 2
15 178 2
10 10 3
84 10 1
232 162 2
206 201 3
248 213 2
70 47 1
105 0 2
216 227 1
38 135 4
90 160 4
142 183 4
139 37 3
130 4 3
160 232 2
66 141 4
190 129 1
195 207 1
183 84 1
172 33 3
78 156 4
175 34 2
20 25 4
24 176 1
138 159 2
129 200 1
217 167 3
245 72 2
143 241 3
58 207 2
201 162 1
112 104 1
56 97 2
235 25 2
128 89 1
71 171 4
240 183 1
141 49 3
48 15 3
1 202 3
8 58 4
174 133 4
188 93 1
206 243 2
207 65 4
90 78 4
160 88 2
121 118 2
21 6 4
224 248 1
18 77 1
53 33 1
110 97 2
78 36 4
93 81 4
83 233 4
138 239 4
201 6 2
132 7 4
79 181 1
163 10 4
60 43 3
94 33 4
57 41 3
96 60 2
219 225 3
221 171 2
229 32 3
49 149 2
134 116 1
97 49 2
95 42 3
165 172 2
19 64 3
232 247 2
39 238 1
133 21 2
217 95 2
228 99 3
168 149 1
102 4 4
132 83 3
191 206 4
Test 7 :
6 7
60000
1 1 1
3 1 2
5 1 2
1 3 4
3 3 4
5 3 3
1 4 1
3 4 1
5 4 2
1 6 4
3 6 3
5 6 3
2 5 4