Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 419 420 421 422 423 424 425 >> Отображать по:
#111250
Битва титанов
  
Темы: [Перебор]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Саша увлекается программированием компьютерных игр. Вот уже три для он пишет новую игру для сотового телефона под названием "Битва титанов". Героями игрушки являются оловянные солдатики. В качестве прототипа для описания действий оловянного солдатика Саша взял шахматную ладью.

Шахматная ладья - это фигура, которая может перемещаться на любое количество клеток по вертикали или горизонтали. Ладьи не могут перемещаться за препятствия. Задача - вычислить максимальное количество ладей, которые можно поставить на доске так, чтобы никакие две не били друг друга. Это означает, что конфигурация правильна при условии, что никакие две ладьи не находятся на одной горизонтали или вертикали в пределах видимости друг друга.

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

Помогите Саше поскорее закончить программу и вычислите максимальное количество ладей на заданной конфигурации доски.

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

Во входном файле в первой строке содержится натуральное число \(N\) - размер доски, не превышающий 4. Следующие \(N\) строк содержат по \(N\) символов — описание шахматной доски, причем символ '.' указывает пустую клетку, а символ верхнего регистра 'X' указывает препятствие. Во входном файле нет пробелов.

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

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

Примеры
Входные данные
4
.X..
....
XX..
....
Выходные данные
5
#111253
Гистограмма
  
Темы: [Стек]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Гистограмма является многоугольником, сформированным из последовательности прямоугольников, выровненных на общей базовой линии. Прямоугольники имеют равную ширину, но могут иметь различные высоты. Например, фигура слева показывает гистограмму, которая состоит из прямоугольников с высотами 2, 1, 4, 5, 1, 3, 3. Все прямоугольники на этом рисунке имеют ширину, равную 1.

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

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

В первой строке входного файла записано число \(N\) (\(0\) < \(N\) ≤ \(10^6\)) - количество прямоугольников гистограммы. Затем следует \(N\) целых чисел \(h_1 ... h_n\), где \(0\) ≤ \(h_i\) ≤ \(10^9\). Эти числа обозначают высоты прямоугольников гистограммы слева направо. Ширина каждого прямоугольника равна \(1\)

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

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

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

Задана последовательность цифр. Определите, можно ли расставить между некоторыми из них знаки "+" и "-", так чтобы получилось заданное число \(M\), но никакие промежуточные вычисления не превосходили по модулю \(10000\).

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

Входные данные содержат две строки: в первой строке - натуральное число \(M\)≤\(20000\), во второй строке - последовательность цифр. Длина входной последовательности не превышает \(200\) символов.

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

Выведите одно слово YES или NO в зависимости от того, есть решение у задачи или нет.

Примеры
Входные данные
2009
20009
Выходные данные
YES
Входные данные
10
000000050049000
Выходные данные
YES
#111267
Сортировка
  
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
6 megabytes

Учительница по программированию задала Вовочке задачу — отсортировать массив из N чисел от 1 до N по возрастанию :). Вовочка поступает так: он просматривает массив слева направо, и, если замечает два элемента, стоящих рядом, таких, что правый меньше левого, он меняет их местами. Так он поступает, пока массив не будет отсортирован. Но Вовочка — очень ленивый ученик. В какой-то момент ему надоело сортировать числа, и он решил посчитать, сколько ещё описанных выше обменов нужно сделать. Помогите ему.

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

В первой строке входного файла находится натуральное число N (1 ≤ N ≤ 1 000 000). Во второй строке через пробел находятся N различных целых чисел, каждое из которых не меньше 1 и не больше N.

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

Выведите одно число — искомое количество обменов. Так как ответ может быть очень большим и сложным, выведите его по очень простому модулю 2.

Примеры тестов

Входные данные
5
1 2 5 4 3
Выходные данные
1

#111270
Поливальная машина
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
6 megabytes

Город N, в отличие от города M, расположен на склоне одного холма. Чистоту улиц этого города обеспечивает единственная поливальная машина. Бензин нынче дорог, поэтому движение муниципального транспорта «в гору» признано слишком расточительным.

Карта города представляет собой прямоугольник, разбитый на H × W клеток, где H и W — высота и ширина карты в клетках соответственно. Часть клеток заняты зданиями, остальные соответствуют улицам и площадям, которые и требуется помыть.

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

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

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

В первой строке входного файла находятся натуральные числа H и W — высота и ширина карты города (1 ≤ W ≤ 1 000, 1 ≤ H ≤ 1 000). В следующей строке расположено единственное натуральное число K — номер столбца клетки первой строки, в которой поливальная машина начинает движение (1 ≤ K ≤ W). Гарантируется, что эта клетка свободна от зданий.

Каждая из следующих H строк содержит W символов ‘|#|’ и ‘.’, означающих, соответственно, клетки со зданиями и без.

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

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

Примеры тестов

Входные данные
8 8
7
..#....#
##..#...
...#..#.
.##..#..
..#.#...
#.#.#...
#.#...##
##..####
Выходные данные
21 23

Страница: << 419 420 421 422 423 424 425 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест