Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.
Формат входного файла
Первая строка входного файла содержит заданный шаблон длиной не более 80 символов.
Формат выходного файла
Выведите в выходной файл искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2 * 109.
Однажды Петя узнал очень важную последовательность из n чисел.
Тщательно проанализировав ее, он обнаружил, что она является арифметической прогрессией.
Чтобы не забыть он записал ее элементы на n карточках.
Но затем случилась неприятность.
Не зная всю важность этой последовательности, его брат Вовочка взял еще n карточек
и написал на них произвольные числа, а потом перемешал все 2n карточек.
Теперь Петя хочет восстановить исходную последовательность по этим карточкам.
К сожалению возможно, что это можно сделать несколькими способами,
но Петю устроят любые n чисел, образующие арифметическую прогрессию.
Петя не может сделать это вручную, поэтому обратился к вам за помощью.
Напомним что последовательность a1, a2, …, an называется арифметической
прогрессией, если ai = ai − 1 + d для всех i от 2 до n и некоторого d.
Число d называется разностью арифметической прогрессии.
Формат входного файла
В первой строке входного файла находится целое число n (1 ≤ n ≤ 100000).
В следующей строке находится 2n целых чисел по модулю не превосходящих 109 —
числа, написанные на карточках, перечисленные в произвольном порядке.
Гарантируется, что можно выбрать n из них так, чтобы они образовывали
арифметическую прогрессию.
Формат выходного файла
В первой строке выходного файла выведите a1 и d — первый элемент и разность
найденной арифметической прогрессии. Если d = 0, число a1 должно встречаться среди
заданных чисел n раз.
Если существует несколько решений, выведите любое.
На столе стоят N матрёшек разного размера.
Матрёшку меньшего размера можно поместить внутрь большей, ту, в свою очередь,
внутрь ещё большей и так далее.
Сколькими способами можно поместить часть матрёшек внутрь других,
чтобы осталось ровно K матрёшек?
Формат входного файла
Входной файл содержит целые числа NK.
Формат выходного файла
Требуется вывести в выходной файл единственное целое
число — искомое число способов.
When wondering through the labyrinth, the goal is usually to find some kind of door.
Well, not this time.
A labyrinth consists of N × N cells, each 1 × 1 meter in size.
Cells are separated by doors. Each door opens in a specific direction (as shown on the picture):
left outwards;
left inwards;
right outwards;
right inwards.
So a cell can be represented by two numbers describing doors on its eastern
and southern sides according to the list above.
The doors are just slightly less then 1 meter in width.
The traveler in the labyrinth is also slightly less then 1 meter in diameter,
so he has following limitations:
He can not pull doors, only push them.
After opening the door and entering the cell it leads to,
he can not take a turn in the direction where the door opened,
because the passage is blocked by the door.
Doors have springs and close automatically when traveler leaves the cell.
Your program must find the shortest path for the traveler from north-western cell (1, 1)
to south-eastern cell (N, N).
Input file format
Input file contains labyrinth size N followed by 2 × N2 numbers
describing doors for each cell row by row.
As there are no doors leading outside of labyrinth,
values for eastern doors in the last column and southern doors in the last row are zero.
Output file format
Output file must contain the shortest path as a list of cell coordinates
(column number, then row number), including both (1, 1) and (N, N) cells.
If there are several solutions with the same length, output any one of them.
If it is impossible to get to a destination cell, output a singe zero.
Напишите программу, которая копирует текст из входного файла и добавляет к нему фразу
"Это сообщение содержит ровно K букв и ровно M цифр.",
при этом K и M должны учитывать буквы и цифры в добавленной фразе.
Буквами считаются строчные и прописные латинские буквы,
а также все символы с ASCII-кодами от 128 до 255.
Слова "буквы" и "цифры" во фразе должны иметь окончание, соответствующее числительному,
например, "21 цифру", "4 цифры", "15 цифр".
При необходимости в контрольной фразе можно не выводить одно или оба слова "ровно".
Формат входного файла
Входной файл содержит одну строку.
Формат выходного файла
В выходной файл вывести сначала строку из входного файла,
затем строку с указанной контрольной фразой.
Ограничения
Длина строки не более 200 символов.
Русские буквы должны быть в кодировке WINDOWS-1251.
Примеры тестов
№
Входной файл (input.txt)
Выходной файл (output.txt)
1
Сегодня contest.
Сегодня contest.
Это сообщение содержит ровно 49 букв и 3 цифры.
Scientists of the Nearsea Institute of Underwater Mythology are researching
the mythical creature called Cthulhu.
The creature is famous for producing many offspring known as Cthulhu spawn.
Each spawn has a small round body with N radially protruding appendages.
Each appendage is either a tentacle or a claw.
Two spawns are considered identical, if one of them can be rotated
in such a way that the sequence of tentacles and claws will
coincide with the other spawn.
For example, if we designate tentacle by "T" and claw by "C",
spawns "TCTCCT" and "CCTTCT" are identical and different from spawns
"TTTCCT" ad "CCTTTC".
You program must, for given N,
calculate the total number of different spawns with N appendages.
Input file format
Input file contains a single integer N.
Output file format
Output file must contain a single integer — number of different spawns.
В одной секретной лаборатории вывели новый вид маленьких монстров, размером чуть больше суслика.
В ходе исследований ученые решили поставить следующий эксперимент.
В центре комнаты устанавливается прямоугольный стол, поверхность которого разбита на
N x M клеток размера 1x1.
В начальный момент времени на некоторых его клетках располагаются монстры,
смотрящие параллельно сторонам стола. По команде экспериментатора монстры начинают
двигаться по прямой в ту сторону, в которую они смотрят, доходят до края стола и
спрыгивают на пол. Там их собирает лаборант Петя и относит в клетку.
Рисунок 1. Монстры на столе для экспериментов
Поскольку у монстров очень грязные лапки, они оставляют следы на тех клетках, на которых они побывали.
Так как отмывать стол придется лаборанту Пете, его заинтересовал вопрос -
в каком количестве клеток побывают монстры. Помогите ему решить эту сложную задачу.
Формат входного файла
Первая строка входного файла содержит числа M и N - размеры лабораторного стола.
Следующая строка содержит число K - количество монстров.
Следующие K строк содержат описания монстров - два целых числа и один символ из множества
{N, E, S, W} - начальные координаты и направление соответствующего монстра
(соответствие направлений и координат приведено на рисунке 1).
Символ отделен от чисел ровно одним пробелом.
Формат выходного файла
В выходной файл выведите единственное число - количество клеток стола, на которых побывают монстры.
Эллипс — геометрическое место точек, сумма расстояний для которых от двух заданных постоянна и равна 2a.
Две заданных точки называются фокусами эллипса и в нашей задаче их координаты обозначаются как
x1, y1, x2, y2. Число a называется большой полуосью эллипса.
Окружность — геометрическое место точек, расстояние для которых от заданной постоянно и равно R.
Заданная точка называется центром окружности и в нашей задаче её координаты обозначаются как x, y.
Число R называется радиусом окружности.
И для окружности, и для эллипса можно определить их внутреннюю часть —
площадь, ограниченную окружностью или эллипсом соответственно.
Напишите программу, которая по заданным окружности и эллипсу находит площадь пересечения их внутренних частей.
Формат входного файла
Во входном файле находятся целые числа x, y, R, x1, y1, x2, y2, a в этом порядке.
Формат выходного файла
Выведите единственное число - площадь пересечения с точностью до 10 − 3.
Bill is working in a secret laboratory. He is developing missiles for
national security projects. Bill is the head of the aerodynamics department.
One surprising fact of aerodynamics is called Whitcomb area rule.
An object flying at high-subsonic speeds develops local
supersonic airflows and the resulting shock waves create the effect called wave drag.
Wave drag does not depend on the exact form of the object, but rather
on its cross-sectional profile.
Consider a coordinate system with OZ axis
pointing in the direction of object's motion. Denote the area of
a section of the object by a plane z = z0 as S(z0).
Cross-sectional profile of the object is a function S that maps z0 to
S(z0). There is a perfect aerodynamic shape called Sears-Haack body.
The closer cross-sectional profile of an object to the cross-sectional
profile of Sears-Haack body, the less wave drag it introduces.
That is an essence of Whitcomb area rule.
Bill's department makes a lot of computer simulations to study missile's aerodynamic properties
before it is even built. To approximate missile's cross-sectional profile one
takes samples of S(z0) for integer arguments z0 from zmin
to zmax.
Your task is to find the area S(z0) for each integer
z0 from zmin to zmax, inclusive, given the description of the missile.
The description of the missile
is given to you as a set of points. The missile is the minimal convex
solid containing all the given points. It is guaranteed that there are
four points that do not belong to the same plane.
Input file format
The first line of the input file contains three integer numbers:
n, zmin and zmax.
The following n lines contain three integer numbers each: x, y, and z coordinates
of the given points. All coordinates do not exceed 100 by their absolute values.
No two points coincide. There are four points that do not belong to the same plane.
Output file format
For each integer z0 from zmin to zmax, inclusive, output one floating
point number: the area S(z0).
The area must be precise to
at least 5 digits after decimal point.
Задана начальная позиция в игре Ним. Определите, кто победит при оптимальной игре обоих игроков.
Формат входного файла
Во входном файле содержится число N — количество Ним-куч.
Далее следует N чисел ai — величина каждой кучи.
Формат выходного файла
В выходной файл выведите число 1, если выиграет первый игрок, 2 — если выиграет второй.
В случае, если позиция выигрышна для первого игрока,
выведите количество вариантов оптимального первого хода.
Правила игры "Ним с делением" такие же, как у игры Ним,
но на каждом шаге игрок выбирает кучу и либо берет из нее произвольное
количество спичек, либо делит эту кучу на две непустые.
Вычислите, кто выиграет при оптимальной игре.
Формат входного файла
Во входном файле содержится число N — количество Ним-куч.
Далее следует N чисел ai — величина каждой кучи.
Формат выходного файла
В выходной файл выведите число 1, если выиграет первый игрок, 2 — если выиграет второй.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
2 сек
Входной файл:
word.in
Ограничение памяти:
256 Мб
Выходной файл:
word.out
Условие
В наши дни предоставление поверхностей заборов и стен промышленных зданий
рекламодателям — уже не оригинальный способ получить дополнительный заработок,
а нечто само собой разумеющееся.
Небольшая компания «Домострой» также решила
выйти на этот рынок и стала предлагать место для рекламы на своих блоках заборов.
Блок представляет собой параллелепипед размером 1 × 1 × L,
на одной из сторон которого есть место для рекламы — пространство
размера 1 × L, в которое можно вписать ровно L букв латинского алфавита.
К сожалению, иногда сделки у компании срывались,
и заранее подготовленные блоки с рекламой отправлялись на склад.
Со временем там скопилось приличное количество блоков различных типов
(блоки разных типов отличаются друг от друга только надписью),
поэтому было решено использовать их вторично.
Была предложена следующая идея: если поставить несколько блоков друг на друга
и закрасить ненужные буквы, то, читая сверху вниз и слева направо,
можно будет прочитать какой-нибудь другой текст, как показано на рисунке.
Таким образом, можно получить рекламную надпись для нового клиента.
При этом из эстетических соображений при прочтении конечной надписи
разрывы в виде закрашенных букв недопустимы.
После того, как некоторое число K блоков, каждый из которых имеет длину L,
поставили друг на друга, получилась прямоугольная таблица размером K × L,
в каждой клетке которой находится буква латинского алфавита.
Каждый рекламный блок соответствует строке этой таблицы.
Теперь содержимое этой таблицы выписывается по столбцам, начиная с самого левого.
При этом в каждом столбце буквы выписываются сверху вниз.
В случае, изображенном на рисунке, в результате этого процесса получилась бы строка
TOEIIZENITKN.
Необходимо, чтобы рекламная надпись, требуемая заказчику,
входила в получившуюся строку как подстрока TOEIIZENITKN.
Требуется написать программу, которая будет определять,
какое минимальное количество блоков надо использовать,
чтобы получить рекламную надпись, необходимую заказчику.
При этом можно считать, что на складе блоков каждого типа неограниченно много.
Система оценивания
Решения, правильно работающие только для N ≤ 5, будут оцениваться из 50 баллов.
Формат входного файла
Первая строка входного файла входного файла содержит
два натуральных числа N и L — число различных типов блоков на складе
и длина каждого блока соответственно.
Последующие N строк содержат по одной записи длиной L,
состоящей из строчных латинских букв — надписи на блоках соответствующего типа.
Надписи на блоках разных типов не совпадают.
Последняя строка входного файла содержит новую рекламную надпись s —
строку, состоящую только из строчных латинских букв.
Можно считать, что на складе находится неограниченное число блоков каждого типа.
Формат выходного файла
В первой строке выходного файла необходимо
вывести натуральное число K — минимальное количество блоков,
которое нужно использовать для составления новой рекламы.
Следующая строка должна содержать K чисел — номера типов блоков,
которые нужно для этого использовать, перечисляя их сверху вниз.
Типы блоков нумеруются с единицы в порядке их задания во входном файле.
Если ответов несколько, выведите любой из них.
Если решения не существует, выведите в выходной файл число − 1.
Scientists of the Nearsea Institute of Underwater Mythology are researching
the mythical creature called Cthulhu.
Bill is working in a secret laboratory. He is developing missiles for
national security projects. Bill is the head of the aerodynamics department.
