Одним холодным летним днем (который попал на выходной) делать было особо нечего, хотелось писать какой-то код, но придумывать очередной пет-проект не хотелось совсем. Тогда и было принято решение опробовать себя в спортивном программировании. Когда был студентом пробовал решать нестандартные задачки, но особых успехов в этом не добился и, как следствие, не увлекся я этим делом. Сейчас уже будучи опытным Ruby/Rails разрабом мне было интересно как я справлюсь с тем, что в матерых кругах считается "задачами оторванными от реальности", поэтому не долго думая отправился на известный мне codeforces.com и начал с самого начала (ну почти).
Задача А: Победитель
сама задача
Победитель популярной в Берляндии карточной игры «Берлоггинг» определяется по следующим правилам. Если на момент окончания игры существует только один игрок, набравший максимальное количество очков, то он и становится победителем.
Ситуация осложняется, если таких игроков несколько. Каждый кон игры некоторый игрок выигрывает или проигрывает некоторое количество очков. В записи о ходе игры это обозначается строкой «name score», где name это имя игрока, а score целое число обозначающее количество заработанных очков данным игроком. Если score — отрицательное число, это обозначает, что игрок проиграл в этом коне. Так вот, если на конец игры несколько игроков набрали максимум очков (пусть это число равно m), то выигрывает тот из них, кто первым набрал как минимум m очков. Перед началом игры у каждого игрока 0 очков. Гарантируется, что на момент окончания игры хотя бы у одного игрока положительное число очков.
Входные данные
В первой строке записано целое число n (1 ≤ n ≤ 1000), n — количество конов сыгранной игры. Далее в n строках идут описания конов, в формате «name score» в хронологическом порядке, где name это строка из строчных букв латинского алфавита длины от 1 до 32, а score это целое число от -1000 до 1000 включительно.
Выходные данные
Выведите имя победителя игры «Берлоггинг».
Что ж, звучит не сложно, решение задачи думаю будет таким: заведем хеш, в котором будем хранить очки каждого игрока и по мере ввода увеличивать их, параллельно заведем переменную max_points в которой будем хранить максимально набранное кем-либо количество очков. тот кто первый обновит эту переменную тот и будет победителем игры.
#include <bits/stdc++.h>
int main()
{
std::string winner;
int max_points = 0;
std::map<std::string, int> data;
int n, current_points;
std::string name;
std::cin >> n;
for (int i = 0; i < n; i++) {
std::cin >> name >> current_points;
std::cin.get();
if (data.find(name) == data.end())
data[name] = 0;
data[name] += current_points;
if (data[name] > max_points) {
winner = name;
max_points = data[name];
}
}
std::cout << winner;
return 0;
}Простая реализация, самое то для первого задания, еще и авторы любезно предоставили нам тестовые данные для контроля решения и моя программа успешно выдает нужный результат. Отправляем на тестирование и переходим к следующей задаче.
Разумеется нет, мое решение успешно провалило тестирование. Прежде чем открыть входные данные на которых был неверный ответ я попробую самостоятельно найти косяк. Пару раз перечитав условие задачи я внезапно осознаю что помимо положительного количества очков может быть и отрицательное, на следующих входных данных программа дает неверный результат
3
mike 10
mike -9
tom 5Правильный ответ tom, мое решение выдает mike. Что ж, надо думать над фиксом. Может быть если изменяется количество очков у того, кто сейчас держит максимум нужно найти нового участника с максимальным количеством очков? Но если таких несколько, то как понять кто был первым? Кажется идея с max_points не рабочая, тогда я решил поступить так: заведем массив, в него будем складывать игроков в отсортированном по возрастанию количества очков порядке, при чем если есть 2 или более игрока с одинаковым количеством очков вставлять нужно не после них, а перед, чтобы правее был тот, кто первым набрал это самое количество, таким образом конечный ответ можно будет получить из последнего элемента массива.
#include <bits/stdc++.h>
struct Player {
std::string name;
int points;
};
// функция добавления игрока в нужную позицию в массиве игроков
void insert_player(std::vector<Player>& players, Player player) {
auto iter = begin(players);
for (; iter != end(players) && player.points > iter->points; iter++);
players.insert(iter, player);
}
int main()
{
std::vector<Player> players;
int n, current_points;
std::string name;
std::cin >> n;
for (int i = 0; i < n; i++) {
std::cin >> name >> current_points;
std::cin.get();
auto iter = find_if(
begin(players),
end(players),
[&name](auto item){
return item.name == name;
}
);
if (iter == end(players)) {
insert_player(players, Player { name, current_points });
continue;
}
auto player = *iter;
player.points += current_points;
// чтобы не заморачиваться со сдвигами в нужную сторону я решил
// просто еще раз вставить игрока в нужную позицию
players.erase(iter);
insert_player(players, player);
}
std::cout << players.back().name;
return 0;
}Итак, данная программа успешно проходит тесты авторов задания, мои собственные тесты, уверен она пройдет и финальное тестирование. Отправляю и снова фейл, на сей раз я все же обратился за проваленным тест кейсом и вот он в минимальном варианте
5
bob 10
bob 20
bob -25
mike 10
bob 5А суть тут вот в чем: несмотря на то, что к концу игры у обоих игроков по 10 очков, и первым к концу игры 10 очков оказалось у Майка, выиграть должен Боб, потому что первыми 2 конами он первым набрал не менее 10 (30 в данном примере). Выдержка из постановки задачи: выигрывает тот из них, кто первым набрал как минимум m очков. Не совсем очевидный для меня факт, ну что поделать, задание есть задание, думаем еще раз. Перед финальным решением я пробовал реализовать пару вариантов, но все они были безуспешными. И собственно последняя идея такая: будем сохранять в массив пару участник-количество_очков, и параллельно будем считать у кого какое финальное количество очков; затем по этим данным найдем максимальное значения по сумме очков (max_points) за игру и всех игроков с таким количеством очков; финальный этап алгоритма - пройти по всем сохраненным "раундам" и заново просчитать сумму очков у топовых игроков до тех пор, пока не найдем первого кто наберет минимум max_points очков, это и будет итоговый победитель
#include <bits/stdc++.h>
struct Player {
std::string name;
int points;
};
int main()
{
std::vector<Player> rounds;
std::map<std::string, int> players;
int n, current_points;
std::string name;
std::cin >> n;
for (int i = 0; i < n; i++) {
std::cin >> name >> current_points;
std::cin.get();
// сохраняем каждый раунд
rounds.push_back(Player { name, current_points });
// и параллельно считаем сумму по каждому игроку
if (players.find(name) == end(players))
players[name] = 0;
players[name] += current_points;
}
// найдем максимум из набранных очков
int max_points = 0;
for (auto&[name, points] : players) {
if (points > max_points)
max_points = points;
}
// и игроков, которые набрали этот максимум
std::map<std::string, int> top_players_points;
for (auto& [name, points] : players)
if (points == max_points)
top_players_points[name] = 0;
std::string winner;
for (auto& round : rounds) {
if (top_players_points.find(round.name) == end(top_players_points))
continue;
// для топовых игроков заново, по шагам считаем сумму и как только
// будет необходимое количество очков - сообщаем кто победитель
top_players_points[round.name] += round.points;
if (top_players_points[round.name] >= max_points) {
winner = round.name;
break;
}
}
std::cout << winner;
return 0;
}
Наконец после отправки этого решения я увидел заветное "Полное решение", первая задача взята.
Задача B: Наименее круглый путь
сама задача
Задана квадратная матрица n × n, состоящая из неотрицательных целых чисел. Вам надо найти такой путь на ней, который
начинается в левой верхней ячейке матрицы;
каждой следующей ячейкой имеет правую или нижнюю от текущей;
заканчивается в правой нижней клетке.
Кроме того, если перемножить все числа вдоль пути и посмотреть на получившиеся произведение, то это число должно быть как можно менее «круглым». Иными словами оно должно заканчиваться на наименьшее возможное количество нулей.
Входные данные
В первой строке содержится целое число n (2 ≤ n ≤ 1000), n — размер заданной матрицы. Далее в n строках содержатся элементы матрицы (целые неотрицательные числа, не превосходящие 109).
Выходные данные
В первую строку выведите искомое наименьшее количество концевых нулей в произведении чисел вдоль пути. Во вторую выведите сам путь.
Выглядит как классическая задача динамического программирования. Чтобы прикинуть решение можно представить матрицу размера 2х2
1 2
3 5Очевидно что из элемента (0,0) в элемент (1,1) можно добраться двумя путями: вправ-вниз и вниз-вправо, в первом случае произведение будет 10, во втором 15, таким образом чтобы получить итоговый ответ нужно выбрать путь с минимальным количество нулей на конце min(вправ-вниз, вниз-вправо) = вниз-вправо То же рассуждение можно экстраполировать на матрицы большего размера: вычисляем путь справа, а потом снизу и выбираем наименьший по количеству нулей на конце.
#include <bits/stdc++.h>
struct Result {
std::string path;
int zeros;
long long value;
};
int get_zeros(long long number) {
int count = 0;
do {
if (number % 10 == 0)
count++;
number /= 10;
} while (number != 0 && number % 10 == 0);
return count;
}
Result get_path(std::vector<std::vector<int>>& matrix, Result prev_result,
int i, int j) {
// Как только дошли до конечной точки путь уже будет в prev_result.path
// остается только вычислить итоговое произведение и количество нулей
if (i == matrix.size() - 1 && j == matrix.size() - 1) {
auto result = Result {
prev_result.path,
prev_result.zeros,
prev_result.value * matrix[i][j]
};
result.zeros = get_zeros(result.value);
return result;
}
// т.к. выход за пределы массива недопустим, то вес такого пути
// будет бесконечно большим
if (i >= matrix.size() || j >= matrix.size())
return Result { "", INT_MAX, 0 };
// вычисляю параметры текущей точки в которой находимся
Result r = {
prev_result.path,
prev_result.zeros,
prev_result.value * matrix[i][j]
};
r.zeros = get_zeros(r.value);
// вычисляю пути вниз и вправо
auto r1 = get_path(matrix, Result { r.path + "D", r.zeros, r.value }, i+1, j);
auto r2 = get_path(matrix, Result { r.path + "R", r.zeros, r.value }, i, j+ 1);
// и возвращаю минимальный
return r1.zeros > r2.zeros ? r2 : r1;
}
int main()
{
std::vector<std::vector<int>> matrix;
int n;
std::cin >> n;
matrix.resize(n);
for (int i = 0; i < n; i++) {
matrix[i].resize(n);
for (int j = 0; j < n; j++)
std::cin >> matrix[i][j];
}
auto result = get_path(matrix, Result { "", 0, 1 }, 0, 0);
std::cout << result.zeros << std::endl << result.path;
return 0;
}
Отправляю решение и получаю Превышено ограничение времени на тесте 11 В принципе понятно что алгоритм будет работать долго (алгоритмическую сложность к сожалению просчитать не могу), поэтому настало время оптимизировать. Основная оптимизация заключается в следующем: каждую клетку программа будет просчитывать 3 раза: когда до нее дойдет очередь, а так же когда она будет частью более длинного пути либо справа, либо снизу. Нужно научить алгоритм использовать уже ранее вычисленные значения. Первым делом в голову приходит перед возвратом результата в функции get_path куда-то его записать, однако потом возникнут сложности с его переиспользованием (т.к. если я знаю "вес" некоторой точки через правый маршрут не значит что я смогу получить "вес" для нижнего маршрута). После перебора пары вариантов я остановился на таком решении: заведем еще одну матрицу будем заполнять ее маршрутом с минимальным количеством нулей на конце от текущей точки до правой-нижней. Таким образом когда я окажусь в клетке с индексом (i, j) и захочу из нее спуститься в клетку (i+1, j) мне достаточно будет обратиться в кеш по индексу (i + 1, j), если там есть что-то, то итоговый маршрут до конца я получу как current_path + path_from_cache, а итоговое количество нулей в произведении я смогу посчитать из current_value * value_from_cache и мне не нужно будет вычислять все это заново. Звучит сложно, отлаживать это до работоспособного состояния было еще сложнее, т.к. рекурсивные алгоритмы и отладка это вещи которые вместе не живут
#include <bits/stdc++.h>
struct Result {
std::string path;
int zeros;
long long value;
};
std::vector<std::vector<Result>> cache_matrix;
int get_zeros(long long number) {
int count = 0;
do {
if (number % 10 == 0)
count++;
number /= 10;
} while (number != 0 && number % 10 == 0);
return count;
}
Result get_path(std::vector<std::vector<int>>& matrix, Result prev_result,
int i, int j) {
if (i == matrix.size() - 1 && j == matrix.size() - 1) {
auto result = Result {
prev_result.path,
prev_result.zeros,
prev_result.value * matrix[i][j]
};
result.zeros = get_zeros(result.value);
cache_matrix[i][j] = Result { "", get_zeros(matrix[i][j]), matrix[i][j] };
return result;
}
if (i >= matrix.size() || j >= matrix.size())
return Result { "INVALID", INT_MAX, 0 };
Result r = {
prev_result.path,
prev_result.zeros,
prev_result.value * matrix[i][j]
};
r.zeros = get_zeros(r.value);
Result r1, r2;
// выполняем примерно те же самые действия что и в прошлом решении
// только предварительно заглянем в кеш, и если там что-то есть
// то не будем вычислять путь заново
if (cache_matrix[i + 1][j].zeros != INT_MAX) {
r1 = r;
r1.path += "D" + cache_matrix[i + 1][j].path;
r1.value *= cache_matrix[i + 1][j].value;
r1.zeros = get_zeros(r1.value);
}
else
r1 = get_path(matrix, Result { r.path + "D", r.zeros, r.value }, i+1, j);
if (cache_matrix[i][j + 1].zeros != INT_MAX) {
r2 = r;
r2.path += "R" + cache_matrix[i][j + 1].path;
r2.value *= cache_matrix[i][j + 1].value;
r2.zeros = get_zeros(r2.value);
}
else
r2 = get_path(matrix, Result { r.path + "R", r.zeros, r.value }, i, j+1);
// самое интересно. теперь когда знаем кратчайший путь из
// текущей точки можно обновить значение в кеше. Если там ничего
// нет, либо уже сохраненный путь "дороже" того, что был сейчас
// построен - обновляю значение
if (r1.zeros > r2.zeros) {
if (r2.zeros < cache_matrix[i][j].zeros) {
auto nr = cache_matrix[i][j + 1];
nr.path = "R" + nr.path;
nr.value *= matrix[i][j];
nr.zeros = get_zeros(nr.value);
cache_matrix[i][j] = nr;
}
return r2;
} else {
if (r1.zeros < cache_matrix[i][j].zeros) {
auto nr = cache_matrix[i + 1][j];
nr.path = "D" + nr.path;;
nr.value *= matrix[i][j];
nr.zeros = get_zeros(nr.value);
cache_matrix[i][j] = nr;
}
return r1;
}
}
int main()
{
std::vector<std::vector<int>> matrix;
int n;
std::cin >> n;
matrix.resize(n);
cache_matrix.resize(n + 1);
cache_matrix[n].resize(n + 1);
for (int i = 0; i < n; i++) {
matrix[i].resize(n);
cache_matrix[i].resize(n + 1);
for (int j = 0; j < n; j++) {
std::cin >> matrix[i][j];
cache_matrix[i][j] = Result { "", INT_MAX, 1 };
}
cache_matrix[i][n] = Result { "", INT_MAX, 1 };
}
for (int j = 0; j <= n; j++) {
cache_matrix[n][j] = Result { "", INT_MAX, 1 };
}
auto r1 = get_path(matrix, Result { "", 0, 1 }, 0, 0);
std::cout << r1.zeros << std::endl << r1.path;
return 0;
}И снова тестирующая система говорит о неудаче, на этот раз неверный ответ. Получился он при матрице размером 20, все элементы которой в диапазоне от 100 до 1000. Тут меня и осенило, ведь в условии задачи сказано что элементы матрицы целые неотрицательные числа, не превосходящие 109. Получается что хранить произведение в 64 битах не вариант, и значит мое решение в корне неверное.
После такого провала, когда победа уже была близка, настроение упало в 0, долгие раздумывания не давали каких-либо других решений. Было решено обратиться за ответом на сам codeforces. Беглый гуглеж сразу выдал разбор задач из этого соревнования, там все сводилось тому как посчитать количество нулей на конце зная сколько множителей 2 и 5 у результирующего произведения. Мдаа, к такому меня жизнь не готовила.
Последней попыткой победить это задание для меня было переписать все это на родной Ruby, т.к. там проблем с большими числами нет, можно работать из коробки. Код приводить не стану т.к. он идентичен плюсам, только на Ruby, скажу лишь что и тут удача мне не улыбнулась, новое решение хоть и справилось с матрицей в 20 элементов, но вот 15й тест и 200 элементов заколотили крышку в гроб моего решения - TIME_LIMIT_EXCEEDED.
C. Задача комментатора
сама задача
Олимпиада в Беркувере в самом разгаре. Здесь у каждого свои задачи — спортсмены борются за медали, а комментаторы за наиболее удобные места ведения репортажей. Сегодня основные спортивные мероприятия пройдут на трех круглых стадионах и задача комментатора выбрать оптимальную точку наблюдения, то есть такую из которой видны все три стадиона. Так как все состязания одинаково важны — то и стадионы должны быть видны из этой точки под одинаковым углом. Если таких точек несколько, то более предпочтительной является та, из которой угол обзора каждого стадиона максимален.
Помогите известному в Берляндии комментатору Г. Берниеву найти оптимальную точку наблюдения. Учтите, что стадионы не загораживают друг друга — комментатор может видеть легко наблюдать один стадион сквозь другой.
Входные данные
Входные данные состоят из трех строк, каждая из которых описывает положение одного стадиона. Строки имеют формат x, y, r, где (x,y) — это координаты центра стадиона ( - 103 ≤ x, y ≤ 103), а r (1 ≤ r ≤ 103) — это его радиус. Все числа во входных данных целые. Стадионы не пересекаются, а их центры не лежат на одной прямой.
Выходные данные
Выведите координаты искомой точки с пятью знаками после десятичной точки. Если решения не существует, то программа не должны выводить что либо. Иными словами она должны оставить выходные данные пустыми.
Признаюсь честно с геометрией у меня довольно таки туго, прочитав задание я так и не понял что подразумевается под точкой из которой 3 окружности видны под одинаковым углом. Угол между двумя прямыми я понимаю, а между точкой и окружностью нет. Таким образом это задание тоже в пролете. Я попробовал посмотреть на разбор, но понимание не пришло.
Итог
Наверное для меня это не сюрприз, что я не смогу решить все задачи и показать какой-то внушительный результат, но все же я получил чего хотел: было интересно поломать мозг над решением а так же писать хоть какой-то код. Если задуматься над тем насколько умение решать такие задачи поможет в моей основной работе, то я могу сказать так: тут проверяются немного другие умения, нежели писать продакшн код, несомненно тот кто щелкает эти задачи будет выдавать не менее гениальные решение и на рабочем месте, но обратное не справедливо на мой взгляд. Однако один несомненный плюс у этого есть: в реальных соревнованиях за отправку неверного решения снимаются штрафные баллы, поэтому перед каждой отсылкой участнику нужно быть на 100% уверенным в своем решение, предусмотреть все возможные и невозможные входные данные, если бы перед тем как перевести статус задачи в Jira в Ready for test разработчики с такой скрупулезностью проверяли свой код, то на свете было бы много счастливых тестировщиков :)
