Задача База на Луне

@semen1984 · Регистрация: 07.05.2024

Студворк — интернет-сервис помощи студентам

В рамках программы освоения космоса было построить научную базу на Луне. Для этого был выделен прямоугольных участок размера w×h метров. База должна состоять из n прямоугольных модулей размера a×b метров. При этом вокруг каждого модуля должен быть защитный барьер – если барьер имеет толщину d, то модуль занимает площадь (a+2d)×(b+2d); барьеры не должны пересекаться.

Стороны модулей должны быть параллельны сторонам участка, и все модули должны быть ориентированы одинаково. Требуется определить максимально возможную толщину барьера, которая позволит разместить все модули на участке.

Формат входных данных
В единственной строке входных данных содержатся пять целых чисел n,a,b,w,h (1≤n,a,b,w,h≤10^18).

Формат результата
Требуется вывести целое число – максимальную возможную целую толщину барьера.

Добавлено через 2 минуты
моё решение валится на 7-м тесте
к сожалению, узнать тестовый сценарий нет возможности
прошу помощи

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def check(x, n, w, h, a, b):
    return (n*(x + a) <= w and n*(x + b) <= h) or (n*(x + a) <= h and n*(x + b) <= w)
 
n, a, b, w, h = input().split(' ')
n = int(n)
a = int(a)
b = int(b)
w = int(w)
h = int(h)
left = max (min (h//n-a, w//n-b), min (h//n-b, w//n-a))
right = min(w,h)
while right - left > 1:
    mid = (left + right) // 2
    if check(mid, n, w, h, a, b):
        right = mid
    else:
        left = mid
print(left//2)

Добавлено через 15 минут

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def check(x, n, w, h, a, b):
    return (n*(x + a) <= w and n*(x + b) <= h) or (n*(x + a) <= h and n*(x + b) <= w)
 
n, a, b, w, h = input().split(' ')
n = int(n)
a = int(a)
b = int(b)
w = int(w)
h = int(h)
left = max (min (h//n-a, w//n-b), min (h//n-b, w//n-a))
right = min(w,h)
print('left=',left)
print('right=',right)
while right - left > 1:
    mid = (left + right) // 2
    if check(mid, n, w, h, a, b):
        left = mid
    else:
        right = mid
    print('left=', left)
    print('right=', right)
print(left//2)

Добавлено через 1 час 14 минут
не удаётся нормально править первое сообщение

обновлённое решение, добавил проверку на сумму площадей модулей и участка:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def check(x, n, w, h, a, b):
    return ((n*(x + a) <= w and n*(x + b) <= h) or (n*(x + a) <= h and n*(x + b) <= w)) and (n*(x+a)*(x+b)<=w*h)
 
n, a, b, w, h = input().split(' ')
n = int(n)
a = int(a)
b = int(b)
w = int(w)
h = int(h)
left = 0
right = min(w//n,h//n)
while right - left > 1:
    mid = (left + right) // 2
    if check(mid, n, w, h, a, b):
        left = mid
    else:
        right = mid
print(left//2)

@CoderPC · 08.07.2024, 12:41

semen1984, примеров то к задаче нет?

@Red white socks · 08.07.2024, 13:06

Сообщение от semen1984

Python
1
2
left = max (min (h//n-a, w//n-b), min (h//n-b, w//n-a))
right = min(w,h)

У вас алгоритм, который в самом худшем случае потребует чуть больше 50 итераций, а вы начинаете выгадывать копейки, выписывая какие-то формулы и это место вполне вероятной ошибки. Приоритет надо отдавать простоте. Особенно когда правильного решения нет.

Добавлено через 3 минуты

Сообщение от semen1984

добавил проверку на сумму площадей модулей и участка

Сообщение от semen1984

(n*(x + a) <= w and n*(x + b) <= h) or (n*(x + a) <= h and n*(x + b) <= w)) and (n*(x+a)*(x+b)<=w*h)

Последнее условие лишнее. Это следствие из предыдущих условий.

@semen1984 · 08.07.2024, 13:09 **[ТС]**

Сообщение от CoderPC

semen1984, примеров то к задаче нет?

нет, к сожалению, это очень осложняет процесс решения

Сообщение от Red white socks

У вас алгоритм, который в самом худшем случае потребует чуть больше 50 итераций, а вы начинаете выгадывать копейки и, конечно же, ошибаетесь.

да, я понимаю
с более широкими границами то же самое получается:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def check(x, n, w, h, a, b):
    return ((n*(x + a) <= w and n*(x + b) <= h) or (n*(x + a) <= h and n*(x + b) <= w)) and (n*(x+a)*(x+b)<=w*h)
    #return n*(x+a)*(x+b)<=w*h
 
n, a, b, w, h = input().split(' ')
n = int(n)
a = int(a)
b = int(b)
w = int(w)
h = int(h)
left = 0
right = max (w,h)
while right - left > 1:
    mid = (left + right) // 2
    if check(mid, n, w, h, a, b):
        left = mid
    else:
        right = mid
print(left//2)

Сообщение от Red white socks

Последнее условие лишнее. Это следствие из предыдущих условий.

Я его добавил в последний момент, чтобы корректно проверять случаи расположения модулей не в ряд и не в столбец (например, 4 модуля - 2 в ряд и 2 столбец)
Думаю, что как раз в условии проверки ошибка.

@udmurt2024 · 08.07.2024, 13:14

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def check(d, n, w, h, a, b):
    return n*(d + a)+d <= w and n*(d + b)+d <= h or n*(d + a)+d <= h and n*(d + b)+d <= w
 
n, a, b, w, h = map(int,input().split(' '))
#n, a, b, w, h = map(int,"1 2 3 4 5".split(' '))
left = 0
right = min(w,h)
while left != right:
    d = (left + right) // 2
    if check(d, n, w, h, a, b):
        if left == d:
            break
        left = d
    else:
        right = d
print(d)

@Red white socks · 08.07.2024, 13:27

Сообщение от semen1984

чтобы корректно проверять случаи расположения модулей не в ряд и не в столбец

В условии ведь

Сообщение от semen1984

Стороны модулей должны быть параллельны сторонам участка, и все модули должны быть ориентированы одинаково

Сейчас просто по математике выглядит глупо
(n*(x + a) <= w and n*(x + b) <= h) or (n*(x + a) <= h and n*(x + b) <= w)
Перемножая неравенства мы в обоих случаях получаем n*n*(x+a)*(x+b)<=w*h, что влечет и выполнение n*(x+a)*(x+b)<=w*h

semen1984, давай еще устраним слабое место: искать бинпоиском непосредственно d

Добавлено через 6 минут
И еще, в задаче не оговорен случай, когда она может не иметь решений. Может быть это упущение при цитировании и тогда это тоже надо отобразить в коде.

@semen1984 · 08.07.2024, 13:56 **[ТС]**

Сообщение от udmurt2024

def check(d, n, w, h, a, b):
return n*(d + a)+d <= w and n*(d + b)+d <= h or n*(d + a)+d <= h and n*(d + b)+d <= w
n, a, b, w, h = map(int,input().split(' '))
#n, a, b, w, h = map(int,"1 2 3 4 5".split(' '))
left = 0
right = min(w,h)
while left != right:
d = (left + right) // 2
if check(d, n, w, h, a, b):
if left == d:
break
left = d
else:
right = d
print(d)

спасибо за исправления!
но тестовая система всё равно выдаёт ошибку на 7м тесте:
N Результат Время (с) Использовано памяти (RSS) (KiB)
1 OK 0.014 9728
2 OK 0.013 9728
3 OK 0.013 9600
4 OK 0.012 9600
5 OK 0.012 9600
6 OK 0.015 9472
7 Неправильный ответ 0.043 9728

Добавлено через 6 минут

Сообщение от Red white socks

Сейчас просто по математике выглядит глупо
(n*(x + a) <= w and n*(x + b) <= h) or (n*(x + a) <= h and n*(x + b) <= w)
Перемножая неравенства мы в обоих случаях получаем n*n*(x+a)*(x+b)<=w*h, что влечет и выполнение n*(x+a)*(x+b)<=w*h
semen1984, давай еще устраним слабое место: искать бинпоиском непосредственно d
Добавлено через 6 минут
И еще, в задаче не оговорен случай, когда она может не иметь решений. Может быть это упущение при цитировании и тогда это тоже надо отобразить в коде.

Вы правильно пишете. Это я уже после десятка попыток находу нелепые исправления делаю.
В ряду может быть не n модулей, а n/2, n/3, n/4, поэтому сравнивать с использованием n тоже не корректно.
Буду думать дальше.

@CoderPC · 08.07.2024, 14:15

Сообщение от semen1984

но тестовая система

и ссылка на задачу разумеется секретная

@semen1984 · 08.07.2024, 15:17 **[ТС]**

Сообщение от CoderPC

и ссылка на задачу разумеется секретная

ссылка без авторизации не работает

прикладываю задачу в виде документа

@udmurt2024 · 08.07.2024, 15:46

Сообщение от semen1984

n,a,b,w,h (1≤n,a,b,w,h≤10^18).

комбинация этих чисел, при которой d=0, вполне допустима, но что выводить если на Луне не хватит места?

@Red white socks · 08.07.2024, 15:53

semen1984, если вообще убрать бинпоиск, решение тоже не проходит?

Python
1
d = max(min(h//n - a, w//n - b), min(h//n - b, w//n - a)) // 2

@semen1984 · 08.07.2024, 16:18 **[ТС]**

спасибо за помощь!

оказалось, что ошибка в проверке на бинарном поиске

система пропустила решение с проверкой:
(w//(2*x+a))*(h//(2*x+b)) >= n or (w//(2*x+b))*(h//(2*x+a)) >= n

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@CoderPC Заблокирован
	08.07.2024, 12:41
	semen1984, примеров то к задаче нет? 0

@semen1984 9 / 7 / 2 Регистрация: 07.05.2024 Сообщений: 75
	08.07.2024, 16:18 [ТС]
	спасибо за помощь! оказалось, что ошибка в проверке на бинарном поиске система пропустила решение с проверкой: (w//(2x+a))(h//(2x+b)) >= n or (w//(2x+b))(h//(2x+a)) >= n 0