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

20/06/2019 by Дария Даниленко

Задача

Задана матрица чисел $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

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

#include <iostream>
using namespace std;

int x[1001][1001];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
          for (int j = 1; j <= m; j++) cin >> x[i][j];
    }
    for (int i = 1; i <= n; i++){
          for (int j = 1; j <= m; j++) x[i][j] += x[i-1][j] + x[i][j-1] - x[i-1][j-1];
    }
    for (int i = 1; i <= n; i++){
          for (int j = 1; j <= m; j++){
            cout << x[i][j]; 
            if (j != m) cout << " ";
          }
          cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int x[1001][1001];

int main() {

int n, m;

cin >> n >> m;

for (int i = 1; i <= n; i++){

for (int j = 1; j <= m; j++) cin >> x[i][j];

}

for (int i = 1; i <= n; i++){

for (int j = 1; j <= m; j++) x[i][j] += x[i-1][j] + x[i][j-1] - x[i-1][j-1];

}

for (int i = 1; i <= n; i++){

for (int j = 1; j <= m; j++){

cout << x[i][j];

if (j != m) cout << " ";

}

cout << endl;

}

return 0;

}

Решение

Создаем матрицу 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

Related Images:

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

26/05/2019 by Дария Даниленко

Задача

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

Одним из примеров строк, задаваемых рекуррентным соотношением являются строки Фибоначчи $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

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

#include <iostream>
using namespace std;

int fib[45];

char solve(int n, int k) {
    if (n == 0) return 'a';
    if (n == 1) return 'b';
    if (k <= fib[n - 2]) return solve(n - 2, k);
    return solve(n - 1, k - fib[n - 2]);
}

int main() {
    int n, k, tests;
    fib[0] = 1;
    fib[1] = 1;
    for (int i = 2; i < 45; i++) fib[i] = fib[i - 1] + fib[i - 2];
    cin >> tests;
    while (tests--) {
        cin >> n >> k;
        cout << solve(n, k) << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int fib[45];

char solve(int n, int k) {

if (n == 0) return 'a';

if (n == 1) return 'b';

if (k <= fib[n - 2]) return solve(n - 2, k);

return solve(n - 1, k - fib[n - 2]);

}

int main() {

int n, k, tests;

fib[0] = 1;

fib[1] = 1;

for (int i = 2; i < 45; i++) fib[i] = fib[i - 1] + fib[i - 2];

cin >> tests;

while (tests--) {

cin >> n >> k;

cout << solve(n, k) << endl;

}

return 0;

}

Решение

Воспользуемся тем, что длина $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

Related Images:

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

24/02/2019 by Дария Даниленко

Задача

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

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

В первой строке задано количество чисел $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

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

#include <iostream>
#include <iomanip>
using namespace std;
int main() {
  int n, k = 0; // n - общее кол-во чисел в потоке; k - кол-во положительных чисел;
  double x; // x - число, считываемое с потока;
  double s = 0; // s - сумма положительных чисел;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> x;
    if (x > 0) {
      s += x;
      k++;
    }
  }
  if (s > 0) cout << fixed << setprecision(2) << s / k;
  else cout << "Not Found";
  return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

int n, k = 0; // n - общее кол-во чисел в потоке; k - кол-во положительных чисел;

double x; // x - число, считываемое с потока;

double s = 0; // s - сумма положительных чисел;

cin >> n;

for (int i = 0; i < n; i++) {

cin >> x;

if (x > 0) {

s += x;

k++;

}

if (s > 0) cout << fixed << setprecision(2) << s / k;

else cout << "Not Found";

return 0;

}

Решение

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

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

#include <iostream>
#include <iomanip>

using namespace std;

int main() {
  int n, k = 0;
  double x, s = 0;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> x;
    if (x > 0) {
      s += x;
      k++;
    }
  }
  s = int(s / k * 100 + 0.5) / 100.0;
  string str = to_string(s);
  str.erase(str.end() - 4, str.end());
  cout << ((s > 0) ? str : "Not Found");
  return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

int n, k = 0;

double x, s = 0;

cin >> n;

for (int i = 0; i < n; i++) {

cin >> x;

if (x > 0) {

s += x;

k++;

}

s = int(s / k * 100 + 0.5) / 100.0;

string str = to_string(s);

str.erase(str.end() - 4, str.end());

cout << ((s > 0) ? str : "Not Found");

return 0;

}

Решение

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

Ссылки

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

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

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

Related Images:

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

05/02/2019 by Дария Даниленко

Существует легенда, что Иосиф Флавий — известный историк первого века — выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из $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

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

#include <iostream>
using namespace std;

int main() {
    int n, k, p;
    cin >> n >> k;
    int person = 0;
    for (int count = 2; count <= n; count++) person = (person + k) % count;
    cout << person+1;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, k, p;

cin >> n >> k;

int person = 0;

for (int count = 2; count <= n; count++) person = (person + k) % count;

cout << person+1;

return 0;

}

Решение

Все люди в кругу пронумерованы от $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

Related Images:

e-olymp 8352. Такси

08/11/2018 by Дария Даниленко

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

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

Три натуральных числа, не превосходящих $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

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

#include <iostream>
#include <cmath>
  using namespace std;

int main() {
  int b1, b2, b3, pas, need; 
  bool f;
  cin >> b1 >> b2 >> b3;
  need = (b1 + b2 + b3)/3;
  pas = (abs(b1 - need) + abs(b2 - need) + abs(b3 - need)) / 2;
  f = (b1 + b2 + b3) % 3;
  (f == true) and cout << "IMPOSSIBLE";
  (f == false) and cout << pas;
  return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int b1, b2, b3, pas, need;

bool f;

cin >> b1 >> b2 >> b3;

need = (b1 + b2 + b3)/3;

pas = (abs(b1 - need) + abs(b2 - need) + abs(b3 - need)) / 2;

f = (b1 + b2 + b3) % 3;

(f == true) and cout << "IMPOSSIBLE";

(f == false) and cout << pas;

return 0;

}

Решение

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

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

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

#include <iostream>
#include <cmath>
  using namespace std;

int main() {
    int b1, b2, b3, need;
    cin >> b1 >> b2 >> b3;
    need = (b1 + b2 + b3) / 3;
    if ((b1 + b2 + b3) % 3!=0) {
        cout << "IMPOSSIBLE";
    }
    else cout << (abs(b1 - need) + abs(b2 - need) + abs(b3 - need))/2;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int b1, b2, b3, need;

cin >> b1 >> b2 >> b3;

need = (b1 + b2 + b3) / 3;

if ((b1 + b2 + b3) % 3!=0) {

cout << "IMPOSSIBLE";

}

else cout << (abs(b1 - need) + abs(b2 - need) + abs(b3 - need))/2;

return 0;

}

Решение

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

Ссылки

Условие задачи на E-Olymp
Код программы на IdeOne (Линейные вычисления)
Код программы на IdeOne (Ветвление)