Поразрядная сортировка(1 задач)
--->
3 задач
<---
Петя разгадывает головоломку, которая устроена следующим образом. Дана квадратная таблица размера NxN, в каждой клетке которой записана какая-нибудь латинская буква. Кроме того, дан список ключевых слов. Пете нужно, взяв очередное ключевое слово, найти его в таблице. То есть найти в таблице все буквы этого слова, причем они должны быть расположены так, чтобы клетка, в которой расположена каждая последующая буква слова, была соседней с клеткой, в которой записана предыдущая буква (клетки называются соседними, если они имеют общую сторону — то есть соседствуют по вертикали или по горизонтали). Например, на рисунке ниже показано, как может быть расположено в таблице слово olympiad.
| P | O | L | T | E |
| R | W | Y | M | S |
| O | A | I | P | T |
| B | D | A | N | R |
| L | E | M | E | S |
Когда Петя находит слово, он вычеркивает его из таблицы. Использовать уже вычеркнутые буквы в других ключевых словах нельзя.
После того, как найдены и вычеркнуты все ключевые слова, в таблице остаются еще несколько букв, из которых Петя должен составить слово, зашифрованное в головоломке.
Помогите Пете в решении этой головоломки, написав программу, которая по данной таблице и списку ключевых слов выпишет, из каких букв Петя должен сложить слово, то есть какие буквы останутся в таблице после вычеркивания ключевых слов.
В первой строке входного файла записаны два числа N (1N10) и M (0M200). Следующие N строк по N заглавных латинских букв описывают ребус. Следующие M строк содержат слова. Слова состоят только из заглавных латинских букв, каждое слово не длиннее 200 символов. Гарантируется, что в таблице можно найти и вычеркнуть по описанным выше правилам все ключевые слова.
В единственную строку выходного файла выведите в любом порядке буквы, которые останутся в таблице.
5 3 POLTE RWYMS OAIPT BDANR LEMES OLYMPIAD PROBLEM TEST
AENRSW
Выпуклый N-угольник разбит непересекающимися диагоналями на треугольники. (Многоугольник называется выпуклым, если любая его диагональ лежит внутри него.) Требуется покрасить каждую сторону и каждую проведенную диагональ в красный или синий цвет так, чтобы у каждого треугольника были стороны как красного, так и синего цвета.
Требуется привести любую из допустимых раскрасок.
В первой строке записано одно число N (4N100) - количество вершин многоугольника.
Далее следуют N–3 строки, в каждой из которых записана пара натуральных чисел — номера вершин, которые соединяет диагональ. Считается, что все вершины занумерованы последовательно натуральными числами от 1 до N.
В выходном файле должны быть 2N–3 строки. Каждая строка содержит 3 числа: номера вершин, которые соединяет данная сторона или диагональ и цвет (1 - синий, 2 - красный), в который Вы красите данную сторону или диагональ.
Возможный ответ на перый тест:
3 4 1
2 3 2
1 2 1
1 3 2
1 4 1
Возможный ответ на второй тест:
5 6 1
4 5 2
3 4 1
3 5 2
2 3 1
1 2 2
1 3 1
1 5 2
1 6 1
4 1 3
6 1 3 3 5 5 1
Помимо открыток Петя и Вася решили устроить одноклассницам чаепитие и заразили своей идеей еще K–2 своих друзей. Они собрались вместе и выбрали в одном довольно известном супермаркете P тортиков. Настал черед рассчитываться за них.
В магазине есть N работающих касс, занумерованных числами от 1 до N. Про i-ю кассу известно, что кассиру требуется Ai единиц времени на обработку одного товара и Bi единиц времени для того, чтобы рассчитаться с покупателем. Обойдя все кассы, школьники посчитали, что на обслуживание покупателей, уже стоящих в i-ю кассу, уйдет Ti единиц времени.
Теперь Петя и Вася задались вопросом, в какие кассы надо встать им и их друзьям (в каждую из выбранных касс должен стоять хотя бы один из них, и каждый из них может стоять не более, чем в одну кассу, поэтому суммарно они могут стоять не более чем в K касс) и сколько тортиков каждый должен взять, чтобы последний из них вышел из магазина как можно раньше. Некоторые из ребят могут в кассу не стоять, а, отдав все тортики другим, выйти через специальный выход для тех, кто ничего не купил.
Напишите программу, которая определит это минимальное время.
В первой строке записано одно число N — количество касс в супермаркете (1 ≤ N ≤ 100000). В следующих N строках записано по три числа Ai, Bi, Ti (0 ≤ Ai, Bi, Ti ≤ 100000). В последней строке записаны два числа — K и P — число школьников и покупок у них соответственно (0 ≤ P ≤ 100000, 2 ≤ K ≤ 100000).
Все числа во входном файле целые.
Выведите минимальное время выхода последнего школьника из магазина.
Комментарии к примерам тестов
Здесь лучше всего встать в обе кассы и купить там по одному тортику.
Выгоднее всего одному из школьников встать со всеми тортиками в первую кассу, а остальным выйти без покупок.
Частичные ограничения
Первая группа состоит из тестов, в которых N ≤ 10 и оценивается в 30 баллов.
Вторая группа состоит из тестов, в которых N ≤ K ≤ 100000 и оценивается в 30 баллов.
Третья группа состоит из тестов без дополнительного ограничения и оценивается в 40 баллов.
2 100 10 40 10 100 50 2 2
160
3 1 2 0 5 2 1 2 10 1 3 5
7