задача "три монеты" из соревнования по программированию

Question

я пока новичок и столкнулся с сложной для меня задачей на бинарный поиск. Думал простые будут...Может быть у меня просто теории недостаточно. Если это так то напишите.

Мне нужен алгоритм решения, который я пойму. Код сам напишу.

ссылка на задачу из acmp: https://acmp.ru/asp/do/index.asp?main=task&id_course=1&id_section=3&id_topic=37&id_problem=1840

Это интерактивная задача.

Перед вами стопка из N монет. В стопке есть все монеты номиналов от 1 до N, причём они упорядочены по возрастанию сверху-вниз. То есть, верхняя монета номиналом 1, а нижняя — N. Вес каждой монеты равен её номиналу. Некто заменил ровно три монеты в стопке на фальшивые — вес таких монет равен нулю. Вы можете спрашивать суммарный вес первых K монет сверху для любого 0 ≤ K ≤ N.

Определите номиналы фальшивых монет не более чем за 32 вопроса, и тогда Некто подарит вам всю стопку монет.

Протокол взаимодействия Вначале на ввод подаётся число N — количество монет (3 ≤ N ≤ 109). Далее ваша программа должна выводить запросы вида «? K», где 0 ≤ K ≤ N. В ответ вы получите сумму весов первых K монет вверху стопки.

Как только ваша программа будет готова сообщить ответ, выведите «! A B C», где 1 ≤ A, B, C ≤ N — различные номиналы фальшивых монет. После этого программа должна завершить работу.

Пример стандартный ввод

стандартный вывод

? 6
? 5
? 4
? 3
? 2
? 1
? 0
! 1 5 3

Answer 1

Просто как идея:

Запрашиваете вес всех монет. Смотрите, какого веса не хватает. Это пусть будет вес X = a+b+c

Если X меньше, чем N, то интервал X,N можно выкинуть из поиска навсегда. Например, если не хватает чисел 1, 2, 3 (то есть их сума равне 6), а всего чисел 100, то нет смысла что то искать в интервале (6, 100)

Двоичным поиском находите любую точку K, где не хватает другого числа Y < X

Тут надо иметь ввиду, что в процессе поиска можно отсечь какой то участок и в нем дальше не искать никогда. Например, если на N/2 нехватка веса также X, то всю область от N/2 до N можно исключить. Если на N/2 нехватки веса нет совсем, то можно исключить диапазон от 0 до N/2 из любых дальнейших поисков.

Остается найти точку, где не хватает веса Z, Z<X, Z!=Y. Эта точка будет с одной из сторон от точки K.

Имея X, Y, Z и зная, что X=a+b+c и что одна из (Y,Z)=a+b, другая просто (Y,Z)=b, можно легко вычислить a, b, c.

Answer 2

Диапазон 1..4 рассматриваем отдельно, чтобы сэкономить один вызов. Делаем вызов для 4, и в случае сомнительных сумм ещё один вызов для 1.

Пойдём бинарным поиском с увеличивающимся шагом, начиная с 4: делаем запросы для 8, 16, 32... монет. Итого 28 шагов до 2³⁰.

Почему так? Если отсутствуют монеты в диапазоне D: lo=2^k+1..hi=2^k+1, то никакая монета из диапазона не может быть суммой двух других.

Вычисляем нехватку s на данном диапазоне.

 sm = sum(l[:hi])
 calls += 1
 s = hi * (hi+1) // 2 - sm

Если отсутствует одна монета, то s<=hi, мы сразу видим её номинал. Заносим в результат, исправляем ноль на значение s, чтобы дальнейшим вычислениям не мешало.

Иначе в диапазоне несколько нулей.

Если s > 2*hi, то в диапазоне три нуля.

Делаем запрос по элементу pivot=s/3.
Если недостача слева slo больше, чем справа shi, то слева от pivot (включая его) два нуля, справа один, и его позиция shi известна. Уточняем позиции слева, делая запрос по slo/2. Аналогично для shi>slo. Расчёт окончен.

Если s находится в пределах от hi+1 до 2*hi, то случай сложный. Может быть как 2 нуля, так и три

D = 17..32 
s = 57 = 17+18+22 = 17+19+21 = 18+19+20 = 25+32 = 26+31 = 27+30 = 28+29

Выполняем деление по pivot=s/2.

Если недостачи слева и справа slo, shi меньше или равны hi, то найдена пара нулей

Иначе нуля три, и выполняем ещё одно деление по s/3 и действуем, как описано раньше для трёх монет.

Алгоритм на случайных тестах и вручную заданных сложных случаях работает, количество проверок не превышает log(n)+2 (32 для 2^30).

Answer 3

import sys

def query(k):
    sys.stdout.write(f"? {k}\n")
    sys.stdout.flush()
    response = int(input())
    return response

# Helper function to calculate expected weight
def expected_weight(k):
    return k * (k + 1) // 2

def search(l, r, diff):
    res = set()
    while r - l > 1:
        if len(res) == 2:
            break
        mid = (l + r) // 2
        actual_weight = query(mid)
        
        if expected_weight(mid) - actual_weight == 0:
            l = mid
        elif expected_weight(mid) - actual_weight == diff:
            r = mid
        else:
            candidate = expected_weight(mid) - actual_weight
            if diff - candidate > r:
                res.add(candidate)
                l = mid
            else:
                res.add(diff - candidate)
                diff-=(diff - candidate)
                r = mid
    return res

def main():

    N = int(input())

    total_weight = query(N)
    total_diff = expected_weight(N) - total_weight
    a, b = search(-1, N + 1, total_diff)

    c = total_diff - a - b
    a, b, c = sorted([a, b, c])
    sys.stdout.write(f"! {a} {b} {c}")
    sys.stdout.write("\n")
    sys.stdout.flush()

if __name__ == "__main__":
    main()

БЛОГ НА HUSL

задача "три монеты" из соревнования по программированию

Ответы (3 шт):