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)

Answer 2

Давайте разберемся, как определить минимальное и максимальное место Васи по сумме двух туров.

Пусть на первом туре участвовало M человек (1 ≤ M ≤ N), и на втором туре участвовало L человек (1 ≤ L ≤ N). Тогда место Васи в первом туре (P) и место Васи во втором туре (Q) удовлетворяют условиям:

1. 0 ≤ P ≤ M (Вася может быть первым, а может быть последним).
2. 0 ≤ Q ≤ L (аналогично, Вася может быть первым или последним на втором туре).

Теперь рассмотрим минимальное и максимальное место Васи по сумме двух туров.

Минимальное место:

• Минимальное место Васи будет находиться там, где он получил максимальное количество баллов. То есть, если Вася занял место P на первом туре, то он обязан обойти всех участников, которые получили меньше баллов на первом туре, и он также должен обойти всех участников, которые получили меньше баллов на втором туре (то есть, заняли места до Q). Следовательно, минимальное место Васи будет max(P, Q) + 1.

Максимальное место:

• Максимальное место Васи будет находиться там, где он получил минимальное количество баллов. То есть, если Вася занял место P на первом туре, то он может быть обойден всеми участниками, которые получили на первом туре больше баллов (их будет M - P), и он также может быть обойден всеми участниками, которые получили на втором туре больше баллов (их будет L - Q). Следовательно, максимальное место Васи будет N - min(M - P, L - Q).

Итак, минимальное место Васи по сумме двух туров: max(P, Q) + 1. Максимальное место Васи по сумме двух туров: N - min(M - P, L - Q).

Пожалуйста, убедитесь, что правильно указали значения P, Q, N, M и L, и затем используйте формулы выше для определения минимального и максимального места Васи по сумме двух туров.