Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.222.69.152] |
|
Сообщ.
#1
,
|
|
|
Всем хай! Сходу к делу!
Условие задачи следующее: на берегу океана сидят и курят жуки и пауки, у которых вместе N ног. У каждого жука по 6 ног, а паука - 8 ног. Известно, что ног у всех жуков в К раз меньше, чем у всех пауков. Сколько всего жуков и пауков находится на берегу океана? N и К - натуральные числа. Если решений нет - выдать ответ ноль. строим мат.модель! х - кол-во жуков, y - кол-во пауков 6х - всего ног у всех жуков 8y - всего ног у всех пауков 6x + 8y = N (1 необходимое условие) 6x * K = 8y (2 необходимое условие) 6x + 6x*K = N 6x(1 + K) = N x = N / (6 + 6K) все, ГОТОВО. Данное уравнение имеет однозначное решение (если будет натуральное Х) иначе - нет решения. Проверим, пусть N = 360, K = 2. x = 360 / (6*3) = 360 / 18 = 20 y = 6*20*2/8 = 30 Итого: 20 + 30 = 50 но есть одно НО(!), нужно решить задачу МЕТОДОМ ПОЛНОГО ПЕРЕБОРА. Что перебирать? ну, наверное {x, y}. Какие допустимые значения перебора х и y? Очевидно, что X(min) = Y(min) = 1. Нужно делать оценку допустимости X(max), Y(max). X(max) будет макс. при минимальном Y = 1. 6*X(max) + 8 = N X(max) <= (N - 8)/6 - берем ближайшее натуральное снизу. Y(max) будем макс. при минимальном X = 1. 6 + 8*Y(max) = N Y(max) <= (N - 6)/8 - берем ближайшее натуральное снизу. В итоге получаются такие переборы, да? for(x = 1 to X(max)) for(y = 1 to Y(max)) здесь подставляем текущие {x; y} в ОБА условия. Если выполнилось - ответ найден. Дальше можно не проверять, т к решение единственное (если оно есть) но есть еще одно НО(!), при возможности, нужно сократить варианты переборов (не до единственного). и вот у меня вопрос, здесь за счет чего варианты перебора можно сократить?? добавить в эти циклы проверку for(x = 1 to X(max)) for(y = 1 to Y(max)) if(6x * K != 8Y) // дальше не считаем но вроде это НЕ сокращает варианты перебора...значения x, y также бегают от 1 до (max). Очень простая задача с очень странными требованиями решения через полный перебор, да, понимаю) подскажите как быть-то |
Сообщ.
#2
,
|
|
|
Ну, к примеру, можешь перебрать все возможные количества жуков, от нуля и до того, как число ног у жуков будет больше N.
Далее подсчитываешь число ног жуков и пауков (6x и 6x*K) и сравниваешь их сумму с N. В принципе, если на этот момент суммарное число ног превысит N, то задача не сходится. И кстати, в твоём решении незачем брать натуральные снизу. Если задача решается, значит все частные ОБЯЗАНЫ быть целыми. Ну и N должно нацело делиться на 6*(K + 1) |
Сообщ.
#3
,
|
|
|
Цитата amk @ к примеру, можешь перебрать все возможные количества жуков, от нуля и до того, как число ног у жуков будет больше N. я, кажись, понял, да, действительно, достаточно запустить лишь цикл по одним насекомым, а вторых искать в зависимости от первых... только НЕ от НУЛЯ, а от 1, т к кол-во ног насекомых - натуральные...ноги1 * K = ноги2 Цитата amk @ Если задача решается, значит все частные ОБЯЗАНЫ быть целыми. да, согласен, дробные "ноги" не рассматриваем, хотя еще подумаю потщательнее этот момент... Цитата amk @ Ну и N должно нацело делиться на 6*(K + 1) это я закладывал и понимаю, просто не стал писать, т к это не влияет на кол-во переборов, просто, если не делится, то сразу ответ 0. в общем, вроде понятно, спс amk! P.S. еще были мысли, что нужно что-то мутить с разложением на простые делители N, K и пр., но ведать не придется, ну и хорошо! Добавлено вот прожка на с++, вроде все ОКейно! #include <iostream> using namespace std; int main(void) { long long K, N; long long result = 0; cin >> N >> K; if(N % (6*K + 6) == 0) { // наличие хотя бы одного жука и 1 паука гарантировано for(long long x = 1; 6*x + 8 <= N; x++) if((6*x + 6*x*K) == N) { result = x + 6*x*K/8; break; } } cout << endl << result << endl; fflush(stdin); cin.get(); return 0; } т е предельное число переборов составляет (N - 8)/6. Кстати, N может на входе достигать 100 миллионов...(100 млн - 8)/6 примерно 11.5 млн переборов. Много это или мало, а черт его знает...но кажется, что многовато и нужна еще какая-то оптимизация. |
Сообщ.
#4
,
|
|
|
Цитата FasterHarder @ // наличие хотя бы одного жука и 1 паука гарантировано Для этого достаточно ненулевого K. Если жуков ноль - К не существует (деление на ноль), если пауков ноль, то К=0. При условии, что решение существует, конечно... |
Сообщ.
#5
,
|
|
|
тут с К все ок
из условия следует, что x, y, K - натуральные числа вот, что делать с 11.5 милл.переборов (в худшем случае), хотя может это и не критично. Прогнал проггу на десятках миллионах N, результат появился сразу (там что-то получилось насекомых 235 000). |
Сообщ.
#6
,
|
|
|
Да я вообще не понимаю твоей заморочки по оптимизации учебной задачи с жёстко фиксированным (применение которого в данном конкретном случае есть явный [censored]) алгоритмом.
|