3

Не идёт код к задаче, помогите, пожалуйста, решить её на Python

Задача Чехарда

Дорожка замощена плитками в один ряд, плитки пронумерованы числами от 1 до 1000. На плитках с номерами A, B и C (A<B<C) сидят три кузнечика, которые играют в чехарду по следующим правилам:

  1. На одной плитке может находиться только один кузнечик.

  2. За один ход один из двух крайних кузнечиков (то есть с плитки A или с плитки C) может перепрыгнуть через среднего кузнечика (плитка B) и встать на плитку, которая находится ровно посередине между двумя оставшимися кузнечиками (то есть между B и C или A и B соответственно). Если между двумя оставшимися кузнечиками находится чётное число плиток, то он может выбрать любую из двух центральных плиток.

Например, если кузнечики первоначально сидели на плитках номер 1, 5, 10, то первым ходом кузнечик с плитки номер 10 может перепрыгнуть на плитку номер 3 (она находится посередине между 1 и 5), или кузнечик с плитки номер 1 может перепрыгнуть на плитку номер 7 или 8 (эти две плитки находятся посередине между плитками 5 и 10).

Даны три числа: A, B, C . Определите, какое наибольшее число ходов может продолжаться игра.

Входные данные

Программа получает на вход три целых числа A, B и C (1≤A<B<C≤1000), записанных в отдельных строках.

Выходные данные

Выведите одно число — наибольшее количество ходов, которое может продолжаться игра.

Примечание к примеру

В примере сначала кузнечик с плитки №6 прыгает на плитку №3. Затем кузнечик с плитки №4 прыгает на плитку №2.

Примеры

Входные данные

1
4
6

Выходные данные

2

Выдает ошибку на тесте 4 и 60 баллов из 100, но какая ошибка посмотреть невозможно:

a = int(input())
b = int(input())    
c = int(input())    

d = (c - b) + (b - a) - 2    
s = 0    
while d > 0:    
    s += 1    
    d >>= 1

print(s)
Улучшить вопрос
11
  • Почему не получается? Кто куда не идёт? Commented 1 нояб. 2024 в 14:02
  • :(( Помогите, пожалуйста, вместо того, чтобы кидаться сарказмом Commented 1 нояб. 2024 в 14:06
  • 1
    @Оксана, учебные задания допустимы в качестве вопросов только при условии, что вы пытались решить их самостоятельно перед тем, как задать вопрос. Пожалуйста, отредактируйте вопрос и укажите, что именно вызвало у вас трудности при решении задачи. Например, приведите код, который вы написали, пытаясь решить задачу Commented 1 нояб. 2024 в 14:07
  • 1
    @чистов_n добавила неполноценный код Commented 1 нояб. 2024 в 14:13
  • 1
    А не будет ли случайно результат равен числу битов (битовой длине) в максимальной из разниц (c - b) и (b - a)? Commented 1 нояб. 2024 в 14:40

1 ответ 1

Сброс на вариант по умолчанию
6

Задача решается аналитически элементарно:

=INT(LOG2(2*MAX(B-A,C-B)-1))

a = int(input())
b = int(input())
c = int(input())
# Option 1
from math import log2
d = max(b - a, c - b)
print(int(log2(2 * d - 1))) 
# Option 2
d = max(c - b, b - a) - 1
print(d.bit_length())

Поскольку нужно найти наибольшее число шагов, то начинаем с большего промежутка d = max(b - a, c - b), что сводится к расположению { A = B - d; B; C = B + d }. С каждым шагом промежуток уменьшается вдвое, поэтому количество шагов равно двоичному логарифму от первоначального расстояния между двумя соседними кузнечиками d. Если очередной промежуток d чётный, то следующий выбирается d/2. Для любого натурального n количество решений для промежутков 2n и 2n+1 одинаковое.

Варианты решения эквивалентны, так как d.bit_length() equals int(log2(d) + 1).

введите сюда описание изображения

Улучшить ответ
10
  • 1
    py from math import log2 a = int(input()) b = int(input()) c = int(input()) d = max(abs(b - a), abs(c - b)) print(int(log2(2 * d - 1))) Commented 1 нояб. 2024 в 16:00
  • 2
    @Lith С bit_length тоже решается, но немного не так, как вы сделали: a = int(input()) b = int(input()) c = int(input()) d = max(c - b, b - a) - 1 print(d.bit_length()) Commented 1 нояб. 2024 в 16:12
  • 2
    @rotabor, вы смелый человек. Я потратил полтора часа на написание объяснения, откуда логарифм берётся и бросил не доведя до конца: никто не стал бы такое читать. Commented 2 нояб. 2024 в 7:41
  • 1
    @StanislavVolodarskiy Как я уже прокомментировал где-то, главное - не бздеть. В конце концов, расхлёбывать будет Оксана :-) Commented 2 нояб. 2024 в 7:43
  • 1
    @StanislavVolodarskiy Смелость - это когда приезжаешь на завод, останавливаешь установку и начинаешь что-то делать, а через несколько часов её нужно запустить... Commented 2 нояб. 2024 в 7:45

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Начните задавать вопросы и получать на них ответы

Найдите ответ на свой вопрос, задав его.

Задать вопрос

Изучите связанные вопросы

Посмотрите похожие вопросы с этими метками.