Вівторок, 21.09.2021, 22:39
Головна Реєстрація RSS
Вітаю Вас, Гість
Наше опитування
Оцініть мій сайт
Всього відповідей: 62
ІІІ ЕТАП ВСЕУКРАЇНСЬКОЇ УЧНІВСЬКОЇ ОЛІМІПАДИ З ІНФОРМАТИКИ 2012-2013 НАВЧАЛЬНОГО РОКУ
8-11 клас

І тур

А – Неуважність
Ім'я файлу, який містить вхідні дані:text.in
Ім'я вихідного файлу:text.out
Обмеження часу:100 мс
Обмеження пам'яті:128 M

Степан вдало пройшов співбесіду і ось уже як чотири місяці працює на одній із найпрестижніших ІТ-компаній. Прийшов час здавати проект менеджеру і Степан, як істинний студент, усе виконує в останню ніч перед здачею. Набирає текст Степан звичайно дуже швидко, але неуважно. От і цього разу останню частину тексту він набрав, не звернувши уваги, що випадково натиснув клавішу Сaps Lock. Таким чином, великі букви були набрані маленькими, а маленькі – великими. Інші символи він набрав вірно. Степан настільки стомився, що немав сил виправити помилки, і він вирішив кілька годин поспати. Допоможіть Степану, доки він спить. Напишіть програму, яка виправляє неуважно набраний текст.
Формат вхідних даних: перший рядок вхідного файлу містить неуважно набраний Степаном текст, який містить не більше 500 символів.
Формат вихідних даних: вихідний файл має містити виправлений текст.
Приклади
Вхідні дані розміщені у файлі text.in Результат роботи знаходиться у файлі text.out
sCHOOLSchool
Ідея розв’язку задачі
Посимвольно зчитати дані до кінця рядка у файлі і, перевіривши належність зчитаного символу до великих або до малих літер латинського алфавіту, виконати відповідний перевід символів. Для переведення малих букв у великі можна скористатися стандартною функцією UpCase. Для переведення з великих у малі можна використати особливість системи ASCII. У цій системі кодування текстової інформації всі символи стоять під визначеними номерами. Якщо знайти різницю в коді малої літери «а» від великої та, додавши до неї значення коду поточної великої літери, знайдемо код шуканої малої літери ord(x) +ord('a')-ord('A'). Використавши обернену функцію chr, знайдемо шукану велику букву.
Розв’язок


B – День святого Валентина
Ім'я файлу, який містить вхідні дані:holy.in
Ім'я вихідного файлу:holy.out
Обмеження часу:500 мс
Обмеження пам'яті:128 M

Скоро день святого Валентина і, Степану як великому прихильнику даного свята, доручили вибрати кульки для прикраси зали. Профорг університету, де навчається Степан, веде строгий перелік усіх кульок, згідно якому в наявності є 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.
Приклади
Вхідні дані
розміщені у файлі holy.in
Результат роботи знаходиться у файлі holy.out
8 5
10 20 10 20 10 10 20 20
10

6 4
21 12 17 28 16 21
5

Ідея розв’язку задачі
Спочатку необхідно відсортувати масив по зростанню. Потім брати послідовно K кульок і шукати різницю діаметрів найменшої (i-ї) та найбільшої (k-ї). Серед отриманих різниць вибрати найменшу.
Розв’язок


С- Степан і Пари
Ім'я файлу, який містить вхідні дані:pair.in
Ім'я вихідного файлу:pair.out
Обмеження часу:1 с
Обмеження пам'яті:128 M

Останнім часом Степан дуже цікавиться парами чисел. А крім пар чисел, його цікавить найбільший спільний дільник пари чисел, позначимо його як НСД(x, y). Зараз у Степана є ціле число n і його цікавить така інформація: скільки існує пар цілих чисел (i, j), таких що 1 ≤ i, j ≤ n і виконується рівність i = НСД(i, j). Допоможіть йому у вирішенні нелегкої задачі.
Формат вхідних даних: у першому рядку дано ціле число n (1 ≤ n ≤ 106).
Формат вихідних даних: єдиний рядок має містити відповідь на задачу.
Зауваження: У першому прикладі підходящою парою є пара (1, 1), так як НСД(1, 1) = 1.У другому прикладі підходять 8 пар чисел:
(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4).
Приклади
Вхідні дані
розміщені у файлі pair.in
Результат роботи знаходиться у файлі pair.out
11
48
1027
Ідея розв’язку задачі
Розглянемо всі числа i та j (1 ≤ i ≤ n, i ≤, j ≤ n), щоб НСД(i, j) = i. Перевіряти всі числа i, починаючи з числа 2-го й обраховувати, скільки цілих чисел, не менших за n, діляться націло на i.
Розв’язок


D – Спадок Степана
Ім'я файлу, який містить вхідні дані:legacy.in
Ім'я вихідного файлу:legacy.out
Обмеження часу:2 с
Обмеження пам'яті:128 M

Степан отримав у спадок від дідуся стоянку із N місць, пронумерованих від 1 до N. Стоянка розбита на дві частини. Перші M місць знаходяться з лівого боку, а інші N – M місць з правого. Кожного дня N жителів цього району паркуються на стоянці Степана. Відомо, що перший житель приходить раніше всіх, потім другий, і так далі, тобто k-й приходить k-м. Також для кожного жителя відомо, скільки він буде платити, якщо його машину поставлять на j-е місце. Степан придбав розподільник місць, який кожному автомобілю, що приїздить вказує, на який бік паркуватися, після чого автомобіль паркується на мінімальне за номером вільне місце відповідного боку. При цьому Степан вирішив зекономити і не придбав програмне забезпечення для розподільника, тому він працює не оптимально. Степан просить вас написати програму для цього розподільника, яка максимізує доходи Степана.
Формат вхідних даних: у першому рядку записані два цілих числа N (2 ≤ N ≤ 1000) і M (1 ≤ M < N) – загальна кількість місць на стоянці і кількість місць із лівого боку відповідно. У кожному із наступних N рядків записано по N цілих додатних чисел. j-е число i-го рядка означає, скільки буде платити i-ий житель за місце з номером j на цій стоянці. Кожне з цих чисел не перевищує 106.
Формат вихідних даних: єдиний рядок має містити одне число – максимальний прибуток стоянки.
Зауваження: Не менш чим у 50% тестів N ≤ 30.
Приклади
Вхідні дані
розміщені у файлі legacy.in
Результат роботи знаходиться у файлі legacy.out
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




Ідея розв’язку задачі
D – Масив вартості стоянки для і-го жителя. Усього 10 стоянок, із них 2 ліві.





Розв’язок


E – Конфетна проблема Степана
Ім'я файлу, який містить вхідні дані:problem.in
Ім'я вихідного файлу:problem.out
Обмеження часу:500 mс
Обмеження пам'яті:128 M

Степан закохався і вирішив привернути увагу дівчини великою коробкою цукерок. За порадою друзів він поїхав унайвідомішу кондитерську фабрику ShenRo і дізнався, що великі коробки цукерок мають трикутну форму. Цукерки в цих коробках розташовуються в кілька рядів. У першому ряду знаходиться одна цукерка, у другому – дві, у третьому – три цукерки і так далі. На фабриці випускаються коробки цукерок із будь-яким числом рядів у межах від 1 до N. Степан хоче купити одну із таких коробок. Але є одна проблема: його дівчина засмутиться, якщо кількість цукерок у коробці не буде ділитись націло на M, тому що в цьому випадку комусь із друзів дівчини дістанеться більше цукерок, чим іншим, або ж якісь цукерки залишаться зайвими. Тому Степан вирішив, що число цукерок у коробці має обов’язково ділитись націло на M.
При виборі подарунка Степан зіткнувся з проблемою придбання відповідної коробки цукерок, оскільки можливих варіантів вибору коробки цукерок виявилося надто багато. Не довго думаючи, Степан вирішив звернутись за допомогою до учасників олімпіади.
Вам необхідно по заданих числах N і M знайти число способів вибору коробки цукерок із множини коробок з кількістю рядів від 1 до N. Способи вважаються різними, якщо їм відповідають коробки з різною кількістю рядів цукерок.
Формат вхідних даних: перший рядок вхідного файлу містить два цілих числа N – максимальна кількість рядів цукерок у коробці і M – кількість друзів дівчини Степана (1 ≤ N, M ≤ 2*109) відповідно.
Формат вихідних даних: вихідний файл має містити одне ціле число – кількість різних способів вибору коробки цукерок.
Оцінювання: N, M ≤ 1000 – не менше 35 балів, N, M ≤ 105 – не менше 55 балів.
Приклади
Вхідні дані
розміщені у файлі problem.in
Результат роботи знаходиться у файлі problem.out
20 104
53 1990
5705 145157
Розв’язок

Наверх