Компания Yandex организовала интересное соревнование с хорошим призовым фондом. Из 6 направлений я выбрал бэкенд, в котором по языку Java было 5 задач. Их нужно было решить за 5 часов. Я выбрал удобное время и сразу столкнулся с такой проблемой - мне было сложно понять условия задачи. Наверное стиль изложения обусловлен защитой от использования ChatGPT или это какой егэшый диалект, но после того, как задача была решена, условия сразу становятся логичными и понятными. Сразу оговорюсь, что за 5 часов я не решил ни одной (shame on you) задачи, но сейчас попытаюсь исправиться, что бы поделится опытом и возможно получить обратную связь от более опытных программистов. Для удобства каждое решение выложу в отдельной статье.
Первая задача - Арт-критика (описание под катом).
Hidden text
Аркадий — главный редактор журнала по арт-критике. По долгу службы Аркадий постоянно сталкивается с фундаментальными вопросами "Что есть красота?”, “Как понять что красиво, а что нет?”.
Главред понимает, что искусство можно оценивать по-разному и к разным арт-объектам можно применять разные метрики. За годы работы в арт-индустрии Аркадий выработал собственный принцип оценки красоты любого произведения искусства. Он может сказать, красив арт-объект или нет, вне зависимости от количества критериев оценки "красивости".
Принцип Аркадия состоит в следующем. Для произвольного объекта искусства определяется некоторое количество критериев в определенном порядке для оценки “красивости”. По каждому критерию можно набрать максимум n первичных баллов. Вторичные баллы за условный критерий i определяются следующим образом:
Если при оценке критерия набирается ai первичных баллов, то Аркадий начисляет критерию a2i вторичных баллов.
Кроме того, Аркадий прибавляет бонусные баллы за ai следующих ненулевых оценок по другим критериям (прибавляются первичные баллы).
Для последнего критерия дополнительные баллы не начисляются.
Например, если n = 10, Аркадий оценивал картину по пяти критериям, и арт-объект набрал [10, 0, 1, 0, 3] первичных баллов, соответственно, то его итоговый результат будет равен 117 вторичных баллов, так как за первый критерий он получил 102 + 1 + 3 балла, за второе и четвертое — по 0, за третье — 12 + 3, за пятое — 32.
Аркадий дал последовательность результатов m оценок критериев произведения искусства. Определите общую сумму вторичных баллов.
Формат ввода:
В первой строке даны два целых числа n и m (1 ≤ n, m ≤ 200 000).
Во второй строке заданы m целых чисел ai (0 ≤ ai ≤ n).
Формат вывода:
Выведите сумму набранных баллов.
Пример 1:
Ввод:
10 5
10 0 1 0 3
Вывод:
117
Пример 2:
Ввод:
5 5
0 0 0 0 0
Вывод:
0
Пример 3:
Ввод:
1 3
1 1 1
Вывод:
5
Первым делом получаем на вход два числа - максимальная оценка и количество параметров. Получим их с помощью класса Scanner:
Scanner scanner = new Scanner(System.in);
int maxScore = scanner.nextInt();
int parameterQuantity = scanner.nextInt();Второй строкой получаем оценки. Их будем добавлять в ArrayList, потому что их количество будет меняться.
List<Integer> scoreList = new ArrayList<>();
for (int i = 0; i < parameterQuantity; i++) {
int nextScore = scanner.nextInt();
scoreList.add(nextScore);
}
scanner.close();Теперь высчитываем “вторичные баллы”. Берем первое число из scoreList, возводим в квадрат, добавляем к нему остальные числа из хвоста scoreList и суммируем в какой-нибудь агрегатор. Затем выводим результат.
int acc = 0;
int tempScore;
for (int i = 0; i < parameterQuantity; i++) {
tempScore = scoreList.get(i);
if (tempScore == 0) continue;
tempScore = tempScore * tempScore;
for (int j = i + 1; j < parameterQuantity; j++) {
if (scoreList.get(j) == 0) continue;
tempScore += scoreList.get(j);
}
acc += tempScore;
}
System.out.println(acc);Скорее всего, это неправильное решение, т.к. в третьем примере этот код выводит 6 вместо 5.
Давайте разберем этот пример, может кто-то сможет найти ошибку в решении. Итак, на вход поступают числа: 1 (максимальная оценка за один параметр), 3 (количество параметров оценивания) и три единицы (оценки по трем параметрам, которые получил арт-объект).
Берем первую оценку 1, возводим в квадрат и добавляем две единицы, получаем 3. Далее берем вторую единицу, возводим в квадрат и добавляем последнюю единицу, получаем 2. Последняя единица просто возводится в квадрат без добавлений. Итог, 3 + 2 + 1 = 6. А должно быть 5.
Следующая задача будет посложнее.
