Всем доброго времени суток!
Решил я в период самоизоляции заняться чем-нибудь полезным, например, потренировать скилл в программировании. Из языков, которые нам преподавали в любимом ВУЗе, был только C++, который я не очень любил. Вот и последние пару месяцев стал изучать Python. Переходить с C++ на Python гораздо удобнее, чем наоборот, поэтому я быстро перестроился и стал наслаждаться его простотой.
Наткнулся я на Яндекс.Практикум, где есть раздел, посвященный алгоритмам. Хотелось быстрого code review и решил попробовать. Делюсь с Вами своими результатами.
Всего заданий было 7 (A-G), но я расскажу о пяти из них. Время было не ограничено, хотя на задачках по олимпиадному программированию оно фиксированно. Этот термин я узнал уже в процессе решения задач, изучая параллельно соответствующую литературу. Жаль, что обработчик Яндекса не может провести полноценного ревью и выдать результат, поэтому приходится довольствоваться малым. Ждать пока какой-либо тест будет не пройден и самому искать баг.
Итак, начнем:
В медиа-сервисе зарегистрировано n пользователей. Все пользователи, за исключением двух, в последние два месяца посещали сайт. Нужно определить id пользователей, которые сайт не посещали.
Формат ввода:
Первая строка содержит число n — количество зарегистрированных пользователей. Это целое число в диапазоне от 2 до $inline$10^6$inline$
Во второй строке через пробел заданы различные n — 2 целых числа. Каждое из них не превосходит n и больше нуля.
Формат вывода:
Нужно в одной строке вывести по возрастанию два пропущенных числа, разделённые пробелом.
Пример
Ввод:
7
6 4 1 2 3
Вывод:
5 7
В примечании было сказано, что алгоритм должен работать не дольше, чем O(n).
Решил попробовать на языке, который совсем недавно пришел в мою жизнь, и крепко в ней закрепился (Python).
Краткий алгоритм:
1. Сортируем введенный массив
2. В цикле проверяем на совпадение итератора и значения массива
3. При несовпадении — добавляем недостающий элемент, а также этот элемент добавляем в другой массив.
В каждой из задач есть соответствующие требования по времени выполнения, а также по памяти. Для разных языков требования разные.
Например, для языков PyPy4, Python 3.7.3, Python 2.7:
Ограничение памяти — 256 Мб
Ограничение времени — 7.5 секунд
Для других языков:
Ограничение памяти — 64 Мб
Ограничение времени — 1 секунда
Все тесты пройдены успешно! Результат: Время — 135 мс, память — 11 Мб. Довольно неплохо для «медленного» питона.
Маша и Медведь играют в игру. У Маши есть фишки с указанным на них количеством очков. На каждой фишке — k очков, k находится в промежутке от $inline$-10^5$inline$ до $inline$10^5$inline$. Медведь называет число, а Маша должна выбрать три фишки, сумма очков на которых наиболее близка с заданному числу.
Формат ввода:
Первая строка содержит целое число n в диапазоне от $inline$-10^5$inline$ до $inline$10^5$inline$ число, названное первым участником. Во второй строке через пробел заданы целые числа в диапазоне от $inline$-10^5$inline$ до $inline$10^5$inline$ — очки для фишек второго участника. Их количество может быть от 3 до $inline$10^4$inline$
Формат вывода:
Нужно вывести целое число — сумму очков трёх фишек, наиболее близкую к n.
Пример
Ввод:
6
-1 -1 -9 -7 3 -6
Вывод:
1
Решение должно работать не дольше, чем за O($inline$n^2$inline$). Ограничение по памяти — O(1).
С этой задачкой я долго возился из-за того, что не проходил сначала ограничение по времени, потом по памяти. Я много слышал, что питон тратит достаточное количество ресурсов, поэтому после фейла с ним написал код на C++. Он тоже не выдержал тестов и провалился сначала на времени, потом на памяти. Может быть дело в несовершенном алгоритме?
Требования
Для всех языков:
Ограничение памяти — 64 Мб
Ограничение времени — 1 секунда
В результате тестирования кода получилось:
Время: 1.09 с
Память: 40 Мб
Все мои попытки уменьшить время проваливались и приводили только к увеличению памяти (странно конечно, потому что я пытался сократить количество типов данных list ).
Но и тут меня ждала неудача. Не уложился я теперь по лимиту использования памяти (80 Мб). Что за чушь! Удаляя некоторые динамические объекты, то есть заменяя вектора на массивы с динамическим выделением памяти, а то и на статические массивы, получилось только хуже. Для реализации представленного кода потребуется 121 Мб памяти (при граничных условиях, то есть при максимальной нагрузки). Так заявляет Яндекс.Практикум во всяком случае.
Я даже захотел сам написать unit-тесты и сравнить результаты, но руки до этого не дошли.
Итак, задача осталась со статусом: частичное решение…
Шерлок Холмс и доктор Ватсон передают друг другу зашифрованные сообщения, состоящие из чисел. Каждое число может обозначать одну букву, слово или знак препинания. Получая последовательность чисел, Холмс и Ватсон могут расшифровывать сообщения друг друга.
Однако они стали подозревать, что кто-то разгадал их шифр и повысили уровень безопасности. Теперь каждое сообщение зашифровано в матрице. Чтобы его прочитать, нужно распечатать значения матрицы по спирали, начиная от центра вверх и далее по часовой стрелке.
Формат ввода:
Первая строка содержит целое нечётное число m в диапазоне от 1 до 1000 — количество строк и столбцов матрицы.
В каждой из следующих m строк даны m целых чисел в диапазоне от -1000 до 1000, разделённых пробелом.
Формат вывода:
Нужно вывести значения в матрице, начиная с центра по спирали. Движение вверх, далее по часовой стрелке. Каждое число выводится в отдельной строке.
Пример
Ввод:
3
9 10 7
0 7 7
8 3 4
Вывод:
7
10
7
7
4
3
8
0
9
Эта задачка показалась мне очень сложной и, не долго думая, начал гуглить. Похожий пример нашел на плюсах, но там реализовали наоборот закручивание матрицы от первого элемента[0][0] до середины[N/2][N/2]. Мои попытки обойтись «малой кровью», то есть внести в алгоритм небольшие поправки, закончились неудачей. Пришлось досконально разбираться в коде, модернизируя его. Это очень полезный навык понимать чужой код и уметь его применять для своих нужд. Не все же время с нуля писать проекты.
Требования
Для всех языков:
Ограничение памяти — 33 Мб
Ограничение времени — 1.4 секунда
Java:
Ограничение памяти — 286 Мб
Ограничение времени — 9 секунд
Node JS 8.16:
Ограничение памяти — 256 Мб
Ограничение времени — 15 секунд
Результаты меня приятно порадовали, так как все тесты пройдены с первого раза. Ну о качестве кода судить Вам.
В результате тестирования кода получилось:
Время: 180 мс
Память: 7.83 Мб
В процессе написания кода, начинаешь задумывать о размере выделяемой памяти и скорости алгоритма. Очень просто использовать библиотеку STL, а вот что у нее «под капотом» ответит не каждый. На работе зашла речь об STL с парнем, который как и я начинают свою карьеру программистом. Он немного прогал на С и возник вопрос о динамической памяти. Я покачал головой, сказав что в таких случаях использую STL в C++ и не парюсь. Наш разговор услышал разработчик со стажем и сказал, что всех нас надо заставить писать на чистом С, чтобы понять всю боль и прелесть языка. Наверное он прав, но сложно перейти с питона обратно на C. Ладно, продолжим решать задачки.
Поиграем в морской бой. Поле представлено матрицей n на m. Длина кораблей ограничена размерами матрицы. Корабли могут быть расположены либо горизонтально, либо вертикально. Соприкасаться друг с другом они могут, пересекаться — нет. По полю несколько раз выстрелили. Нужно выяснить, сколько кораблей было сбито и сколько ранено.
Формат ввода
В первой строке подаются числа n и m, $inline$1≤n,m≤10^4$inline$
В следующей строке — количество кораблей k, $inline$0≤k≤10^4$inline$
В следующих k строках — описание кораблей: 4 числа через пробел. Первая пара чисел определяет ячейку матрицы, то есть номер строки и столбца, где расположено начало корабля. Вторая пара соответствует концу корабля. Нумерация строк и столбцов начинается с 0.
Далее следует s — количество выстрелов, целое число в диапазоне от 0 до 10000.
В следующих s строках — описание выстрелов: пара чисел через пробел. Первое число соответствует номеру строки на поле для ячейки, куда попал выстрел, второе — номеру столбца. Стрелять в ячейку более одного раза нельзя.
Формат вывода
Нужно вывести 2 числа в строке, разделённые пробелом. Первое число — количество раненых кораблей, второе число — количество сбитых. Корабль считается сбитым, если выстрелы попали во все занимаемые им ячейки. Раненым — если задета хоть одна ячейка.
Пример
Ввод:
5 5
4
4 0 4 1
4 3 4 4
2 2 2 2
1 4 2 4
5
4 0
4 1
0 0
4 4
2 2
Вывод:
1 2
Конечно же я не бросил все и начал читать Кернигана и Ритчи. Нет, я просто продолжил писать на Python. Алгоритм получился не очень изящный:
1. Решил, что необходимо добавлять не только координаты начала и конца кораблей, а все его части.
2. Потом сравнивать координаты выстрелов с координатами кораблей и, если попал, то удалять координату. Сразу проверяем на нулевую длину. При положительном результате kill++.
3. Проверку на раненые корабли организовал через цикл, пробегаясь по кораблям и сравнивая исходные координаты с первоначальными.
Требования
Для всех языков:
Ограничение памяти — 64 Мб
Ограничение времени — 1 секунда
И опять с первого раза уложился! Статус полное решение и все 17 тестов пройдены.
Результат:
Время: 30мс
Память: 3.98 Мб
Конечно за 3 вложенных цикла меня можно поставить к стенке, но на первый взгляд мне эта идея показалась рабочей. Надо бы поработать над совершенством кода, но меня ждет еще одна задачка.
Мэр города Плужникова решил открыть серию пиццерий в городе. Город представлен в виде матрицы NxN, где каждая ячейка на позиции [i][j] — это отдельный квартал. Доставка из каждой пиццерии возможна не далее, чем на R кварталов от её расположения. Расстояние определяется минимальным количеством кварталов, которые пройдёт доставщик, если он передвигается по горизонтали или по вертикали. Ходить по диагонали нельзя. Например, представим, что N=5,R=2, и пиццерия расположена в ячейке (3,3). Тогда доставить пиццу можно в кварталы, помеченные символом X.
00X00
0XXX0
XXXXX
0XXX0
00X00
Артёмка очень любит пиццу. Он хочет попасть в квартал, где доступно максимальное количество заказов из разных пиццерий, чтобы выбрать лучшую. Помогите Артёмке найти максимальное количество доступных пиццерий, если он попадет в квартал, где это значение не меньше, чем в любом другом.
Формат ввода
В первой строке заданы через пробел два числа: N и M, оба принадлежат отрезку [1, 1000].N обозначает размерность города в кварталах по горизонтали и по вертикали. M — число пиццерий в городе. В следующих M строках каждая пиццерия описана значениями X,Y,R. X и Y— это квартал, где пиццерия расположена. (1≤X,Y≤N), R— максимальная дистанция, на которую можно заказать доставку. (1≤R≤100).
Формат вывода
Выведите одно число — максимально возможное количество пиццерий, из которых доставляют в квартал, где это значение не меньше любого другого.
Пример
Ввод:
8 2
5 3 3
6 1 5
Вывод:
2
В двух словах об алгоритме:
1. Создается функция, которая генерит все кварталы, покрываемые одной пиццерией. Она возвращает список координат.
2. Далее нам нужно всеми возможными способами пересекать массивы координат от разных пиццерий.
3. Генерирую все возможные сочетания N по K, где N — количество пиццерий, а К — убывает
4. И эти сочетания используются в качестве индексов в массиве с координатами пиццерий (с кварталами). Сочетания записываются в массив.
5. Массивы сочетаний пересекаются, и проверяется общие элементы. Начинаем с максимального числа пиццерий.
Вот такой мудреный алгоритм получился. Код еще мудренее…
Требования
Для языков PyPy4, Python 3.7.3, Python 2.7:
Ограничение памяти — 256 Мб
Ограничение времени — 60 секунд
Для других языков:
Ограничение памяти — 64 Мб
Ограничение времени — 1 секунда
За код прошу сильно не ругать, названия переменных немного перепутаны. Это конечный вариант, который тесты все равно не прошел.
Результат первых попыток:
Время: 60.04 с
Память: 45.9 Мб
Результат тестирования представленного выше кода:
Время: 1.004 с
Память: 258.9 Мб
Честно говоря, я не очень представляю как можно было при пиковых нагрузках сократить настолько время. Уже не помню, что именно я поменял в коде. Теперь стояла проблема уменьшить память. Я решил сократить до минимума количество list-ов и переменных. Удалял массивы сразу после потери в них необходимости, так как слабо представлял как работает память в python. И опять возвращаемся к словам разработчика со стажем.
Реализовать алгоритм на плюсах я поленился, решив все-таки почитать про выделение памяти, быстродействие алгоритма и олимпиадное программирование.
Решил я в период самоизоляции заняться чем-нибудь полезным, например, потренировать скилл в программировании. Из языков, которые нам преподавали в любимом ВУЗе, был только C++, который я не очень любил. Вот и последние пару месяцев стал изучать Python. Переходить с C++ на Python гораздо удобнее, чем наоборот, поэтому я быстро перестроился и стал наслаждаться его простотой.
Наткнулся я на Яндекс.Практикум, где есть раздел, посвященный алгоритмам. Хотелось быстрого code review и решил попробовать. Делюсь с Вами своими результатами.
Всего заданий было 7 (A-G), но я расскажу о пяти из них. Время было не ограничено, хотя на задачках по олимпиадному программированию оно фиксированно. Этот термин я узнал уже в процессе решения задач, изучая параллельно соответствующую литературу. Жаль, что обработчик Яндекса не может провести полноценного ревью и выдать результат, поэтому приходится довольствоваться малым. Ждать пока какой-либо тест будет не пройден и самому искать баг.
Итак, начнем:
A. Найди id
В медиа-сервисе зарегистрировано n пользователей. Все пользователи, за исключением двух, в последние два месяца посещали сайт. Нужно определить id пользователей, которые сайт не посещали.
Формат ввода:
Первая строка содержит число n — количество зарегистрированных пользователей. Это целое число в диапазоне от 2 до $inline$10^6$inline$
Во второй строке через пробел заданы различные n — 2 целых числа. Каждое из них не превосходит n и больше нуля.
Формат вывода:
Нужно в одной строке вывести по возрастанию два пропущенных числа, разделённые пробелом.
Пример
Ввод:
7
6 4 1 2 3
Вывод:
5 7
В примечании было сказано, что алгоритм должен работать не дольше, чем O(n).
Решил попробовать на языке, который совсем недавно пришел в мою жизнь, и крепко в ней закрепился (Python).
Краткий алгоритм:
1. Сортируем введенный массив
2. В цикле проверяем на совпадение итератора и значения массива
3. При несовпадении — добавляем недостающий элемент, а также этот элемент добавляем в другой массив.
Найти id. Python
count = int(input())
array = [int(i) for i in input().split()]
infinity = float("inf")
array.sort()
array.append(infinity)
array.append(infinity)
ar = []
for a in range(1, count + 1):
if array[a - 1] != a:
array.insert(a - 1, a)
ar.append(a)
print(" ".join(map(str, ar)))
В каждой из задач есть соответствующие требования по времени выполнения, а также по памяти. Для разных языков требования разные.
Например, для языков PyPy4, Python 3.7.3, Python 2.7:
Ограничение памяти — 256 Мб
Ограничение времени — 7.5 секунд
Для других языков:
Ограничение памяти — 64 Мб
Ограничение времени — 1 секунда
Все тесты пройдены успешно! Результат: Время — 135 мс, память — 11 Мб. Довольно неплохо для «медленного» питона.
B. Три фишки
Маша и Медведь играют в игру. У Маши есть фишки с указанным на них количеством очков. На каждой фишке — k очков, k находится в промежутке от $inline$-10^5$inline$ до $inline$10^5$inline$. Медведь называет число, а Маша должна выбрать три фишки, сумма очков на которых наиболее близка с заданному числу.
Формат ввода:
Первая строка содержит целое число n в диапазоне от $inline$-10^5$inline$ до $inline$10^5$inline$ число, названное первым участником. Во второй строке через пробел заданы целые числа в диапазоне от $inline$-10^5$inline$ до $inline$10^5$inline$ — очки для фишек второго участника. Их количество может быть от 3 до $inline$10^4$inline$
Формат вывода:
Нужно вывести целое число — сумму очков трёх фишек, наиболее близкую к n.
Пример
Ввод:
6
-1 -1 -9 -7 3 -6
Вывод:
1
Решение должно работать не дольше, чем за O($inline$n^2$inline$). Ограничение по памяти — O(1).
С этой задачкой я долго возился из-за того, что не проходил сначала ограничение по времени, потом по памяти. Я много слышал, что питон тратит достаточное количество ресурсов, поэтому после фейла с ним написал код на C++. Он тоже не выдержал тестов и провалился сначала на времени, потом на памяти. Может быть дело в несовершенном алгоритме?
Три фишки. Python
from itertools import combinations
number = int(input())
array = [int(i) for i in input().split()]
two_num_array = []
numeric = [a for a in range(0, number)]
for j in combinations(numeric, 3):
new = list(j)
two_num_array.append(array[new[0]] + array[new[1]] + array[new[2]])
print(min(two_num_array, key=lambda a: abs(a - number)))
Требования
Для всех языков:
Ограничение памяти — 64 Мб
Ограничение времени — 1 секунда
В результате тестирования кода получилось:
Время: 1.09 с
Память: 40 Мб
Все мои попытки уменьшить время проваливались и приводили только к увеличению памяти (странно конечно, потому что я пытался сократить количество типов данных list ).
Ну в C++ должно быть все хорошо. Он и быстрее и память под переменные поменьше должен выделять— сказал я, и бросился вспоминать плюсы.
Три фишки. C++
#include <set>
#include <vector>
#include <iostream>
using namespace std;
// Нерекурсивный алгоритм генерации сочетаний
bool NextSet(int *a, int n, int m)
{
int k = m;
for (int i = k - 1; i >= 0; --i)
if (a[i] < n - k + i + 1)
{
++a[i];
for (int j = i + 1; j < k; ++j)
a[j] = a[j - 1] + 1;
return true;
}
return false;
}
int main()
{
vector<int> vec_a;
set<int> end_set;
int min, num;
int M;
cin >> M;
int *ptr_d;
ptr_d = new int[M];
for (int m = 0; m < M; m++)
{
int n;
cin >> n;
ptr_d[m] = n;
}
int *a;
a = new int[M];
//Каждое число в сочетании кладем в вектор
for (int i = 0; i < M; i++)
{
a[i] = i + 1;
vec_a.push_back(i + 1);
}
if (M >= 3)
{
while (NextSet(a, M, 3))
{
for (int i = 0; i < 3; i++)
vec_a.push_back(a[i]);
}
}
//Последовательно каждые 3 элемента в векторе vec_a представляют собой //сочетания
for (int i = 0; i < vec_a.size() - 2; i++)
end_set.insert(ptr_d[vec_a[i] - 1] + ptr_d[vec_a[i+1] - 1] + ptr_d[vec_a[i+2] - 1]);
//В set ищем наиболее близкий по значению элемент перебором
//А тут можно было бы реализовать бинарный поиск, в set же значение отсортированы
std::set<int>::iterator it = end_set.begin();
min = abs(*it - M);
for (it = end_set.begin(); it != end_set.end(); ++it)
{
if (abs(*it - M) <= min)
{
min = abs(*it - M);
num = *it;
}
}
cout << num;
delete[] ptr_d;
delete[] a;
return 0;
}
Но и тут меня ждала неудача. Не уложился я теперь по лимиту использования памяти (80 Мб). Что за чушь! Удаляя некоторые динамические объекты, то есть заменяя вектора на массивы с динамическим выделением памяти, а то и на статические массивы, получилось только хуже. Для реализации представленного кода потребуется 121 Мб памяти (при граничных условиях, то есть при максимальной нагрузки). Так заявляет Яндекс.Практикум во всяком случае.
Я даже захотел сам написать unit-тесты и сравнить результаты, но руки до этого не дошли.
Итак, задача осталась со статусом: частичное решение…
C. Разгадай шифр
Шерлок Холмс и доктор Ватсон передают друг другу зашифрованные сообщения, состоящие из чисел. Каждое число может обозначать одну букву, слово или знак препинания. Получая последовательность чисел, Холмс и Ватсон могут расшифровывать сообщения друг друга.
Однако они стали подозревать, что кто-то разгадал их шифр и повысили уровень безопасности. Теперь каждое сообщение зашифровано в матрице. Чтобы его прочитать, нужно распечатать значения матрицы по спирали, начиная от центра вверх и далее по часовой стрелке.
Формат ввода:
Первая строка содержит целое нечётное число m в диапазоне от 1 до 1000 — количество строк и столбцов матрицы.
В каждой из следующих m строк даны m целых чисел в диапазоне от -1000 до 1000, разделённых пробелом.
Формат вывода:
Нужно вывести значения в матрице, начиная с центра по спирали. Движение вверх, далее по часовой стрелке. Каждое число выводится в отдельной строке.
Пример
Ввод:
3
9 10 7
0 7 7
8 3 4
Вывод:
7
10
7
7
4
3
8
0
9
Эта задачка показалась мне очень сложной и, не долго думая, начал гуглить. Похожий пример нашел на плюсах, но там реализовали наоборот закручивание матрицы от первого элемента[0][0] до середины[N/2][N/2]. Мои попытки обойтись «малой кровью», то есть внести в алгоритм небольшие поправки, закончились неудачей. Пришлось досконально разбираться в коде, модернизируя его. Это очень полезный навык понимать чужой код и уметь его применять для своих нужд. Не все же время с нуля писать проекты.
Разгадай шифр. С++
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;
int main()
{
int N;
vector<int> array;
ifstream file("input.txt");
if (!file) {
std::cout << "Not open " << endl;
return -1;
}
ofstream out_file("output.txt");
file >> N;
int r = N/2;
int **mtrx;
mtrx = new int*[N];
for (int i = 0; i < N; i++) mtrx[i] = new int[N];
//Считаем матрицу из файла
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
file >> mtrx[i][j];
int rowBeg = N / 2 - 1;
int rowEnd = N / 2;
int colBeg = N / 2;
int colEnd = N / 2 + 1;
// раскручиваем
while (r--)
{
for (int i = rowEnd; i > rowBeg; i--)
{
array.push_back(mtrx[i][colBeg]);
}
for (int i = colBeg; i < colEnd; i++)
{
array.push_back(mtrx[rowBeg][i]);
}
for (int i = rowBeg; i < rowEnd + 1; i++)
{
array.push_back(mtrx[i][colEnd]);
}
for (int i = colEnd; i >= colBeg; i--)
{
array.push_back(mtrx[rowEnd + 1][i]);
}
colBeg--;
rowBeg--;
colEnd++;
rowEnd++;
}
//Всегда остается последняя часть недокручена. Цикл необходим для этого
for (int i = rowEnd; i > rowBeg; i--)
{
array.push_back(mtrx[i][colBeg]);
}
for (auto &i : array)
out_file << i << "\n";
for (int i = 0; i < N; i++)
delete[] mtrx[i];
delete[] mtrx;
out_file.close();
file.close();
return 0;
}
Требования
Для всех языков:
Ограничение памяти — 33 Мб
Ограничение времени — 1.4 секунда
Java:
Ограничение памяти — 286 Мб
Ограничение времени — 9 секунд
Node JS 8.16:
Ограничение памяти — 256 Мб
Ограничение времени — 15 секунд
Результаты меня приятно порадовали, так как все тесты пройдены с первого раза. Ну о качестве кода судить Вам.
В результате тестирования кода получилось:
Время: 180 мс
Память: 7.83 Мб
В процессе написания кода, начинаешь задумывать о размере выделяемой памяти и скорости алгоритма. Очень просто использовать библиотеку STL, а вот что у нее «под капотом» ответит не каждый. На работе зашла речь об STL с парнем, который как и я начинают свою карьеру программистом. Он немного прогал на С и возник вопрос о динамической памяти. Я покачал головой, сказав что в таких случаях использую STL в C++ и не парюсь. Наш разговор услышал разработчик со стажем и сказал, что всех нас надо заставить писать на чистом С, чтобы понять всю боль и прелесть языка. Наверное он прав, но сложно перейти с питона обратно на C. Ладно, продолжим решать задачки.
D. Морской бой
Поиграем в морской бой. Поле представлено матрицей n на m. Длина кораблей ограничена размерами матрицы. Корабли могут быть расположены либо горизонтально, либо вертикально. Соприкасаться друг с другом они могут, пересекаться — нет. По полю несколько раз выстрелили. Нужно выяснить, сколько кораблей было сбито и сколько ранено.
Формат ввода
В первой строке подаются числа n и m, $inline$1≤n,m≤10^4$inline$
В следующей строке — количество кораблей k, $inline$0≤k≤10^4$inline$
В следующих k строках — описание кораблей: 4 числа через пробел. Первая пара чисел определяет ячейку матрицы, то есть номер строки и столбца, где расположено начало корабля. Вторая пара соответствует концу корабля. Нумерация строк и столбцов начинается с 0.
Далее следует s — количество выстрелов, целое число в диапазоне от 0 до 10000.
В следующих s строках — описание выстрелов: пара чисел через пробел. Первое число соответствует номеру строки на поле для ячейки, куда попал выстрел, второе — номеру столбца. Стрелять в ячейку более одного раза нельзя.
Формат вывода
Нужно вывести 2 числа в строке, разделённые пробелом. Первое число — количество раненых кораблей, второе число — количество сбитых. Корабль считается сбитым, если выстрелы попали во все занимаемые им ячейки. Раненым — если задета хоть одна ячейка.
Пример
Ввод:
5 5
4
4 0 4 1
4 3 4 4
2 2 2 2
1 4 2 4
5
4 0
4 1
0 0
4 4
2 2
Вывод:
1 2
Конечно же я не бросил все и начал читать Кернигана и Ритчи. Нет, я просто продолжил писать на Python. Алгоритм получился не очень изящный:
1. Решил, что необходимо добавлять не только координаты начала и конца кораблей, а все его части.
2. Потом сравнивать координаты выстрелов с координатами кораблей и, если попал, то удалять координату. Сразу проверяем на нулевую длину. При положительном результате kill++.
3. Проверку на раненые корабли организовал через цикл, пробегаясь по кораблям и сравнивая исходные координаты с первоначальными.
Морской бой. Python
Q = str(input())
N = int(input())
field = []
shot_coord = []
len_ship = []
killed = 0
injured = 0
for c in range(0, N):
array = [int(i) for i in input().split()]
coord1 = [array[0], array[1]]
coord2 = [array[2], array[3]]
boat = []
if abs(coord2[0] - coord1[0]) > 0:
for i in range(coord1[0], coord2[0] + 1):
boat.append([i, coord2[1]])
elif abs(coord2[1] - coord1[1]) > 0:
for i in range(coord1[1], coord2[1] + 1):
boat.append([coord2[0], i])
else:
boat.append([coord1[0], coord1[1]])
len_ship.append(len(boat))
field.append(boat)
M_shot = int(input())
for i in range(0, M_shot):
ar = [int(i) for i in input().split()]
shot_coord.append(ar)
for temp in shot_coord:
for sh in field:
for q in sh:
if temp == q:
sh.remove(q)
if len(sh) == 0:
killed = killed + 1
for i in range(0, len(field)):
if len_ship[i] != len(field[i]) and len(field[i]) != 0:
injured = injured + 1
print(str(injured) + " " + str(killed))
Требования
Для всех языков:
Ограничение памяти — 64 Мб
Ограничение времени — 1 секунда
И опять с первого раза уложился! Статус полное решение и все 17 тестов пройдены.
Результат:
Время: 30мс
Память: 3.98 Мб
Конечно за 3 вложенных цикла меня можно поставить к стенке, но на первый взгляд мне эта идея показалась рабочей. Надо бы поработать над совершенством кода, но меня ждет еще одна задачка.
E. Самый пиццовый квартал
Мэр города Плужникова решил открыть серию пиццерий в городе. Город представлен в виде матрицы NxN, где каждая ячейка на позиции [i][j] — это отдельный квартал. Доставка из каждой пиццерии возможна не далее, чем на R кварталов от её расположения. Расстояние определяется минимальным количеством кварталов, которые пройдёт доставщик, если он передвигается по горизонтали или по вертикали. Ходить по диагонали нельзя. Например, представим, что N=5,R=2, и пиццерия расположена в ячейке (3,3). Тогда доставить пиццу можно в кварталы, помеченные символом X.
00X00
0XXX0
XXXXX
0XXX0
00X00
Артёмка очень любит пиццу. Он хочет попасть в квартал, где доступно максимальное количество заказов из разных пиццерий, чтобы выбрать лучшую. Помогите Артёмке найти максимальное количество доступных пиццерий, если он попадет в квартал, где это значение не меньше, чем в любом другом.
Формат ввода
В первой строке заданы через пробел два числа: N и M, оба принадлежат отрезку [1, 1000].N обозначает размерность города в кварталах по горизонтали и по вертикали. M — число пиццерий в городе. В следующих M строках каждая пиццерия описана значениями X,Y,R. X и Y— это квартал, где пиццерия расположена. (1≤X,Y≤N), R— максимальная дистанция, на которую можно заказать доставку. (1≤R≤100).
Формат вывода
Выведите одно число — максимально возможное количество пиццерий, из которых доставляют в квартал, где это значение не меньше любого другого.
Пример
Ввод:
8 2
5 3 3
6 1 5
Вывод:
2
В двух словах об алгоритме:
1. Создается функция, которая генерит все кварталы, покрываемые одной пиццерией. Она возвращает список координат.
2. Далее нам нужно всеми возможными способами пересекать массивы координат от разных пиццерий.
3. Генерирую все возможные сочетания N по K, где N — количество пиццерий, а К — убывает
4. И эти сочетания используются в качестве индексов в массиве с координатами пиццерий (с кварталами). Сочетания записываются в массив.
5. Массивы сочетаний пересекаются, и проверяется общие элементы. Начинаем с максимального числа пиццерий.
Вот такой мудреный алгоритм получился. Код еще мудренее…
Самый пиццовый квартал. Python
from functools import reduce
from itertools import combinations
def count_cover(pizza_x, pizza_y, Rad, N):
cover_liner = []
pizza_y_ = pizza_y
R_ = Rad
while pizza_y_ != -1:
for i in range(pizza_x - R_, pizza_x + R_ + 1):
if i >= 0 and i < N:
cover_liner.append(pizza_y_ * N + i)
pizza_y_ = pizza_y_ - 1
R_ = R_ - 1
pizza_y_ = pizza_y + 1
R_ = Rad - 1
while pizza_y_ != N:
for i in range(pizza_x - R_, pizza_x + R_ + 1):
if i >= 0 and i < N:
cover_liner.append(pizza_y_ * N + i)
pizza_y_ = pizza_y_ + 1
R_ = R_ - 1
return cover_liner
info = [int(i) for i in input().split()]
count_pizza_house = info[1]
end_array = []
array_for_intersection = []
for a in range(0, count_pizza_house):
pizza = [int(i) for i in input().split()]
end_array.append(count_cover(pizza[0] - 1, pizza[1] - 1, pizza[2], info[0]))
pizza.clear()
numeric = [a for a in range(0, count_pizza_house)]
pizza.clear()
info.clear()
for i in range(count_pizza_house, 0, -1):
for j in combinations(numeric, i):
info.append(list(j))
array_for_intersection.clear()
for i_mass in info:
for q in i_mass:
array_for_intersection.append(end_array[q])
intersection = list(reduce(lambda u, v: u & v, (set(x) for x in array_for_intersection)))
if len(intersection) > 0:
print(len(array_for_intersection))
break
array_for_intersection.clear()
del end_array
del count_coverТребования
Для языков PyPy4, Python 3.7.3, Python 2.7:
Ограничение памяти — 256 Мб
Ограничение времени — 60 секунд
Для других языков:
Ограничение памяти — 64 Мб
Ограничение времени — 1 секунда
За код прошу сильно не ругать, названия переменных немного перепутаны. Это конечный вариант, который тесты все равно не прошел.
Результат первых попыток:
Время: 60.04 с
Память: 45.9 Мб
Результат тестирования представленного выше кода:
Время: 1.004 с
Память: 258.9 Мб
Честно говоря, я не очень представляю как можно было при пиковых нагрузках сократить настолько время. Уже не помню, что именно я поменял в коде. Теперь стояла проблема уменьшить память. Я решил сократить до минимума количество list-ов и переменных. Удалял массивы сразу после потери в них необходимости, так как слабо представлял как работает память в python. И опять возвращаемся к словам разработчика со стажем.
Реализовать алгоритм на плюсах я поленился, решив все-таки почитать про выделение памяти, быстродействие алгоритма и олимпиадное программирование.