Соревнования по двоеборью проводятся в два тура. на каждом из туров участники получают некоторые , причем всех участников различны как на турах, так и в сумме за два тура. считается, что участник занял место k, если ровно k-1 из участников набрали больше , чем он. всего в соревновании участвовало n человек. на первом туре вася занял место p, а на втором туре - место q. определите, какое минимальное и максимальное место мог занять вася по сумме двух туров.

ответ: минимальное место: max(p + q - n, 1); максимальное место: min(p + q - 1, n)

решение:

гарантированно ниже васи по сумме двух туров будут участники, занявшие в каждом туре места ниже васи (их за каждый тур ниже васиных, тогда и сумма будет ниже); аналогично, гарантированно выше васи будут все, кто оба раза занимал место выше васи.

а) минимальное (самое высокое) место у васи будет, если будет как можно меньше тех, кто оба тура был выше васи в таблице результатов. в первом туре был p - 1 более успешный участник (и n - p менее успешных), во втором - q - 1. в лучшем для васи случае min(q - 1, n - p) более успешных участников второго тура не были выше васи в первом туре, и только q - 1 - min(q - 1, n - p) = max((q - 1) - (q - 1), (q - 1) - (n - p)) = max(q + p - n - 1, 0) окажутся гарантированно выше васи, и вася сможет занять место 1 + max(q + p - n - 1, 0) = max(q + p - n, 1).

б) аналогично, максимально возможное (наихудшее) место будет, если тех, кто гарантированно ниже васи, будет как можно меньше. оба раза проиграли васе не больше max((n - p) - (q - 1), 0), тогда место васи окажется не ниже n - max(n - p - q + 1, 0) = min(p + q - 1, n)