e-olymp 2061. Юные программисты

Задача 

Известно, что в школе не менее чем $k_{1}$учеников, но не более чем $k_{2}$ учеников. Также известно, что каждый мальчик дружит с $n$ девочками, а каждая девочка с $m$ мальчиками. Какое минимальное количество учеников может быть в школе, и сколько в школе мальчиков и девочек?

Юные программисты, как Вы видите, до сих пор решают эту задачку. Помогите им.

Входные данные

В первой строке входного файла находится $4$ числа, разделённых пробелами: $k_{1}$, $k_{2}$, $n$ и $m$. Все входные данные натуральные числа, не превышающие $10000$, $k_{1}\leq k_{2}$.

Выходные данные

В единственной строке вывести через пробел три числа: сначала количество учеников в школе, потом количество мальчиков и затем девочек. Гарантируется, что входные данные корректны и ответ всегда существует.

Тесты

Входные данные Выходные данные
20 30 4 5 27 15 12
5 10000 54 44 98 44 54
1 10000 100 100 200 100 100
1 2 1 1 2 1 1
100 120 2 3 100 60 40
50 50 25 25 50 25 25
9900 10000 99 56 9920 3584 6336
9999 10000 9998 2 10000 2 9998
101 110 2 3 105 63 42

Решение

Объяснение 

Решение основано на достаточно простой идее перебора всех вариантов количества мальчиков и количества девочек и нахождения наименьшего из них, удовлетворяющего условию. Для этого создаётся два цикла, внешний из которых отвечает за переменную мальчиков, а внутренний— за переменную девочек.  Внутреннее условие находит минимальное количество учеников в классе.

e-olymp

ideone

4 thoughts on “e-olymp 2061. Юные программисты

    • Вы пишите «Внутреннее условие фильтрует варианты, оставляя наименьшие верные.» Мне кажется это слишком запутанная формулировка для поиска минимума. Тем более, что «фильтр» и множественное число подразумевают несколько значений. А у Вас только одно.
    • Пожалуйста, уберите двоеточие в заголовках. Только не поленитесь посмотреть на Википедии, что такое двоеточие и когда оно используется. Тогда будет понимание, а не просто подчинение требованиям.

    Я когда-то это задачу на скорую руку сдал даже без использования k2. Возможно оно защло из-зи неполных тестов? Можете предложить тест, где Ваше решение работает, а моё нет?

    • Спасибо, формулировку изменил.
      Я ставил двоеточие потому, что думал, что данные слова являются обобщающими. Но да, теперь понял, что это просто заголовки.
      Тест искал, но не нашёл. Могу разве что отметить, что мой вариант ещё умеет находить количество учеников для класса только из мальчиков или только из девочек ($n=0$ или $m=0$), что, правда, не входит в область определения, заданную условием, так что достаточно бесполезно. Ещё при других вариантах неверного условия, мой вариант выдаёт «0 0 0», а не наименьшее после $k_{1}$ значение. Хотя, да, опять же, в контексте решения задачи, где гарантируется наличие правильного ответа, это абсолютно не нужно. В остальном, то есть при $k_{1}$, $k_{2}$,$n$, $m$, допускаемых условием задачи, ответы сходились. Проверял простым перебором, и такой не очень хитрой программкой.

      • Вместо всего выше перечисленного, что сводится к эмпирической работе с черным ящиком, полезнее будет осознать алгоритм, предложенный Игорем Евгеньевичем и подумать, должен ли он работать и если нет, то почему. И если да, то почему? И еще над тем, зачем он предложил свое решение, если Ваше тоже работает.

Добавить комментарий