Олімпіади з інформатики: грудня 2014

неділя, 14 грудня 2014 р.

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), але не навпаки.

Послідовність з двох і більше точок площини a₁, a₂,…, a_k назвемо циклом, якщо кожна точка a_i сполучена вектором з a_i₊₁ (1≤i≤k-1), та a_k сполучена вектором з a₁. Цикли вважаються різними, якщо вони відрізняються хоча б однією вершиною.

Завдання

Напишіть програму 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.

2014 рік. Задачі 2 етапу Вінницької олімпіади з інформатики 8-9 клас

Задачі 2 етапу Вінницької олімпіади з інформатики

за 14 грудня 2014 року 8-9 клас

2. Задача Forecast. Василько та Юлія грають в таку гру. Спочатку кожен записує на папері свій прогноз – число від 1 до 6. Потім вони кидають гральний кубик з числами від 1 до 6 на гранях. Чий прогноз виявляється ближчим до того числа, що випало, той і переміг. Треба написати програму для визначення переможця.

Технічні умови. Програма Forecast читає з пристрою стандартного введення три числа через пропуски (пробіли) – прогноз Василька, Юлі та результат кидання кубика. Програма виводить “V”, якщо переміг Василько, “J” якщо Юлія або ”D” – якщо прогноз обох однаково близький до результату (тобто переможця виявити неможливо.

Приклади

Введення	Виведення
3 4 5 1 6 2 4 4 3	J V D

Program Forecast

var a,b,c:integer;

BEGIn

read(a,b,c);

if ((abs(c-a))>(abs(c-b))) then write('J');

if ((abs(c-a))<(abs(c-b))) then write('V');

if ((abs(c-a))=(abs(c-b))) then write('D');

end.

Задачі 2 етапу Вінницької олімпіади з інформатики

За 14 грудня 2014 року 8-9 клас

3. Задача Сandy. На вулиці Сонячній треба побудувати 3 будинки, з відомою кількістю поверхів у кожному. Але краєвид буде зіпсовано, якщо кількість поверхів у будь-яких двох з них відрізняється більше, ніж на Z. Архітектор може зменшити в якомусь з будинків кількість поверхів на 1, але обов’язково при цьому збільшити на 1 поверх в іншому, зробивши новий проект. Потрібно зробити так, аби краєвид не був зіпсований.

Технічні умови. Програма Сandy читає з пристрою стандартного введення чотири невід'ємних цілих числа b₁, b₂, b₃ , Z через пропуск, кожне з них не більше за 10⁹ - кількість поверхів у кожному з будинків згідно першого проекту та дозволену різницю між кількістю поверхів. Програма виводить одне число – мінімальну к-сть перероблених проектів, Якщо зберегти краєвид неможливо, вивести - 1.

Приклад

Введення	Виведення
1 6 3 2	2

Program Candy;

var a,b,c,z,min,max,k,mini,maxi : longint;

mas : array [1..3] of integer;

BEGIN

read(a,b,c,z);

k:=0;

mas[1]:=a; mas[2]:=b; mas[3]:=c;

while ( (abs(mas[1]-mas[2]) > z) or (abs(mas[1]-mas[3]) > z) or (abs(mas[2]-mas[3]) > z) ) do

begin

if mas[1]>=mas[2] then begin

max:=mas[1]; maxi:=1; min:=mas[2]; mini:=2; end

else begin

max:=mas[2]; maxi:=2; min:=mas[1]; mini:=1; end;

if mas[3]>max then begin max:=c; maxi:=3; end;

if mas[3]<min then begin min:=c; mini:=3; end;

dec(max); inc(min); inc(k); mas[mini]:=min;

mas[maxi]:=max; end;

writeln(k); readln; END.

Задачі 2 етапу Вінницької олімпіади з інформатики

За 14 грудня 2014 року 8-9 клас

1. Newprize. Три учні за перемогу у конкурсі повинні розіграти між собою один приз – одна запакована коробка з призом. Є ще 2 такі самі, але порожніх коробки. Спочатку кожен має по одній коробці. Потім вони починають швиденько обмінюватися коробками один з другим у певному порядку. Переможцем стає той, у кого опиниться коробка з призом після усіх обмінів.

Технічні умови. Програма читає з пристрою стандартного введення два числа P та K (1 <= P <= 3, 0 <= K <= 100), що відповідно вказують на номер учня, що спочатку отримав коробку з премією та кількість обмінів а далі K пар чисел а і b (1 <= a, b <= 3, a <> b) - номери учнів, що мінялися коробками на даному кроці. Програма виводить одне число – номер переможця, якому дістався коробка з премією.

Приклад

Введення	Виведення
1 5 1 2 1 3 3 2 13 12	2

Розв’язання

var a,v,u: integer;

b: array [1..100,1..3] of integer; c: array [1..100,1..3] of integer; x, z,f, p,k,i,j: integer;

begin writeln(' '); read(p, k);

for i:=1 to k do

for j:=1 to 3 do begin

c[i,j]:=0; b[i,j]:=0; end;

for i:=1 to k do begin read(x, z);

if x=1 then c[i,1]:=1; if x=2 then c[i,2]:=2; if x=3 then c[i,3]:=3;

if z=1 then b[i,1]:=1; if z=2 then b[i,2]:=2; if z=3 then b[i,3]:=3; end;

for i:=1 to k do begin v:=c[i,1]+c[i,2]+c[i,3]; u:=b[i,1] +b[i,2]+b[i,3];

if v=p then p:=u else if (v<>p)and(u<>p) then p:=p else if u=p then p:=c[i,1]+c[i,2]+c[i,3]; end; write(p); writeln; end.

Задачі 2 етапу Вінницької олімпіади з інформатики

За 14 грудня 2014 року 8-9 клас

4.Задача Songs. Петро записав на листочку кількість пісень у своїй фонотеці, але трішки прибрехав - хай друзі заздрять. Та совість замучила, і він зробив запис (знову не дуже чесний ;-) коротшим на одну цифру. Але викреслив одну цифру так, щоб число, яке залишилося, було найбільшим.

Технічні умови. Програма Songs читає з пристрою стандартного введення одне ціле значення n (10<=n<=99999), і виводить на пристрій стандартного виведення число без однієї цифри (це число має бути найбільшим серед усіх можливих варіантів закреслень цифри).

Приклади

Введення	Виведення
431 138	43 38

Олімпіади з інформатики

неділя, 14 грудня 2014 р.

за усі роки Всеукраїнських олімпіад з інформатики 1998-2007 рр

Задачі Всеукраїнських олімпіад з інформатики 1998-2007 рр

XVII Всеукраїнська олімпіада з інформатики 2004 рік 3 етап

2014 рік. Задачі 2 етапу Вінницької олімпіади з інформатики 8-9 клас

неділя, 14 грудня 2014 р.

за усі роки Всеукраїнських олімпіад з інформатики 1998-2007 рр

Задачі Всеукраїнських олімпіад з інформатики 1998-2007 рр

XVII Всеукраїнська олімпіада з інформатики 2004 рік 3 етап

2014 рік. Задачі 2 етапу Вінницької олімпіади з інформатики 8-9 клас

неділя, 14 грудня 2014 р.