Разбираем задачу про выпечку

Мы любим тупые бес­смыс­лен­ные задач­ки, но ещё боль­ше — когда их мож­но взло­мать и полу­чить неожи­дан­ные резуль­та­ты. Сего­дня мы сло­ма­ем одну из таких зада­чек с помо­щью СИЛЫ КОДА. 

Задача

В одном хлеб­ном мага­зин­чи­ке есть 3 сор­та було­чек. На 10 руб­лей мож­но купить либо 1 булоч­ку пер­во­го сор­та, либо две булоч­ки вто­ро­го, либо 3 булоч­ки тре­тье­го сор­та. В мага­зин зашла груп­па детей, маль­чи­ков и дево­чек поров­ну. Они сло­жи­лись и полу­чи­ли 70 руб­лей. Всю сум­му они потра­ти­ли на покуп­ку було­чек так, что­бы всем доста­лось поров­ну — и по булоч­кам, и по деньгам.

Сколь­ко было куп­ле­но було­чек и каких сор­тов, если ни одна из було­чек не была поде­ле­на на части?

Короткое решение из интернета

Любо­пыт­но, что нигде не при­во­дит­ся сам ход реше­ния, а есть толь­ко ответ: в мага­зин зашли 3 маль­чи­ка и 3 девоч­ки и купи­ли по 2 булоч­ки 3-го сор­та и по 1 булоч­ке 2-го сорта. 

Но это скуч­но и тупо: про­сто узнать ответ. Как мы его получили?

Пошаговое решение

Так как маль­чи­ков и дево­чек зашло поров­ну, то их полу­чи­лось чёт­ное коли­че­ство. Зна­чит, детей мог­ло быть 2, 4, 6, 8, 10 и так далее. Нуж­но про­ве­рить, полу­чит­ся ли раз­де­лить покуп­ки на 70 руб­лей поров­ну меж­ду детьми в каж­дой группе.

2 чело­ве­ка: им нуж­но купить про­сто чёт­ное коли­че­ство любых оди­на­ко­вых було­чек в любой комбинации:

2 пер­во­го сор­та (20 р.) и 10 вто­ро­го сор­та (50 р.) 

2 пер­во­го сор­та (20 р.), 2 вто­ро­го сор­та (10 р.) и 12 тре­тье­го сор­та (40 р.) 

2 пер­во­го сор­та (20 р.), 6 вто­ро­го сор­та (30 р.) и 6 тре­тье­го сор­та (20 р.) 

4 пер­во­го сор­та (40 р.) и 6 вто­ро­го сор­та (30 р.) 

4 пер­во­го сор­та (40 р.), 2 вто­ро­го сор­та (10 р.) и 6 тре­тье­го сор­та (20 р.) 

6 пер­во­го сор­та (60 р.) и 2 вто­ро­го сор­та (10 р.) 

14 вто­ро­го сор­та (70 р.) 

10 вто­ро­го сор­та (50 р.) и 6 тре­тье­го сор­та (20 р.) 

6 вто­ро­го сор­та (30 р.) и 12 тре­тье­го сор­та (40 р.) 

2 вто­ро­го сор­та (10 р.) и 18 тре­тье­го сор­та (60 р.) 

Вид­но, что уже в груп­пе из двух чело­век у нас 10 реше­ний. Посмот­рим, что будет дальше.

4 чело­ве­ка: усло­вия меня­ют­ся — нуж­но, что­бы коли­че­ство було­чек каж­до­го сор­та дели­лось на 4. Попро­бу­ем подобрать.

Було­чек тре­тье­го сор­та нам нуж­но 12, пото­му что 12 делит­ся на 4, а дру­гое коли­че­ство таких було­чек, кото­рое тоже делит­ся на 4, мы на 70 руб­лей не купим. Но мы тогда потра­тим на 12 було­чек 40 руб­лей, и у нас оста­ёт­ся 30. На эти день­ги мы не смо­жем подо­брать оди­на­ко­вые бул­ки так, что­бы их чис­ло дели­лось на 4. Зна­чит, тре­тье­сорт­ные булоч­ки тут не участвуют.

Було­чек вто­ро­го сор­та нам нуж­но 8 (40 руб­лей) или 4 (20 руб­лей). Но на остав­ши­е­ся 30 или 50 руб­лей мы можем купить толь­ко 3 или 5 було­чек пер­во­го сор­та, а это тоже не делит­ся на 4. Зна­чит, вто­рой сорт тоже мимо.

Но на 70 руб­лей мы можем купить толь­ко 7 булок пер­во­го сор­та, а это не делит­ся на 4. Зна­чит, детей было не четверо.

6 чело­век: то же самое — под­би­ра­ем булоч­ки так, что­бы они дели­лись на 6, и начи­на­ем сно­ва с самых дешёвых.

Було­чек тре­тье­го сор­та нам нуж­но 6, 12 или 18. Если их будет 6 (20 р.), то у нас оста­ёт­ся 50 р., а на них мы не смо­жем набрать булок пер­во­го и вто­ро­го сор­та так, что­бы каж­дое из них дели­лось на 6. Если було­чек тре­тье­го сор­та будет 12 (40 р.), то у нас оста­ёт­ся 30 р. как раз на 6 було­чек вто­ро­го сор­та. Полу­ча­ем то самое реше­ние, кото­рое все при­во­дят как един­ствен­но правильное:

12 тре­тье­го сор­та (40 р.) и 6 вто­ро­го сор­та (30 р.)

Если у нас будет 18 булок тре­тье­го сор­та (60 р.), то на остав­ши­е­ся 10 руб­лей мы купим толь­ко 1 или 2 бул­ки, а это нас не устроит.

Допу­стим, булок тре­тье­го сор­та нам не нуж­но, и тогда нам пона­до­бит­ся 6 булок вто­ро­го сор­та (30 р.) или 12 булок вто­ро­го сор­та (60 р.). Пер­вый слу­чай мы толь­ко что разо­бра­ли, а во вто­ром на 10 руб­лей мы не смо­жем купить дру­гих оди­на­ко­вых булок так, что­бы их чис­ло дели­лось на 6. 

С бул­ка­ми пер­во­го сор­та всё про­сто — 7 булок на 6 не делится.

Далее мы можем в той же логи­ке пере­би­рать все воз­мож­ные ком­би­на­ции булок и детей, начи­ная с самых дешё­вых. У нас есть общий дели­тель (8, 10 и т. д.), понят­ный бюд­жет и цены. Про­сто берём и перебираем.

Стоп! Мы пере­би­ра­ем? А како­го рож­на мы пере­би­ра­ем вручную?

Программистское решение

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

Смысл будет такой:

  1. Мы по оче­ре­ди пере­би­ра­ем все чёт­ные коли­че­ства детей, кото­рые зашли в магазин.
  2. Пере­би­ра­ем все воз­мож­ные покуп­ки булочек.
  3. Если полу­чив­ша­я­ся сум­ма нас устра­и­ва­ет, то дела­ем про­вер­ку: если коли­че­ство було­чек каж­до­го сор­та без остат­ка делит­ся на общее коли­че­ство детей, то выво­дим это как ответ и про­дол­жа­ем даль­ше, пока не закон­чит­ся перебор.

Что­бы хоть как-то огра­ни­чить коли­че­ство детей, кото­рые при­дут в мага­зин, узна­ем самое боль­шое коли­че­ство було­чек, кото­рое мож­но купить на 70 руб­лей. Если даже мы возь­мём на все день­ги 7 ком­плек­тов було­чек тре­тье­го сор­та, то это полу­чит­ся 21 булоч­ка. Если делить по одной на каж­до­го, полу­чим 21 чело­век — это и будет верх­няя гра­ни­ца цик­ла. Мы пом­ним, что 21 — это нечёт­ное чис­ло, но чёт­ность мы про­ве­рим в дру­гом месте. 

Для пере­бо­ра було­чек будем счи­тать ком­плек­ты, а не сто­и­мость. Один ком­плект — 10 руб­лей, на кото­рый мож­но купить одну, две или три булоч­ки сво­е­го сор­та. Полу­ча­ет­ся, что мак­си­мум на 70 руб­лей мож­но взять 7 ком­плек­тов — это и возь­мём для гра­ни­цы пере­бо­ра по коли­че­ству булочек.

Теперь у нас есть всё, что нуж­но для кода:

// переменные для булочек и для количества детей	
var a,b,c;
var i;

// ограничиваем цикл максимальным количеством возможных булочек — 21
for (i = 1; i <= 21; i++){
	// если число детей чётное, то продолжаем
	if (i % 2 == 0){

		// на 70 рублей можно максимум купить по 7 наборов булочек каждого сорта
		for (a = 0; a <= 7; a++ ){
			for (b = 0; b <= 7; b++){
				for (c = 0; c <= 7; c++){

					// если наборов 7, (7 наборов по 10 рублей = 70), то продолжаем
					if (a + b + c == 7){

						// если количество булочек каждого сорта поровну делится на количество детей — выводим каждое найденное такое решение
						if ((a % i == 0) && ((b * 2) % i == 0) && ((c * 3) % i == 0) ){
							console.log(i + " человека: на каждого " + a + " булочек 1-го сорта," + b + " булочек 2-го сорта и " + c + " булочек 3-го сорта");
						}
						
					}	
				}
			}
		}
	}	
}

Если выпол­нить этот код в кон­со­ли бра­у­зе­ра, то сра­зу уви­дим отве­ты — 2, 6 и 14 детей. Пере­бор — это сила.

Итого

Полу­ча­ет­ся, что у зада­чи не одно пра­виль­ное реше­ние, как все гово­рят, а целых две­на­дцать: десять реше­ний для дво­их детей и по одно­му реше­нию для шесте­рых и четырнадцати.

Текст и код:
Миша Поля­нин

Редак­тор:
Мак­сим Ильяхов

Худож­ник:
Даня Бер­ков­ский

Кор­рек­тор:
Ира Михе­е­ва

Вёрст­ка:
Маша Дро­но­ва

Соц­се­ти:
Олег Веш­кур­цев