Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 195 196 197 198 199 200 201 >> Отображать по:
#2867
Вслепую по лабиринту
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Это интерактивная задача.

Ваша цель — написать программу, управляющую роботом, идущим вслепую по лабиринту.

Лабиринт состоит из N на M (1 ≤ N, M ≤ 30) клеток. Каждая из клеток может быть свободной или заблокированной (непроходимой). Все клетки на границе лабиринта непроходимые. Робот начинает работу в свободной клетке, он может переместится на юг, запад, север или восток в свободную клетку. Робот не имеет оптических сенсоров, только сенсор удара, так что при попытке перемещения в заблокированную клетке сработает сенсор и робот останется в той же клетке.

Робот должен побывать во всех проходимых клетках лабиринта. Из начальной клетки гарантированно можно попасть во все достижимые клетки лабиринта.

Протокол интерактивного взаимодействия

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

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

Каждая строка выходных данных должна представлять собой команду для робота. Это должна быть одна из пяти возможных строк: SOUTH, WEST, NORTH, EAST, или DONE. Строка DONE должна быть напечатана после посещения роботом всех проходимых клеток. После вывода DONE программа должна завершать свою работу. Необходимо очищать выходной буфер после вывода каждой команды (flush).

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

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

Примеры

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

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

NORTH
EAST
SOUTH
EAST
SOUTH
WEST
SOUTH
WEST
NORTH
WEST
WEST
NORTH
EAST
NORTH
DONE

BLOCKED
BLOCKED
EMPTY
BLOCKED
BLOCKED
EMPTY
BLOCKED
BLOCKED
EMPTY
EMPTY
BLOCKED
BLOCKED
EMPTY
BLOCKED
#2868
Дерево?
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Имеется неориентированный граф, состоящий из N вершин и M ребер. Необходимо проверить, является ли граф деревом. Напомним, что дерево — это связный граф, в котором нет циклов (следовательно, между любой парой вершин существует ровно один простой путь). Граф называется связным, если от одной вершины существует путь до любой другой.

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

Во входном файле в первой строке содержатся два целых числа N и M (1 ≤ N ≤ 100, 0 ≤ M ≤ 1000), записанные через пробел. Далее следуют M различных строк с описаниями ребер, каждая из которых содержит два натуральных числа Ai и Bi (1 ≤ Ai <Bi ≤ N), где Ai и Bi — номера вершин, соединенных i-м ребром.

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

В выходной файл выведите слово YES, если граф является деревом или NO в противном случае.

Примеры
Входные данные
3 2
1 2
1 3
Выходные данные
YES
#2871
Вслепую по лабиринту
  

Это интерактивная задача.

Ваша цель — написать программу, управляющую роботом, идущим вслепую по лабиринту. Лабиринт состоит из N на M (1 ≤ N, M ≤ 30) клеток. Каждая из клеток может быть свободной или заблокированной (непроходимой). Все клетки на границе лабиринта непроходимые. Робот начинает работу в свободной клетке, он может переместится на юг, запад, север или восток в свободную клетку. Робот не имеет оптических сенсоров, только сенсор удара, так что при попытке перемещения в заблокированную клетке сработает сенсор и робот останется  в той же клетке. Робот должен побывать во всех проходимых клетках лабиринта. Из начальной клетки гарантированно можно попасть во все достижимые клетки лабиринта.

Протокол интерактивного взаимодействия

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

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

Каждая строка выходных данных должна представлять собой команду для робота. Это должна быть одна из пяти возможных строк: SOUTH, WEST, NORTH, EAST, или DONE. Строка DONE  должна быть напечатана после посещения роботом всех проходимых клеток. После вывода DONE программа должна завершать свою работу. Необходимо очищать выходной буфер после вывода каждой команды (flush).

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

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

Пример

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

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

NORTH
EAST
SOUTH
EAST
SOUTH
WEST
SOUTH
WEST
NORTH
WEST
WEST
NORTH
EAST
NORTH
DONE

BLOCKED
BLOCKED
EMPTY
BLOCKED
BLOCKED
EMPTY
BLOCKED
BLOCKED
EMPTY
EMPTY
BLOCKED
BLOCKED
EMPTY
BLOCKED
#2872
Дерево?
  

Имеется неориентированный граф, состоящий из \(N\) вершин и \(M\) ребер. Необходимо проверить, является ли граф деревом. Напомним, что дерево — это связный граф, в котором нет циклов (следовательно, между любой парой вершин существует ровно один простой путь). Граф называется связным, если от одной вершины существует путь до любой другой.

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

Во входном файле в первой строке содержатся два целых числа \(N\) и \(M\) (\(1 \le N \le 100\), \(0 \le M \le 1\,000\)), записанные через пробел. Далее следуют \(M\) различных строк с описаниями ребер, каждая из которых содержит два натуральных числа \(A_i\) и \(B_i\) (\(1 \le A_i < B_i \le N\)), где \(A_i\) и \(B_i\) — номера вершин, соединенных \(i\)-м ребром.

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

В выходной файл выведите слово «YES», если граф является деревом, или «NO» в противном случае.

Примеры
Входные данные
3 2
1 2
1 3
Выходные данные
YES
#2873
Бактерии
  

У юного биолога Антона в красивой стеклянной колбе живут n бактерий. Добавляя различные реактивы в колбу, Антон может контролировать число бактерий. Так, если p — некоторое простое число, то Антон умеет в домашних условиях получать вещество CpH2p+1OH, которое, будучи добавленным в колбу, уменьшает число бактерий ровно в p раз. Если же число бактерий не делилось на p, то результат действия вещества неопределен, и эксперимент теряет научную точность. Этого Антон допустить не желает, поэтому он применяет вещество CpH2p+1OH только когда число бактерий делится на p.

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

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

Во входном файле содержатся два натуральных числа n и m (1 ≤ n, m ≤ 109) — изначальное и желаемое число бактерий в колбе у Антона.

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

Если получить ровно m бактерий невозможно, выведите в выходной файл слово «Impossible».

Если же искомый результат достижим, выведите кратчайшую последовательность добавлений веществ, которая позволяет его достичь, в следующем формате: добавление вещества CpH2p+1OH кодируется числом p, добавление вещества C20H25N3O — числом 0. Числа должны быть разделены пробелами и/или переводами строк.

Если существует несколько кратчайших последовательной добавлений веществ, оставляющих m бактерий, выведите любую из них.

Примеры
Входные данные
12 18
Выходные данные
2 0 2
Входные данные
56 6
Выходные данные
Impossible
Страница: << 195 196 197 198 199 200 201 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест