Завдання IІ етапу Всеукраїнської учнівської олімпіади

з інформатики у 2018/2019 н.р.

Задача A. Простий калькулятор (100 балів)

Обмеження часу: 1 с

Обмеження пам'яті: 128 M

Простий калькулятор може обчислювати наступні вирази:

Num1 + Num2

Num1 - Num2

Num1 * Num2

Num1 / Num2

Де num1 і num2 цілі числа (не більші за 100000).

Знайдіть значення заданого виразу. Символи + - * / позначають відповідно операції додавання, віднімання, множення та ділення відповідно. Всі операції цілочисельні, тобто 5/3=1.

Вхідні дані. Рядок містить вираз який має обчислити простий калькулятор.

Вихідні дані. Виведіть результат виразу, який потрібно обчислити.

Приклади вхідних та вихідних даних

input.txt	output.txt
3 * 12	36
16 + 45	61

Вся складність задачі в тому, що при зчитуванні вхідних даних необхідно врахувати символьний тип змінної, яка вказує математичну операцію. Але при зчитуванні символьної змінної в Pascal, якщо числа і операція розділені пропусками, тосимвольній змінній присвоїться значення - пропуск. Для усунення цієї помилки, потрібно зчитувати не одну, а три символьні змінні. Середня змінна і буде відповідати операції, інакше, середовище буде видавати помилку про невідповідність типів. Тоді програма в Delphi матиме вигляд:

program Project2;

{$APPTYPE CONSOLE}

uses

  SysUtils;

var

 f,g:text;a,b,c:integer; d,e,l:char;

begin

  assign(f,'input.txt');

  assign(g,'output.txt');

  reset(f);

  rewrite(g);

  read(f,a,e,d,l,b);

  if d='+' then c:=a+b;

  if d='-' then c:=a-b;

  if d='*' then c:=a*b;

  if d='/' then c:=a div b;

   write(g,c);

  close(f);

  close(g)

end.

Якщо ж не здогадатися перевірити спостереження значень змінних, для усунення помилки, можна скористатися роботою з рядками.  Тоді програма в Delphi матиме такий вигляд:

program Project2;

{$APPTYPE CONSOLE}

uses

  SysUtils;

var
 f,g:text;a,b,c,i,k:integer; e,d:string;
begin
  assign(f,'input.txt');
  assign(g,'output.txt');
  reset(f);
  rewrite(g);
  read(f,d);
 i:=pos(' ',d);
  val(copy(d,1,i-1),a,k);
  val(copy(d,i+3,length(d)-i-2),b,k);
  e:=copy(d,i+1,1);
  if e='+' then c:=a+b;
  if e='-' then c:=a-b;
  if e='*' then c:=a*b;
  if e='/' then c:=a div b;
   write(g,c);
  close(f);
  close(g)
end.

Простіше, звичайно, це робиться на С++, так як тут зчитування змінних різного типу проходить так як звичайно. Отож, програма матиме вигляд:

#include <fstream>

using namespace std;

int main(int argc, char *argv[]) {int a,b,s;

ifstream f;

ofstream g;

f.open("input.txt");

g.open("output.txt");

char c;

f>>a>>c>>b;

if (c='+') s=a+b;

if (c='-')s=a-b;

if (c='*')s=a*b;

if (c='/')s=a / b;

g<<s ;

g.close();

f.close();

}

Задача B. Задача Фокус-покус (100 балів)

Обмеження часу: 1 с

Обмеження пам'яті: 256 M

Петрик П’яточкін загадав число від 1 до 10⁹, а Вам повідомив три остачі, які утворилися при діленні загаданого числа на числа 971, 997, 1033. Зробіть фокус – швидко відгадайте число. Напишіть програму, що за даними остачами, знаходить загадане число.

Вхідні дані. Єдиний рядок містить три натуральних числа.

Вихідні дані. Єдиний рядок має містити одне натуральне число.

Приклад вхідних та вихідних даних

input.txt	output.txt
5 10 15	835049324

Програма в Delphi може матиме такий вигляд:
    program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
 f,g:text;a,b,c,i,j,k,d:longint;
 begin
  assign(f,'input.txt');
  assign(g,'output.txt');
  reset(f);
  rewrite(g);
  read(f,a,b,c);
  for i:=1 to 1000000000 do
  if (i mod 971=a)and(i mod 997=b)and(i mod 1033=c)then
  write(g,i);
  close(f);
  close(g)
end.

Якщо використати вкладені цикли, то програма в Delphi матиме такий вигляд:

program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
 f,g:text;a,b,c,i,j,k,d:longint;
 begin
  assign(f,'input.txt');
  assign(g,'output.txt');
  reset(f);
  rewrite(g);
  read(f,a,b,c);
  for i:=1 to 1000 do
  for j:=1 to 1000 do
  for k:=1 to 1000 do
if (i*971+a=j*997+b)and(i*971+a=k*1033+c)then d:=i*971+a;
   write(g,d);
  close(f);
  close(g)
end.

Задача С. Розфарбування таблиці множення (100 балів)

Ім’я вхідного файлу: іnput.txt

Ім’я вхідного файлу: output.txt

Обмеження часу: 1 с

Обмеження пам'яті: 16 M

Таблицею множення назвемо таблицю розміру n рядків на m стовпців, в якій на перетині i-го рядка і j-ого стовпця розміщене число i * j (рядки і стовпці нумеруються з одиниці).

В одній з математичних шкіл було вирішено провести педагогічний експеримент. Для того, щоб учням було простіше запам'ятовувати таблицю множення, деякі числа в ній будуть пофарбовані в червоний, деякі - в синій, а деякі - в зелений колір (решта чисел будуть чорними).

Процес фарбування чисел можна умовно розбити на чотири етапи. На першому етапі всі числа фарбуються в чорний колір. На другому - всі парні числа фарбуються в червоний колір, на третьому - всі числа, що діляться на 3, фарбуються в зелений колір, на четвертому - всі числа, що діляться на 5, фарбуються в синій колір.

Директор школи хоче знати, яку кількість картриджів для принтерів необхідно закупити для друку таблиць. Тому йому необхідна інформація про те, скільки чисел якого кольору буде в розфарбованій таким чином таблиці множення n на m. Напишіть програму, яка допоможе у підрахунку таких кількостей.

Вхідні дані. Рядок містить два натуральних числа n і m (1 ≤ n, m ≤ 1000).

Вихідні дані. У першому рядку виведіть кількість чисел, пофарбованих у червоний колір, в другій - у зелений, в третій - у синій, в четвертій - у чорний. Дотримуйтесь формату, наведеному в прикладах.

Приклади вхідних та вихідних даних

input.txt	output.txt
10 10	RED : 21 GREEN : 39 BLUE : 36 BLACK : 4
5 2	RED : 5 GREEN : 2 BLUE : 2 BLACK : 1

program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
 f,g:text;n,m,b,c,i,j,k,d:longint;a:array[1..1000,1..1000]of longint;
 begin
  assign(f,'input.txt');
  assign(g,'output.txt');
  reset(f);
  rewrite(g);
  read(f,n,m);
  b:=0;c:=0;d:=0;k:=0;
  for i:=1 to n do
  for j:=1 to m do begin
  a[i,j]:=i*j;
  if a[i,j] mod 5=0 then b:=b+1 else
  if a[i,j] mod 3=0 then c:=c+1 else
  if a[i,j] mod 2=0 then d:=d+1 else k:=k+1 end;
  writeln(g,'RED : ',d);
  writeln(g,'GREEN : ',c);
  writeln(g,'BLUE : ',b);
  writeln(g,'BLACK : ',k);
  close(f);
  close(g)
end.

Задача D. Ліфт (100 балів)

Ім’я вхідного файлу: іnput.txt

Ім’я вхідного файлу: output.txt

Обмеження часу: 1 с

Обмеження пам'яті: 64 M

Щоб підняти на N-й поверх M-поверхового будинку новий холодильник, Степан визвав бригаду вантажників. Оплата роботи вантажників відбувається таким чином: за підйом холодильника на один поверх необхідно заплатити 200 гривень, за спуск на один поверх – 100 гривень. За підйом та спуск ліфтом оплата не береться. Незважаючи на те, що в Степановому будинку є ліфт, йому, напевно, все ж таки доведеться заплатити вантажникам, тому що ліфт зупиняється тільки на кожному K-му поверсі, починаючи з першого (тобто на поверхах з номерами 1, K+1, 2K+1, 3K+1, …). Необхідно знайти, якої мінімальної суми грошей буде достатньо, щоб вантажники доставили холодильник з першого поверху на N-й.

Вхідні дані. У рядку записані три числа: M (2≤M≤100), N (2≤N≤M) и K (2≤K≤M-1), розділені пропусками.

Вихідні дані. Вивести єдине число – мінімальну вартість підйому холодильника.

Приклад вхідних та вихідних даних

input.txt	output.txt
20 7 4	200
20 7 2	0

program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;
 label 1;
var
 f,g:text;n,m,b,c,i,k,d:integer;
 begin
  assign(f,'input.txt');
  assign(g,'output.txt');
  reset(f);
  rewrite(g);
  read(f,m,n,k);
   i:=(n-1) div k;
  if i*k+1=n then begin c:=0;goto 1 end;
   b:=(n-(i*k+1))*200;
   d:=((i+1)*k+1-n)*100;
   if d<b then c:=d else c:=b;
  1:writeln(g,c);
  close(f);
  close(g)
end.

Завдання IІ етапу Всеукраїнської учнівської олімпіади

з інформатики 2017/2018 н.р.

Задача A. Покер (100 балів)

Ім’я вхідного файлу: іnput.txt

Ім’я вхідного файлу: output.txt

Ліміт часу: 1с.

Задано 5 цілих чисел. Серед них:

·        якщо однакові 5, то вивести "Impossible", інакше

·        якщо однакові 4, то вивести "Four of a Kind", інакше

·        якщо однакові 3 и 2, то вивести "Full House", інакше

·        якщо є 5 послідовних, то вивести "Straight", інакше

·        якщо однакові 3, то вивести "Three of a Kind", інакше

·        якщо однакові 2 і 2, то вивести "Two Pairs", інакше

·        якщо однакові 2, то вивести "One Pair", інакше

·        вивести "Nothing".

Вхідні дані

У першому рядку задано 5 чисел (від 1 до 13 включно) через пропуск.

Вихідні дані

Виводиться один рядок - результат аналізу.

Приклади

іnput.txt	output.txt
1 3 9 3 2	One Pair
1 5 5 4 4	Two Pairs
10 11 12 13 1	Nothing

Вже з умови видно, що для розв'зання даної задачі потрібно застосувати розгалуження, порівнюючи 5 вхідних чисел. Звичайно, найпростіше перевірити рівність всіх п'яти чисел. Навіть, не знаючи формул комбінаторики, можна перебрати всі варіанти і в решти випадків. Найскладніше визначити чи є 5 послідовних чисел. Якби ці числа йшли за порядком, то це було б дуже просто, а якщо ж порядок не не суттєвий то перебрати всі варіанти тяжко, так як розміщень даних чисел може бути аж 5! Без урахування порядку, та використовуючи модуль, можна зменшити кількість варіантів. Ото ж, програма в Delphi може бути такою:

program Project2;

{$APPTYPE CONSOLE}

uses

  SysUtils;

label 1;

var

 f,g:text;i,a,b,c,d,e:byte;

begin

  assign(f,'input.txt');

  assign(g,'output.txt');

  reset(f);

  rewrite(g);

  read(f,a,b,c,d,e);

  if (abs((a-b)*(b-c)*(c-d)*(d-e))=1)or(abs((a-e)*(b-c)*(c-d)*(d-e))=1)
  or(abs((a-e)*(b-a)*(c-d)*(d-e))=1)or(abs((a-e)*(b-c)*(a-b)*(d-e))=1)
  or(abs((a-e)*(b-c)*(c-d)*(d-e))=1)or(abs((a-c)*(c-d)*(d-e)*(e-b))=1)
  or(abs((a-c)*(c-d)*(d-b)*(b-e))=1)or(abs((b-c)*(c-d)*(d-a)*(a-e))=1)
  or(abs((b-c)*(c-a)*(a-d)*(d-e))=1)or(abs((b-a)*(a-c)*(c-d)*(d-e))=1)

  or(abs((c-b)*(b-a)*(a-d)*(d-e))=1)        {це не всі варіанти}
  then begin   then begin  write(g,'Straight'); goto 1 end;

  if (a=b)and(a=c)and(a=d)and(a=e) then begin write(g,'Impossible');goto 1 end else

  if ((a=b)and(a=c)and(a=d))or((a=b)and(a=c)and(a=e))or

  ((a=b)and(a=e)and(a=d))or((a=d)and(a=c)and(a=e))or((d=b)and(b=c)and(b=e))

  or((a=b)and(a=c)and(a=e)) then begin write(g,'Four of a Kind');goto 1 end else

  if ((a=b)and(a=c)and(d=e))or((a=b)and(a=d)and(c=e))or

  ((a=b)and(a=e)and(d=c))or((b=c)and(b=d)and(a=e))or((b=d)and(b=e)and(a=c))

  or((c=d)and(c=e)and(a=b))or((a=c)and(a=d)and(b=e))or((a=d)and(a=e)and(b=c))

  or((a=c)and(c=e)and(b=d))or((b=c)and(c=e)and(a=d))then begin

  write(g,'Full House');goto 1 end else

  if ((a=b)and(c=d))or((a=c)and(d=e))or((a=d)and(b=c))or((a=b)and(d=e))or

  ((a=b)and(c=e))or((a=c)and(b=d))or((a=c)and(b=e))or((a=d)and(b=e))or

  ((a=e)and(c=d))or((b=c)and(d=e))or((b=d)and(c=e))or((b=e)and(c=d))or

  ((a=d)and(c=e))or((a=e)and(b=c))or((a=e)and(b=d))then begin

  write(g,'Two Pairs');goto 1 end else

  if ((a=b)and(a=c))or((a=b)and(a=d))or

  ((a=b)and(a=e))or((b=d)and(b=c))or((b=d)and(b=e))

  or((c=d)and(c=e))or((a=c)and(c=e))or((b=c)and(c=e))or((a=d)and(d=e))

  or((a=b)and(b=d))then begin write(g,'Three of a Kind');goto 1 end else

  if (a=b)or(a=c)or(a=d)or(a=e)or(b=d)or(b=c)or(e=b)or(d=c)

  or(c=e)or(d=e) then write(g,'One Pair') else write(g,'Nothing');

  1:close(f);

  close(g)

end.

Краще в цій задачі використати масив. Спочатку відсортуємо його за зростанням, тоді легко перевіряти і рівність елементів, так як вони будуть сусідніми, і їх послідовність. Отже, програма буде мати вигляд:

program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;

label 1,2;
var
 f,g:text;i,j,k,n,l:byte;a:array[1..5]of byte;
begin
  assign(f,'input.txt');
  assign(g,'output.txt');
  reset(f);
  rewrite(g);
  for i:=1 to 5 do
  read(f,a[i]);
  for i:=1 to 4 do
  for j:=i+1 to 5 do
  if a[i]>a[j]then begin l:=a[i];a[i]:=a[j];a[j]:=l end;
  for i:=1 to 4 do
  if a[i+1]-a[i]=1 then k:=k+1;
  if k=4 then begin write(g,'Straight'); goto 1 end;
  k:=0; l:=a[1];
  for i:=2 to 5 do begin
  if a[i]<>l then goto 2;
  if a[i]=a[i-1] then begin n:=n+1;l:=a[i] end;
  2:if (a[i]=a[i-1])and(a[i]<>l) then k:=k+1 end;
  if n=4 then begin write(g,'Impossible'); goto 1 end;
  if (n=3)or(k=3) then begin write(g,'Four of a Kind'); goto 1 end;
  if ((n=1)and(k=2))or((n=2)and(k=1))then begin write(g,'Full House');goto 1 end;
  if (n=2)or(k=2) then begin write(g,'Three of a Kind'); goto 1 end;
  if (n=1)and(k=1)then begin write(g,'Two Pairs');goto 1 end;
  if (n=1)or(k=1)then begin write(g,'One Pair');goto 1 end
   else write(g,'Nothing');
  1:close(f);
  close(g)

end.

Задача B. Рада школи (100 балів)

Ім’я вхідного файлу: іnput.txt

Ім’я вхідного файлу: output.txt

Ліміт часу: 1 с.

До керівництва ради школи входять батьки, учні та вчителі, причому батьків повинно бути не менше 1/3 від загальної кількості членів ради. На поточний момент часу до ради школи входить N людей, з них K батьків. Визначте, скільки батьків потрібно додатково ввести в число ради школи, щоб їх кількість була не меншою 1/3 від загального числа всіх учасників.

 Вхідні дані

Вхідні дані містять два числа N і K (N › 0, 0 ≤ K ≤ N≤100000) записані через пропуск.

Вихідні дані

Вихідні дані містять одне число - мінімальна кількість батьків, яких потрібно долучити до числа ради школи.

Приклад

іnput.txt	output.txt
27 7	3

Ну, а ця задача досить проста, але потрібно врахувати випадки, коли К становить  більше ніж третю частину від N, щоб не отримати від'ємне число. Тоді програма буде мати вигляд:

program Project2;

{$APPTYPE CONSOLE}

uses

  SysUtils;

var

 f,g:text;n,k:int64;

begin

  assign(f,'input.txt');

  assign(g,'output.txt');

  reset(f);

  rewrite(g);

  read(f,n,k);

  if n=k then k:=0 else

  k:=n div 3 -k+1;

  write(g,k);

  close(f);

  close(g)

end.

Задача С. N-та цифра (100 балів)

Ім’я вхідного файлу: іnput.txt

Ім’я вхідного файлу: output.txt

Ліміт часу: 1с.

Дано початковий рядок 1, над яким застосовують наступну операцію: приписують праворуч такий же рядок, але з заміною нулів на одиниці, а одиниць на нулі. Цю операцію повторюють нескінченну кількість разів. Ваше завдання полягає в знаходженні N-тої цифри в отриманому рядку.

Вхідні дані

В першому рядку записано кількість тестів K. В наступних K рядках записано число N, номер цифри в K-му рядку (1≤K≤100, 1≤N≤1000000000).

Вихідні дані

В результаті вивести K рядків, в кожному з яких N-та цифра, відповідного рядка.

Приклади

іnput.txt	output.txt
1 7	1
2 1 2	1 0

Задача D. Порожній прямокутник (100 балів)

Ім’я вхідного файлу: іnput.txt

Ім’я вхідного файлу: output.txt

Ліміт часу: 2с.

            Задано N різних точок на площині (2≤N≤1000). Виберемо будь-які дві точок з даної множини з координатами (x1, y1) і (x2, y2). Для цієї пари точок можна побудувати прямокутник зі сторонами, паралельними осям координат, так що обрані точки будуть перебувати в протилежних кутах прямокутника. Прямокутник, побудований таким чином, назвемо порожнім, якщо всередині нього і на його границі немає інших заданих точок. Вам потрібно визначити, скільки різних порожніх прямокутників можна побудувати із заданого множини точок.

Вхідні дані

            Вхідні дані складаються з декількох рядків. Перший рядок файлу містить величину N(кількість точок). У кожному наступному рядкові через пропуск задаються координати X і Y однієї точки з множини цілих чисел, що не перевищують по модулю 1000000 (в 50% тестів координати не перевищують по модулю 10000).

Вихідні дані

Вихідні дані містять єдиний рядок зі знайденим числом порожніх прямокутників

Приклад

іnput.txt	output.txt
5 -1 4 1 4 1 1 2 1 -2 2	2