П`ятниця, 29.03.2024, 17:25
Головна Реєстрація RSS
Вітаю Вас, Гість
Наше опитування
Оцініть мій сайт
Всього відповідей: 68
Головна » 2017 » Лютий » 13 » Перший тур 3-етапу Всеукраїнської олімпіади з інформатики 2016/2017 н.р.
20:08
Перший тур 3-етапу Всеукраїнської олімпіади з інформатики 2016/2017 н.р.

13 лютого 2017 року відбувся перший тур ІІІ-го обласного етапу Всеукраїнської учнівської олімпіади з інформатики 2016/2017 н.р. Він проводився з використанням автоматичної системи прийняття та перевірки робіт учасників олімпіади. У зв’язку з цим на порталі Хмельницького обласного інституту післядипломної педагогічної освіти (http://sbs2.km.ua/olymp/) сервер було увімкнуто з 11.00 до 16.00 для учасників олімпіади з інформатики.

В першому турі взяли участь 87 учнів з 17 районів і 12 міст.

Переяслав-Хмельницький район представляли учні Хоцьківської ЗОШ І-ІІІ ступенів:

Коваленко Валентина - учениця 7-го класу (8 клас),
Янча Тетяна (9 клас),
Чухно Катерина (10 клас),
Козій Іван (11 клас).

Submit a solution for A

Full score:100
Input file name:laugh.in
Output file name:laugh.out
Time limit:100 ms
Real time limit:5 s
Memory limit:64M

Сміх
Степан любить багато сміятися. Сміх - це послідовність букв «a» і «h», які чергуються. Так наприклад, «ahahaha», «hah» і «a» є сміхом, а «abacaba» і «hh» - ні. Степан розмовляє дуже швидко, тому всі його слова зливаються в одне велике. Для дослідження вам потрібно з'ясувати, як довго він може сміятися. У вас є рядок - запис розмови Степана. Визначте найбільшу довжину сміху в цій розмові.
Вхідні дані:
Перший рядок вхідного файлу містить одне натуральне число N (1 ≤ N ≤ 105) - довжина рядка з розмовою Степана. У другому рядку міститься рядок з маленьких латинських букв довжиною N - запис розмови Степана.
Вихідні дані:
У вихідний файл виведіть одне число - найбільшу довжину сміху в розмові Степана.
Система оцінювання: В даній задачі кожен тест оцінюється окремо.
Examples
Input in laugh.inOutput in laugh.out
5
ahaha
5

24
ahahrunawayahahsofasthah
4

10
ahahaahaha
5

 


Submit a solution for B

Full score:100
Input file name:fractions.in
Output file name:fractions.out
Time limit:100 ms
Real time limit:5 s
Memory limit:64M

Операції з дробами
Дроби, як відомо, давня слабкість Степана. Ось і зараз він бере правильний раціональний нескоротний дріб a/b і виконує з ним наступні операції: до чисельника і знаменника дробу додає 1, а потім дріб скорочує до нескоротного. Степана зацікавило питання, чи можна за допомогою таких операцій з дробу a/b отримати правильний дріб c/d. Допоможіть Степану.
Вхідні дані:
Єдиний рядок вхідного файлу містить чотири числа a, b, c, d (0 < a < b ≤ 105, 0 < c < d ≤ 105), числа a і b взаємно прості, c і d взаємно прості, a/b ≠ c/d.
Вихідні дані:
Виведіть одне натуральне число - скільки описаних операцій потрібно зробити, щоб з дробу a/b отримати правильний дріб c/d. Якщо цього зробити не можливо, то виведіть 0.
Система оцінювання: В даній задачі кожен тест оцінюється окремо.
Examples
Input in fractions.inOutput in fractions.out
1 3 2 32
2 3 1 30

 


Submit a solution for C

Full score:100
Input file name:maximum.in
Output file name:maximum.out
Time limit:100 ms
Real time limit:5 s
Memory limit:64M

Максимальний добуток
Степан останнім часом приділяв мало уваги програмуванню і як, результат, не здав залік. Тепер йому потрібно терміново вирішити наступну задачу: Дано масив цілих чисел A1, A2, ..., AN, абсолютна величина елементів якого не перевищує 2. Потрібно знайти такий непорожній підвідрізок Al, Al+1, ..., Ar цього масиву (1 ≤ l ≤ r ≤ N), що добуток чисел Al * Al+1 * ... * Ar є максимально можливим. Звісно, Степан просить у вас допомоги у вирішенні даної задачі.
Вхідні дані:
В першому рядку вхідного файлу знаходиться число N (1 ≤ N ≤ 200 000) — кiлькiсть елементів масиву. В другому рядку знаходиться N цiлих чисел Ai (-2 ≤ Ai ≤ 2) - елементи масиву.
Вихідні дані:
Єдиний рядок вихідного файлу має містити два числа l і r - знайдені границі оптимального відрізка (1 ≤ l ≤ r ≤ N). Якщо iснує декiлька вiдповiдей, виведiть будь-яку з них.
Система оцінювання: В даній задачі кожен тест оцінюється окремо.
Examples
Input in maximum.inOutput in maximum.out
5
1 -1 2 2 1
3 5

3
-1 0 -2
2 2

 


Submit a solution for D

Full score:100
Input file name:dream.in
Output file name:dream.out
Time limit:100 ms
Real time limit:5 s
Memory limit:64M

Дивний сон
Степану сниться дивний сон. У ньому Степан знаходиться на полі в клітиночку розміром N × M в клітинці з координатами (x, y). Спочатку Степан дивиться уздовж додатного напрямку осі X. Потім він починає йти по полю з наступною закономірністю:
- Пройти на одну клітинку вперед. Повернути на 90° вправо.
- Пройти на одну клітинку вперед. Повернути на 90° вправо.
- Пройти на дві клітинки вперед. Повернути на 90° вправо.
- Пройти на дві клітинки вперед. Повернути на 90° вправо.
- Пройти на три клітинки вперед. Повернути на 90° вправо.
- Пройти на три клітини вперед. Повернути на 90° вправо.
- Пройти на чотири клітини вперед. Повернути на 90° вправо.
- І так далі...
Рух триває до тих пір, поки Степан не вийде за межі поля. Після цього він прокидається. Вранці Степан вирішив проаналізувати свій сон. Він здогадався, що в кожній клітинці він був максимум один раз, але ніяк не може згадати, скільки клітинок він відвідав. Степан просить вас написати програму, яка порахує кількість відвіданих ним клітинок.
Вхідні дані:
У першому рядку вхідного файлу знаходяться два натуральних числа N, M (1 ≤ N, M ≤ 109) - розміри дошки уздовж осі X і осі Y відповідно. У другому рядку знаходяться два натуральних числа x, y (1 ≤ x ≤ N; 1 ≤ y ≤ M) - координати стартової позиції Степана.
Вихідні дані:
У вихідний файл виведіть одне число - кількість клітинок, відвіданих Степаном уві сні.
Система оцінювання: В даній задачі кожен тест оцінюється окремо.
Examples
Input in dream.inOutput in dream.out
7 6
3 4
36

2 2
1 1
2

2 2
1 2
4

 


Submit a solution for E

Full score:100
Input file name:virus.in
Output file name:virus.out
Time limit:150 ms
Real time limit:5 s
Memory limit:64M

Вірус
Степан дуже ретельно слідкує за своїм здоров'ям. Кожного дня він читає книги з медицини і шукає інформацію про нові хвороби, тому вже давно знає, що різні хвороби можуть збуджуватись вірусами. Степану давно відомі деякі види вірусів і він перевірив, що жодного з них у нього не має. Але, одного не самого вдалого для Степана дня, він дізнався, що віруси можуть мутувати. Нехай ДНК віруса представлено у вигляді рядка t, який складається з n маленьких літер латинського алфавіту. В книзі було написано, що в представленні мутивованого вірусу рівно два символа, які стоять один від одного на k позицій: si i si+k при i ∈ [1; n-k], замінено на деякі інші. Дізнавшись таку страшну новину, Степан одразу кинувся перевіряти, чи не хворіє він мутивованим вірусом. ДНК Степана також є рядком з маленьких літер латинського алфавіту. Допоможіть йому дізнатись, чи є в його ДНК підрядки довжиною n, які підходять під опис мутивованого віруса, наведений вище.
Вхідні дані:
В першому рядку вхідного файлу дано представлення ДНК Степана s - рядок з маленьких літер латинського алфавіту. У другому рядку задано представлення ДНК віруса t - рядок з n маленьких літер латинського алфавіту. В третьому рядку задано число k (1 ≤ k ≤ n-1).
Вихідні дані:
У перший рядок вихідного файлу виведіть скільки разів мутивований вірус зустрічається в ДНК Степана. У другому рядку виведіть через пробіл в зростаючому порядку індекси початку входження мутивованого вірусу.
Система оцінювання: В даній задачі три підзадачі. Бали за кожну підзадачу нараховуються тільки якщо усі тести підзадачі пройдені.
Підзадача 1 (30 балів): ДНК Степана і віруса складаються не більш чим із 100 символів.
Підзадача 2 (30 балів): ДНК Степана і віруса складаються не більш чим із 10 000 символів.
Підзадача 3 (40 балів): ДНК Степана і віруса складаються не більш чим із 200 000 символів.
Examples
Input in virus.inOutput in virus.out
abaaaaa
baab
3
2
3 4

Наверх

Переглядів: 921 | Додав: ivv
Всього коментарів: 0
avatar