Напишите программу, которая в последовательности натуральных чисел определяет максимальное число, оканчивающееся на 3. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, оканчивающееся на 3. Количество чисел не превышает 1000. Введённые числа не превышают 30 000. Программа должна вывести одно число – максимальное число, оканчивающееся на 3

22

Объяснение:

Понятно, что каждая из команд может только увеличить число.

У нас обязательно есть число 16, из него есть два пути:

1. сделать +1

2. сделать x2

Если мы сделаем +1, то после этого уже точно не сможем сделать x2, т.к. 17 x 2 =  34, а 34 > 33, а уменьшить число мы не сможем. Если мы будем делать постоянно +1, то мы точно пройдём через 30.

Значит не нужно делать +1, когда мы на числе 16, а надо делать x2.

Следовательно, концовка у нас точно будет такая 16 -> 32 -> 33.

Теперь надо посчитать, сколько различных получить 16 из 2. К любому такому мы допишем нашу концовку и получим программу подходящую под наши условия, и к тому же все программы, подходящие под данные условия, выглядят именно так.

Считать сколькими можно получить 16 из 2 будет динамическим программированием.

ans[i] - количество различных программ, которые получают i из 2.

Очевидно, ans[2] = 1 (пустая программа).

ans[3] = 1 (нужно сделать +1)

ans[4] = ans[3] + ans[2] = 2 (можно сделать +1 к 3, а можно x2 к 2)

Далее вычисления всегда следующие:

ans[i] = ans[i - 1] + ans[i / 2] для чётных i (можно либо добавить +1 к числу i - 1, либо сделать x2 для числа i / 2)

ans[i] = ans[i - 1] для нечётных i (можно получить только путём добавления +1 к числу i - 1)

Итак, считаем:

ans[2] = 1

ans[3] = ans[2] = 1

ans[4] = ans[3] + ans[2] = 2

ans[5] = ans[4] = 2

ans[6] = ans[5] + ans[3] = 4

ans[7] = ans[6] = 4

ans[8] = ans[7] + ans[4] = 6

ans[9] = ans[8] = 6

ans[10] = ans[9] + ans[5] = 8

ans[11] = ans[10] = 8

ans[12] = ans[11] + ans[6] = 12

ans[13] = ans[12] = 12

ans[14] = ans[13] + ans[7] = 16

ans[15] = ans[14] = 16

ans[16] = ans[15] + ans[8] = 22

Значит 16 из 2 можно получить И столькими же можно получить 33 из 2 выполняя условия задачи.

// PascalABC.NET 3.1, сборка 1219 от 16.04.2016
begin
  var a:=ReadLines('m17.txt').JoinIntoString.ToIntegers;
  a.Println;
  var b:=a.Select((x,i)->Rec(x,i)).Where(x->x.Item1<0)
    .Select(x->x.Item2).ToArray;
  if b.Count<>2 then
    Writeln('Количество отрицательных элементов не равно двум')
  else begin
    a:=SeqFill(b[0],0).Concat(a.Skip(b[0]).Take(b[1]-b[0]+1))
      .Concat(SeqFill(a.Length-b[1]-1,0)).ToArray;
    a.Println
    end
end.

Тестовое решение:
23 14 7 15 0 13 -6 41 18 13 8 42 27 -11 3 19 10
0 0 0 0 0 0 -6 41 18 13 8 42 27 -11 0 0 0

Файл с исходными данными имеет имя m17.txt. Тестовый файл находится во вложении. Разбивка на строки сделана по 5 значений, но может быть совершенно произвольной. Также нет привязки именно к 17 числам, главное - чтобы отрицательных чисел было ровно два, иначе будет выдано сообщение о их неверном количестве.