Задача
Известно, что в школе не менее чем $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; } |
Объяснение
Решение основано на достаточно простой идее перебора всех вариантов количества мальчиков и количества девочек и нахождения наименьшего из них, удовлетворяющего условию. Для этого создаётся два цикла, внешний из которых отвечает за переменную мальчиков, а внутренний— за переменную девочек. Внутреннее условие находит минимальное количество учеников в классе.