Завдання 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