| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Object Pascal: кроссплатформенные технологии > Задачка «Запись кассеты» |
| Автор: 000denmoroz000 28.12.2006, 11:23 |
| Свалилась тут на меня одна задачка, думаю-думаю,а как решить не знаю. Текст задачи Входной файл: input.txt Выходной файл: output.txt Ограничение по времени: 2 секунды Ограничение по памяти: 64 Mb Ограничение на размер исходного кода: 50Kb Коля решил записать с компьютера N песен на двустороннюю аудиокассету с одинаковыми параметрами сторон. Ему известна общая длительность кассеты в минутах. Когда он отобрал N песен с общим временем звучания не больше, чем время звучания кассеты, записать их у него не получилось. Проблема заключалась в том, что одна из песен не поместилась целиком на одну из сторон кассеты. Ваша задача написать программу, которая поможет Коле определить, какие из отобранных им песен нужно записать в полном объеме на одну сторону кассеты, а какие – на вторую. Если этого сделать невозможно, то нужно вывести ответ:-1. Следует учесть, что запись производится без пауз между песнями, а также каждая из песен имеет ненулевую длительность звучания. Ограничения: Все числа целые 0 < L =< 120 0 =< h =< 2, 0 =< m, s < 60 1 =< N =< 5000 Длина самой длинной песни не превышает L минут. Формат входных данных: В первой строке входного файла input.txt записано целое четное число L – общая длительность кассеты в минутах. Во второй строке файла содержится число отобранных песен N. Каждая из следующих N строк содержит длительность песни в одном из следующих форматов: h:m:s – длительность звучания песни h часов, m минут и s секунд; m:s – длительность звучания песни m минут и s секунд; s – длительность звучания песни s – секунд. Формат выходных данных: Выходной файл output.txt должен содержать одну либо N строк. Если песни нельзя записать на кассету, то файл должен содержать только одно число: -1. В противном случае файл должен состоять из N строк, в каждую из которых нужно вывести номер стороны кассеты (1 или 2) для записи i –ой песни. Номера песен соответствуют их порядковым номерам во входном файле. Если решений несколько, то достаточно выдать любое из них. Пример input.txt output.txt input.txt output.txt 80 1 4 -1 4 2 3 0:30:0 1 03:00 20:00 2 0:3:7 9:03 2:02 20:00 Жду ваших предложений по решению. Буду очень благодарен. |
| Автор: 000denmoroz000 28.12.2006, 11:43 |
| Мои мысли: - Хранить все длительности песен в массиве - Идти по массиву и смотреть: 1) Если время текущей записи i < L/2 то добавляем на первую сторону, иначе пропускаем. 2) Тоже самое с остальными записями. Правильно ли это решение - не знаю, т.к. ещё не закодил...  |