Соревнования по двоеборью проводятся в два тура. на каждом из туров участники получают некоторые , причем всех участников различны как на турах, так и в сумме за два тура. считается, что участник занял место 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)