понедельник, 20 ноября 2017 г.

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

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 года .
Построим ориентированный граф, вершинами которого будут являться буквы.Определим, для каких пар букв точно известно, что одна меньше другой.  Для этого для каждых двух соседних в списке слов одинаковой длины найдем первую слева позицию, в которой они различаются. Добавим в наш граф ребро из буквы, стоящей на найденной позиции меньшего слова в букву, стоящую на этой же позиции большего слова.
Ребро будет обозначать, что буква, из которой выходит ребро меньше буквы, в которую входит это ребро. Если в нашем графе появится цикл, то решения нет. Это можно проверить с помощью обхода в глубину.  Топологически отсортируем полученный граф. Тогда полученное расположение букв будет искомым.  Потому что все ребра будут идти слева
направо, а это значит, что буква, стоящая левее, будет меньше.













воскресенье, 19 ноября 2017 г.

Результаты личного тура Первокурсник




Личный тур "ПЕРВОКУРСНИК" состоялся 18 ноября  2017 года,
начало в 13:45:00, конец в 17:15:00, длительность 3:30:00. Фотоальбом  смотрите здесь. Разбор задач будет опубликован  позднее.

Зарегистрировалось 75 человек, но приняли участие 48 человек. К сожалению, не смогли прийти одиннадцатиклассники из ФМЛИ. В их отсутствие Шморгунов Александр уверенно выиграл тур, решив все 6 предложенных задач за 2 часа 16 минут и намного опередив всех соперников. Диплом 1 степени. Поздравляю! 

Вторым стал Чекменёв Владимир,  он решил 4 задачи, в том числе задачу C на динамику (вариант классического рюкзака). Очень хороший результат. Диплом 1 степени. Желаю успеха на ВсОШ! 

Далее следует большая группа школьников и студентов, решивших 3 задачи. Все они получат дипломы 2-й и 3-й степени. 


Теперь о главных героях тура - первокурсниках СГУ: Морозов Николай, Карманов Александр, Голенев Илья, Поляков Артем,  Торчагин Никита,  Головина Мария и Русинова Юлия. Все из 111- ПМо, ИТНИТ.  Морозов Николай, Голенев Илья, Поляков Артем решили 2 задачи (как и ожидалось), упорно бились за улучшение перебора в задаче "Казакус", но не догадались пронумеровать массив кодами карт и помечать введенные карты. Карманов Александр отказался от борьбы после решения второй задачи.  Впрочем, очень неплохо. Выступили даже лучше, чем второй курс.  Победители будут награждены перед лицом своих товарищей грамотами и подарками. Паркер и ручки попроще уже ждут своих хозяев.

Морозов Николай, 1 место
Карманов Александр, 2 место

Голенев Илья, 3 место

Поляков Артем, 4 место
Все-таки не понимаю, почему первокурсники других специальностей игнорируют возможность проверить свои силы и получить опыт программирования. 

Приняли участие в чемпионате и магистры 1 курса Мельников Вадим (8 место) и Белых Евгений (10 место). Спасибо за участие, вы молодцы.

К сожалению, второй и третий курс показали, что в сравнении с первым курсом ничему новому они не научились.  

Протокол соревнований:

Участник
A
B
C
D
E
F
Решено задач
Штраф
39/68
39/92
2/46
15/215
1/28
1/8
1
Шморгунов Александр
+
1
+
+
+
6
6
426
2
Чекменев Владимир
1
1
7
1
4
514
3
Александров Максим
+
+
1
3
46
4
Черных Елена
+
+
+
3
47
5
Тропин Иван
+
1
+
3
51
6
Шевелев Роман
1
+
+
3
57
7
Алексеев Валерий
+
+
1
3
70
8
Мельников Вадим
+
+
2
3
87
9
Размыслов Константин
+
2
+
3
136
10
Белых Евгений
+
2
3
3
208
11
Колпаков Владимир
+
+
4
3
302
12
Кудинов Денис
+
+
6
3
373
13
Гришин Дмитрий
+
1
9
3
387
14
Титов Георгий
+
5
7
3
410
15
Биричевский Евгений
+
+
2
22
16
Морозов Николай
+
+
2
24
17
Борнякова Юлия
+
+
2
27
18
Козлов Иван
+
+
2
32
19
Молчанов Сергей
+
+
2
33
20
Литовченко Алексей
+
+
2
36
21
Карманов Александр
+
+
2
40
22
Алексюк Иван
+
+
2
50
23
Дуркин Анатолий
1
+
2
56
24
Федоров Павел
+
+
2
61
25
Хилько Павел
+
1
2
76
26
Петунин Артем
+
+
2
81
27
Корычев Роман
2
+
2
87
28
Ищук Виталий
+
+
2
88
29
Савин Артем
2
+
2
92
30
Головатенко Михаил
1
1
2
96
31
Голенев Илья
+
+
2
104
32
Дмитрачков Иван
+
1
2
111
33
Кравцов Максим
+
+
2
152
34
Поляков Артем
+
1
2
159
35
Надуткин Фёдор
+
3
2
205
36
Филиппов Денис
+
+
2
240
37
Напалков Владислав
3
+
2
262
38
Корнилов Александр
+
1
22
39
Мустафин Ильнур
+
1
42
40
Торчагин Никита
2
1
70
41
Головина Мария
+
1
88
42
Балыгин Егор
7
1
319
43-48
Кожагельдиев Никита
0
0
43-48
Шеремет  Иван
0
0
43-48
Глинко Ярослав
0
0
43-48
Халилов Алиага
0
0
43-48
Смоленцев Антон
0
0
43-48
Русинова Юлия
0
0