УМОВИ ЗАДАЧ ОЛІМПІАДИ
ЗАДАЧІ З ПРОГРАМУВАННЯ
Задача Ticket2. У місті Старопрограмістську є
усього 2 види міського транспорту: метро, де квиток на одну поїздку коштує 3
біта (ось така там грошова одиниця) і автобус, квиток на поїздку у якому коштує
2 біта. Можна придбати проїзний квиток на обидва види транспорту за 60
біт, на метро – за 40 біт, а на автобус – за 30 біт. Усі проїзні квитки дають
право на необмежену кількість поїздок протягом місяця. Яку
мінімальну суму витратить на міський транспорт за місяць житель міста
програміст Байтученко, якщо протягом місяця він планово має виконувати x
поїздок на метро та y поїздок на автобусі?
Технічні умови. Програма Ticket2 читає з пристрою
стандартного введення два числа x та y через пропуск (0 <=x;
y<= 100). Програма виводить на пристрій стандартного виведення мінімально
можливу суму місячних витрат Байтученка (зрозуміло, у бітах).
Приклад
Введення
Виведення
9
30
57
Програма мовою Паскаль
PROGRAM Ticket2;
var
x,y,s1,s2,sum: integer;
begin
read(x,y);
s1:=x*3;
s2:=y*2;
if s1>=
40
then s1:=40;
if
s2>=30 then s2:=30;
if s1+s2>=60 then sum:=60
else
sum:=s1+s2;
writeln(sum);
end.
Задача Clock2015. У вінницькому магазині-музеї
«Колоніальні товари. Пан Заваркін та сини» є N
годинників. Відомо, що К з них показують неправильний
час, а покази решти – правильні. Потрібно написати програму, яка
дозволить відвідувачу магазина дізнатися точний час.
Технічні
умови. Програма Clock2015 читає
з пристрою стандартного введення 2 числа N і K (0
<= K <= N<= 1000), а далі N рядків по 2
числа – покази відповідного годинника. Перше число - години (0-23),
друге – хвилини (0-59). Всі числа розділено пропусками. Програма виводить на
пристрій стандартного виведення два числа – точний час у годинах та
хвилинах. Якщо однозначно точний час знайти неможливо – виведіть
-1.
Приклад
Введення
Виведення
5
3
13
20
13 20
20 13
9 00
13 20
13 21
20 13
9 00
13 20
13 21
Програма мовою Паскаль
var
i,m,k,res,n,p,j,r,h:longint;
a:array[0..10000] of longint;
begin
read(n,k);
p:=n-k;
for i:= 1 to n do
begin
readln(h,m);
m:=m+h*60;
inc(a[m]);
end;
for j:= 0 to 10000 do
if a[j]=p then
begin
inc(r);
res:=j;
end;
if r=1 then begin
write (res div 60,' ' );
if res mod 60 <10 then write(0,res mod 60)
else write(res mod 60);
end
else write(-1);
end.
Задача Money. У вас є достатня кількість
монет 3-х номіналів a, b та c.
Потрібно розрахуватися (тобто віддати продавцю) задану суму N максимально
можливою кількістю монет. Монет продавцю потрібно дати не менше, ніж 2.
Технічні умови. Програма Money читає
з пристрою стандартного введення через пропуск чотири цілих числа N,
a, b, c (1 ≤ N, a, b, c ≤ 40000) – N – задана сума і a,
b, c – наявні номінали монет. Числа a, b і c можуть
збігатися.
Вихідні дані: Виведіть одне число - максимально
можливу кількість монет. Гарантується, що зазначену суму можна виплатити
завжди.
Приклади
Введення
Виведення
Пояснення:
5 5 3 2
2
потрібно дати 2 монети: одна з них
2, друга 3.
7 5 5 2
2
потрібно дати 2 монети: одна з них
5, друга 2.
var
g:array[-40000..41000] of LONGINT ;
n,a,b,c,k,v1,v2,v3,i:longint;
begin
read(n,a,b,c);
for i:= -n to n do g[i]:=0;
K:=0;
g[a]:=1;
g[b]:=1;
g[c]:=1;
for i:= 0 to n do
if (i>=a) or (i>=b) or (i>=c) then
begin
if (g[i-a]+1>g[i]) and (g[i-a]<>0)
and(i>=a) then g[i]:=g[i-a] +1;
if (g[i-b]+1>g[i]) and (g[i-b]<>0)and (i>=b) then g[i]:=g[i-b] +1;
if (g[i-c]+1>g[i]) and (g[i-c]<>0) and (i>=c) then g[i]:=g[i-c] +1;
end;
write(g[n]);
end.
Задача Castle.
Стародавній
замок має прямокутну форму. Замок містить щонайменше дві кімнати. Підлогу замка
можна умовно поділити на M x N клітин. Кожна
така клітинка містить «0» або «1», які задають порожні ділянки та стіни замку
відповідно. Напишіть програму, яка б знаходила площу найбільшої кімнати, яку
можна утворити шляхом видалення стіни або її частини, тобто, замінивши лише
одну «1» на «0». Видаляти зовнішні стіни заборонено.
Технічні умови. Програма Castle читає з
пристрою стандартного введення «план замку». Перший рядок містить ціле
число M, другий – ціле число N –
кількість рядків та кількість стовпчиків (3 ≤ M ≤ 1000,
3 ≤ N ≤ 1000). M наступних рядків
містить по N нулів або одиниць, що йдуть поспіль (без
пробілів). Перший та останній рядок, а також перший та останній стовпчик
формують зовнішні стіни замку і складаються лише з одиниць. Програма виводить
на пристрій площу найбільшої кімнати, яка утвориться в разі
видалення внутрішньої стіни.
Приклади:
Введення Виведення
6
8
11111111
10011001
10011001
11111001
10101001
11111111 10
8
11111111
10011001
10011001
11111001
10101001
11111111 10
9
12
111111111111
101001000001
111001011111
100101000001
100011111101
100001000101
111111010101
100000010001
111111111111
12
111111111111
101001000001
111001011111
100101000001
100011111101
100001000101
111111010101
100000010001
111111111111
38
Програма мовою Паскаль
var n,m,i,j,color,sum,max:longint;
c:char;
a:array[-1..1001,-1..1001] of longint;
s: longint;
procedure dep(x,y,c:longint);
begin
inc(s) ;
a[x,y]:=c;
if (a[x,y+1]<>c)and
(a[x,y+1]<>-1) then dep(x,y+1,c);
if( a[x,y-1]<>c)and
(a[x,y-1]<>-1) then dep(x,y-1,c);
if (a[x+1,y]<>c) and
(a[x+1,y]<>-1) then dep(x+1,y,c);
if (a[x-1,y]<>c) and
(a[x-1,y]<>-1) then dep(x-1,y,c);
end;
begin
read(n,m);
color:=1;
for i := 1 to n do
begin
readln;
for j:= 1 to m do
begin
read(c);
a[i,j]:=ord(c)-48;
if a[i,j]=1 then a[i,j]:=-1;
end;
end;
for i:= 2 to n-1 do
for j:= 2 to m-1 do
begin
if a[i,j]=-1 then
begin
a[i,j]:=0;
dep(i,j,color);
if s>max then max:=s;
a[i,j]:=-1;
inc(color);
s:=0;
end;
if a[i,j]=0 then
begin
a[i,j]:=0;
dep(i,j,color);
if s>max then max:=s;
inc(color);
s:=0;
end;
end;
writeln(max);
end.
Ще один варіант Програма мовою Паскаль через рекурсію
var n,m,i,j,p,x,y:integer;
a:array[1..1000,1..1000] of longint;
c:char;
b:array[1..1000000] of longint;
col,max,max1,cl,cp,cn,cw,nc,kc:longint;
cx,cy:array[1..1000000] of integer;
{
procedure paint(q,w:integer);
begin
a[q,w]:=col;
b[col]:=b[col]+1;
if a[q-1,w]=0 then paint(q-1,w);
if a[q+1,w]=0 then paint(q+1,w);
if a[q,w-1]=0 then paint(q,w-1);
if a[q,w+1]=0 then paint(q,w+1);
end;}
procedure paint(q,w:integer);
begin
nc:=1; kc:=1;
cx[nc]:=q;
cy[nc]:=w;
while kc>=nc do
begin
x:=cx[nc];
y:=cy[nc];
a[x,y]:=col;
b[col]:=b[col]+1;
nc:=nc+1;
if a[x-1,y]=0 then begin
kc:=kc+1;
cx[kc]:=x-1;
cy[kc]:=y;
a[x-1,y]:=col;
end;
if a[x+1,y]=0 then begin
kc:=kc+1;
cx[kc]:=x+1;
cy[kc]:=y;
a[x+1,y]:=col;
end;
if a[x,y-1]=0 then begin
kc:=kc+1;
cx[kc]:=x;
cy[kc]:=y-1;
a[x,y-1]:=col;
end;
if a[x,y+1]=0 then begin
kc:=kc+1;
cx[kc]:=x;
cy[kc]:=y+1;
a[x,y+1]:=col;
end;
end;
end;
BEGIN
readln(m);
readln(n);
for i:=1 to m do
begin
for j:=1 to n-1 do
begin
read(c);
val(c,a[i,j],p);
end;
readln(c);
val(c,a[i,n],p);
end;
col:=1;
for i:=2 to m-1 do
for j:=2 to n-1 do
if a[i,j]=0 then
begin
col:=col+1;
paint(i,j);
end;
max:=0;
for i:=2 to m-1 do
for j:=2 to n-1 do
if a[i,j]=1 then
begin
max1:=1;
cl:=a[i,j-1]; cp:=a[i,j+1];
cw:=a[i-1,j]; cn:=a[i+1,j];
if cl>1
then max1:=max1+b[cl];
if ((cp>1) and (cp<>cl))
then max1:=max1+b[cp];
if ((cw>1) and (cw<>cl) and (cw<>cp))
then max1:=max1+b[cw];
if ((cn>1) and (cn<>cl) and (cn<>cp) and (cn<>cw))
then max1:=max1+b[cn];
if max1>max then max:=max1;
end;
write(max);
END.
a:array[1..1000,1..1000] of longint;
c:char;
b:array[1..1000000] of longint;
col,max,max1,cl,cp,cn,cw,nc,kc:longint;
cx,cy:array[1..1000000] of integer;
{
procedure paint(q,w:integer);
begin
a[q,w]:=col;
b[col]:=b[col]+1;
if a[q-1,w]=0 then paint(q-1,w);
if a[q+1,w]=0 then paint(q+1,w);
if a[q,w-1]=0 then paint(q,w-1);
if a[q,w+1]=0 then paint(q,w+1);
end;}
procedure paint(q,w:integer);
begin
nc:=1; kc:=1;
cx[nc]:=q;
cy[nc]:=w;
while kc>=nc do
begin
x:=cx[nc];
y:=cy[nc];
a[x,y]:=col;
b[col]:=b[col]+1;
nc:=nc+1;
if a[x-1,y]=0 then begin
kc:=kc+1;
cx[kc]:=x-1;
cy[kc]:=y;
a[x-1,y]:=col;
end;
if a[x+1,y]=0 then begin
kc:=kc+1;
cx[kc]:=x+1;
cy[kc]:=y;
a[x+1,y]:=col;
end;
if a[x,y-1]=0 then begin
kc:=kc+1;
cx[kc]:=x;
cy[kc]:=y-1;
a[x,y-1]:=col;
end;
if a[x,y+1]=0 then begin
kc:=kc+1;
cx[kc]:=x;
cy[kc]:=y+1;
a[x,y+1]:=col;
end;
end;
end;
BEGIN
readln(m);
readln(n);
for i:=1 to m do
begin
for j:=1 to n-1 do
begin
read(c);
val(c,a[i,j],p);
end;
readln(c);
val(c,a[i,n],p);
end;
col:=1;
for i:=2 to m-1 do
for j:=2 to n-1 do
if a[i,j]=0 then
begin
col:=col+1;
paint(i,j);
end;
max:=0;
for i:=2 to m-1 do
for j:=2 to n-1 do
if a[i,j]=1 then
begin
max1:=1;
cl:=a[i,j-1]; cp:=a[i,j+1];
cw:=a[i-1,j]; cn:=a[i+1,j];
if cl>1
then max1:=max1+b[cl];
if ((cp>1) and (cp<>cl))
then max1:=max1+b[cp];
if ((cw>1) and (cw<>cl) and (cw<>cp))
then max1:=max1+b[cw];
if ((cn>1) and (cn<>cl) and (cn<>cp) and (cn<>cw))
then max1:=max1+b[cn];
if max1>max then max:=max1;
end;
write(max);
END.
