Школьный этап Всероссийской олимпиады школьников по информатике в Сургутском районе 9-11 класс

Максимальное значение доступности равно $$$N-1$$$ и достигается, если соединить какой-то город (назовём его столицей) со всеми остальными. Действительно, все требования выполняются (перелететь между любыми двумя городами можно с пересадкой в столице). Доступность не может превышать $$$N-1$$$, так как для каждого города существует $$$N-1$$$ город, не совпадающий с ним. Поэтому количество способов при $$$N>2$$$ равно количеству вариантов выбрать столицу, то есть $$$N$$$. При $$$N=2$$$ существует единственный способ соединения городов, который и будет максимальным, так что при $$$N=2$$$ ответ равен 1.

Очевидно, что если у участника номер паспорта больше $$$N$$$, то совпадение невозможно. Если несколько участников имеют номер, не превосходящий $$$N$$$, то в соответствующую комнату можно заселить только одного участника, для остальных совпадение уже невозможно (комната занята). Таким образом, ответ — количество различных чисел среди $$$a_i$$$, не превосходящих $$$N$$$. Подсчитать их можно, например, заведя булевский вектор из $$$N$$$ элементов, помечая там те числа, которые уже были, и в случае изменения значения элемента увеличивая счётчик возможных совпадений на единицу.

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

Обратим внимание на следующие факты:

1. Пустая запись является корректной.
2. Если две записи являются корректными, то их слияние тоже является корректным. Действительно, получится заседание, в котором к моменту окончания первой записи быди приняты все внесённые законопроекты, а затем заседание продолжилось внесением очередного законопроекта и также корректно завершилось.
3. Если запись является корректной, её можно "вставить" внутрь обсуждения одного законопроекта и получить корректную запись. Это прямо следует из третьего пункта регламента.

Несложно показать, что любую запись можно получить из пустой с помощью действий 2 или 3. Действительно, пусть у нас есть некая корректная запись. Рассмотрим первый законопроект. Он или был поставлен на голосование последним (тогда был применено третье действие — вся оставшаяся запись была вставлена в обсуждение этого законопроекта), или был поставлен на голосование в какой-то момент раньше. Тогда к моменту после голосования по первому законопроекту все внесённые законопроекты уже "закрыты", то есть часть записи от внесения законопроекта на обсуждение до голосования представляет собой корректную запись. Аналогично оставшаяся часть представляет собой корректную запись (так как к моменту её начала никаких законопроектов на повестке дня не стоит, то стартовые условия выполняются, остальные же требования следуют из корректности первоначальной записи), и в этом случае было применено второе действие. В каждом случае получаем переход к записи меньшей длины; будем продолжать действовать таким образом, пока не дойдём до пустой записи.

Тем самым мы показали, что условие задачи эквивалентно правильной скобочной последовательности с 26 типами скобок. Для проверки того, что скобочная последовательность является правильной, лучше всего использовать стек: в начале обсуждения законопроекта мы кладём на стек букву, соответствующую внёсшей его партии, по окончании — сравниваем вершину стека с буквой, соответствующей партии, законопроект которой поставлен на голосование (если не равны — запись некорректна) и снимаем букву со стека. Если в какой-то момент времени была попытка взять вершину пустого стека — запись некорректна. Если по завершении всей записи стек не пуст — какие-то законопроекты не поставлены на голосование и запись некорректна. Во всех остальных случаях запись корректна.

Если строка состоит из одного символа, то ответ $$$-1$$$ в случае, если число не является составным (1 2 3 5 7), и $$$10$$$ (к примеру) в случае, если является (то есть 4 6 8 9).

Если строка состоит из более чем одного символа, то работает ответ ($$$B=S+1$$$, $$$X=S$$$), где $$$S$$$ — сумма цифр (так как $$$X^k-1=(X-1)\cdot(X^{k-1}+\ldots+X+1)$$$, то остаток числа в $$$S+1$$$-ичной системе от деления на $$$S$$$ равен остатку от деления на $$$S$$$ суммы его цифр, то есть 0 по построению).