0

не могу второй день решить задачу. Идей вообще нет. Скажите алгоритм решения. Код сам напишу.

Задача из acmp: https://acmp.ru/asp/do/index.asp?main=task&id_course=1&id_section=3&id_topic=37&id_problem=1839

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

Антона в очередной раз пригласили принять участие в марафоне, но этот марафон оказался довольно необычным — он проводился на стадионе!

Антона позвали в другой город, поэтому про стадион, на котором он собирается бежать, ему ничего не известно (даже примерно). Чтобы скрасить свое участие в этом довольно скучном событии, он поставил перед собой задачу — узнать длину кругового участка стадиона.

Опыт Антона в забегах позволяет ему с высокой точностью отмерять расстояние и пробегать ровно k метров по треку. Но памятью наш бегун похвастаться не может. Единственное, что он в силах запомнить — это сколько кругов он уже пробежал.

Антон предлагает вам скооперироваться, а именно помочь ему узнать длину беговой дорожки стадиона за не более чем 100 продвижений по треку.

Протокол взаимодействия

Взаимодействие происходит с помощью запросов. Вы можете просить Антона пробежать на k метров вперёд с помощью запроса run k (1 ≤ k ≤ 10^9). В ответ на такой запрос вы получите единственное число — количество кругов, которое он уже пробежал, включая текущий запрос. Круг считается завершённым, если бегун пробегает стартовую точку или находится в ней.

Гарантируется, что длина участка — положительное целое число, не превышающее 10^9.

Если вы готовы указать длину кругового участка, то вы можете убедиться в его правильности с помощью запроса ensure s. После такого запроса программа должна немедленно завершиться.

При превышении количества запросов (более 100) вы получите вердикт Wrong answer (при условии завершения работы программы).

Ваше решение может получить вердикт Time Limit Exceeded, если вы ничего не выводите или забываете сбросить буфер вывода.

Пример

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

1
1
2
3

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

run 5
run 2
run 4
run 1
ensure 4
3
  • (1) вы не перепутали ввод и вывод? (2) между командами run Антон бежит или стоит? (3) в начальный момент Антон находится на старте?
    – Pak Uula
    2 июн 2021 в 11:29
  • Идей вообще нет : по бинарному поиску
    – MBo
    2 июн 2021 в 16:36
  • Задача действительно оказалась на бинарный поиск :)
    – Pak Uula
    2 июн 2021 в 21:51

2 ответа 2

2

Идея алгоритма такова.

Пусть на каком-то шаге Антон пробежал суммарно дистанцию D, про которую известно, что она составляет n целых кругов. Тогда мы можем утверждать, что длина круга x заключена в пределах D/(n+1)< x <=D/n.

Так как арифметика целочисленная, то границы интервала l и r, между которыми заключен x, равны ceil(D/(n+1)) и floor(D/n)

Теперь можно начинать бинарный поиск.

Если x находится ближе к левому краю интервала, то есть x <= (l+r)/2, то (n+1)x <= (n+1)(l+r)/2. Сдвинем Антона в точку (n+1)(l+r)/2, то есть выдадим команду run((n+1)(l+r)/2 - D) и сравним результат с n.

Если результат будет n+1, значит x находится в левой половине интервала [l,r] - сдвинем правый конец: r = (r+l)/2

Если результат будет n, значит x находится в правой половине интервала [l,r] - сдвинем левый конец: l = (r+l)/2.

Так как арифметика целочисленная, то нужно аккуратно обработать случай, когда r = l+1. Если x == l, то после дистанции l*(n+1) счётчик кругов будет n+1. Если x == l+1, то после дистанции l*(n+1) счётчик кругов будет n.

Реализация на Python:

import math

class Anton:
    def __init__(self, x):
        self.x = x
        self.D = 0
    def run(self, k):
        self.D += k
        return self.D // self.x

def solve(anton, MAX=10**9, log=False, steps=100):
    a = anton
    n = a.run(MAX-1)
    if n == 0:
        if log:
            print(1, MAX, MAX, a.D, n)
        return MAX
    # (a.D+1)//(n+1) + 1 == ceil((a.D+1)/(n+1))
    # a.D//n == florr(a.D/n)
    # замена на целочисленную арифметику, так как при больших MAX 
    # арифметика с плавающей точкой даёт неверные ответы из-за потери точности
    l,r = (a.D+1)//(n+1) + 1, a.D//n
    
    if log:
        print(1,l,r, a.D, n)
    for i in range(2, steps+1):
        dx = (r-l)//2
        if dx == 0:
            if r == l:
                return l
            n2 = a.run((n+1)*l-a.D)
            if n2 == n+1:
                return l
            elif n2 == n:
                return r
            else:
                assert False, f"Must never happen: failed at the last step: n={n}, n2={n2}, l={l}, distance={a.D}"
        assert (n+1)*l >= a.D, f"Must never happen: n={n}, l={l}, distance={a.D}"
        distance = (n+1)*(l+dx)
        n2 = a.run(distance - a.D)
        if n2 == n:
            l = l+dx
        elif n2 == n+1:
            r = l+dx
        else:
            assert False, f"Failed on step {i}: {n}, {n2}, {l}, {r}, {x}"
        n = n2
        assert l*n <= a.x*n
        assert a.x*n <= r*n
        if log:
            print(i, l,r, a.D, n)
    if l != r:
        return None
    return l

Примеры работы.

solve(Anton(123456789), log=True) =>

1 111111111 124999999 999999999 8
2 118055555 124999999 1062499995 8
3 121527777 124999999 1093749993 8
4 123263888 124999999 1109374992 8
5 123263888 124131943 1117187487 9
6 123263888 123697915 1236979150 10
7 123263888 123480901 1358289911 11
8 123372394 123480901 1480468728 11
9 123426647 123480901 1481119764 11
10 123453774 123480901 1481445288 11
11 123453774 123467337 1481608044 12
12 123453774 123460555 1604987215 13
13 123453774 123457164 1728400296 14
14 123455469 123457164 1851832035 14
15 123456316 123457164 1851844740 14
16 123456740 123457164 1851851100 14
17 123456740 123456952 1851854280 15
18 123456740 123456846 1975309536 16
19 123456740 123456793 2098765481 17
20 123456766 123456793 2222221788 17
21 123456779 123456793 2222222022 17
22 123456786 123456793 2222222148 17
23 123456786 123456789 2222222202 18
24 123456787 123456789 2345678953 18
25 123456788 123456789 2345678972 18

123456789

solve(Anton(987654321), log=True) =>

1 500000000 999999999 999999999 1
2 749999999 999999999 1499999998 1
3 874999999 999999999 1749999998 1
4 937499999 999999999 1874999998 1
5 968749999 999999999 1937499998 1
6 984374999 999999999 1968749998 1
7 984374999 992187499 1984374998 2
8 984374999 988281249 2964843747 3
9 986328124 988281249 3945312496 3
10 987304686 988281249 3949218744 3
11 987304686 987792967 3951171868 4
12 987548826 987792967 4937744130 4
13 987548826 987670896 4938354480 5
14 987609861 987670896 5925659166 5
15 987640378 987670896 5925842268 5
16 987640378 987655637 5925933822 6
17 987648007 987655637 6913536049 6
18 987651822 987655637 6913562754 6
19 987653729 987655637 6913576103 6
20 987653729 987654683 6913582781 7
21 987654206 987654683 7901233648 7
22 987654206 987654444 7901235552 8
23 987654206 987654325 8888888925 9
24 987654265 987654325 9876542650 9
25 987654295 987654325 9876542950 9
26 987654310 987654325 9876543100 9
27 987654317 987654325 9876543170 9
28 987654317 987654321 9876543210 10
29 987654319 987654321 10864197509 10
30 987654320 987654321 10864197520 10

987654321

solve(Anton(10**9), log=True) =>

1 1000000000 1000000000 999999999 0

1000000000

Благодаря тому, что в Python целые не ограничены, эта реализация может работать с числами любой размерности. Единственное требование - достаточное количество итераций: MAX < 2**(steps-1)

8
  • А если MAX_S = 10**9 ?
    – MBo
    2 июн 2021 в 15:51
  • @MBo Да, был неправ. Исправил.
    – Pak Uula
    2 июн 2021 в 21:50
  • Из описания непонятно, как в начале достичь дистанции во сколько-то целых кругов. Не придётся ли назад возвращаться? (это не разрешено)
    – MBo
    3 июн 2021 в 6:19
  • @MBo первое смещение делается на MAX-1. Для всех значений длин круга, за исключением максимального, это даст ненулевое значение n, из которого вычисляются начальные значения l и r. Если смещение на MAX-1 даёт число кругов 0, значит длина круга равна MAX.
    – Pak Uula
    3 июн 2021 в 6:29
  • Т.е. Антон пробегает 999999999 метров. Потом, получается, назад? А нельзя - Вы можете просить Антона пробежать на k метров вперёд. Вместо этого можно использовать бинарный поиск с расширяющимися шагами, а по достижению одного круга переходить к сужающимся шагам.
    – MBo
    3 июн 2021 в 6:36
0

(P.S. прочитал условие как от 1 до 109, вместо от 1 до 10^9; Поэтому и предложил алгоритм +109 до 400 метров, и так далее ...)

Я бы разбил задачу на три состояния

  1. Пока пробежал < 1 круга
  2. Пробежал 1 круг

Для каждого состояния написал бы свою логику например: Для (1) известно что обычно длина круга 400 метров, поэтому прибавляем по максимуму до суммы 399 а затем прибавляем 1 (400) если в этот момент кво кругов станет 1 мы нашли решение ! Для (2) в момент когда кво кругов станет = 1 мы будем знать, минимальную длину круга (пробежал до этого + 1) и максимальную; Начиная с этого момента нам необходимо добежать до (мин_круг * 2) максимально быстро и Если произошла смена круга - мы нашли решение; В противном случае до (мин_круг+1) * 2 и так далее ... может не оптимально, зато просто !

4
  • Для длины круга миллион метров будет работать?
    – MBo
    2 июн 2021 в 15:20
  • почему бы нет ?! конечно будет
    – santavital
    3 июн 2021 в 6:47
  • Сколько шагов будет до миллиона? (просто стратегия не описана)
    – MBo
    3 июн 2021 в 7:24
  • Прошу прощения, когда читал задание - прочитал от 1 до 109, вместо от 1 до 10^9
    – santavital
    3 июн 2021 в 12:07

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.