На днях прошел второй тур алгоритмического марафона, куда меня позвала Виктория Бородина
Результат: мы решили одну задачу из пяти. Кто-то скажет, что это провал, а я скажу, что для нас это настоящая победа! В прошлый раз мы тоже решили одну задачу и теперь можно сказать, что стабильность - признак мастерства, а не того, что в прошлый раз нам просто повезло
Но я знаю, что вам интересно, а что это была за задача? Вот вам условие:
Дмитрий имеет 𝑛 кубиков, пронумерованных слева направо от 1 до 𝑛. Кубик с индексом 𝑓 — его любимый.
Дмитрий бросил все кубики на стол, и 𝑖-й кубик показал значение 𝑎𝑖 (1≤𝑎𝑖≤100). После этого он расположил кубики в порядке невозрастания их значений, от большего к меньшему. Если два кубика показывают одинаковое значение, они могут быть расположены в любом порядке.
После сортировки Дмитрий убрал первые 𝑘 кубиков. Затем ему стало интересно, удалил ли он свой любимый кубик (учтите, что его позиция могла измениться после сортировки).
Например, если 𝑛=5, 𝑓=2, 𝑎=[4,3,3,2,3] (любимый кубик выделен зеленым цветом), и 𝑘=2, могло произойти следующее:
После сортировки 𝑎=[4,3,3,3,2], так как любимый кубик оказался на второй позиции, он будет удален.
После сортировки 𝑎=[4,3,3,3,2], так как любимый кубик оказался на третьей позиции, он не будет удален.
Мы решили эту задачу таким образом: мы знаем, что кубики будут отсортированы определенным образом, а значит нам просто нужно мониторить, попадут ли все кубики, которые имеют то же значение, что и любимый кубик “под нож” или нет. А сделать это уже не так сложно, если мониторить рядом стоящий кубик
Вот, что у нас получилось:
def check_favorite_cube(cubes, f, k):
fav = cubes[f - 1]
if len(cubes) == k:
return "YES"
cubes.sort(reverse=True)
if fav == cubes[k]:
if fav != cubes[k - 1]:
return "NO"
return "MAYBE"
elif fav < cubes[k]:
return "NO"
else:
return "YES"
А как решили бы вы?