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 396. Дождь

24/11/2021 by Александр Мармалюк

Условие

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

Напишите программу, которая по координате $\ x_0\ $ точки появления капли над землей вычисляет координату $x$ точки соприкосновения капли с землей $\ \left(y = 0\right).\ $ Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка.

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

Во входном файле в первой строке содержатся два целых числа через пробел – координата $\ x_0\ $ точки появления капли $\ \left( 0 \lt x_0 \lt 10000\right)\ $ и количество отрезков-препятствий $\ N\ (0 \leqslant N \leqslant 100).\ $ Далее следует $\ N\ $ строк, каждая из которых содержит четыре разделенные пробелами числа $\ x_1,\ $ $\ y_1,\ $ $\ x_2,\ $ $\ y_2\ $ – координаты левого и правого концов отрезка-препятствия (все числа целые и находятся в диапазоне от $\ 0$\ до $\ 10000\ $, $\ x_1 \lt x_2,$ $y_1 \neq y_2.\ $ Отрезки не пересекаются и не соприкасаются.

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

В выходной файл вывести одно целое число – координату $\ x\ $ точки соприкосновения капли с землей.

Тесты

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

30 4 25 35 40 30 1 32 20 30 33 22 50 29 18 10 33 19	18
7 5 1 6 10 8 5 3 8 2 6 10 11 9 9 10 14 12 6 6 12 7	8
4 4 1 1 3 3 2 3 0 6 7 3 5 2 6 5 9 6	4
8 3 8 6 2 4 7 4 9 3 6 1 10 2	2
2 3 5 9998 0 10000 7 9996 11 9994 4 9996 9 9993	9

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

#include <iostream>
#include <cmath>
#include <vector>
#define MAX_Y 10000;
using namespace std;
struct slide {
    double x1;
    double y1;
    double x2;
    double y2;
};
//высота соприкосновения капли с крышей [ур-ние прямой по 2-м точкам]
double f (slide x, double x0) {
    double dx = x.x2 - x.x1;
    double dy = x.y2 - x.y1;
    return ((dy*(x0 - x.x1))/dx + x.y1);
}
vector <slide> roof; //вектор всех крыш
//считывание и заполнение данных
void read (int n) {
    while (n--) {
        double a, b, c, d;
        slide x;
        cin >> a >> b >> c >> d;
        if (a < c) {
            x.x1 = a;
            x.y1 = b;
            x.x2 = c;
            x.y2 = d;
        }
        else
        {
            x.x1 = c;
            x.y1 = d;
            x.x2 = a;
            x.y2 = b;
        }
        roof.push_back(x);
    }
}
int main() {
    int n, x, y = MAX_Y + 1;
    slide a;
    cin >> x >> n;
    if (n == 0) {
        cout << x;
        return 0;
    }
    read (n);
    while (roof.size()) {
        int index = -1;
        int value = -1; //предполагаемая высока соприкосновения капли со следующей крышей
        bool no_projection = true;
        for (int i = 0; i < roof.size(); i++) { //поиск самой высокой крыши в точке х
            if ((x <= roof[i].x2) and (x >= roof[i].x1)) { //капля проектируется на и-тую крышу?
                no_projection = false;
                if ((f(roof[i], x) > value) and (f(roof[i], x) < y)) { //и-тая крыша выше ранее найденной?
                    value = f(roof[i], x);
                    index = i;
                }
            }
            if (min(roof[i].y1, roof[i].y2) > y) {  //крыша целиком осталась выше?
                roof.erase(roof.begin() + i);
                i--;
            }
        }
        if ((roof.size() == 0) or (no_projection)) {  //если удалили все крыши или свободно падает на землю
            cout << x;
            return 0;
        }
        if (roof[index].y1 < roof[index].y2)  //какой конец крыши ниже?
            x = roof[index].x1;
        else
            x = roof[index].x2;
        y = min(roof[index].y1, roof[index].y2); //сохранили новую ординату
        roof.erase(roof.begin() + index);
    }
    cout << x;
    return 0;
}

#include <iostream>

#include <cmath>

#include <vector>

#define MAX_Y 10000;

using namespace std;

struct slide {

double x1;

double y1;

double x2;

double y2;

};

//высота соприкосновения капли с крышей [ур-ние прямой по 2-м точкам]

double f (slide x, double x0) {

double dx = x.x2 - x.x1;

double dy = x.y2 - x.y1;

return ((dy*(x0 - x.x1))/dx + x.y1);

}

vector <slide> roof; //вектор всех крыш

//считывание и заполнение данных

void read (int n) {

while (n--) {

double a, b, c, d;

slide x;

cin >> a >> b >> c >> d;

if (a < c) {

x.x1 = a;

x.y1 = b;

x.x2 = c;

x.y2 = d;

}

else

{

x.x1 = c;

x.y1 = d;

x.x2 = a;

x.y2 = b;

}

roof.push_back(x);

}

int main() {

int n, x, y = MAX_Y + 1;

slide a;

cin >> x >> n;

if (n == 0) {

cout << x;

return 0;

}

read (n);

while (roof.size()) {

int index = -1;

int value = -1; //предполагаемая высока соприкосновения капли со следующей крышей

bool no_projection = true;

for (int i = 0; i < roof.size(); i++) { //поиск самой высокой крыши в точке х

if ((x <= roof[i].x2) and (x >= roof[i].x1)) { //капля проектируется на и-тую крышу?

no_projection = false;

if ((f(roof[i], x) > value) and (f(roof[i], x) < y)) { //и-тая крыша выше ранее найденной?

value = f(roof[i], x);

index = i;

}

if (min(roof[i].y1, roof[i].y2) > y) { //крыша целиком осталась выше?

roof.erase(roof.begin() + i);

i--;

}

if ((roof.size() == 0) or (no_projection)) { //если удалили все крыши или свободно падает на землю

cout << x;

return 0;

}

if (roof[index].y1 < roof[index].y2) //какой конец крыши ниже?

x = roof[index].x1;

else

x = roof[index].x2;

y = min(roof[index].y1, roof[index].y2); //сохранили новую ординату

roof.erase(roof.begin() + index);

}

cout << x;

return 0;

}

Решение

Для удобства создадим структуру slide, которая будет описывать координаты концов отрезка-крыши. Также будем считать, что первый конец отрезка находится левее (для этого будем менять местами точки в случае необходимости).
Будем представлять каждую крышу как отрезок прямой на плоскости. Для этого применим уравнение прямой по двум точкам, принадлежащим этой прямой:
$$\frac{x — x_1}{x_2 — x1}=\frac{y — y_1}{y_2 — y_1}$$
Чтобы проверить, может ли капля в текущий момент проектироваться на некоторую крышу, надо проверить, находится ли абсцисса капли между абсциссами концов отрезка-крыши, а также найти ту крышу, которая в абсциссе капли «выше всех» (другими словами, у какой из прямых, которым принадлежат те отрезки, на которые проектируется капля, наибольшее значение ординаты в абсциссе капли). Для этого создадим функцию, которая и будет возвращать искомое значение ординаты. Также важно убедиться в том, что эта крыша находится ниже текущего положения капли. Заметим, что если некоторая крыша целиком находится выше капли, то мы на неё уже никогда не попадем, поэтому её нужно удалить из вектора. Найдя нужную крышу, определим новые координаты капли после того, как она скатится по этой крыше. Если капля в свободном падении и на её пути больше нет препятствий (крыш не осталось или нет такой, на которую проектируется капля), то текущая абсцисса капли и будет ответом на задачу.

Ссылки

Условие задачи на eolymp.com
Решение задачи на ideone.com

e-olymp 1619. Ограбление домов

23/06/2021 by Oleksandr.Ivanov

Задача

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

Зная количество денег в каждом доме, определите максимальную сумму, которую Вы сможете ограбить сегодня вечером без уведомления полиции.

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

Первая строка содержит количество домов $n (1 \leqslant n \leqslant 10^6)$. Вторая строка содержит n целых неотрицательных чисел $a_1, a_2, …, a_n$, где $a_i$ — количество денег, которое может быть вынесено из iго дома.

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

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

Тесты

№	Входные данные	Выходные данные
1	5 6 1 2 10 4	16
2	10 4 1 29 0 14 8 31 12 7 5	85
3	2 1 3	3

Код

#include <iostream>
 
using namespace std;
 
void houseRobbery(int houseCount, unsigned long *maxSum, unsigned long *initialHouses) {
    /*
    A function that, through dynamic programming, calculates the maximum production of houses not standing nearby.
    The function does not return anything, since it modifies arrays through pointers
    */
    
    // Initial state values from first two houses
    maxSum[0] = initialHouses[0];
    maxSum[1] = max(initialHouses[0], initialHouses[1]);
 
    // Since by condition it is given that we cannot rob two houses in a row, 
    // then we will take the maximum house of two: maxSum[i - 1] and maxSum[i - 2] + initialHouses[house] 
    // (where initialHouses[house] is the amount of money in the i-th house)
    for (int house = 2; house < houseCount; house += 1) {
        maxSum[house] = max(maxSum[house - 1], maxSum[house - 2] + initialHouses[house]);
    }
}
 
int main() {
    int houseCount;
    cin >> houseCount;

    // Initialize the arrays not containing negative values
    unsigned long initialHouses[houseCount], maxSum[houseCount];
 
    // Filling the initial array of houses with user input
    for (int element = 0; element < houseCount; element += 1) {
        cin >> initialHouses[element];
    }
    
    // Calling the function
    houseRobbery(houseCount, maxSum, initialHouses);
 
    cout << maxSum[houseCount - 1];
    return 0;
}

#include <iostream>

using namespace std;

void houseRobbery(int houseCount, unsigned long *maxSum, unsigned long *initialHouses) {

A function that, through dynamic programming, calculates the maximum production of houses not standing nearby.

The function does not return anything, since it modifies arrays through pointers

// Initial state values from first two houses

maxSum[0] = initialHouses[0];

maxSum[1] = max(initialHouses[0], initialHouses[1]);

// Since by condition it is given that we cannot rob two houses in a row,

// then we will take the maximum house of two: maxSum[i - 1] and maxSum[i - 2] + initialHouses[house]

// (where initialHouses[house] is the amount of money in the i-th house)

for (int house = 2; house < houseCount; house += 1) {

maxSum[house] = max(maxSum[house - 1], maxSum[house - 2] + initialHouses[house]);

}

int main() {

int houseCount;

cin >> houseCount;

// Initialize the arrays not containing negative values

unsigned long initialHouses[houseCount], maxSum[houseCount];

// Filling the initial array of houses with user input

for (int element = 0; element < houseCount; element += 1) {

cin >> initialHouses[element];

}

// Calling the function

houseRobbery(houseCount, maxSum, initialHouses);

cout << maxSum[houseCount - 1];

return 0;

}

Решение

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

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

Для решения данной задачи будет использовать метод последовательного вычисления (далее МПВ).
МПВ подходит, только если функция ссылается исключительно на элементы перед ней — это его основной минус.
Суть метода в следующем: необходимо создать массив на N элементов и последовательно заполнять его значениями. Таким образом вычисляется, в том числе те значения, которые для ответа не нужны. В значительной части задач на динамику этот факт можно опустить, так как для ответа часто бывают нужны как раз все значения.

Зная, что такое динамическое программирование и МПВ — можно описать алгоритм решения.
Пусть $a_i$ — количество денег в $i$-ом доме и houseRobbery(i) — максимальное количество денег, которое удалось унести грабителю.

Следовательно, значения начальных состояний будут такими:
— Для первого дома — количество денег в нем.
— Для второго — максимальное количество денег из первых двух домов.

Далее в цикле рассматривается $i$-й дом и определять для него $houseRobbery(i)$, где houseRobbery(i) — максимальное из houseRobbery(i - 1) и houseRobbery(i - 2) + initialHouses[i], так как нужно учитывать houseRobbery(i - 1), если $i$-й дом не был ограблен, а houseRobbery(i - 2) + initialHouses[i], если $i$-й дом — ограблен.

И так как используется МПВ, то последний элемент в заведенном массиве и будет решением этой задачи.

Ссылки

e-olymp 6975. Магический Множитель

19/06/2021 by Tychenko

Задача

Ельфійські раси Середзем’я вважали, що деякі числа є більш важливими, ніж інші. При використанні конкретного кількості $n$ металу для виплавки меча, вони вважають, що меч буде найбільш потужним, якщо його товщина $k$ обрана відповідно до наступного правила:

Визнач невід’ємне ціле число $n$. Знайти найменше $k$, для якого десяткове представлення чисел в послідовності

$n, 2n, 3n, 4n, 5n,\ldots, kn$

містить всі десять цифр (від $0$ до $9$) як мінімум один раз?

Лорд Елронд з Рівенделл доручив Вам розробити алгоритм, який знайде оптимальну товщину $k$ для будь-якого заданого кількості металу $n$.

Вхідні дані

Кожен рядок містить одне число $n$ $(1 \leqslant n \leqslant 200000000)$.

Вихідні дані

Для кожного тесту вивести в окремому рядку необхідне значення $k$ — таке що кожна цифра від $0$ до $9$ зустрічається хоча б один раз.

Тести

№	Вхідні дані	Вихідні дані
1	1 10 123456789 3141592	10 9 3 5
2	200000000	45

№

Вхідні дані

Вихідні дані

123456789

3141592

200000000

Код

#include <iostream>
using namespace std;
bool Cheking(bool arr[]) {
  bool q = true;
  for (int i = 0; i < 10; i++) if (arr[i] == false) q = false;
  if (q == false) return true;
  else return false;
}
void Filling(bool arr[], long a) {
  int b;
  while (a > 0) {
    b = a % 10;
    arr[b] = (bool)1;
    a = (a - b) / 10;
  }
}
int main() {
  long n, k;
  bool arr[10];
  while (cin >> n) {
    k = 0;
    for (int i = 0; i < 10; i++) arr[i] = 0;
    while (Cheking(arr)) {
      k++;
      Filling(arr, k * n);
    }
    cout << k << '\n';
  }
}

#include <iostream>

using namespace std;

bool Cheking(bool arr[]) {

bool q = true;

for (int i = 0; i < 10; i++) if (arr[i] == false) q = false;

if (q == false) return true;

else return false;

}

void Filling(bool arr[], long a) {

int b;

while (a > 0) {

b = a % 10;

arr[b] = (bool)1;

a = (a - b) / 10;

}

int main() {

long n, k;

bool arr[10];

while (cin >> n) {

k = 0;

for (int i = 0; i < 10; i++) arr[i] = 0;

while (Cheking(arr)) {

k++;

Filling(arr, k * n);

}

cout << k << '\n';

}

Рішення

Для знаходження числа $k$ треба всі отриманні цифри (від $0$ до $9$), які зустрічаються в числовій послідовності $n, 2n, 3n, 4n, 5n,\ldots, kn$, відзначати як знайдені. Для цього було використано масив з $10$ елементів, де поіндексово (відповідно до цифри) відзначалася знайденна цифра, яка зустрічалося в числовій послідовності хоча б один раз. Пошук числа $k$ здійнувався за допомогою циклу, де методом поступового збільшення $k$, здійснювалася перевірка числа. Перевірка рахувалося успішною і завершувала цикл, якщо в масиві було відзначено всі цифри. В разі неуспішної перевірки цикл продовжувався.

Посилання

Задача на e-olymp.
Код рішення на Replit.
Код рішення на Ideone.

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

16/03/2021 by Verheles Vladyslav

Задача

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

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

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

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

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

Тесты

№	Входные данные	Выходные данные
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

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
Засчитанное решение

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
Засчитанное решение

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 7023. Тасование Ханафуда

11/12/2020 by Михайло Будіш

Задача

Есть несколько способов, чтобы перетасовать колоду карт. Одним из таких примеров является перетасовка для японской карточной игры «Ханафуда». Ниже показано, как ее выполнить.

Имеется колода из $n$ карт. Начиная с $p$-ой карты сверху, $c$ карт вынимаются и кладутся на вершину колоды, как показано на рисунке. Такую операцию назовем операциею срезки.

Напишите программу, которая моделирует перетасовку Ханафуда, и выведет номер карты, которая в конце будет находиться наверху.

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

Состоит из нескольких тестов. Каждый тест начинается со строки, содержащей два натуральных числа $n$ $(1 ≤ n ≤ 50)$ и $r$ $(1 ≤ r ≤ 50)$ — количество карт в колоде и количество операций срезания.

Каждая из следующих $r$ строк описывает операцию срезания. Они выполняются в перечисленном порядке. Каждая строка содержит два натуральных числа $p$ и $c$ $(p + c ≤ n + 1)$. Начиная с $p$-ой карты сверху, c карт вытаскиваются и кладутся наверх.

Последняя строка содержит два нуля.

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

Для каждого теста вывести в отдельной строке номер верхней карты после выполнения тасования. Считайте, что сначала карты пронумерованы числами от $1$ до $n$ снизу доверху.

Тесты

№	Входные данные	Выходные данные
1	5 2 3 1 3 1 10 3 1 10 10 1 8 3 0 0	4 4

Код

#include <iostream>
#include <string>
 
using namespace std;
 
struct Comma {
    int num, pos;
    Comma() {
        num = 0;
        pos = 0;
    }
};
 
int main() {
    int n, r;
    while(cin >> n >> r) {
        int p, c;
        string s;
        // Filling the array with cards' numbers separated by comma
        for (int i = n; i > 0; i--) s += (i == 1 ? to_string(1) : to_string(i) + ",");
        if (n > 0) {
            for (int i = 0; i < r; i++) {
                cin >> p >> c;
                // Create object with number of comma in string and its position
                Comma comma1, comma2;
                int s_len = s.length();
                if (p != 1) {
                    // -------- Looking for indexes of needed commas to pick 'c' cards
                    for (int j = 0; j < s_len; j++) {
                        if (comma1.num == p-1) {
                            comma1.pos = j;
                            comma1.num = 0;
                        }
                        if (comma2.num == p+c-1) {
                            comma2.pos = j;
                            comma2.num = 0;
                        }
                        if (comma1.pos == 0 && s[j] == ',') comma1.num += 1;
                        if (comma2.pos == 0 && s[j] == ',') comma2.num += 1;
                    }
                    // ---------------------------------------------------------------
 
 
                    // --------- Swapping cards ---------
                    string s1 = s.substr(comma1.pos, comma2.pos - comma1.pos);
                    s.erase(comma1.pos, comma2.pos - comma1.pos);
                    if (s1[s1.length()-1] != ',') s = s1 + ',' + s;
                    else s = s1 + s;
                    // ----------------------------------
                }
            }
            int k = 0;
            while (s[k] != ',') k++;
            string res = s.substr(0, k);
            cout << res << "\n";
        }
    }
}

#include <iostream>

#include <string>

using namespace std;

struct Comma {

int num, pos;

Comma() {

num = 0;

pos = 0;

}

};

int main() {

int n, r;

while(cin >> n >> r) {

int p, c;

string s;

// Filling the array with cards' numbers separated by comma

for (int i = n; i > 0; i--) s += (i == 1 ? to_string(1) : to_string(i) + ",");

if (n > 0) {

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

cin >> p >> c;

// Create object with number of comma in string and its position

Comma comma1, comma2;

int s_len = s.length();

if (p != 1) {

// -------- Looking for indexes of needed commas to pick 'c' cards

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

if (comma1.num == p-1) {

comma1.pos = j;

comma1.num = 0;

}

if (comma2.num == p+c-1) {

comma2.pos = j;

comma2.num = 0;

}

if (comma1.pos == 0 && s[j] == ',') comma1.num += 1;

if (comma2.pos == 0 && s[j] == ',') comma2.num += 1;

}

// ---------------------------------------------------------------

// --------- Swapping cards ---------

string s1 = s.substr(comma1.pos, comma2.pos - comma1.pos);

s.erase(comma1.pos, comma2.pos - comma1.pos);

if (s1[s1.length()-1] != ',') s = s1 + ',' + s;

else s = s1 + s;

// ----------------------------------

}

int k = 0;

while (s[k] != ',') k++;

string res = s.substr(0, k);

cout << res << "\n";

}

Решение

Решить данную задачу можно несколькими способами. Первая мысль, которая мне пришла в голову — поместить все числа в строку и совершать тасование с помощью методов работы со строками, такими как $erase$ и $substr$. В течении решения стало понятно, что просто записывать числа в строку будет неправильно, так как возможны и двузначные числа. Так как неизвестно какое число будет следующим (однозначное или двузначное), особенно после нескольких перестановок, появляется идея хранить в строке числа, разделенные между собой запятыми. И в дальнейшем, если мне понадобится вытащить 5 карт из колоды начиная с 17, то я дойду до 16 запятой и возьму все, что хранится после нее, до 17+5 запятой и переставлю эти числа в начало строки (наверх колоды). Также в процессе поиска позиции необходимой запятой мне нужно получить ее позицию в строке, поэтому я решил создать структуру $Comma$, которая будет хранить номер запятой в строке и ее позицию относительно всех символов в данной строке, чтобы использовать ее во время каждой перестановки.

Таким образом, получаем рабочее решение данной задачи.

P.S. Новые решения согласно советам преподавателя

#include <iostream>
#include <string>

using namespace std;

int main() {
    int n, r;
    while(cin >> n >> r) {
        int p, c;
        string s;
        for (int i = n; i > 0; i--) s += (char)i;
        if (n > 0) {
            for (int i = 0; i < r; i++) {
                cin >> p >> c;
                if (p != 1) {
                    string s1 = s.substr(p-1, c);
                    s.erase(p-1, c);
                    s = s1 + s;
                }
            }
            cout << (int)s[0] << "\n";
        }
    }
}

#include <iostream>

#include <string>

using namespace std;

int main() {

int n, r;

while(cin >> n >> r) {

int p, c;

string s;

for (int i = n; i > 0; i--) s += (char)i;

if (n > 0) {

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

cin >> p >> c;

if (p != 1) {

string s1 = s.substr(p-1, c);

s.erase(p-1, c);

s = s1 + s;

}

cout << (int)s[0] << "\n";

}

#include <iostream>

using namespace std;

struct Card {
    int number;
    Card *next;
    Card(int num, Card *nxt = 0) {
        number = num;
        next = nxt;
    };
};

int main() {
    int n, r;
    Card *top_card = 0;
    while(cin >> n >> r) {
        int p, c;
        for (int i = 1; i <= n; i++) {
            top_card = new Card(i, top_card);
        };
        if (n > 0) {
            for (int i = 0; i < r; i++) {
                cin >> p >> c;
                if (p != 1) {
                    Card *first_moving = 0, *last_moving = 0, *last_before_moving = top_card;
                    for (int j = 1; j < p - 1; j++) {
                        last_before_moving = last_before_moving->next;
                    }
                    first_moving = last_before_moving->next;
                    last_moving = first_moving;

                    for (int j = 1; j < c; j++) {
                        last_moving = last_moving->next;
                    }
                    last_before_moving->next = last_moving->next;
                    last_moving->next = top_card;
                    top_card = first_moving;
                }
            }
            cout << top_card->number << "\n";
        }
    }
}

#include <iostream>

using namespace std;

struct Card {

int number;

Card *next;

Card(int num, Card *nxt = 0) {

number = num;

next = nxt;

};

int main() {

int n, r;

Card *top_card = 0;

while(cin >> n >> r) {

int p, c;

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

top_card = new Card(i, top_card);

};

if (n > 0) {

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

cin >> p >> c;

if (p != 1) {

Card *first_moving = 0, *last_moving = 0, *last_before_moving = top_card;

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

last_before_moving = last_before_moving->next;

}

first_moving = last_before_moving->next;

last_moving = first_moving;

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

last_moving = last_moving->next;

}

last_before_moving->next = last_moving->next;

last_moving->next = top_card;

top_card = first_moving;

}

cout << top_card->number << "\n";

}

Ссылки

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

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

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() , которая генерирует следующую лексиграфическую перестановку в диапазоне элементов.