Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 148 149 150 151 152 153 154 >> Отображать по:
#944
Cамый дешевый путь
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

Вводятся два числа \(N\) и \(M\) — размеры таблицы (\(1\le N\le20\), \(1\le M\le20\)). Затем идет \(N\) строк по \(M\) чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100).

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

Выведите минимальный вес еды в килограммах, отдав которую можно попасть в правый нижний угол.

Примеры
Входные данные
5 5
1 1 1 1 1
3 100 100 100 100
1 1 1 1 1
2 2 2 2 1
1 1 1 1 1
Выходные данные
11
#945
Шашку - в дамки
  
Источники: [ Личные олимпиады, Олимпиады сайта, 2009, Задача O ]

На шахматной доске (8x8) стоит одна белая шашка. Сколькими способами она может пройти в дамки?

(Белая шашка ходит по диагонали. на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.)

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

Вводятся два числа от 1 до 8: номер столбца (считая слева) и номер строки (считая снизу), где изначально стоит шашка.

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

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

Примеры
Входные данные
3 7
Выходные данные
2
Входные данные
1 8
Выходные данные
1
Входные данные
3 6
Выходные данные
4
#946
Ход конем
  

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить ТОЛЬКО на две клетки вниз и на одну клетку вправо, либо на две клетки вправо и на одну клетку вниз (смотри рисунок).

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

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

В первой строке входного файла находятся два натуральных числа N и M (1 ≤ N, M ≤ 50).  

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

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

Примеры
Входные данные
4 4
Выходные данные
2
#950
База данных
  

Ценные бумаги на фондовом рынке характеризуются множеством параметров. У них есть цена и ликвидность, также оценивать динамичность изменения цены, среднюю прибыльность, потенциал роста прибыльности и др. показатели. Аналитики трейдовой компании "WebMarket" ввели специальный показатель надежности ценной бумаги и научились эффективно его оценивать. Большое значение этого показателя соответствует малому риску покупки ценной бумаги. Но с ростом надежности обычно падает среднее оцениваемое значение прибыльности.

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

Ценные бумаги в базе данных имеют три атрибута:

  • code — непустая строка латинских символов и цифр длины 30 или меньше
  • id — целочисленный идентификатор (начиная с 0)
  • reliability — целое число из диапазона \([-2^{31}, 2^{31})\).

Каждой новой ЦБ выдается следующий по порядку id и значение её надёжности устанавливается в 0. Если ценная бумага отзывается с рынка, ее id для новых бумаг не используется.

База данных получает запросы, которые позволяют вводить новые ЦБ на рынок, получать текущую информацию о ЦБ, отзывать ЦБ с рынка, менять значение надежности у ЦБ и находить ЦБ, которая стоит на n-м месте, если упорядочить ЦБ по убыванию надежности, а при одинаковых значениях по возрастанию идентификатора.

При добавлении ЦБ с кодом, который раньше встречался, но соответствующая ЦБ была отозвана с рынка, ей назначается новый идентификатор.

Входные данные
Первая строка входа содержит число запросов \(N\). (\(1 \le N \le 100\,000\)). Затем идут \(N\) строк, каждая из которых содержит один запрос. Запросы бывают 4 типов:
  • ISSUE code: добавить новую ЦБ code в базу данных, или вывести информацию о ЦБ, если она уже есть в базе
    • если ЦБ code существует, то вывести EXISTS id reliability
    • если ЦБ code не существует, то вывести CREATED id 0
  • DELETE code: удалить ЦБ code из базы
    • если ЦБ code существует, то вывести OK id reliability
    • если ЦБ code не существует, то вывести BAD REQUEST
  • RELIABILITY code reliability: увеличить количество очков ЦБ, гарантируется, что значение останется в диапазоне \([-2^{31}, 2^{31})\).
    • если ЦБ code существует, то вывести OK id new_reliability
    • если ЦБ code не существует, то вывести BAD REQUEST
  • FIND n: найти n-ю ЦБ (начиная с 0)
    • если база не пуста, найти ЦБ, которая имела бы порядковый номер n (нумерация начинается с 0), если все ЦБ упорядочить сначала по убыванию баллов, а группы ЦБ с одинаковыми баллами упорядочить по времени их добавления (то есть по возрастанию id); а если n больше, чем количество ЦБ в базе, то найти последнюю ЦБ в этом порядке; для обоих случаев вывести OK code id reliability
    • если база пуста, то вывести EMPTY

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

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

Примеры
Входные данные
17
ISSUE aaa
FIND 10
ISSUE bbb
ISSUE ccc
RELIABILITY aaa 10
RELIABILITY bbb 30
RELIABILITY ccc 20
RELIABILITY xxx 20
FIND 1
FIND 2
FIND 0
ISSUE eee
ISSUE fff
FIND 3
FIND 111
DELETE bbb
FIND 0
Выходные данные
CREATED 0 0
OK aaa 0 0
CREATED 1 0
CREATED 2 0
OK 0 10
OK 1 30
OK 2 20
BAD REQUEST
OK ccc 2 20
OK aaa 0 10
OK bbb 1 30
CREATED 3 0
CREATED 4 0
OK eee 3 0
OK fff 4 0
OK 1 30
OK ccc 2 20
#952
ДКА
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Описание автомата задаётся в следующей форме. Сначала задаётся функция перехода автомата. Функция перехода задаётся в виде троек CUR CHAR NEW, где CUR — идентификатор исходного состояния — произвольная символьная строка, не содержащая пробельные символы. CHAR — символьная строка длиной ровно 1 символ. NEW — идентификатор целевого состояния — произвольная символьная строка, не содержащая пробельные символы. Элементы описания перехода могут отделятся друг от друга произвольным количеством пробельных символов. Описание функции перехода завершается строкой "END" в качестве идентификатора исходного состояния. Элементы CHAR и NEW отсутсвуют.

Далее перечисляются заключительные состояния автомата. Каждое состояние — это символьная строка. Список состояний завершается символьной строкой "END". Далее задаётся начальное состояние автомата — символьная строка. Затем задаётся проверяемое слово — символьная строка. Все элементы входного файла могут отделяться друг от друга произвольным количеством пробельных символов. Можете предполагать, что входные данные корректны, то есть удовлетворяют спецификации и действительно задают детерминированный конечный автомат.

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

Результат работы автомата должен быть напечатан в следующем виде. Сначала напечатайте число 1, если данный автомат допускает данную цепочку, и 0 в противном случае. Затем напечатайте количество символов, прочитанных во входной цепочке к моменту принятия автоматом решения. Наконец, напечатайте идентификатор состояния, в котором в данный момент находился автомат.

Примеры
Входные данные
S a S
END
S END
S
aaaa
Выходные данные
1
4
S
Входные данные
S a S
END
S END
S
aaaba
Выходные данные
0
3
S
Страница: << 148 149 150 151 152 153 154 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест