A. Рагнарос и Нефариан играют в карты
Каждая карта существ характеризуется силой атаки и запасом здоровья. Атака - целое неотрицательное число, запас здоровья - натуральное число. Карты заклинаний очень разнообразны, поэтому будем считать единственным признаком карты-заклинания константу -1. У Рагнароса в руке N карт. Какова общая атака и запас здоровья карт-существ?
Дано: в первой строке число N (0< N <= 10) - количество карт в руке. Далее N строк, содержащих описание карт: атака и здоровье для карт-существ, число -1 для карт-заклинаний.
Определить и напечатать в одной строке через пробел общую силу атаки и запас здоровья карт-существ.
Разбор. Просто посчитать суммы. Заминку может вызвать чтение данных. Это можно сделать, например, так:
for (int i=0; i
cin>>a;
if (a!=-1){
cin>>h;
attack+=a;
health+=h;
}
}
B. Кто победил?
Рагнарос и Нефариан играют в карты. Каждая карта характеризуется силой атаки и запасом здоровья. Атака - целое неотрицательное число, здоровье - натуральное число. Схватились две карты, A - атакующая, B - защищающаяся. По результатам атаки у A уменьшается здоровье на величину атаки B, а у B уменьшается здоровье на величину атаки A.
Результат схватки может быть таким:
- A победила B, если после схватки сохранила часть здоровья, а B потеряла все свое здоровье;
- A проиграла B, если после схватки потеряла все свое здоровье, а B сохранила часть своего здоровья;
- обе карты погибли, если обе потеряли все свое здоровье;
- ничья: обе карты сохранили часть своего здоровья.
Дано: две строки. В первой строке значения атаки и здоровья карты A, во второй строке значения атаки и здоровья карты B.
Определить результат схватки карт и вывести его числом 1, 2, 3 или 4 в соответствии с условием задачи.
Разбор. Просто записать 4 условных оператора.
C. Защитники
Каждая карта, кроме стоимости (маны), атаки и здоровья, характеризуется тегом (провокация, предсмертный хрип, боевой клич и т.п.). У Рагнароса в руке есть несколько карт с провокацией (taunt) и он хочет знать сколько карт-провокаторов, дающих максимальное суммарное здоровье он может выложить на стол, имея M очков маны. Если максимальную суммарную мощь защиты можно обеспечить разным количеством карт, то взять наименьшее число.
Дано: в первой строке число - количество карт в руке. Далее N строк, содержащих 3 числа (мана, атака, защита) и строку-тег. Все числа записаны через пробел, строка отделена от чисел пробелом. Последняя строка - количество очков маны у Рагнароса.
Определить и напечатать минимальное количество карт, обеспечивающее максимальную защиту, и значение суммарной защиты.
Разбор. Сравнительно трудная задача. Жюри подобрало ограничения так, чтобы перебор не проходил по времени. Требуется динамическое программирования. Это вариант задачи о рюкзаке с дополнительным условием на минимальный набор карт. Читайте Т. Кормен и др. "Алгоритмы: построение и анализ".
D. Казакус
Нефариану пришла карта “Казакус”. С ее помощью можно создать необыкновенной силы заклинание, если в колоде нет одинаковых карт. Вам надо написать программу, проверяющую, все ли карты разные.
Дано: в первой строке число N (0 <= N <= 100000), далее N строк с названиями карт. Пожалуй нет. Упростим задачу для первокурсников. Далее N строк с кодами карт. Кодом является число в диапазоне от 1111 до 999999.
Напечатать “Make a spell”, если все карты разные, или “You can’t”, если нашлись одинаковые.
Разбор. Несложная задача. Первый курс мог бы и догадаться. Задачу на подсчет, сколько раз встречается каждая цифра в числе Пи (первые 500 цифр) решали. Так и здесь: организовать массив, индексами считать коды карт. Читаем карты, в ячейку с кодом карты записываем 1. Как только встретится карта, для которой в ячейке стоит 1, значит, такая карта повторная. Печатаем "You can’t" и останавливаем процесс. Да, не стоило копировать и вставлять этот текст. Если в процессе чтения единиц не встретилось до конца списка карт, значит, повторных нет.
E. Принц Малчезар - строитель стен
Страна демонов представляет собой бескрайнюю пустыню. Тут и там разбросаны порталы, укрепрайоны, просто замки высших демонов. На первый взгляд - хаотично. Но это не хаос, это строгий порядок.
После введения декартовой системы координат обнаруживается, что все поселения демонов располагаются внутри единичных квадратов, так что координаты i-го поселения задаются числами xi + 0.5 и yi + 0.5, где xi , yi — целые числа, i = 1, 2,..., n. Координаты всех поселений различны.
У правящей династии высших демонов принцев не меньше, чем у арабских шейхов. И этих принцев надо занять междоусобицей, чтобы не было времени подсидеть венценосного отца. Принцу Малчезару было поручено разделить страну на наделы стенами “от края до края”, параллельными осям координат. В каждом земельном наделе должно быть ровно одно поселение. Если стена параллельна оси Ox, то её y- координата должна быть целым числом, иначе x-координата должна быть целым числом. В обоих случаях соответствующие целые координаты по модулю не превышают 2 · 109 . Помогите принцу разделить страну, построив не более чем n − 1 стену. Стены могут пересекаться, а наделы имеют прямоугольную форму.
Разбор. Разделение королевства. Источник. Командный чемпионат СПБ 2013-2014.
Формально геометрия. Сортировка.
Идея простая. Отсортируем замки по x координате, между каждой парой соседних замков проведем прямую. Посмотрим на замки, которые имеют одинаковую координату по x. Для каждого такого x отсортируем замки по y координате. Проведем прямую между каждой парой соседних замков. Заметим, что при таком разделении, количество прямых не превышает n − 1.
Проблемой может быть сортировка. Квадратичная устойчивая сортировка не пройдет по времени, а быстрая сортировка неустойчива. Надо вдумчиво писать компаратор, или использовать устойчивый вариант сортировки.
F. Мерзоцид в гостях у мурлоков
Профессор Мерзоцид время от времени наведывается в Болота с целью изучения культуры мурлоков, которые там проживают. Недавно он был в гостях у племени Мертвожабрых. Профессор довольно быстро научился понимать их язык, изучил многие обряды, но никак не мог освоить систему счисления. Было понятно, что используется позиционная система счисления с основанием 10, но секрет числовых значений используемых цифр от профессора скрывали. Профессор обозначил цифры мурлоков буквами от ‘a’ до ‘j’. Чтобы определить значения цифр мурлоков, профессор отправился к алтарю Мертвожабрых. Там, в строгом секрете от чужаков, хранится священный камень с секретным списком n заклинаний, определяющих систему прокачки мурлоков. Известно, что заклинания представляют собой числа, записанные в системе счисления мурлоков и расположенные в порядке строгого возрастания. Способ записи чисел цифрами - слева направо. Помогите профессору восстановить по этому списку какое-нибудь соответствие цифр мурлоков цифрам от 0 до 9. Только Королю Личу известно, каких научных высот достигнет Мерзоцид с помощью секретных знаний Мертвожабрых.
Разбор. G. Племя тив. Источник. XX Командный чемпионат школьников Санкт-Петербурга по программированию Санкт-Петербург, НИУ ИТМО, 4 ноября 2012 года .
Построим ориентированный граф, вершинами которого будут являться буквы.Определим, для каких пар букв точно известно, что одна меньше другой. Для этого для каждых двух соседних в списке слов одинаковой длины найдем первую слева позицию, в которой они различаются. Добавим в наш граф ребро из буквы, стоящей на найденной позиции меньшего слова в букву, стоящую на этой же позиции большего слова.
Ребро будет обозначать, что буква, из которой выходит ребро меньше буквы, в которую входит это ребро. Если в нашем графе появится цикл, то решения нет. Это можно проверить с помощью обхода в глубину. Топологически отсортируем полученный граф. Тогда полученное расположение букв будет искомым. Потому что все ребра будут идти слева
направо, а это значит, что буква, стоящая левее, будет меньше.
направо, а это значит, что буква, стоящая левее, будет меньше.
