1

Возникла проблема при решении задачи на Python3. Текст задачи

Ваня принес на кухню рулет, который он хочет разделить с коллегами. Для этого он хочет разрезать рулет на N равных частей. Разумеется, рулет можно резать только поперек. Соотвественно, Костя сделает N - 1 разрез ножом через равные промежутки.

По возвращению с кофе-брейка Ваня задумался — а можно ли было обойтись меньшим числом движений, будь нож Вани бесконечно длинным (иначе говоря, если он мог бы сделать сколько угодно разрезов за раз, если эти разрезы лежат на одной прямой)? Считается, что места для разрезов намечены заранее, и все разрезы делаются с ювелирной точностью.

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

Вам дано число N, требуется сказать, каким минимальным числом разрезов можно обойтись.

Формат входных данных

Дано одно натуральное число N (1≤N≤2000000000) — количество людей на кофе-брейке.

Формат выходных данных

Выведите одно число — минимальное число движений, которое придется сделать Косте.

Замечание

Чтобы разрезать рулет на 6 частей, Ване сначала придется разрезать его на две равные части, после чего совместить две половинки и сделать два разреза.

Чтобы разрезать рулет на 5 частей, Ване понадобится разделить его в соотношении 2:3, после чего совместить два рулета по левому краю и разрезать больший рулет на одинарные кусочки — меньший тоже разделится на одинарные."

Решил ее я так:

a = int(input())
b = 2
c = 1
while (b<=a):
    c+=1
    b=2**c
if a-b!=0 and a-b>0:
    c+=1
print(c)

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

3
  • Добавьте ссылку на проверяющую систему. 2 фев 2022 в 8:17
  • Добавьте словестное описание вашего решения. 2 фев 2022 в 8:17
  • подправил задание 2 фев 2022 в 8:21

2 ответа 2

3

Ваша программа ошибается для небольших N:

N     ваш   должно
     ответ   быть

1      1      0          # ошибка
2      2      1          # ошибка
3      2      2
4      3      2          # ошибка
5      3      3
6      3      3
7      3      3
8      4      3          # ошибка

Пусть fN - минимальное число разрезаний для N кусков. Какие у него есть свойства?

  1. f1 = 0 - ничего резать не надо если вы завтракаете в одиночестве.

  2. f2N ≤ 1 + fN - если число разрезов чётное, то режем рулет строго пополам, две половинки кладём рядом и следуем решению для N разрезов.

  3. fN > k, если N > 2k. Каждый разрез в лучшем случае удваивает число кусков. Лучший результат для k разрезов - 2k кусков. Если требуется больше кусков, нужно и больше разрезов.

  4. fN+1 ≥ fN - неубывание. Разрезание для большего числа кусков годится и для меньшего числа кусков.

Из 1, 2 получается ответ для степеней двойки (N = 2k): по индукции f2k ≤ k. Способ разрезания - k раз режем все куски пополам: f2k = k.

Если N между соседними степенями двойки (2k-1 < N < 2k), то из монотонности следует k-1 ≤ fN ≤ k. Из третьего пункта k-1 < fN. Следовательно fN = k.

В итоге нам надо найти ceil(log_2(N)):

n = int(input())

e = 0
p = 1
while p < n:
    e += 1
    p *= 2
print(e)

P.S. В Питоне задачу можно решить в виде замкнутой формулы. n.bit_length() возвращает длину числа в битах. Это почти то что нам нужно - формула ошибается на единицу на точных степенях двойки, для остальных чисел ответ верный. Проверить что число точная степень двойки можно так: n & (n - 1) == 0. Операция n & (n - 1) стирает младший ненулевой бит числа. Если число "стёрлось" до нуля, значит единичный бит в нем был только один, значит это была степень двойки.

Программа:

n = int(input())
print(n.bit_length() - (n & (n - 1) == 0))

P.P.S. Битовые хитрости не нужны. Предыдущее выражение просто-напросто равно (n - 1).bit_length():

print((int(input()) - 1).bit_length())
3
0

Либо так через логарифм по основанию 2:

import math

print(math.ceil(math.log2(int(input())))

Ваш ответ

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

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