Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "Пятая личная олимпиада"

Задача A. Число сочетаний

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Факториал числа n – произведение всех натуральных чисел от 1 до n:

Сочетанием из n по k называют набор из k элементов, выбранных из данного множества, содержащего n различных элементов. При этом наборы, отличающиеся только порядком следования элементов, считаются одинаковыми.

Число возможных сочетаний из n по k вычисляется по следующей формуле:

По заданным целым числам n и k требуется вычислить число сочетаний.

При решении данной задачи необходимо реализовать функцию F(n), вычисляющую факториал числа.

Входные данные

Входной файл INPUT.TXT содержит целые числа n и k (0 ≤ kn ≤ 20).

Выходные данные

В выходной файл OUTPUT.TXT выведите число сочетаний из n по k.

Примеры

INPUT.TXTOUTPUT.TXT
13 23
27 335

Задача B. Незнайка

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Незнайка и его друзья собрались в космическое путешествие. Они уже и новый звездолет построили. Хоть он и построен был с учетом новых технологий, был у него один большой недостаток. После T1 часов полета, аккумуляторы требовали обязательной подзарядки от солнечной батареи в течении T2 часов, а конструкция звездолета такова, что его двигатель на время подзарядки останавливается и звездолет начинает двигаться в обратную сторону. Известно, что за T1 часов полета звездолет улетает на S1 км, а за T2 часов разрядки возвращается на S2 км.

Требуется определить: сколько потребуется времени для полета Незнайки и его друзей на различные планеты, если известно расстояние S до планет.

Входные данные

Входной файл INPUT.TXT содержит пять натуральных чисел, разделенных пробелами: T1, T2, S1, S2, S. Все числа не превышают 107.

Выходные данные

В выходной файл OUTPUT.TXT выведите время в часах (с точностью до двух знаков после запятой), за которое звездолет долетит до планеты. Если добраться до планеты не получится, то следует вывести «NO».

Примеры

INPUT.TXTOUTPUT.TXT
15 3 5 3 44.00
25 3 5 3 612.00
35 1 3 3 6NO
410 1 100 20 50065.00

Задача C. Забег

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Однажды заяц и черепаха решили устроить благотворительный забег. Они выбрали дистанцию длиной L км и позвали много-много зрителей.

Черепаха и заяц бегут с постоянной скоростью. Скорость черепахи всего V км/ч, а скорость зайца на D км/ч выше. Поэтому сразу после старта заяц обогнал черепаху и убежал далеко вперед. Но просто так выиграть гонку зайцу не интересно. Поэтому добежав до финиша, он мгновенно развернулся и побежал назад с той же скоростью, чтобы узнать положение черепахи. Добежав до черепахи, которая совсем недалеко успела убежать от старта, он снова мгновенно развернулся и побежал в сторону финиша. Так от черепахи до финиша и обратно до нового положения черепахи и бегал заяц, пока черепаха не добежала до финиша. Что самое интересное – финишную черту она пересекла одновременно с зайцем!

Если черепаха пробежала L км, то какой путь пробежал заяц?

Входные данные

Входной файл INPUT.TXT содержит четыре целых числа, разделенных пробелами: L – длина дистанции (1 ≤ L ≤ 109), V – скорость черепахи (1 ≤ V ≤ 109), D – разница в скорости зайца и черепахи (0 ≤ D ≤ 109), P – точность (0 ≤ P ≤ 6).

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число – пройденный зайцем путь с P знаками после запятой и с точностью 10-P .

Примеры

INPUT.TXTOUTPUT.TXT
130 4 2 345.000
220 5 0 020
333 80 28 144.6

Задача D. Zuma

(Время: 2 сек. Память: 16 Мб Баллы: 100)

Возможно, некоторым из вас знакома игра Zuma о приключениях лягушки. В данной задаче правила похожи и довольно просты: в каменном жёлобе находится ряд разноцветных шаров; пушка, расположившаяся рядом с жёлобом, имеет некоторый запас разноцветных шаров и периодически закидывает их в желоб. Заброшенные шары встраиваются в ряд. Если после выстрела в желобе образуется непрерывная последовательность из трех или более шаров одного цвета, включающая заброшенный шар, то они исчезают, а соседние шары сдвигаются, смыкая ряд. Если после исчезновения шаров в месте стыка соседние шары образуют непрерывную последовательность из трех или более шаров одного цвета, то они также исчезают, и так далее. Цель игры – уничтожить все шары.

ЭтапРисунокПояснение
1Выстреливается новый шар «B», в позицию после шара №1
2После выстрела новый шар образует с соседними последовательность цвета «B», в позициях 2-5. Длина последовательности ≥3, поэтому шары 2-5 исчезнут
3Оставшиеся шары займут позиции 1-3, и поскольку новая последовательность цвета «А» длины ≥3, она тоже исчезнет

Пронумеруем шары слева направо, начиная с единицы. Выстрел шара в позицию n означает, что он появится правее шара с номером n и окажется в позиции n+1. Номера шаров, расположенных правее прилетевшего шара, увеличиваются на единицу. Приземление шара левее всего ряда обозначается позицией с номером 0. После исчезновения некоторых шаров, шары в желобе нумеруются заново слева направо, начиная с единицы.

Требуется написать программу, определяющую оптимальную стратегию стрельбы. Оптимальной стратегией называется та, при которой наименьшее количество выстрелов приводит к исчезновению всех шаров, а если таких стратегий несколько, то выбирается та, при которой первый выстрел производится как можно левее, а если несколько и таких, то сравнение идёт по второму выстрелу и т.д.

Входные данные

Входной файл INPUT.TXT содержит описание ряда шаров, цвет каждого шара описывается заглавной буквой английского алфавита (A..Z). Известно, что длина ряда не превышает 14 шаров, а для уничтожения ряда требуется не более 10 выстрелов, если следовать оптимальной стратегии.

Выходные данные

В выходной файл OUTPUT.TXT выведите строку: сначала минимальное количество выстрелов, затем через пробел пары буква-число: цвет шара и позицию выстрела. Выстрелы в ответе должны быть перечислены в порядке их следования в игре.

Примеры

INPUT.TXTOUTPUT.TXT
1ABBBAA1 B1
2ACMNEERC10 A0 A0 C0 M2 M2 N2 N2 E2 R2 R2


Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483