Сайти для підготовки до олімпіади інформатики

Стратегічна задача на  оптимізацію кількості

 інформаційних  зв’язків між користувачами.

У деякій освітній системі є n працівників. Між деякими із них здійснюються двосторонні мобільні зв'язки.

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

Провайдер-фірма хоче вибрати декілька працівників і назвати їх вузловими  операторами таким чином, що із будь-якого  мобільного системи освіти існує прямий зв'язок до деякого вузлового оператора системи освіти. 

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

Відповідь: m(n)=n-[n/3]-1.

Вказівка. Переформулюємо умову задачі на мові теорії графів. Потрібно знайти таке мінімальне число s,  що у будь-якому зв’язному графі, у якого n вершин можна відмітити не більше ніж s його вершин таким чином, що у будь-якої вершини знайдеться відмічена сусідня вершина(вважаємо,  що сусідня вершина зветься сусідкою).

Доведемо, що s >= n-[n/3]-1. Розглянемо граф з чотирма вешинами v⁽⁰⁾, v⁽¹⁾_j, v⁽²⁾ _j, v⁽³⁾_j , j = 1, . . . , [n/3], та ребрами (v⁽⁰⁾, v⁽¹⁾_j), (v⁽¹⁾, v⁽²⁾_j),  (v⁽²⁾, v⁽³⁾_j), j = 1, . . . , [n/3].

Нехай k - довільне число від 1 до [n/3]. У вершин v⁽²⁾ _k, v⁽³⁾_k  повинна бути відмічена сусідка, а це значить обов’язково буде відмічена v⁽²⁾ _k, як єдина сусідка v⁽³⁾_k  і одна з вершин v⁽¹⁾_j, v⁽³⁾_j повинна бути відмічена, оскільки інших сусідів у   v⁽²⁾ _k  немає. Таким чином, всього повинно бути відмічено  не менше  2*[n/3]-1 вершини.

Доведемо, що s <= n-[n/3]-1. Можна вважати, що заданий граф являється деревом, так як в протилежному випадку можна виділити скріплююче дерево і довести твердження для нього.  Виберемо в якості кореня висячу вершину і назвемо її v⁽⁰⁾,а інші розташуємо по рівнях стандартним чином.  Розфарбуємо вершини в три кольори так, що  вершини на рівнях 3k+1 пофарбовані в один колір, на рівнях виду 3k+2 пофарбовані в другий колір, а інші в третій колір. За принципом Діріхле знайдеться такий колір, в який пофарбовано що найменше  [n/3]+1 вершини. Відмітимо вершини інших кольорів. Тоді ми відмітили не більше n-[n/3]-1 вершин, і у будь-якої невисячої вершини є відмічена сусідня вершина. Нехай v – висяча вершина(v не дорівнює v⁽⁰⁾),  нехай v₁ – батько– батько v₁. ВІдмітимо, що v₂ існує, так як рівнів не менше трьох. Якщо у v не існує відміченої v, v₂ сусідньої вершини, то v₁ – невідмічена, а значіть, відмічені  v та  v₂. Приберемо мітку з вершини v, та відмітимо вершину v₁. Тоді кількість відмічених вершин не зміниться, у всіх вершин, у яких   була відмічена сусідка, вона залишається, а також вона і у вершини v тепер буде відмічена сусідка. Аналогічно зробимо для кореневої вершини. Зробивши, при необхідності подібну операцію скінчену кількість разів, ми отримаємо те, що у всіх вершин була відмічена сусідка. Що і вимагало довести.

Зразки задач для складання алгоритмів мовою програмування Pascal (це задачі міської олімпіади з інформатики за 2017 рік у м. Вінниці)

Задача Tel. Василь з батьком купували два мобільні телефона – мамі і Василеві. Так як на другий товар у супермаркеті суттєва знижка, за перший заплатили R1  гривень, а за другий менше -  R2 . Число S називається середнім з двох чисел R1 і R2, якщо S дорівнює (R1 + R2) / 2.  Василь негайно підрахував  середнє значення ціни S, яке також виявилося цілим числом. Коли мамі вручили новий телефон, сказали його ціну R1  та розповіли про знижку. Мама поцікавилася, а скільки ж коштує телефон Василя, але він пам’ятав лише середнє значення ціни та ціну маминого телефона.  Допоможіть Василю сказати мамі правду.

Технічні умови. Програма Tel  читає з пристрою стандартного введення  два цілих числа R1 і S, (обидва між 1000 і +10000) в одному рядку через пропуск, програма виводить на пристрій стандартного виведення єдине ціле число – вартість телефона Василя.

Приклад.  Введення   4000 3000. Виведення 2000.  Функція для розв’язання Задача Tel: R2(R1;S)=2*S-R1 якщо (1000<=R1<=10000), &(1000<=S<=10000).

var  R2, S, R1: integer; begin read (R1, S); R2:= 2*S – R1; write (R1); end.

var r1,r2,s:int64; begin   read(r1,s);   r2:=2*s-r1;   write(r2); end.

Задача Ink. Як відомо, все частіше і частіше  різні папери не пишуть від руки, а друкують на принтері. Актуальною є проблема придбання запасних картриджів. Їх варто купувати разом з принтером. Якщо разом з принтером купити N  картриджів, це буде коштувати А+В*N гривень. Відомо, що  покупець на всю покупку може витратити не більше С гривень.

Визначте максимальне число запасних картриджів, що їх зможе купити покупець.

Технічні умови. Програма Ink  читає з пристрою стандартного введення  три цілих числа A, B, C (1 ≤ A, B, C ≤ 2*109, A ≤ C) - вартість принтера, вартість одного картриджа і максимальну вартість усієї покупки. Програма виводить єдине число - максимальне придбаних картриджів.

Приклад .  Введення	Виведення
20 10 55	3

Функція для розв’язання Задача Ink: N(a;b;c)=[(c-a)/b],  якщо а+b *n<=C

var A, B, C, N: real; begin read(A, B, C); N:=(C-A)/B; write(trunc(N)); end.

var a,b,c,n:int64; begin   read(a,b,c);   c:=c-a;   if c<0 then c:=0;   n:=(c div b);   write(n) end.

Задача Wiring.   Василь бажає підключити всі свої m електроприладів  до n розеток, що є в кімнаті. У магазині продаються  розгалужувачі з 1 розетки на 2 по ціні A гривні за штуку, а мультиплексори з однієї розетки на п’ять — по ціні B гривні за штуку. Запас обох товарів у магазині завжди достатній. Розгалужувачі та мультиплексори можна вільно підключати один до одного та розетки, що є. Яку мінімальну суму доведеться  витратити Василю, аби  підключити всі наявні в нього  електроприлади?  Василь не проти, якщо після підключення всіх m приладів залишаться незаняті розетки, его турбує  лише мінімізація затрат.

Технічні умови. Програма  Wiring  читає з пристрою стандартного введення рядок  чисел через пропуск: n (1 ≤ n ≤ 1015) — кількість розеток,  m (1 ≤ m ≤ 1015) — кількість електроприладів, два цілих числа a і b (1 ≤ a,b ≤ 1000), - вартість розгалужувача  і мультиплексора відповідно. Програма виводить на пристрій стандартного виведення  єдине число – мінімальну суму, яку повинен витратити Василь.

Приклади

Введення	Виведення
1 3 1 10	2
2 4 9 10	10
3 8 9 10	19

Функція для розв’язання Задача Wiring: 1)C(a;b;k;l)=min[(ak+bl],  цей мінімум шукають на множині (k+4l<=m-n)&(k+l<=m-n), якщо n-m<0.  2) C(a;b;k;l)=0, якщо (n-m)>=0. 

var n,m,a,b,min,k,d,mo:int64; begin    read(n,m,a,b);    k:=m-n;    if k<=0 then begin write(0) end            else begin     d:=(k div 4);    mo:=(k mod 4);                    min:=k*a;                    if mo>0 then m:=d*b+b                            else m:=d*b;                    if min>m then min:=m;                    m:=d*b+mo*a;                    if m<min then min:=m;                    write(min);                 end; end.

Задача Tiles. План будинку має форму прямокутника зі сторонами axb. Вздовж всіх стін  (всередині будинку) проходить коридор шириною h. Підлогу коридору вирішили покрити плиткою розміром 1х1. Скільки плиток для цього потрібно купити? Вважайте, що a>2h,  b>2h.

Технічні умови.  Програма Tiles читає з пристрою стандартного введення  три натуральних  числа  a,b,h (кожне з них не більше 106. Програма виводить на пристрій стандартного виведення  єдине число – кількість плиток, яку потрібно купити.

Приклад. Введення  5 10 2.  Виведеня  44.  Функція для розв’язання Задача Tiles: K(a;b;h)=2ah+2h(b-2h],  якщо a>2h,  b>2h.

var a, b, h, x: integer; begin read (a, b, h); x:=2*h*(a+b-(2*h)); write (x); end.

var a,b,h,r:int64; begin   read(a,b,h);   r:=a*b-(a-2*h)*(b-2*h);   write(r); end.

Завдання  для самостійного програмування

Завдання С 

 

Задання С1. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних розв’язків на числових проміжках [-k; k], де k- ціле число, рівняння

n²+(n-1)²+n²(n-1)²=(n(n-1)+1)²,

де n - ціле невідоме число.

 

 

Завдання С2. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних розв’язків на числових проміжках [-k; k], де k- ціле число, рівняння 

n²+(n-1)²+(n-2)²+ n²(n-1)² +(n-1)²(n-2)² =(n(n-1)(n-2)+1)²,

де n - ціле невідоме число.

 

Задання С3. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (a;b;c)  на проміжках [-k; k], де k- ціле число, рівняння

(a-b)³+(b-c)³+(c-a)³=3(a-b)(b-c)(c-a)

де a, b,c - цілi невідомі числa.

 

 

Задання С4. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (a;b;c) на числових проміжках [-k; k], де k- ціле число, рівняння

(a+b)³+(b+c)³+(c+a)³-3(a+b)(c+b)(a+c) =2(a³+b³+c³-3abc)

де a, b,c - цілi невідомі числa.

  

Задання С5. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (a;b;c) на числових проміжках [-k; k], де k- ціле число, рівняння

(a+b+c)(a²+b²+c²-ab-cb-ac)=a³+b³+c³-3abc

де a, b,c - цілi невідомі числa.

 

Задання С6. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (a;b;c) на числових проміжках [-k; k], де k- ціле число, рівняння

(a+b+c)³-3(a+b)(b+c)(c+a)=a³+b³+c³-3abc

де a, b,c - цілi невідомі числa.

 

Завдання D 

Задання D1. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних розв’язків на числових проміжках [-p; p], де p - ціле число, рівняння

1² + n² = 4(9+n),

де  n - ціле невідоме числa.

 

Задання D2. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних двійок-розв’язків (m;n)  на числових проміжках [-p; p], де p - ціле число, рівняння

m² + n² = m(m+n),

де m,n - цілi невідомі числa.

 

Задання D3. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (k;m;n)  на числових проміжках [-p; p], де p - ціле число, рівняння

m² + n² + k²=km+mn+kn,

де k,m,n, - цілi невідомі числa.

 

 

Задання D4. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (k;m;n)  на числових проміжках [-g; g], де g - ціле число, рівняння

m²n+k²n+n²m=n³+m³+k³

де k,m,n - цілi невідомі числa.

Задання D5. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (k;m;n) на числових проміжках [-q; q], де q - ціле число, рівняння

m³n²+k³m²+n³k² = n⁵ +m⁵+k⁵,

де k,m,n, - цілi невідомі числa.

 

Задання D6. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних четвірок-розв’язків (k;m;n;р) на числових проміжках [-g; g], де g - ціле число, рівняння

(mn+kp)²=(n²+m²)(k²+p²)

де k,m,n,p - цілi невідомі числa.

 

 

 

Завдання F 

Задання F1. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних розв’язків на числових проміжках [-d; d], де d - ціле число, рівняння

1 + 18n+ n² = (2+n)(59+n),

де  n - ціле невідоме числa.

Задання F2. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних двійок-розв’язків (m;n)  на числових проміжках [-t; t], де t - ціле число, рівняння

m² + n² = (m-6)(m+n+30),

де m,n - цілi невідомі числa.

 

Задання F3. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (k;m;n)  на числових проміжках [-r; r], де r - ціле число, рівняння

(m-1)² + n² + (k+1)²=k(m-1)+mn+(k+1)n,

де k,m,n, - цілi невідомі числa.

 

 

Задання F4. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (k;m;n)  на числових проміжках [-h; h], де h - ціле число, рівняння

m²(n-1)+k²n+(n+1)²m=(n-1)³+m³+(k+1)³

де k,m,n - цілi невідомі числa.

Задання F5. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (k;m;n) на числових проміжках [-s; s], де s - ціле число, рівняння

m⁴n+k⁴m+n⁴k = n⁵ +m⁵+k⁵,

де k,m,n, - цілi невідомі числa.

 

Задання F6. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних четвірок-розв’язків (k;m;n;р) на числових проміжках [-g; g], де g - ціле число, рівняння

(mn+kp)²=((n-1)²+(m-1)²)((k+1)²+(p+1)²)

де k,m,n,p - цілi невідомі числa.

 

Завдання W 

Задання W1. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних розв’язків на числових проміжках [-n; n], де n - ціле число, рівняння

1=0.25(m²+1)² – 0.25(m²-1)²

де  m - ціле невідоме числa.

Задання W2. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних двійок-розв’язків (m;n)  на числових проміжках [-t; t], де t - ціле число, рівняння

mⁿ=0.25(mⁿ+n)²-0.25(mⁿ-n)²   

де m,n - цілi невідомі числa.

 

Задання W3. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (k;m;n)  на числових проміжках [-y; y], де y - ціле число, рівняння

k⁴ + 4 =  (m² – 2m + 2)(n² + 2n + 2),

де k,m,n, - цілi невідомі числa.

 

 

Задання W4. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних двійок-розв’язків (a;b)  на числових проміжках [-h; h], де h - ціле число, рівняння

a⁴ + 4b⁴ = (a² – 2ab + 2b²)(a² + 2ab + 2b²);

де a,b - цілi невідомі числa.

Задання W5. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних двійок-розв’язків (k;n) на числових проміжках [-s; s], де s - ціле число, рівняння

k⁴+(n+k)(n+2k)(n+3k)(n+4k)=(n² + 5kn+5k²)²,

де k,n, - цілi невідомі числa.

 

Задання W6. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних двійок-розв’язків (k;n) на числових проміжках [-g; g], де g - ціле число, рівняння

k⁴+(n-k)n(n+k)(n+2k)=(n² + kn- k²)²;

де k,n - цілi невідомі числa.

 

 

Список рекомендованих сайтів для підготовки до олімпіади

http://schoololymp.byethost32.com – школа олімпійського резерву при ВІППО
http://www.olymp.vinnica.ua – Всеукраїнські Інтернет-олімпіади з різних предметів (фізика, інформатика). На сайті розміщена цікава інформація про Всеукраїнські олімпіади по інформатиці, фізиці. Проводилася мережна олімпіада по інформатиці.
http://www.uoi.in.ua – Всеукраїнська олімпіада з інформатики
http://www.e-olimp.com.ua E-Olimp система підготовки та проведення олімпіад зіспортивного програмування
http://www.qbit.org.ua/ -Молодёжное научное общество QBit - Кубит - г. Харьков
http://algolib.chat.ru –алгоритми: методи розв’язання
http://algolist.manual.ru –алгоритми: методи розв’язання
http://olympiads.win.true.nl/ioi – Міжнародна олімпіада з інформатики
http://www.olympiads.ru - Події, задачі, тести, рішення, коментарі. На сайті також можна викачати бібліотеку для написання "перевірялок" до задач - Testlib.
http://neerc.ifmo.ru/School/ - На цьому сайті міститься інформація про олімпіади школярів по інформатиці, які проходять в Росії, в яких беруть участь Петербурзькі школярі
http://www.olympiada.km.ua/ - Задачі заочних і обласних олімпіад Хмельницької області. Архіви турнірів, конкурсів. Багато іншої корисної інформації.
http://comp-science.narod.ru/ - Матеріали олімпіад школярів по програмуванню в Пермській області; підготовка до олімпіад по програмуванню; дидактичні матеріали по алгебрі і геометрії; технологія генерації дидактичних матеріалів по математиці; дидактичні матеріали по інформатиці (задачі, тести); методична скарбничка; посилання на освітні ресурси Internet.
http://acm.timus.ru- Тут ви можете знайти деяку кількість задач з різних змагань. Перевіряюча система дозволяє вам перевірити ваш розв’язок для кожної задачі.
http://www.informatics.ru/ - Даний сайт присвячений російським олімпіадам школярів по інформатиці. Автори сайту - члени журі і наукового комітету Всеросійської олімпіади, а також тренери збірної команди Росії для міжнародної олімпіади. Тут викладаються матеріали Всеросійських олімпіад, учбово-тренувальних зборів по інформатиці, різні книги і статті, присвячені даній тематиці.
http://g6prog.narod.ru - Сайт присвячений докладному розбору олімпіадних задач по інформатиці. Рівень задач від міської до міжнародної олімпіад. Програмні тексти до задач не додаються (представлений словесний опис рішення). До деяких задач додаються тести. Є багато корисних книг по олімпіадних задачах і велика кількість посилань на аналогічні ресурси.
http://byoi.narod.ru - Архів республіканських, міських, районних олімпіад, зборів до IOI. Підбір рідкісних, ефективних алгоритмів.
http://homepages.compuserve.de/chasluebeck - Дуже великий архів задач по інформатиці на російській мові.
http://www.stream.newmail.ru/index.html - Тут можна отримати відповідь на питання про олімпіади, взнати останні новини, підготуватися до олімпіад. На сайті є бібліотека книг і докладний каталог ресурсів.