Category Archives: 5. Массивы

Задачи на использование классических массивов и работе с ними через указатели и ссылочные типы.

Массивы

Опубликовано: 20/10/2014

К этой рубрике относятся задания на использование классических массивов, работе с ними через указатели и ссылочные типы. Желательно снова перечитать параграф 3.5 и 3.6 из праймера. Размер массива обычно будет читаться из входного потока. Это вынуждает использовать динамические массивы. В качестве заготовки можно использовать такой код:

#include <iostream>
using namespace std;
 
int main() {
    size_t n;   
    cin >> n;
    double *x = new double [n];
    for(size_t i = 0; i < n; i++)
        cin >> x[i];
        
    // Processing 
    for(size_t i = 0; i < n; i++)
        cout << "x[" << i << "] = " << x[i] << "\t";
}

#include <iostream>

using namespace std;

int main() {

size_t n;

cin >> n;

double *x = new double [n];

for(size_t i = 0; i < n; i++)

cin >> x[i];

// Processing

for(size_t i = 0; i < n; i++)

cout << "x[" << i << "] = " << x[i] << "\t";

}

Выполнить программу Обратите внимание, что цикл в котором … Continue reading →

нет комментариев

В классе и дома решаются следующие тренировочные задачи (1 балл):

Санта Клаус
Кубики — 3 — используйте массив bool для хранения предположений о потери кубика для каждой из 26+26=52 букв.
Прямоугольник — используйте массив точек.

Опубликованные решения

e-olymp 7258. Числовые операции

12/04/2021 by Філіпенко Микита

Условие

На доске записано число $1$. Каждую секунду Петя может провести над числом одну из двух операций: либо прибавить к числу $1$, либо произвольным образом переставить цифры числа (но так, чтобы на первом месте оказался не ноль). После этого Петя вытирает с доски старое число и записывает вместо него получившееся.

Задание

Напишите программу, которая для заданного натурального числа определяет, за какое наименьшее число операций Петя может, начав с единицы, дойти до этого числа.

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

Первая строка входного файла содержит число $T (1 \leqslant T < 10^4$), которое задает количество чисел во входном файле, для которых требуется найти ответ. В последующих T строках задано по одному натуральному числу $N_i$,$2\leqslant N_i < 10^9$, $1 \leqslant i \leqslant T$. Известно, что среди чисел $N_i, 1 \leqslant i \leqslant T$, нет одинаковых.

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

Выходной файл должен содержать $T$ чисел по одному в строке — в $i$-й строке должно быть записано наименьшее количество секунд, которое понадобится истратить Пете, чтобы, начав с единицы, записать на доске соответствующее число $N_i$.

Тесты

№

Ввод

Вывод

955

4

137

318

3028

300

39

40

71

50

Код

#include <iostream>

using namespace std;

int nonzero(int number) //функция,которая считает количество цифр,не равных нулю,кроме последней
{
  int count = 0;
  number /= 10;
  while (number != 0) {
    if (number % 10 != 0) count++;
    number /= 10;
  }
  return count;
}
int summa(int number) //функция,которая возвращает сумму цифр числа
{
  int sum = 0;
  while (number != 0) {
    sum += number % 10;
    number /= 10;
  }
  return sum;
}
bool edinica(int number) //функция,которая проверяет есть ли среди цифр числа,кроме последней, единица
{
  number /= 10;
  bool ok = false;
  while (number != 0) {
    if (number % 10 == 1) ok = true;
    number /= 10;
  }
  return ok;
}
int kol_vo(int number) //функция,вычисляющая кол-во цифр числа
{
  int count = 0;
  while (number != 0) {
    count++;
    number /= 10;
  }
  return count;
}
int formula(int number) //формула,по которой можно дойти от 1 до 10^(a-1),где a- кол-во цифр числа
{
  int a = kol_vo(number);
  return (5 * a - 1) * (a - 1);
}

int main() {
  //инииализируем переменную t и считываем ее с клавиатуры
  int t;
  cin >> t;
  //инициализируем переменную ni и задаем цикл,который будет работать пока мы вводим значения ni и t>0
  int ni;
  while (cin >> ni and t > 0) {
    //кладем в переменную kol_vo1 значение функции kol_vo от значения ni
    int kol_vo1 = kol_vo(ni);
    //появляется необходимость создать переменную,которая будет равна значению ni,так как с этим значением
    //в дальнейшем будут проводится операции,а в конце программы нам нужно будет обратиться к исходному значению ni 
    int a = ni;
    //задаем массив,размерность которого равна кол-ву цифр числа
    int b[kol_vo1];
    for (int i = 0; i < kol_vo1; i++) {
      b[i] = a % 10;
      a /= 10;
    }
    //далее производим проверку условия №2,которое описано в решении. Если число проходит условие,то 
    //выводим соответствующую формулу,указанную в условии №2
    bool ok = false;
    for (int i = 0; i < kol_vo1 - 1; i++) {
      if (b[i] == 0) ok = true;
      else {
        ok = false;
        break;
      }
    }
    if (b[kol_vo1 - 1] > 1 and ok == true) {
      cout << summa(--ni) + nonzero(--ni) - edinica(--ni) + formula(ni) << endl;
    }
    //далее производим проверку условия №1,которое описано в решении. Если число проходит условие,то 
    //выводим соответствующую формулу,указанную в условии №1
    bool ok2 = false;
    for (int i = 0; i < kol_vo1 - 1; i++) {
      if (b[i] != 0) ok2 = true;
    }
    if (ok2 == true) cout << summa(ni) + nonzero(ni) - edinica(ni) - 1 + formula(ni) << endl;
    //остались крайние случаи,когда число однозначное или кратное 10^n.Проверяем число на эти условия
    //и если оно является таковым,выводим соответствующие значения
    if (kol_vo1 == 1) cout << ni - 1 << endl;
    if (ni == 10 or ni == 100 or ni == 1000 or ni == 10000 or ni == 100000 or ni == 1000000 or ni == 10000000 or ni == 100000000 or ni == 1000000000) cout << formula(ni) << endl;
    //декрементируем переменную t
    t--;
  }
}

#include <iostream>

using namespace std;

int nonzero(int number) //функция,которая считает количество цифр,не равных нулю,кроме последней

{

int count = 0;

number /= 10;

while (number != 0) {

if (number % 10 != 0) count++;

number /= 10;

}

return count;

}

int summa(int number) //функция,которая возвращает сумму цифр числа

{

int sum = 0;

while (number != 0) {

sum += number % 10;

number /= 10;

}

return sum;

}

bool edinica(int number) //функция,которая проверяет есть ли среди цифр числа,кроме последней, единица

{

number /= 10;

bool ok = false;

while (number != 0) {

if (number % 10 == 1) ok = true;

number /= 10;

}

return ok;

}

int kol_vo(int number) //функция,вычисляющая кол-во цифр числа

{

int count = 0;

while (number != 0) {

count++;

number /= 10;

}

return count;

}

int formula(int number) //формула,по которой можно дойти от 1 до 10^(a-1),где a- кол-во цифр числа

{

int a = kol_vo(number);

return (5 * a - 1) * (a - 1);

}

int main() {

//инииализируем переменную t и считываем ее с клавиатуры

int t;

cin >> t;

//инициализируем переменную ni и задаем цикл,который будет работать пока мы вводим значения ni и t>0

int ni;

while (cin >> ni and t > 0) {

//кладем в переменную kol_vo1 значение функции kol_vo от значения ni

int kol_vo1 = kol_vo(ni);

//появляется необходимость создать переменную,которая будет равна значению ni,так как с этим значением

//в дальнейшем будут проводится операции,а в конце программы нам нужно будет обратиться к исходному значению ni

int a = ni;

//задаем массив,размерность которого равна кол-ву цифр числа

int b[kol_vo1];

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

b[i] = a % 10;

a /= 10;

}

//далее производим проверку условия №2,которое описано в решении. Если число проходит условие,то

//выводим соответствующую формулу,указанную в условии №2

bool ok = false;

for (int i = 0; i < kol_vo1 - 1; i++) {

if (b[i] == 0) ok = true;

else {

ok = false;

break;

}

if (b[kol_vo1 - 1] > 1 and ok == true) {

cout << summa(--ni) + nonzero(--ni) - edinica(--ni) + formula(ni) << endl;

}

//далее производим проверку условия №1,которое описано в решении. Если число проходит условие,то

//выводим соответствующую формулу,указанную в условии №1

bool ok2 = false;

for (int i = 0; i < kol_vo1 - 1; i++) {

if (b[i] != 0) ok2 = true;

}

if (ok2 == true) cout << summa(ni) + nonzero(ni) - edinica(ni) - 1 + formula(ni) << endl;

//остались крайние случаи,когда число однозначное или кратное 10^n.Проверяем число на эти условия

//и если оно является таковым,выводим соответствующие значения

if (kol_vo1 == 1) cout << ni - 1 << endl;

if (ni == 10 or ni == 100 or ni == 1000 or ni == 10000 or ni == 100000 or ni == 1000000 or ni == 10000000 or ni == 100000000 or ni == 1000000000) cout << formula(ni) << endl;

//декрементируем переменную t

t--;

}

Решение

Количество цифр в числе никогда не уменьшается, а может увеличиться только при добавлении к числу, состоящее только из девяток и единицы. Поэтому, для достижения числа $N$ сначала нужно дойти до числа $10$, потом до чисел $99$ и $100$ и т.д., пока кол-во цифр в числе не будет таким, как требуется.
Наименьшее кол-во операций,необходимое для того,чтобы перейти от числа $10^{n-1}$ до заданного $n$-значного числа $N=$:
1.Если число $N$ содержит хотя бы одну цифру, отличную от нуля, кроме первой, то кол-во операций можно посчитать по формуле summa(N) + nonzero(N) – edinica(N)-1, где summa(N)-сумма цифр числа, nonzero(N)-кол-во цифр,отличных от нуля, на всех позициях числа $N$, кроме последней, edinica(N)-число,которое равно единице,если хотя бы на одной позиции числа $N$, кроме последней,есть единица, или равна нулю, если единиц на этих позициях нет.
2.Если все цифры числа $N$, кроме первой,нулевые,а первая цифра больше единицы, то кол-во операций можно посчитать по формуле summa(N-1)+nonzero(N-1) –edinica(N-1).

Доказательство формул

Для дальнейшего удобства обозначим перестановку цифр числа через $\Rightarrow$.
Число $N$-заданное число, число $n$-кол-во цифр числа $N$. Если $n=1$,$N=7$,то для того,чтобы дойти от единицы до заданного числа,потребуется $N-1$ операций. В нашем случае 6 операций
($1+1=2,
2+1=3,
…
6+1=7$)
Если $n\geq2$,то для этого достаточно привести пример цепочки,подсчитывающая кол-во операций,которая число $10^{n-1}$ превращает в $N$. Но вместо прямого порядка действий будем делать обратный эквивалентный. То есть, $N \Rightarrow 10^{n-1}$: за одну операцию мы можем или уменьшить число на единицу, или переставить в нем цифры так,чтобы на первом месте оказался не нуль. Могут возникнуть следующие случаи:
1.Если $N=10^{n-1}$, то кол-во операций равно summa(N) + nonzero(N)-edinica(N)-1 $= $0.
Например, возьмем число $1000$. Сумма цифр $= 1$, количество ненулевых цифр $= 1$, количество единиц $= 1$, соответственно значение $= 1+1-1-1 =0$.

2.Если $N!=10^{n-1}$ и число первая цифра числа $N$ равна единица:
Сначала отнимаем от числа $N$ столько единиц, чтобы последняя цифра стала нулем,далее
Переставим местами последнюю цифру с какой-нибудь другой,отличной от нуля,кроме первой, и опять отнимем кол-во единиц,чтобы последняя цифра стала нулевой. Повторять будем до тех пор,пока все цифры,кроме первой,станут нулями.
Например,возьмем число $137$.
$137-1=136$, $136-1=135$, $135-1=134$, $134-1=133$ ,$133-1=132$ ,$132-1=131$, $131-1=130$ ,$130 \Rightarrow 103$ , $103-1=102$, $102-1=101$, $101-1=100$
Кол-во операций $= 11$. Проверяем по формуле. summa(137)=11, nonzero(137)=2, edinica(137)=1. Итого получаем $11+2-1-1=11$

3.Если первая цифра числа $N$ больше единицы, но хотя бы на одной позиции числа,кроме последней, есть единица, делаем:
Сначала уменьшаем последнюю цифру,пока она не станет нулем, затем переставляем цифры: поставим на место первой цифры единицу, а первую цифру сделаем последней, а нуль, который стоял в конце числа, поставим на место бывшей первой. После этого будем действовать согласно алгоритму пункта №2.
Например, число $318$.
$318-1=317$, $317-1=316$, $316-1=315$, $315-1=314$, $314-1=313$, $313-1=312$, $312-1=311$, $311-1=310$, $310 \Rightarrow 103$, $103-1=102$, $102-1=101$, $101-1=100$
Итого $12$ операций. Просчитываем по формуле summa(318)+nonzero(318)-edinica(318)-1.
Получаем $12+2-1-1=12$.

4.Если ни на одной из позиций числа $N$, кроме,возможно,последней, нет единиц, но в числе есть хотя бы одна ненулевая цифра,кроме первой, то делаем:
Последнюю цифру делаем нулевой, переставляем последний нуль с любой ненулевой цифрой,кроме первой, пока на последнем месте не окажется последняя ненулевая цифра (не считая первую), последнюю ненулевую уменьшаем не до нуля, а до единицы, переставим единицу с первой цифрой, новую последнюю цифру сделаем нулевой.
Например, число $3028$.
$3028-1=3027$, $3027-1=3026$, $3026-1=3025$, $3025-1=3024$, $3024-1=3023$, $3023-1=3022$, $3022-1=3021$, $3021-1=3020$, $3020 \Rightarrow 3002$, $3002-1=3001$, $3001 \Rightarrow 1003$, $1003-1=1002$, $1002-1=1001$, $1001-1=1000$
Получаем $14$ операций. Проверяем по формуле summa(3028)+nonzero(3028)-edinica(3028)-1 $= 13+2-0-1=14$.

5.Если первая цифра числа $N$ больше единицы, а все другие цифры-нулевые, то делаем:
Отнимем от числа $N$ единицу, а дальше будем использовать один из раннее алгоритмов в пунктах 2-4.
Например, число $300$.
$300-1=299$, $299-1=298$, $298-1=297$, $297-1=296$, $296-1=295$ $=$ … $291-1=290$, $290 \Rightarrow 209$, $209-1=208$ $=$ … $202-1=201$, $201 \Rightarrow 102$, $102-1=101$, $101-1=100$
Итого $22$ операции. summa(300-1)+nonzero(300-1)-edinica(300-1) $= 20+2-0=22$.

6.Подсчет операций от $1$ до $10^{n-1}$.
Для того,чтобы перейти от числа $10^{n-1}$ к $10^n$, понадобится число $10^n – 1$,которое равно $k$. По предыдущим алгоритмам, понадобится:
summa(k)+ nonzero(k) – edinica(k) -1 $=$ $9 \cdot n + (n-1) -0 -1=10 \cdot n – 2$ операций, где b $>$ 1.
Если $n=1$, то кол-во операций $= 10 \cdot n – 2 =8$.

Кол-во операций можно посчитать по формуле $(5 \cdot n -1) \cdot (n – 1)$ ,где $n$- кол-во цифр заданного числа.

Ссылки

Філіпенко Микита

e-olymp 3738. Простая сортировка

16/03/2021 by Verheles Vladyslav

Задача

Дан массив целых чисел.

Ваша задача — отсортировать его в порядке неубывания.

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

В первой строке входного файла содержится число N (1 ≤ N≤ 100000) — количество элементов в массиве. Во второй строке находятся N целых чисел, по модулю не превосходящих 109.

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

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

Тесты

№	Входные данные	Выходные данные
1	10 1 8 2 1 4 7 3 2 3 6	1 1 2 2 3 3 4 6 7 8
2	9 7 39 8 1 4 2 65 10 5	1 2 4 5 7 8 10 39 65
3	12 -3 7 -7 -11 40 -30 25 30 2 7 -30 1	-30 -30 -11 -7 -3 1 2 7 7 25 30 40

Код

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

int main() {
    int a;
    cin >> a;
    int* arr = new int[a];
    for (int i = 0; i < a; i++)
    {
        cin >> arr[i];
    }
    sort(arr, arr + a);
    for (int i = 0; i < a; i++)
    {
        cout << arr[i] << ' ';
    }
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int a;

cin >> a;

int* arr = new int[a];

for (int i = 0; i < a; i++)

{

cin >> arr[i];

}

sort(arr, arr + a);

for (int i = 0; i < a; i++)

{

cout << arr[i] << ' ';

}

Решение

Для решения задачи используем функцию сортировки из библиотеки algorithm. Для начала создаем одномерный массив, потом с помощью цикла записываем значение в массив. С помощью функции sort, сортируем и записываем изменения в массив. Потом с помощью цикла выводим результат.

Ссылки

Задача на e-olymp
Код решения на ideone
Засчитанное решение на e-olymp

Verheles Vladyslav

e-olymp 7241. Transit

06/03/2021 by Дарієнко Дмитро

Задача

Країна Ужляндія має вигідне географічне розташування – її територія знаходиться на перетині важливих торгівельних шляхів. Одним із таких є торгівельний шлях, яким сусідня братська держава доставляє свої унікальні обігрівачі до інших країн.

На кордоні Ужляндії та братської держави, де починається цей шлях, розташований спеціальний пропускний пункт, через який щодня проїжджає потяг із величезною кількістю обігрівачів. Зовсім недавно між урядами двох братських країн було погоджено нові правила транзиту обігрівачів через територію Ужляндії на найближчі $N$ днів. Згідно з новим договором має обратися певне число $m$ – максимальна кількість обігрівачів в одному потязі. Тоді з кожного потяга, що транспортує $A_i$ обігрівачів, буде відвантажено рівно $ A_i -m $ одиниць іноземної продукції (звичайно, якщо $A_i > m$ , інакше ж потяг рухатиметься без зупинок і нічого відвантажено не буде). Власне це й буде плата за проходження потяга територією Ужляндії, вона еквівалентна грошовим витратам на утримання залізничних колій. Сумарна кількість відвантажених в Ужляндії за $N$ днів обігрівачів повинна бути не менша $K$, інакше країна зазнає збитків.

Стала відома кількість обігрівачів у потязі в кожен із $N$ днів (ця інформація надається за умовами контракту). Знайдіть максимальне число $m$, при якому Ужляндія не зазнає економічних збитків.

Формат вхідних даних

В першому рядку записано два числа $N$, $K$ ($1 \leqslant N \leqslant 10^6$, $1 \leqslant K \leqslant 2 \cdot 10^9$). В наступному рядку задано $N$ чисел – кількість обігрівачів у потязі в кожен з $N$ днів, що не перевищує $10^9$.

Формат вихідних даних

В єдиному рядку виведіть одне число – відповідь на задачу, гарантується, що відповідь завжди існує.

Пояснення до прикладу

Всього територією Ужляндії пройде $4$ потяги з $11, 6, 1$ та $8$ обігрівачами відповідно. Щоби країна не знала збитків, потрібно відвантажити не менше $7$ обігрівачів. Очевидно, що максимальне можливе $m$, яке задовольнить цю умову, буде рівне $6$, тоді з потягів буде відвантажено відповідно $5, 0, 0, 2$ обігрівачів, що в сумі дорівнює $7$ і задовольняє умову.

Тести

№	Вхідні дані	Вихідні дані
1	4 7 1 8 6 11	6
2	10 20 1 8 6 11 16 14 21 10 13 4	11
3	5 10 12 4 3 6 9	5
4	6 11 5 8 6 9 4 7	4
5	2 1 2 2	1

Код

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

long N, K;
long* A;

long sum_depending_on_mid(int m) {
    long summ = 0;
    for (int i = 0; i <= N - 1 ; i++) {
        if(A[i] > m) summ += A[i] - m;
    }
    return summ;
}

int main() {
    cin >> N >> K;
    A = new long[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A, A + N);
    long low = 0;
    long high = A[N - 1];
    long mid = 0;
    while (low != high and sum_depending_on_mid(mid = (low + high) / 2) != K) {
        long past_low = low;
        long past_high = high;
        if (sum_depending_on_mid(mid) < K) {
            high = mid;
        } else low = mid;
        if (past_low == low and past_high == high) {
            cout << mid;
            return 0;
        }
    }
    cout << mid;
    delete[] A;
}

#include <iostream>

#include <algorithm>

using namespace std;

long N, K;

long* A;

long sum_depending_on_mid(int m) {

long summ = 0;

for (int i = 0; i <= N - 1 ; i++) {

if(A[i] > m) summ += A[i] - m;

}

return summ;

}

int main() {

cin >> N >> K;

A = new long[N];

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

cin >> A[i];

}

sort(A, A + N);

long low = 0;

long high = A[N - 1];

long mid = 0;

while (low != high and sum_depending_on_mid(mid = (low + high) / 2) != K) {

long past_low = low;

long past_high = high;

if (sum_depending_on_mid(mid) < K) {

high = mid;

} else low = mid;

if (past_low == low and past_high == high) {

cout << mid;

return 0;

}

cout << mid;

delete[] A;

}

Рішення

Для знаходження числа $m$ я використовував бінарний пошук, перед цим зробивши сортування по зростанню елементів в масиві. Отже, вся задача зводиться до використання бінарного пошуку, та функції яка рахує $\sum\limits_{i=0}^{n-1} A_i — m$, при $A_i > m$ ($m$ — значення mid; $n$ — кількість елементів в масиві; $A_i$ — значення $i$-го елемента масиву). Далі ця сума порівнюється з $K$ для подальшої роботи пошуку та знаходження числа $m$. Якщо такого числа $m$ не існує ми шукаємо найближче, при якому країна не зазнає збитків.

Посилання

Задача на e-olymp.
Код рішення на ideone.
Зараховане на e-olymp.

Дарієнко Дмитро

e-olymp 2691. Проходной балл

27/12/2020 by Жук Світлана

Задача

Дан список учащихся с указанием годовых оценок по всем предметам. Для поступления в Школу Одаренных Детей необходимо, чтобы средний балл по всем предметам был не ниже, чем $K$. Определите, кого из перечисленных ребят могут зачислить в эту школу.

Формат входных данных

В первой строке дано число $N$ ($1 \leqslant N \leqslant 10000$), количество учащихся в списке. Каждая из следующих $N$ строк имеет вид: фамилия и имя, затем число $M_i$ ($1 \leqslant M_i \leqslant 50$) — количество предметов, которые изучал ученик, а затем годовые оценки по каждому из этих предметов.
В последней строке дано единственное число $K$ — проходной балл. Фамилия и имя — строки, состоящие не более чем из $20$ латинских букв. Все числа во входном файле натуральные и не превышают $10^9$.

Формат выходных данных

Требуется вывести список ребят, которые могут быть зачислены.

Тесты

№	Входные данные	Выходные данные
1	3 Ivanov Ivan 2 7 9 Petrov Petr 1 7 Sidorov Sidor 2 10 8 4	Ivanov Ivan Petrov Petr Sidorov Sidor
2	1 Ivanov Ivan 1 6 5	Ivanov Ivan
3	4 Petrov Petr 10 1 2 3 4 5 6 7 8 9 10 Sidorov Sidor 5 8 8 8 4 4 Ivanov Ivan 0 Darienko Dasha 3 10 3 9 6	Sidorov Sidor Darienko Dasha
4	2 Petrov Petr 10 1 2 3 4 5 6 7 8 9 10 Darienko Dasha 3 10 3 9 11
5	5 Petrov Petr 10 100000000 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 1000000000 Darienko Dasha 5 500000000 500000000 500000000 700000000 800000000 Sidorov Sidor 20 100000000 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 1000000000 500000000 500000000 500000000 700000000 800000000 500000000 500000000 500000000 700000000 800000000 Ivanov Ivan 8 600000000 600000000 600000000 800000000 200000000 1000000000 300000000 300000000 Sergeev Alexandr 1 700000000 600000000	Darienko Dasha Sergeev Alexandr

Код

Оптимальное решение:

#include <iostream>
#include <string>
#define surname 0
#define name 1
#define column 2

using namespace std;

int main() {
    //количество учеников
    int n;
    cin >> n;
    //в первый столбец запишем фамилии, во второй - имена
    string names[column][n];
    //тут будут средние баллы соответствующих учеников 
    int average [n];
    
    //количество предметов и текущий балл данного ученика
    int subjects, mark;
    //сумма оценок данного ученика
    long sum;
    
    for (auto i = 0; i < n; i++){
        sum = 0;
        //последовательный ввод фамилии, имени и количества предметов
        cin >> names[surname][i] >> names[name][i] >> subjects;
        //ввод оценок в нужном количестве и подсчет суммы
        for (auto j = 0; j < subjects; j++){
            cin >> mark;
            sum += mark;
            
        }
        //вычисление среднего для данного ученика
        average[i] = sum / subjects;
    }
    //средний проходной балл
    int k;
    cin >> k;
    
    //если среднее не меньше проходного балла, 
    //выводим фамилию и имя данного ученика
    for (auto i = 0; i < n; i++){
        if (average[i] >= k) cout << names [surname][i] << 
        " " << names[name][i] << endl;
    }
    return 0;
}

#include <iostream>

#include <string>

#define surname 0

#define name 1

#define column 2

using namespace std;

int main() {

//количество учеников

int n;

cin >> n;

//в первый столбец запишем фамилии, во второй - имена

string names[column][n];

//тут будут средние баллы соответствующих учеников

int average [n];

//количество предметов и текущий балл данного ученика

int subjects, mark;

//сумма оценок данного ученика

long sum;

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

sum = 0;

//последовательный ввод фамилии, имени и количества предметов

cin >> names[surname][i] >> names[name][i] >> subjects;

//ввод оценок в нужном количестве и подсчет суммы

for (auto j = 0; j < subjects; j++){

cin >> mark;

sum += mark;

}

//вычисление среднего для данного ученика

average[i] = sum / subjects;

}

//средний проходной балл

int k;

cin >> k;

//если среднее не меньше проходного балла,

//выводим фамилию и имя данного ученика

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

if (average[i] >= k) cout << names [surname][i] <<

" " << names[name][i] << endl;

}

return 0;

}

Более структурированное решение:

#include <iostream>
#include <string>
 
using namespace std;
 
struct student {
    string name, surname;
    int average;
    void inputFullName() {
        cin >>surname >>name;
    }
    void printFullName() {
        cout <<surname <<" " <<name <<endl;
    }
    void inputMarks() {
        int subjects, mark;
        long sum = 0;
        cin>> subjects;
        //ввод оценок в нужном количестве и подсчет суммы
        for (auto j = 0; j < subjects; j++){
            cin >>mark;
            sum +=mark;
 
        }
        //вычисление среднего для данного ученика
        average = sum / subjects;
    }
    bool passCheck(int k) {
        return average >= k;
    }
};
 
int main() {
    //количество учеников и средний проходной балл
    int n;
    cin >> n;
    //массив учеников
    student list[n];
 
    for (auto i = 0; i < n; i++){
        list[i].inputFullName();
        list[i].inputMarks();
    }
    //ввод среднего проходного балла
    int k;
    cin >> k;
 
    //если среднее не меньше проходного балла, 
    //выводим фамилию и имя данного ученика
    for (auto i = 0; i < n; i++){
        if (list[i].passCheck(k)) 
            list[i].printFullName();
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

struct student {

string name, surname;

int average;

void inputFullName() {

cin >>surname >>name;

}

void printFullName() {

cout <<surname <<" " <<name <<endl;

}

void inputMarks() {

int subjects, mark;

long sum = 0;

cin>> subjects;

//ввод оценок в нужном количестве и подсчет суммы

for (auto j = 0; j < subjects; j++){

cin >>mark;

sum +=mark;

}

//вычисление среднего для данного ученика

average = sum / subjects;

}

bool passCheck(int k) {

return average >= k;

}

};

int main() {

//количество учеников и средний проходной балл

int n;

cin >> n;

//массив учеников

student list[n];

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

list[i].inputFullName();

list[i].inputMarks();

}

//ввод среднего проходного балла

int k;

cin >> k;

//если среднее не меньше проходного балла,

//выводим фамилию и имя данного ученика

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

if (list[i].passCheck(k))

list[i].printFullName();

}

return 0;

}

Решение

Введем данные в соответствующие структуры (см. комментарии в коде), вычислим средние баллы для каждого ученика и выведем фамилии и имена всех тех и только тех, чей средний балл выше проходного.
Т. к. все исходные данные натуральные и не превышают $10^9$ используем для их ввода тип int. При этом сумма оценок может выйти за пределы типа int ($50\cdot10^9 > 2 147 483 647$), поэтому для переменной sum используем тип long. Также заметим, что среднее арифметическое натуральных чисел может быть дробным числом, но в данном случаи средний проходной балл $K$ по условию являет натуральным числом, поэтому будет уместно отбросить дробную часть при сравнении, т. е. использовать целочисленных тип данных в вычислениях.

Ссылки

Задача на e-olymp

Код оптимального решения на ideone

Код решения со структурами на решения со структурами на ideone

Засчитанное оптимальное решение на e-olymp

Засчитанное структурированное решение на e-olymp

Жук Світлана

e-olymp 6253. Репликация вируса

23/12/2020 by Євчук Даяна

Задача

Некоторые вирусы реплицируются путем замены фрагмента ДНК в живой клетке фрагментом ДНК, который вирус несет с собой. Это заставляет клетку создавать вирусы, идентичные оригинальной, зараженной клеткой. Группа биологов заинтересована в том, чтобы узнать, сколько ДНК вносит вирус в геном хозяина. Чтобы узнать об этом, они упорядочили полный геном здоровой клетки, а также идентичную клетку, инфицированную вирусом.

Геном оказался довольно большим, поэтому теперь им нужна Ваша помощь на этапе обработки данных. Имея последовательность ДНК до и после вирусной инфекции, определите длину самой маленькой одной последовательной части ДНК, которая может быть вставлена в первую последовательность, чтобы превратить ее во вторую. Один последовательный фрагмент ДНК также может быть удален из того же положения в последовательности, куда был вставлен ДНК. Небольшие изменения в ДНК могут иметь большие эффекты, поэтому вирус может вставить только несколько букв или даже ничего.

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

Состоит из двух строк, содержащих последовательность ДНК до и после вирусной инфекции, соответственно. Последовательность ДНК задается как строка, содержащая от 1 до $10^5$ букв верхнего регистра из алфавита {A, G, C, T}.

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

Выведите одно целое число — минимальную длину ДНК, вставленную вирусом.

Тесты

№	Входные данные	Выходные данные
1	AAAAA AGCGAA	3
2	GTTTGACACACATT GTTTGACCACAT	4
3	SMMSMM SMAHMA	4

Код

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

int main() {
    //Инициализируем массивы, удовлетворяющие условия
    char b[100001], a[100001];
    cin >> b >> a;
    // b-строка до (before), a-строка после (after)
    int s = 0, l1 = strlen(b), l2 = strlen(a), e1 = l1, e2 = l2;
    //определяем длины первой и второй строк, без учёта нуль-символа. 
    
    // Проверяем есть ли символ в массиве b[s], 
    // Если есть и он такой же, как и в массиве a[s] - счётчик увеличивается
    // в результате мы узнаём на каком, крайнем слева, символе начинаются расхождения (s)
    for (; b[s] && b[s] == a[s]; ++s);
    
    // Цикл проходиться по массиву a и b с конца введённых в них строк
    // Цикл двигается по массиву до первого расхождения в буквах (b[e1]!=a[e2])
    // в результате мы узнаём на каком, крайнем справа, символе начинаются расхождения (e2)
    for (; e1>=0 && e2>=0 && b[e1]==a[e2]; --e1, --e2);
    
    // Считаем максимальное количество букв, которые подверглись расхождению, ища максимальное от
    // максимального между 0 и разницей в кол-ве символов второй строки от первой и
    // разницей между крайним правым и крайним левым номером элемента на котором начались расхождения + 1
    cout << max(max(0,l2-l1),e2-s+1) << endl;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

//Инициализируем массивы, удовлетворяющие условия

char b[100001], a[100001];

cin >> b >> a;

// b-строка до (before), a-строка после (after)

int s = 0, l1 = strlen(b), l2 = strlen(a), e1 = l1, e2 = l2;

//определяем длины первой и второй строк, без учёта нуль-символа.

// Проверяем есть ли символ в массиве b[s],

// Если есть и он такой же, как и в массиве a[s] - счётчик увеличивается

// в результате мы узнаём на каком, крайнем слева, символе начинаются расхождения (s)

for (; b[s] && b[s] == a[s]; ++s);

// Цикл проходиться по массиву a и b с конца введённых в них строк

// Цикл двигается по массиву до первого расхождения в буквах (b[e1]!=a[e2])

// в результате мы узнаём на каком, крайнем справа, символе начинаются расхождения (e2)

for (; e1>=0 && e2>=0 && b[e1]==a[e2]; --e1, --e2);

// Считаем максимальное количество букв, которые подверглись расхождению, ища максимальное от

// максимального между 0 и разницей в кол-ве символов второй строки от первой и

// разницей между крайним правым и крайним левым номером элемента на котором начались расхождения + 1

cout << max(max(0,l2-l1),e2-s+1) << endl;

}

Решение

Нам нужно определить длину самой маленькой одной последовательной части ДНК, которая может быть вставлена в первую последовательность, чтобы превратить ее во вторую.

В циклах for мы узнаём крайний слева и справа элемент обоих массивов, на которых буквы первой строки начинают не совпадать с буквами второй, s и e2 соответственно. Чтобы узнать результат необходимо проверить является ли l2 > l1 и больше ли l2-l1 чем e2-s1+1.

Задача на e-olymp
Код программы на ideone
Засчитанное решение

Євчук Даяна

ПМ 1 курс 2 группа.

e-olymp 6941. Сумма НОД

22/12/2020 by Натан Чачко

Задача

Для заданных $n$ натуральных чисел найдите сумму НОД (наибольших общих делителей) всех возможных пар этих чисел.

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

В первой строке задано количество тестов $n \ (1 < n < 100)$. Каждый тест состоит из одной строки и содержит количество входных чисел $m \ (1 < m < 100)$, за которым следуют $m$ натуральных чисел. Все входные числа натуральные, не превышающие $10^6.$

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

Для каждого теста в отдельной строке вывести сумму $НОД$ всех возможных пар.

Тесты

№	Входные данные	Выходные данные
1	3 4 10 20 30 40 3 7 5 12 3 125 15 25	70 3 35
2	2 3 12 7 8 4 5 14 25 11	6 10
3	4 4 5 6 7 8 4 8 6 2 9 3 2 15 6 5 12 25 29 19 11	7 11 6 10

Код

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

int main() {
    int n, m, sum;
    cin >> n;
    while(n-- > 0) {
        cin >> m; 
        int ns[m];
        for(int i = 0; i < m; i++) cin >> ns[i];
        sum = 0;
        for(int i = 0; i < m; i++) {
            for(int j = i + 1; j < m; j++) sum += gcd(ns[i], ns[j]);
        }
        cout << sum << endl;
    }
}

#include <iostream>

using namespace std;

int gcd(int a, int b) {

return b == 0 ? a : gcd(b, a%b);

}

int main() {

int n, m, sum;

cin >> n;

while(n-- > 0) {

cin >> m;

int ns[m];

for(int i = 0; i < m; i++) cin >> ns[i];

sum = 0;

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

for(int j = i + 1; j < m; j++) sum += gcd(ns[i], ns[j]);

}

cout << sum << endl;

}

Решение

Алгоритм решения этой задачи очень простой: чтобы найти сумму НОД всех пар чисел в строке нужно сначала найти все сочетания по два числа из строки, потом посчитать НОД для каждой пары и сложить все НОД.

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Натан Чачко

Примат первого курса

E-Olymp 7029. Поликлиника

21/12/2020 by Євчук Даяна

Задача

На прием к доктору каждый день приходит много людей. Каждый пациент находится на приеме целое число минут, однако разных пациентов доктор может принимать разное количество времени. Доктор начинает прием в момент времени $t_1$ минут и заканчивает прием в момент времени $t_2$ минут. Это означает, что любой пациент независимо от того, сколько времени его будет принимать доктор, может зайти на прием в моменты $t_1, t_1 + 1, …, t_2 − 1$. Заходить на прием к доктору в другое время или тогда, когда доктор принимает другого пациента, запрещено. Если пациент приходит в поликлинику в момент $t$, он ожидает первый момент времени $s ≥ t$ такой, что на этот момент доктор ведет прием, причем уже успел осмотреть всех пациентов, которые пришли в поликлинику раньше, то есть до момента $t$. Если доктор не успевает осмотреть всех до конца приема, то остаток пациентов должен прийти на следующий день.

Зная, в какой момент доктор начинает и заканчивает прием, те, кто и когда придут на прием в конкретный день, а также сколько времени будет осматривать доктор каждого пациента, определите момент времени, в который необходимо прийти на прием Пете Пяточкину, чтобы гарантированно попасть в этот день к доктору, и при этом ожидать приема как можно меньше. В случае, если имеется несколько альтернативных вариантов такого момента времени, Вам необходимо определить наименьший (наиболее ранний) из них.

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

В первой строке приведено три числа: количество желающих попасть на прием n, время начала приема $t_1$ и время завершения приема $t_2$, больший чем $t_1$.

Во второй строке перечислены $n$ чисел $a_1, a_2, …, a_n$ — время, когда в поликлинику зашли соответственно первый, второй, $…, n$-ый желающий попасть к доктору. Числа $a_1, a_2, …, a_n$ попарно различны и расположены в порядке возрастания.

В третьей строке перечислены n чисел $b_1, b_2, …, b_n$ — время, необходимое доктору на осмотр соответственно первого, второго, $…, n$-го пациента.

Все входные числа натуральные. Количество пациентов $n$ не больше $10^5$, остальные числа не превосходят $10^9$.

Сутки на планете, где проживает Петя Пяточкин, длятся значительно дольше, чем на Земле, поэтому время начала приема $t_1$, время завершения приема $t_2$, а также числа $a_1, a_2, …, a_n$ и $b_1, b_2, …, b_n$ могут быть большими чем 1440 — количество минут в земных сутках.

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

Вывести наименьший момент времени, когда Петя Пяточкин должен прийти в поликлинику, чтобы гарантированно попасть к доктору, подождав приема как можно меньше времени. Если Петя придет одновременно с другим человеком, его как младшего пропустят вперед.

Тесты

№	Входные данные	Выходные данные
1	3 10 20 7 14 18 5 2 1	17
2	5 10 20 4 9 12 16 22 4 10 10 9 2	9
3	1 10 20 5 15	5

Код

#include <iostream>

using namespace std;

int a[100003], b[100003];

int main() {
    long long t1, t2, t, n, i, j, l;
    cin >> n >> t1 >> t2;
    t = 0;
    //Заполняем время прихода пациентов на приём в массив a
    for (i = 1; i <= n; i++) {
        cin >> a[i];
    }
    //Заполняем время на приём пациентов в массив b
    for (i = 1; i <= n; i++) {
        cin >> b[i];
    }
    //Проверяет приходит ли пациент в начале времени приёма или после его начала 
    if (a[1] >= t1) {
        cout << t1 << endl;
        return 0;
    }
    //Вводим точки отсчёта
    else {
        t = a[1];
        l = t1 - a[1];
        t1 += b[1];
    }
    j = 2;
    //Условие: Если разница между началом приёма и приёмом > 0; цикл не прошёл всех пациентов; приём ещё не окончен.
    while (l > 0 && j <= n && t1 < t2) {
        //Проверяет приходит ли следующий пациент к началу или уже после начала приёма врача
        if (a[j] >= t1) {
            t = t1;
            l = 0;
        } else {
            //Проверяет является ли разница между началом приёма следующего пациента и временем его прихода меньше, чем предыдущая зафиксированная разница
            if (t1 - a[j] < l) {
                t = a[j];
                l = t1 - a[j];
            }
            t1 += b[j];
        }
        j++;
    }
    //Если время приёма ещё не окончено, пациенты все прошли и прийти раньше не получилось - приходим сразу в конце приёма последнего
    if (t1 < t2 && l != 0 && j > n) {
        t = t1;
        l = 0;
    }
    cout << t << endl;
}

#include <iostream>

using namespace std;

int a[100003], b[100003];

int main() {

long long t1, t2, t, n, i, j, l;

cin >> n >> t1 >> t2;

t = 0;

//Заполняем время прихода пациентов на приём в массив a

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

cin >> a[i];

}

//Заполняем время на приём пациентов в массив b

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

cin >> b[i];

}

//Проверяет приходит ли пациент в начале времени приёма или после его начала

if (a[1] >= t1) {

cout << t1 << endl;

return 0;

}

//Вводим точки отсчёта

else {

t = a[1];

l = t1 - a[1];

t1 += b[1];

}

j = 2;

//Условие: Если разница между началом приёма и приёмом > 0; цикл не прошёл всех пациентов; приём ещё не окончен.

while (l > 0 && j <= n && t1 < t2) {

//Проверяет приходит ли следующий пациент к началу или уже после начала приёма врача

if (a[j] >= t1) {

t = t1;

l = 0;

} else {

//Проверяет является ли разница между началом приёма следующего пациента и временем его прихода меньше, чем предыдущая зафиксированная разница

if (t1 - a[j] < l) {

t = a[j];

l = t1 - a[j];

}

t1 += b[j];

}

j++;

}

//Если время приёма ещё не окончено, пациенты все прошли и прийти раньше не получилось - приходим сразу в конце приёма последнего

if (t1 < t2 && l != 0 && j > n) {

t = t1;

l = 0;

}

cout << t << endl;

}

Решение

Создаём два массива, удовлетворяющих условия, a — время прихода пациентов и b — время на их приём. Инициализируем все необходимые переменные: t_1 и t_2 — время приёма, t — время в которое Петя должен прийти, n- кол-во пациентов, i и j — счётчики, l — время между приходом пациента и началом его приёма.

Проверяем приходит ли первый пациент в самое начало приёма или после начала приёма, если в начало приёма — то приходим тогда.

В цикле while определяем минимальное время, в которое Петя может прийти на приём к врачу. Проверяем приходит ли следующий пациент до завершения приёма предыдущего. Если приходит во время завершения, или через некоторое время, то заходим после приёма предыдущего. (Нам уступают) Если нет, цикл продолжается, проверяет, является ли разница между началом приёма следующего пациента и временем его прихода меньше, чем предыдущая зафиксированная разницы. Если да — записывает её и время прихода данного пациента, и переходит к следующему пациенту.

В конце проверяем, если время приёма ещё не окончено, пациенты все прошли и прийти раньше не получилось — приходим сразу в конце приёма последнего.

Задача на e-olymp
Код программы на ideone
Засчитанное решение

Євчук Даяна

ПМ 1 курс 2 группа.

e-olymp 7095. Факторіали

13/12/2020 by Федяєва Євгенія

Задача

Президент Першого національного Банку майор Томаса Б. Кiнгмена кожну ніч перекладає вміст сейфів, у яких клієнти банку зберігають свої коштовності. Грабіжникам це також відомо, і тому вони орендували один із сейфів у цьому банку й чекають, поки президент перекладе в їхній сейф щось цінне. Таким чином до їхніх рук потрапила скринька з коштовностями самого майора! Тепер у грабіжників є всього лиш кілька годин для того, щоб відкрити кодовий замок з трьох цифр, забрати цінності й повернути скриньку назад, щоб ніхто навіть не дізнався, що пограбування взагалі відбулося.

Знаючи пристасть майора до великих чисел, грабіжники переконані, що кодом є три послідовні цифри числа $N!$, що записують безпосередньо перед нулями наприкінці запису числа $N!$. Наприклад:

при $N$ = $7$ кодом буде $504$, бо $7!$ = $5040$;
при $N$ = $17$ кодом буде $096$, бо $17!$ = $355687428096000$.

За даним натуральним числом $N$ знайти три послідовні цифри числа $N!$, що записують безпосередньо перед нулями наприкінці запису числа $N!$.

Вхідні дані

Вхідний файл містить єдине ціле число $N$. $(7 \leqslant N \leqslant 1000000000)$.

Вихідні дані

Вихідний файл має містити рівно три цифри — шуканий код.

Тесты

№	Входные данные	Выходные данные
1	7	504
2	17	096
3	50	512
4	1000000000	144

Код

#include <iostream>

#define COEF 10000000
#define TEN 10

using namespace std;

unsigned int arr[] = { 1, 94194688,80754176,28792576,93638144,44194688,16269824,94550272,61946112,68933632,
                       68754176,19323648,22612992,36351232,57997312,66792576,2167808,95748096,88043776,
                       37690112,65638144,99247872,80831232,42968832,38960896,2194688,36401664,29433088,
                       21091328,35679232,40269824,3200512,39416576,62174976,23727104,49750272,52626176,
                       72337664,68916224,93513984,25146112,14722816,60257024,2170112,13989632,28933632,
                       91983872,29619968,23259904,52859904,2354176,61171456,14485248,81225984,93129472,
                       98123648,42294528,83940096,91339008,90945024,77812992,83786752,30308352,33122816,
                       709376,45551232,13495552,4053504,28486912,65094912,93197312,79194112,80894208,
                       48729344,89670656,26832576,59147776,51826688,14217984,72698112,10487808,29000448,
                       21455616,72560128,94383616,23588096,83462144,14917632,85698816,11810304,3083776,
                       84299264,11034368,6525952,27101696,68170112,92235008,45980416,15386112,44244224,
                       3398144 };
int main()
{
    int N;
    unsigned long long factorial = 1;
    cin >> N;
    int idx = N/COEF;
    factorial = arr[idx];
    int start = !N%COEF ? idx*COEF : idx*COEF + 1;
    if (N % COEF != 0)
    {
        for(int i = start; i <= N; i++)
        {
            factorial *= i;
            while(factorial % TEN == 0) factorial /= TEN;
            factorial %= COEF;
        }
    }
    factorial %= TEN*TEN*TEN;
    cout << factorial/(TEN*TEN) << (factorial/TEN)%TEN << factorial%TEN;
    return  0;
}

#include <iostream>

#define COEF 10000000

#define TEN 10

using namespace std;

unsigned int arr[] = { 1, 94194688,80754176,28792576,93638144,44194688,16269824,94550272,61946112,68933632,

68754176,19323648,22612992,36351232,57997312,66792576,2167808,95748096,88043776,

37690112,65638144,99247872,80831232,42968832,38960896,2194688,36401664,29433088,

21091328,35679232,40269824,3200512,39416576,62174976,23727104,49750272,52626176,

72337664,68916224,93513984,25146112,14722816,60257024,2170112,13989632,28933632,

91983872,29619968,23259904,52859904,2354176,61171456,14485248,81225984,93129472,

98123648,42294528,83940096,91339008,90945024,77812992,83786752,30308352,33122816,

709376,45551232,13495552,4053504,28486912,65094912,93197312,79194112,80894208,

48729344,89670656,26832576,59147776,51826688,14217984,72698112,10487808,29000448,

21455616,72560128,94383616,23588096,83462144,14917632,85698816,11810304,3083776,

84299264,11034368,6525952,27101696,68170112,92235008,45980416,15386112,44244224,

3398144 };

int main()

{

int N;

unsigned long long factorial = 1;

cin >> N;

int idx = N/COEF;

factorial = arr[idx];

int start = !N%COEF ? idx*COEF : idx*COEF + 1;

if (N % COEF != 0)

{

for(int i = start; i <= N; i++)

{

factorial *= i;

while(factorial % TEN == 0) factorial /= TEN;

factorial %= COEF;

}

factorial %= TEN*TEN*TEN;

cout << factorial/(TEN*TEN) << (factorial/TEN)%TEN << factorial%TEN;

return 0;

}

Решение

Поскольку процесс расчёта факториала больших чисел занимает много времени, его можно ускорить использованием массива факториалов некоторых чисел. Полное значение факториала не нужно, поэтому массив содержит последние $8$ ненулевых цифр значений факториалов чисел, кратных $10000000$, которые можно получить с помощью следующего кода:

#include <iostream>
#define TEN 10
using namespace std;
int main()
{
    int N = 1000000000, count = 1;
    unsigned long long factorial = 1;
    for(int i = 1; i <= N; i++)
    {
        factorial *= i;
        while(factorial%TEN == 0) factorial /= TEN;
        factorial %= 100000000;
        if (i % 10000000 == 0) {cout << factorial << ","; count++;}
        if (count == TEN) {cout << endl; count = 1;}
    }
    return  0;
}

#include <iostream>

#define TEN 10

using namespace std;

int main()

{

int N = 1000000000, count = 1;

unsigned long long factorial = 1;

for(int i = 1; i <= N; i++)

{

factorial *= i;

while(factorial%TEN == 0) factorial /= TEN;

factorial %= 100000000;

if (i % 10000000 == 0) {cout << factorial << ","; count++;}

if (count == TEN) {cout << endl; count = 1;}

}

return 0;

}

Если на входе — число $N$, меньшее $10000000$, его факториал рассчитывается обычным циклом, попутно отбрасывая ненужные цифры высших разрядов. В конце выводятся искомые последние три цифры факториала числа $N$. Если на входе — число $N$, большее $10000000$, выбирается соответствующее значение из массива по индексу $N/10000000$, и далее с помощью цикла считается произведение оставшихся чисел из $N!$. С уменьшением кратности чисел, факториалы которых содержатся в массиве, увеличивается скорость выполнения программы.

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Федяєва Євгенія

e-olymp 7240. Степан — бізнесмен

05/12/2020 by Валентина Михайліщук

Задача

Ужляндія, як відомо, країна з розвиненими торговими відносинами.

Степан вирішив спробувати зайнятися торгівлею і підзаробити собі на відпустку продажем комп’ютерної техніки. Для цього йому необхідно закуповувати техніку у інших продавців. Перш ніж почати роботу, він вирішив постежити за подіями на ринку Ужляндії і придумати, як отримувати найбільший прибуток.

Степан дізнався, що кожен продавець продає один комп’ютер, і кожен покупець готовий купити рівно один комп’ютер. Всього на ринку торгують [latex]N[/latex] продавців, вартість комп’ютера у [latex]i[/latex]-го з них дорівнює [latex]A_{i}[/latex] Ужляндських монет, причому ціни можуть відрізнятися у різних продавців. Крім того, він знайшов для себе [latex]M[/latex] потенційних покупців, кожен з яких хоче купити комп’ютер за [latex]B_{i}[/latex] монет. При цьому сам Степан може купити і продати будь-яку кількість комп’ютерів.

Степану необхідно отримати найбільший прибуток (вигідно купити і вигідно продати). Тому він звернувся за допомогою до Вас — кращому програмісту Ужляндії.

Формат вхідних даних

Перший рядок вхідного файлу містить розділення одиночним пропуском два цілих числа [latex]N, M (1 \leqslant N, M \leqslant 10^{5})[/latex] — кількість продавців на ринку Байтландіі і кількість потенційних покупців відповідно.
Другий рядок містить [latex]N[/latex] цілих чисел [latex]A_{i} (0 \leqslant A_{i} \leqslant 10^{9})[/latex] — вартості, за якими продавці готові продавати комп’ютери.
Третій рядок містить [latex]M[/latex] цілих чисел [latex]B_{i} (0 \leqslant B_{i} \leqslant 10^{9})[/latex] — суми, які потенційні покупці готові віддати при покупці комп’ютера.

Формат вихідних даних

Перший рядок вихідного файлу має містити одне ціле число [latex]S[/latex] — розмір максимальної вигоди в монетах, яку може отримати Степан.

Тести

№	Вхідні дані	Вихідні дані	Пояснення до прикладів
1	2 3 1 1 3 3 3	4	Степан купує комп’ютери у 1-го і 2-го продавців і продає їх будь-яким двом покупцям.
2	6 5 5 10 8 4 7 2 3 1 11 18 9	27	Степану найбільш вигідно купити комп’ютери у 1-го, 4-го і 6-го продавців і продати 3-му, 4-му і 5-му покупцям.
3	4 5 6 7 9 8 3 3 5 1 2	0	Степану невигідно закуповувати техніку, адже ціни продавців перевищують суми, які готові віддати покупці.
4	4 5 4 4 4 4 6 4 3 9 2	7	Степану байдуже в кого купувати комп’ютери, але продати вигідно їх він зможе лише 1-му і 4-му покупцям.
5	3 3 5 1 3 9 8 6	14	Степан купує всі комп’ютери, адже всіх їх він зможе вигідно продати.
6	4 1 2 5 4 6 8	6	Покупець лише один, тому Степан має купити комп’ютер тільки у 1-го продавця.
7	3 6 1 7 4 0 0 0 0 0 0	0	Клієнти є, але ніхто з них не збирається платити, тож Степан не отримає прибутку.
8	4 2 0 7 4 6 0 3	3	Перший продавець віддає свій комп’ютер безкоштовно, а другий покупець готовий заплатити. Отже, Степан може заробити.
9	1 5 5 5 7 9 3 4	4	Хоча покупців багато, але продавець лише один. Степан має продати комп’ютер 3-му клієнту.

Код

#include <iostream>
#include <algorithm>
using namespace std;
bool decrease(int a, int b) {
  return a > b;
}
int main() {
  int N, M, i = 0;
  cin >> N >> M;
  
  int * dealers = new int[N]; //створюємо масив  вартостей, за якими продавці готові продавати комп'ютери
  for (int i = 0; i < N; i++) {
    cin >> dealers[i];
  }
  int * clients = new int[M]; //створюємо масив сум, які покупці готові віддати при покупці комп'ютера
  for (int i = 0; i < M; i++) {
    cin >> clients[i];
  }
  sort(dealers, dealers + N); //відсортуємо масив за зростанням ціни
  sort(clients, clients + M, decrease); //відсортуємо масив за спаданням ціни
  long int S = 0;
  while (dealers[i] < clients[i] && i < N) {
    S += (clients[i] - dealers[i]); //розраховуємо вигоду
    i++;
  }
  cout << S;
  return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

bool decrease(int a, int b) {

return a > b;

}

int main() {

int N, M, i = 0;

cin >> N >> M;

int * dealers = new int[N]; //створюємо масив вартостей, за якими продавці готові продавати комп'ютери

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

cin >> dealers[i];

}

int * clients = new int[M]; //створюємо масив сум, які покупці готові віддати при покупці комп'ютера

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

cin >> clients[i];

}

sort(dealers, dealers + N); //відсортуємо масив за зростанням ціни

sort(clients, clients + M, decrease); //відсортуємо масив за спаданням ціни

long int S = 0;

while (dealers[i] < clients[i] && i < N) {

S += (clients[i] - dealers[i]); //розраховуємо вигоду

i++;

}

cout << S;

return 0;

}

Розв’язок

Щоб отримати маскимальну вигоду, Степан має купувати комп’ютери за найменшою ціною, а продавати якомога дорожче. Отже, потрібно створити масиви і відсортувати їх: масив вартостей, за якими продавці готові продавати комп’ютери — за зростанням; масив сум, які потенційні покупці готові віддати при покупці комп’ютера — за спаданням. Далі створюємо цикл, за допомогою якого розраховуємо вигоду від реалізації кожного комп’ютера. Оскільки масиви відсортовані, то, як тільки прибуток стане від’ємним або нульовим, можемо припинити розрахунки і вивести розмір максимальної вигоди.

Посилання

Код на ideone
Задача на e-olymp
Зарахований розв’язок на e-olymp

Валентина Михайліщук

e-olymp 399. Последствия гриппа в Простоквашино

19/05/2020 by Никита Репнин

Задача

”Дорогой дядя Фёдор!

После того, как мама испугалась, что ты можешь заболеть какой-то нечеловеческой болезнью и забрала тебя в город, Шарик видимо все-таки чем-то заболел, ибо его поступки я уже иначе объяснить не могу, как последствиями постоянного общения с Хрюшей.

Суди сам: он сначала распилил шахматную доску на квадратики, потом на каждый квадратик наклеил изображение круглой скобки и, выдав определенное количество квадратиков, заставляет меня считать, сколько разных правильных скобочных последовательностей я смогу построить из имеющегося у меня числа квадратиков. При этом он еще и требует, чтобы я использовал все квадратики!

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

Дядя Фёдор, если тебе не трудно, напиши мне программу для подсчета этого количества, ибо из-за того, что Шарик задает мне свою непонятную задачу до 20 раз на день, у меня даже не остается времени ухаживать за моей любимой коровой.

Всегда твой верный друг – кот Матроскин.”

Помогите дяде Фёдору написать программу для Матроскина, иначе тот может остаться без молока.

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

В первой строке задано число $n$ – количество заданий Шарика за день. В следующих $n$ строках задано по одному числу $k$ – количество выданных в очередной раз Матроскину квадратиков с изображением скобок. Квадратики Матроскин может переворачивать, получая при этом как открывающую, так и закрывающую скобку.

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

Вывести в $n$ строках по одному числу – ответ на соответствующее задание Шарика.

Тесты

№	Входные данные	Выходные данные
1	3 2 3 4	1 0 2
2	5 3 11 7 43 27	0 0 0 0 0
3	6 2 28 42 14 64 0	1 2674440 24466267020 429 55534064877048198 1

Код

#include <iostream>
using namespace std;
 
int main() {
    int n, k;
    long long brackets [33];
    brackets [0] = 1;
    for(int i = 1; i <= 32; ++ i){
        brackets [i]=0;
        for(int j = 0; j < i; ++ j){
            brackets [i] += brackets [j] * brackets [i - 1 - j];
        }
    }
    cin >> n;
        for (int i = 0; i < n; i ++) {
        cin >> k;
        cout << (k % 2 == 0 ? brackets [k / 2] : 0) << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, k;

long long brackets [33];

brackets [0] = 1;

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

brackets [i]=0;

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

brackets [i] += brackets [j] * brackets [i - 1 - j];

}

cin >> n;

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

cin >> k;

cout << (k % 2 == 0 ? brackets [k / 2] : 0) << endl;

}

return 0;

}

Решение

Правильную скобочную последовательность можно построить лишь из четного количества скобок, т.е. для нечетного числа ответ заведомо $0$. А для $2m$ скобок ($m$ открывающих и $m$ закрывающих) ответ равен числу Каталана $C_m$. Для вычисления которого используется рекуррентное соотношение: $$C_m=\sum_{i=0}^{m-1} C_i \cdot C_{m-1-i}$$

Задача на e-olymp
Код программы на ideone
Засчитанное решение

Никита Репнин

Странно, я точно помню,что что-то здесь писал…

e-olimp 8536. Заповнення смуги $3 \times n$

03/05/2020 by Анна Цивинская

Внимание: Задача на сайте e-olymp была заменена на другую. Теперь такой задачи там нет.

Задача

Смугу висотою $3$ см і шириною $n$ см суцільно заповнено прямокутниками $3 \times 1$ та $1 \times 3$ см. Скількома способами можна її заповнити? Різні способи – це різні кількості вказаних прямокутників та їх різні розташування.

Вхідні дані

Одне натуральне число $n$ $(1 \leqslant n \leqslant 50)$.

Вихідні дані

Вивести кількість способів, якими можна заповнити смугу.

Тести

Вхідні дані	Вихідні дані
1	1
5	4
12	60
50	122106097

Код № 1

#include <iostream>
using namespace std;
 
int main() {
   int n;
   cin >> n;
   int F[51] = {0, 1, 1, 2, 3};
   for(int i = 5; i <= n; i++) {
      F[i] = F[i-2] + F[i-3] + F[i-4];
   }
   cout << F[n];
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int F[51] = {0, 1, 1, 2, 3};

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

F[i] = F[i-2] + F[i-3] + F[i-4];

}

cout << F[n];

return 0;

}

Рішення 1

Це завдання на динамічне програмування, тому спочатку нам потрібно розбити цю задачу на декілька простих. Треба порахувати кількість способів для чотирьох перших елементів масиву. Якщо рахувати далі, то ми помітимо, що кожне наступне значення отримується за формулою F[i] = F[i-2] + F[i-3] + F[i-4].

Код № 2

#include <iostream>
using namespace std;
 
int F[51] = {0, 1, 1, 2, 3};
 
int numberOfWays(int n) {
   if(F[n]) {
      return F[n];
   } else {
      F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);
   }
   return F[n];
}
 
int main() {
   int n;
   cin >> n;
   cout << numberOfWays(n);
   return 0;
}

#include <iostream>

using namespace std;

int F[51] = {0, 1, 1, 2, 3};

int numberOfWays(int n) {

if(F[n]) {

return F[n];

} else {

F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);

}

return F[n];

}

int main() {

int n;

cin >> n;

cout << numberOfWays(n);

return 0;

}

Рішення 2

Також для рішення цієї задачі можна використати рекурсію. При виклику функції ми перевіряємо, чи є в пам’яті це значення. Якщо такого значення не має, то ми його рахуємо. Таким чином ми уникаємо використання зайвої пам’яті.

Посилання

Умова задачі на E-Olymp
Зараховане рішення № 1 на E-Olymp
Зараховане рішення № 2 на E-Olymp
Код задачі № 1 на Ideone
Код задачі № 2 на Ideone

Анна Цивинская

I study at the Odessa I.I.Mechnikov National University, specializing in Applied Mathematics.

e-olimp 8234. Сходинки

09/04/2020 by Елизавета Савицкая

Задача

Скількома способами можна потрапити на $n$-ту сходинку, якщо можна ступати на наступну, переступати через одну і через дві сходинки.

Вхідні дані

Одне число $n$ — номер сходинки $(n \leqslant 60)$.

Вихідні дані

Вивести кількість способів, якими можна потрапити на $n$-ту сходинку.

Тести

Вхідні дані	Вихідні дані
0	1
5	13
15	5768
32	181997601
60	4680045560037375

Код № 1

#include <iostream>
using namespace std;

int main() {
   int n;
   cin >> n;
   long long arr[61] = {0};
   arr[0] = 1;
   arr[1] = 1;
   arr[2] = 2;
   for(int i = 3; i <= n; i++) {
      arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
   }
   cout << arr[n];
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

long long arr[61] = {0};

arr[0] = 1;

arr[1] = 1;

arr[2] = 2;

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

arr[i] = arr[i-1] + arr[i-2] + arr[i-3];

}

cout << arr[n];

return 0;

}

Рішення

Розіб’ємо задачу на декілька простих. Спочатку розрахуємо кількість способів для однієї сходинки (1 спосіб), потім для двох (2 способи: 0 $\rightarrow$ 1 $\rightarrow$ 2; 0 $\rightarrow$ 2) і також потрібно врахувати випадок, коли кількість сходинок дорівнює нулю (1 спосіб). Далі легко помітити, що кожне наступне значення дорівнює сумі трьох попередніх звідки і отримуємо формулу:
arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
Також цю задачу можна вирішити за допомогою рекурсії. Я використала рекурсію з запам’ятовуванням для того, щоб уникнути переповнення стеку викликів (загальна ідея така: при кожному виклику функції перевіряємо, чи маємо ми вже це значення, і якщо ні, рахуємо його. Таким чином ми будемо використовувати кожне значення лише один раз).

Код № 2

#include <iostream>
using namespace std;

long long arr[61] = {0};

long long num_of_ways(int n) {
   if(arr[n]) {
      return arr[n];
   }
   else {
      arr[n] = num_of_ways(n-1) + num_of_ways(n-2) + num_of_ways(n-3);
   }
   return arr[n];
}
int main() {
   int n;
   cin >> n;
   arr[0] = 1;
   arr[1] = 1;
   arr[2] = 2;
   cout << num_of_ways(n);
   return 0;
}

#include <iostream>

using namespace std;

long long arr[61] = {0};

long long num_of_ways(int n) {

if(arr[n]) {

return arr[n];

}

else {

arr[n] = num_of_ways(n-1) + num_of_ways(n-2) + num_of_ways(n-3);

}

return arr[n];

}

int main() {

int n;

cin >> n;

arr[0] = 1;

arr[1] = 1;

arr[2] = 2;

cout << num_of_ways(n);

return 0;

}

Посилання

Елизавета Савицкая

В жизни нет ничего невозможного

e-olymp 236. Триомино

30/03/2020 by Евгений Фищук

Триомино

Сколькими способами можно замостить прямоугольник $2 × n$ триоминошками? Триомино — это геометрическая фигура, составленная из трех квадратов, соединяющихся между собой вдоль полного ребра. Есть только две возможных триоминошки:

Например, замостить прямоугольник $2 × 3$ можно только тремя различными способами. Поскольку ответ может быть достаточно большим, искомое количество способов следует вычислять по модулю $10^6$.

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

Первая строка содержит количество тестов $t$ ($1 \leqslant t \leqslant 100$). Каждая из следующих $t$ строк содержит значение $n$ ($0 < n < 10^9$).

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

Для каждого теста в отдельной строке выведите количество способов, которыми можно замостить прямоугольник $2 × n$. Результат следует выводить по модулю $10^6$.

Тесты

№	Входные данные	Выходные данные
1	3 3 4 6	3 0 11
2	4 12 15 21 9	153 571 7953 41

Код

#include <iostream>
#include <vector>
#define MOD 1000000
typedef long long ll;
using namespace std;

vector<vector<ll>> multiply(vector<vector<ll>> v1) {
    ll x00 = v1[0][0];
    ll x01 = v1[0][1];
    ll x10 = v1[1][0];
    ll x11 = v1[1][1];
    ll res00, res01, res10, res11;
    res00 = ((x00 * x00) % MOD + (x10 * x01) % MOD) % MOD;
    res01 = ((x00 * x01) % MOD + (x01 * x11) % MOD) % MOD;
    res10 = ((x10 * x00) % MOD + (x10 * x11) % MOD) % MOD;
    res11 = ((x10 * x01) % MOD + (x11 * x11) % MOD) % MOD;
    return{ {(res00 + MOD) % MOD, (res01 - MOD) % MOD}, {(res10 + MOD) % MOD, (res11 - MOD) % MOD} };
}
vector<vector<ll>> pow_mod(vector<vector<ll>> v, int p) {

    if (p == 1) return v;
    if ((p % 2) == 0) {
        vector<vector<ll>> vct = (pow_mod(v, p / 2));
        return multiply(vct);
    }
}

int main() {
    int t, n;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> n;
        if (n % 3)
        {
            cout << 0 << endl;
        }
        else
        {
            n /= 3;
            int p = 2;
            ll a1 = 1, a2 = 1;
            while (n > 0)
            {
                if (n & 1)
                {
                    vector<vector<ll>> a = { {4,-1},{1,0} };
                    a = pow_mod(a, p / 2);
                    ll tmp1 = a1;
                    ll tmp2 = a2;
                    a1 = (tmp1 * a[0][0]) % MOD + (tmp2 * ((a[0][1] + MOD) % MOD)) % MOD;
                    a2 = (tmp1 * a[1][0]) % MOD + (tmp2 * ((a[1][1] + MOD) % MOD)) % MOD;
                }
                p *= 2;
                n >>= 1;
            }
            cout << a1 % MOD << endl;
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

#define MOD 1000000

typedef long long ll;

using namespace std;

vector<vector<ll>> multiply(vector<vector<ll>> v1) {

ll x00 = v1[0][0];

ll x01 = v1[0][1];

ll x10 = v1[1][0];

ll x11 = v1[1][1];

ll res00, res01, res10, res11;

res00 = ((x00 * x00) % MOD + (x10 * x01) % MOD) % MOD;

res01 = ((x00 * x01) % MOD + (x01 * x11) % MOD) % MOD;

res10 = ((x10 * x00) % MOD + (x10 * x11) % MOD) % MOD;

res11 = ((x10 * x01) % MOD + (x11 * x11) % MOD) % MOD;

return{ {(res00 + MOD) % MOD, (res01 - MOD) % MOD}, {(res10 + MOD) % MOD, (res11 - MOD) % MOD} };

}

vector<vector<ll>> pow_mod(vector<vector<ll>> v, int p) {

if (p == 1) return v;

if ((p % 2) == 0) {

vector<vector<ll>> vct = (pow_mod(v, p / 2));

return multiply(vct);

}

int main() {

int t, n;

cin >> t;

for (int i = 0; i < t; i++)

{

cin >> n;

if (n % 3)

{

cout << 0 << endl;

}

else

{

n /= 3;

int p = 2;

ll a1 = 1, a2 = 1;

while (n > 0)

{

if (n & 1)

{

vector<vector<ll>> a = { {4,-1},{1,0} };

a = pow_mod(a, p / 2);

ll tmp1 = a1;

ll tmp2 = a2;

a1 = (tmp1 * a[0][0]) % MOD + (tmp2 * ((a[0][1] + MOD) % MOD)) % MOD;

a2 = (tmp1 * a[1][0]) % MOD + (tmp2 * ((a[1][1] + MOD) % MOD)) % MOD;

}

p *= 2;

n >>= 1;

}

cout << a1 % MOD << endl;

}

return 0;

}

Решение

Если n нацело не делится на $3$, то выводится ноль,в ином случае данная задача решается через рекуррентную формулу $a_n=4*a_{n-1}-a_{n-2}$. Но из-за слишком больших чисел мы не можем использовать данную формулу просто так, поэтому мы воспользуемся быстрым вычислением членов рекуррентной последовательности через матрицы. Надо умножать матрицу

$\begin{pmatrix}
4&-1 \\
1&0 \\
\end{pmatrix}$ в степени $p$(где $p$ равна двойке в степени номера единицы в двоичной записи числа ${{n}\over{3}}$) на матрицу $\begin{pmatrix}
1\\
1\\
\end{pmatrix}$ каждый раз, когда встречается единица в двоичной записи числа ${{n}\over{3}}$. На выход подается первое число вектора $2 × 1$.

Ссылки

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

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

Евгений Фищук

e-olymp 9066. Кружок стрельбы

03/03/2020 by Владислав Гринькив

Задача

После успешного обучения Атрея стрельбе из лука «Когтя» Фэй решила не останавливаться на достигнутом и открыть целый кружок стрельбы из лука.

На занятие кружка пришли $n$ учеников. Фэй пронумеровала их целыми числами от $1$ до $n$. В начале занятия ученики встали вдоль координатной прямой, заблаговременно нарисованной на полу, причем i-й ученик стоял в точке с координатой $x_i$. Получилось так, что координаты учеников строго возрастали, то есть $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

У каждого из учеников есть свой волшебный лук, который характеризуется своей дальностью $r_i$ и силой $c_i$. Оба параметра — целые положительные числа. Когда ученик совершает выстрел из лука, магический снаряд начинает лететь вдоль координатной прямой в сторону увеличения координаты. Снаряд летит до тех пор, пока его сила положительна. В момент выстрела сила заряда равна силе лука, из которого совершается выстрел. Каждый раз, когда снаряд пролетает очередные $r_i$ единиц расстояния вдоль прямой, он теряет одну единицу силы.

Если ученик произвел выстрел, и снаряд, выпущенный им, достиг следующего по порядку вдоль прямой ученика, снаряд прекращает свой полет, а ученик, которого достиг снаряд, внезапно решает, что ему тоже надо произвести выстрел, и совершает его. Ученик совершит выстрел, даже если снаряд достиг его, имея силу $0$.

Фэй хочет, чтобы каждый ученик совершил хотя бы один выстрел. Для этого она может дать команду некоторым ученикам сделать это, после чего эти ученики совершат выстрел, что может повлечь за собой новые выстрелы других учеников.

Помогите Фэй определить минимальное количество учеников, которым надо дать команду совершить выстрел, чтобы каждый ученик в результате совершил хотя бы один выстрел.

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

Первая строка содержит количество учеников $n$ $(1 \leqslant n \leqslant 1000)$ на кружке Фэй.

Каждая из следуюших $n$ строк содержит три целых числа $x_i$, $r_i$ и $c_i$ ($1 \leqslant x_i \leqslant 10^9$, $1 \leqslant r_i$, $c_i \leqslant 100$) — координату очередного ученика, а также дальность и силу его лука соответственно. Гарантируется, что $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

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

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

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 1 3 3 5 1 2 8 2 3 10 1 2 11 3 2	2
2	6 1 3 5 4 2 2 7 4 3 10 1 2 11 3 2 13 4 3	1

Код

#include <iostream>
using namespace std;
struct archerProfile {
  unsigned long x;
  unsigned long r;
  unsigned int c;
}archer[1000];
int main(){ 
  int n;
  int commands = 1;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> archer[i].x >> archer[i].r >> archer[i].c;
  }
  for (int i = 0; i < n - 1; i++) {
    unsigned long long distanceBetweenArchers = archer[i + 1].x - archer[i].x;
    if (distanceBetweenArchers > archer[i].c * archer[i].r) {
      commands += 1;
    }
  }
  cout << commands;
  return 0;
}

#include <iostream>

using namespace std;

struct archerProfile {

unsigned long x;

unsigned long r;

unsigned int c;

}archer[1000];

int main(){

int n;

int commands = 1;

cin >> n;

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

cin >> archer[i].x >> archer[i].r >> archer[i].c;

}

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

unsigned long long distanceBetweenArchers = archer[i + 1].x - archer[i].x;

if (distanceBetweenArchers > archer[i].c * archer[i].r) {

commands += 1;

}

cout << commands;

return 0;

}

Решение

Для решения задачи, мы должны найти расстояние между лучниками, то есть $x_{i+1}-x_i$, после чего найти максимальное расстояние, которое пролетит стрела у $x_{i}$ лучника умножив силу его лука $c_i$ и расстояние $r_i$, после чего сделать проверку, если расстояние между лучниками больше чем максимальное расстояние которое пролетит стрела, то мы дадим команду совершить ещё один выстрел.

Ссылки

Условие задачи на e-olymp
Код на Ideone
Засчитанное решение на e-olymp

Владислав Гринькив

e-olymp 1462. Хитрая сортировка

25/02/2020 by Нина Хоробрых

Задача

Дана последовательность чисел. Вам следует упорядочить их по неубыванию последней цифры, а при равенстве последних цифр – по неубыванию самих чисел.

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

Первая строка содержит число $n \ (1 \leqslant n \leqslant 1000)$, а вторая — сами натуральные числа, не превышающие $32000$.

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

Выведите последовательность чисел, упорядоченную согласно условию.

Тесты

№	Входные данные	Выходные данные
1	7 12 15 43 13 20 1 15	12 33 14 44 64 77
2	4 345 112 999 29	112 345 29 999
3	9 78 33 13 0 12 89 20 78 9990	0 20 9990 12 13 33 78 78 89

Код

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int mass[n];
    for (int i = 0; i < n; i++) {
        cin >> mass[i];
    }
    
    for (int i = 0; i < n; i++){
        for (int j = 1; j < (n - i);  j++) {
        if (mass[j] % 10 < mass[j-1] % 10) {
                swap (mass[j-1], mass[j]);
        } 
        else if ( mass[j] % 10 == mass[j-1] % 10 and mass[j] < mass[j-1]){
            swap (mass[j-1], mass[j]);
        }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << mass[i] << " ";
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n;

cin >> n;

int mass[n];

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

cin >> mass[i];

}

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

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

if (mass[j] % 10 < mass[j-1] % 10) {

swap (mass[j-1], mass[j]);

}

else if ( mass[j] % 10 == mass[j-1] % 10 and mass[j] < mass[j-1]){

swap (mass[j-1], mass[j]);

}

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

cout << mass[i] << " ";

}

return 0;

}

Решение

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

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Нина Хоробрых

Student of Odessa I. I. Mechnikov National University.

e-olymp 8956. Вывести массив 4

25/02/2020 by Кирилл Колесник

Задача

Задан массив из [latex]n[/latex] целых чисел. Выведите только его отрицательные элементы, изменив первоначальный порядок на противоположный.

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

Первая строка содержит число [latex]n (1 \leqslant n \leqslant 100)[/latex]. Во второй строке записаны [latex]n[/latex] целых чисел, каждое из которых не превышает по модулю [latex]100[/latex].

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

В первой строке выведите количество отрицательных элементов массива. Во второй строке выведите сами отрицательные элементы в обратном порядке. Если отрицательных элементов в массиве нет, то выведите [latex]«NO»[/latex].

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	7 -2 5 4 -3 7 -1 0	3 -1 -3 -2
2	5 2 1 0 1 5	NO
3	3 -1 -2 -3	3 -3 -2 -1

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

#include <iostream>
using namespace std;

int main() {
    int n, count = 0;
    cin >> n; 
    int arr[n];
    for (int i = 0; i < n; i++){
        cin >> arr[i];
        if (arr[i] < 0){
            count++;
        }
    }
    if(count == 0){
        cout << "NO";
    } else {
        cout << count << endl;
        for (int c = n - 1; c >= 0; c--){
            if (arr[c] < 0){
                cout << arr[c] << " "; 
            }
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, count = 0;

cin >> n;

int arr[n];

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

cin >> arr[i];

if (arr[i] < 0){

count++;

}

if(count == 0){

cout << "NO";

} else {

cout << count << endl;

for (int c = n - 1; c >= 0; c--){

if (arr[c] < 0){

cout << arr[c] << " ";

}

return 0;

}

Решение задачи

Для решения этой задачи, прежде всего, необходимо объявить две целочисленные переменные ― [latex]n[/latex] и [latex]count[/latex]. Переменная [latex]n[/latex] считывает первое число в строке ввода, и после объявления некоторого массива arr[n], она становится значением числа его элементов. Переменной [latex]count[/latex] обязательно присваиваем значение [latex]0[/latex], ведь именно она позднее будет отвечать за подсчет отрицательных элементов заданного массива.

С помощью цикла for задаем массив, начиная с нулевого элемента и заканчивая [latex]n[/latex]-ым элементом (не включительно!). Внутри цикла размещаем условный оператор if, который прибавляет единицу к переменной count каждый раз, когда элемент массива отрицателен. После окончания цикла важно не забыть о еще одном условном операторе, который будет выводить [latex]«NO»[/latex] и заканчивать работу программы, если значение [latex]count[/latex] равно нулю (то есть именно в том случае, если в массиве не будет ни одного отрицательного элемента). Но если в массиве всё же есть отрицательные элементы, то программа должна продолжить работу, что мы и предусматриваем, выполняя все остальные операции в рамках оператора else. Отлично! Теперь полученное значение переменной [latex]count[/latex] (если оно больше нуля) можно вывести, однако это еще не конец, ведь также необходимо вывести все отрицательные элементы в обратном порядке, так что переходим на новую строку с помощью endl и продолжаем.

Реализация подобной процедуры не так сложна, как кажется. Для этого необходимо создать еще один цикл for, перебирающий массив с конца (то есть от [latex]n-1[/latex] до [latex]0[/latex] включительно). Внутри цикла вновь создаем условный оператор if, который каждый раз выводит элемент массива (с пробелом), если он оказывается отрицательным. Не забываем закрыть скобку оператора else, ведь эта процедура также выполняется внутри условного оператора.

Готово!

Кирилл Колесник

e-olymp 2386. Следующая перестановка

10/02/2020 by Виктория Крачилова

Условие задачи

Найдите следующую перестановку. Тождественная перестановка является следующей для обратной.

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

В первой строке записано количество элементов $n$ $\left(1\leqslant n\leqslant10^5\right)$ в перестановке. Во второй строке записана перестановка из $n$ чисел.

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

Вывести $n$ чисел — искомую перестановку.

Тесты

№	Ввод	Вывод
1	3 3 2 1	1 2 3
2	1 9	9
3	5 2 4 5 3 1	2 5 1 3 4
4	4 3 5 4 1	4 1 3 5
5	2 2 3	3 2

Алгоритм Нарайаны

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

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int n;
    cin>>n;
    int a[n]; // массив для перестановки из n чисел
    for (int i = 0; i < n; i++) cin>> a[i];
    for (int i = n - 2; i >= 0; i--) { 
        if (a[i] < a[i+1]){
            int min = i + 1; // индекс минимального элемента 
            for (int j = i + 2; j < n; j++) {
                if (a[j] > a[i] && a[j] < a[min]) min = j;
            }
            swap(a[i], a[min]);
            reverse(&a[i+1], &a[n]);
            break;
        }
        if (i == 0) reverse(&a[i], &a[n]);
    }
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n;

cin>>n;

int a[n]; // массив для перестановки из n чисел

for (int i = 0; i < n; i++) cin>> a[i];

for (int i = n - 2; i >= 0; i--) {

if (a[i] < a[i+1]){

int min = i + 1; // индекс минимального элемента

for (int j = i + 2; j < n; j++) {

if (a[j] > a[i] && a[j] < a[min]) min = j;

}

swap(a[i], a[min]);

reverse(&a[i+1], &a[n]);

break;

}

if (i == 0) reverse(&a[i], &a[n]);

}

for (int i = 0; i < n; i++) cout << a[i] << " ";

return 0;

}

Решение

Пусть $a$ — данная $n$-элементная перестановка $\left(a\;=\;\left[a_1,\;a_2,\;…,\;a_n\right]\right)$. Применяем алгоритм Нарайаны :

Находим наибольший номер $i$ (если он существует), такой, что $a_i<a_{i+1}$. Находим такой номер $j$, что число $a_j$ является наименьшим среди чисел $a_{i+1},\;a_{i+2},\;…,\;a_n$, превосходящим $a_j$. Меняем местами элементы $a_i$ и $a_j$ .
Если такого номера не существует, то $a$ — наибольшая $n$-элементная перестановка.
Изменяем порядок элементов, занимающих места с $\left(i+1\right)$-го по $n$-е, на противоположный.

Полученная перестановка $\left[a_1,\;a_2,\;…,\;a_{i-1},\;a_j,\;a_n,\;a_{n-1},\;…,\;a_{j+1},\;a_i,\;a_{j-1},\;…,\;a_{i+1}\right]$ будет являться искомой перестановкой.

Ссылки

Функция next_permutation()

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

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

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    next_permutation(a, a+n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n;

cin >> n;

int a[n];

for (int i = 0; i < n; i++) cin >> a[i];

next_permutation(a, a+n);

for (int i = 0; i < n; i++) cout << a[i] << " ";

return 0;

}

Решение

Применяем функцию next_permutation() , которая генерирует следующую лексиграфическую перестановку в диапазоне элементов.

Ссылки

Виктория Крачилова

студентка Одесского национального университета имени И.И. Мечникова

e-olymp 1661. Рюкзак Алладина

29/01/2020 by Валентин Цушко

Условие

Попав в пещеру с сокровищами, наш Алладин не стал брать старую почерневшую лампу. Он кинулся собирать в свой рюкзак золотые монеты и драгоценные камни. Он бы, конечно, взял все, но чудес не бывает — слишком большой вес рюкзак может просто не выдержать.

Много раз он выкладывал одни вещи и на их место помещал другие, пытаясь как можно выше поднять стоимость взятых драгоценностей.

Требуется определить максимальную стоимость груза, который Алладин может поместить в свой рюкзак.

Будем считать, что в пещере имеются предметы $n$ различных типов, количество предметов каждого типа не ограничено. Максимальный вес, который может выдержать рюкзак, равен $w$. Каждый предмет типа $i$ имеет вес $w_{i}$ и стоимость $v_{i}$ $(i = 1, 2, \ldots, n)$.

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

В первой строке содержится два натуральных числа $w$ и $n$ $(1 \leqslant w \leqslant 250, 1 \leqslant n \leqslant 35)$ — максимальный вес предметов в рюкзаке и количество типов предметов. Следующие $n$ строк содержат по два числа $w_{i}$ и $v_{i}$ $(1 \leqslant w_{i} \leqslant 250, 1 \leqslant v_{i} \leqslant 250)$ — вес предмета типа $i$ и его стоимость.

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

Выведите максимальную стоимость груза, вес которого не превышает $w$.

Тесты

№	Входные данные	Выходные данные
1	10 2 5 10 6 19	20
2	250 35 187 100 28 109 245 142 123 83 237 78 36 172 15 248 90 24 181 137 40 233 8 99 231 128 79 132 43 217 156 104 45 191 130 113 105 225 206 5 26 120 26 119 64 138 23 147 19 202 79 54 149 185 158 79 209 88 110 133 235 209 188 230 15 220 107 164 235 137 60 167	4067
3	35 4 20 4 1 2 10 8 7 6	70

Программный код

#include <iostream>
using namespace std;
 
int main()
{
    int w, n;
    const int NegNum = -1;
    cin >> w >> n;
    int WeiCos[n][2], s[w + 1];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 2; j++){
            cin >> WeiCos[i][j];
        }
    }
    s[0] = 0;
    for(int j = 1; j <= w; j++){
        s[j] = NegNum;
    }
    for(int i = 0; i < n; i++){
        for(int j = WeiCos[i][0]; j <= w; j++){
            if(s[j - WeiCos[i][0]] != NegNum && s[j] < s[j - WeiCos[i][0]] + WeiCos[i][1]){
                s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];
            }
        }
    }
    int maxS = 0;
    for(int i = 1; i <= w; i++){
        maxS = max(maxS, s[i]);
    }
    cout << maxS;
 
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int w, n;

const int NegNum = -1;

cin >> w >> n;

int WeiCos[n][2], s[w + 1];

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

for(int j = 0; j < 2; j++){

cin >> WeiCos[i][j];

}

s[0] = 0;

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

s[j] = NegNum;

}

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

for(int j = WeiCos[i][0]; j <= w; j++){

if(s[j - WeiCos[i][0]] != NegNum && s[j] < s[j - WeiCos[i][0]] + WeiCos[i][1]){

s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];

}

int maxS = 0;

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

maxS = max(maxS, s[i]);

}

cout << maxS;

return 0;

}

Решение

Допустим $w = 9$, $n = 2$, первый предмет $w_{1} = 3$, $n_{1} = 4$, а второй предмет $w_{2} = 2$, $n_{2} = 1$. После того как считаем условие в два одномерных или один двумерный массив (как вам удобнее). Создадим одномерный массив в котором его размер будет равен $w$ и первый элемент будет равен 0, а остальные будут равны минус бесконечности или как в нашем случае (в коде) -1, как показано на (рис. 1). И дальше как показано на (рис. 2) начиная с элемента с номером веса предмета мы прибавляем его стоимость к стоимости предыдущей как показано в коде s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];, если прошлый не минус бесконечность. И так же со вторым элементом, когда они пересекаются с первым мы их сравниваем и вписываем в массив, больший. И в самом конце проходим заново массив и выбираем самый больший элемент, где бы он ни был как показано на (рис. 3). И таким образом на последних позициях которые равняются весу, будут записаны самые дорогие комбинации, благодаря записи самых дорогих элементов в ячейки.

Ссылки:
Задача на e-olymp
Код на OnlineGDB
Код на Ideone
Засчитанное решение на e-olymp

Валентин Цушко

Всё идёт по плану

e-olymp 2663. Сортировка пузырьком

28/01/2020 by Даниил Кадочников

Условие

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

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

В первой строке содержится количество элементов $n$ ($1 \leqslant n \leqslant 1000$) в массиве. Во второй строке — сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10$^$9$.

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

Выведите одно число — количество обменов пузырьковой сортировки.

Тесты

№	Ввод	Вывод
1	3 1 3 2	1
2	2 2 1	1
3	4 4 1 5 3	3
4	5 5 4 1 100000 7	4
5	6 6 5 4 3 2 1	15

Решение

Используем простой алгоритм пузырьковой сортировки: проходим по массиву циклом, если два элемента стоят не в том порядке, то меняем их местами. Так как задача состоит в том, чтобы вывести число обменов, при каждом обмене прибавляем к счётчику $1$. При каждом выполнении цикла по j ставится на место хотя бы 1 элемент, поэтому с каждым полным проходом его длина сокращается на $1$.

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

#include <iostream>
using namespace std;
int n;

int main() {
    cin >> n;
    int arr[n];

    for(int i=0; i<n; i++) cin >> arr[i];
    int counter=0;
    for(int u=0; u<n;u++) {
        for(int j=1; j<(n-u); j++) {
            if((arr[j]<arr[j-1])) {
                
                int prev;
                prev = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = prev;
                counter++;            
            }
        }
    }
    cout << counter;
    return 0;
}

#include <iostream>

using namespace std;

int n;

int main() {

cin >> n;

int arr[n];

for(int i=0; i<n; i++) cin >> arr[i];

int counter=0;

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

for(int j=1; j<(n-u); j++) {

if((arr[j]<arr[j-1])) {

int prev;

prev = arr[j-1];

arr[j-1] = arr[j];

arr[j] = prev;

counter++;

}

cout << counter;

return 0;

}

Ссылки

решение на e-olymp
код на ideone

Даниил Кадочников

e-olymp 8963. Наименьшие влево

19/01/2020 by Даниил Кадочников

Условие

Задан массив из [latex]n[/latex] целых чисел. Переместить все минимальные элементы в начало массива, не меняя порядок других.

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

В первой строке записано натуральное число [latex]n[/latex]. В следующей строке записаны [latex]n[/latex] целых чисел. Все числа по модулю не превышают [latex]100[/latex].

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

Выведите элементы обновленного массива.

Тесты

№	Ввод	Вывод
1	7 6 -3 -7 4 -7 -4 5	-7 -7 6 -3 4 -4 5
2	2 100 -100	-100 100
3	6 -2 -2 7 3 99 -2	-2 -2 -2 7 3 99
4	5 1 1 1 1 1	1 1 1 1 1

Решение

Вместо обычных массивов будем использовать векторы, чтобы было удобнее добавлять элементы в конец. Минимальный элемент можно найти с помощью простого цикла: если какой-либо элемент вектора меньше min, то min присваивается значение этого элемента, и так пока не найдено наименьшее число. Подсчитаем, сколько раз оно встречается в векторе. Столько же раз его нужно добавить в новый вектор. Наконец, переносим в v2 все оставшиеся элементы, не равные min.

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

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

int main()
{
    int n;
    cin >> n;
    vector <int> v, v2;
    int x;
    while(cin>>x) v.push_back(x);
    int min = v[0];
    for(int q=1; q<n; q++) {
        if(v[q]<min) min = v[q];
    }

    int min_counter = 0;
    for(int w=0; w<n; w++) {
        if(v[w] == min) min_counter++;
    }

    for(int e=0; e<min_counter; e++) v2.push_back(min);
    for(int r=0; r<n; r++) {
        if(v[r]!=min) v2.push_back(v[r]);
    }
    for(int t=0; t<n; t++) cout << v2[t] << " ";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

int n;

cin >> n;

vector <int> v, v2;

int x;

while(cin>>x) v.push_back(x);

int min = v[0];

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

if(v[q]<min) min = v[q];

}

int min_counter = 0;

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

if(v[w] == min) min_counter++;

}

for(int e=0; e<min_counter; e++) v2.push_back(min);

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

if(v[r]!=min) v2.push_back(v[r]);

}

for(int t=0; t<n; t++) cout << v2[t] << " ";

return 0;

}

Ссылки

решение на E-olymp
код на ideone

Даниил Кадочников