Задача A. Сувениры ≡

Условие

На Заводе кухонной утвари решили изготовить сувениры, заготовки для которых имеют форму трех кубов разного размера, поставленных друг на друга. Длина ребра куба, стоящего на поверхности, равна а. Каждый следующий куб, расположенный выше, имеет длину ребра, в два раза большую, чем предыдущий.

Заведующий складом попросил своего друга Петра написать программу для вычисления площади поверхности S заготовки, которая образована видимыми со всех сторон внешними элементами заготовки для того, чтобы оценить, сколько необходимо заказать краски.

Помогите Петру найти требуемую площадь S для покраски заготовки сувенира.

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

Единственная строка содержит одно целое число a, 0 < a ≤ 10⁸ – длина ребра куба в основании заготовки (сантиметры).

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

Выведите единственное целое число S – площадь внешней видимой со всех сторон поверхности заготовки (в квадратных сантиметрах).

Примеры тестов

12

16704

5

2900

Задача B. Предприимчивый бухгалтер ≡

Условие

После окончания университета Василий поступил на работу на Завод кухонной утвари на должность бухгалтера. В день выдачи заработной платы он получил деньги в банке купюрами достоинством 100, 200, 500, 1000 и 5000 рублей.

Его верный товарищ Петр предложил ускорить процесс выдачи денег рабочим через кассу и заранее разложить их по конвертам по N рублей в каждом (N – зарплата рабочего в цехе в рублях). Помогите Василию и Петру найти количество возможных различных способов получить сумму N рублей из данных купюр.

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

Единственная строка содержит целое число N, 1 ≤ N ≤ 10⁵.

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

Выведите одно число – количество способов получить значение N, используя только перечисленные виды купюр.

Примеры тестов

12250

0

100

1

700

6

Задача C. Штамповка заготовок ≡

Условие

На Заводе по изготовлению кухонной утвари перешли на сдельно-премиальную оплату труда. Рабочие цеха никелированных изделий Михаил и Александр решили оптимизировать свою работу и сократить время изготовления изделий.

Процесс изготовления изделия состоит из двух этапов: штамповка заготовки и никелирование. Штамповщик производит i-ую заготовку за время p_i, причем одновременно он может изготавливать только одну заготовку. Затем второй рабочий укладывает изделие в ванну, где происходит его никелирование химическим методом за время q_i. Одновременно в ванне может находиться несколько заготовок.

Напишите программу, которая поможет Михаилу и Александру определить последовательность штамповки заготовок, чтобы сделать суммарное время выполнения их работы минимальным (время считается от момента начала работы и до окончания процесса никелирования последнего изделия).

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

Первая строка входных данных содержит целое положительное число N – количество изделий, которые нужно изготовить, N не превосходит 10⁵. Далее приведены N строк, содержащих время штамповки p_i и время никелирования q_i для каждой заготовки, где p_i и q_i – целые положительные числа, не превосходящие 1000.

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

Программа должна вывести последовательность номеров заготовок, в соответствии с которой их должен делать штамповщик. Последовательность является некоторой перестановкой чисел от 1 до N.

Примеры тестов

3
10 30
10 10
20 25

1 3 2

Задача D. Устаревшее устройство ≡

Условие

Разбирая кладовку на Заводе перед инвентаризацией, заведующий складом нашел устаревшее устройство сбора информации. Командой молодых инженеров было установлено, что устройство работоспособно и содержит описание потенциально полезных технологических процессов, которые можно применить для увеличения прибыли Завода. Кроме того, предприятие, изготовившее его, до сих пор работает. Было решено обратиться к его специалистам с просьбой извлечь информацию из найденного устройства.

В архивах предприятия-изготовителя устройства из обрывков документации посчастливилось найти пример формата передаваемых данных:

12

  значение_1 ###

  значение_2

  90

    значение_4

    12

      Значение_5

    21

  09

21

Инженеры смогли считать данные по устаревшим интерфейсам устройства. После этого они попросили Петра написать программу для проверки формата данных.

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

Все значения перечисляются до начала другого блока и до конца текущего.

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

На вход программы подается последовательность строк, содержащих команды найденного устройства. Входные значения содержат символы латинского алфавита, цифры и ‘#’.

Максимальное количество строк равняется 30.

Ввод входных данных заканчивается пустой строкой.

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

Выведите YES, если структура входных данных соответствует приведенному в тексте задачи формату или NO – в противном случае.

Примеры тестов

  15 ###
  astra
  90
    56
    12
      907
    21
  09
  

NO

12
  yellow ###
  thin
  90
    12
      678 ###
      9342 ###
      num
    21
  09
21
 

YES

Задача E. Диагностика ≡

Условие

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

Последовательность сигналов подается в виде массива целых чисел A и размерностью N > 1. Искомая последовательность определяется массивом целых чисел T с размерностью M < N.

Требуется написать программу, которая выведет целое число – количество последовательностей T, встреченных в массиве A.

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

В первой строке вводятся два целых числа через пробел N и M, 1 < N ≤ 10⁵, 1 ≤ M ≤ N – количество элементов массива сигналов A и длина последовательности T соответственно.

Следующие две строки содержат по N и M целых чисел соответственно – значения измеренных сигналов и искомой последовательности.

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

В единственной строке выведите целое число – сколько раз повторяется последовательность T в последовательности A.

Примеры тестов

5 2
1 1 2 1 1
1 1

2

7 2
8 5 9 7 6 7 1
9 5

0