Задачи за тренинг

Задача 9а. [8.2.1, стр.459]
В един склад имало n вида стоки в ограничени количества. За всяка стока се знае: цената ci и теглото wi на една продуктова единица. Задачата е да натовари камион с дадена товароносимост m със стоки от склада с най-голяма възможна цена. Обемът на стоките може да бъде пренебрегнат. 

Вход:
На входа най-напред се задават числата n и m - видове стоки и товароносимостта на камиона. На следващите n реда са дадени брой продуктови единици, тегло wi и стойност ci на една продуктова единица от съответния вид стока. Всички числа са цели в интервала [1, 100]. Входът съдържа много примери.
.
Изход:

Отпечатва се максималната стойност за натоварените на камиона стоки - за всеки пример на отделен ред.

Пример:
3 10
4 1 10
3 4 20
2 5 30

Решение на примера:
70

Пояснение на примера: В склада има 3 вида стоки (n = 3), а товароносимостта на камиона е 10 (m = 10). От първия вид стока в склада има 4 продуктови единици, всяка с тегло 1 (w1 = 1) и стойност 10 (c1 = 10), от втория вид - 3 продуктови единици с тегло 4 (w2 = 4) и стойност 20 (c2 = 20) и от третия вид - 2 продуктови единици с тегло 5 (w3 = 5) и стойност 30 (c3 = 30). Оптималното решение се получава от 4 продуктови единици от първия вид стока и една от третия вид, общо тегло 4х1 + 1х5 = 9 и стойност 4х10 + 1х30 = 70. 
Задача 9b. Зайче в беда

Веднъж малкото бяло зайче, гонено от един ловец попаднало в лабиринт, които имал форма на квадратна дъска N x N. В него чакал големия лош вълк, които предварително изкопал дупки, където зайчето да падне и той да го хване по-лесно. В последния момент зайчето с ужас разбрало, че може да се движи само в посока надолу и надясно и че изхода от лабиринта е чак в долния десен ъгъл на дъската.

Зайчето трябвало да разбере каква е вероятността да излезе от лабиринта без да падне в някоя дупка. За целта трябвало да изчисли броя пътища от входа до изхода на лабиринта, като успяло да се снабди с картата на този лабиринт. Картата е зададена с размер N, като местата на дупките са означени с 0, а проходимите места с 1. Напишете програма, която пресмята търсения брой пътища.

Вход:
На входа се задава числото N < 100 - размерът на дъската и матрица с единици и нули. Входът съдържа много примери.

Изход:

За всеки пример на отделен ред се отпечатва цяло число - търсения брой пътища.

Пример:
2
1 1
1 1
3
1 0 1
1 0 1
1 1 1
2
0 1
1 1

Решение на примера:
2
1
0