Разбор задач с "ПЕРВОКУРСНИКА"

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.

Результат схватки может быть таким:

1. A победила B, если после схватки сохранила часть здоровья, а B потеряла все свое здоровье;
2. A проиграла B, если после схватки потеряла все свое здоровье, а B  сохранила часть своего здоровья;
3. обе карты погибли, если обе потеряли все свое здоровье;
4. ничья: обе карты сохранили часть своего здоровья.

Дано: две строки. В первой строке значения атаки и здоровья карты 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 года .

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

Ребро будет обозначать, что буква, из которой выходит ребро меньше буквы, в которую входит это ребро. Если в нашем графе появится цикл, то решения нет. Это можно проверить с помощью обхода в глубину.  Топологически отсортируем полученный граф. Тогда полученное расположение букв будет искомым.  Потому что все ребра будут идти слева
направо, а это значит, что буква, стоящая левее, будет меньше.