Темы
    Информатика(2656 задач)
---> 42 задач <---
Источники --> Личные олимпиады --> Нижегородская олимпиада школьников
Страница: 1 2 3 4 5 6 7 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

Игра будет состоять в том, что игрок будет управлять автобусом, перемещающимся по городу. В первой версии игры город будет представлять собой прямоугольное поле размера $N\times M$ клеток, каждая из которых либо занята зданием, либо свободна (т.е. по ней проходит дорога). Автобус игрока может перемещаться лишь по дорогам, но не по зданиям.

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

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

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

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

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

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

На первой строке входного файла находятся два числа $N$ и $M$ — количество строк и столбцов игрового поля соответственно ($1\leq N, M\leq 500$). Далее следуют $N$ строк, описывающих поле. В каждой строке находятся ровно $M$ символов, каждый из которых может быть или “#” (решётка, ASCII-код 35), или “.” (точка). Решётка обозначает клетку со зданием, точка — свободную клетку.

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

В выходной файл выведите $N$ строк по $M$ символов в каждой: для клеток, в которых находятся здания, выводите “#”, для клеток, где игрок может побывать не более одного раза — “X” (латинская заглавная буква X), для остальных клеток — “.”.

Примечание

Если ваша программа будет работать при $N,M\leq 100$, то вы получите как минимум 50 баллов.

Если ваша программа будет работать при $N,M\leq 250$, то вы получите как минимум 60 баллов.

Примеры
Входные данные
4 12
.#....#.##..
.##.#.#.##..
......####..
.##.#.#.####
Выходные данные
X#X...#X##..
X##.#.#X##..
XXX...####..
X##X#X#X####
Входные данные
3 2
##
##
##
Выходные данные
##
##
##
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Дядя Фёдор, кот Матроскин и Шарик решили обновить забор вокруг своего сада в Простоквашино. Матроскин и Шарик, недолго думая, вкопали $N$ столбов вдоль одной из сторон участка. Это очень сильно расстроило Дядю Фёдора, так как его друзья забыли о самом главном — калитка должна находиться именно на этой стороне, и для неё необходимо было оставить проём шириной как минимум $W$. Теперь им придётся выкапывать некоторые столбы.

Чтобы работа не пропадала даром, выкопать надо как можно меньше столбов. Помогите Дяде Фёдору определить, какие именно столбы надо выкопать. После выкапывания столбов должен найтись промежуток (между двумя оставшимися столбами, или между оставшимся столбом и концом стороны участка, или между двумя концами стороны участка) ширины больше или равной $W$.

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

Первая строка содержит два целых числа $N$ и $W$ — количество вкопанных столбов и минимально необходимую ширину проёма для калитки соответственно. Гарантируется, что $0 \leq N \leq 30\,000$ и что $0 \leq W \leq 60\,000$.

Будем считать, что вдоль интересующей нас стороны участка введена ось координат. Во второй строке входного файла находятся два числа $L$ и $R$ — координаты левого и правого конца этой стороны ($L < R$). Далее следуют $N$ чисел — координаты вкопанных столбов. Все координаты (включая $L$ и $R$) — различные целые числа, по модулю не превосходящие $30\,000$. Гарантируется, что все столбы вкопаны между левым и правым концами стороны.

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

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

Если решений несколько, то вы можете вывести любое. Если решения нет, то выведите в выходной файл одну строку, содержащую число -1.

Примеры
Входные данные
3 2
2 6
3 4 5
Выходные данные
1
2
Входные данные
3 2
1 6
4 3 5
Выходные данные
0
Входные данные
3 5
1 7
5 3 4
Выходные данные
3
2
1
3
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Пусть нам дано натуральное число $N$. Рассмотрим множество различных целых чисел $\{a_1, a_2, \dots, a_k\}$, где каждое число лежит в интервале от $0$ до $N-1$ включительно. Назовём такое множество свободным от сумм, если в этом множестве не найдётся таких трёх чисел, что сумма двух из них сравнима с третьим по модулю $N$. Строго говоря, назовём множество свободным от сумм, если для каждой тройки (не обязательно различных) индексов $x$, $y$ и $z$ ($1\leq x,y,z\leq k$) выполняется неравенство: $$(a_x+a_y) \bmod N \neq a_z$$

где $p \bmod q$ — остаток от деления $p$ на $q$.

Например, при $N=6$ множествами, свободными от сумм, не являются, например, $\{0\}$ (т.к. $(0+0)\bmod 6=0$), $\{1,2\}$ (т.к. $(1+1) \bmod 6=2$), $\{3,4,5\}$ (т.к. $(4+5)\bmod 6=3$), но множество $\{1,3,5\}$ является свободным от сумм.

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

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

Во входном файле находится одно целое число $N$. Гарантируется, что $1\leq N\leq 35$.

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

В выходной файл выведите одно число — ответ на задачу.

Примечание

Все множества, свободные от сумм, для $N=6$ — это следующие: $\{5\}$, $\{4\}$, $\{3\}$, $\{3,5\}$, $\{3,4\}$, $\{2\}$, $\{2,5\}$, $\{2,3\}$, $\{1\}$, $\{1,5\}$, $\{1,4\}$, $\{1,3\}$, $\{1,3,5\}$, $\{\}$ (последнее множество — пустое, т.е. не содержащее ни одного элемента, с $k=0$ — тоже считается свободным от сумм).

Примеры
Входные данные
2
Выходные данные
2
Входные данные
6
Выходные данные
14
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

Есть бесконечный резервуар с водой и два пустых сосуда объёмом 5 и 12 литров. Можно наливать воду из резервуара в любой сосуд до его заполнения, переливать воду из —одного сосуда в другой до заполнения второго или опустошения первого (смотря что будет раньше) и выливать воду из сосуда на землю до полного опустошения сосуда. Как таким образом можно отмерить 3 литра?

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

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

Во входном файле находятся три целых числа — $V_1$, $V_2$ и $V$ — объёмы двух сосудов и объем воды, который нужно отмерить. Гарантируется, что $1\leq V_1,V_2\leq 32767$ и $0\leq V\leq \max(V_1,V_2)$.

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

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

  • если это действие — переливание из одного сосуда в другой, то первое число должно быть номером сосуда, откуда надо переливать воду, а второе — номером сосуда, куда переливать;
  • если это действие — набор воды из резервуара, то первое число должно быть нулём, а второе  — номером сосуда, куда наливать;
  • если это действие — выливание воды “на землю”, то первое число должно быть номером сосуда, а второе — нулём.

После выполнения всех операций хотя бы в одном сосуде должна находиться вода в объёме $V$.

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

Если решений не существует, выведите одно число -1.

Примеры
Входные данные
5 12 3
Выходные данные
10
0 1
1 2
2 1
1 2
0 1
1 0
0 1
1 2
0 1
1 2
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

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

На первой строке входного файла находится число $K$ — количество тестов во входном файле. Далее идёт описание $K$ тестов. Каждый тест задаётся описанием двух многоугольников, которые надо проверить на пересечение. Каждый многоугольник задаётся в следующем формате: сначала указывается одно число $N_i$ — число вершин этого многоугольника, после чего идут $N_i$ строк, каждая из которых содержит два разделённых пробелом числа $x_{ij}$ и $y_{ij}$ — координаты $j$-й вершины этого многоугольника. Вершины перечислены в порядке обхода многоугольника.

Число пар многоугольников в одном тесте $1 \leq K \leq 10$, число вершин каждого многоугольника $3 \leq N_i \leq 100$, координаты вершин — целые числа, $|x_{ij}|, |y_{ij}| \leq 10\,000$.

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

Для каждой пары многоугольников выведите в выходной файл на отдельной строке одно слово: “YES”, если многоугольники пересекаются, и “NO”, если нет.

Примеры
Входные данные
2
3
0 0
-1 0
0 -1
3
1 1
2 1
1 2
4
0 0
2 0
2 2
0 2
4
1 1
3 1
3 3
1 3
Выходные данные
NO
YES

Страница: 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест