21 грудня 2019 року
відбувся ІІ етап Всеукраїнської олімпіади
з інформатики у м. Вінниці
8-9 класи
Умови завдань
Задача Bld. Володимир любить парнi числа, а Петро — непарнi. Тому вони завжди
радiють, якщо зустрiчають числа, якi їм подобаються. Сьогоднi їм зустрілися всi
цiлi числа вiд A до B включно. Володимир вирiшив порахувати
суму всiх парних чисел вiд A до B, а Петро — суму всiх непарних,
пiсля чого вони почали сперечатися, у кого вийшла сума бiльша. Допоможiть їм —
знайдiть рiзницю мiж сумою Володимира i сумою Петра.
Технічні умови. Програма Bld читає
з пристрою стандартного введення через пропуск два цiлих додатнiх числа A i B,
якi не перевищують 2*109. Програма повинна вивести на
пристрві стандартного виведення одне число — рiзниця мiж сумою парних чисел i
сумою непарних чисел вiд A до B.
Приклади
|
Введення
|
Виведення
|
|
3 6
|
2
|
|
3 7
|
-5
|
- - - - - - - - - - -
- - - - - - - - - - - - -
Задача Money. Ярослав та Мирослава мають спільну колекцію з ? монет. Як символ
своєї дружби вони хочуть окремо зберігати таку пару монет, що в сумі номінальна
вартість цих двох монет дає особливе число ?. Підрахуйте кількість різних
способів вибрати потрібну пару.
Технічні умови. Програма Money читає
з пристрою стандартного введення натуральні числа ? та ?, не менші за 2. У другому
рядку - ? натуральних чисел — номінальні вартості монет із колекції. Усі числа
(включно з числами ? та ?) не перевищують 200000. Програма виводить на пристрій
стандартного виведення єдине число — кількість способів вибрати дві монети з
сумарною номінальною вартістю ?. Відомо, що шукана кількість не перевищує 109.
Приклади
|
Введення
|
Виведення
|
|
4 5
2 2 3 2 1 |
4
|
|
10 3
6 2 10 |
0
|
- - - - - - - - - - -
- - - - - - - - - - - - -
Задача Stamps. Нещодавно на уроці математики Ярослав і Мирослава вивчили, що
арифметичною прогресією називають послідовність чисел, у якій різниця між
кожними двома сусідніми членами однакова. А невдовзі після того діти дізналися,
що на честь ювілею математичного товариства столиці було випущено дві серії
марок. Кожна серія складається з ? марок різної номінальної вартості, і ці ?
номіналів утворюють арифметичну прогресію. Для своєї колекції марок Ярослав
придбав одну з цих серій, а Мирослава — іншу. Однак, роздивляючись придбання
одне одного, діти ненароком перемішали всі марки.
Знаючи номінали марок
— 2? попарно різних чисел, — допоможіть дітям розділити марки на дві серії.
Відомо, що це можна зробити рівно в один спосіб.
Технічні умови. Програма
Stamps читає з пристрою стандартного введення натуральне число ? — кількість
марок у серії, 3 ⩽ ? ⩽ 100 000. У другому рядку через пропуски 2? різних
натуральних чисел, менших за 109, — перемішані номінали марок.
Програма виводить на пристрій стандартного виведення в порядку зростання всі
номінали марок Ярославової серії, а в другий рядок — усі номінали марок
Мирославиної серії (так само в порядку зростання). Діти пам’ятають, що
найдешевша марка Ярослава має менший номінал, ніж найдешевша марка Мирослави.
Приклад
|
Введення
|
Виведення
|
|
4
7 9 23 3 16 15 11 2 |
2 9 16 23
3 7 11 15 |
Коментар до прикладу
Виведені у вихідний
файл послідовності утворюють шукані серії марок, адже є арифметичними
прогресіями: 9 − 2 = 16 − 9 = 23 − 16 та 7 − 3 = 11 − 7 = 15 −
11. Серії виведено в правильному порядку, бо 2 < 3.
- - - - - - - - - - -
- - - - - - - - - - - - -
Задача Newnumbers. Козак Вус подарував вам набiр з n цифр
(тобто чисел вiд 0 до 9 включно). I хоче дiзнатися у вас: яку максимальну
кiлькiсть чисел з них можна скласти так, щоб кожне з них дiлилося на 3 та кожна
цифра з набору була використана не бiльше 1 разу. Щоб скласти число, вам
потрiбно вибрати будь-які цифри з набору, вибрати їхнiй порядок та скласти
число з цих цифр. Звернiть увагу, що ви не зобов’язанi використати всi цифри.
Ви ж не можете вiдмовити Вусу? :)
Маленька пiдказка вiд
Математичної Сови:
Остача (залишок) вiд
дiлення x на число 3 дорiвнює остачi вiд дiлення суми цифр
числа x на число 3.
Число a є
кратним числу b (тобто a дiлиться на b) лише, якщо
остача вiд дiлення числа a на число b дорiвнює 0.
Технічні умови Програма Newnumbers читає
з пристрою стандартного введення у першому рядку мiстить одне цiле число n (1
⩽ n⩽5 · 105) — кiлькiсть цифр. У другому рядку записано n цiлих
чисел, кожне з яких має значення вiд 0 до 9 включно. Програма виводить на
пристрій стандартного виведення одне ціле число — максимальну кількість чисел
кратних 3, що можна скласти з цього набору.
Приклади
|
Введення
|
Виведення
|
|
1
0 |
1
|
|
14
8 8 4 8 1 1 0 0 2 1 9 3 4 1 |
8
|
Зауваження до
прикладів
У першому прикладі ми
можемо скласти лише одне число 0.
У другому прикладі з
цього набору ми можемо скласти максимум 8 чисел. Один iз можливих
способів — це скласти такі числа: 0, 0, 48, 9, 3, 21, 81, 84.
Невикористаними у нас залишаться цифри 1, 1.
Математична модель до завдання:
Максимальна кількість
чисел обчислюється за формулою
n =p(0=mod3)+min(k(1=mod3);
m(2=mod3))+(1/3)*(max(k(1=mod3); m(2=mod3) -min(k(1=mod3); m(2=mod3))
де p(0=mod3) - це кількість цифр, що кратні 3.;
k(1=mod3) -це кількість цифр, що мають вигляд 3х+1;
m(2=mod3)) - це кількість цифр, що мають вигляд 3х+2;
Кодування алгоритму на СІ
#include <iostream>
#include <cmath>
using namespace std;
int main(){
long long kol, tsifra, ost;
cin >> kol;
long long n = 0, L = 0, m = 0;
for (long long i = 0; i < kol; i++){
cin >> tsifra;
ost = tsifra % 3;
if (ost == 0)
n = n + 1;
else if (ost == 1)
L = L + 1;
else
m = m + 1;
}
long long rez = n + min(L, m) + (max(L, m) - min(L,m))/3;
cout << rez;
}
Кодування
алгоритму на мові Рython
var k,l,o,m,n,i,min,max,rez:longint;
begin
readln(n);
k:=0; l:=0; m:=0;
for i:=1 to n do
begin
read(o);
o:=(o mod 3);
case o of
0:k:=k+1;
1:l:=l+1;
2:m:=m+1;
end;
end;
if l>m then begin max:=l;
min:=m; end
else begin max:=m; min:=l; end;
rez:=k+min+((max-min) div 3);
write(rez);
endA.
Кодування алгоритму на мові Pascal
var k,l,o,m,n,i,min,max,rez:longint;
begin
readln(n);
k:=0; l:=0; m:=0;
for i:=1 to n do
begin
read(o);
o:=(o mod 3);
case o of
0:k:=k+1;
1:l:=l+1;
2:m:=m+1;
end;
end;
if l>m then begin max:=l;
min:=m; end
else begin max:=m; min:=l; end;
rez:=k+min+((max-min) div 3);
write(rez);
end.
Кодування на мові Pascal генератора перевірочних тестів(текстових файлів з даними)
до алгоритму:
var f:text;
n,p,i,k,l,m,min,max,a,o,rez,c:longint;
pp:boolean;
begin
read(n);
read(p);
assign(f,'figures.test.20');
rewrite(f);
writeln(f,n);
for i:=1 to n do
begin
pp:=true;
case p of
1:begin while pp do
begin a:=random(10); c:=(a mod 3); if c=0 then pp:=false; end; end;
2:begin while pp do
begin a:=random(10); c:=(a mod 3); if c=1 then pp:=false; end; end;
3:begin while pp do
begin a:=random(10); c:=(a mod 3); if c=2 then pp:=false; end; end;
4:begin while pp do
begin a:=random(10); c:=(a mod 3); if ((c=0) or (c=1)) then pp:=false; end; end;
5:begin while pp do
begin a:=random(10); c:=(a mod 3); if ((c=0) or (c=2)) then pp:=false; end; end;
6:begin while pp do
begin a:=random(10); c:=(a mod 3); if ((c=2) or (c=1)) then pp:=false; end; end;
7:a:=random(10);
end;
write(f,a,' ');
o:=(a mod 3);
case o of
0:k:=k+1;
1:l:=l+1;
2:m:=m+1;
end;
if l>m then begin max:=l;
min:=m; end else begin max:=m; min:=l; end;
end;
rez:=k+min+((max-min) div 3);
writeln(f,'');
write(f,rez);
close(f);
write(rez);
end.
Тести для перевірки алгоритму:
Тест 1.
Ввід 4
5 5 8 8
Вивід 1
Тест 2.
Ввід 8
5 5 7 8 8 5 8 4
Вивід 3
Тест 3.
Ввід 16
5 5 7 8 6 8 5 8 4 6 6 3 4 2 8 0
Вивід 9
Тест 4.
Ввід 32
5 5 7 8 8 5 8 4 4 2 8 2 4 7 8 5 4 5 8 8 7 1 8 8 4 7 8 4 5 7 1 7
Вивід 15
Задача Money. Ярослав та Мирослава мають
спільну колекцію з 𝑛 монет.
Як символ своєї дружби вони хочуть окремо зберігати таку пару монет, що в сумі
номінальна вартість цих двох монет дає особливе число 𝑠. Підрахуйте кількість різних способів
вибрати потрібну пару.
Технічні умови. Програма Money читає
з пристрою стандартного введення натуральні числа 𝑠 та 𝑛, не менші за 2. У другому рядку - 𝑛 натуральних чисел — номінальні вартості
монет із колекції. Усі числа (включно з числами 𝑠 та 𝑛) не перевищують 200 000. Програма
виводить на пристрій стандартного виведення єдине число — кількість способів
вибрати дві монети з сумарною номінальною вартістю 𝑠. Відомо, що шукана кількість не
перевищує 109.
Приклади
|
Введення
|
Виведення
|
|
4 5
2 2 3 2 1 |
4
|
|
10 3
6 2 10 |
0
|
- - - - - - - - - - - - - - - - - - - - - - - -
Задача Macrohard. У компанії Macrohard
працює n програмістів. Відомо, коли кожен фахівець приходить на роботу, і коли
йде з неї. Директор компанії вирішив дізнатися, скільки годин протягом доби на
роботі є всі працівники.
Технічні умови. Програма Macrohard читає
з пристрою стандартного введення натуральне число n (n ≤ 1000)
— кількість програмістів. У наступних n рядках міститься
інформація про всіх працівників компанії: в кожному рядку записано по два
натуральних числа — година, о котрій деякий програміст приходить на роботу, й
час, коли він іде з компанії (саме в такому порядку). Жодне з цих чисел не
перевищує 23. Якщо друге число не перевищує перше, це означає, що програміст
залишається на ніч і йде додому наступного дня. Програма виводить на пристрій
стандартного виведення єдине число — кількість годин (упродовж одного дня),
коли всі програмісти перебувають у компанії.
Приклади
|
Введення
|
Виведення
|
|
3
8 20 14 19 12 16
Введення
2
18 6
2 8
|
2
Виведення
4
|
Пояснення до прикладу
Всі три фахівці перебувають у фірмі протягом двох годин — із
14-ї до 16-ї.
- - - - - - - - - - - - - -
- - - - - - - - - -
Задача CBS. Задано шаблон, що
складається з круглих дужок та знаків питання.
Потрібно написати програму, яка визначить, скількома способами
можна замінити знаки питання круглими дужками так, аби отримати правильну
послідовність круглих дужок.
Правильна послідовність дужок (анлг. Correct Bracket
Sequences) - окремий випадок послідовності з круглих дужок, що визначається
таким чином:
ε (порожній рядок) є правильною послідовністю дужок;
нехай S - правильна послідовність, тоді (S) є правильна
послідовність;
нехай S1, S2 - правильні послідовності, тоді S1S2 є правильна
послідовність;
Приклади правильних послідовностей дужок ((()()()())), (())(()())
Технічні умови Програма Cbs читає
з пристрою стандартного введення рядок довжиною не більше 10000 символів,
виключно круглі дужки та знаки запитання. Програма виводить на пристрій
стандартного виведення шукану величину – кількість способів по модулю 109+7.
Приклад
Введення
????(?
Виведення
2
- - - - - - - - - - - - - -
- - - - - - - - - -
Задача Figures. Дано набiр з n цифр
вiд 0 до 9 включно. Потрібно дiзнатися, яку максимальну кiлькiсть чисел з них
можна скласти так, щоб кожне з них дiлилося на 3 та кожна цифра з набору була
використана не бiльше 1 разу. Щоб скласти число, вам потрiбно вибрати будь-які
цифри з набору, вибрати їх порядок та скласти число з цих цифр. Звернiть увагу,
що ви не зобов’язані використати всi цифри.
Математична підказка:
·
Остача (залишок) вiд
дiлення x на число 3 дорiвнює остачi вiд дiлення суми цифр
числа x на число 3.
·
Число a є кратним
числу b (тобто a дiлиться на b) лише, якщо остача вiд
дiлення числа a на число b дорiвнює 0.
Технічні умови. Програма Figures читає
з пристрою стандартного введення у першому рядку одне цiле число n (1
⩽ n⩽5 · 105) — кiлькiсть цифр. У
другому рядку записано n цiлих чисел, кожне з яких має
значення вiд 0 до 9 включно. Програма виводить на пристрій стандартного
виведення одне цiле число — максимальну кiлькiсть чисел кратних 3, що можна
скласти з цього набору.
Приклади
|
Введення
|
Виведення
|
|
1
0 |
1
|
|
14
8 8 4 8 1 1 0 0 2 1 9 3 4 1 |
8
|
Зауваження до прикладів
У першому прикладi ми можемо скласти лише одне число 0.
У другому прикладi з цього набору ми можемо скласти
максимум 8 чисел. Один iз можливих способiв — це скласти наступнi
числа: 0, 0, 48, 9, 3, 21, 81, 84. Невикористаними у нас залишаться
цифри 1, 1.
Немає коментарів:
Дописати коментар