Задача 5. Календарь на Альфе Центавра

Автор:Андрей Станкевич   Ограничение времени: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

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
116d = 1, m = 1первая ошибка
216m = 1, k ≤ 107 1первая ошибка
317i = 1, j = 1первая ошибка
417k = 1первая ошибка
517k ≤ 1004первая ошибка
617нет1 — 5первая ошибка

Замечание

Обратите внимание, при решении этой задачи рекомендуется использовать 64-битные типы данных, например long long в C++, int64 в Паскале.

Примеры тестов

Стандартный вход Стандартный выход
1
30 12 7
18 1 2021
b

Разбор

Заметим ключевую идею. Пусть мы нашли x — номер дня от начала летосчисления до заданного во вводе дня. С первого дня первого месяца первого года (который, как мы знаем, имел обозначение "a"), прошло x − 1 дней. Каждые w дней повторялся день с обозначением "a", поэтому на самом деле нас интересует величина y = (x − 1mod w.

Заметим, что если y = 0, то день имеет обозначение "a", если y = 1, то "b", и так далее. Чтобы получить по сдвигу относительно "a" букву в английском алфавите, можно воспользоваться возможностями языка программирования. В С++ это сделать проще всего:


    cout << 'a' + y << endl;

В других языках могут потребоваться функции приведения типа. Например, в Паскале:


    writeln(chr(ord('a') + y));

В языке Python:


    print(chr(ord('a') + y))

Осталось разобраться, как найти x.

Подзадача 1

В первой подзадаче год состоит из одного дня. Поэтому i = 1 и j = 1, а значит x = k.

Подзадача 2

Во второй подзадаче m = 1, то есть месяц всего один. x = (k − 1) ⋅ d + i. Заметим, что в этой подзадаче благодаря тому, что k небольшое, достаточно 32-битного типа данных.

Подзадача 3

В третьей подзадаче речь все время идет о первом дне первого месяца. x = (k − 1) ⋅ d ⋅ m + 1.

Подзадача 4

В четвертой подзадаче k = 1. Год учитывать не надо, надо учесть только день и месяц. x = (j − 1) ⋅ d + i.

Подзадачи 5 и 6

Наконец получим общую формулу: x = (k − 1) ⋅ m ⋅ d + (j − 1) ⋅ d + i. Отличие пятой подзадачи в том, что в ней k невелико и поэтому можно использовать 32-битный тип данных.

В заключение отметим, что различные способы итерациями перебирать дни могли проходить некоторые подзадачи, например подзадачи 1, 2, 3, 5.


0.101s 0.019s 13