ОЛІМПІАДА З ІНФОРМАТИКИ

Задача «Буратіно»

 Стародавній замок має форму квадрата і містить NхN кімнат. У кожній кімнаті розставлені скриньки із золотими монетами. Буратіно знаходиться у верхній лівій кімнаті і мріє, зібравши якомого більше монет, добратися до правої нижньої кімнати. З кожної кімнати він може перейти до сусідньої знизу або сусідньої праворуч. Буратіно також хоче запам’ятати маршрут, який він пройде. Допоможіть Буратіно.

Формат вхідних даних: у першому рядку файла Input.txt знаходиться одне число  N( N від 1 до 30). В кожному і-тому з наступних N рядків знаходиться N чисел, що визначають кількість монет у кімнаті (i, j ).

Формат вихідних даних: ваша программа повинна виводити у перший рядок файла Output.txt одне ціле число- кількість монет, яку вдалося зібрати Буратіно. У другому рядку – маршрут- номери кімнат, у яких побував Буратіно, починаючи з кімнати (1,1, і закінчуючи  ( N, N).

Задача «Терези»

вхідний файл                                Input.txt

Вихідний файл                             Output.txt

обмеження по часу                     1 секунда

Є підоймові терези і набір гир масою 1,3,9,27… 3^n-1 кг, причому кожна гиря в єдиному екземплярі. На лівий  важіль терезів кладеться предмет масою m кг. Потрібно розподілити гирі на терезах так, щоб був досягнутий баланс. Не вимагається використовувати всі гирі.

 Формат вхідних даних: у першому рядку файлу Input.txt - числа m i n   ( n менше рівне 20)  (цілі,  невід’ємні), розділені символом «пробіл»

Формат вихідних даних:  у першому рядку файла Output.txt -  число  m і маси  гир на лівому важелі в порядку зростання . У другому рядку – маси гир на правому важелі терез