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

Робота з масивами Pascal

Працюйте в системі http://www.e-olimp.com

Отримуйте високий рейтинг

Розв'язуйте задачі з тем

"Геометрія", "Графи", "Динамічне програмування"

Слідкуйте за новинами !!!

Тематика

1. Олімпіадна інформатика

2. Тематика завдань

3. Системи тестування (ejudge, e-olymp, Contester )

4. Оптимізація розв’язку (прості числа, лічилка)

5. Довга арифметика (факторіал, фібоначі)

6. Повний перебір (лексичний перебір)

7. Обчислювальна геометрія (ліві повороти, площа многокутника)

8. Теорія графів (пошук в глибину, остове дерево, алгоритм флойда)

9. Практикум з розв’язування задач

1.Олімпіадна інформатика

Що потрібне для успішної участі в олімпіадах по інформатиці? Як показує практика, тільки знання мови програмування для цього явно не достатньо. Взагалі, виявляється, що олімпіадні задачі по інформатиці лежать десь на стику математики і програмування. І дуже часто виявляється, що розв’язуючи задачі школярі не тільки вчаться програмувати, але і освоюють нові розділи математики.

Як перевіряються розв’язки задач олімпіади

Історично склалося так, що розв’язки на олімпіадах по програмуванню перевіряються автоматично. Ваше завдання написати програму, яка за заданими вхідними даними обчислює і виводить вихідні дані.

Апаратне та програмне забезпечення

Учасникам олімпіади можуть вибирати мову програмування с заданого переліку: Pascal, C або C++. Система програмування Free Pascal 2.0 (чи новішої версії), GCC 4.2 (чи новішої версії), Turbo Delphi Explorer, Visual C++ 2008 Express).

2. Тематика задача олімпіади

Завдання олімпіади мають бути алгоритмічного характеру, тобто основними результатами роботи учасника має бути: алгоритм, що правильно та ефективно розв’язує поставлену задачу, та програма, що реалізує запропонований алгоритм.

Основними категоріями олімпіадних задач є:

3.Системи тестування (ejudge, e-olymp, Contester )

Працюйте в он-лайн системах, які автоматично перевіряють та тестують Ваші розв’язки:

http://olymp.sumdu.edu.ua - Веб-ресурс підтримки та проведення шкільних та студентських олімпіад з інформатики

http://www.e-olimp.com.ua/ -  Інтернет-портал організаційно-методичного забезпечення дистанційних олімпіад з програмування для обдарованої молоді навчальних закладів України

http://www.olymp.vinnica.ua/ - Центр підтримки та проведення олімпіад школярів з використанням можливостей Internet.

Список тестуючи систем

Список ресурсів

http://vippolabinfo.16mb.com – сайт «Лабораторія інформатики сьогодні»,  методична підтримки напрямків роботи.

http://vippoolimp.16mb.com – Волинська учнівська Інтернет олімпіада з програмування.

http://schoololymp.byethost32.com – заочна школа роботи з обдарованими учнями з інформатики.

4. Оптимізація розв’язку (прості числа, лічилка)

5.Довга арифметика (факторіал, фібоначі)

6.Повний перебір (лексичний перебір)

Побудуємо лексичний перебір для довільних  елементів масиву

X=3 2 4 2 4 3 1

а) Рухаємось справа наліво. Крок вперед можна зробити, якщо  наступне число більше за попереднє. Ми зупинилися перед числом 2. Це число потрібно помітити.

X=3  2  4  2 4   3 1

б) Рухаємось справа наліво. Крок вперед можна зробити, якщо   число менше за знайдене число(2). Ми зупинилися перед числом 3. Це число потрібно помітити.

X= 3  2  4  2 4  3 1

в) Переставляємо знайдені числа.

X= 3  2  4  3 4  2 1

г) Запишемо числа, розміщені після першого знайденого в зворотному порядку.

X=3  2  4  3 1  2  4

7.Обчислювальна геометрія (ліві повороти, площа многокутника)

Ліві повороти

{Визначення координат векторів}
x[n+1]:=x[1];
y[n+1]:=y[1];
for i:=1 to n do begin
a[i]:=x[i+1]-x[i];
b[i]:=y[i+1]-y[i];
end;
{Підрахунок кількості додатних добутків}
a[n+1]:=a[1];
b[n+1]:=b[1];
k:=0;
for i:=1 to n do
if a[i]*b[i+1]-a[i+1]*b[i]>=0 then k:=k+1;

За заданими кількістю вершин і координатами n-кутника визначити його площу (15 балів).

x[n+1]=x[1]

y[n+1]=y[1]

s=0

для i=1 дo n

s=s+ (x[i]*y[i+1]-x[i+1]*y[i]

s=1/2*abs(s);

8.Теорія графів (пошук в глибину, остове дерево, алгоритм флойда)

Основні поняття теорії графів

1. Граф представляє собою не порожню множину точок і ліній, два кінці котрих належать заданій множині точок. 

Неорієнтований граф:

Відкриті Ейлером властивості графа:

1. Число непарних вершин зв'язного графа завжди парне. Неможливо накреслити граф з непарним числом непарних вершин.

2. Якщо  всі  вершини графа парні,  то можна одним розчерком (тобто не відриваючи олівця від паперу) накреслити граф, не проводячи по кожному ребру більше одного разу. При цьому можна починати з будь-якої вершини графа і закінчувати його в тій же вершині.

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

4. Граф з більше ніж  двома  непарними  вершинами  неможливо накреслити одним розчерком.

Гамільтонів шлях проходить через кожну вершину по одному разу (по ребрах проходить декілька разів або жодного)

Ейлеровий шлях – це шлях, який ми проходимо з однієї вершини в іншу через всі ребра тільки один раз.

Задача про туриста (пошук в глибину)

Турбаза мала для ночівлі N місць, з’єднаних стежками. Туристів можна вести в одну сторону. Довжина стежки – одноденний перехід. Пройти і перевірити всі M-денні маршрути, які починаються на базі K.

Орієнтований ненавантажений граф.

n=6; m=3; k=1;

Дано орієнтований ненавантажений граф. N вершин. Знайти всі маршрути довжини m=3, які виходять з вершини з номером k.

Алгоритм Флойда-Уоршелла

З алгоритму Дейкстри зрозуміло, що можна знайти найкоротшу відстань від заданої вершини графа до решти його вершин. А якщо ця інформація потрібна для будь-якої вершини графа? Найперша відповідь, яка спадає на думку: необхідно виконати алгоритм Дейкстри в циклі для всіх вершин графа. Питання лише в часі виконання такого алгоритму, оскільки його оцінка буде О(п³). Однак існує компактніший за записом алгоритм Флойда-Уоршелла, з яким ми зараз і ознайомимося.

Запишемо сам алгоритм:

1. Визначити вершину графа k = 1, через яку буде здійснюватися перерахунок відстані між вершинами і та j.

2. Визначити вершину і = 1.  Визначити вершину j = 1,

3. Якщо величина d_{j, k} + d_k,j менша за значення d_i,j ,то замінити значення d_i,j на d_{i, k} + d_k,і . В іншому разі залишити зна­чення d_i,j без змін.

4. Якщо j <= п, то перейти до наступної вершини j+ 1 і повер­нутися до п. 4.

5. Якщо i<= п, то перейти до наступної вершини і + 1 і повернутися до п. 3.

6. Якщо k<=n, то перейти до наступної вершини k + 1 і повер­нутися до п. 2,

7. Завершити алгоритм.

У результаті виконання алгоритму елементи d_i,j будуть міс­тити найкоротшу відстань між відповідними вершинами графа і та j.

Реалізація алгоритму Флойда-Уоршелла мовою Pascal буде такою:

for k := 1 to n do

for і := 1 to n do

for j := 1 to n do

if d[i,k]+d[k,j]<d[i,j] then d[i,j]:=d[i, k]+d[k,j];

9.Практикум з розв’язування задач

Задача 4 «Зернинки»

Задача 5. Банкомат

Задачі 6. Купування квитків

Тема. Жадібні алгоритми

Задача 1. Центи

Задача 2. Кінцевий результат

Задача 3 Знижки

А  - Неуважність

Степан вдало пройшов співбесіду і ось уже як чотири місяці працює на одній із самих престижних ІТ компаній. Прийшов час здавати проект менеджеру і Степан, як істинний студент, все виконує у останню ніч перед здачею. Набирає текст Степан звичайно дуже швидко, але неуважно. От і цього разу останню частину тексту він набрав не звернувши уваги, що випадково натиснув клавішу caps lock. Таким чином великі букви були набрані маленькими, а маленькі великими. Інші символи він набрав вірно. Степан настільки стомився, що немає сил виправити помилки, і він вирішив кілька годин поспати. Допоможіть Степану, доки він спить, напишіть програму, яка виправляє неуважно набраний текст.

Формат вхідних даних: перший рядок вхідного файлу містить неуважно набраний Степаном текст, який містить не більше 500 символів.

Формат вихідних даних: вихідний файл має містити виправлений текст.

Приклади

sCHOOL

School

B - День святого Валентина

Скоро день святого Валентина і, Степану як великому прихильнику даного свята, доручили вибрати кульки для прикраси зали. Профорг університету, де навчається Степан, веде строгий перелік усіх кульок, згідно якому в наявності є N однокольорових (що поробиш – бідні студенти) кульок, діаметр i-ї кульки (1 ≤ i ≤ N) дорівнює Di міліметрів. Згідно новим вимогам профкому, залу необхідно прикрасити не менше ніж K кульками. Оскільки профоргу університету не подобається свято закоханих, то вона ввела своє поняття – так званий показник некрасивості – рівний максимально можливому числу Di – Dj при 1 ≤ i, j ≤ M, де M – кількість кульок для зали, а Di – їх діаметр. Допоможіть Степану із N іграшок вибрати М (M ≥ K) так, щоб для вибраних M кульок показник некрасивості був мінімальним.

Формат вхідних даних: перший рядок вхідного файлу містить два натуральних числа N (2 ≤ N ≤ 100 000) і K (2 ≤ K ≤ N) відповідно. Другий рядок містить N цілих чисел Di (1 ≤ Di ≤ 10⁹) – діаметр i-ї кульки.

Формат вихідних даних: вихідний файл має містити значення показника некрасивості, вибраних M кульок.

Пояснення: Приклад 1 - Існує кілька різних варіантів вибору. Степан може вибрати, наприклад, 6 кульок: 3, 5, 6, 4, 7 і 8
Приклад 2- Степан вибере 4 кульки: 1, 5, 3 і 6.

Приклади

8 5

10 20 10 20 10 10 20 20

10

6 4

21 12 17 28 16 21

5

C - Степан і Пари

Останнім часом Степан дуже цікавиться парами чисел, а крім пар чисел його цікавить найбільший спільний дільник пари чисел, позначимо його як НСД(x, y). Зараз у Степана є ціле число n і його цікавить така інформація: скільки існує пар цілих чисел (i,j), таких що 1 ≤ i, j ≤ n і виконується рівність i = НСД(i, j). Допоможіть йому у вирішенні нелегкої задачі.

Формат вхідних даних: у першому рядку дано ціле число n (1 ≤ n ≤ 10⁶).

Формат вихідних даних: єдиний рядок має містити відповідь на задачу.

Зауваження: У першому прикладі підходящою парою є пара (1, 1), так як НСД(1, 1) = 1.
У другому прикладі підходять 8 пар чисел: (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4).

Приклади

1

1

4

8

10

27

D - Спадок Степана

Степан отримав у спадок від дідуся стоянку з N місць, пронумерованих від 1 до N. Стоянка розбита на дві частини. Перші M місць знаходяться з лівого боку, а інші N - M місць з правого. Кожного дня N жителів цього району паркують свої автомобілі на стоянці Степана. Відомо, що перший житель приходить раніше усіх, потім другий, і так далі, тобто k-й приходить k-м. Також для кожного жителя i відомо, скільки він буде платити, якщо його машину поставлять на j-е місце. Степан придбав розподільник місць, який кожному автомобілю, що приїздить вказує, на який бік паркуватись, після чого автомобіль паркується на мінімальне за номером вільне місце відповідного боку. При цьому Степан вирішив зекономити і не придбав програмне забезпечення для розподільника, тому він працює не оптимально. Степан просить Вас написати програму для цього розподільника, яка максимізує доходи Степана.

Формат вхідних даних: у першому рядку записані два цілих числа N (2 ≤ N ≤ 1000) і M (1 ≤ M < N) – загальна кількість місць на стоянці і кількість місць з лівого боку відповідно. У кожному із наступних N рядків записано по N цілих додатних чисел. j-е число i-го рядка означає, скільки буде платити i-ий житель за місце з номером j на цій стоянці. Кожне з цих чисел не перевищує 10⁶.

Формат вихідних даних: єдиний рядок має містити одне число – максимальний прибуток стоянки.

Зауваження: Не менш чим у 50% тестів N ≤ 30.

Приклади

2 1

3 2

6 4

8

4 1

4 3 1 1

3 1 1 1

1 1 4 1

1 1 1 2

12

E- Конфетна проблема Степана

Степан закохався і вирішив привернути увагу дівчини великою коробкою цукерок. За порадою друзів він поїхав на саму відому кондитерську фабрику ShenRo і дізнався, що великі коробки цукерок мають трикутну форму. Цукерки в цих коробках розташовуються у кілька рядів. У першому ряду знаходиться одна цукерка, у другому – дві, у третьому – три цукерки і так далі. На фабриці випускаються коробки цукерок з любим числом рядів у межах від 1 до N. Степан хоче купити одну із таких коробок. Але є одна проблема: його дівчина засмутиться, якщо кількість цукерок у коробці не буде ділитись націло на M, тому що у цьому випадку комусь із друзів дівчини дістанеться більше цукерок, чим іншим, або ж якісь цукерки залишаться лишніми. Тому Степан вирішив, що число цукерок у коробці має обов’язково ділитись націло на M.

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

Вам необхідно по заданих числах N і M знайти число способів вибору коробки цукерок із множини коробок з кількістю рядів від 1 до N. Способи вважаються різними, якщо їм відповідають коробки з різною кількістю рядів цукерок.

Формат вхідних даних: перший рядок вхідного файлу містить два цілих числа N - максимальна кількість рядів цукерок у коробці і M – кількість друзів дівчини Степана (1 ≤ N, M ≤ 2*10⁹) відповідно.

Формат вихідних даних: вихідний файл має містити одне ціле число - кількість різних способів вибору коробки цукерок.

Оцінювання: N, M ≤ 1000 – не менше 35 балів, N, M ≤ 10⁵ – не менше 55 балів.

Приклади

20 10

4

53 199

0

5705 145

157

А - Арифметика

Молодший брат Степана Мишко навчається у першому класі. Він дуже допитливий і постійно дістає Степана запитаннями: А скільки? А чому? Сьогоднішній день не виключення. Мишко каліграфічно виписує цифри в ряд і запитує: А скільки різних цифр у записі цього числа. На перші приклади Степан швидко знаходив відповідь. Але Мишко чим далі, тим більші числа записував. Це стало для Степана проблемою. Допоможіть Степану, напишіть програму, яка визначає, кількість різних цифр у числі Мишка.

Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N (1 ≤ N ≤ 10¹⁰⁰⁰), записане Мишком.

Формат вихідних даних: вихідний файл має містити одне число – кількість різних цифр у числі.

Приклади

1233

3

B- Степан і сірники

Степан дуже полюбляє гратись із сірниками. Але він не балується ними, не розпалює вогонь, а розв'язує різні головоломки. Наприклад, він уміє прирівнювати число дев'ять до числа одинадцять, переклавши лише один сірник. Нещодавно батьки Степана подарували йому декілька наборів, кожен з яких складається з дванадцяти сірників. Хлопчик почав збирати з них різні геометричні фігури. Він вже зібрав багато різних фігур, але тепер йому стало цікаво: з яких наборів можливо склеїти каркас паралелепіпеда за допомогою дванадцяти сірників з набору та клею? Ламати сірники не можна і жоден із сірників не повинен виступати за каркас.

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

Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N (1 ≤ N ≤ 100), яке представляє кількість наборів. Далі йдуть N рядків, кожен з яких містить у собі опис набору сірників - дванадцять цілих додатніх чисел не перевищують 10⁹.

Формат вихідних даних: вихідний файл має містити N рядків. Для кожного набору сірників виведіть “yes”, якщо з нього можливо склеїти каркас паралелепіпеда, і “no” в іншому випадку.

Приклади

2

1 1 1 1 2 2 2 2 3 3 3 3

1 1 1 1 2 2 2 2 3 3 3 4

yes

no

C - Задача від Степана

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

Наприклад, прямокутник зі сторонами 1 і 10 можна повністю накрити прямокутником 10 і 3, але не можна накрити прямокутником зі сторонами 9 і 9. Прямокутники зі сторонами 10 і 3, а також зі сторонами 9 і 9 накрити не можна, відповідно в наборі із цих трьох прямокутників тільки один маленький. Напишіть програму, яка вирішить згадану Степаном задачу – визначить кількість маленьких прямокутників у даному наборі.

Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число N (2 ≤ N ≤ 200000). У кожному з наступних N рядків міститься два цілих додатних числа – розміри одного прямокутника. Усі розміри не перевищують 1000000. Серед даних прямокутників немає однакових.

Формат вихідних даних: вихідний файл має містити одне ціле число - кількість маленьких прямокутників у даному наборі.

Приклади

3

1 10

9 9

10 3

1

4

1 7

2 6

3 5

4 4

0

D - Штрафи

Степан нещодавно купив автомобіль, але водійські права ще не отримав. В зв’язку з цим він не має права на ньому їздити. Але його дружина вже спланувала вихідні, і поїздка до столиці входить в ці плани. Недовго думаючи, Степан знайшов вихід. Відомо, що ДАІ стоять не на всіх дорогах, а лише на тих, які обминути не можна, тому що так вони спіймають більше правопорушників. Відомо, що в країні Степана N міст, і вони з’єднані M дорогами. Зрозуміло, ніякі дві дороги не з’єднують одну й ту саму пару міст (в країні ж розумні люди працюють). Степан живе в місті А, а столиця знаходиться в місті 1. За відсутність водійських прав штраф складає 1000 карбованців. Скажіть, скільки в нього має бути при собі грошей, щоб він міг виплатити всі штрафи.

Формат вхідних даних: Перший рядок містить два числа N, M (2 ≤ N ≤ 10⁵ , 1 ≤ M ≤ 10⁵). Інші М рядків містять два числа Xi і Yi, які описують дорогу між містом Xi і містом Yi. В останньому рядку написано число A (2 ≤ A ≤ N) – місто в якому живе Степан.

Формат вихідних даних: Виведіть в одному рядку єдине число – кількість карбованців які Степан має мати при собі.

Приклади

6 7

1 2 

2 3

3 1

3 4

4 5

4 6

5 6

6

1000

E - Ремонт

Степан придбав нову квартиру і до приїзду батьків вирішив поклеїти шпалери. На перший погляд все просто, але, коли він приступив до роботи, виявилась невелика проблема – необхідно вирівнювати малюнки на сусідніх полосах шпалер. Як визнаний програміст, Степан сформулював задачу таким чином. Кожну полосу шпалер можна описати її частиною – прямокутником довжиною N і шириною M (щоб отримати повну полосу, цей прямокутник можна багато разів домалювати до самого себе справа і зліва). Для простоти подумки поділимо цей прямокутник на рівні клітинки так, щоб утворилось N рядків і М стовпців. Щоб було ще простіше, рисунок на шпалерах позначимо символами ”.” і ”*” (крапка і зірочка), по одному символу в кожній клітинці.

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

Формат вхідних даних: перший рядок вхідного файлу містить два цілих числа N і M(1 ≤ N ≤ 20, 1 ≤ M ≤ 100000). Наступні N рядків містять по М символів кожна – опис першої полоси шпалер. Наступні N рядків містять по М символів кожна – опис другої полоси шпалер. Кожен рядок опису шпалер містить тільки символи ”.” і ”*”.

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

Приклади

2 5

.*.*.

*.*.*

*.*..

.*.**

1

1 5

***..

*..**

2

Учасники олімпіади можуть вибирати мову програмування знаступного переліку: Pascal, C або C++. Середовища розробки програм FreePascal 2.4.0 (чи новішої версії), CodeBlocks 10.05 (чи новішої версії), GCC 4.6(чи новішої версії). Для перевірки робіт учасників будуть використані такі версії компіляторів: FPC 2.4, GCC 4.6. У зв’язку із специфікою задач, що не вимагають візуального середовища розробки і помилками викликаними написаннями програм в TurboDelphiExplorer та Visual C++ ці середовища на ІV етапі доступними не будуть.

задача 1. abc, cba, acb,bac,acb,bca

задача 2. НСД різниці координат + 1

задача 3. кексики

задача 4. синтаксичний аналіз виразу (автомати)

задача 5. сортуванння, сума з k+1 до N

задача 6. дільники= парне, непарне

задача 7. дільники= 2, 3 5

задача 8. трикутне число – сума чисел від 1 до N, S=(N-1)/2*N;