Лучшие помощники
- Megamozg 2205 б
- Matalya1 1800 б
- DevAdmin 1720 б
- arkasha_bortnikov 895 б
- Dwayne_Johnson 865 б
15 декабря 2022 23:34
989
Лягушка и кузнечикОграничение по времени: 0.5 секунды
В крайних клетках полоски шириной в одну клетку и длиной в N клеток сидят лягушка и кузнечик: лягушка в клетке под номером 1, кузнечик в клетке под номером N. Каждую секунду лягушка прыгает в сторону кузнечика, и одновременно кузнечик прыгает в сторону лягушки. Лягушка может прыгать только на две или на три клетки, кузнечик — только на одну или на две клетки. За какое наименьшее время они смогут оказаться в одной клетке?
Формат входных данных
Единственная строка входных данных содержит целое число N — длину клетчатой полосы (2≤N≤2⋅109).
Формат выходных данных
Если лягушка и кузнечик могут оказаться в одной клетке, требуется вывести одно целое число — минимальное количество секунд, через которое они могут встретиться. Если они не смогут оказаться в одной клетке, требуется вывести число «−1» (без кавычек).
Система оценки
Решения, правильно работающие при N≤30, будут оцениваться в 30 баллов.
Решения, правильно работающие при N≤105, будут оцениваться в 50 баллов.
Пояснение
В первом примере лягушка может прыгнуть из клетки 1 в клетки 3 и 4, а кузнечик может прыгнуть из клетки 5 в клетки 3 и 4. Поэтому через 1 секунду они могут оказаться в одной клетке.
Во втором примере лягушка и кузнечик могут встретиться через 2 секунды. Например, лягушка прыгает в клетку 3, затем в клетку 6, а кузнечик прыгает в клетку 8, затем в клетку 6.
1
ответ
Ответ:
N = int(input())
M = 1537
n = N - 1
l = -1
r = n
while l < r - 1:
m = (l + r) // 2
if n - 5 * m < M:
r = m
else:
l = m
s = r
n -= 5 * s
dist = [0] + [-1] * M
jumps = [3,4,5]
q = [0]
while q:
d = q.pop()
for i in range(3):
if d + jumps[i] < M and dist[d + jumps[i]] == -1:
dist[d + jumps[i]] = dist[d] + 1
q.append(d + jumps[i])
print(-1 if dist[n] == -1 else s + dist[n])
Объяснение:
N = int(input())
M = 1537
n = N - 1
l = -1
r = n
while l < r - 1:
m = (l + r) // 2
if n - 5 * m < M:
r = m
else:
l = m
s = r
n -= 5 * s
dist = [0] + [-1] * M
jumps = [3,4,5]
q = [0]
while q:
d = q.pop()
for i in range(3):
if d + jumps[i] < M and dist[d + jumps[i]] == -1:
dist[d + jumps[i]] = dist[d] + 1
q.append(d + jumps[i])
print(-1 if dist[n] == -1 else s + dist[n])
Объяснение:
0
·
Хороший ответ
17 декабря 2022 23:34
Остались вопросы?
Еще вопросы по категории Информатика
1. Как называется свойство алгоритма,1. Как называется свойство алгоритма, означающее, что данный алгоритм применим к решению целого класса задач? а)...
Сделать программу на c++ :Даны строки: имя фамилия отчество , Нужно чтобы программа выдавал отчества в алфавитном порядке, как это можно сделать?...
fоr i in rаngе( d, 63, c): рrint ( i, end=" " ) В результате работы этого фрагмента программы на эк...
Даю 22 балла Какое МАКСИМАЛЬНОЕ количество вопросов достаточно задать вашему собеседнику, чтобы точно определить день и месяц его рождения? Сделать по...
Считая, что каждый символ кодируется одним байтом, оцените информационный объем следующего предложения: В человеке должно быть все прекрасно: и лицо,...
Все предметы 
