---> 405 задач <---
Страница: << 35 36 37 38 39 40 41 >> Отображать по:
#1650
  
Темы: [Потоки]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

Формат входных данных

Первая строка входного файла содержит пять натуральных чисел N, M, w, b, g. 1≤N, M70 – высота и ширина картины, 1≤w,b,g1000 – цена рисования одного белого единичного квадрата, черного единичного квадрата и серой линии единичной длины, соответственно. Далее следует N строк, каждая из которых состоит из M литер. Литера B соответствует черному квадрату, а W – белому.

Формат выходных данных

Единственная строка выходного файла должна содержать одно целое число, которое есть минимальной суммой затрат на улучшение картины.

Примеры
Входные данные
3 2 10 12 1
BW
WB
BW
Выходные данные
7
ограничение по времени на тест
0.3 second;
ограничение по памяти на тест
64 megabytes

 Маленький мальчик делает бусы. У него есть много пронумерованных бусинок. Каждая бусинка имеет уникальный номер – целое число в диапазоне от 1 до N. Он выкладывает все бусинки на полу и соединяет бусинки между собой произвольным образом так, что замкнутых фигур не образуется. Каждая из бусинок при этом оказывается соединенной с какой-либо другой бусинкой.
Требуется определить, какое максимальное количество последовательно соединенных бусинок присутствует в полученной фигуре (на рисунке эти бусинки выделены темным цветом).

Формат входных данных

В первой строке – количество бусинок 1≤N≤2500. В последующих N-1 строках по два целых числа – номера, соединенных бусинок.

Формат выходных данных

Вывести одно число – искомое количество бусинок.

Пример

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

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

7

4 5

6 7

7 4

7 2

1 3

4 1

5

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

Суперчислом называется число, являющееся суммой двух простых чисел из диапазона [2…\(B\)]. Требуется найти все суперчисла из заданного диапазона [\(A\)…\(B\)].

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

Во входном файле даны два числа \(A\) и \(B\) (2 ≤ \(A\) ≤ \(B\) ≤ 40000), определяющие диапазон [\(A\)…\(B\)].

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

В выходной файл вывести все найденные суперчисла из заданного диапазона в возрастающем порядке.

Примеры
Входные данные
3 10
Выходные данные
4
5
6
7
8
9
10
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes

Дано \(N\) натуральных чисел. Требуется для каждого числа найти количество вариантов разбиения его на сумму двух других чисел из данного набора.

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

В первой строке дано число \(N\) ( 1 ≤ \(N\) ≤ 10000). Далее заданы \(N\) натуральных чисел, не превосходящих \(10^9\). Для каждого числа количество разбиений меньше 231.

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

Вывести \(N\) чисел – количество разбиений, в порядке, соответствующем исходному.

Примеры
Входные данные
5 
3
3
2
2
1
Выходные данные
2
2
0
0
0
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На плоскости задано N (1 ≤ N ≤ 30) супермногоугольников (без пересечений и самопересечений). Каждый супермногоугольник задаётся координатами своих Ki (3 ≤ Ki ≤ 30, 1 ≤ iN) вершин в порядке обхода против часовой стрелки. Все координаты — целые числа из диапазона -32000..32000. Требуется соединить супермногоугольники М отрезками так, чтобы:

  1. Oтрезок соединяет только пару супермногоугольников.

  2. Суммарная длина отрезков была минимальна.

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

Формат входных данных

В первой строке число N. В следующих N строках. Число Ki и Ki пар чисел – координаты вершин.

Формат выходных данных

В первой строке число М и сумма длин найденных отрезков с точностью 10-3. В следующих М строках числа L1 X1 Y1 L2 X2 Y2 – номера супермногоугольников и координаты концов отрезков с точностью 10-3.

Примеры

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

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

2

3 1 0 2 0 1 1

4 6 5 7 5 7 6 6 6

1 6.364

1 1.500 0.500 2 6.000 5.000

3

3 0 0 1 0 0 1

4 5 5 6 5 6 6 5 6

3 0 5 1 6 0 6

2 8.000

3 1.000 6.000 2 5.000 6.000

1 0.000 1.000 3 0.000 5.000


Страница: << 35 36 37 38 39 40 41 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест