Задача G. Эффективное летнее чтение ≡
| Автор: | Kofanova A.А. | Ограничение времени: | 1 сек | |
| Входной файл: | test.sql | Ограничение памяти: | 256 Мб | |
| Выходной файл: | test.log |
Условие
Школьнику Стёпе на лето задали большой список литературы. Первые два месяца каникул он полностью посвятил отдыху, и теперь у него остался только один месяц (30 дней), чтобы успеть прочитать как можно больше произведений из списка. При этом ученик готов тратить на чтение не более 5 часов в день.
Так как главная цель — максимизировать количество прочитанных книг, Стёпа решает использовать жадную стратегию: он всегда выбирает следующей ту книгу, в которой меньше всего страниц. Если количество страниц совпадает, книги читаются в порядке возрастания их идентификатора.
Изначально школьник читает со скоростью 30 страниц в час. Однако, как только суммарное количество прочитанных за этот месяц страниц достигает отметки в 1000 страниц, его навык скорочтения улучшается, и скорость увеличивается до 40 страниц в час.
Примечание: Если переключение скорости происходит прямо в процессе чтения какой-то книги, время на ее чтение рассчитывается пропорционально.
Пример: Допустим, Стёпа уже прочитал суммарно 650 страниц. Следующая по списку книга содержит 400 страниц. В этом случае первые 350 страниц этой книги (до достижения порога в 1000) он будет читать со старой скоростью (30 страниц/час), а оставшиеся 50 страниц — с новой скоростью (40 страниц/час).
Чтение списка литературы должно автоматически прекратиться, если добавление следующей по порядку книги приведет к превышению общего лимита времени. Книги, прочитанные лишь частично (на которые не хватило времени до конца), в итоговый список не попадают.
Структура БД:
CREATE TABLE books (
id INTEGER PRIMARY KEY AUTOINCREMENT,
title TEXT NOT NULL,
pages INTEGER NOT NULL CHECK (pages > 0)
);
Схема БД в UML-нотации:
Напишите SQL-запрос, который смоделирует процесс чтения и выведет список книг в том порядке, в котором их прочитает школьник.
Формат входного файла
Формат выходного файла
Результирующая таблица должна содержать следующие столбцы:
- Порядок — порядковый номер прочитанной книги (начиная с 1).
- Название книги — столбец title.
- Количество страниц — столбец pages.
- Всего страниц — накопительная сумма прочитанных страниц на момент окончания чтения текущей книги.
- Затрачено часов (всего) — суммарное затраченное время в часах на момент окончания чтения текущей книги. Значение необходимо округлить до двух знаков после запятой с помощью функции ROUND().
Ограничения
Полагается, что для работы с базой данных используется SQLite3.