Страница: << 25 26 27 28 29 30 31 >> Отображать по:
#1635
Альтернативные пути
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Будем снисходительными к Путнику, считая «хорошими» не только пути, на которых в точности достигается максимально возможная сумма, а еще и пути, сумма которых отличается от максимальной не более чем на \(K\).

Количество «хороших» путей гарантированно не превышает \(10^9\).

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

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

Первая строка входного файла содержит три целых числа \(M\) (2≤\(M\)≤200), N (2≤\(N\)≤200) и \(K\) (0≤\(K\)≤200). Каждая из последующих \(M\) строк содержит \(N\) чисел, записанных в соответствующих клеточках.

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

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

Примеры
Входные данные
2 3 3
1 9 7
2 5 3
Выходные данные
20
2
#1669
Отчет
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Заданы две последовательности чисел: объем продукции и процент брака. Требуется найти наибольшую подпоследовательность, в которой объем продукции растет, а процент брака падает.

Один из цехов завода производит продукцию в течение \(N\) месяцев. Начальнику цеха было поручено составить отчет о росте производительности данного цеха и об уменьшении доли некачественной продукции в процентном соотношении (точность доли процента до одного знака после запятой, например, 2/7=0.(285714) ≈ 28.6%). При этом в отчет должна войти информация как можно за большее число месяцев \(K\) (\(K\) ≤ \(N\)) работы цеха. Начальник цеха решил, что он включит в отчет данные только по тем месяцам (не обязательно взятым подряд, но обязательно в хронологическом порядке), по которым наблюдается строгий рост количества производимой продукции и строгий спад доли бракованных товаров по сравнению с данными предыдущего месяца, вошедшего в отчет. Определить, какое максимальное количество месяцев удовлетворяет этим условиям и сколько есть возможных вариантов составления отчета.

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

Первая строка файла содержит число \(N\) (1 ≤ \(N\) ≤ 40) - количество месяцев работы цеха. Далее следует N строк, содержащих целые числа \(v_i\) (1 ≤ \(v_i\) ≤ 10000) и \(b_i\) (1 ≤ \(b_i\) ≤ \(v_i\)); \(v_i\) - объем продукции, произведенной цехом за \(i\)-ый месяц; \(b_i\) - количество бракованной продукции в \(i\)-ом месяце.

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

Первая строка файла содержит число \(K\) - количество месяцев, по которым будет включена в отчет информация о работе цеха. Вторая строка содержит число \(P\) - количество возможных вариантов составления отчета с максимальным содержанием.

Примеры
Входные данные
10
313 100
313 106
442 106
442 104
475 104
475 102
539 102
539 109
682 109
682 111
Выходные данные
5
32
#1699
Распознавание изображений
  

Новый проект Екатерины посвящен распознаванию изображений. При этом она решила применить инновационный подход, основанный на нанотехнологиях. Начать Екатерина решила с простого. Она выбрала d изображений, которые называются «цифрами» от \(0\) до \(d-1\). Каждое изображение представляет собой прямоугольник \(w\) на \(h\), заполненный белыми и черными квадратиками (назовем их пикселами). Все картинки различны (т.е. отличаются хотя бы одним пикселом).

Наноробот размещается в левом верхнем углу изображения и начинает выполнять программу, записанную на специальном языке программирования, описание которого приведено ниже. Задача робота состоит в том, чтобы понять, на какую из d картинок он помещен.

Язык программирования для наноробота содержит следующие команды:

'U', 'D', 'L', 'R' – команды перемещения вверх, вниз, влево и вправо соответственно. Если робот выходит за пределы изображения — программа считается ошибочной.

'(' ':' ')' - условный оператор. Робот смотрит на цвет пиксела, на котором он стоит. Если пиксел белый, то выполняется subprogram_w, если черный — subprogram_b.

'0', '1', …, '9' – команда распознавания. Робот должен выполнить одну из этих команд, когда он узнает, на каком изображении он расположен. После этой команды выполнение программы завершается.

Каждое перемещение занимает одну наносекунду. Выполнение условного оператора или оператора распознавания происходит мгновенно.

Ирина заинтересована в правильных программах. Т.е. если робот помещается на картинку, соответствующую цифре \(i\), то программа должна завершиться вызовом команды 'i'.

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

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

Первая строка содержит три целых числа \(d, h\) и \(w (1 ≤ d, h, w ≤ 10)\) – количество изображений, высота и ширина изображений соответственно.

В следующих строках содержатся d описаний изображений. Каждое описание состоит из \(h\) строк по \(w\) символов в каждой. Символы могут быть двух типов: 'B' и 'W' и обозначать черный и белый пиксел соответственно.

Изображения даются в порядке от \(0\) до \(d-1\). Описания изображений разделены пустой строкой.

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

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

Примеры
Входные данные
3 5 4
WBBW
BWWB
BWWB
BWWB
WBBW

WWBW
WBBW
BWBW
WWBW
WWBW

WBBW
BWWB
WWBW
WBWW
BBBB
Выходные данные
D(1:D(2:0))
#1709
Страх и ненависть в Вес-Лагасе
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В Вес-Лагасе построили новый отель. В отеле бесконечное количество номеров (отелей с конечным количеством номеров для гостей Вес-Лагаса не хватает).

Гости Вес-Лагаса очень суеверные: они испытывают страх перед числом 13 и ненавидят номера, в десятичной записи которых присутствует это число. Поэтому в отеле нет комнат, которые содержат 13 в записи своего номера. Например, в отеле нет комнат с номерами 13, 132, 913, 1308, 1313. Требуется определить, какой номер имеет N-я по счету комната.

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

Входной файл содержит несколько тестовых блоков. Первая строка содержит число T (1 ≤ T ≤ 100) – количество тестовых блоков.

Каждая из следующих T строк описывает один тестовый блок и содержит единственное число N 
(\(1 \leq N \leq 10^{18}\)).

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

Выведите ответ для каждого тестового блока в отдельной строке.

Примеры
Входные данные
3
20
150
1
Выходные данные
21
162
1
#1720
НОВП
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Входные данные

Во входном файле записаны две последовательности. Каждая последовательность описывается двумя строками следующим образом: в первой строке идет длина последовательности \(M\) (1 \(\le\) \(M\) \(\le\) 500), во второй идут \(M\) целых чисел \(a_i\) (\(−2^{31}\) \(\le\) \(a_i\) < \(2^{31}\)) – члены последовательности. Нужно найти возрастающую последовательность наибольшей длины, являющейся подпоследовательностью обоих данных последовательностей.

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

В первой строке выходного файла выведите \(N\) - длину наибольшей общей возрастающей подпоследовательности.

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

Примеры
Входные данные
5
1 4 2 5 -12
4
-12 1 2 4
Выходные данные
2
1 2
Страница: << 25 26 27 28 29 30 31 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест