Завдання ІІ етапу Всеукраїнської учнівської олімпіади з інформатики (+ авторські розв'язки та тести)
2016-2017 н.р.
Київська область

В архіві:

-  Завдання ІІ етапу Всеукраїнської учнівської олімпіади з інформатики
- авторські розв'язки;
- тести.

Задача 1. FELLING (30 балів). Вирішено вирубати деякі із N дерев, що ростуть у ряд, відстані між якими однакові. Після вирубки повинно залишитись M дерев, а відстані між сусідніми повинні також залишитись одинаковими. Написати програму, яка визначає, скільки існує способів вирубки дерев.

Вхідні дані: Файл Fell.dat через пропуск містить два цілих числа M и N (0≤ M ≤ N ≤1000).

Результат: У файлі Fell.res повинно міститись одне число – шукана кількість способів.

Розв'язок:

program FELLING;
 var n,m,i,d,s:integer;
     f1,f2:text;
procedure Inpt;
begin
 Assign(f1,'Fell.dat');
 Reset(f1);
 Read(f1,n,m);
 Close(f1)
end;
procedure Proc;
begin
 s:=0;
 if m=0 then
  s:=1
 else
  if m=1 then
          s:=n
         else
          for d:=1 to (n-1)div(m-1) do
           Inc(s,n-(m-1)*d)
end;
procedure Outp;
begin
 Assign(f2,'Fell.res');
 Rewrite(f2);
 Write(f2,s);
 Close(f2)
end;
begin
 Inpt;
 Proc;
 Outp
end.

Задача 2 LAWN (30 балів). Газон можна вважати площиною, на якій в кожній точці з цілими координатами росте один пучок трави. Було пострижено деяку прямокутну ділянку газону. Сторони цієї ділянки паралельні осям координат, а дві протилежні вершини розташовано в точках (x1, y1) і (x2, y2). Пучки трави, що знаходяться на межі цього прямокутника, також були пострижені. Дощувальна установка розміщена в точці з координатами (x3, y3) і має радіус дії струменя r. Установка почала поливати усі пучки, відстань від яких до точки (x3, y3) не перевищує r. Написати програму, що визначає кількість пучків трави, які виявилося постриженими і политими.

Вхідні дані: У першому рядку файлу Lawn.dat через пропуск записані чотири цілі числа x1, y1, x2, y2 (−100 000≤ x1<x2≤100 000;−100 000 ≤ y1<y2≤100 000). У другому рядку вхідного файлу містяться три цілі числа x3, y3, r (−100 000≤ x3, y3≤100 000; 1≤ r ≤100 000).

Результати: У файл Lawn.res необхідно вивести одне ціле число - число пучків трави, які були і пострижені, і политі.

Розв'язок:

program Lawn;
 var x1,y1,x2,y2,x3,y3,x,k,r,y:integer;
     f:text;
function Kol(x,z1,z2:integer):integer;
 var min,max,k:integer;
begin
 if (x<x1)or(x>x2)or(z1>y2)or(z2<y1) then
  k:=0
  else           begin
   min:=y1;
   if z1>y1 then
    min:=z1;
    max:=y2;
   if z2<y2 then
    max:=z2;
    k:=max-min+1 end;
 kol:=k
end;
procedure Inpt;
begin
 Assign(f, 'Lawn.dat');Reset(f);
 ReadLn(f,x1,y1,x2,y2);
 Read(f,x3,y3,r);
 Close(f);
end;
procedure Proc;
begin
 k:=Kol(x3,y3-r,y3+r);
 y:=r;
 for x:=1 to r-1 do                           begin
  while sqr(x)+sqr(y)>sqr(r) do
   y:=y-1;
  k:=k+kol(x3+x,y3-y,y3+y)+kol(x3-x,y3-y,y3+y)end;
 k:=k+kol(x3+r,y3,y3)+kol(x3-r,y3,y3);
end;
procedure Outp;
begin
 Assign(f, 'Lawn.res');Rewrite(f);
 Write(f,k);
 Close(f);
end;
begin
 Inpt;
 Proc;
 Outp
end.

Задача 3 FORT (45 балів). У замку квадратної форми є вісім башень, чотири на стиках стін і по одній посередині кожної стіни. Замок захищає гарнізон із N солдатів (N≤100). Необхідно визначити кількість захисників кожної стіни, розмістивши їх в башнях так, щоб вздовж кожної стіни була однакова кількість по M (M<N) солдатів.

Вхідні дані: У файлі Fort.dat записано через пропуск два числа N та M.

Результати: У файл Fort.res записати всі можливі варіанти розстановки солдатів у башнях, кожен варіант з нового рядка у формі, зображеній на таблиці (зірочки – кількість солдатів у башнях).

Розв'язок:

program Fort;
 var i,s,j,a,b,c,v,n,max,g,h,o,p:integer;
     M:array [1..3,1..3] of integer;
     D:array [1..2,1..20] of integer;
     f:text;
procedure Inpt;
begin
 Assign(f,'Fort.dat');Reset(f);
 ReadLn(f,s);ReadLn(f,a);Close(f)
end;
procedure Add;
begin
 b:=Round(n/2);
 for i:=n-1 downto b do             begin
  c:=n-i;j:=j+1;D[1,j]:=c;D[2,j]:=i end;
 v:=j;j:=0;i:=0;
end;
procedure Big;
begin
 if M[2,1]>M[2,3] then max:=M[2,1]
                  else max:=M[2,3];
 if M[1,2]>max then max:=M[1,2];
 if M[3,2]>max then max:=M[3,2];
end;
procedure Left;
begin
 g:=a-max;h:=Random(g);
 M[1,1]:=h;M[3,1]:=g-h;
 M[1,3]:=a-(M[1,1]+M[1,2]);
 M[3,3]:=a-(M[3,1]+M[3,2]);
 g:=0;h:=0;
end;
procedure Right;
begin
 g:=a-max;h:=Random(g);
 M[1,3]:=h;M[3,3]:=g-h;
 M[1,1]:=a-(M[1,2]+M[1,3]);
 M[3,1]:=a-(M[3,2]+M[3,3]);
 g:=0;h:=0;
end;
procedure Up;
begin
 g:=a-max;h:=Random(g);
 M[1,1]:=h;M[1,3]:=g-h;
 M[3,1]:=a-(M[1,1]+M[2,1]);
 M[3,3]:=a-(M[3,1]+M[3,2]);
 g:=0;h:=0;
end;
procedure Down;
begin
 g:=a-max;h:=Random(g);
 M[3,1]:=h;M[3,3]:=g-h;
 M[1,1]:=a-(M[2,1]+M[3,1]);
 M[1,3]:=a-(M[2,3]+M[3,3]);
 g:=0;h:=0;
end;
procedure Outp;         {тут щось глючить!}
begin
 for o:=1 to 3 do
  if (M[o,1]>=0)and(M[o,2]>=0)and(M[o,3]>=0)then
   WriteLn(f,M[o,1],' ',M[o,2],' ',M[o,3])
   else Break;
 WriteLn(f,' ');
 o:=0;p:=0;
end;
procedure Mrz;
begin
 n:=s-(a*2);Add;
 repeat
  i:=i+1;
  for j:=1 to v do begin
   M[2,1]:=D[1,i];M[2,3]:=D[2,i];
   M[1,2]:=D[1,j];M[3,2]:=D[2,j];
   Big;
   if max=M[2,1] then Left;
   if max=M[2,3] then Right;
   if max=M[1,2] then Up;
   if max=M[3,2] then Down;
   Outp            end;
 until i=v;
end;
begin
 Inpt;
 Assign(f,'Fort.res');Rewrite(f);
 Mrz;
 Close(f)
end.

Задача 4 CUBES (55 балів). Кубик з ребром N см пофарбували і розрізали на кубики з ребром 1 см При цьому з'явилися такі, у яких забарвлена різна кількість граней. Наприклад, якщо N=3, то після розрізання буде 8 кубиків, у яких забарвлено три грані, 12 з двома гранями, 6 з однією, а один кубик буде зовсім незабарвлений. Написати програму програму, яка б визначала, скільки кубиків з кожною можливою кількістю забарвлених граней.

Вхідні дані: У файлі Cub.dat записано натуральне число N (від 1 до 100000).

Результати: У файл Cub.dat у рядок через пропуск потрібно записати різні варіанти зафарбувань одержаних після розрізання кубиків у форматі: кількість зафарбованих граней/кількість кубиків у порядку зростання першого параметра

Розв'язок:

program Cubes;
 var n,a,b,c,d:integer;
     f:text;
procedure Inpt;
begin
 Assign(f,'Cubes.dat');
 Reset(f);
 Read(f,n);
 close(f);
end;
procedure Outp;
begin
 Assign(f,'Cubes.res');
 Rewrite(f);
 if n=1 then write(f,'0/0 1/0 2/0 3/1');
 if n=2 then write(f,'0/0 1/0 2/0 3/8');
 if n>2 then
  begin
   a:=8;
   b:=12*n-24;
   c:=6*n*n-3*a-2*b;
   d:=n*n*n-a-b-c;
   write(f,'0/',d,' ','1/',c,' ','2/',b,' ','3/',a);
  end;
 Close(f);
end;
begin
 Inpt;
 Outp
end.