Страница: << 43 44 45 46 47 48 49 >> Отображать по:
#3361
Bugs
  
ограничение по времени на тест
10.0 second;
ограничение по памяти на тест
64 megabytes

Ограничение по времени – 10 секунд.
Ограничение по памяти – 64 мегабайта.
Компания Bugs начинает выпуск планки оперативной памяти Q-RAM размером 6 террабайт. Каждая планка состоит из 6 квадратных микросхем в форме прямоугольника \(3\times 2\). В результате технологического процесса, используемого в компании Bugs, получается прямоугольная область, разделенная на \(N\times M\) квадратных микросхем. После этого микросхемы тщательно проверяются и битые микросхемы помечаются черным маркером.


После этого, область разрезается на отдельные планки размером \(3\times 2\)(или \(2\times 3\)). Естественно, ни одна планка не должна содержать битых микросхем. Может возникнуть такая ситуация, что не все хорошие микросхемы войдут в какую-либо планку. Однако для снижения себестоимости компания хочет изготовить из произведенной области как можно больше планок.
На вход вашей программе будет даваться размер области и список битых микросхем на ней. Для этой области вам необходимо определить максимальное количество планок, которое можно вырезать из нее.

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

Первая строка содержит три целых числа \(N\), \(M\) и \(K\) (\(1\leq N\leq 150\), \(1 \leq M \leq 10\), \(0 \leq K \leq M\times N\)), где \(N\) – длина области, \(M\) – ее ширина, а \(K\) – количество битых микросхем. Следующие K строк содержат описание битых микросхем. Каждая из них содержит координаты битой микросхемы в виде двух целых чисел \(x\) и \(y\) (\(1 \leq x \leq N\), \(1 \leq y \leq M\)).

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

Для каждой области выведите максимальное количество планок, которое может быть вырезано из нее на отдельной строке.

Примеры
Входные данные
6 6 5
1 4
4 6
2 2
3 6
6 4
Выходные данные
3
Входные данные
6 5 4
3 3
6 1
6 2
6 4
Выходные данные
4
#3363
Палиндромность
  

Напомним, что палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево. Например, палиндромами являются строки «abba» и «madam».
Для произвольной строки s введем операцию деления пополам, обозначаемую half(s). Значение half(s) определяется следующими правилами:
Если s не является палиндромом, то значение half(s) не определено;
Если s имеет длину 1, то значение half(s) также не определено;
Если s является палиндромом четной длины 2m, то half(s) — это строка, состоящая из первых m символов строки s;
Если s является палиндромом нечетной длины 2m + 1, большей 1, то half(s) — это строка, состоящая из первых m + 1 символов строки s.
Например, значения half(inforamatics) и half(i) не определены, half(аbbа) = ab, half(madam) = mad. Палиндромностью строки s будем называть максимальное число раз, которое можно применить к строке s операцию деления пополам, чтобы результат был определен.
Например, палиндромность строк «informatics» и «i» равна 0, так как к ним нельзя применить операцию деления пополам даже один раз. Палиндромность строк «abba» и «madam» равна 1, а палиндромноств строки «totottotot» равна 3, посколвку операция деления пополам применима к ней три раза:
«totottotot» —> «totot» —> «tot» —> «to».
Задана некоторая строка s. Необходимо изменить в ней минимальное число символов так, чтобы ее палиндромность стала равной k.

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

Первая строка входного файла содержит число k (\(0 \leq k \leq 20\)). Вторая строка входного фай­ла содержит непустую строку s, состоящую из строчных букв латинского алфавита. Ее длина не превосходит \(10^5\) символов.

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

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

Примеры
Входные данные
2
abaabc
Выходные данные
1
Входные данные
1
ababa
Выходные данные
1
Входные данные
2
aa
Выходные данные
-1
#3365
Дорожное движение
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

В городе Z в час пик очень оживленное движение. Неправильно выбранный маршрут может на долгое время задержать вас в пути. Вам известно, что схема города представляет собой N горизонтальных и M вертикальных односторонних дорог, образующих прямоугольник N-1 на M-1 километр. На пересечении каждой вертикальной и горизонтальной дороги находится перекресток, на котором можно изменить направление движения. Заметьте, что для изменения направления движения нужно сначала полностью затормозить.
Вы находитесь в точке (1, 1), или другими словами, в левом нижнем углу города. Движение происходит слева направо и снизу вверх. Вам необходимо добраться до точки (N, M) за наименьшее время. Проблема в том, что на каждой дороге свой скоростной режим и максимальное ускорение, которое можно развить, разное для каждой дороги (и равно, соответственно, \(A_i\) км/\(c^2\) для вертикальной дороги с номером i и \(B_j\) км/c2 для горизонтальной дороги с номером j). При этом скорость на дорогах не ограничена. Ускорение и торможение происходит по стандартным физическим законам.
Однако ваше преимущество состоит в том, что вы хорошо знаете город и можете попасть напрямую с перекрестка (i, j) на перекресток (i+1, j+1), в объезд главных дорог (перед этим также нужно полностью затормозить). Время, необходимое для этого, не зависит от номера перекрестка и равно C. Дороги пронумерованы в порядке, соответствующем направлению движения. Напомним, что движение на всех дорогах одностороннее.

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

В первой строке входного файла расположены числа \(N\), \(M\) и \(C\) (\(1 \leq N, M \leq 1000\), \(10^{-3} \leq C \leq 10\)). Далее, во второй и третьей строках расположены числа \(A_1\), ..., \(A_N\) и \(B_1\), ..., \(B_M\), соответственно (\(10^{-3} \leq A_i, B_i \leq 10\)).

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

В первой строке выходного файла выведите искомое время с восемью знаками после запятой. Во второй строке укажите количество перекрестков \(K\), через которые проходит маршрут, включая первый и последний. Далее, в \(K\) строчках выведите координаты соответствующих перекрестков. Выведите координаты только тех перекрестков, где нужно затормозить(учтите, что после каждого переезда по диагонали нужно затормозить).

Примеры
Входные данные
2 2 4.0
2.0 2.0
2.0 2.0
Выходные данные
2.82842712
3
1 1
1 2
2 2
#3372
Жадная волна
  
ограничение по времени на тест
0.2 second;
ограничение по памяти на тест
64 megabytes

Поле размером \(N\times M\) клеток заполнено целыми числами. Требуется найти на поле клетку, из которой волна, запущенная не более чем на \(K\) итераций, покроет площадь с максимальной суммой расположенных на ней чисел.
Пример распространения волны для поля размером \(5\times 4\). Волна запущена из клетки (3, 3) и была остановлена после трех итераций. Белые клетки – клетки, не покрытые волной, серые и черные – клетки, покрытые волной. Клетки, покрытые волной на последней итерации, отмечены серым цветом.

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

В первой строке входного файла содержатся три целых числа через пробел \(N\), \(M\) и \(K\) (\(1 \leq N, M \leq 100\), \(1 \leq K \leq N + M\)). Следующие \(N\) строк содержат по \(M\) чисел, каждое из которых не превосходит \(10000\) по абсолютной величине.

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

Выведите четыре числа \(R\), \(C\), \(P\) и \(S\), где \(R\) – номер строки, \(C\) – номер столбца, из которых следует запустить волну, \(P\) – количество итераций распространения волны, \(S\) – максимальная сумма чисел, покрытых волной. Если существует несколько вариантов ответа, то вывести любой, в котором число \(P\) минимально. \(1 \leq P \leq K\).

Оценка

Решение, верно работающее при \(N, M \leq 15\) будет получать 50 баллов. Эти баллы выставляются при прохождении всех тестов группы. В оставшихся тестах \(N, M \leq 100\), эта группа оценивается при прохождении всех тестов группы.

Примеры
Входные данные
5   4   3
1   2   3   4
1   6   7   8
9  10  11  12 
0   0   0   0
2   0   0   1
Выходные данные
3  3  3  66
#3374
Последовательность
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Известны первые \(k\) членов последовательности – \(a_1, a_2, \dots, a_k\) (\(0 \leq a_i \leq 9\), где \(i = 1, 2, \dots, k\)). Другие члены последовательности вычисляются по следующему правилу: \(a_i = \sum_{j=i-k}^{i-1}a_j\), то есть каждый следующий член равен сумме \(k\) предыдущих. Необходимо найти последние \(r\) цифр числа \(a_n\).

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

В первой строке входного файла находятся \(3\) целых числа – \(k\), \(n\) и \(r\) (\(1 \leq k \leq 20\), \(1 \leq n \leq 10^{18}\), \(1 \leq r \leq 9\)). В следующей строке находится \(k\) чисел – \(a_1, a_2, \dots, a_k\).

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

Первой строкой выходного файла выведите \(r\) цифр числа \(a_n\). Ведущие нули следует опустить.

Примечание

1. Тесты, в которых \(r = 1\), будут оцениваться 75 баллами:
1.1 Тесты, в которых \(n<10^6\), будут оцениваться 25 баллами.
1.2 Тесты, в которых \(n \geq 10^6\), будут оцениваться 50 баллами:
1.2.1 Тесты, в которых \(k < 7\), будут оцениваться 30 баллами.
1.2.2 Тесты, в которых \(6 < k < 11\), будут оцениваться 20 баллами.
2. Тесты, в которых \(r > 1\), будут оцениваться 25 баллами.

Примеры
Входные данные
2 5 1
1 2
Выходные данные
8
Входные данные
1 100001 1
5
Выходные данные
5
Страница: << 43 44 45 46 47 48 49 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест