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

Задача 1. «Одиниці»

Умова. Дано ціле число I записане в десятковій системі числення.

Завдання. Написати програму ONE.*, яка порахує кількість одиниць в його двійковому записі.

Вхідні дані. Вхідний текстовий файл ONE.DAT містить в єдиному число I.

Вихідні дані. Вихідний текстовий файл ONE.SOL містить єдине ціле число - кількість одиниць.

Приклади файлів

Задача 2. «Нафтові плями»

Умова. Після аварії на морській нафтовій свердловині в океан вилилося багато нафти. Вона розтеклася по воді, після чого утворилася певна кількість нафтових плям. Для ліквідації наслідків аварії було створено штаб з координації дій. Співробітники штабу зберігають інформацію про плями в комп'ютері у вигляді матриці розмірністю M x N. Комірка матриці містить 0, якщо нафтова пляма в цих координатах відсутня та 1, якщо наявна (2 ≤ M, N ≤ 100). У матриці комірки плям не можуть дотикатися одна до одної ні сторонами, ні кутами.

Приклади файлів

Завдання. Для полегшення ліквідації наслідків аварії потрібно написати програму OIL.*, яка знаходитиме загальну кількість плям та кількість плям з однаковою площею.

Вхідні дані. Вхідний текстовий файл OIL.DAT містить в першому рядку два числа M та N, далі слідують M рядків, у кожному по N цілих чисел розділених пропусками - елементи матриці.

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

Завдання 3. «Ламана»

Ім'я файлу програми: LAMAN.*

Ім'я вхідного файлу: LAMAN.DAT

Ім'я вихідного файлу: LAMAN.SOL

Максимальний час роботи на одному тесті: 5с

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

-          починати з лівого нижнього кута, який знаходиться в початку координат;

-           можна пересуватися вздовж цих прямих;

-           при проходженні через точку  завжди змінювати напрям швидкості на перпендикулярний.

Знайти мінімальну довжину шляху  до верхньої правої точки.

Технічні умови. Програма Laman читає з файлу розміри шоколадної плитки (цілі числа, не більші 10^100000). Числа розділено пропуском. Програма виводить на екран  єдине число - шукану величину.

Приклади файлів

Задача 4. Сума дільників

Ім'я вхідного файлу:   sum.in

Ім'я вихідного файлу:   sum.out

Нехай х - натуральне число. Назвемо число y його дільником, якщо 1 ≤ у ≤ х і залишок від ділення x на y дорівнює нулю.

Задано число х. Знайдіть суму його дільників.

Формат вхідних даних: перший рядок вхідного файлу містить одне ціле число х (1 ≤ х ≤ 10¹⁸). Усі прості дільники числа х не перевищують 1000.

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

Приклад вхідних і вихідних даних:

Задача 5. Куфічний дирхем

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

Дізнавшись, що Шаміль Ігорович вже багато років захоплюється колекціонуванням старовинних монет і полює за середньовічною срібною монетою з назвою «Куфічний дирхем», Віталій Вікторович вирішив неодмінно подарувати йому цю монету.

Скориставшись Інтернетом, Віталій Вікторович визначив всі K міст, де можна придбати дану монету, а також її вартість у кожному із цих міст. Країна, у якій живуть Віталій Вікторович і Шаміль Ігорович, налічує N міст і M двосторонніх автомобільних доріг, кожна з яких з'єднує два різних міста держави. Відомо, що Віталій Вікторович живе в місті A, а Шаміль Ігорович - в місті B. Для кожної дороги Віталій Вікторович обчислив вартість проїзду з урахуванням технічних характеристик свого автомобіля. З метою економії Віталій Вікторович вирішив придбати монету по дорозі із міста A у місто B. Іншими словами, маршрут руху Віталія Вікторовича повинен проходити через місто, у якому він вирішить придбати монету. Однак виявилось, що їхати через місто, у якому монета коштує менш за все, не завжди вигідно, тому що вигравши у вартості монети, можна втратити набагато більше у вартості дороги і навпаки...

Ваше завдання - допомогти Віталію Вікторовичу вибрати оптимальний маршрут і місто Z, де слід придбати монету. Маршрут повинен починатися в місті A, закінчуватися в місті B і проходити через місто Z. Вартість даного маршруту повинна бути мінімальною. Під вартістю маршруту будемо розуміти суму кількості грошей, витрачених на дорогу і вартість монети в місті Z. Нижче наведено приклад для N = 5, M = 7, A = 1, B = 4.

Рисунок 1.Візуалізація другого прикладу.

Для даного приклада K = 4, вартість монети позначено зверху над кругом, що позначає місто.

Оптимальний маршрут виділено червоним кольором. Для даного прикладу Z = 3.

Вхідні дані:

Перший рядок вхідного файлу містить три цілих числа N, M і K (2 ≤ N ≤ 5000; 1 ≤ M ≤ 100000; 1 ≤ K ≤ N), де N - кількість міст в країні, M - кількість доріг, а K - кількість міст, у яких продається шукана монета. Будемо вважати, що всі міста пронумеровані цілими числами від 1 до N.

Другий рядок вхідного файлу містить два цілих числа A і B (1 ≤ A, B ≤ N; A ≠ B), де A - номер міста, в якому живе Віталій Вікторович, а B - номер міста, в якому живе Шаміль Ігорович.

Третій рядок містить K пар цілих чисел V_i і С_i( 1 ≤ V_i ≤ N; 1 ≤ С_i ≤ 10⁹), де V_i - це номер міста, у якому можна придбати потрібну монету, а С_i - вартість монети у відповідному місті. Відомо, що V_i ≠ V_j, якщо i ≠ j. Всі числа у рядку розділені одиночними пробілами.

Кожен наступний із M рядків містить три числа X_i, Y_i, S_i (1 ≤ X_i, Y_i ≤ N; X_i ≠ Y_i; 1 ≤ S_i ≤ 10⁵), де X_i і Y_i - номери міст, з'єднаних двосторонньою дорогою, а S_i - вартість проїзду по даній дорозі. Не існує двох різних доріг, що з'єднують одні і ті ж міста.

Вихідні дані

Єдиний рядок вихідного файлу має містити одне ціле число - мінімальну вартість маршруту. Гарантується, що рішення існує.

Приклад вхідних та вихідних даних: