Завдання 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((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;
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.
Краще в цій задачі використати масив. Спочатку відсортуємо його за зростанням, тоді легко перевіряти і рівність елементів, так як вони будуть сусідніми, і їх послідовність. Отже, програма буде мати вигляд:
{$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;
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
|
