Задача оценивается в 00 баллов. Ограничение по времени работы в каждой задаче секунда
жүктеу/скачать 168,22 Kb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Пример входных и выходных данных Ввод Вывод Примечание
- Система оценивания
| Задача 3. Пятница, 13-е
Календарь жителей планеты Плюк состоит из N месяцев, каждый месяц состоит ровно из 30 дней, неделя состоит из 7 дней. Особо несчастливыми на планете Плюк считается 13-е число месяца, если оно выпадает на пятницу. Известно, что Новый год на планете Плюк начался в k-й по счету день недели (1-й день недели — понедельник, 2-й — вторник, 3-й — среда, … , 7-й — воскресенье). Определите, сколько в этом году на планете Плюк будет особо несчастливых пятниц, 13-е. Программа получает на вход два натуральных числа, записанных в отдельных строках. Первое число — количество месяцев в календаре планеты Плюк N, не превосходящее 10 9 . Второе число — номер дня недели, на который приходится первое число первого месяца нового года, может принимать значения от 1 до 7. Программа должна вывести единственное целое число — количество несчастливых дней в этом году. Пример входных и выходных данных Ввод Вывод Примечание 12 1 2 На 13-е число будут приходиться пятницы четверого и одиннадцатого месяцев. Система оценивания Решение, правильно работающее только для случаев, когда N не превосходит 100, будет оцениваться в 60 баллов. Страница 3 из 8 Решение Решение на 60 баллов использует простое моделирование. Сначала посчитаем, на какой день недели приходится 13-е число первого месяца, затем будем считать, на какой день недели приходится 13-е число каждого следующего месяца. Если пронумеровать дни недели от 1 до 6, а воскресенье считать днём недели номер 0, то для получения дня недели 13-го числа следующего месяца нужно к текущему номеру дня недели прибавить 30 и взять остаток от деления на 7. Повторяем это в цикле N раз и при получении числа 5 увеличиваем ответ на 1. Пример решения на языке Python: N = int(input()) k = int(input()) ans = 0 k = (k + 12) % 7 for i in range(N): if k == 5: ans += 1 k = (k + 30) % 7 print(ans) Такое решение будет получать результат «превышено максимальное время работы» при больших значениях N, так как за 1 секунду невозможно выполнить цикл в 10 9 шагов. Для решения задачи на полный балл заметим, что поскольку числа 7 и 30 — взаимно простые, то в последовательности дней недели, на которые выпадают 13-е числа месяца будет цикл длины 7: пятница, воскресенье, вторник, четверг, суббота, понедельник, среда. Поэтому для нахождения ответа достаточно найти первый месяц года, в котором будет пятница 13-е, и к ответу добавить количество оставшихся месяцев в году, деленное на 7 нацело. Пример решения, набирающего полный балл: N = int(input()) k = int(input()) k = (k + 12) % 7 i = 1 ans = 0 while i <= N and k != 5: i += 1 k = (k + 30) % 7 if i > N: print(0) else: print(1 + (N - i) // 7) Страница 4 из 8 |