Тексты задач для тренировочных интернет-туров по информатике для размещения на сайте school-collection. edu. ru (стр. 7 )

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

Необходимо вывести п целых чисел — для каждого города 1, если им будет править первый принц, 2 — если второй, 0 — если оба. Если ответов несколько, можно выводить любой из них. Ответ существует для любых корректных входных данных.

Пример

Задача D. Тетрис

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 3 секунды

Ограничение по памяти: 256 мебибайт

Напомним известную задачу, связанную с игрой в Тетрис.

В процессе игры в Тетрис связные фигуры (т. е. связные, если идти по 4-м направлениям) падают вниз в колодец из N строк и 20 столбцов. Каждая фигура помечена уникальной буквой английского алфавита от “A” до “Z”.

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

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

Первая строка входного файла содержит целое число N (0 ≤ N ≤ 50 ) – количество строк в колодце. Каждая из следующих строк содержит по 20 символов, каждый из которых – это либо буква от “A” до “Z”, либо символ “.” (ASCII 46), обозначающий пустую клетку.

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

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

Входной файл содержит несколько тестов. Каждый тест дан в следующем формате: число N (1 ≤ N ≤ 50) и N строк из 20 символов каждая. Символы могут иметь ASCII коды от 32 до 127.

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

Для каждого теста необходимо вывести слово YES или N0 — корректен тест или нет. Тест считается корректным, если выполнены все следующие условия:

•  используются только символы “A... Z” и “.”;

•  фигура (т. е. множество всех клеток с некоторой буквой) образует связную область;

•  никакая фигура не “висит в воздухе”;

•  фигуры действительно могли упасть в таком порядке.

Подзадача 1

Дополнительные упрощения:

•  сумма N по всем тестам не превышает 500,

•  каждый символ будет либо буквой "А", либо точкой “.”.

Решение оценивается в 25 баллов.

Подзадача 2

Дополнительные упрощения:

• сумма N по всем тестам не превышает 5 000,

• во входных данных не будет никаких других букв, кроме “A” и “B”.

Решение оценивается в 25 баллов.

Подзадача 3

Сумма N по всем тестам не превышает 50000.

Решение оценивается в 25 баллов.

Подзадача 4

Сумма N по всем тестам не превышает 500000.

Решение оценивается в 25 баллов.

Пример

7.  Описание заданий для седьмого интернет-тура

На седьмом туре было предложено 4 задачи: задача A «Построить граф», задача B «А где матроид?», задача C «Планеты и звезды» и задача D «Двойной шифр». Тексты задач представлены ниже.

Задача A. Построить граф

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мебибайт

Нужно построить неориентированный невзвешенный граф из N вершин и не более, чем М ребер, в котором число кратчайших путей из вершины 1 в вершину N максимально. Кратные рёбра и петли запрещены.

Ваша программа должна реализовать функцию BuildGraph(N, M, а, Ь), которая строит и возвращает оптимальный граф (2 ≤ N, 1 ≤ М). Здесь N и М —количество вершин и количество рёбер в графе, а а и b — массивы, в которые нужно сохранить концы рёбер графа. Ребра можно записывать в произвольном порядке. Концы каждого ребра следует возвращать в паре ячеек (a[i],b[i]). Если вы хотите использовать меньше, чем М рёбер, вместо неиспользованных рёбер запишите пары (-1,-1). Вершины нумеруются числами от 1 до N. Если оптимальных ответов несколько, можно вернуть любой из них.

Подзадача 1 (баллы: 15)

Ограничения: N ≤ 7; в каждом тесте функция BuildGraph будет вызываться для одного N и всех М от 1 до N·(N–1)/2.

Подзадача 2 (баллы: 10)

Ограничения: М = N·(N–1)/2; подзадача состоит из одного теста, в котором функция BuildGraph будет вызываться для всех N от 2 до 30.

Подзадача 3 (баллы: 25)

Ограничения: N ≤ 12; в каждом тесте функция BuildGraph будет вызываться для одного N и всех М от 1 до N·(N–1)/2.

Подзадача 4 (баллы: 60)

Ограничения: N ≤ 30; в каждом тесте функция BuildGraph будет вызываться для одного N и всех М от 1 до N·(N–1)/2.

Пример

Задача B. А где матроид?

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мебибайт

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

Необходимо реализовать функцию, которая сообщает количество способов удаления из графа r рёбер так, чтобы он перестал быть связным. Трудность состоит в том, что в граф иногда могут добавлять рёбра. Гарантируется, что в процессе работы граф всё время будет оставаться кактусом.

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

•  init (n, m, х, у) – он будет вызван один раз в начале запуска программы. Число п обозначает количество вершин в графе, m – количество рёбер в графе. Здесь х и y – массивы концов рёбер, каждый имеет размер m, i-ое ребро соединяет вершины х[i] и у[i], для всех i от 0 до m – 1. Вершины графа нумеруются, начиная с нуля. В графе нет петель и кратных рёбер.

•  add (u, v) – добавление в текущий граф ребра между вершинами и и v. Эта функция будет вызвана не более 2·105 раз.

•  getCount () – запрос искомого количества способов для текущего графа. Поскольку количество способов может быть велико, следует возвращать ответ по модулю 109 + 7. Эта функция также будет вызвана не более 2·105 раз.

Примеры

Подзадача 1 (баллы: 20)

Ограничения: 1 ≤ п ≤ 100. Функция add (u, v) не будет вызываться.

Подзадача 2 (баллы: 20)

Ограничения: 1 ≤ п ≤ 2000. Функция add (u, v) не будет вызываться.

Подзадача 3 (баллы: 30)

Ограничения: 1 ≤ п ≤ 100 000. Функция add (u, v) не будет вызываться.

Подзадача 4 (баллы: 30)

Ограничения: 1 ≤ п ≤ 100 000.

Задача C. Планеты и звезды

Ограничение по времени: 2 секунды

Ограничение по памяти: 256 мебибайт

Однажды наивный Фрай из нашей вселенной и злой Фрай из параллельной вселенной получили доступ к устройству Профессора, которое могло передвигать звёзды и планеты. Злой Фрай решил уничтожить п планет следующим образом: он начинает передвигать звезду с номером i к планете с номером i (так получилось, что количество планет и звёзд совпадает) со скоростью v, а наивный Фрай (он согласился помогать злому Фраю за конфеты) двигает с той же скоростью планету с номером i к звезде с номером i. Когда звезда и планета сталкиваются, они мгновенно аннигилируют (исчезают), а Фрай получает одну конфету. Проблема в том, что, если столкнутся звезда и планета с разными номерами, то возникнет чёрная дыра, которая засосёт всю галактику. Столкновение двух звёзд или двух планет, а также столкновение более чем двух объектов тоже приводит к возникновению чёрной дыры. Это невыгодно для всей галактики и для каждого из нас, в частности.

Можно считать, что планеты и звёзды — это точки на плоскости с целыми координатами, по модулю не превышающими 108, и никакие планеты и звёзды не совпадают. Помогите Фраю получить все п конфет как можно быстрее или определите, что уничтожение всех планет невозможно. Если вы начали двигать какие-то пары, то остановить их уже нельзя. Вы можете выбрать и в какие моменты времени запускать адский механизм Профессора для каждой пары. Время считается от первого запуска до того момента, когда все планеты уже уничтожены.

Для решения задачи необходимо написать программу, в которой реализована функция solution (n, х, у, v). Здесь n – это количество пар точек (1 ≤ п ≤ 105). Массивы х и у имеют длину 2п и задают координаты звёзд и планет: для всех i от 0 до п — 1. Пара (x[2i], y[2i]) – это координаты i-й звезды, а пара (x[2i + 1], y[2i + 1]) – координаты i - й планеты. Cкорости всех планет и звёзд одинаковы и равны v (1 ≤ v ≤ 108).

Функция должна возвращать как можно меньшее время, за которое Фрай может уничтожить все планеты, с относительной или абсолютной погрешностью 10-6, или число –1, если уничтожение всех планет невозможно.

Примеры

Подзадача 1 (баллы: 20)

Дополнительное ограничение: п ≤ 2.

Подзадача 2 (баллы: 20)

Дополнительное ограничение: п ≤ 50.

Подзадача 3 (баллы: 20)

Дополнительное ограничение: п ≤ 1000.

Подзадача 4 (баллы: 40)

Дополнительные ограничения отсутствуют.

Задача D. Двойной шифр

Ограничение по времени: 2 секунды