Информатика

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

Необходимо найти в заданной серии показаний прибора максимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 9 минут. Если получить такое произведение не удаётся, ответ считается равным –1. Количество энергии, получаемое прибором за минуту, не превышает 1000 условных единиц. Общее количество показаний прибора в серии не превышает 10 000.

Задача А (2 балла). 

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

Задача Б (4 балла). 

Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). 

Входные данные
В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что \(N > 9\). В каждой из следующих N строк задаётся одно неотрицательное целое число – очередное показание прибора.

За билетами на премьеру нового мюзикла выстроилась очередь из N человек, каждый из которых хочет купить 1 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя "постояльцев" очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному. 

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

 

Однако для борьбы со спекулянтами кассир продавала не более 3-х билетов в одни руки, поэтому договориться таким образом между собой могли лишь 2 или 3 подряд стоящих человека.

 

Известно, что на продажу i-му человеку из очереди одного билета кассир тратит A_i секунд, на продажу двух билетов - Bi секунд, трех билетов - Ci секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.

 

Обратите внимание, что билеты на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних билетов (то есть билетов, которые никому не нужны).

 

Входные данные: 
- в первой строке записано число N - количество покупателей в очереди (\(1<=N<=5000\));
- далее идет N троек натуральных чисел Ai, Bi, Ci. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются начиная от кассы.

 

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

 

Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-4927. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.

 

Клавиатура телефона выглядит так:

 

Напишите программу, определяющую количество телефонных номеров длины N, набираемых ходом коня.

 

Входные данные: на вход подается целое число N (\(1<=N<=50\)).

 

Выходные данные: выведите файл искомое количество телефонных номеров.

Лесенкой называется набор кубиков, в котором каждый более верхний 

слой содержит кубиков меньше, чем предыдущий.

 

---

| |

---------

| | | | |

-----------

| | | | | |

-----------------

| | | | | | | | |

-----------------

 

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

 

Во входном файле записано число N (1<=N<=100).

 

В выходной файл вывести искомое число лесенок.

 

Пример

Пример входного файла

3

 

Пример выходного файла

2

 

Дана последовательность, требуется найти длину наибольшей возрастающей 

подпоследовательности.

 

В первой строке входного файла записано число N - длина последовательности  (1 <= N <= 1000). Во второй строке записана сама последовательность  (через пробел). Числа последовательности - целые числа,  не превосходящие 10000 по модулю.

 

В выходной файл требуется вывести наибольшую длину возрастающей подпоследовательности.

 

 

 

На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить какие-то пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.

 

- в первой строке записано число N - количество гвоздиков (\(2 <= N <= 100\));
- в следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).

 

Выходные данные: выведите единственное число - минимальную суммарную длину всех ниточек.

В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке.

За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено).

При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).

 

Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол.

 

В первой строке записаны два числа N и M - размеры таблицы (\(1<=N<=20\), \(1<=M<=20\)). Далее записаны N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (каждое число от 0 до 100).

 

Выходные данные
Выведите минимальную сумму, потратив которую можно попасть в правый нижний угол.

 

Будем рассматривать только строчки, состоящие из заглавных латинских букв. Например, рассмотрим строку AAAABCCCCCDDDD. Длина этой строки равна 14. Поскольку строка состоит только из латинских букв, повторяющиеся символы могут быть удалены и заменены числами, определяющими количество повторений. Таким образом, данная строка может быть представлена как 4AB5C4D. Длина такой строки 7. Описанный метод мы назовем упаковкой строки. 

 

Напишите программу, которая берет упакованную строчку и восстанавливает по ней исходную строку.

 

Входной файл содержит одну упакованную строку. В строке могут встречаться только конструкции вида nA, где n - количество повторений символа (целое число от 2 до 99), а A - заглавная латинская буква, либо конструкции вида A, то есть символ без числа, определяющего количество повторений. Максимальная длина строки не превышает 80.

 

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

 

Примеры

 

Ввод	Вывод
3A4B7D	AAABBBBDDDDDDD
22D7AC18FGD	DDDDDDDDDDDDDDDDDDDDDDAAAAAAACFFFFFFFFFF FFFFFFFFGD
95AB	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAB
40AB39A	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

 

Дан текст. Напишите программу, которая посчитает статистику - сколько раз встречается буква A, сколько - B и т.д. При этом большие и маленькие латинские буквы считать одинаковыми. В тексте могут быть сколь угодно длинные строки. Длина текста не превышает 100 Кб.

 

На вход подается текст, состоящий из английских букв (больших и маленьких), знаков препинания, цифр и т.д.

 

Выведите 26 строк. Каждая строка должна соответствовать латинской букве, буквы должны идти в алфавитном порядке.Каждая строка должна содержать сначала большую латинскую букву, которой она соответствует, пробел, символ - (тире), пробел и число: сколько раз буква встречается во входном файле.

 

Сколько раз встречается?

 

Входные данные
Вам дается две строки. Длина каждой из строк не превышает 255 символов.

Выходные данные
Посчитайте и выведите на экран, сколько раз первая строка встречается в качестве подстроки во второй.

 

Найдите в тексте 1543.

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

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

Если в нем встречается число 1543, выведите слово URA, если же 1543 в файле не встречается, выведите NO.

 

Дан текст (при этом в нем могут быть

строки длиннее 255 символов, строк может быть много и т.д.).

 

В ответе надо вывести точно такой же текст.