Задача
Известно, что в школе не менее чем $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 |
Решение
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> using namespace std; int main() { int k1, k2, m, n; int x = 0, y = 0, M = 10001; //x-мальчики, y-девочки, M- минимальное из вариантов количества учеников (10001 сначала, чтобы первый раз прошло условие внутри цикла) cin >> k1 >> k2 >> n >> m; for(int i = 0; i <= k2; i++){ for(int j = k1-i; j <= k2; j++){ //j=k1-i, так как сумма i+j должна быть хотя бы k1. Рассматривать варианты меньше, смысла не имеет /* M>i+j— если сумма меньше предыдущего из меньших, то перезаписываем переменные, если больше- пропускаем. i*j== количество дружащих пар. k1<=i+j — общее число учеников должно быть больше или равно k1 и меньше, либо равно k2 (i+j<=k2). Количество мальчиков в классе должно быть больше либо равно количеству, которое требуется девочкам для дружбы (i>=m), аналогично с девочками (i>=n)*/ if(M > i + j && i * n == j * m && k1 <= i + j && i + j <= k2 && i>=m && j>=n){ x = i; y = j; M = i+j; } } } cout<< x + y << " " << x << " " << y << endl; return 0; } |
Объяснение
Решение основано на достаточно простой идее перебора всех вариантов количества мальчиков и количества девочек и нахождения наименьшего из них, удовлетворяющего условию. Для этого создаётся два цикла, внешний из которых отвечает за переменную мальчиков, а внутренний— за переменную девочек. Внутреннее условие находит минимальное количество учеников в классе.
Я когда-то это задачу на скорую руку сдал даже без использования k2. Возможно оно защло из-зи неполных тестов? Можете предложить тест, где Ваше решение работает, а моё нет?
Спасибо, формулировку изменил.
Я ставил двоеточие потому, что думал, что данные слова являются обобщающими. Но да, теперь понял, что это просто заголовки.
Тест искал, но не нашёл. Могу разве что отметить, что мой вариант ещё умеет находить количество учеников для класса только из мальчиков или только из девочек ($n=0$ или $m=0$), что, правда, не входит в область определения, заданную условием, так что достаточно бесполезно. Ещё при других вариантах неверного условия, мой вариант выдаёт «0 0 0», а не наименьшее после $k_{1}$ значение. Хотя, да, опять же, в контексте решения задачи, где гарантируется наличие правильного ответа, это абсолютно не нужно. В остальном, то есть при $k_{1}$, $k_{2}$,$n$, $m$, допускаемых условием задачи, ответы сходились. Проверял простым перебором, и такой не очень хитрой программкой.
Вместо всего выше перечисленного, что сводится к эмпирической работе с черным ящиком, полезнее будет осознать алгоритм, предложенный Игорем Евгеньевичем и подумать, должен ли он работать и если нет, то почему. И если да, то почему? И еще над тем, зачем он предложил свое решение, если Ваше тоже работает.
В порядке челленджа более высокого порядка могу предложить всем неравнодушным решить данную задачу при ограничениях 1e18.