Задачка с олимпиады, как решать?

Question

[Герман Шестак]

Доброго времени суток. Первый раз за 16 лет участвую в олимпиаде по информатике от мехмата.. Вопросы с первой же задачкой, информатик сказал, что там "3 цикла " - и всё))
Как не подхожу к вопросу - не могу понять, как считать-то? Не требую решения, просто натолкните на мысль пожалуйста.
Вот условие, сокращенно.
185 студентов заказывают маршрутки. Есть на 16, 17, 21 место. При заказе маршрутки все места должны быть заняты. Найдите все варианты заказа.

Comments

[Ivan Bogachev]

При чем тут в тегах вопроса нода и питон?

[Герман Шестак]

Ivan Bogachev, а что поставить-то?)

Answer 1

[Saboteur]

ну?
так задачка на три цикла.
Крутите три цикла, делаете перебор всех вариантов.

while marshrutka16
  while marshrutka17
    while marshrutka21
      if (185-16*marshrutka16-17*marshrutka17-21*marshrutka21==0) then print 'this variant is fine';

И крутите каждый цикл от нуля до 185/размер маршрутки

Comments

[Герман Шестак]

Хм.. логично, всё никак не мог представить это вообще))
А marshrutkaXX - какое значение имеет?

[Герман Шестак]

А всё, дошло

[Saboteur]

Герман Шестак, ну хоть лайк поставьте =)

Answer 2

[longclaps]

Хех, ниасиливает тостер динамическое программирование.

n = 185
dp = [1] + [0] * n
for cap in 16, 17, 21:
    for i in range(n - cap, -1, -1):
        for j in range(i + cap, n + 1, cap):
            dp[j] += dp[i]
print(dp[n])

UPDATE

Найдите все варианты заказа.

а я только подсчитал их

n = 185
dp = [['']] + [[] for _ in range(n)]
for cap in 16, 17, 21:
    for i in range(n - cap, -1, -1):
        for seed in dp[i]:
            for j in range(i + cap, n + 1, cap):
                dp[j].append(f"{(seed + ' + ') if seed else ''}{cap}*{(j - i) // cap}")
print(*dp[n], sep='\n')

Comments

[Герман Шестак]

Почитал статей, но что-то плохо понимаю
Можешь написать простой код, слишком красивый у тебя и трудный для моего понимания))

[longclaps]

Герман Шестак, ты думаешь, что я за минуту всё растолкую лучше, чем статьи из топа выдачи гугла? Ты мне льстишь ) Читай еще. Экспериментируй с кодом, смотри что происходит на разных шагах.

Answer 3

[Ivan Bogachev]

185 = 16A + 17B + 21C, где A, B, C - целые.
Несложно сообразить также то, что A, B, C - ограничены сверху.
Далее можно хоть тупым перебором перебрать все возможные варианты - те самые "3 цикла", о которых говорит ваш информатик - и понять, сколько раз равенство будет верным.

P.S.: Мне кажется, что в таком виде - это не мехмат, это средняя школа.

Answer 4

[Дмитрий]

На олимпиаде по Мехмату - перебором?! Тут уж как в анекдоте "такие инженеры нам ... не нужны". А если бы в задаче было условие эвакуировать население Кипра (до миллиона человек) тремя дюжинами кораблей (до 500 пассажиров каждый) - тоже бы решали перебором?

просто натолкните на мысль

линейное диофантово уравнение с тремя неизвестными

UPD:
Прошу прощения: невнимателен - олимпиада "по информатике от мехмата" - видимо предполагалось решать именно перебором в циклах... негодую, но неправ (хотя ответ свой пока оставлю)