e-olymp 683. Частичная сумма матрицы

Задача

Задана матрица чисел $a_{ij}$ где $1 \leqslant i \leqslant n$, $1 \leqslant j \leqslant m$. Для всех $i, j$ найдите $$S_{i,j}=\sum_{k=1, t=1}^{k\leqslant i, t \leqslant j}a_{kt}.$$

Входные данные

В первой строке записаны размеры матрицы — $n, m$ $(1 \leqslant n, m \leqslant 1000)$. В последующих $n$ строках записано по $m$ чисел $a_{ij}$ $(1 \leqslant a_{ij} \leqslant 1000)$.

Выходные данные

Выведите $n$ строк по $m$ чисел $S_{i,j}$.

Тесты

Входные данные Выходные данные
3 5
1 2 3 4 5
5 4 3 2 1
2 3 1 5 4
1 3 6 10 15
6 12 18 24 30
8 17 24 35 45
4 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16
6 7
15 78 69 36 567 654 5
54 54 52 81 237 5 98
987 2 65 5 32 89 67
541 89 4 32 4 1 40
68 7 345 6 21 23 56
9 5 7 2 5 4 1000
15 93 162 198 765 1419 1424
69 201 322 439 1243 1902 2005
1056 1190 1376 1498 2334 3082 3252
1597 1820 2010 2164 3004 3753 3963
1665 1895 2430 2590 3451 4223 4489
1674 1909 2451 2613 3479 4255 5521

Код программы

 

Решение

Создаем  матрицу x[1001][1001]  вне int main() . Сдвигаем индексацию массива на единицу и заполняем его. Таким образом первая строка и первый столбец у нас оказываются заполнены нулями. Чтобы не вычислять каждую новую $S_{i,j}$ от $(i+1)\cdot (j+1)$ предыдущих значений, воспользуемся основным свойством частичных сумм: если $$S_{i,j}=\sum_{k=1, t=1}^{k\leqslant i, t \leqslant j}a_{kt},$$ то тогда $S_{i,j} — a_{ij}=S_{i-1,j}+S_{i,j-1}-S_{i-1,j}\cap S_{i,j-1}$, где $S_{i-1,j}\cap S_{i,j-1} = S_{i-1,j-1}$. Тогда при $1 \leqslant i \leqslant n$, $1 \leqslant j \leqslant m$ вычисляем частичные суммы по формуле: $$S_{i,j} = S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}+a_{ij}.$$

Ссылки

Условие задачи на E-olymp

Код программы на IdeOne

e-olymp 2524. Строки Фибоначчи

Задача

В математике достаточно часто применяются так называемые рекуррентные соотношения. Обычно они применяются для задания числовых последовательностей, но могут применяться и для задания последовательностей строк.

Одним из примеров строк, задаваемых рекуррентным соотношением являются строки Фибоначчи $F_{0} = a$, $F_{1} = b$, … . Они задаются следующим образом: $F_{0} = a$, $F_{1} = b$, $F_{i} = F_{i-2}F_{i-1}$, $i >1$. Первые семь строк Фибоначчи выглядят следующим образом: $a$, $b$, $ab$, $bab$, $abbab$, $bababbab$, $abbabbababbab$.

Дима занимается в кружке олимпиадного программирования и интересуется алгоритмами на строках. Недавно он узнал о строках Фибоначчи. Он быстро понял, что их длина с увеличением номера $n$ растет очень быстро, поэтому задача нахождения всех символов строки $F_{n}$ требует слишком большого объема памяти. Поэтому он решил ограничиться задачей нахождения некоторых символов.

Напишите программу, которая находит $k$-ый символ строки $F_{n}$.

Входные данные

Первая строка содержит количество тестов $t$ ($1 ≤ t ≤ 100$). Каждая из следующих $t$ строк содержит два целых числа $n$ и $k$ ($0 ≤ n ≤ 45$, $1 ≤ k ≤ |F_{n}|$, через $|F_{n}|$ обозначена длина строки $F_{n}$, позиции символов в строке нумеруются с единицы).

Выходные данные

Выведите $t$ строк, каждая из которых содержит $k$-ый символ строки $F_{n}$.

Тесты

Входные данные Выходные данные
4
0 1
1 1
3 2
7 7
a
b
a
a
1
10 15
a
6
45 6
38 30
6 5
24 40
0 1
2 2
b
a
b
b
a
b

Код программы

Решение

Воспользуемся тем, что длина $i$-той строки Фибоначчи будет равна $i$-тому числу Фибоначчи, так как для них справедливо одно и то же рекуррентное соотношение. Заводим массив fib[45]; , куда мы вычислим первые ($n ≤ 45$) числа Фибоначчи. Функция solve(int n, int k)  находит $k$-ый символ строки $F_{n}$: так как $F_{i} = F_{i-2}F_{i-1}$, то если $k ≤ |F_{n-2}|$, то $k$-ый символ строки следует искать в $F_{n-2}$, в другом случае следует искать $(k — F_{n-2})$-ый символ в $F_{n-1}$. Таким образом, постепенно углубляясь в рекурсию, программа будет иметь дело с задачами все меньших размеров, пока наконец не выйдет на одну из единичных строк ( n == 0  или n == 1 ), и не выведет $a$ или $b$ соответственно.

Ссылки

Условие задачи на E-olymp

Код программы на IdeOne

e-olymp 910. Среднее арифметическое положительных

Задача

Задана последовательность вещественных чисел. Найти среднее арифметическое положительных чисел.

Входные данные

В первой строке задано количество чисел $n$ ($0 < n ≤ 100$). В следующей строке заданы $n$ действительных чисел, значения которых не превосходят по модулю $100$.

Выходные данные

Вывести среднее арифметическое положительных чисел с двумя десятичными знаками. В случае отсутствия положительных чисел вывести сообщение $Not$ $Found$.

Тесты

Входные данные Выходные данные
3
5.2 -2 4
4.60
3
-5.2 -2 -4
Not Found
5
16 -78 56 1 -3
24.33
1
17.33
17.33
1
-17.33
Not Found

Код программы

Решение

В начале читаем из потока общее количество чисел n . Затем с помощью цикла остальные числа, одновременно проверяя положительные ли они. Если число положительное, то прибавляем его к общей сумме и увеличиваем счетчик k++ . В конце s!=0 означает, что в потоке есть хотя бы одно положительное число — тогда мы высчитываем и выводим $\frac{s}{k}$ с двумя знаками после запятой. В противном случае — $Not$ $Found$.

Код программы (Тернарная операция)

Решение

Для вывода ответа с помощью тернарной операции необходимо, чтобы выходные данные были одного типа. Используем метод to_string, предварительно округлив $s$ до двух знаков после запятой. Так как при использовании метода  double переводится с шестью знаками после запятой, то используем erase, чтобы удалить лишние четыре.

Ссылки

Условие задачи на E-olymp

Код программы на IdeOne (1)

Код программы на IdeOne (2)

 

e-olymp 971. Задача Иосифа Флавия

Задача Иосифа Флавия

Существует легенда, что Иосиф Флавий — известный историк первого века — выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из $41$ иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Однако Иосиф наряду с одним из своих единомышленников счел подобный конец бессмысленным — он быстро вычислил спасительные места в порочном круге, на которые поставил себя и своего товарища. И лишь поэтому мы знаем его историю.

В нашем варианте мы начнем с того, что выстроим в круг $N$ человек, пронумерованных числами от $1$ до $N$, и будем исключать каждого $k$-ого до тех пор, пока не уцелеет только один человек. (Например, если $N=10$, $k=3$, то сначала умрет $3$-й, потом $6$-й, затем $9$-й, затем $2$-й, затем $7$-й, потом $1$-й, потом $8$-й, за ним — $5$-й, и потом $10$-й. Таким образом, уцелеет $4$-й.)

Входные данные

Во входном файле даны натуральные числа $N$ и $k$. $1≤N≤500$, $1≤k≤100$.

Выходные данные

Выходной файл должен содержать единственное число — номер уцелевшего человека.

Тесты

Ввод Вывод
1 10 3 4
2 500 100 480
3 50 10 36
4 1 1 1
5 41 3 31

Код программы

Решение

Все люди в кругу пронумерованы от $0$ до $N-1$, началом будет person = 0 . Нужно исключить $person+(k-1)$ человека. Начальная позиция следующего раунда $person + k$. Но если номер исключенного человека $N-1$, следующая начальная позиция $N$, что выходит за пределы круга, по-этому мы берем остаток от деления на количество оставшихся в живых людей: (person + k) % count .

Таким образом круг уменьшается на одного человека, при этом номер уцелевшего в круге размера $N$ равняется номеру в получившемся круге размера $N-1$. Предполагаем, что это работает и в обратную сторону: берем круг размером  count = 2, высчитываем, кто будет в начальной позиции в следующем раунде. count в таком случае количество не убитых, а живых, и оно увеличивается с каждым раундом до $N$. В конце прибавляем $1$, потому что в начале все значения были сдвинуты.

Ссылки

Условие задачи на E-olymp

Код программы на IdeOne

e-olymp 8352. Такси

Такси

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

Входные данные

Три натуральных числа, не превосходящих $100$ — количество пассажиров в первой, второй и третьей маршрутках соответственно.

Выходные данные

Выведите одно число — наименьшее количество пассажиров, которое требуется пересадить. Если это невозможно, выведите слово [latex]IMPOSSIBLE[/latex]  (заглавными буквами).

Тесты

Ввод Вывод
1 1 2 3 1
2 100 100 99 IMPOSSIBLE
3 100 100 100 0
4 19 59 6 31
5 30 9 74 IMPOSSIBLE

Код программы (Линейные вычисления)

Решение

В начале выводим полную формулу. Для этого находим, сколько пассажиров должно быть в одном автобусе после всех перестановок : $\frac{b1 + b2 + b3}{3}$. Далее, от количества пассажиров в каждом автобусе изначально отнимаем требуемое значение. Так как оно может отличаться как в плюс, так и в минус используем модуль : $|b1-need|+|b2-need|+|b3-need|$. А так как «излишки» перераспределяются между оставшимися двумя автобусами, то чтобы избежать повторения мы делим все на $2$ : $\frac{|b1-need|+|b2-need|+|b3-need|}{2}$.

Далее мы вычисляем, существует ли остаток от деления общего количества пассажиров на $3$; для этого используем логическую переменную. Если остаток существует и  f == true  , то  выводится [latex]IMPOSSIBLE[/latex].  Если же f == false , то вычисляется и выводится количество перестановок пассажиров.

 

Код программы (Ветвление)

Решение

Алгоритм решения в данном случае полностью повторяет предыдущий, но с помощью условного оператора мы можем сразу же проверить сумму пассажиров на делимость, вывести [latex]IMPOSSIBLE[/latex] и завершить программу не вычисляя формулы.

Ссылки

Условие задачи на E-Olymp

Код программы на IdeOne (Линейные вычисления)

Код программы на IdeOne (Ветвление)