XVII Всеукраїнська олімпіада з інформатики 2004 рік 4 етап
Перший тур
Вектори (100 балів)
На площині задано множину точок (x, y), де x та y – цілі, 1≤x≤M, 1≤y≤N. З кожної точки виходить рівно один з наступних векторів: (-1,-1), (-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1). Кожен вектор сполучає одну цілочисельну точку площини з іншою. Наприклад, якщо з точки (2, 5) виходить вектор (1, 1), то він сполучає цю точку з (3, 6), але не навпаки.
Послідовність з двох і більше точок площини a1, a2,…, ak назвемо циклом, якщо кожна точка ai сполучена вектором з ai+1 (1≤i≤k-1), та ak сполучена вектором з a1. Цикли вважаються різними, якщо вони відрізняються хоча б однією вершиною.
Завдання
Напишіть програму VECTORS, що за інформацією про вектори, що виходять з точок площини, знаходить кількість різних циклів.
Вхідні дані
Перший рядок вхідного файлу VECTORS.DAT містить два цілих числа N (1≤N≤100) та M (1≤M≤100). Кожен з наступних N рядків, містить M пар чисел (тобто, 2×M чисел). Пара x, що знаходиться у рядку y задає вектор у точці (x, y).
Вихідні дані
Єдиний рядок вихідного файлу VECTORS.SOL має містити ціле число – кількість циклів, утворених векторами.
Приклад вхідних та вихідних даних
VECTORS.DAT
|
VECTORS.SOL
|
2 4
-1 1 -1 1 -1 0 0 1
1 0 1 0 0 -1 0 -1
|
2
|
Var x,y: array[0..101,0..101] of integer;
a: array[0..101,0..101] of boolean;
i,j,ii,jj,co,xx,yy,n,m,nom,count: integer;
fi,fo: Text;
Begin
Assign(fi,'vectors.dat'); reset(fi);
Readln(fi,N,M);
For i:=1 to N do Begin
For j:=1 to M do Begin Read(fi,jj,ii); x[i,j]:=jj; y[i,j]:=ii;
a[i,j]:=true; yy:=i+ii; xx:=j+jj; a[yy,xx]:=true;
co:=0;
While (x[yy,xx]<>0) or (y[yy,xx]<>0) do Begin inc(co);
ii:=y[yy,xx]; jj:=x[yy,xx]; inc(xx,jj); inc(yy,ii);
if (yy=i) and (xx=j) Then Begin inc(count); Break End;
if co>m*n Then Break;
End;
End; Readln(fi);
End;
Assign(fo,'vectors.sol'); rewrite(fo); Writeln(fo,count); Close(fo);
End.
Погодні умови (100 балів)
Система рейсів авіакомпанії OlympAirways була спроектована таким чином, щоб з будь-якого аеропорту, що обслуговується авіакомпанією, можна було перелітіти до будь-якого іншого аеропорту, скориставшись, можливо, більше ніж одним рейсом. Кожен рейс сполучає два аеропорти, та виконується у обидва боки.
Існує проблема, що деякі рейси певний час можуть не виконуватись через погані погодні умови. Таким чином, ймовірно, що клієнт не зможе перелетіти з аеропорту A до B, користуючись лише літаками авіакомпанії OlympAirways. Для дослідження подібних ситуацій науковий відділ компанії ввів поняття числа вразливості зв’язку між парою аеропортів A та B. Це число дорівнює кількості рейсів авіакомпанії, відміна довільного з яких (при умові, що всі інші рейси виконуються у звичайному порядку) призведе до неможливості перельоту до аеропорту B з аеропорту A.
Завдання
Напишіть програму WEATHER, яка за інформацією про усі рейси, що виконуються авіакомпанією, визначає суму чисел вразливості зв’язку між усіма парами аеропортів.
Вхідні дані
Перший рядок вхідного файлу WEATHER.DAT містить ціле число N (1≤N≤100) – кількість аеропортів, що обслуговуються авіакомпанією. Другий рядок містить ціле число M (1≤M≤4950) – кількість рейсів, які виконуються авіакомпанією. Кожний з наступних M рядків визначає рейс, який представлено парою цілих чисел від 1 до N — номерами аеропортів, які він сполучає.
Вихідні дані
Єдиний рядок вихідного файлу WEATHER.SOL має містити ціле число – сумарне число вразливості зв’язку між усіма різними парами аеропортів A та B, таких, що номер A менше за номер B.
Приклад вхідних та вихідних даних
WEATHER.DAT
|
WEATHER.SOL
|
5
5
1 2
4 2
4 5
3 2
3 1
|
10
|
const MAXN = 100;
MAXM = 4950;
var ne:array[1..2*MAXM]of integer;
el:array[1..2*MAXM]of byte;
f:array[1..MAXN]of integer;
t,mn:array[1..MAXN]of byte;
x,y,i,N,M,time,h:integer;ans:longint;
o:text;
function rec(k,bk:integer):integer;
var x:integer;
tmp,ret:longint;
begin
ret:=0;
x:=f[k];time:=time+1;
t[k]:=time;mn[k]:=time;
while x<>0 do
begin
if t[el[x]] = 0 then
begin
tmp:=rec(el[x],k);
ret:=ret+tmp;
if mn[el[x]] = t[el[x]] then
begin
ans:=ans+tmp*(N-tmp);
end;
if mn[el[x]]<mn[k] then mn[k]:=mn[el[x]];
end
else if (el[x]<>bk)and(t[el[x]]<mn[k]) then mn[k]:=t[el[x]];
x:=ne[x];
end;
ret:=ret+1;
rec:=ret;
end;
begin
assign(o,'weather.dat');reset(o);
read(o,N,m);
for i:=1 to M do
begin
read(o,x,y);
inc(h);
el[h]:=y;ne[h]:=f[x];f[x]:=h;
inc(h);
el[h]:=x;ne[h]:=f[y];f[y]:=h;
end;
close(o);
rec(1,0);
assign(o,'weather.sol');rewrite(o);
writeln(o,ans);
close(o);
end.
спосіб2
const MaxN = 100;
MaxM = 10000;
type tedge = array[1..MaxM,1..2] of integer;
sedge = ^tedge;
var edge : sedge;
count : array[1..MaxN+1] of integer;
N,M : integer;
Res : longint;
a,b : array[1..maxN] of integer; {notes}
mark : array[1..maxN] of boolean;
numb : integer;
const fileinput = 'WEATHER.DAT';
fileoutput = 'WEATHER.SOL';
procedure ReadData; {Read data from file}
var i : integer;
begin
assign(input,fileinput);
reset(input);
readln(N);
readln(M);
for i:=1 to M do
begin
readln(edge^[2*i-1,1],edge^[2*i-1,2]);
edge^[2*i,1]:=edge^[2*i-1,2];
edge^[2*i,2]:=edge^[2*i-1,1]
end;
M:=M*2;
close(input)
end;
procedure SortData; {Sort edge's array with time O(M)}
var i : integer;
edges : sedge;
begin
fillchar(count,sizeof(count),0);
for i:=1 to M do
inc(count[edge^[i,1]]);
for i:=2 to succ(N) do
inc(count[i],count[pred(i)]);
new(edges);
for i:=1 to M do
begin
edges^[count[edge^[i,1]]]:=edge^[i];
dec(count[edge^[i,1]])
end;
dispose(edge);
edge:=edges
end;
procedure WriteData; {Write result}
begin
assign(output,fileoutput);
rewrite(output);
writeln(Res);
close(output)
end;
function Work(curent,parent : integer) : integer; {Depth search and calculating}
var i,s,r : integer;
begin
r:=1;
inc(numb);
a[curent]:=numb;
mark[curent]:=true;
b[curent]:=a[curent];
for i:=succ(count[curent]) to count[succ(curent)] do
if mark[edge^[i,2]] then
begin
if (edge^[i,2]<>parent) and (a[edge^[i,2]]<b[curent]) then
b[curent]:=a[edge^[i,2]]
end
else
begin
s:=Work(edge^[i,2],curent);
if b[edge^[i,2]]>a[curent] then
inc(Res,s*(N-s));
if b[edge^[i,2]]<b[curent] then
b[curent]:=b[edge^[i,2]];
inc(r,s)
end;
Work:=r
end;
procedure Calculate; {Calc result}
begin
Res:=0;
fillchar(a,sizeof(a),0);
b:=a;
fillchar(mark,sizeof(mark),false);
numb:=0;
Work(1,0)
end;
begin
new(edge);
ReadData;
SortData;
Calculate;
WriteData;
dispose(edge)
end.
Шоколадні плитки (100 балів)
Напевно, всім відомо, що шоколад корисний для мозку людини. Тому учасники національної олімпіади країни Олімпія принесли на тур багато плиток шоколаду, щоб ґеніальні ідеї приходили до них швидше. Але принесеного шоколаду виявилося забагато, і після туру в кабінеті залишилося N прямокутних плиток, які складалися з часток розмірами 1×1. Двоє учасників вирішили з’їсти частину шоколаду, що залишився, але, враховуючи те що протягом туру вони скоштували досить багато шоколаду, було вирішено зробити це у досить незвичайний ігровий спосіб, за наступними правилами.
Учасники виконують певні операції з шоколадними плитками по черзі: спочатку перший, потім другий, знову перший і т.д. У свою чергу учасник обирає плитку шоколаду, з якою він буде виконувати одну з наступних операцій:
1) Розламати плитку на дві; лінія розлому повинна проходити паралельно сторонам плитки та між частками.
2) Відламати та з’їсти довільний «рядок» або «стовпчик» плитки, який не є крайнім.
3) Відламати та з’їсти всі частки плитки, що знаходяться з краю, але щоб після цього від плитки залишилася принаймні одна частка (мінімальний розмір плитки, з якою може бути виконана така операція – 3×3).
Жодна з цих операцій не може бути виконана з плиткою 1×1, тому всі такі плитки залишаються до кінця гри. Програє той учасник, який у свою чергу не зможе зробити жодної з наведених операцій.
Завдання
Напишіть програму CHOCO, яка за інформацією про плитки шоколаду, що залишилися після туру, визначає кількість варіантів першого ходу першого учасника, які ґарантують йому виграш, при дотриманні виграшної стратегії в подальшому.
Вхідні дані
У першому рядку вхідного файлу CHOCO.DAT міститься ціле число N (1≤N≤100) – кількість шоколадних плиток. У другому рядку містяться N пар цілих чисел, кожна i-та з яких задає довжину та ширину i-ої плитки. Довжина та ширина не менші за 1 та не перевищують 100.
Вихідні дані
У єдиному рядку вихідного файлу CHOCO.SOL повинно міститися ціле число – кількість варіантів першого ходу першого учасника, які ґарантують йому виграш, при дотриманні оптимальної стратегії в подальшому.
Приклад вхідних та вихідних даних
CHOCO.DAT
|
CHOCO.SOL
|
1
3 3
|
3
|
Виграшні ходи першого учасника наступні: операція (3), операція (2) з другим рядком, та операція (2) з другим стовпчиком.
const MAXN = 101;
MAXX = 101;
type
PointType = record
X, Y : integer;
end;
var a:array[1..MAXN]of pointtype;
p:array[1..MAXX,1..MAXX]of byte;
t:array[0..16]of byte;
o:text;
N,i,j,k,z,max,s:integer;
_1,_2,_3,_4,_5:longint;
begin
assign(o,'CHOCO.DAT');reset(o);
read(o,N);max:=0;
for i:=1 to N do
begin
read(o,a[i].x,a[i].y);if a[i].x>max then max:=a[i].x;if a[i].y>max then max:=a[i].y;
end;
close(o);
p[1,1]:=0;{1x1 is 0}
for i:=1 to max do for j:=i to max do
begin
fillchar(t,sizeof(t),0);
for k:=1 to i-1 do
begin
t[p[k,j] xor p[i-k,j]]:=1;
end;
for k:=1 to j-1 do
begin
t[p[i,k] xor p[i,j-k]]:=1;
end;
for k:=1 to i-2 do
begin
t[p[k,j] xor p[i-k-1,j]]:=1;
end;
for k:=1 to j-2 do
begin
t[p[i,k] xor p[i,j-k-1]]:=1;
end;
if (i>=3)and(j>=3) then t[p[i-2,j-2]]:=1;
for k:=0 to 16 do if t[k] = 0 then
begin
p[i,j]:=k;
p[j,i]:=k;
break;
end;
end;
assign(o,'CHOCO.SOL');rewrite(o);
s:=0;
for z:=1 to N do s:=s xor p[a[z].x,a[z].y];
for z:=1 to N do
begin
i:=a[z].x;j:=a[z].y;
{}
for k:=1 to i-1 do
begin
if s xor p[i,j] xor p[k,j] xor p[i-k,j] = 0 then
begin
inc(_2);
end;
end;
for k:=1 to j-1 do
begin
if s xor p[i,j] xor p[i,k] xor p[i,j-k]=0 then
begin
inc(_1);
end;
end;
for k:=1 to i-2 do
begin
if s xor p[i,j] xor p[k,j] xor p[i-k-1,j]=0 then
begin
inc(_4);
end;
end;
for k:=1 to j-2 do
begin
if s xor p[i,j] xor p[i,k] xor p[i,j-k-1]=0 then
begin
inc(_3);
end;
end;
if (i>=3)and(j>=3) then
begin
if s xor p[i,j] xor p[i-2,j-2] = 0 then inc(_5);
end;
end;
writeln(o,_1+_2+_3+_4+_5);
close(o);
end.
спосіб 2
Var SG: array[1..100,1..100] of Integer;
fl,clear: array[0..100] of boolean;
Var i,j,k,Res,max,a,b,N,M,Count:integer;
fi,fo:Text;
Function Col:integer;
var a,b,i,ii,j,k:integer;
Begin
Reset(fi); Readln(fi,n);
For ii:=1 to n do Begin read(fi,a,b); fl:=clear; i:=a; j:=b;
For k:=1 to j-1 do If Res xor SG[i,j] xor SG[i,k] xor SG[i,j-k]=0 Then Inc(count);
For k:=1 to i-1 do If Res xor SG[i,j] xor SG[k,j] xor SG[i-k,j]=0 Then Inc(count);
For k:=1 to j-2 do If Res xor SG[i,j] xor SG[i,k] xor SG[i,j-k-1]=0 Then Inc(count);
For k:=1 to i-2 do If Res xor SG[i,j] xor SG[k,j] xor SG[i-k-1,j]=0 Then Inc(count);
if (i>2) and (j>2) Then If Res xor SG[i,j] xor SG[i-2,j-2]=0 Then Inc(count);
End;
Col:=Count;
End;
Begin
For i:=1 to 100 do For j:=i to 100 do Begin fl:=clear;
For k:=1 to j-1 do fl[SG[i,k] xor SG[i,j-k]]:=true;
For k:=1 to i-1 do fl[SG[k,j] xor SG[i-k,j]]:=true;
For k:=1 to j-2 do fl[SG[i,k] xor SG[i,j-k-1]]:=true;
For k:=1 to i-2 do fl[SG[k,j] xor SG[i-k-1,j]]:=true;
if (i>2) and (j>2) Then fl[SG[i-2,j-2]]:=true;
For k:=0 to 100 do if not fl[k] Then Break;
SG[i,j]:=k; SG[j,i]:=k;
End;
Assign(fi,'choco.dat'); Reset(fi); Readln(fi,n);
For i:=1 to n do Begin read(fi,a,b); Res:=Res xor SG[a,b] End;
Close(fi);
Assign(fo,'choco.sol'); ReWrite(fo); Writeln(fo,Col); Close(fo);
End.
