С едно уточнение, че говорим за бик, а не за вол (вол+крава=бивол), продължавам с разсъжденията на математик, кадър на СМГ И ФМИ:
Ето логиката, по която аз стигнах до решението:
- почваме от 100 телета
- тъй като сумата от трите типа говедо
трябва да е 100, а всяка сума от бикове и крави е кратна на 5 лв. излиза, че и сумата на телетата трябва да е кратна на 5 (иначе няма как общия сбор да се допълни до 100 лв.)
- следователно телетата вървят на пакети по 5 лв. (10 броя)
- следователно за всяка десятка телета която махнем, трябва да заместим с комбинация от 10 крави и бика
- всяка комбинация от 10 крави и бика струва от 50 лв. (10 крави и 0 бика) до 100 лв. (0 крави и 10 бика), като очевидно има точно по една комбинация за всяка сума в този диапазон (50 лв. + (5 лв. * брой бикове) )
- следователно ако извадим от 100-те телета 20 или повече и прибавим съответния брой крави и бикове, то добавяме поне 100 лв. (мин. 20 крави) към оставащия брой телета, което директно надхвърля зададената обща сума от 100 лв.
- следователно може да махнем само едня десятка телета
- оставаме с 45 лв. за телета
- следователно комбинираната ни десятка крави и бикове трябва да струва 55 лв., или 9 крави и 1 бик (няма друга комбинация).
- това е единствено решение (ако имаме по-малко от 90 телета, няма да можем да запълним броя от 100 говеда)
Абе хора, brute force-а е за по-малоумно
В този ред на мисли всеки проблем в него е добре дошъл.
Замислям се даже защо не пуснах и трите цикъла до 100 (или 100 000?), ей така просто да се използва CPU time пълноценно. Лошото е, че сложността по памет е обидно ниска. Дали да не обявим конкурс за най-недъгав алгоритъм за тая задачка?
----------------------------------
Тука няма смисъл от 3-ти цикъл май? Защото в уравнението calves може да се сметне като имаме bulls и cows
----------------------------------
Цъ цъ цъ, пълна липса на въображение... Далеч по-елегантно е с brute force, пък и така откриваме всички евентуални решения :O)
for (int bulls = 0; bulls < 10; ++bulls) {
for (int cows = 0; cows < 20; ++cows) {
for (int calves = 0; calves < 200; ++calves) {
if (10 * bulls + 5 * cows + 0.5f * calves == 100 && bulls + cows + calves == 100) {
Console.WriteLine("{0} {1} {2}", bulls, cows, calves);
}
}
}
}
------------------------------
Объркал си задачата. Задачата не е с волове, а с бикове....
И понеже в едно стадо нужда от повече от един бик няма => бикът е един.
Оттам нататък е лесно.
1 - бик
X – крави
100 –(х+1) – телета
10.1 + 5.х + 0,5.(100 – х – 1) = 100
Елементарно уравнение с 1 неизвестно....
Крави 9, телета 90....
Дечицата това наум го смятат.....
-------------------------------------
Така, brute force-ът е подходящо решение, но трябва да се прилага по по-елегантен начин. Трябва да се слагат ограничения.
Така например лесно можем да проверим, че воловете (или биковете) не трябва да са повече от 4, кравите не повече от 9 и т.н.
А най-лесният вариант е да сведем задачата до следното уравнение:
y = (100 – 19x)/9
x – волове
y – крави
И така правим
for (int x=1; x<=4; ++x) {
y = (100 – 19x)/9;
// ако y е цяло, прекъсваме
}
За 4ти клас толкоз. Аз така ги решавах тогава. ;-P
Вход
Регистрация
Галерия
FAQ
Айде кажете колко са.
