Разбор задачи про настольный теннис

Эта статья посвящена разбору задачи про игру в настольный теннис. Придумаем алгоритм для ее решения и напишем его на языке Java. Отмечу, что чистота кода в решении и принципы ООП принесены в жертву внятности и понятности алгоритма человеческому глазу как ни парадоксально, ведь как завещал дядя Боб чистота кода подразумевает написание исходного кода программ на человекопонятном языке. Ну да ладно, немного отошли от темы. Задача взята с одного из соревновательных раундов codeforces.com. Вашему внимание условие задачи:

К теннисному столу выстроилась очередь из n человек. Сначала первые двое играют партию в теннис. Потом проигравший встаёт в конец очереди, а победитель играет со следующим человеком из очереди, и так далее. Они играют до тех пор, пока кто-нибудь не выиграет в k партиях подряд. Этот игрок признаётся победителем.

Про каждого из участников вы знаете его силу игры в теннис, и у всех игроков они различны. В партии всегда побеждает игрок с большей силой. Определите, кто станет победителем.

Входные данные

В первой строке находятся два числа, разделённые пробелом: n и k (2 ≤ n ≤ 500, 2 ≤ k ≤ 1012) — количество людей и количество побед подряд, после которого игрок становится победителем, соответственно.

В следующей строке содержится n целых чисел a1, a2, …, an (1 ≤ ai ≤ n), выражающих силу игроков. Гарантируется, что эта строка содержит перестановку, то есть все ai различны.

Выходные данные

Выведите одно число — силу победителя.

Пример:

входные данные

выходные данные

Начнем расправляться с условием по порядку. Имеем очередь из n игроков, последовательно играющих друг с другом. Для реализации очереди вполне подойдет такая структура данных как массив. Размерность массива n – это количество игроков, а его элементы – сила каждого игрока в этом массиве. Нетрудно догадаться, что нам предстоит сравнивать последовательно элементы массива друг с другом и присуждать победу игроку, с большей силой, далее проигравший становится в конец, а победителя сравниваем со следующим игроком (следующим элементом массива) до тех пор, пока игрок не проиграет, либо до достижения их необходимого числа побед  – k. Для ввода этих данных через консоль воспользуемся классом Scanner из пакета java.util.

Отлично, у нас есть входные данные! Дело за малым, осталось придумать как определить победителя. Заметим, что из условия задачи можно выделить инвариант для алгоритма: проигравший встаёт в конец очереди. Нам необязательно учитывать это условие, и описывать это условие кодом. Инвариант здесь это то, что если мы проходим до конца массива не выявив победителя, то победителем станет игрок, с наибольшей силой. Это замечание позволяет нам упростить реализацию. Напишем метод для поиска максимального элемента массива:

Метод статический, потому что все решение мы пишем в одном классе. Мы использовали классический прием поиска максимального элемента массива: полагаем, что максимальный элемент первый и далее сравниваем его последовательно с каждым следующим элементом массива и если максимальный меньше, то присваиваем максимуму новое значение.

Отлично, мы упростили задачу, теперь напишем функцию самого процесса игры, исходя из замеченного нами инварианта. По сути для написания нам нужно просто переписать условие задачи на язык Java.

Прежде всего обратим внимания на еще один инвариант: если нужное количество побед больше количества игроков (k>n), то победителем так же станет игрок с максимальной силой.

Мы решили половину задачи, вторая половина будет выглядеть так. Мы проводим сравнение силы игроков, до тех пор, пока  кто-то из них не достигнет нужного количества побед, либо дойдем до последнего игрока. Второе условие гарантирует нам победу игрока с максимальной силой.

Алгоритм имеет сложность O(N), не самая идеальная, наверняка можно улучшить, но для нас сейчас это не важно. Вот и конечный результат, учитывающий все условия поставленной задачи. Полностью исходный код программы:

2 comments On Разбор задачи про настольный теннис

Оставить комментарий:

Ваш email не будет опубликован.