В этой задаче надо было заметить, что для замощения вертикали нужно не менее $$$\lceil{\frac{n}{a}}\rceil{}$$$ плиток, где $$$\lceil{x}\rceil$$$ — округление вверх. Для замощения горизонтали нужно не менее $$$\lceil{\frac{m}{a}}\rceil{}$$$ плиток. Тогда итоговый ответ равен произведению этих количеств.
Это специальная задача на освещение 2-х важных моментов:
- Во-первых нельзя суммировать числа от А до Я обычным циклом, это будет слишком медленно. В худшем случае придется суммировать числа от $$$-10^9$$$ до $$$10^9$$$, то есть $$$2*10^9$$$ чисел, и эту сумму придется считать $$$5*10^5$$$ раз. Итоговое число операций это $$$2*10^9*5*10^5 = 10^{15}$$$, что слишком много, ведь за одну секунду компьютер может выполнять порядка $$$10^8$$$ операций. Ограничение на 1 тест при этом — 1 секунда. Таким образом такой программе понадобилось бы порядка $$$\frac{10^{15}}{10^8}=10^7$$$ секунд на вычисление ответа, что в 10 миллион раз дольше, чем надо. Для быстрого вычисления суммы чисел арифметической прогрессии надо пользоваться известной формулой: $$$a_1 + a_2 + ... + a_n = \frac{(a_1 + a_n) * n}{2}$$$.
- Второй момент состоит в том, что на вход программе в худшем случае подается по 2 числа $$$2*10^5$$$ раз, то есть суммарно миллион чисел. Ввод и вывод данных программой — очень медленная операция, поэтому на некоторых языках типа python скорее всего не получится сдать задачу совсем (на официальных соревнованиях обычно вообще не гарантируется, что все задачи можно сдать на python), а на других языках нужно использовать ускорение ввода/вывода. В C++ это обычно делается командами
cin.tie(0);иios_base::sync_with_stdio(false);. Кроме того, если вы пишете на C++ надо не забыть писать"\n"вместоendlдля переноса строки. Последняя команда всегда сбрасывает буфер вывода, поэтому работает медленнее (буферизация символов — это сохранение их во временном месте, чтобы потом вывести их кучкой за раз. Это нужно, потому что некоторые устройства имеют медленный доступ, и обращение в ним после каждого символа очень замедляет программу).
Здесь все просто: чтобы сэкономить максимальную сумму, надо выносить самые дорогие товары. Для этого достаточно отсортировать массив и посчитать сумму $$$k$$$ самых дорогих элементов. Нужно помнить, что нельзя $$$k$$$ раз искать самый дорогой элемент втупую по всему массиву (слишком медленно) и что $$$k$$$ может быть больше, чем $$$n$$$.
Эта задача является чисто реализационной — нужно хорошо знать базовые конструкции своего языка программирования и аккуратно имплементировать то, что просят в условии. Проще всего это было сделать так: завести трехмерный массив/вектор/лист и сохранить в него ввод. Далее нужно итерироваться только по "внутренности" этого трехмерного массива, т.к. нас не интересуют кубики, которые находятся на его границе, они автоматически не являются изолированными. Для каждого кубика внутри мы проверяем, что он со всех 6 сторон окружен единицами. При этом нам не надо проверять выход за границы массива, так как мы итерируемся только по внутренним ячейкам.
Это немного нетипичная задача, в которой часть условия находится прямо в тесте, а именно: изначальное число вирусов и множитель, во сколько раз увеличивается их число каждую секунду, надо вычислить из теста в условии. Из условия ясно, что число вирусов в каждый момент времени — геометрическая прогрессия. Тогда отношение $$$\frac{352947}{1029}=343$$$ — во сколько раз увеличилось число вирусов за 3 секунды, с 3 по 6. Тогда $$$\sqrt{343}=7$$$ — множитель геометрической прогрессии. Поделим 1029 на 7 3 раза, чтобы узнать число вирусов в начальный момент — нулевую секунду. $$$\frac{1029}{7^3}=3$$$. Таким образом мы можем вычислить число вирусов в любую секунду t: $$$3*7^t$$$.
Эта несложная идейная задача основана на следующих наблюдениях:
- Во-первых, нужно вычеркнуть само число $$$k$$$. Таким образом не будет подмножества из 1-го элемента с суммой $$$k$$$.
- Во-вторых, нужно что-то сделать с подмножествами из двух элементов и суммой $$$k$$$. Все такие подмножества имеют очевидный вид: $$$i$$$ и $$$k-i$$$, где $$$0 \lt i \lt k$$$. В каждой такой паре нужно вычеркнуть минимум одно число. Здесь заметим, что в каждой такой паре одно из чисел будет больше или равно $$$\frac{k}{2}$$$. Тогда, если мы вычеркнем меньшие числа, то больше не будет подмножеств с суммой равной $$$k$$$, потому что мы уже обработали все подмножества из 1 и 2 элементов, а в любых других подмножествах будет минимум по 3 элемента, больших или равных $$$\frac{k}{2}$$$, что будет больше или равно $$$\frac{3*k}{2}$$$, что уже больше $$$k$$$.




