Loading [MathJax]/jax/output/SVG/jax.js

Международная олимпиада 2020, Санкт-Петербург, Россия, 2020 год


Дано целое число n>1. На горном склоне расположено n2 фуникулёрных станций на разных высотах. Каждая из двух фуникулёрных компаний A и B владеет k подъёмниками. Каждый подъёмник осуществляет регулярный беспересадочный трансфер с одной из станций на другую, более высоко расположенную станцию. k трансферов компании A начинаются на k различных станциях; также они заканчиваются на k различных станциях; при этом трансфер, который начинается выше, и заканчивается выше. Те же условия выполнены для компании B. Будем говорить, что две станции связаны фуникулёрной компанией, если можно добраться из нижней станции в верхнюю, используя один или несколько трансферов данной компании (другие перемещения между станциями запрещены). Найдите наименьшее k, при котором заведомо найдутся две станции, связанные обеими компаниями.
посмотреть в олимпиаде

Комментарий/решение:

  1
1 года 10 месяца назад #

Очень легкое решение но просто лень писать

  8
1 года 10 месяца назад #

Гений

  7
1 года 9 месяца назад #

bruh...