Задача A. Рейтинг персонажей ≡

Условие

В компьютерной игре, которую разрабатывает команда школьников, есть персонажи Элина, Алекс, Джон и Кейт. На первом уровне игры каждый персонаж может найти и сохранить в арсенале один из предметов: магический кристалл или аптечку. Также персонажи на первом уровне могут улучшить свою способность наносить урон врагу. В конце уровня составляется рейтинговая таблица персонажей, где показывается место каждого.

После прохождения первого уровня стало известно, что:

– Элина и герой, находящийся на третьем месте, нашли по магическому кристаллу;

– у Алекса и персонажа, находящегося на первом месте, есть аптечка;

– персонаж, занимающий первое место, наносит больший урон, чем персонаж, находящийся на втором месте;

– Кейт наносит меньший урон, чем персонаж на втором месте рейтинговой таблицы;

– у Джона и Алекса одинаковый уровень способности наносить урон.

Определите место каждого персонажа в рейтинговой таблице.

ВНИМАНИЕ! Для решения этой задачи составление программы для компьютера не требуется!

Формат выходных данных

Выходные данные необходимо отправить в систему проверки решений в виде простого текста – четыре заглавные буквы без пробелов и знаков препинания, являющиеся первыми буквами имен персонажей, в порядке убывания их мест в рейтинговой таблице, например: КДАЭ (пример возможного, но, вероятно, неверного ответа.
При отправке ответа в систему засчитывается только первая попытка.

Задача B. Уровни компьютерной игры ≡

Условие

Разрабатываемая друзьями компьютерная игра должна была содержать k игровых уровней сложности по m миссий на каждом. Каждая отдельная миссия выполняется в p локациях. В процессе работы над игрой друзья внесли некоторые изменения следующего характера: количество миссий m увеличилось на d_m, а количество уровней k, наоборот, уменьшилось на d_k. При этом число локаций p для каждой миссии на каждом игровом уровне не изменилось. После создания игры друзья обнаружили, что общее количество локаций в игре изменилось.

Помогите друзьям узнать, на сколько изменилось общее количество локаций в компьютерной игре.

Напишите программу для решения этой задачи!

Формат входных данных

Единственная строка содержит пять целых чисел k, m, p, d_m, d_k, 1 < k ≤ 10³, 0 < m, p, d_k ≤ 10⁴, d_m < k, 0 < d_k < k − 1, где k, m, p – количество игровых уровней, миссий и локаций соответственно, d_m - величина, на которую увеличилось количество миссий, d_k – величина, на которую уменьшилось количество уровней.

Формат выходных данных

Выведите единственное целое число n, которое показывает, на сколько изменилось общее количество локаций в компьютерной игре. Вывести абсолютное значение.

Примеры тестов

50 30 100 7 11

5700

12 15 5 4 6

330

Задача C. Клады ≡

Условие

В ходе разработки игрового сценария команда разработчиков решила предусмотреть возможность найти клад для игровых персонажей. Клад может состоять из нескольких предметов, у каждого из которых есть своя стоимость. Предметы можно затем продать, для того, чтобы заработать золото на покупку инвентаря и оружия персонажа. Для того, чтобы было проще написать программу в дальнейшем, решили, что стоимость отдельных типов предметов будет фиксирована: 100, 200, 500 и 1000 золотых.

Ребята хотят, чтобы клады в игре были максимально разнообразны. Помогите команде разработчиков написать программу для подсчета количества возможных различных способов составить клад из предметов (стоимости 100, 200, 500, 1000 золотых) для заданной общей стоимости клада N золотых.

Напишите программу для решения этой задачи!

Формат входных данных

Единственная строка содержит целое положительное число N, 0 < N ≤ 10⁵.

Формат выходных данных

Выведите единственное целое число K, которое показывает количество способов составить клад из предметов фиксированной стоимости.

Примеры тестов

100

1

700

6

Задача D. Квесты ≡

Условие

Команда школьников – разработчиков компьютерной игры – решила, что один из ее уровней будет представлять собой квест, в котором необходимо выполнить N заданий. Каждое задание необходимо выполнить, чтобы дойти до конца квеста и пройти на следующий уровень. При этом каждое задание имеет сложность a_i и награду t_i очков опыта. Если персонаж игрока имеет опыт меньше, чем a_i, он не сможет выполнить задание и получить награду. В случае, если задание выполнено, персонаж получает соответствующую награду.

Для оценки сложности уровня требуется написать программу, которая поможет определить, сможет ли игрок преодолеть квест, если в начале уровня имеет K очков опыта и выполняет задания успешно и последовательно одно за другим.

Напишите программу для решения этой задачи!

Формат входных данных

В первой строке через пробел вводятся два целых числа N, K, 1 ≤ N ≤ 100, 0 ≤ K ≤ 10⁵, где N – количество заданий квеста, которые необходимо выполнить последовательно для перехода на следующий уровень, K – количество очков опыта персонажа игрока, которым он обладает при входе на уровень.

Во второй строке через пробел вводятся N целых чисел a_i, 0 ≤ a_i ≤ 10⁵, которые показывают сложность каждого задания.

В третьей строке через пробел вводятся N целых чисел t_i, 0 ≤ t_i ≤ 10⁵, которые представляют собой награду – количество очков опыта, которое приобретет игрок после выполнения i-го задания. Все задания необходимо выполнить последовательно для перехода на следующий уровень.

Формат выходных данных

В единственной строке выведите через пробел слово WIN и целое число – количество очков опыта, который будет у персонажа игры, если квест может быть успешно пройден, или только слово FAIL, если он не сможет пройти квест при заданном K.

Примеры тестов

3 50
20 65 90
25 65 100

WIN 240

5 5
0 10 30 25 40
5 15 30 30 50

FAIL

Задача E. Размещение портала ≡

Условие

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

Если в секторе i расположить портал, то путешествие в сектор j займет время a[i,j] + a[j,i] (при этом i не равно j). Помогите команде разработчиков найти такой сектор, путешествие из которого до самого удаленного от него сектора займет минимальное время.

Пусть время путешествия задано массивом целых неотрицательных чисел а, размер которого N×N. Будем считать a[i,i] = 0.

Напишите программу для решения этой задачи!

Формат входных данных

В первой строке вводится число N – количество секторов на карте, 0 < N ≤ 100.

В следующих строках вводятся элементы массива a через пробел построчно, где 0 ≤ a[i,j] ≤ 1000.

Формат выходных данных

В единственной строке выведите единственное целое число – номер сектора, в котором следует расположить портал.

Примеры тестов

3
0 25 36
27 0 29
35 29 0

2