https://www.e-olymp.com/uk/problems?tag=10
Блог для юних програмістів: http://proginschool.blogspot.com), т
V8=219201;
V9=1978819;
V10=19728201.
8-9 класи
10-11 класи
Умови завдань
Блог для юних програмістів: http://proginschool.blogspot.com), т
21 грудня 2019 року
відбувся ІІ етап Всеукраїнської олімпіади з інформатики у м. Вінниці
Задача Вінницького про потужність комунікацій
Задача Вінницького
про потужність комунікацій в соціальній мережі
Умова задачі:
Один власник акаунту в соціальній мережі розсилає n різних повідомлень 1-го рівня для n одержувачів(кожний одержувач отримує тільки одне повідомлення 1-го рівня). Згодом кожний одержувач повідомлення 1-го рівня розсилає n-1 повідомлень 2-го рівня для n-1 одержувачів(при цьому кожний одержувач отримує тільки одне повідомлення 2-го рівня і не отримував повідомлення 1-го рівня). Після цього, кожний одержувач повідомлення 2-го рівня розсилає n-2 повідомлень 3-го рівня для n-2 одержувачів(при цьому кожний одержувач отримує тільки одне повідомлення 3-го рівня і не отримував повідомлень 1-го та 2-го рівнів). І так далі. Таким чином, кожний одержувач повідомлень m-го рівня розсилає повідомлення n-m повідомлень (m+1)-го рівня для n-m одержувачів(при цьому кожний одержувач отримує тільки одне повідомлення (m+1)-го рівня і не отримував повідомлень менших за номером m+1 рівнів). Зрозуміло, якщо n=m, то розсилання повідомлень припиняється(тобто, це означає, що повідомлень (n+1 )-го рівня не розсилалося вже нікому). Допоможіть адміністратору соціальної мережі автоматично розраховувати таку суму, яка містить два доданки: 1) кількість усіх осіб, котрі задіяні у цій комунікації; 2)кількість усіх повідомлень будь-якого рівня у цій комунікації.
Технічні умови для програмування. Програма Measure читає з пристрою стандартного введення натуральне число n, не менші за 1 та не більші 50. Число n – це кількість різних повідомлень 1-го для n одержувачів. Програма виводить на пристрій стандартного виведення єдине число — суму, яка має два доданки: 1) кількість усіх осіб, котрі задіяні у цій мережній комунікації; 2)кількість усіх повідомлень будь-якого рівня у цій мережній комунікації.
Приклади
Введення
|
Виведення
|
3
|
31
|
5
|
651
|
Розв’язування. Створимо математичну модель до цієї задачі. Згідно умови задачі створюємо простий граф, в якому будь-яка вершина позначає особу, а будь-яке ребро означає повідомлення певного рівня(кольору)) для n=3;
Згідно умови задачі створюємо простий граф для n=3;
Розрахунки: Кількість повідомлень: 15. Кількість осіб 16. Сума: 31.
Згідно умови задачі створюємо простий граф для n=4;
Розрахунки: Кількість повідомлень: 64. Кількість осіб 65. Сума: 129.
Простий граф(для n=4) містить в собі чотири підграфи(випадку n=3), тому використаємо математичну індукцію для виведення рекурентної формули.
Проаналізуємо перехід від індуктивного кроку n=k до наступного кроку n=k+1 і
отримаємо рекурентний закон
розрахунку потрібної для адміністратора суми для довільного k:
v0=1; vk=k(vk-1+1)+1 , якщо k – натуральне число.
V1=3;
V2=9;
V3=31;
V4=129;
V5=651;
V6=3913;
V7=27399; V8=219201;
V9=1978819;
V10=19728201.
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.
