Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 72 73 74 75 76 77 78 >> Отображать по:
#587
Симпатичные узоры
  
Источники: [ Командные олимпиады, ВКОШП, 2000, Задача E ]
Прямоугольное поле заполнено белыми и черными клетками, требуется определить количество вариантов замощения поля таким образом, чтобы на нем не встречалось ни одного белого или черного квадрата 2 на 2.

Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узор из черных и белых плиток, каждая из которых имеет размер 1×1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника M×N метров.

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

Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата 2×2 метра, полностью покрытого плитками одного цвета. На рисунке 1 показаны примеры различных симпатичных узоров, а на рисунке 2 - несимпатичных.

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

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

В первой строке входных данных содержатся два положительных целых числа, разделенных пробелом: \(M\) и \(N\) (1 <= \(M\)·\(N\) <= 30).

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

Выведите единственное число - количество различных симпатичных узоров, которые можно выложить во дворе размера \(M\)×\(N\) . Узоры, получающиеся друг из друга сдвигом, поворотом или отражением, считаются различными.

Примеры
Входные данные
1 2
Выходные данные
4
Входные данные
4 1
Выходные данные
16
#588
Кубики
  
Источники: [ Командные олимпиады, ВКОШП, 2000, Задача F ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Даны кубики с 6 буквами написанными на них и слово. Требуется составить слово из кубиков.

Родители подарили Пете набор детских кубиков. Поскольку Петя скоро пойдет в школу, они купили ему кубики с буквами. На каждой из шести граней каждого кубика написана буква.

Теперь Петя хочет похвастаться перед старшей сестрой, что научился читать. Для этого он хочет сложить из кубиков ее имя. Но это оказалось довольно сложно сделать - ведь разные буквы могут находиться на одном и том же кубике и тогда Петя не сможет использовать обе буквы в слове. Правда одна и та же буква может встречаться на разных кубиках. Помогите Пете!

Дан набор кубиков и имя сестры. Выясните, можно ли выложить ее имя с помощью этих кубиков и если да, то в каком порядке следует выложить кубики.

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

В первой строке вводится число \(N\) (1 <= \(N\) <= 100) - количество кубиков в наборе у Пети. Во второй строке задано имя Петиной сестры - слово, состоящие только из больших латинских букв, не длиннее 100 символов. Следующие N строк содержат по 6 букв (только большие латинские буквы), которые написаны на соответствующем кубике.

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

В первой строке выведите "YES" если выложить имя Петиной сестры данными кубиками можно, "NO" в противном случае.

В случае положительного ответа, во второй строке выведите \(M\) различных чисел из диапазона 1…\(N\), где \(M\) - количество букв в имени Петиной сестры. \(i\)-е число должно быть номером кубика, который следует положить на \(i\)-е место при составлении имени Петиной сестры. Кубики нумеруются с 1, в том порядке, в котором они заданы во входных данных. Если решений несколько, выведите любое. Разделяйте числа пробелами.

Примеры
Входные данные
2
AB
AAAAAB
AAAAAA
Выходные данные
YES
2 1
Входные данные
3
ANNY
AAAAAA
NNNNNN
YYYYYY
Выходные данные
NO
#590
Похожие матрицы
  
Источники: [ Командные олимпиады, ВКОШП, 2000, Задача H ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Необходимо по данной матрице построить матрицу, у которой сумма строк и столбцов совпадает с суммами исходной матрицы, все числа кратны заданному P, а также отличаются от соответствующих чисел исходной матрице не более, чем на P.

Рассмотрим таблицу, состоящую из \(N\) строк и \(M\) столбцов. Если в каждой ячейке такой таблицы стоит целое число, назовем такую таблицу целочисленной матрицей. Скажем, что эта матрица кратна чиcлу \(p\), если все числа в ее ячейках кратны \(p\).

Рассмотрим теперь суммы элементов матрицы по строкам и столбцам соответственно. Обозначим сумму чисел \(i\)-й строки за \(H_i\), а сумму чисел \(j\)-го столбца за \(V_j\). Упорядоченный набор чисел (\(H_1\), \(H_2\), …, \(H_N\), \(V_1\), \(V_2\), …, \(V_M\)) назовем профилем матрицы. Скажем, что матрица почти кратна \(p\), если все числа, входящие в ее профиль, кратны \(p\). Почти кратная 5 матрица и ее профиль изображены на рисунке 1.

Если две матрицы \(A\) и \(B\) имеют одинаковый размер, причем элемент, стоящий на пересечении \(i\)-й строки и \(j\)-го столбца в матрице \(A\) отличается от соответствующего элемента матрицы \(B\) не более чем на \(p\), скажем, что \(A\) отличается от \(B\) не более чем на \(p\). Скажем, что матрица \(B\) похожа на матрицу \(A\) относительно числа \(p\), если
1. отличается от не более чем на \(p\)
2. профили \(B\) и \(A\) совпадают.
На рисунке 2 изображены две похожие относительно числа 5 матрицы, первая из них почти кратна 5, а вторая кратна 5. Третья матрица на рисунке 2 тоже кратна 5, но непохожа на первую (хотя похожа на вторую).

Дано число p и почти кратная p матрица A. Ваша задача - найти такую матрицу B, чтобы она была кратна p и похожа на A относительно p.

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

В первой строке входных данных задаются целые числа \(p\) (1 <= \(p\) <= 10), \(N\) и \(M\) (1 <= \(N\), \(M\) <= 30). Следующие \(N\) строк содержат по \(M\) целых неотрицательных чисел, не превышающих 1000, которые являются элементами исходной матрицы \(A\).

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

Выведите матрицу \(B\) по строкам - сначала \(M\) элементов первой строки, затем \(M\) элементов второй, и т. д. Разделяйте числа пробелами и/или переводами строк. Заботиться о красивом форматировании таблицы не надо. Если искомой матрицы не существует, выведите единственное число - "-1". Если решений несколько, выведите любое из них.

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

Вася нарисовал выпуклый \(N\)-угольник и провел в нем несколько диагоналей таким образом, что никакие две диагонали не пересекаются внутри \(N\)-угольника. Теперь он утверждает, что весь \(N\)-угольник оказался разбит на треугольники. Напишите программу, которая проверяет истинность Васиного утверждения.

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

Сначала вводятся числа \(N\) - количество вершин \(N\)-угольника (3 <= \(N\) <= 1000) и \(M\) - количество диагоналей, проведенных Васей. Далее на вход программы поступают \(M\) пар чисел, задающих диагонали (каждая диагональ задается парой номеров вершин, которые она соединяет). Гарантируется, что каждая пара чисел задает диагональ (то есть две вершины различны и не являются соседними), а также что никакие две пары не задают одну и ту же диагональ. Никакие две диагонали не пересекаются внутри \(N\)-угольника. Вершины \(N\)-угольника нумеруются числами от 1 до \(N\).

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

Если Васино утверждение верно, то программа должна выводить единственное число 0. В противном случае необходимо вывести сначала число \(K\) - количество вершин в какой-нибудь не треугольной части. Далее должно быть выведено \(K\) чисел - номера вершин исходного \(N\)-угольника, которые являются вершинами этой \(K\)-угольной части в порядке обхода этой части.

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

Палиндром - это строка, которая читается одинаково как справа налево, так и слева направо.

На вход программы поступает набор больших латинских букв (не обязательно различных). Разрешается переставлять буквы, а также удалять некоторые буквы. Требуется из данных букв по указанным правилам составить палиндром наибольшей длины, а если таких палиндромов несколько, то выбрать первый из них в алфавитном порядке.

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

В первой строке входных данных содержится число \(N\) (1 <= \(N\) <= 100000). Во второй строке задается последовательность из \(N\) больших латинских букв (буквы записаны без пробелов).

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

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

Группы тестов

25 баллов — (1 ≤ N ≤ 10) .

25 баллов — (1 ≤ N ≤ 1 000 ) .

50 баллов — полные ограничения.

Примечание

Сложность работы программы должна быть O(n). Использование встроенной сортировки(sort, sorted), алгоритмов сортировки пузырёк/quick sort/merge sort и других запрещено!



Примеры
Входные данные
3
AAB
Выходные данные
ABA
Входные данные
6
QAZQAZ
Выходные данные
AQZZQA
Входные данные
6
ABCDEF
Выходные данные
A
Страница: << 72 73 74 75 76 77 78 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест