Мина доста време, да кажа набързо, как става "само със събиране".
Много прилича на
"Задача 79", но допълнително се вмъква и броене.
Имаме таблица 11х11
В началното положение сме в най-долния ляв ъгъл.
Като дойде купувач с 1 лев, се придвижваме една позиция нагоре, а като дойде такъв с 2 лева, се придвижваме една позиция надясно.
Независимо от реда на купувачите, винаги стигаме в горния десен ъгъл на таблицата, като според конретната наредба на купувачите нашето придвижване в таблицата описва някакъв път.
Дотук всичко е като в "Задача 79".
За да намерим търсената вероятност, трябва да успеем да преброим всичките възможни пътища в таблицата, които не "падат" под диагонала (ако падне, значи до момента са дошли повече купувачи с 2 лв, откоркото са минали с 1 лв). Тия пътища ще ги нарека "безпроблемните".
Нека за момент си представим, че във всяка клетка по диагонала и над диагонала е записан броя на безпроблемните пътища по които може да се стигне до тая клетка.
Сега трябва да съобразим следните три неща:
1. Очевидно, в най-лявата колона е записано числото 1, защото до всяка клетка в тази колона може да се стигне по един единствен път (т.е., идвали са само купувачи с 1 лев). В тая конкретна колона, всичките пътища са безпроблемни така или иначе. А какво ще запишем в най-долната клетка на тая колона е въпрос на дефиниция. На мен ми изглежда най-естествено там да запишем 0, а не 1.
2. В клетките по диагонала пише същото което пише в клетка отляво до тях (с изключение на най-долната лява където вече приех, че ще е 0). Защо ? Защото търсим само безпроблемните пътища, а те "идват" отляво. Ако дойдат отдолу, значи не са безпроблемни.
3. В клетките които са над диагонала и не са в най-лявата колона трябва да пише сумата на клетката отляво и клетката отдолу (това по принцип са всичките пътища до тая клетка - или ще се "дойде" в тая клетка отдолу, или ще е от ляво).
Тия съображения от 1 до 3, ни дават простичък алгоритъм, чрез който на ръка можем набързо да пресметнем броя на безпроблемните пътища за клетките над диагонала в таблицата. Започваме отдолу и отляво и клетка по клетка сумираме.
При таблица 11х11 и само със събиране за около 5 минути стигаме до най-горния десен ъгъл на таблицата и на практика сме изчислили общия брой безпроблемни пътища, което всъщност ни трябва.
ПП 1.
Най-важното е съображение 2. То ни гарантира че през цялото време броим само безпроблемните пътища.
ПП 2.
В Задача 79 се "движим" по решетката, а тук по клетките - все тая, реших да е по клетките, защото е по-прегледно (според мен) да пишем цифрите вътре в клетките, е не по рамката. И затова табличката е 11х11 а не 10х10.
А също така, там решетката е завъртяна на 45 градуса, но това няма никакво значение - просто на мен ми е по-лесно да описвам алгоритъма за "права" таблица, отколкото за завъртяна решетка.
ПП 3.
Хе-хе, никой не забеляза грубата грешка в Съображение 1.
Поправих я вече, не я търсете.
А също така, направих и картинка
сървър
