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

Доброго времени суток. Первый раз за 16 лет участвую в олимпиаде по информатике от мехмата.. Вопросы с первой же задачкой, информатик сказал, что там "3 цикла " - и всё))
Как не подхожу к вопросу - не могу понять, как считать-то? Не требую решения, просто натолкните на мысль пожалуйста.
Вот условие, сокращенно.
185 студентов заказывают маршрутки. Есть на 16, 17, 21 место. При заказе маршрутки все места должны быть заняты. Найдите все варианты заказа.
  • Вопрос задан
  • 680 просмотров
Решения вопроса 2
saboteur_kiev
@saboteur_kiev Куратор тега Python
software engineer
ну?
так задачка на три цикла.
Крутите три цикла, делаете перебор всех вариантов.
while marshrutka16
  while marshrutka17
    while marshrutka21
      if (185-16*marshrutka16-17*marshrutka17-21*marshrutka21==0) then print 'this variant is fine';


И крутите каждый цикл от нуля до 185/размер маршрутки
Ответ написан
longclaps
@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')
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
sfi0zy
@sfi0zy Куратор тега JavaScript
Creative frontend developer
185 = 16A + 17B + 21C, где A, B, C - целые.
Несложно сообразить также то, что A, B, C - ограничены сверху.
Далее можно хоть тупым перебором перебрать все возможные варианты - те самые "3 цикла", о которых говорит ваш информатик - и понять, сколько раз равенство будет верным.

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

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы