Соревнования по двоеборью проводятся в два тура. ** каждом из туров участники получают...

Question

Соревнования по двоеборью проводятся в два тура. На каждом из туров участники получают некоторые баллы, причем баллы всех участников различны как на турах, так и в сумме за два тура. Считается, что участник занял место K, если ровно K-1 из участников набрали больше баллов, чем он. Всего в соревновании участвовало N человек. На первом туре Вася занял место P, а на втором туре - место Q. Определите, какое минимальное и максимальное место мог занять Вася по сумме двух туров.

Answer 1

Ответ: минимальное место: 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)