Задачі співбесід та олімпіад з інформатики

 

Записувати алгоритм можна у вигляді блок-схеми або програми мовами Паскаль, С, Бейсик.

 

2001 рік

 

1. Дано масив X(100) и Y(100). Побудувати алгоритм, що міняє місцями значення елементів X(k) и Y(k) для цих масивів, не використовуючи допоміжні проміжні змінні.

2. На сільській вулиці живуть Шевченки та Бублики у власних будинках. Вони вирішили помінятися будинками так, щоб з одного краю вулиці жили Шевченки, а з іншого Бублики. Скласти алгоритм переселення такий, щоб кожна сім’я переселялася не більше 1 разу і в кожному обміні брали участь тільки 2 сім’ї.

3. Дослідити довжину періоду нескінченного степеневого дробу за основою Р, що представляє число N/M, (для скінченного дробу вважати довжину рівною 0), М, N, P – цілі числа.

4. Який мінімальний набір купюр (без використання 1 гривні) потрібен, щоб можна було виплатити довільну суму більшу 10 гривень.

5. Одержати розклад на прості множники числа n!.

6. Побудувати алгоритм видачі решти мінімальною кількістю монет в старій англійській грошовій системі (12 пенсів = 1 шилінг; 20 шилінгів = 1 фунт; 21 фунт = 1 гінея).

7. На аркуші в клітинку намальовано коло радіуса R, з центром на перетині ліній. Знайти кількість клітинок, які повністю лежать в середині кола.

8. Виконати циклічну перестановку 100 чисел, не використовуючи додаткової пам’яті.

9. Побудувати алгоритм виплати заданої суми копійок мінімальною кількістю сучасних українських монет.

10. Навести приклад задачі, алгоритм розв’язання якої не можна реалізувати на ПК Pentium III/900/256RAM/30G HDD/FDD.

11. Написати програму, що обчислює N-й елемент такої впорядкованої множини M:

    1) 1 є елементом множини M;

    2) якщо a – елемент множини, то 2a, 3a и 5a також є елементами множини M.

    3) інших елементів, окрім перерахованих у пп.1) і 2), у множині M немає.

12. Написати програму, яка визначає, чи є три задані натуральні числа взаємно простими і не використовує операцій множення, ділення та похідних від них (ділення націло і т.ін.).

13. Задано скінченну послідовність з лівих і правих круглих дужок. Перевірити, чи можна додати до неї цифри та знаки арифметичних дій так, щоб вийшов правильний арифметичний вираз.

14. Написати алгоритм знаходження всіх натуральних чисел, що не перевищують N і діляться на кожну зі своїх цифр, відмінну від нуля.

15. Задано два натуральні числа a та b. Скласти алгоритм, що перевіряє, чи є число c елементом такої множини M:

         1) a та b є елементами множини M;

         2) якщо x та y – елементи множини M, то x + y + xy також є елементом множини M.

         3) інших елементів, окрім перерахованих у пп.1) і 2), у множині M немає.

16. Номери білетів на маршрутне таксі складаються з 8 цифр від 00000000 до 99999999. Білет вважається щасливим, якщо сума цифр парних розрядів номера дорівнює сумі цифр непарних розрядів. Скласти алгоритм знаходження N-го по порядку щасливого білета.

 

 

2002 рік

 

1. Задано два натуральні числа. Перевірити, чи можна одне з них одержати за рахунок викреслювання цифр в іншому.

2. Є необмежена кількість пляшок місткістю V1, V2, …, Vn літрів. Скласти алгоритм, який перевіряє чи можна відміряти за їх допомогою об’єм V літрів рідини.

3. Досконалими називаються числа, які дорівнюють сумі всіх своїх дільників, включаючи 1 (наприклад 6 = 1 + 2 + 3). Скласти алгоритм пошуку N-го по порядку досконалого числа.

4. На двох аркушах в клітинку (розміром N ´ N) намальовано по одній геометричній фігурі шляхом фарбування деяких клітинок у чорний колір. Визначити чи рівні між собою утворені фігури.

5. З аркушу паперу в клітинку розміром M ´ N вирізали деякі клітинки. Знайти на яку кількість частин розпадеться після цього залишок аркушу. (Наприклад: Якщо вирізати з шахової дошки всі білі клітинки, то вона розпадеться на 32 частини)

6. Скласти алгоритм переводу числа з арабської форми запису у римську.

7. Є необмежена кількість прямокутників розміром A ´ B та C ´ D, чи можна з них скласти прямокутник розміром E ´ F ?

8. Написати алгоритм розкладу натурального числа N > 1 на суму натуральних доданків так, щоб їх добуток був максимальним.

 

 

 

2003 рік

 

1. Побудувати алгоритм знаходження найменшого натурального числа, якого немає серед чисел заданої таблиці розміру N ´ М.

2. У правильному N-кутнику (N > 3) провели кілька діагоналей так, що жодні 3 не перетинаються в одній точці. Проведені діагоналі задаються номерами кінцевих вершин. Скласти алгоритм знаходження кількості частин, на які ці діагоналі розбивають N-кутник.

3. Є n1 камінців вагою m1, n2 камінців вагою m2, … nk камінців вагою mk. Побудувати алгоритм перевірки, чи можна за допомогою цих камінців набрати вагу М.

4. K кісток (фішок) доміно задано парами чисел: (ni, mi), 1 ≤ i ≤ K, 0 ≤ ni, mi ≤ 6. Написати алгоритм перевірки, того що з цих кісток (фішок) можна скласти єдиний неперервний ланцюжок за правилами гри в доміно (стикуються сторони з однаковими числами).

5. Цифри двох n-розрядних (n > 1000) додатних чисел a та b в системі числення за основою k  записано в масивах А та В. Заповнити масив С цифрами числа a + b в тій самій системі числення.

6. Вершини куба знаходяться в точках з координатами (0,0,0); (0,0,1); (0,1,0); (0,1,1); (1,0,0); (1,0,1); (1,1,0); (1,1,1). На гранях куба вибрано дві точки з координатами A1(x1, y1, z1) та A2(x2, y2, z2). Знайти довжину найкоротшого шляху між цими точками по поверхні куба.

7. Записати алгоритм знаходження всіх натуральних чисел, які дорівнюють сумі кубів своїх цифр.

8. N-розрядні числа А та В задано послідовністю своїх цифр
aN, aN–1, …, a1, a0 та bN, bN–1, …, b1, b0 (100 < N < 10000). Записати алгоритм знаходження послідовності всіх цифр добутку А·В.

9. Трикутну піраміду задано координатами своїх вершин А1, А2, А3, А4. Записати алгоритм перевірки знаходження точки (x, y, z) всередині піраміди.

10. Точки А1, А2, А3, А4  на площині задано своїми координатами. Записати алгоритм знаходження найменшої площі опуклого многокутника, який містить ці 4 точки.

 

 

2004 рік

 

1. Є шахова дошка розміром N ´ N. Знайти довжину найкоротшого шляху на цій дошці шахового коня з клітинки з координатами (x1, y1) в клітинку з координатами (x2, y2).

2. Задано числа А та В, більші за 1 і менші за 10М. Не використовуючи операцій множення та ділення надрукувати значення А/В з точністю до N-го розряду після коми.

3. N-кутник задано координатами на площині послідовності (за годиннико­вою стрілкою) його вершин (x1,y1), (x2,y2), … , (xN,yN). Перевірити чи є цей N-кутник опуклим.

4. Многочлен aN×xN+aN–1×xN–1+aN–2×xN–2+ … +a1×x+a0 задано своїми коефіцієн­тами. Знайти всі його дійсні корені з точністю до N-го розряду після коми.

5. N прямокутників на площині зі сторонами паралельними осям координат задано координатами пари своїх вершин протилежних по діагоналі [(a1,b1), (c1,d1)]; [(a2,b2), (c3,d3)]; [(a4,b4), (c4,d4)]; … [(aN,bN), (cN,dN)]. Визначити, чи мають ці прямокутники спільну точку.

6. Задано алгебричний вираз, складений з невід’ємних дійсних чисел і знаків операцій + , –  і ´. Потрібно розставити в цьому виразі дужки так, щоб його значення стало найбільшим можливим.

7. Усередині квадрата з координатами лівого нижнього кута (0, 0) і правого верхнього кута (100, 100) розмістили N квадратиків, сторони яких паралельні осям координат і мають довжину 5. Жодні два квадратики не мають спільних точок. Потрібно знайти найкоротший шлях із точки (0, 0) в точку (100, 100), який не перетинав би жодного з цих N квадратиків.

8. Задано таблицю розміру M ´ N, що складається з цілих чисел. Фішка знаходиться у лівій верхній комірці таблиці. За один крок фішка може зміститися до сусідньої комірки, що знаходиться праворуч або знизу. Розробити алгоритм, що знаходить максимальну суму чисел у всіх комір­ках на шляху від початкової позиції фішки до правої нижньої комірки.

9. Розробити алгоритм, що дозволяє знайти усі такі розташування 8-ми ферзів на шахівниці розміром 8 ´ 8, що жоден ферзь не загрожує іншим.

10. Послідовність … будується так: спочатку записується 0, потім повторюється така дія: вже записану частину записують справа із заміною 0 на 1, 1 на 2 та 2 на 0, тобто 0; 01; 0112; 01121220… Розробити алгоритм, що знаходить цифру цієї послідовності з номером N.

11. Таблиця розміру M ´ N складається з нулів та одиниць, при цьому всі одиниці згруповано у прямокутники, та такі прямокутники не перетинаються. Розробити алгоритм, що знаходить кількість прямокутників у таблиці.


2005 рік

 

1. Решта. У невеликій крамниці виникли проблеми від того, що недосвідчений продавець не може підрахувати скільки решти давати покупцям. Треба розробити програму, що допоможе йому у цьому!

Наявними банкнотами є 20 грн., 10 грн., 5 грн., 2 грн. та 1 грн., монетами: 50 коп., 20 коп., 10 коп., 5 коп. Оскільки найменшою монетою є 5 коп., вартість покупки має заокруглюватись за таким принципом:

1 або 2 копійки – заокруглюється до 0.

3 або 4 копійки – заокруглюється до 5.

6 або 7 копійки – заокруглюється до 5.

8 або 9 копійки – заокруглюється до 10.

Програма має підрахувати решту та вказати які банкноти та монети використовувати, та у якій кількості. У кожному випадку сумарна кількість монет та банкнот має бути мінімальною з можливих.

2. Намисто. У пустелі Макмахара група дослідників знайшла залишки невідо­мої цивілізації. Було знайдено велику кількість намист, які використовува­лись представниками цієї цивілізації для запису чисел. Кожне з намист скла­дається зі з’єднаної в кільце нитки, на яку нанизано деяку кількість бусинок.

Бусинки бувають двох кольорів, чорного та білого, і, зрозуміло, що намиста використовувались для зображення двійкових чисел.

На жаль, ніхто не знає, чи позначає чорний колір 1, а білий – 0 або навпаки. Також не зрозуміло, де число починається і навіть у якому напрямку його читати!

Просте намисто, наведене нижче, може зображати кілька чисел.

 

 

Чорне як 1

Біле як 1

За годинниковою стрілкою

Проти годинникової стрілки

За годинниковою стрілкою

Проти годинникової стрілки

ЧЧЧБ = 14

БЧЧЧ = 7

ЧЧЧБ = 1

БЧЧЧ = 8

ЧЧБЧ = 13

ЧЧЧБ = 14

ЧЧБЧ = 2

ЧЧЧБ =1

ЧБЧЧ = 11

ЧЧБЧ = 13

ЧБЧЧ = 4

ЧЧБЧ = 2

БЧЧЧ = 7

ЧБЧЧ = 11

БЧЧЧ = 8

ЧБЧЧ = 4

 

Ми можемо сказати, що найменше число, яке можна зобразити – 1, найбільше 14.

У цьому простому випадку мінімальне та максимальне числа збігаються незалежно від того, читаємо ми число за годинниковою стрілкою чи проти. Однак, існують складніші випадки, коли різні напрямки читання дають різні найбільше та найменше значення. Ваша задача: написати програму, що за намистом визначає найбільше і найменше числа, яке воно може зображати.

3. Графіка. У деяких графічних програмах екран розділяють на 4 області, занумеровані 1, 2, 3, 4, кожна з частин ділиться рекурсивно за тим же принципом, на довільну глибину. За цією схемою, кожна комірка на екрані може бути унікально ідентифікована послідовністю цифр від 1 до 4, як на малюнку:

1

2

4

3

11

12

21

22

14

13

24

23

41

42

31

32

44

43

43

33

 

Задано послідовність цифр з діапазону 1–4, що ідентифікують початкову комірку та послідовність переміщень у формі В(вгору), Н(вниз), Л(ліворуч), П(праворуч). Вашою задачею є визначити комірку, в яку приведе задана послідовність рухів, також як послідовність цифр 1–4, або сповістити, що послідовність рухів виводить за межі екрана.

4. Монахи. Монахи Києво-Печерської Лаври відомі своєю любов’ю до програмування. Після багатьох років тренувань кожен монах має пройти фінальний тест, щоб увійти у спільноту програмістів. Під час тесту, новачка приводять у кімнату, в якій знаходяться 3 великі урни зі скляними бусинками. Його задача полягає у тому, щоб звільнити одну з урн, використовуючи спеціальну процедуру. Кожного дня новачок має обрати 2 урни, та обережно перекладати бусинки з однієї урни до другої до тих пір, поки кількість бусинок в урні, куди перекладають бусинка, не збільшиться вдвічі. Більше жодні бусинки не перекладаються.

Наприклад у трьох урнах було відповідно 115, 200 та 256 бусинок. Якщо перекладати бусинки з другої урни в першу в результаті отримаємо в урнах відповідно 230, 85 та 256 бусинок наприкінці першого дня. На другий день можна перекладати бусинки з урни, в якій 256 бусинок, до урни, де знаходиться 85 бусинок, отримавши в урнах відповідно 230, 170 та 171 бусинок наприкінці другого дня.

Якщо було 12, 30  та 12 бусинок, перемістивши бусинки з першої урни до третьої отримаємо 0, 30 та 24 бусинки, розв’язавши задачу.

Головний гуру спільноти хоче мати для кожного завдання, що отримує новачок, мінімальну кількість днів, потрібну для спорожнення однієї з урн. Ваша задача: написати програму, що за трьома числами – кількістю бусинок в урнах – визначатиме цю мінімальну кількість днів.

 

5. Ханойська вежа. Маємо три вертикальних стрижня. На один із стрижнів нанизані  n різних дисків, які впорядковані за розміром – найменший зверху,  найбільший знизу. Необхідно перенести початкову вежу на інший стрижень (будь-який із двох вільних). На кожному кроці дозволяється перекладати тільки один диск. Більший диск ніколи не повинен бути зверху меншого.

 

Приклад. Рішення для двох дисків

 

 

 

 

 

 


Довести, що будь-який алгоритм вирішення проблеми Ханойської вежі з  n дисками потребує не менше 2 n-1 перекладань дисків.

 

6. Новини по телефону. 230 друзів мешкають у різних містах і спілкуються між собою лише по телефону. Один телефонний дзвінок завжди триває одну хвилину. Дехто з друзів бажає поширити новину серед усіх інших за найменший час.

6.1. За який найменший час усі друзі можуть узнати про цю новину, якщо кожен з них може зробити не більш ніж 2 дзвінка.

6.2. Узагальнити задачу на випадок n друзів.

 

   

 

2006 рік

 

В печері знаходяться подільні (золото, срібло) та неподільні (ваза, сундук) скарби. Про кожний i - ий скарб відомі його вага wi, вартість ci та чи є він подільним (fi = 1 якщо скарб подільний, та fi = 0 інакше). Аладін може винести із печери скарбів вагою не більше W. Написати алгоритм, який обирає підмножину скарбів максимальної вартості, яку може винести Аладін із печери. Кількість різних скарбів у печері не більша за 1000.

Гравець має n карток з додатними числами. Склеюючи їх одна з одною, можна отримати різні довгі числа. Наприклад, із чисел 123, 124, 56, 90 можна отримати 24 різні числа: 1231245690, 1241235690, 5612312490, 9012312456, 9056124123 і так далі. Число 9056124123 є найбільшим серед них. Написати алгоритм, який для заданого набору чисел знаходить максимальне число, що можна отримати в результаті операцій склеювань.

Є набір двовимірних векторів, заданих своїми координатами (xi, yi). Необхідно знайти таку підмножину векторів, з яких можна скласти опуклий многокутник найбільшої площі. Написати алгоритм, який знаходить максимальну площу такого многокутника. Якщо опуклого многокутника скласти не можна, то вивести 0.0.

Бджола починає свій рух у клітину 1 або 2 і направляється до клітини з номером n. Пересуватися бджолі дозволяється лише по сусіднім клітинам від меншого номера до більшого. Скількома різними шляхами бджола може потрапити у клітину з номером  n?
Bee trace

 

2007 рік

1. Обчислювальний пристрій (калькулятор) працює тільки з цілими числами будь якої довжини, але має тільки одну комірку пам’яті. Пристрій може виконувати прості арифметичні дії: додавання, віднімання, множення, піднесення до квадрату.
Як на такому пристрої обчислити значення виразу
No description

2. Чи можливо розбити всі натуральні числа на дві множини таким чином, щоб ні одна з цих множин не містила ні однієї безкінечної цілочисельної  арифметичної прогресії.
Вкажіть алгоритм побудови перших n чисел ціх множин.

3. Послідовність чисел. Є масив рядків, відсортований лексикографічно. Кожний рядок в масиві містить лише цифри, тобто його можна трактувати як число. Числа в кожному рядку не більші за 2*109. Відсортувати рядки масиву як числа по зростанню.

 

Приклад входу

Приклад виходу

{"1","174","23","578","71","9"}

{"1", "9", "23", "71", "174", "578"}

{"172","172","172","23","23"}

{"23", "23", "172", "172", "172"}

 

4. K - ий елемент. Позначимо через F(n) функцію, яка обчислює кількість одиниць в бінарному представленні числа n. Наприклад, F(279) = 5, оскільки 279 = (100010111)2. Послідовність Х будується наступним чином: X0 = 0, Xi = A * F(Xi-1) + B. За заданими A, B, K знайти K - ий елемент послідовності Х. Відомо, що 0 ? A, B ? 106, 1 ? K ? 109.

 

Приклад входу

Приклад виходу

A

B

K

0

12

5

12

15

21

500000001

51

 

5. Стрічка. Стрічка довжини n складається з чорних та білих квадратів одиничного розміру. Стрічка кодується послідовністю чисел – кількістю чорних клітин, що стоять поруч зліва направо.

Наприклад, наведена вище стрічка має код 2, 3, 2, 8, 1. При цьому не враховується кількість білих клітин, якими розділяються чорні клітини. Вказаному коду задовольняє і така стрічка:

За довжиною стрічки n та її коду знайти кількість різних стрічок, що задовольняють цьому коду. Відомо, що 1 ? n ? 200, код має довжину g (0 ? g ? (n + 1) / 2) і сам код складається з g натуральних чисел.

 

Приклад входу

Приклад виходу

n

g

код

 

4

0

{}

1

5

2

{1, 2}

3

 

6. Гармонійні трійки. Трійка чисел (a, b, c) називається гармонійною, якщо виконується одна із наступних умов:

1. НСД(a, b) = 1, НСД(b, c) = 1, НСД(a, c) = 1

2. НСД(a, b) > 1, НСД(b, c) > 1, НСД(a, c) > 1

Під НСД(a, b) розуміється найбільший спільний дільник чисел a та b. Наприклад, трійка (2, 3, 4) не є гармонійною, а трійки (3, 4, 5) та (6, 8, 10) є гармонійними.

За заданим натуральним n (1 < n < 666666) знайти кількість гармонійних трійок (a, b, c), для яких a < b < c та 2 ? a, b, c ? n.

 

Приклад входу

Приклад виходу

4

0

31

1891

 

7. Думки навпаки. На площині розташовано m еліпсів, n кіл та p трикутників таким чином, що вони ділять її на максимально можливу кількість частин s. За заданим значенням s вивести усі такі можливі трійки чисел m, n, p, відсортувавши їх спочатку по m, а потім по n. Відомо, що 0 ? m, p < 100, 0 ? n < 20000. Якщо для вхідного s жодної трійки (m, n, p) не існує, то вивести Impossible.

 

Приклад входу

Приклад виходу

20

0 0 3

0 1 2

1 0 2

1 3 0

10

Impossible