Задача 1. “Код да Винчи” – 15 баллов

Тип задачи: Задача по программированию

Задание рассчитано на написание программы на любом языке программирования.

Ввод данных может осуществляться как из входного файла, так и с клавиатуры.

Недавно Соня научилась считать. Она тут же заметила, что число 2 обладает замечательным свойством 2 + 2 = 2 * 2. Ее друг Леня тут же объяснил ему, что дело не в двойке.

— «Дело в том, что последовательность 2, 2 – особенная,» – сказал Соне Леня.

– «Такие последовательности изобрел Леонардо да Винчи и их принято называть «Кодом да Винчи».

Код да Винчи – это такая последовательность натуральных чисел, что сумма ее членов равна их

произведению. Например, последовательность 1, 2, 3 – тоже является кодом да Винчи.»

Соня тут же сложила 1, 2 и 3, потом перемножила их и обрадовалась.

Теперь Соня хочет найти более длинные коды да Винчи. Помогите ей!

Формат входных данных

Во входном файле input.txt задано целое число N (2<= N <= 100).

Формат выходных данных

Выведите в файл output.txt любой код да Винчи длины N. Разделяйте числа пробелами.

Члены последовательности не должны превышать 10⁹. Если такого кода да Винчи длины N не существует,

выведите в выходной файл единственное число – «-1».

Пример

З

Задача 2. “Робот” – 10 баллов

Тип задачи: Задача по алгоритмизации

Робот движется внутри лабиринта следующим образом:

1. Робот передвигается по клеткам вверх, вниз, вправо и влево.
2. Если нет препятствий (внутренних стенок или внешней стены лабиринта), то робот сохраняет направление своего движения.
3. Столкнувшись с препятствием, робот меняет направление движения на 90 градусов по часовой стрелке и движется в этом направлении до следующего столкновения.
4. Столкнувшись с определенной внутренней стенкой первый раз, робот уменьшает ее прочность. Столкнувшись с этой внутренней стенкой второй раз (подойдя к ней с любой стороны), робот окончательно разрушает эту стенку и продолжает движение, не меняя движения.
5. Внутри стены лабиринта не подвержены разрушению и столкновение с ними всегда приводит к изменению движения по описанному выше правилу.

Робот начал движение влево из верхнего левого угла лабиринта. Сколько внутренних стенок останется неразрушенными, если известно, что робот прошел 1000 клеток? В число не разрушенных внутренних стенок входят и те внутренние стенки, которые были повержены, но не разрушены. В ответе укажите целое число.

Задача 3. “Волосатый бизнес” – 20 баллов

Тип задачи: Задача по программированию. Математическое моделирование

Задание рассчитано на написание программы на любом языке программирования.

Ввод данных может осуществляться как из входного файла, так и с клавиатуры.

Одного неформала выгнали с работы, и теперь ему надо как-то зарабатывать себе на жизнь. Поразмыслив, он решил, что сможет иметь очень неплохие деньги на продаже собственных волос. Известно, что пункты приема покупают волосы произвольной длины стоимостью С у.е. за каждый сантиметр. Так как волосяной рынок является очень динамичным, то цена одного сантиметра волос меняется каждый день, как и курс валют. Неформал является очень хорошим бизнес-аналитиком. Он смог вычислить, какой будет цена одного сантиметра волос в каждый из ближайших N дней (для удобства пронумеруем дни в хронологическом порядке от 0 до N-1). Теперь он хочет определить, в какие из этих дней ему следует продавать волосы, чтобы по истечению всех N дней заработать максимальное количество денег. Заметим, что волосы у неформала растут только ночью и вырастают на 1 сантиметр за ночь. Следует также учесть, что до 0-го дня неформал с горя подстригся наголо, и к 0-му дню длина его волос составляла 1 сантиметр.

Входные данные

В первой строке входного файла INPUT.TXT записано целое число N (0 < N ≤ 100). Во второй строке через пробел заданы N натуральных чисел, не превосходящих 100, соответствующие стоимости C[i] 1 сантиметра волос за каждый i-й день.

Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести максимальную денежную сумму, которую может заработать неформал за N дней.

Примеры

Ключи

к заданиям первого (школьного) этапа Всероссийской предметной олимпиады школьников

по информатике и ИКТ 2016/2017 учебный год

11 класс

(максимум – 45 баллов)

Задача 1. “Код да Винчи” – 15 баллов

Задание рассчитано на написание программы на любом языке программирования.

Ввод данных может осуществляться как из входного файла, так и с клавиатуры.

program B;

var

n, i : integer;

begin

assign(input, ‘input.txt’); reset(input);

assign(output, ‘output.txt’); rewrite(output);

read(n):

for i := 1 to n – 2 do

write(1,‘ ‘);

writel n(‘2 ‘,n);

close(input); close(output);

end.

Задача 2. “Робот” – 10 баллов

Обратим внимание, что сталкиваясь с препятствием, в том случае, если робот вынужден менять направление движения, он будет поворачиваться по часовой стрелке, пока не получит возможность продолжить движение. Выполним формально предложенный алгоритм:

1. A1 –D1. Ослабили стенку D1|E1.

2. D1 –D4. Ослабили стенку D4|D5.

3. D4 – A4.

4. A4 –A2. Ослабилистенку A1|A2.

5. A2 –C2. Ослабили стенку C2|D2.

6. C2 –C3. Ослабили стенку C3|C4.

7. C3 – A3.

8. A3 –A1. Ослабилистенку A1|A2.

9. A1 –F1. Ослабили стенку D1|E1

10. F1 – F6.

11. F6 –C6. Ослабили стенку B6|C6.

12. C6 –C1. Ослабили стенку C3|C4.

13.C1 – F1..

14.F1 – F6..

15.F6 –A6. Ослабили стенку B6|C6.

После этого шага робот находится на клетке из внешнего радиуса поля и при этом все стенки, мешающие передвигаться по этому внешнему радиусу разрушены. Таким образом, на протяжении всех последующих ходов робот будет передвигаться по внешнему радиусу и не сможет разрушить ни одну из оставшихся стенок. Посчитаем количество оставшихся стенок (включая стенки, которые ослаблены, но не разрушены): C2|D2,E2|F2,B2|B3,D3|E3,E4|F4,D4|D5,A5|B5,E5|E6.

Таких стенок осталось восемь, что и является ответом на вопрос задания.

Ответ – 8 стенок.

Задача 3. “Волосатый бизнес” – 20 баллов

Тип задачи: Задача по программированию. Математическое моделирование

Задание рассчитано на написание программы на любом языке программирования.

Ввод данных может осуществляться как из входного файла, так и с клавиатуры.

В этой задаче нужно понять, в какой день на текущий момент времени выгоднее всего сдавать волосы. Все просто: сдавать их нужно в тот день, когда цена максимальна среди оставшихся дней. Т.е. пока еще общий срок истечения дней не окончен каждый раз нужно находить максимальный элемент массива C[k] (k=p+1..N-1) и сдавая все волосы получать свои C[k]*(k-p) у.е. , где p — номер последнего дня cдачи волос. За первый день сдачи можно считать p=-1.