Как нужно разместить полки для наилучшей защиты замка?

@Антон Ф · Регистрация: 17.07.2019

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

Условие:
Замок имеет форму большого квадрата, составленного из N × N маленьких квадратиков. Внешние квадратики являются башнями, именно они играют основную роль в защите замка от неприятеля. Например, если замок имеет размер 4 × 4, то у него 12 башен (смотрите второй рисунок, башни на нем выделены серым цветом).

Замок охраняют K полков, которые необходимо разместить по башням. В одной башне можно разместить несколько полков, но при этом в каждой башне должен находиться хотя бы один полк, иначе неприятель легко захватит эту башню. Если все башни защищены, то неприятель выбирает для атаки одну из четырех сторон замка, которую защищает наименьшее число полков (то есть суммарное число полков во всех башнях данной стороны квадрата минимально).

Определите, как нужно разместить полки для наилучшей защиты замка.
Я попытался решить эту задачу, посмотрел материал в Инете, но код прошёл не все тесты:

Python
1
2
3
4
5
6
n = int(input())
k = int(input())
z = n * n
d = (n - 2) * (n - 2)
b = z - d
print(n+(k-b)//2)

Код я писал пытаясь реализовать такое решение (ответы mail.ru):
Можно по размеру замка узнать количество башен. Для этого из площади замка вычитаем площадь внутреннего двора (квадрат со стороной N - 2).
Замок := N * N
Двор := (N - 2) * (N - 2)
Башни := Замок - Двор

Количество полков K должно быть не меньше количества башен: K >= Башни. Иначе полков не хватит на все башни; жалуемся на несоблюдение условий и завершаем работу.

Первым делом надо разместить в каждой башне по одному полку. Осталось меньше полков: K - Башни.
Сейчас с каждой стороны замка сидит ровно N полков: Охрана = N

Как наиболее эффективно оборонять все стены? Два варианта:
1) поместить полк на стене между углами - тогда один полк будет охранять только одну сторону. Не очень;
2) поместить полк в угловой башне - тогда он будет охранять сразу две стены. Замечательно!

А два полка в противоположных углах будут охранять сразу все стороны. По сути, будет Охрана = N + 1.
Третий полк в углу еще усилит охрану, но только с двух сторон (по-прежнему Охрана = N + 1).
Зато четвертый, напротив третьего, будет охранять оставшиеся две стороны (Охрана = N + 2).

Мы видим простую закономерность: каждые два полка сверх числа башен увеличивают качество охраны на 1 сверх исходного количества полков N с каждой стороны замка.

Таким образом, получаем простую формулу: Охрана := N + (K - Башни) div 2

Я даже понял откуда что берётся в текстовом решении, но переписать на питон не могу

@codcw · 03.03.2020, 20:48

если необязательно равномерно размещать полки сверх тех, которые в каждой клетке - просто раскидать все оставшиеся по углам, только непонятно что нужно сделать, какие выходные данные?

@u235 · 03.03.2020, 22:18

codcw, да, причем достаточно в не в четырех, а в двух, напротив друг друга.
Видимо на выходе нужно число защитников самой слабой стены.. Но ТС виднее..
Кстати:

Python
1
b=4*(n-1)

@Антон Ф · 06.03.2020, 18:08 **[ТС]**

Выходные данные
Выведите единственное число — количество полков на наименее укрепленной стороне замка при наилучшем размещении полков. Если имеющихся полков недостаточно для защиты всех башен, выведите число 0.

Добавлено через 24 минуты
Я идиот тупорылый, в этой задаче можно и нужно if юзать (я просто не учёл что башен может быть больше чем полков

и на это указано в выходных данных):

Python
1
2
3
4
5
6
7
8
9
n = int(input())
k = int(input())
z = n * n
d = (n - 2) * (n - 2)
b = z-d
if b > k:
  print(0)
else:
  print(n+(k-b)//2)

Добавлено через 30 секунд
Если что, Сириус оно прошло

Добавлено через 9 секунд

@u235 · 06.03.2020, 20:12

Не по теме:

Вы молодец! Похоже едиственный тут из участников кто решил все самостоятельно. Удачи!

Новые блоги и статьи Все статьи Все блоги /
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ

@codcw 815 / 527 / 214 Регистрация: 22.12.2017 Сообщений: 1,495
	03.03.2020, 20:48
	если необязательно равномерно размещать полки сверх тех, которые в каждой клетке - просто раскидать все оставшиеся по углам, только непонятно что нужно сделать, какие выходные данные? 0

@u235 5519 / 2872 / 571 Регистрация: 07.11.2019 Сообщений: 4,762
	06.03.2020, 20:12
	Не по теме: Вы молодец! Похоже едиственный тут из участников кто решил все самостоятельно. Удачи! 1