A. Собираемся в Хогвартс Ограничение времени 1 секунда

Ограничение памяти 62Mb

Ввод стандартный ввод или test.in

Вывод стандартный вывод или test.out

В 1990 году Джоан Роулинг была в переполненном поезде, следовавшем из Манчестера в Лондон, когда идея о Гарри Поттере, по словам писательницы, вдруг «упала на голову». Таким образом, можно сказать, что 2020 год – юбилейный для саги о Гарри Поттере. Мы с вами тоже отметим это, решив несколько задач о героях этих книг. Каждому юному волшебнику для обучения в школе Хогвартс необходимо приобрести специальные волшебные принадлежности (магические книги, шары знаний, волшебные свитки). На эти цели банк Гринготтс выдает деньги. Для каждого школьника сумма определяется индивидуально, необходимое количество принадлежностей заранее высылается совиной почтой. Известно, что цены на волшебные предметы, следующие: магическая книга – 20 золотых галеонов, шар знаний – 10 золотых галеонов, волшебный свиток – 5 золотых галеонов. Выданную банком сумму нужно потратить полностью, так как иначе деньги сгорят. От Вас требуется написать программу, которая подбирает и выведет все возможные варианты покупок для отдельно взятого юного волшебника. Обратите внимание, что у каждого ученика школы Хогвартс должна быть хотя бы одна магическая книга. Гарантируется, что на выделенную сумму можно купить хотя бы один набор волшебных предметов, удовлетворяющий̆ всем условиям.

Формат ввода

В первой строке входного файла записано одно целое число L – выданная банком сумма в галеонах (1 ≤ L ≤ 1000). Во второй строке входного файла записано одно целое число N – количество предметов, которые нужно купить (1 ≤ N ≤ 100).

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

В M строках выходного файла вывести по три целых числа, разделенных пробелами, – количество магических книг, шаров знаний и волшебных свитков. Каждый такой набор описывает один из вариантов покупки. Причем варианты должны быть описаны в порядке увеличения количества купленных магических книг, а при равенстве этого количества – в порядке увеличения шаров знаний и, в последнюю очередь, по увеличению количества свитков.

Можно на любом языке

1) 145 (10 сс) - 10010001 (2 сс)

145 (10 сс) - 221 (8 сс)

145 (10 сс) - 91  (16 сс)

2) 854 (10 сс) - 1101010110 (2 сс)

854 (10 сс) - 1526 (8 сс)

854 (10 сс) - 356  (16 сс)

Объяснение:

145 (10 сс) - 10010001 (2 сс)

145 делим в столбик на 2 без остатка. 145/2=72 (145-144=1), далее 72/2=36 (72-72=0), 36/2=18 (36-36=0), 18/2=9 (18-18=0), 9/2=4 (9-8=1), 4/2=2 (4-4=0), 2/2=1 (2-2=0). Записываем в обратном порядке полученные цифры: 10010001.

145 (10 сс) - 221 (8 сс)

145 делим в столбик на 8 без остатка. 145/8=18 (145-144=1), 18/8=2 (18-16=2). Записываем в обратном порядке полученные цифры: 221

145 (10 сс) - 91  (16 сс)

145 делим в столбик на 16 без остатка. 145/16=9 (145-144=1).

Записываем в обратном порядке полученные цифры: 91

Программа работает неверно: даже на примере из условия вместо 2600 выводится 55*245 = 13475. В программе происходит что-то странное, например, сравниваются элементы последовательности и 8 (зачем?)



Подумаем, как можно было бы решать задачу.
- Наивный сохранить все числа в массив и пробежаться по нему в двойном цикле, в псевдокоде это выглядит примерно так:
max = 0
for i = 1 to n do
  for j = 1 to n do
    if |i - j| >= 8 and max < a[i] * a[j] then
      max = a[i] * a[j]
Это нехорошо и по времени (время выполнения порядка n^2), и по памяти (количество памяти растет с ростом n пропорционально n).
- Немного ускоряем: у нас пары i, j и j, i ничем не отличаются, так что будем считать, что j < i. Учитывая условие, что |i - j| >= 8, получаем, что j <= i - 8. Переписываем:
max = 0
for i = 9 to n do
  for j = 1 to i - 8 do
    if max < a[i] * a[j] then
      max = a[i] * a[j]
Это решение работает в 2 раза быстрее, но этого недостаточно. Памяти тоже слишком много.
- Продолжаем ускорять. Пусть i зафиксировано. Мы пытаемся сравнить a[i] * a[j] с max для всех j от 1 до i - 8. Очевидно, произведение будет максимально, если a[j] - максимум среди a[1], a[2], ..., a[i - 8]. Возможное решение: создадим массив из максимумов среди первых k чисел, и будем сравнивать уже с максимумом.
maximums[1..n]
maximums[1] = a[1]
for i = 2 to n do 
  maximums[i] = max(maximums[i - 1], a[i])
max = 0
for i = 9 to n do
  if max < a[i] * maximums[i - 8] then
    max = a[i] * maximums[i - 8]
Это решение уже работает быстро, но остались проблемы с большим расходом памяти.
- Последний рывок. Заметим, что для того, чтобы разобраться с числом под номером i, нам совсем не нужен массив a, а из массива maximums достаточно знать только maximums[i - 8], ..., maximums[i - 1] - 8 чисел. Так что большие массивы не нужны, их можно убрать. Тогда программа будет эффективна и по времени, и по памяти.

У меня максимумы хранятся в массиве maxs[0..7], все номера берутся по модулю 8. В вашей программе это может быть реализовано иначе.
Pascal:
var
  i, n, t, max: integer;
  maxs: array[0..7] of integer;
begin
  read(n);
  read(t);
  max := 0;
  maxs[1] := t;
  for i := 2 to n do
  begin
    read(t);
    if (i > 8) and (max < t * maxs[i mod 8]) then
      max := t * maxs[i mod 8];
    if t > maxs[(i + 7) mod 8] then
      maxs[i mod 8] := t
    else
      maxs[i mod 8] := maxs[(i + 7) mod 8];
  end;
  write(max);
end.