Завдання ІІ етапу Всеукраїнської олімпіади з інформатики /2010 - 2011 н.р./

Матеріал з ТерноВікі

Завдання II етапу Всеукраїнської учнівської олімпіади з інформатики 26 грудня 2010 р.

Задачі 1. «Симпатичні числа» (20 балів)

Кажуть, що десяткові числа «симпатичні», якщо вони містять у своєму записі тільки цифри 0 та 7. Побудуємо послідовність невід’ємних цілих «симпатичних» чисел в порядку зростання: 0, 7, 70, 77, 700, 707 і так далі. Скласти програму, яка знаходить m-те по порядку в цій послідовності «симпатичне» число.

Формат вхідних даних На вході задається одне натуральне число N (N<10000) – номер «симпатичного» числа в порядку зростання. Формат вихідних даних На виході програма повинна видати «симпатичне» число за вказаним номером.

Вхідні дані Вихідні дані 2 1 6 101

Задача 2. Номер Будинку (50 балів) Задано N – кількість будинків, які пронумеровані від 1 до N і К – кількість доріг. Кожна із доріг задається трійкою чисел – двома номерами будинків – кінці дороги і довжиною дороги. В кожному будинку живе одна людина. Знайти точку – місце зустрічі всіх людей від якого сумарна відстань до всіх будинків була б мінімальною. Шукана точка співпадає з одним із будинків. Скласти програму, яка знаходить номер цього будинку.

Вхідний файл Input.txt: В першому рядку задано числа N і К, а в кожному із наступних К рядків задано трійку чисел, яка характеризує дорогу (два номери будинків і відстань). Вихідний файл Output.txt: Містить число, яке задає номер будинку.

Задача 3. Фішка (30 балів) Фішка може рухатися по полю довжини N, тільки вперед. Довжина ходу фішки не більше ніж К. Знайти число різних маршрутів, по яких фішка може пройти поле від початку до кінця. Формат вхідних даних На вході задаються два натуральних числа N I K. Формат вихідних даних На виході програма повинна вивести кількість маршрутів. Наприклад. N=3, K=2 Відповідь: 3 Оскільки все можливих маршрутів є три: 1, 1, 1; 1.2; 2, 1.