Темы --> Информатика --> Алгоритмы --> Эвристические методы
---> 29 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 6 >> Отображать по:
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
Задается число, состоящее из N единиц. Требуется вывести квадрат этого числа.

Найдите квадрат числа, десятичная запись которого состоит из $n$ единиц.

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

Входной файл содержит единственное число $n$ (1 ≤ $n$ ≤ $10^5$).

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

Выведите искомый квадрат.

Примеры
Входные данные
2
Выходные данные
121
Входные данные
9
Выходные данные
12345678987654321
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

Недавно на уроке информатики ученики одного из классов изучили булевы функции. Напомним, что булева функция $f$ сопоставляет значениям двух булевых аргументов, каждый из которых может быть равен 0 или 1, третье булево значение, называемое результатом. Для учеников, которые выразили желание более подробно изучать эту тему, учительница информатики на дополнительном уроке ввела в рассмотрение понятие цепного вычисления булевой функции $f$.

Если задана булева функция $f$ и набор из $N$ булевых значений $a_1,a_2,\ldots,a_N$, то результат цепного вычисления этой булевой функции определяется следующим образом:

* если $N=1$, то он равен $a_1$;

* если $N>1$, то он равен результату цепного вычисления булевой функции $f$ для набора из $(N-1)$ булевого значения $f(a_1,a_2),a_3,\ldots,a_N$, который получается путём замены первых двух булевых значений в наборе из $N$ булевых значений на единственное булево значение — результат вычисления функции $f$ от $a_1$ и $a_2$.

Например, если изначально задано три булевых значения: $a_1=0$, $a_2=1$, $a_3=0$, а функция $f$ — ИЛИ (OR), то после первого шага получается два булевых значения — (0 OR 1) и 0, то есть 1 и 0. После второго (и последнего) шага получается результат цепного вычисления, равный 1, так как 1 OR 0 = 1.

В конце дополнительного урока учительница информатики написала на доске булеву функцию $f$ и попросила одного из учеников выбрать такие $N$ булевых значений $a_i$, чтобы результат цепного вычисления этой функции был равен единице. Более того, она попросила найти такой набор булевых значений, в котором число единиц было бы как можно бо́льшим.

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

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

Первая строка входного файла содержит одно натуральное число $N$ ($2\le N\le100\,000$).

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

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

В выходной файл необходимо вывести строку из $N$ символов, определяющих искомый набор булевых $a_i$ с максимально возможным числом единиц. Если ответов несколько, требуется вывести любой из них. Если такого набора не существует, выведите в выходной файл фразу «No solution».

Пояснения к примерам

В первом примере процесс вычисления цепного значения булевой функции $f$ происходит следующим образом: $1011\to111\to01\to1$

Во втором примере вычисление цепного значения булевой функции $f$ происходит следующим образом: $11111\to0111\to111\to01\to1$

В третьем примере получить цепное значение булевой функции $f$, равное 1, невозможно.

Примеры
Входные данные
4
0110
Выходные данные
1011
Входные данные
5
0100
Выходные данные
11111
Входные данные
6
0000
Выходные данные
No solution
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Задача на перекрашивание.
<з>Дан прямоугольник $m \times n$, клетки которого раскрашены в три цвета. Можно выбрать квадрат $2 \times 2$ и, если в нем какой-то цвет преобладает,
перекрасить весь этот квадрат $2 \times 2$ в этот цвет.
Если в нем по две клетки двух цветов, то все его клетки можно
перекрасить в третий цвет. Требуется такими операциями
перекрасить весь прямоугольник в один цвет.

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

Числа $m$, $n$ ($3 \le m, n \le 100$) и раскрашенный прямоугольник.
Прямоугольник задается набором из $m$ строк, в каждой из которых
$n$ символов $R$, $G$ или $B$.

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

Последовательность перекрашиваемых квадратов (не более $10mn$ операций),
по одному перекрашиванию в строке. Каждое перекрашивание задается
парой чисел - номером строки и столбца левого верхнего квадрата в перекрашиваемом прямоугольнике.

                                                                                                  
Input
4 4
RBRR
GRGG
RRGB
GRRG
Output

1 1
1 2
1 3
3 1
2 2
2 3
3 3
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
+структуры данных

В этой задаче не будет идти речь о Бердяндии, о дорогах или авиарейсах. Здесь не будет надоевших монет. Речь пойдет о простой квадратной матрице.

В квадратную матрицу A порядка n были вписаны числа от 1 до n2, каждое по одному разу. Затем для каждого числа была записана пара чисел topi,j и lefti,j, где topi,j это количество чисел в столбце j стоящих выше числа Ai,j и одновременно больших него, а lefti,j это количество чисел в строке i стоящих левее числа Ai,j и одновременно больших него.

Вам заданы матрица top и left. Ваша задача состоит в нахождении возможной матрицы A, соответствующей входным данным.

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

В первой строке входного файла записано целое число n (1 ≤ n ≤ 600), где n это порядок искомой матрицы. Далее во входном файле записана пара матриц top и left, в виде n строк по n чисел в каждой строке. Матрицы разделены пустой строкой.

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

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

Примеры
Входные данные
3
0 0 0
0 0 0
0 0 2

0 0 0
0 1 0
0 1 2
Выходные данные
1 2 6
5 3 7
9 8 4
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes
1 1 0 1

Юная любительница ювелирных изделий Октябрина к празднику 4-го ноября хочет подарить своей лучшей подруге Тракторине ожерелье из n черных и розовых жемчужин.

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

Ось симметрии делит ожерелье на непрерывные части, содержащие одинаковое число жемчужин. При этом, если ось проходит через какую-то жемчужину, то она относится к обеим частям, если же ось проходит между двух жемчужин, то эти жемчужины находятся в разных частях. Таким образом, следующие ожерелья имеют ось симметрии:

Ваша задача – помочь Октябрине найти необходимую расстановку жемчужин.

Входные данные
Первая и единственная строка входного файла содержит единственное число n (2 ≤ n ≤ 1000) – требуемое количество жемчужин в ожерелье.

Выходные данные
Если искомой расстановки не существует, выведите в выходной файл единственное число –1, иначе выведите n целых чисел – расстановку жемчужин. Розовой жемчужине соответствует число 0, черной – число 1.

Примечание.

Расстановка жемчужин в первом примере:

Примеры
Входные данные
6
Выходные данные
0 0 1 0 1 1
Входные данные
3
Выходные данные
-1

Страница: << 1 2 3 4 5 6 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест