Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 118 119 120 121 122 123 124 >> Отображать по:
#652
Удаление клеток
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке находятся числа \(M\) и \(N\), в следующих \(M\) строках - по \(N\) символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана - точка. 1 <= \(M\), \(N\) <= 100.

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

Вывести одно число.

Примеры
Входные данные
5 10
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####
Выходные данные
5
#653
Несоставляемое число
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Даны N натуральных чисел. Найти минимальное натуральное число, не представимое суммой никаких из этих чисел, если в эту сумму каждое исходное число может входить не более одного раза.
Ограничения: 1 <= N <= 10 000, значения исходных чисел от 1 до 1 000 000 000.
Ввод: В первой строке находится число N, в следующих N строках - по одному натуральному числу.
Вывод: Вывести одно число.
Примеры 
Ввод 1    Ввод 2
4         4
1         1
1         2
1         4
5         8
Вывод 1   Вывод 2
4         16
#654
SMS
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Сообщения SMS сотового телефона MOBILA составлены из прописных латинских букв. Если буква первая на кнопке, нужно нажать эту кнопку один раз, чтобы добавить букву в сообщение. Если буква вторая - нужно нажать кнопку дважды и т.д. Так, чтобы набрать слово "SMS", нужно нажать

(PQRS)(PQRS)(PQRS)(PQRS)(MNO)(PQRS)(PQRS)(PQRS)(PQRS)

Чтобы ввести две буквы, находящиеся на одной кнопке, нужно между нажатиями клавиши сделать паузу. Например, чтобы ввести сообщение "AA", нужно нажать

(ABC)(пауза)(ABC)

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

(ABC)(ABC)(ABC)(ABC)(пауза)(ABC)

соответствует сообщению "CAA". К сожалению, сотовые телефоны этой модели давно не производятся, и остался только один такой телефон. Он может произвольно вставлять и игнорировать паузы во время ввода сообщения, что может привести к некоторым изменениям в сообщениях. Например, введя MOSCOWQUARTERFINAL, можно получить вместо этого OMSCMNWQTTARTERPDEINAL. Вы получили SMS-сообщение и знаете, что оригинальное сообщение содержало N букв. Чтобы определить вероятность угадывания оригинального сообщения, найдите число возможных сообщений, которые могли превратиться в то, которое Вы получили.

Мобила

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

В первой строке задана длина оригинального сообщения \(N\). Вторая строка содержит полученное SMS-сообщение. 1 <= \(N\) <= 80, полученное сообщение состоит только из прописных латинских букв, длина полученного сообщения - от 1 до 80 букв.

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

Вывести число сообщений из \(N\) букв, которые, будучи набранными на на этом телефоне, могут превратиться в данное сообщение.

Примеры
Входные данные
8
ADGJMPTW
Выходные данные
1
Входные данные
9
ADGJMPTW
Выходные данные
0
#655
Дерево игры
  
Темы: [Рекурсия]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Игра для двух игроков определяется её деревом. Соперники делают ходы по очереди. Первый игрок начинает игру. Игра кончается или вничью, или победой одного из игроков. Листья дерева этой игры могут иметь значения, равные одному из трёх чисел: +1 - победа первого игрока, -1 - победа второго игрока, 0 - ничья. Ваша задача - определить, кто выиграет, если оба противника следуют правильной стратегии.

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

Узлы дерева пронумерованы последовательными целыми числами. Корень дерева всегда имеет номер 1. Первая строка входного файла содержит целое \(N\) - число узлов в дереве игры. Следующая \(N\) - 1 строка описывает узлы - одна строка для каждого узла (за исключением первого). Вторая строка содержит описание второго узла дерева, третья - третьего узла и т.д. Если узел является листом, первый символ строки - \(L\), затем идёт пробел, затем номер родительского узла, ещё пробел и результат игры (+1 - победа первого игрока, -1 - победа второго, 0 - ничья). Если узел внутренний, то строка содержит N - первый символ, затем пробел и номер родительского узла. 2 <= \(N\) <= 1000.

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

Выводится +1, если выигрывает первый игрок, -1, если второй, и 0 - в случае ничейного исхода.

Пример

Примеры
Входные данные
7
N 1
N 1
L 2 -1
L 2 +1
L 3 +1
L 3 +1
Выходные данные
+1
Входные данные
7
N 1
N 1
L 2 -1
L 2 +1
L 3 +1
L 3 0
Выходные данные
0
Входные данные
7
N 1
N 1
L 2 -1
L 2 +1
L 3 +1
L 3 -1
Выходные данные
-1
#656
Дуга на сфере
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На поверхности планеты, являющейся шаром радиусом \(R\), заданы две точки своими широтой и долготой. Найти минимальную длину пути по поверхности этой планеты из одной точки в другую.

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

В первой строке находится число \(R\), во второй строке заданы широта и долгота первой точки, в третьей строке - широта и долгота второй точки. Широта в градусах от -90 до 90, долгота в градусах от -180 до 180, 100 <= \(R\) <= 10 000, все числа вещественные.

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

Вывести длину пути с двумя знаками после запятой.

Примеры
Входные данные
3437.5
-45 -45
45 -45
Выходные данные
5399.61
Страница: << 118 119 120 121 122 123 124 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест