Автор: | Андрей Станкевич | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
На планете в системе Альфы Центавра год состоит из m месяцев,
пронумерованных от 1 до m, а каждый месяц из d дней, пронумерованных от 1 до d.
В свою очередь, неделя у поселенцев на этой планете состоит из w дней,
проиндексированных строчными английскими буквами,
от "a
" до w-й буквы английского алфавита.
Первый день первого месяца первого года соответствует букве "a
".
Требуется определить, какой букве будет соответствовать i-й день j-го месяца k-го года.
Первая строка ввода содержит три целых числа d, m и w.
Вторая строка ввода содержит три целых числа i, j и k.
Выведите одну строчную букву английского алфавита — какой букве соответствует i-й день j-го месяца k-го года.
1 ≤ d, m ≤ 100, 1 ≤ w ≤ 26
1 ≤ i ≤ d, 1 ≤ j ≤ m, 1 ≤ k ≤ 109
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Доп. ограничения | Необходимые подзадачи | Информация о проверке |
---|---|---|---|---|
1 | 16 | d = 1, m = 1 | первая ошибка | |
2 | 16 | m = 1, k ≤ 107 | 1 | первая ошибка |
3 | 17 | i = 1, j = 1 | первая ошибка | |
4 | 17 | k = 1 | первая ошибка | |
5 | 17 | k ≤ 100 | 4 | первая ошибка |
6 | 17 | нет | 1 — 5 | первая ошибка |
Обратите внимание, при решении этой задачи рекомендуется использовать 64-битные типы данных,
например long long
в C++, int64
в Паскале.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
Заметим ключевую идею. Пусть мы нашли x — номер дня от начала летосчисления
до заданного во вводе дня.
С первого дня первого месяца первого года
(который, как мы знаем, имел обозначение "a
"), прошло x − 1 дней.
Каждые w дней повторялся день с обозначением "a
",
поэтому на самом деле нас интересует величина y = (x − 1) mod w.
Заметим, что если y = 0, то день имеет обозначение "a
", если y = 1, то "b
", и так далее. Чтобы получить по сдвигу относительно "a
" букву в английском алфавите, можно воспользоваться возможностями языка программирования. В С++ это сделать проще всего:
cout << 'a' + y << endl;
В других языках могут потребоваться функции приведения типа. Например, в Паскале:
writeln(chr(ord('a') + y));
В языке Python:
print(chr(ord('a') + y))
Осталось разобраться, как найти x.
В первой подзадаче год состоит из одного дня. Поэтому i = 1 и j = 1, а значит x = k.
Во второй подзадаче m = 1, то есть месяц всего один. x = (k − 1) ⋅ d + i. Заметим, что в этой подзадаче благодаря тому, что k небольшое, достаточно 32-битного типа данных.
В третьей подзадаче речь все время идет о первом дне первого месяца. x = (k − 1) ⋅ d ⋅ m + 1.
В четвертой подзадаче k = 1. Год учитывать не надо, надо учесть только день и месяц. x = (j − 1) ⋅ d + i.
Наконец получим общую формулу: x = (k − 1) ⋅ m ⋅ d + (j − 1) ⋅ d + i. Отличие пятой подзадачи в том, что в ней k невелико и поэтому можно использовать 32-битный тип данных.
В заключение отметим, что различные способы итерациями перебирать дни могли проходить некоторые подзадачи, например подзадачи 1, 2, 3, 5.