|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
09.01.2013, 21:31 | #1 |
Новичок
Джуниор
Регистрация: 09.01.2013
Сообщений: 1
|
задача паскаль покупка билетов
3. Покупка билетов
Имя входного файла: Input.txt. Имя выходного файла: Output.txt. Максимальное время работы на одном тесте: 5 секунд. Максимальный объем использованной памяти: 4 Мбайты. За билетами на премьеру нового мюзикла собралась очередь из N лиц, каждое из которых хочет купить 1 билет. На всю очередь работала только одна касса, потому продажа билетов продвигалась очень медленно, от чего «клиенты» очереди впадали в отчаяние. Самые сообразительные быстро приметили, что, как правило, несколько билетов в одни руки кассир продает быстрее, чем когда эти же билеты продаются по одному. Поэтому они предложили нескольким людям, которые стоят рядом, отдавать деньги первому из них, чтобы он купил билеты на всех. Но для борьбы со спекулянтами кассир продавала не больше 3-х билетов в одни руки, потому договориться таким образом между собой могли лишь 2 или 3 лица, которые стоят рядом. Известно, что на продажу і лицу из очереди одного билета кассир тратит Аі секунд, на продажу двух билетов – Ві секунд, трёх билетов – Сi секунд. Задание. Напишите программу, которая определит минимальное время, за которое можно было бы обслужить всех покупателей. Обратите внимание, что билеты на группу людей, которые объединились, всегда покупает первый из них. Также никто с целью ускорения не покупает лишние билеты (то есть билеты, которые никому не нужные). Входные данные. Первая строка входного файла содержит единственное число N – количество покупателей в очереди (1N5000). В каждой из следующих N строк записана тройка натуральных чисел Аі, Bi, Сi. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются, начиная от кассы Выходные данные. Исходный файл содержит одно число – минимальное время в секундах, за которое можно было бы обслужить всех покупателей. Пример входных и выходных данных Input.txt Output.txt 5 12 5 10 15 2 10 15 5 5 5 20 20 1 20 1 1 2 4 3 4 5 1 1 1 |
09.01.2013, 23:50 | #2 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Покупка приложения | kettanaito | Общие вопросы Delphi | 1 | 19.10.2011 23:32 |
рассчитать количество "счастливых" билетов с указанной сумой цифр (паскаль) | gylayko | Помощь студентам | 2 | 22.09.2011 19:48 |
Покупка нетбука | dodomenos | Свободное общение | 1 | 31.03.2011 15:57 |
Задача: Найти количество всех 2K-значных счастливых билетов с суммой цифр, равной N. | Lodyr | Помощь студентам | 7 | 04.01.2010 16:19 |