Всем привет, добро пожаловать на чтениеВопросы по алгоритму выходныхТемы.
Выбранный сегодня алгоритмический вопрос — это вопрос C из конкурса 1407, и этот вопрос сдали более 6700 человек. Хоть и прошедших много, вопрос этот действительно непростой, и алгоритм придумать непросто. Помимо сложности, этот вопрос очень и очень интересен.Честно говоря, я впервые вижу такой вопрос.
Ссылка на тему: https://codeforces.com/contest/1407/problem/C
Без лишних слов, давайте рассмотрим тему.
смысл названия
Этот вопрос является нетипичным вопросом алгоритма, а не вопросом алгоритмабольше похоже на игру. Цель игры состоит в том, чтобы угадать расположение n чисел от 1 до n. Нам нужно взаимодействовать с системой посредством ввода и вывода, получить больше информации от системы и, наконец, дать результат угадывания.
Сначала система выдаст целое число n, указывающее, что расстановка состоит из n чисел, и эти n чисел состоят из первых n положительных целых чисел, то есть n чисел от 1 до n. После этого мы можем вывести команду в видевопрос в системе, вопрос ?xy. Система вычислит x-е число в расстановке и вернет результат по модулю y-го числа (индекс расстановки начинается с 1), то есть вернетзначение .
Система принимает не более 2n запросов, и когда мы угадали всю перестановку, она выводит перестановку. в.
Образец
Этот пример нужно перевернуть, и 3 в первом входе представляет n. Затем посмотрите на вывод, а затем посмотрите на вход. В этом примере угадывается результат [1, 3, 2]. Сначала запрашивается результат остатка num[1] и num[2], и система возвращает 1. Затем спросите результат взятия остатка от num[3] и num[2], и ответ будет 2. Затем запросите num[1]%num[3] и num[2]%num[1] и получите 1 и 0 соответственно. Наконец, основываясь на этой информации, мы догадались, что перестановка — это [1, 3, 2], которая возвращается в виде !1 3 2.
идеи
После этого вопроса мы можем сначала найти, что,После определения n определяются n чисел.. Поскольку n самое большое, все остальные числа по модулю n сами по себе. Итак, нам нужно сначала найти позицию n.
Но положение n найти нелегко.Есть только один способ подумать об этом, то есть, когда остаток двух чисел равен n-1, можно определить, что одно из двух чисел равно n-1 и другой н. Но, очевидно, делая это, мы не можем решить ее за указанное количество шагов. Поскольку комбинация n чисел близка квиды, но лимит титула мы можем запросить не более 2n раз.
Очевидно, что сначала найти n, а потом искать другие значения не получится.
Поскольку эта идея не сработала, я начал искать другие пути. После того, как мы запросим результат x % y, какой в этом смысл? Есть ли другая информация об этом результате?
Давайте проведем краткий анализ, предположим, что x % y = 1, так что же это говорит? Очевидно, ничего нельзя сказать, потому что вариантов слишком много. 1 по модулю других чисел равен 1, и x % (x-1) также равен 1. Но что, если x % y > (n/2)? На самом деле, это может объяснить проблему. Поскольку диапазон значений x и y равен [1, n], результат после взятия по модулю двух чисел больше половины n, что, очевидно, показывает, что x — это результат, а y — число, большее x. Также возможен случай, когда x % y = 0. В этом случае, хотя мы и не можем определить значения x и y, мы можем знать, что x должно быть кратно y и x > y.
Хотя мы это знаем, этого недостаточно для решения задачи, и нам еще нужно попытать счастья, потому что мы не можем гарантировать, что сможем найти все числа больше n половин за количество запросов. Но этот пункт анализа не бесполезен, на этой основе мы можем пойти дальше. После того, как мы найдем остаток от x и y, мы можем найти остаток от y и x. Предположим, x % y = a, y % x = b, какие результаты мы можем получить, анализируя a и b?
Сначала мыЯсно, что a и b не будут равны, причина тоже очень проста, ведь x и y не должны быть равны (числа в перестановке разные). С тем же успехом мы могли бы предположить, что x > y, тогда y % x = b = y и x % y = a y должно быть получено a Мы можем судить о соотношении между x и y по соотношению между a и b., не только это, но и определить значение y.
Это очень близко к решению этой проблемы здесь, и я всего в одном шаге, но я все же пошел в обход здесь. Моя идея в то время состояла в том, чтобы сопоставить эти числа попарно, чтобы я мог идентифицировать половину из них. Затем мы соединяем нерешенные числа, пока не останется только одно число. Позже выяснилось, что есть и контрпримеры, например [1, 3, 2, 4, 5], в этом примере 1 и 3 парные, 2 и 4 парные, 5 единичные. Мы до сих пор не можем понять это.
Я тут долго думал, а потом обнаружил, что ответ далеко, а решение на самом деле очень простое. мыНужно только пройти спереди назад, чтобы сохранить максимальное значениеВот и все. Мы предполагаем, что максимальное значение равно id, и любое число, меньшее id, можно найти по результату по модулю it и id. Если встречается число больше id, id также можно получить, взяв результат по модулю. Итак, в конце мы можем найти все числа, кроме максимального, а оставшееся число равно n.
Разобраться в этом действительно, очень просто, и прямо скажем, хреново, но разобраться самостоятельно не так-то просто. И форма этого вопроса тоже очень новая, очень-очень интересная, подходит для игры на выходных.
Наконец, давайте посмотрим на код:
import sys
def guess(x, y):
print('? {} {}'.format(x, y))
# 输出之后需要flush一下，防止影响输入
sys.stdout.flush()
st = input()
return int(st)
st = input()
n = int(st)
num = [-1 for _ in range(n+2)]
# 一开始将最大值的下标设为1
idx = 1
for i in range(2, n+1):
x = guess(idx, i)
y = guess(i, idx)
# 说明遇到了更大的数，那么x就是之前的最大值
if x > y:
num[idx] = x
idx = i
# 否则求出来的就是i
else:
num[i] = y
num[idx] = n
print('! {}'.format(' '.join(map(str, num[1:n+1]))))
На этом сегодняшний вопрос окончен, и я искренне желаю вам удачи каждый день. Если вам все еще нравится сегодняшний контент, пожалуйста, зайдите на одинТройная поддержкабар~(Нравится, подписывайтесь, делайте репост)
Оригинальная ссылка, обратите внимание
В этой статье используетсяmdniceнабор текста
- END -