Питон 17 .
в левом верхнем углу прямоугольной таблицы размером n×m находится черепашка. в каждой клетке таблицы записано некоторое число. черепашка может перемещаться вправо или вниз, при этом маршрут черепашки заканчивается в правом нижнем углу таблицы.
подсчитаем сумму чисел, записанных в клетках, через которую проползла черепашка (включая начальную и конечную клетку). найдите наибольшее возможное значение этой суммы и маршрут, на котором достигается эта сумма.
входные данные
в первой строке входных данных записаны два натуральных числа n и m, не превосходящих 100 — размеры таблицы. далее идет n строк, каждая из которых содержит m чисел, разделенных пробелами — описание таблицы. все числа в клетках таблицы целые и могут принимать значения от 0 до 100.
выходные данные
первая строка выходных данных содержит максимальную возможную сумму, вторая – маршрут, на котором достигается эта сумма. маршрут выводится в виде последовательности, которая должна содержать n-1 букву d, означающую передвижение вниз и m-1 букву r, означающую передвижение направо. если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.
примеры
входные данные
5 5
9 9 9 9 9
3 0 0 0 0
9 9 9 9 9
6 6 6 6 8
9 9 9 9 9
выходные данные
74
d d r r r r d d
1) N = 4
2) N = 1
Объяснение:
1) в первом случае стоит условие "пока переменная N (которая изначально равна 1) меньше или равна 5" мы умножаем данную переменную на 2, до тех пор пока она не станет больше или равна 5 , соответственно цикл завершается, когда N стала больше 5.
1 * 2 = 2, N присваивается ответ (т.е. число 2), далее 2 * 2 = 4, далее по идее программа будет делать ещё одно действие, потому что условие не достигнуто и N не равно 5, но в итоге ответ будет равен 4, потому что 4 * 2 уже получится 8, что не соответствует условию.
2) во втором такая же схема, поменялось только действие с произведения на разность
если что-то не понятно, спрашивай в комментариях :)
i,k,N : Integer;
Begin
For i:=0 to 6 do m[i]:=0;
Readln(N);
k:=6;
While N>0 do
Begin
If N>=Power(2,k) then
Begin
N:=N-Trunc(Power(2,k));
Inc(m[k]);
end else Dec(k);
end;
For i:=0 to 6 do Writeln(Power(2,i),' ',m[i],' шт.');
end.
Еще вариант:
Const
NN = 7;
money : array[1..7] of Integer = (1,2,4,8,16,32,64);
Var m : array[1..NN] of Integer;
i,k,N : Integer;
Begin
For i:=1 to NN do m[i]:=0;
Readln(N);
k:=NN;
While N>0 do
Begin
If N>=money[k] then
Begin
N:=N-money[k];
Inc(m[k]);
end else Dec(k);
end;
For i:=1 to NN do Writeln(money[i],' ',m[i],' шт.');
end.