Задача №112780. Дварфы-1
Кто-то украл драгоценности короля дварфов! Дварфовая полиция, поднятая по тревоге, ночью арестовала \(N\) подозреваемых. Подозреваемых пронумеровали числами от \(1\) до \(N\), после чего заперли всех их в одной клетке.
Утром судья рассадит подозреваемых по одиночным камерам, после чего опросит всех их в случайном порядке. Очевидно, что каждый подозреваемый будет свидетельствовать против кого-то другого, не себя.
Ночью все подозреваемые собрались, чтобы обсудить их стратегию.
Им известно, что в комнате для допросов поставили новый стол. Они понимают, что во время допроса единственный способ передавать друг другу информацию — это оставлять засечки на столе.
Когда серия допросов начнётся, на столе не будет никаких засечек. Во время допроса, дварф будет видеть все засечки, оставленные до него. На столе не может быть более \(M\) засечек — если засечек будет слишком много, судья их заметит и обвинит дварфов в сговоре. Оставленную засечку удалить нельзя. Все засечки выглядят одинаково.
Судья будет вызывать подследственных в случайном порядке. Приговор обвиняемого (назовём его А) зависит только от того, против кого он даст показания. Если А даст показания против того, кто ещё не был допрошен, А будет оправдан, в противном случае А будет приговорён (вне зависимости от того, был ли оправдан или приговорён дварф, против которого даст показания А).
Дварфы хотят разработать стратегию, в которой каждый знает, что ему делать в зависимости от количества засечек на столе (от \(0\) до \(M\)). Увидев количество засечек, каждый подозреваемый должен знать, какого дварфа ему обвинить, нужно ли ему оставлять засечки на столе и если нужно, то сколько. Каждый дварф может вести себя независимо (не обязательно правила действий для всех дварфов совпадают).
Задача. Разработайте стратегию, которая оправдает как можно больше дварфов. Она будет протестирована на разных порядках допросов дварфов, после чего количество баллов будет зависеть от среднего количества подозреваемых, получивших оправдательный приговор.
Система оценивания. Для каждого теста проверяющей системой будет сгенерировано \(K = 100000\) случайных перестановок, которые будут определять порядок вызова дварфов на допрос. Предоставленная участником стратегия будет протестирована на всех этих перестановках. Количество баллов, начисляемых за тест, равно \(min \left({ \left \lceil{ 20\times{\left({ \frac{W}{S} }\right)}}^4\right \rceil, 20}\right)\) где \(W\) — среднее количество оправданных дварфов. Параметр \(S\) зависит от теста:
Test No. |
N |
M |
S |
1 |
10 |
1 |
6.5 |
2 |
100 |
2 |
70.5 |
3 |
100 |
3 |
74.7 |
4 |
100 |
6 |
77.9 |
5 |
100 |
10 |
80.7 |
Тесты в этой задаче являются открытыми. В условии описаны 5 наборов входных данных, каждый из них рассматривается как отдельная задача с соответствующим номером, в систему необходимо отправить ответ на нее.
Формат посылки в проверяющую систему. Стратегией считается текстовый файл, состоящий из \(N\) строк. \(i\)-ая строка описывает алгоритм действия \(i\)-го дварфа и представляет из себя \(2*(M+1)\) целых чисел, разделённых пробелами:
- Первые два числа предписывают, кого должен обвинить \(i\)-ый дварф и сколько засечек он должен оставить на столе, если на столе нет засечек.
- Третье и четвёртое число предписывают, кого должен обвинить \(i\)-ый дварф и сколько засечек он должен оставить на столе, если на столе одна засечка.
- Пятое и шестое число предписывают, кого должен обвинить \(i\)-ый дварф и сколько засечек он должен оставить на столе, если на столе две засечки.
- ...
- Последние два числа предписывают, кого должен обвинить \(i\)-ый дварф и сколько засечек он должен оставить на столе, если на столе \(M\) засечек.
Количество засечек на столе не должно превышать \(M\). Дварф не может дать показания против себя.