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

Бумажная полоска разделена на N клеток. Двое играющих по очереди выбирают и зачёркивают ровно K пустых смежных клеток. Выигрывает сделавший последний ход. Оба игрока придерживаются правильной стратегии. Дана ситуация игры. Требуется определить, кто выиграет.

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

Ограничения:1 <= K <= N <= 40.

В первой строке содержатся числа N и K, во второй строке N символов: латинская заглавная O - пустая клетка, латинская заглавная X - зачёркнутая клетка.

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

Вывести одно число: 1, если выиграет первый, сделавший ход; 2, если выиграет второй; 0, если ход сделать нельзя.

Примеры
Входные данные
1 1
O
Выходные данные
1
Входные данные
2 1
OO
Выходные данные
2
Входные данные
3 1
OOO
Выходные данные
1
Входные данные
38 1
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
Выходные данные
2
#668
Граница многоугольника
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Ограничения: 3 <= N <= 100 000, координаты вершин целые и по модулю не превосходят 1 000 000 000.

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

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

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

Вывести одно число - количество точек с целочисленными координатами на границе многоугольника.

Примеры
Входные данные
8
5 15
15 5
15 -5
5 -15
-5 -15
-15 -5
-15 5
-5 15
Выходные данные
80
#669
Путь спелеолога
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Ограничения: 1 <= N <= 30.

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

В первой строке содержится число N. Далее следует N блоков. Блок состоит из пустой строки и N строк по N символов: # - обозначает клетку, заполненную камнями, точка - свободную клетку. Начальное положение спелеолога обозначено заглавной буквой S. Первый блок представляет верхний уровень пещеры, достижение любой свободной его клетки означает выход на поверхность. Выход на поверхность всегда возможен.

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

Вывести одно число - длину пути до поверхности.

Примеры 

Ввод 1
3

###
###
.##

.#.
.#S
.#.

###
...
###
Вывод 1
6
Комментарий 1
Нужно спуститься на уровень вниз,
сделать два движения на запад,
подняться на уровень вверх,
сделать движение на юг,
подняться на уровень вверх.

#672
Провода
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дано N отрезков провода длиной L1, L2, ..., LN сантиметров. Требуется с помощью разрезания получить из них K равных отрезков как можно большей длины, выражающейся целым числом сантиметров. Если нельзя получить K отрезков длиной даже 1 см, вывести 0.

Ограничения: 1 <= N <= 10 000, 1 <= K <= 10 000, 100 <= Li <= 10 000 000, все числа целые.

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

В первой строке находятся числа N и К. В следующих N строках - L1, L2, ..., LN, по одному числу в строке.

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

Вывести одно число - полученную длину отрезков.

Примеры
Входные данные
4 11
802
743
457
539
Выходные данные
200
#675
Гомер Симпсон
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Обеденный перерыв Гомера Симпсона составляет \(T\) миллисекунд. Один гамбургер Гомер съедает за \(N\) миллисекунд, один чизбургер - за \(M\). Какое количество гамбургеров и чизбургеров нужно съесть, чтобы потраченное время было как можно больше, не превышая \(T\). При равенстве потраченного времени необходимо максимизировать суммарное количество съеденных гамбургеров и чизбургеров.

Ограничения: \(1 \le M, N, T \le 1 000 000\), все числа целые.

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

В первой строке находятся три числа - \(M\), \(N\) и \(T\), разделённые пробелами.

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

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

Примеры
Входные данные
1 2 1000
Выходные данные
1000
Входные данные
2 1 1000
Выходные данные
1000
Страница: << 120 121 122 123 124 125 126 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест