Темы
    Информатика(2609 задач)
---> 8 задач <---
Страница: 1 2 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Из описания некоего растения: «… его время жизни составляет 20 лет. В первый год плод растения попадает в землю. Первые побеги растения появляются лишь на второй год. Плодоносить растение начинает с четвертого года и ежегодно дает по 1 плоду, которые сразу попадают в землю, и из них вырастают такие же растения. На двадцатый год своей жизни растение плодоносит в последний раз, а на двадцать первый год – погибает».

Напишите программу, которая определяет, сколько живых растений будет в N-м году, если в первый год мы посадим один плод этого растения. Только что посаженные плоды за растения не считаются. Также не считаются живыми растения, для которых данный год является 21-м (или больше) годом жизни.

Замечания

Из описания следует, что плод, который появился в 4-м году, сразу попадает в землю, и этот год считается 1-м годом жизни нового растения (при этом при подсчете числа живых растений в этом году данное растение еще не будет учтено). Это растение даст первые побеги в 5-м году, начнет плодоносить — в 7-м, а последний раз будет плодоносить в 23-м году и перестанет быть живым – в 24-м.

При подсчете числа живых растений в 20-м году исходное растение еще считается живым, а в 21-м — уже не считается.

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

Вводится единственное натуральное число N, не превышающее 100.

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

Выведите единственное число – сколько живых растений будет в Nм году. Только что посаженные плоды за растения не считаются.

Комментарий к примеру тестов

1. Первые три года растение не плодоносит, на четвертый год оно дало 1 плод, но он еще не считается полноценным живым растением.

2. Первые 3 года у нас есть 1 растение, на 4-й год оно дает 1 плод; на 5-й год этот плод прорастает, а исходное растение дает еще 1 плод; на 6-й год второй плод прорастает, исходное растение дает плод, который растением еще не считается.

3. Начиная с 4-го года, исходное растение начинает давать по одному плоду (и дает по плоду на 4-м, 5-м, 6-м, 7-м, 8-м,… годах). Растение, которое получилось из плода, который появился на 4-м году, начинает плодоносить с 7-го года (и дает плоды на 7-м, 8-м, … годах). Растение, которое получилось из плода, который появился на 5-м году, начинает плодоносить с 8-го года. При этом все плоды, появившиеся на 9-м году, растениями еще не считаются. Итого, учитывая исходное растение, у нас будет 9 растений.

Система оценивания

ПодзадачаБаллыОграниченияНеобходимые подзадачи
130$n \le 15$тесты
230$n \le 40$1
340Нет дополнительных ограничений2

Примеры
Входные данные
4
Выходные данные
1
Входные данные
6
Выходные данные
3
Входные данные
9
Выходные данные
9
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Рассмотрим расписание движения электричек на некоторой железнодорожной линии. Нас будут интересовать только электрички, идущие в одном направлении.

Каждая электричка отправляется с некоторой станции и следует до некоторой другой станции со всеми остановками. При этом средняя маршрутная скорость у каждой электрички своя (будем считать, что весь маршрут электричка проходит с этой скоростью, временем стоянки на станциях пренебрежем). Поскольку на участке только один путь в данном направлении — электрички в процессе следования друг друга не обгоняют.

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

Естественно, что в книжке-расписании нужно расположить электрички так, чтобы они были указаны в хронологическом порядке. А именно, если две электрички имеют хотя бы одну общую станцию (даже если она является начальной станцией для одной, и конечной — для другой электрички), электрички в расписании должны идти в том порядке, в каком они проходят через эту станцию (поскольку электрички не обгоняют друг друга, то это же будет справедливо для всех общих станций этих двух электричек). Если же электрички не имеют ни одной общей станции, то они могут быть указаны в любом порядке.

По данному расписанию движения электричек определите порядок, в котором электрички должны идти в книжке—расписании.

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

Сначала вводится целое число N (1 ≤ N ≤ 1000) — количество электричек. Далее идёт описание электричек: каждая электричка задается четырьмя числами Ai, Bi, Ci, Di (0 ≤ Ai < Bi ≤ 106, 1 ≤ Ci ≤ 100, 0 ≤ Di ≤ 10000), которые обозначают, что данная электричка отправляется со станции «Ai-й километр» и следует до станции «Bi-й километр». Электричка отправляется с начальной станции в момент Ci. Один километр электричка проезжает за Di секунд.

Гарантируется, что расписание можно составить корректно, в частности, никакая электричка не обгоняет другую.

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

Выведите последовательность из N номеров от 1 до N – номера электричек в том порядке, в котором они должны идти в книжке-расписании. Если возможных ответов несколько, выведите любой.

Комментарий к примеру тестов

Ответ 2 3 1 также будет верным.

Примеры
Входные данные
3
1 10 3 4
3 5 3 4
10 11 10 1

Выходные данные
3 2 1 
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Студенты пришли на занятия в большую аудиторию и все сели на какие-то места первого ряда аудитории. Пришедший преподаватель объявил, что сейчас состоится контрольная работа, и решил пересадить студентов так, чтобы никакие два студента не сидели на двух подряд идущих местах (чтобы между любыми двумя студентами всегда было как минимум одно свободное место).

Помогите преподавателю пересадить минимальное число студентов, чтобы достичь нужного результата.

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

Сначала вводится натуральное число N — количество мест в первом ряду аудитории, а затем число K — количество студентов. Далее в порядке возрастания перечислены номера мест, на которые студенты сели изначально (все места пронумерованы числами от 1 до N).

1 ≤ K ≤ 1000, 2K–1 ≤ N ≤ 109.

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

Выведите одно число — минимальное количество студентов, которых придется пересадить.

Решение для n <= 15 будет набирать 30 баллов, для n <= 1000 будет набирать 60 баллов.

Примеры
Входные данные
7 4
2 4 6 7
Выходные данные
3
Входные данные
8 4
2 4 6 7
Выходные данные
1
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В волшебном лесу растут N деревьев. На плане леса они изображены точками (диаметром деревьев можно пренебречь). Территорией леса считается наименьший по площади выпуклый многоугольник (возможно, вырожденный), содержащий в себе все деревья.

Отважный путешественник и писатель Ручкин однажды решился на отчаянный поступок — он совершил путешествие в этот лес. После этого он описал свое путешествие в книге. В частности, в книге описаны все деревья леса в том порядке, в каком они встречались Ручкину (каждое дерево описано ровно один раз).

Художник Кистин решил нарисовать иллюстрацию для этой книги. Для этого он приехал и остановился в деревне недалеко от волшебного леса. Теперь он хочет выбрать точку, с которой он будет рисовать иллюстрацию. Кистин очень боится заходить в волшебный лес, поэтому хочет найти точку для рисования обязательно за пределами леса (в том числе, она не может находиться на границе леса).

Он решил нарисовать весь лес: он хочет взять длинный-длинный холст, и зарисовать весь лес справа налево, от самой правой точки леса до самой левой. При этом деревья леса должны на картине идти справа налево ровно в том же порядке, в котором они описаны в книге. Естественно, никакое дерево не должно быть заслонено другим деревом (т.е. на отрезке между Кистиным и деревом не может быть других деревьев).

Помогите ему: напишите программу, которая по координатам деревьев волшебного леса в том порядке, в каком они описаны у Ручкина, поможет Кистину выбрать точку, из которой деревья видны в требуемом порядке.

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

Задано число N — количество деревьев в лесу (1 ≤ N ≤ 100000). Далее перечислено N пар чисел, задающих координаты деревьев в том порядке, в каком они описаны в книге Ручкина. Все координаты – целые числа, не превосходящие по абсолютной величине 105. Гарантируется, что никакие два дерева не растут в одной точке.

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

Если подобрать точку для Кистина возможно, выведите сообщение Possible, а в следующей строке — два вещественных числа: координаты точки. Координаты выведенной точки не должны превышать 1015 по абсолютной величине. Если подобрать точку с указанными ограничениями не удастся, выведите сообщение Impossible.

При проверке ответа для случая Possible он будет считаться верным, если на расстоянии менее 10–5 от выведенной точки будет существовать точка, удовлетворяющая условию.

Примеры

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

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

3

0 0

1 2

2 1

Possible

1 4

3

1 0

2 0

3 0

Possible

1 1

3

1 0

3 0

2 0

Impossible

4

0 0

2 3

4 2

3 1

Impossible

4

0 0

4 0

2 2

4 4

Possible

-2 2

ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В одной театральной кассе есть в продаже билеты любой стоимости, выражающейся натуральным числом. При покупке билетов по цене за билет от A до B рублей включительно нужно дополнительно оплатить сервисный сбор в размере C процентов от номинальной стоимости билетов (сервисный сбор не обязательно выражается целым числом рублей, но всегда выражается целым числом копеек). При покупке билетов стоимостью менее A рублей за билет, а также более B рублей за билет, сервисный сбор не берется.

У вас есть X рублей и вам нужно K билетов одинаковой цены (цена обязательно должна выражаться натуральным числом рублей, 0 не считается натуральным). Билеты какого самого дорогого номинала вы можете себе позволить?

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

Вводятся целые A, B, C, X, K (1 ≤ A B ≤ 109, 0 ≤ C ≤ 1000, 0 ≤ X ≤ 109, 1 ≤ K ≤ 100000).

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

Если на имеющиеся деньги невозможно приобрести ни одного билета, выведите 0. Иначе выведите натуральное число – номинальную стоимость приобретённых билетов.

Система оценивания

Подзадача 1. Все числа $\le100$ - 50 баллов.

Подзадача 2. Без дополнительных ограничений - 50 баллов.

Примеры
Входные данные
1 10 0 5 5
Выходные данные
1
Входные данные
10 100 50 50 5
Выходные данные
9
Входные данные
10 100 50 100 5
Выходные данные
13

Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест