Информатика

1 132 задачивместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Type Printer#33314
Вам нужно напечатать N слов на Movable Type Printer. Movable Type Printers — это старые принтеры, для работы которых требуется ставить маленькие металлические кусочки (каждый из кусочков содержит одну букву) в определенном порядке, образуя таким образом слова. Потом все они вдавливаются в лист бумаги. Таким образом печатается одно слово. Ваш принтер позволяет делать следующие операции:
  • Добавить букву в конец слова, находящегося сейчас на принтере.
  • Удалить последнюю букву из слова, находящегося сейчас на принтере. Эту операцию можно делать, только если слово содержит хотя бы одну букву.
  • Напечатать слово, находящееся на принтере.
Изначально на принтере содержится пустое слово. В конце печати на принтере можно оставить непустое слово. Слова, которые вам даны, вы можете печатать в произвольном порядке.
 
Каждая из трёх операций занимает одну единицу времени. Вам нужно найти последовательность операций, которая печатает данные N слов за минимальное время. Если минимальных последовательностaей несколько, выведите любую.
 
Входные данные
Ваша программа должна считать следующие входные данные:
 
На первой строке число N (1<=N<=25000).
На следующих N строках слова, состоящие из маленьких букв латинского алфавита. Длина каждого слова не превышает 20. Все слова различны.
 
Выходные данные
Ваша программа должна вывести следующие данные:
 
На первой строке M — число операций.
На следующих M строках по одному символу — описание операций. Каждая операция описывается одним символом:
Добавление символа обозначается собственно символом.
Удаление символа обозначается символом «-» (минус, ASCII-код 45).
Операция «напечатать текущее слово» обозначается символом «P» (заглавная латинская буква P).
 
Ввод Вывод
3
print
the
poem
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P
БорОбход в глубину
✓ 1✗ 741 200средняяВойти и решать
Кот Гусь и случайная матрица#33256

Кот Гусь подготовил для Ника Фьюри прямоугольную таблицу a размера \(n \cdot m\), содержащую числа от 0 до p−1. Ник Фьюри сразу понял, что каждое число в этой таблице выбрано случайно равновероятно от 0 до p−1, независимо от остальных.

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

Формально, вам необходимо найти такие \(1 <= i_1 <= i_2 <= n\), \(1 <= j_1 <= j_2 <= m\), что сумма ax,y по всем \(i_1 <= x <= i_2\), \(j_1 <= y <= j_2\) делится на p, и среди таких имеет максимальную сумму.

Входные данные
В первой строке расположено три целых числа n, m, p (\(1 <= n·m, p <= 1 000 000\)) — размерности матрицы и число, на которое должна делится сумма подматрицы.
В следующих n строках расположено по m целых чисел, j-е число в i-й строке равно ai,j (\(0 <= a_{i,j} <= p ? 1\)).
Гарантируется, что каждое число в a выбрано независимо случайно равновероятно от 0 до p−1.

Выходные данные
Выведите одно целое число — максимальную сумму прямоугольной подматрицы, в которой сумма делится на p. Если таких нет, выведите 0.

 

Примеры
№ Входные данные Выходные данные
1
6 7 5
0 0 3 0 1 0 4
0 2 3 0 2 2 1
2 4 1 4 4 0 3
1 1 0 2 0 3 2
3 0 3 1 0 1 2
1 2 0 0 3 3 1
 65
КучаПрефиксные суммы(минимумы, ...)
✓ 8✗ 1791 200средняяВойти и решать
BalloonsBOOM#33119
Любимая компьютерная игра Васи называется “Overtouched”. В начале игры на
экране появляются несколько рядов с разноцветными шариками. Игрок нажимает на любой шарик, после чего все шарики такого же цвета удаляются. После удаления все оставшиеся шарики сдвигаются влево так, чтобы в ряду между соседними шариками не оставалось пустых мест, порядок шариков в ряду при этом не изменяется. 
Нужно вывести все оставшиеся шарики.

Формат входных данных:
Вводятся числа n и m (0 <n,m < 1^9999999999 + 11) – количество строк и шариков в каждой строке соответственно. Затем вводится цвет каждого шарика. В следующей строке вводится цвет шариков k, которые нужно удалить.

Формат выходных данных:
Выводятся оставшиеся шарики после удаления.
 
Ввод Вывод
4 3
1 2 3
4 2 2
1 7 6
2 2 2
2
1 3
4
1 7 6
(с) Кабицкий А., 2018г.
Алгоритмы обработкиОдномерные массивы
✓ 0✗ 81 200средняяВойти и решать
Вася с пультом#33116
Однажды, Вася взял без спроса у бабушки пульт от телевизора и выбежал во двор с прямого хода. Радиус двора - R метров. Прямой путь от парадного выхода до калитки - хорда AB, являющаяся диаметром этой окружности. Добежав до центра окружности, он увидел деда выскочившего ему наперерез. Василий принял решение сбежать через дырку в заборе. Но чтобы не портить бабушкины цветы и тем самым не добить её своим поступком, он подумал что лучше всего бежать по дорожкам. На картинке они обозначены.


Близжайщая тропинка ведущая до дырки - AC, к ней от центра ведёт дорожка ОН. 
 
Подсчитайте расстояние которое ему предстоит пробежать c момента как он выскочил из дома.
1 < R < AC < 10^18

Входные данные:
10 16
Выходные данные
24.000

(с) Медведев Д., 2018
Вычисление по заданной формулеЭлементарная геометрия
✓ 0✗ 11 200средняяВойти и решать
вес Деда Мороза#33112
Дед Мороз очень любит раздавать «подарочки» и если он долго их не раздаёт, то начинает грустить и поедать печеньки (не факт, что печеньки не олени). И он начинает толстеть, но когда он дарит хотя бы один подарочек, то возвращается к начальному весу (Т-Т ©Маша). На какой максимальный вес потолстеет Дед Мороз, если на одном отрезке он дарит по 1 подарку на каждый целый индекс, а всего он обойдёт m домов. Даны n отрезков пути для Деда Мороза на его траектории раздачи подарочков и сами отрезки. Также дано количество домов, которое он обойдёт.
Изначальный вес Деда Мороза 227 ± 1 кг.

Ввод Вывод
3 12
2 6
3 9
3 4
 3
(с) Манаев В., Кашукова М., 2018 г.
Задачи на моделированиеОтрезки
✓ 0✗ 21 200средняяВойти и решать
Лучшее место#32967
В зале ожидания на вокзале стоят N рядов из M кресел. Чтобы ожидающие не скучали, вместо некоторых кресел установлено K мощных Wi-Fi роутеров. Ожидающие стараются занять места ближе к роутерам, так как тогда они смогут смотреть ролики с Youtube или VK с более высоким разрешением, без задержек. Если пассажир сидит на месте с номером c в ряде r, а i-й роутер расположен на месте Ci в ряде Ri, то расстояние до i-го роутера вычисляется как max(|r−Ri|,|c−Ci|), где |x| – абсолютное значение x. Креслам в зале ожидания был присвоен приоритет от 1 до N⋅M−K, меньшие номера получили кресла с меньшим расстоянием до ближайшего роутера, среди кресел с одинаковым расстоянием до роутеров более удобными считаются кресла, стоящие в ряду с меньшим номером, а среди них — с меньшим номером места в ряду. На рисунке показан приоритет кресел в зале ожидания с 4 рядами из 7 кресел, в котором установлены 2 роутера (их позиции помечены черным цветом). Темно-серым цветом выделены кресла, стоящие на расстоянии 1 от роутеров, светло-серым — на расстоянии 2, белым — 3.
 

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

Первая строка ввода содержит четыре целых чисел — количество рядов N (2 ≤ N ≤ 109) и мест в ряду M (2 ≤ M ≤ 109), количество роутеров K (1 ≤ K ≤ 100, K < N⋅M), количество запросов Q (1 ≤ Q ≤ 100). Далее следует K строк, содержащих два целых числа — местонахождение роутеров: номер ряда Ri (1 ≤ Ri ≤ N) и номер места в ряду Ci (1 ≤ Сi ≤ M). Среди них нет совпадающих. Далее следует строка, содержащая Q целых чисел в диапазоне от 1 до N⋅M−K – приоритеты кресел.

Вывести для каждого запроса на отдельной строке одно целое число — расстояние до ближайшего роутера от кресла с заданным приоритетом.
 
Ввод Вывод
4 7 2 4
2 5
4 4
1 6 16 26
1
1
2
3
Бинарный поискСканирующая прямая
✓ 1✗ 131 300средняяВойти и решать
Разбиение последовательности#32948
Последовательность натуральных чисел от 1 до `N` нужно разбить на две части от 1 до `K` и от `K+1` до `N` так, чтобы абсолютное значение разности суммы чисел в первой и второй части последовательности было как можно меньше. То есть нужно найти такое `K`, что значение выражения `|\ sum_{i=1}^K\ i\ -\ sum_{i=K+1}^N\ i\ |` минимально. Например, для последовательности чисел от 1 до 4 разбиение будет минимальным для `K=3`, так как `|\ (1+2+3)-(4)\ |\ =\ 2`, что меньше значения разности для `K=1` равного `|\ (1)-(2+3+4)\ |\ =\ 8` и для `K=2` равного `|\ (1+2)-(3+4)\ |\ =\ 4`.
Напишите программу, которая для заданного `N` находит минимальное разбиение.
Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 10^9`).
Вывести одно целое число `K`. Если существует несколько вариантов разбиения, то вывести меньшее из возможных `K`.

Ввод Вывод
4 3

Вывод формулыВычисление по заданной формуле
✓ 2✗ 351 300средняяВойти и решать
31922#31922
Даны два простых числа p и q. Надо расшифровать сообщение состоящее из последовательности чисел оканчивающееся нулем с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<10), далее вводится длина N (N<10) и сообщение состоящее из натральных чисел не превышающее 10.

Ввод Вывод
3 7
1 11 12 16 17 6 7 8 18 0 0		 1234567890

Арифметические алгоритмы (Теория чисел)МЦКО-10. RSA
✓ 0✗ 121 400средняяВойти и решать
RSA. Расшифровать сообщение#31921
Даны два простых числа p и q. Надо расшифровать сообщение состоящее из последовательности чисел оканчивающееся нулем с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<10) и сообщение состоящее из натуральных чисел оканчивающееся нулем.

Ввод Вывод
3 7
1 11 12 16 17 0		 1 2 3 4 5

Арифметические алгоритмы (Теория чисел)МЦКО-10. RSA
✓ 0✗ 251 300средняяВойти и решать
RSA. Зашифровать большое числовое сообщение#31920
Даны два простых числа p и q. Надо зашифровать сообщение длинной N с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<100), далее вводится сообщение состоящее из цифр.

Ввод Вывод
3 7
12345678901234567890		 1 11 12 16 17 6 7 8 18 0 1 11 12 16 17 6 7 8 18 0

"Длинная" арифметикаМЦКО-10. RSA
✓ 0✗ 271 300средняяВойти и решать
Fenced In#29546
Коровы Фермера Джона боятся больших пространств. Поэтому разгородил своё поле на некоторое количество маленьких регионов, построив вертикальные (север-юг) и горизонтальные (восток-запад) изгороди.
Поле представляет собой прямоугольник с угловыми вершинами в точках (0,0) and (A,B). ФД построил n вертикальных изгородей (0≤n≤25,000) в различных позициях a1…an (0<ai<A); каждая изгородь проходит от точки (ai,0) до точки (ai,B). Он также построил m горизонтальных изгородей (0≤m≤25,000) в в различных позициях b1…bm (0<bi<B); каждая изгородь, проходит из (0,bi) в (A,bi). Каждая вертикальная изгородь пересекается с каждой горизонтальной изгородью, разделив поле на (n+1)(m+1) регионов.
 
К несчастью, ФД забыл построить ворота в своих изгородях, сделав невозможным коровам покидать свой регион. Он хочет исправить ситуацию, удалив куски изгороди, чтобы позволить коровам перемещаться между соседними регионами. Он хочет выбрать некоторые пары соседних регионов и удалить всю длину изгороди между ними. А ещё он хочет обеспечить, чтобы коровы могли попасть в любую часть поля.
 
Например, ФД мог построить изгороди так:
 
+---+--+
|      |   |
+---+--+
|     |    |  
|     |    |
+---+--+
и открыть их так:
 
+---+--+
|          |  
+---+  +  
|          |  
|          |
+---+--+
Помогите ФД определить минимальную суммарную длину изгородей, которые он должен удалить, чтобы достичь своей цели.
 
ФОРМАТ ВВОДА:
Первая строка ввода содержит числа A, B, n, and m (1≤A,B≤1,000,000,000). Следующие n строк содержат a1…an. Следующие m строк содержат b1…bm.

ФОРМАТ ВЫВОДА:
Выведите минимальную длину изгороди, которую ФД должен удалить. Заметим что это число может не поместиться в 32-битное целое и Вам нужно использовать 64-битное целое (например, "long long" в C/C++ )
 
Ввод Вывод
15 15 5 2
2
5
10
6
4
11
3
 44
Алгоритмы сортировкиЖадный алгоритм
✓ 1✗ 41 200средняяВойти и решать
Дом у дороги#29479
Министерство дорожного транспорта решило построить себе новый офис. Поскольку министр регулярно выезжает с инспекцией наиболее важных трасс, было решено, что офис министерства не должен располагаться слишком далеко от них.
 
Наиболее важные трассы представляют собой прямые на плоскости. Министерство хочет выбрать такое расположение для своего офиса, чтобы максимум из расстояний от офиса до трасс был как можно меньше.
 
Требуется написать программу, которая по заданному расположению наиболее важных трасс определяет оптимальное расположение дома для офиса министерства дорожного транспорта.
 
Входные данные
Первая строка входного файла содержит одно целое число n — количество наиболее важных трасс (1  ≤ n ≤ 104 ).
 
Последующие n строк описывают трассы. Каждая трасса описывается четырьмя целыми числами x1, y1, x2 и y2 и представляет собой прямую, проходящую через точки (x1, y1)  и (x2, y2) . Координаты заданных точек не превышают по модулю 104. Точки (x1 , y1)  и (x2 , y2)  ни для какой прямой не совпадают.
 
Выходные данные
Выходной файл должен содержать два разделенных пробелом вещественных числа: координаты точки, в которой следует построить офис министерства дорожного транспорта. Координаты по модулю не должны превышать 109, гарантируется, что хотя бы один такой ответ существует. Если оптимальных ответов несколько, необходимо выведите любой из них.
 
Ответ должен иметь абсолютную или относительную погрешность не более 10−6, что означает следующее. Пусть максимальное расстояние от выведенной точки до некоторой трассы равно x, а в правильном ответе оно равно y. Ответ будет засчитан, если значение выражения | x − y | /  max(1, |y| )  не превышает 10−6.
 
 
Ввод Вывод
4
0 0 0 1
0 0 1 0
1 1 2 1
1 1 1 2
 0.5000000004656613 0.4999999995343387
7
376 -9811 376 -4207
6930 -3493 6930 -8337
1963 -251 1963 -5008
-1055 9990 -684 9990
3775 -348 3775 1336
7706 -2550 7706 -8412
-9589 8339 -4875 8339
 4040.9996151750674 12003.999615175067

 Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2011, 2 день, Задача D 
Вычислительная геометрияТернарный поиск
✓ 2✗ 381 300средняяВойти и решать
Генерация ПСП#27312

Самой инновационной разработкой "British Scientists, Inc" является способ нахождения решения для любой задачи, которую возможно решить с помощью тильда-омега-лямбда-исчисления (то есть, для никакой). Для этого они перебирают все возможные скобочные последовательности длины x, где х - первая цифра секретной константы, использующейся во многих разработках компании. Если x нечётное, они просто прибавляют к нему единицу. Потом они используют продвинутые алгоритмы, использующие нейролингвистическое программирование и вычисленные по спирали Фибоначчи числа Каталана гуголдцатого порядка для определения местонахождения термов. Но эти алгоритмы уже реализованы и запатентованы. 

Ваша же задача - реализовать алгоритм перебора. 


Входные данные
На вход подаётся первая цифра секретной константы - x (\(1 <= x <= 9\)). 
 

Выходные данные
Нужно вывести все ПСП длины x (или x+1, если \(x \% 2 ==1\)) в лексикографическом порядке.

 

Примеры
№ Входные данные Выходные данные
1 1
( )
[ ]
{ }
Рекурсивный переборСтроки
✓ 8✗ 4501 200средняяВойти и решать
27309#27309
Вы должны реализовать алгоритм или структуру данных, эффективно реализующих следующие запросы:
1)Добавление в массив элемента
2)Извлечение k-того по величине элемента массива (первым по величине будет считаться наименьший элемент)
Гарантируется, что каждый элемент встречается в массиве всего один раз
 
Входные данные:
В первой строке указано натуральное число n, за ним следует n целых чисел. 
Далее вводится натуральное m - количеств запросов.
В каждой из следующих m строк содержится слово "add" или "get" и целое число k.
Все численные значения по модулю не превосходят 1000. 
В первом случае вы должны дополнить массив элементом со значением k. Иначе - вывести k-тый элемент отсортированного текущего массива (индексация с единицы).
 
Выходные даннные: 
Вы должны ответить на запрос извлечения k-того элемента массива, а именно вывести его значение на экран.

(c) Ибрахим Ахмад, 2017
Двоичное дерево поискаПорядковые статистики
✓ 0✗ 41 300средняяВойти и решать
Кедор и Гихаил#27305
Меллерт Гихаил сегодня был в прекрасном настроении до того, как его одноклассник Фусков Кедор не заговорил о политике. Гихаил очень сильно разозлился, поэтому придумал задачу по информатике для Кедора, чтобы тот начал решать и наконец-то заткнулся. 
Задача была такая:  “Существует n логических функций, которые зависят от одного и того же множества переменных. Даны n чисел, битовое представление которых определяет таблицу истинности для каждой функции. Вам необходимо найти такой порядок расположения функций, чтобы из каждой функции логически следовала любая из последующих или сказать, что это  невозможно. Если ответ существует, то необходимо найти лексикографически минимальный порядок. Можно показать, что размер множества переменных, от которого зависят функции, не влияет на решение задачи”.
 Кедор – ваш лучший друг, а Гихаил – заклятый враг, поэтому вы решили помочь с решением задачи, а затем вместе с Кедором возобновить разговоры о политике, чтобы Гихаил от злости улетел на Луну.
 
Входные данные
В первой строке дано число n (1 <= n <= 10) – кол-во функций. 
Во второй строке дано n чисел в диапазоне [0; 10^9] – таблицы истинности функций, переведенные в десятичную систему счисления. 
Выходные данные
Если порядок существует, в первой строке выведите “YES”, во второй лексикографически минимальную перестановку из всех возможных. Если порядка нет, то выведите “NO”.

Пример
Ввод Вывод
3
3 1 7
 YES
2 1 3
2
1 2
NO
 

(с)  Курбатов Е., 2017
 
битмаскиПереборРазбор случаев
✓ 3✗ 171 200средняяВойти и решать
Building a Ski Course#27301
Фермер Джон помогает превратить его большое поле в лыжный маршрут для предстоящих Му-олимпийских игр. Поле имеет размеры M x N (1 <= M,N <=100) и его целевое финальное состояние описывается решеткой из M x N символов таких как:
 
RSRSSS
RSRSSS
RSRSSS
 
Каждый символ описывает состояние снега на этом участке R – грубый, S – гладкий (организаторы считают, что в таком случае - чередования грубых и гладких участков, гонка будет интересней).
 
Для выполнения этой задачи ФД планирует модифицировать свой трактор так, чтобы тот мог «отштамповать» любой фрагмент размером B x B (B<=M,B<=N) грубым снегом или гладким снегом.
ФД хочет сделать B как можно большим. С B=1 он может подготовить поле, штампуя индивидуально квадраты в соответствии с заданным финальным состоянием. Однако для бОльших значений B может оказаться невозможным выполнить задачу. Каждый квадрат поля должен быть обработан трактором. Невозможно оставить ячейку поля в исходном состоянии.
 
Помогите ФД определить максимально возможное значение B, которое он сможет успешно использовать.
 
INPUT FORMAT:
 
* Строка 1: Два разделённых пробелом целых числа M и N.
 
* Строки 2..M+1: M строк ровно по N символов (каждый R или S),
        описывающих желаемое финальное состояние поля.

 
OUTPUT FORMAT:
 
* Строка 1: Максимальное значение B, которое ФД может использовать, чтобы создать нужное поле.
 
 
Ввод Вывод
3 6
RSRSSS
RSRSSS
RSRSSS
 3


 
OUTPUT DETAILS:
 
ФД может отштамповать R колонках 1-3, затем S в колонках 2-4, затем R в колонках 3-5, и наконец,  S в колонках 4-6.
 
Двумерные массивыКонструктив
✓ 0✗ 41 200средняяВойти и решать
Малыш и Карлсон#27293
Малыш может съесть банку варенья за А1 минут, корзину печенья за B1 минут, выпить бутылку молока за C1 минут. А Карлсон может сделать это за A2, B2, C2 минут соответственно. Напишите программу, вычисляющую, за какое минимальное время они смогут покончить с завтраком, состоящим из банки варенья, корзины печенья и бутылки молока?
 
В первой строке входного файла содержится три целых числа, разделенных пробелами – значения параметров A1, B1, C1. Во второй строке входного файла содержится три целых числа, разделенных пробелами – значения параметров A2, B2, C2. Все числа в диапазоне от 1 до 106.
В выходной файл вывести одно число – минимальное время завтрака с точностью 10−5.
 
Ввод Вывод
13 10 14
6 6 7
 12.00000

(с) Южно-Уральский открытый командный чемпионат, 2006
Бинарный поиск по ответуЗадачи на моделирование
✓ 5✗ 1231 200средняяВойти и решать
Modern Art #3#27225
Недавно вошла в моду корова-художница Picowso.
Picowso рисует особым образом. Она начинает на чистом холсте N×N, представленной матрицей N×N нолей, где ноль означает пустую ячейку холста. Затем она рисует до 9 прямоугольников на холсте, каждый одним из 9 цветов (последовательно пронумерованных 1…9). Например, она может начать рисовать прямоугольник цветом 2, получая такое промежуточное состояние холста:
 
2220 
2220 
2220 
0000
Затем она может нарисовать прямоугольник цветом 7:
 
2220 
2777 
2777 
0000
Затем она может нарисовать прямоугольник цветом 3:
 
2230 
2737 
2777 
0000
Каждый прямоугольник имеет стороны, параллельные сторонам холста и самый большой прямоугольник может быть размером с весь холст, а самый маленький размером в одну ячейку. Каждый цвет из 1…9 используется ровно один раз, хотя впоследствии любой цвет может полностью покрыть некоторые из ранних цветов.
 
По заданному конечному положению холста вычислите сколько из ещё видимых цветов могли быть первым нарисованным цветом.
 
ФОРМАТ ВВОДА:
 
Первая строка ввода содержит N, размер холста (1≤N≤10). Следующие N строк описывают финальную картинку холста, каждая содержит по N чисел в интервале 0…9. Гарантируется, что такой ввод был получен рисованием как описано выше с использованием различных цветов.

ФОРМАТ ВЫВОДА:
 
Выведите количество цветов, которые могли быть использованы первым, из всех цветов, которые видны на финальном рисунке.
 
Ввод Вывод
4
2230
2737
2777
0000
 1
Двумерные массивыКонструктив
✓ 4✗ 181 200средняяВойти и решать
COWBASIC#27217
Беси изобрела новый язык программирования, но поскольку нет компилятора, она нуждается в Вашей помощи для исполнения её программ.
COWBASIC - это простой, элегантный язык. У него две основные черты: сложение и циклы. Для решения проблемы переполнения, Беси выполняет все операции сложения по модулю 109+7. MOO-цикл исполняет блок кода фиксированное количество раз. Циклы и сложения могут быть вложенными.
 
Вам дана COWBASIC-программа, определите результат её выполнения - число, которое она вернёт.
 
ФОРМАТ ВВОДА:
 
Вам дана COWBASIC-программа длиной не более 100 строк, каждая строка длиной не более 350 символов. COWBASIC-программа это список операторов.
Имеется три типа операторов:
 
<переменная> = <выражение>
 
<литерал> MOO {
  <список операторов>
}
 
RETURN <переменная>
Имеется три типа выражений:
 
<литерал>
 
<перменная>
 
( <выражение> ) + ( <выражение> )
 
Литерал - это положительное целое число не более 100,000.
 
Переменная - это строка не более 10 маленьких латинских букв.
 
Гарантируется, что переменная никогда не будет использована или возвращена оператором RETURN прежде, чем она будет определена. Гарантируется, оператор RETURN будет только один раз в последней строке программы.
 
ФОРМАТ ВЫВОДА:
 
Выведите одно положительное целое число - значение переменной, возвращённой оператором RETURN.
ОЦЕНИВАНИЕ
 
в 20% тестов MOO-циклы не вложены.
В других 20% всех тестов программу будет иметь только одну переменную. MOO-циклы могут быть вложенными
В остальных тестах нет никаких ограничений.
 
Ввод Вывод Примечание 
x = 1
10 MOO {
  x = ( x ) + ( x )
}
RETURN x
 1024 Эта COWBASIC-программа вычисляет 210 
n = 1
nsq = 1
100000 MOO {
  100000 MOO {
    nsq = ( nsq ) + ( ( n ) + ( ( n ) + ( 1 ) ) )
    n = ( n ) + ( 1 )
  }
}
RETURN nsq
 4761 Эта программа вычисляет (105∗105+1)2 (по модулю 109+7).
.

 
"Длинная" арифметикаЗадача на реализацию
✓ 1✗ 31 200средняяВойти и решать
Little Difference#27120
Little Lidia likes playing with numbers. Today she has a positive integer n, and she wants to decompose it to the product of positive integers.

Because Lidia is little, she likes to play with numbers with little difference. So, all numbers in decomposition should differ by at most one. And of course, the product of all numbers in the decomposition must be equal to n. She considers two decompositions the same if and only if they have the same number of integers and there is a permutation that transforms the first one to the second one.
Write a program that finds all decompositions, which little Lidia can play with today.

Input
The only line of the input contains a single integer n (1 ≤ n ≤ 1018).

Output
In first line output the number of decompositions of n, or −1 if this number is infinite. If number of decompositions is finite, print all of them one per line. In each line first print number ki of elements in decomposition. Then print ki integers in this decomposition in any order. Don’t forget that decompositions which are different only in order of elements are considered the same.
 
Input Output
12 3
1 12
3 2 3 2
2 4 3
1 -1

In the second example 1 can be represented as product of any number of ones.
Динамическое программирование: последовательностиКонструктив
1 300средняяВойти и решать
Поделиться
Класснуть