OCPC2021. Задача F. Электрик наносит ответный удар (код решения)

20/01/2024 by Александр Мармалюк

Условие

В заведении «Покосившийся Скворечник» главврач экономит на зарплате системного администратора, поэтому эту должность в свободное от уколов время занимает электрик Геннадий из палаты номер 404. На сегодняшнем дежурстве одна из розеток внезапно заговорила с Геннадием и посулила тому суперспособности, если он её раскрутит. Результатом их общения, однако, стал лишь удар тока по нерадивому электрику, и теперь Геннадий задумал месть: он устроит лживой розетке Очень Длинное Замыкание!

Дата-центр «Покосившегося Скворечника» устроен следующим образом: помимо разной аппаратуры, из стены в ряд торчат 2∙n коннекторов: это n штепселей и n розеток. Геннадий планирует разбить их на пары розетка-штепсель и соединить каждую пару одним проводом таким образом, что штепсель всегда находится левее соответствующей розетки – эту идею ему навеяли правила средневекового этикета. Чтобы замыкание было Очень Длинным, Геннадий хочет, чтобы суммарная длина проводов, использованных для его коварного замысла, была максимально возможной. Помогите ему! Ну, или не мешайте хотя бы, и просто подскажите, провод какой длины он должен отрезать от соседней линии электропередач, чтобы распилить его на столь нужные ему провода.

Первая строка ввода содержит целое число $n$ $(2 \leqslant n \leqslant 1000).$ Вторая строка содержит n целых чисел – координаты штепселей слева направо. Третья строка содержит n чисел – координаты розеток слева направо. Все числа во второй и третьей строках различны и находятся в диапазоне от $0$ до $10^5$.

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

Тесты

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

2 1 4 6 8	9
2 1 4 2 5	2
4 2 5 6 9 3 7 12 22	22
3 2 3 4 12 13 17	33

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

#include <iostream>
using namespace std;
int main() {
    int n, res = 0;
    cin >> n;
    for (int tmp, i = 0; i < n; i++) {
        cin >> tmp;
        res -= tmp;
    }
    for (int tmp, i = 0; i < n; i++) {
        cin >> tmp;
        res += tmp;
    }
    cout << res;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, res = 0;

cin >> n;

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

cin >> tmp;

res -= tmp;

}

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

cin >> tmp;

res += tmp;

}

cout << res;

return 0;

}

Решение

Обратим внимание на то, что оптимальным будет решение подключать $i$-й штепсель к $i$-й розетке. В условии задачи сказано, что существует хотя бы один способ подключить все коннекторы так, чтобы соблюсти средневековое правило этикета. Значит, последовательно подключая самый левый свободный штепсель в самую левую свободную розетку (а поскольку коннекторы изначально упорядочены, это и значит $i$-й штепсель в $i$-й розетку), мы удовлетворим правило этикета. Теперь покажем, что суммарная длина проводов в любом другом подключении не меньше. Предположим, мы подключили $i$-й штепсель в $j$-ю розетку (и это первый случай подключения штепселя не на «свое» место). Поскольку все предыдущие розетки, если они есть, уже заняты, $j \gt i$. Если можно подключить $j$-й штепсель в $i$-ю розетку (т.е. $j$-й штепсель левее $i$-й розетки), то суммарная длина проводов не изменится. Если же $j$-й штепсель правее $i$-й розетки, то чтобы иметь возможность его подключить, надо переподключить штепсели между $i$-м и $j$-м (надо заметить, что такая возможность не гарантирована). В результате этого мы сэкономим провода на не более, чем расстояние между $i$-й розеткой и $j$-м штепселем. Но поскольку $k$-я розетка, в которую мы подключим $j$-й штепсель, обязательно правее самого штепселя, то суммарная длина проводов нового подключения будет больше исходной как минимум на расстояние между $k$-й розеткой и $j$-м штепселем, поскольку этот фрагмент провода «дублируется» подключением $i$-го штепселя в $j$-ю розетку.

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

Решение задачи на ideone.com

Ссылка на контест

Related Images:

e-olymp 1679. Честная цепочка

19/12/2020 by Максим Ливитчук

Условие

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

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

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

В единственной строке задается последовательность камней в исходной цепочке: символ E обозначает изумруд, символ R — рубин. Количество символов в строке не превышает $500000$.

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

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

Тесты

№	ввод	вывод
1	REER	3
2	REERREER	12
3	RRRRRRRR	0
4	EREREERERERREREREEERERERERERRREREREERERERERE	273
5	REEERREE	7

Код

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

int main() {
    int cnt = 0;
    char buf;
    map<int, long long> mp;
    mp[0] = 1;
    while(cin >>buf) {
        if(buf=='R')
            cnt++;
        else
            cnt--;
        mp[cnt]++;
    }
    long long answer = 0;
    for(auto e: mp) {
        answer += e.second*(e.second-1)/2;
    }
    cout <<answer;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

int cnt = 0;

char buf;

map<int, long long> mp;

mp[0] = 1;

while(cin >>buf) {

if(buf=='R')

cnt++;

else

cnt--;

mp[cnt]++;

}

long long answer = 0;

for(auto e: mp) {

answer += e.second*(e.second-1)/2;

}

cout <<answer;

}

Компактный код

#include 
#include <map>
using namespace std;
 
int main() {
    int cnt = 0;
    char buf;
    map mp;
    mp[0] = 1;
    while(cin >>buf) mp[buf=='R'?++cnt:--cnt]++;
    long long a = 0;
    for(auto e: mp) a += e.second*(e.second-1)/2;
    cout <<a;
}

#include

#include <map>

using namespace std;

int main() {

int cnt = 0;

char buf;

map mp;

mp[0] = 1;

while(cin >>buf) mp[buf=='R'?++cnt:--cnt]++;

long long a = 0;

for(auto e: mp) a += e.second*(e.second-1)/2;

cout <<a;

}

Решение

Составим массив из $n+1$ чисел, каждое из которых будет располагаться в месте возможного начала или конца фрагмента цепочки, который гномы должны вручить богине. Число в самом начале цепочки возьмём равным $0$, а все следующие числа будут представлять из себя количество R минус количество E, встречающихся в фрагменте с начала до этого числа.

Наглядный пример такого массива для пятого примера (подписан как cnt)

На таком массиве наглядно видно, что правильным фрагментом будет любой, начинающийся и кончающийся одинаковым числом, ведь это значит что между этими числами равное количество как R($+1$), так и E($-1$), которые сокращаются.

Выделенные в том же примере фрагменты с началом и концом в 0 и -2

Так как нам не важны конкретные правильные фрагменты, а только их суммарное количество, нам будет достаточно знать, сколько раз в массиве встречается то или иное число. В коде эту информацию хранит ассоциативная таблица mp. Запись mp[cnt]++; создаёт новый равный нулю элемент по ключу cnt, если раньше в структуре его не было, после чего инкрементирует значение.
Сам же массив воспроизводится на ходу из ввода, в переменной cnt. В конце программы количество фрагментов считается как сумма $\frac{n(n-1)}{2}$, где $n$ — mp[i] для всех встречавшихся в массиве чисел.

Ссылки

Related Images:

e-olymp 7213. Шашка на кубе

12/12/2020 by Максим Ливитчук

Условие

Поверхность куба отрезками, параллельными рёбрам куба, разделена на квадратные клетки, длина сторон которых в $l$ (нечетное натуральное число) раз меньше длины ребра куба. Шашку передвигают за один ход из клетки на произвольную смежную с ней клетку (что имеет с данной общую сторону).

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

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

Содержит натуральные числа $l$ и $m$ ($l < 52$, $m < 200$).

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

Вывести искомое количество способов.

Тесты

l	m	вывод
3	3	1
3	4	0
3	5	25
51	199	4009263689513240276071196173369495212494629453793821392879244551766927964742684514532573281589075237363501397360
3	199	11954860546705755218324706261555627152268568460810054501274297031890136116190373877274924800908756150285132065690107399

Код

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

#define cr(a, b, x, y) case a: return CellCoord{b, x, y}
#define SIDENUM 3 //количество сторон куба которые хранятся
#define MAX_L 51 //максимальное значение L

#define BASE 1000000000 //10^9, основание системы счисления для длинной арифметики 
#define DNUM 9 //количество цифр 10-ичной системы счисления в 1 "цифре" длинной арифметики

struct LongNum {
    //реализация длинной арифметики на векторах со сложением и выводом
    vector<int> v;
    LongNum() {} //стандартный конструктор
    LongNum(int s) { //конструктор из int
        v.push_back(s);
    }
    void print() { //вывод числа
        cout <<(v.empty() ? 0 : v.back());
        for (int i = (int)v.size() - 2; i>=0; i--)
            cout <<setfill('0') <<setw(DNUM) <<v[i];
    }
    void add(LongNum term) { //прибавление длинного числа
        auto b = term.v;
        int carry = 0;
        for (size_t i = 0; i < max(v.size(), b.size()) || carry; i++) {
            if (i == v.size())
                v.push_back(0);
            v[i] += carry + (i < b.size() ? b[i] : 0);
            carry = v[i] >= BASE;
            if (carry)  v[i] -= BASE;
        }
    }
};

struct CellCoord {
    //хранит данные о положении клетки
    short side;
    short x, y;
};

struct CellNeighbors {
    //хранит данные о положении всех(4) соседей определённой клетки
    CellCoord n[4];
};

CellCoord FixNeighbor(short l, short side, short x, short y) {
    //исправляет данные о положении клетки, если она выходит за края грани
    if(x == -1) { //если сосед находится левее грани
        switch(side) {
        //если координаты выходят за левую границу 0-ой грани - меняет грань на 1-ую,
        //обнуляя y, а в x записывает старый y 
        cr(0, 1, y,     0); //и так далее
        cr(1, 1, l-1,   y);
        cr(2, 1, l-y-1, l-1);
        }
    } else if(x == l) {//правее
        switch(side) {
        cr(0, 1, l-y-1, 0);
        cr(1, 1, 0,     y);
        cr(2, 1, y,     l-1);
        }
    } else if(y == -1) {//выше
        switch(side) {
        cr(0, 1, l-x-1, 0);
        cr(1, 0, x,     l-1);
        cr(2, 1, x,     l-1);
        }
    } else if(y == l) {//ниже
        switch(side) {
        cr(0, 1, x,     0);
        cr(1, 2, x,     0);
        cr(2, 1, l-x-1, l-1);
        }
    } else {
        // если координаты не вышли за границы грани просто возвращаем неизменёные координаты
        return CellCoord{side, x, y};
    }
}

CellNeighbors GetNeighbors(short l, short side, short x, short y) {
    //возвращает исправленные координаты всех(4) соседних клеток
    return CellNeighbors{{
        FixNeighbor(l, side, x-1, y),
        FixNeighbor(l, side, x+1, y),
        FixNeighbor(l, side, x, y-1),
        FixNeighbor(l, side, x, y+1)
    }};
}

int main() {
    short l, m;
    bool flag = false;
    cin >>l >>m;
    LongNum cubes[2][SIDENUM][MAX_L][MAX_L];

    cubes[0][0][l/2][l/2] = LongNum(1);
    //за 0 ходов можно дойти 1 путём в изначальную точку

    CellNeighbors nbs[SIDENUM][MAX_L][MAX_L];
    //массив координат соседей

    for(short side=0; side<SIDENUM; side++) {
        for(short xi=0; xi<l; xi++) {
            for(short yi=0; yi<l; yi++) { //перебор координат всех клеток
                nbs[side][xi][yi] = GetNeighbors(l, side, xi, yi);
                //кэш координат соседних клеток
            }
        }
    }

    for(short i=0; i<m; i++) {
        for(short side=0; side<SIDENUM; side++) {
            for(short xi=0; xi<l; xi++) {
                for(short yi=0; yi<l; yi++) { //перебор всех клеток
                    LongNum neighbor_sum;
                    for(auto e: nbs[side][xi][yi].n) { //перебор всех соседей
                        neighbor_sum.add(cubes[flag][e.side][e.x][e.y]);
                        //сложение количества путей ко всем соседям на предыдущем шаге
                    }
                    cubes[!flag][side][xi][yi] = neighbor_sum;
                    //запись получившейся суммы в клетку
                }
            }
        }
        flag = !flag; //замена местами массива для предыдущего шага и нынешнего
    }
    cubes[flag][1][l/2][l/2].print();
    //вывод количества путей к центру соседней грани на m-ом шаге
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include <iostream>

#include <iomanip>

#include <vector>

using namespace std;

#define cr(a, b, x, y) case a: return CellCoord{b, x, y}

#define SIDENUM 3 //количество сторон куба которые хранятся

#define MAX_L 51 //максимальное значение L

#define BASE 1000000000 //10^9, основание системы счисления для длинной арифметики

#define DNUM 9 //количество цифр 10-ичной системы счисления в 1 "цифре" длинной арифметики

struct LongNum {

//реализация длинной арифметики на векторах со сложением и выводом

vector<int> v;

LongNum() {} //стандартный конструктор

LongNum(int s) { //конструктор из int

v.push_back(s);

}

void print() { //вывод числа

cout <<(v.empty() ? 0 : v.back());

for (int i = (int)v.size() - 2; i>=0; i--)

cout <<setfill('0') <<setw(DNUM) <<v[i];

}

void add(LongNum term) { //прибавление длинного числа

auto b = term.v;

int carry = 0;

for (size_t i = 0; i < max(v.size(), b.size()) || carry; i++) {

if (i == v.size())

v.push_back(0);

v[i] += carry + (i < b.size() ? b[i] : 0);

carry = v[i] >= BASE;

if (carry) v[i] -= BASE;

}

};

struct CellCoord {

//хранит данные о положении клетки

short side;

short x, y;

};

struct CellNeighbors {

//хранит данные о положении всех(4) соседей определённой клетки

CellCoord n[4];

};

CellCoord FixNeighbor(short l, short side, short x, short y) {

//исправляет данные о положении клетки, если она выходит за края грани

if(x == -1) { //если сосед находится левее грани

switch(side) {

//если координаты выходят за левую границу 0-ой грани - меняет грань на 1-ую,

//обнуляя y, а в x записывает старый y

cr(0, 1, y, 0); //и так далее

cr(1, 1, l-1, y);

cr(2, 1, l-y-1, l-1);

}

} else if(x == l) {//правее

switch(side) {

cr(0, 1, l-y-1, 0);

cr(1, 1, 0, y);

cr(2, 1, y, l-1);

}

} else if(y == -1) {//выше

switch(side) {

cr(0, 1, l-x-1, 0);

cr(1, 0, x, l-1);

cr(2, 1, x, l-1);

}

} else if(y == l) {//ниже

switch(side) {

cr(0, 1, x, 0);

cr(1, 2, x, 0);

cr(2, 1, l-x-1, l-1);

}

} else {

// если координаты не вышли за границы грани просто возвращаем неизменёные координаты

return CellCoord{side, x, y};

}

CellNeighbors GetNeighbors(short l, short side, short x, short y) {

//возвращает исправленные координаты всех(4) соседних клеток

return CellNeighbors{{

FixNeighbor(l, side, x-1, y),

FixNeighbor(l, side, x+1, y),

FixNeighbor(l, side, x, y-1),

FixNeighbor(l, side, x, y+1)

}};

}

int main() {

short l, m;

bool flag = false;

cin >>l >>m;

LongNum cubes[2][SIDENUM][MAX_L][MAX_L];

cubes[0][0][l/2][l/2] = LongNum(1);

//за 0 ходов можно дойти 1 путём в изначальную точку

CellNeighbors nbs[SIDENUM][MAX_L][MAX_L];

//массив координат соседей

for(short side=0; side<SIDENUM; side++) {

for(short xi=0; xi<l; xi++) {

for(short yi=0; yi<l; yi++) { //перебор координат всех клеток

nbs[side][xi][yi] = GetNeighbors(l, side, xi, yi);

//кэш координат соседних клеток

}

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

for(short side=0; side<SIDENUM; side++) {

for(short xi=0; xi<l; xi++) {

for(short yi=0; yi<l; yi++) { //перебор всех клеток

LongNum neighbor_sum;

for(auto e: nbs[side][xi][yi].n) { //перебор всех соседей

neighbor_sum.add(cubes[flag][e.side][e.x][e.y]);

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

}

cubes[!flag][side][xi][yi] = neighbor_sum;

//запись получившейся суммы в клетку

}

flag = !flag; //замена местами массива для предыдущего шага и нынешнего

}

cubes[flag][1][l/2][l/2].print();

//вывод количества путей к центру соседней грани на m-ом шаге

}

Решение

Из условия можно понять, что задача про специфического вида граф, по которому движется шашка. Его вершинами являются клетки на гранях куба, а дуги лежат между клетками с общими границами. Очевидно количество путей за $m$ шагов до любой точки в графе будет равняться сумме количества путей за $m-1$ шагов ко всем соседним вершинам, то есть мы можем получать решение задачи для $m$ шагов из решения меньшей задачи для $m-1$ шагов, из чего можно понять что это задача на динамическое программирование.
Для решения создадим массив со всеми вершинами и будем хранить в нём количество путей к каждой из них на i-ом шаге. Удобнее всего задать такой массив как 6 числовых матриц размером $ l \times l$, по одной на каждую грань куба.

Раскладка шести граней куба с переходами между границами

Соседство будем определять, прибавляя или отнимая единицу от одной из координат клетки в матрице, например $(x-1, y)$ всегда будет соседом $(x, y)$, не считая крайних случаев, когда $x-1$ будет меньше нуля. Такие ситуации в коде обрабатывает функция FixNeighbor(...), в которой прописаны все подобные крайние случаи.

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

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

Оптимизированный вариант хранения куба

Так как для получения значения клетки через $i$ шагов нужны значения всех её соседей через $i-1$ шагов, а для получения значения соседей через $i$ шагов нужно значение клетки через $i-1$ шагов, нам не хватит только одного массива для перезаписи, надо использовать минимум два для хранения предыдущего и нынешнего состояния. В программе это реализовано с помощью булевой переменной flag — сначала мы вычисляем следующее состояние на основании 0-ого массива ( flag), записывая результат 1-ый ( !flag), а потом инвертируем значение переменной на противоположное и массивы в алгоритме меняются местами.

Ссылки

Related Images:

e-olymp 8546. Найдите сумму

21/12/2019 by Никита Рудь

Задача

По заданному натуральному числу $n$ вычислите сумму

$\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+ … +\frac{1}{n\cdot(n+1)}$

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

Одно натуральное число $n$ ($n$ $⩽$ $1000$).

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

Выведите сумму с $6$ десятичными знаками.

Тесты

№	Входные данные	Выходные данные
1	1	0.500000
2	5	0.833333
3	12	0.923077

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

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

int main() {
    int n;
    double sum = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        sum += 1. / (i * (i + 1));
    }
    cout << fixed << setprecision(6) << sum;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

int n;

double sum = 0;

cin >> n;

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

sum += 1. / (i * (i + 1));

}

cout << fixed << setprecision(6) << sum;

}

Решение

Для вычисления данной суммы необходимо сложить $n$ слагаемых вида

$\frac{1}{i \cdot (i + 1)}$

начиная с $i = 1$ и с шагом в единицу до $i = n$.

Ссылки

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

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

Related Images:

e-olymp 8671. Представимые суммой квадратов

15/12/2019 by Алина Зозуля

Задача

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

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

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

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

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

Тесты

№	Входные данные	Выходные данные
1	5	5
2	10	5 10
3	13	5 10 13
4	20	5 10 13 17 20
5	30	5 10 13 17 20 25 26 29

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

#include <iostream>
#include <cmath>
using namespace std;
bool check(int n)
{
    
    for (int i = 1; i * i < n; i++) // перебор всех i
    {   
        double j = sqrt (n - i * i);
        if ((j == floor(j)) and (j != i)) // проверка j целое или дробное 
            {
                return true; // комбинация найдена - возвращаем true
            }
    } 
    return false; // комбинация не найдена - возвращаем false
}
int main() {
    int n;
    cin >> n; // считываем число, до которого будем искать
    for (int k = 5; k <= n; k++) // проверка для каждого k
        if (check(k))
            cout << k << " ";
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

bool check(int n)

{

for (int i = 1; i * i < n; i++) // перебор всех i

{

double j = sqrt (n - i * i);

if ((j == floor(j)) and (j != i)) // проверка j целое или дробное

{

return true; // комбинация найдена - возвращаем true

}

return false; // комбинация не найдена - возвращаем false

}

int main() {

int n;

cin >> n; // считываем число, до которого будем искать

for (int k = 5; k <= n; k++) // проверка для каждого k

if (check(k))

cout << k << " ";

return 0;

}

Решение

Для решения задачи создадим функцию check(), которая будет возвращать $true$, если число можно представить в виде суммы двух квадратов или же $false$, если нельзя. В функции перебираем всевозможные варианты $i$ и считаем $j$ для каждого $i$ по формуле $j=\sqrt{n-i^2}$, до тех пор пока не найдем целое (не равное $i$ ) $j$ или же не переберем все $i$. Просматриваем до $ i \cdot i < n $, потому что сумма двух квадратов не может превышать заданного числа. Формулу получили выразив $j$ из исходной формулы $(i^2+j^2=n)$.

Ссылки

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

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

Related Images:

e-olymp 9405. Профессор и шары

06/12/2019 by Алина Малыхина

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

Для праздника Профессор купил голубые, красные и жёлтые воздушные шары. Всего $n$ штук. Жёлтых и голубых вместе — $a$. Красных и голубых — $b$ штук.

Сколько голубых, красных и жёлтых шаров купил Профессор?

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

Три натуральных числа $n$, $a$, $b$.

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

В одной строке выведите количество голубых, красных и жёлтых шаров, которые купил Профессор.

Тесты

№	Входные данные	Выходные данные
1	10 6 8	4 4 2
2	12 8 10	6 4 2
3	14 10 12	8 4 2
4	16 14 12	10 2 4

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

#include <iostream>
using namespace std;

int main()
{
    int n, a, b, blue, yellow, red; 
    cin >> n >> a >> b; 
    blue = b + a - n; //считаем кол-во синих шаров
    red = b - blue; //считаем кол-во красных шаров
    yellow = a - blue; //считаем кол-во жёлтых шаров
    cout << blue <<" "<< red <<" "<< yellow; 
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n, a, b, blue, yellow, red;

cin >> n >> a >> b;

blue = b + a - n; //считаем кол-во синих шаров

red = b - blue; //считаем кол-во красных шаров

yellow = a - blue; //считаем кол-во жёлтых шаров

cout << blue <<" "<< red <<" "<< yellow;

return 0;

}

Решение

Для решения задачи необходимо вывести формулу для вычисления количества жёлтых ($y$), синих ($u$) и красных ($r$) шаров. Из условия имеем, что:

$$\left.\begin{matrix}
&u&+&y&=a&\\
&r&+&u&=b&\\
&r&+&u&+&y&=n&
\end{matrix}\right\}$$

Выразим $r$ и $y$ через $u$:

$$\left.\begin{matrix}
r=&b&-&u&\\
y=&a&-&u&
\end{matrix}\right\}$$

Подставим эти значения в формулу $r+u+y=n$:

$n=b-u+u+a-u$

$u$ и $-u$ взаимоуничтожатся и мы получим, что:

$n=a+b-u$

Теперь выведем формулу для вычисления количества синих шаров:

$u=b+a-n$

Ссылки

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

Related Images:

e-olymp 682. Сумма на отрезке

30/05/2019 by Никита Пушкин

Задача

Задан набор чисел $a_{1}, …, a_{n}$. Для заданных индексов $l$ и $r$ найдите $$S_{l,r}=a_{l}+a_{l+1}+..+a_{r}$$

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

В первой строке записано количество чисел $n$ $\left(1 \leq n \leq 10^{6}\right)$. Во второй строке записаны числа $a_{i}$ $\left(1 \leq a_{i} \leq 1000\right)$, разделенные пробелом. На третьей строке записано число $m$ $\left(1 \leq m \leq 10^{6}\right)$ — количество запросов. Далее на отдельных строках записаны сами запросы $l_{i}$ и $r_{i}$ $\left(1 \leq l_{i} \leq r_{i} \leq n\right)$.

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

Выведите в отдельных строках $m$ чисел $S_{l_i,r_i}$.

Тесты

#	Входные данные	Выходные данные
1	5 1 2 3 4 5 5 1 5 2 3 3 4 2 5 1 4	15 5 7 14 10
2	10 10 10 10 10 10 10 10 10 10 10 5 1 3 3 5 5 7 7 9 3 7	30 30 30 30 50
3	10 57 42 24 73 98 71 65 76 12 33 7 1 2 4 5 8 10 1 10 7 10 2 5 3 8	99 171 121 551 186 237 407
4	3 10 15 20 2 1 2 1 3	25 45
5	7 299 38924 2388 4399 7549 79475 57947 10 1 3 2 3 3 3 4 7 6 7 3 5 5 5 6 6 1 6 1 7	41611 41312 2388 149370 137422 14336 7549 79475 133034 190981

#include <iostream>
 
using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    long long a[n];
    for (int i = 0; i < n; i++) {
        cin>>a[i];
    }
    long long summ[n + 1];
    summ[0] = 0;
    for (int i = 1; i < n + 1; i++) {
        summ[i] = summ[i - 1] + a[i - 1];
    }
    int m;
    cin>>m;
    while (m--) {
        int l, r;
        cin>>l>>r;
        printf("%d", summ[r] - summ[l - 1]);
        printf("%s", "\n");
    }
}

#include <iostream>

using namespace std;

int main() {

std::ios::sync_with_stdio(false);

int n;

cin>>n;

long long a[n];

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

cin>>a[i];

}

long long summ[n + 1];

summ[0] = 0;

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

summ[i] = summ[i - 1] + a[i - 1];

}

int m;

cin>>m;

while (m--) {

int l, r;

cin>>l>>r;

printf("%d", summ[r] - summ[l - 1]);

printf("%s", "\n");

}

Решение

Сначала читаем с клавиатуры набор $n$ чисел и добавляем их в массив $a\left[n\right]$. Далее создаем массив $summ$ из $n+1$ элементов, $i$-ый элемент которого равен сумме всех элементов $a$ до $i-1$ включительно. Затем $m$ раз считываем $l$ и $r$ с клавиатуры, и отнимаем от $summ\left[r\right]$ «хвост» в виде суммы элементов до $l-1$ элемента.

Условие задачи можно найти на e-olymp
Код решения — ideone

Related Images:

e-olymp 913. Используй подпрограмму

01/04/2019 by Никита Пушкин

Задача

Вычислить сумму и произведение $n$ пар заданных вещественных чисел, воспользовавшись подпрограммой $SumDob$ для вычисления суммы и произведения двух вещественных чисел.

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

В первой строке задано натуральное число $n$ — количество пар чисел. В последующих $n$ строках через пробел задано по $2$ вещественных числа. Все входные данные по модулю не превышают $100$.

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

В $n$ строках вывести через пробел по два числа: сначала сумму, а потом произведение очередной пары чисел. Результат выводить с точностью $4$ знака после десятичной точки.

Тесты

#	Входные данные	Выходные данные
1	2 6 7.5 2.1 2.0	13.5000 45.0000 4.1000 4.2000
2	4 2 5 3 5 4 5 5 5	7.0000 10.0000 8.0000 15.0000 9.0000 20.0000 10.0000 25.0000
3	2 100 100 56 65	200.0000 10000.0000 121.0000 3640.0000
4	6 10 10 20 20 40 40 50 50 70 70 80 80	20.0000 100.0000 40.0000 400.0000 80.0000 1600.0000 100.0000 2500.0000 140.0000 4900.0000 160.0000 6400.0000
5	1 2 2	4 4

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

pair<double, double> SumDob (double a, double b){
    return make_pair(a + b, a * b);
}
 
int main() {
    int n;
    cin>>n;
    while (n--){
        double a, b;
        cin>>a>>b;
        cout<<fixed<<setprecision(4)<<SumDob(a,b).first<<" "<<SumDob(a,b).second<<endl;
    }
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

pair<double, double> SumDob (double a, double b){

return make_pair(a + b, a * b);

}

int main() {

int n;

cin>>n;

while (n--){

double a, b;

cin>>a>>b;

cout<<fixed<<setprecision(4)<<SumDob(a,b).first<<" "<<SumDob(a,b).second<<endl;

}

return 0;

}

Решение

Как и было указано в условии задачи, при решении задачи использовалась подпрограмма $SumDob$, которая возвращает сумму и произведение двух вещественных чисел $a$ и $b$. Потом мы с помощью цикла выводим пару чисел, полученных из подпрограммы $SumDob$ $n$ раз с $n$ пар введенных значений.

Условие задачи можно найти на e-olymp
Код решения — ideone

Related Images:

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

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

Задача

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

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

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

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

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

Тесты

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

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

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

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

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

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

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

cin >> n;

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

cin >> x;

if (x > 0) {

s += x;

k++;

}

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

else cout << "Not Found";

return 0;

}

Решение

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

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

#include <iostream>
#include <iomanip>

using namespace std;

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

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

int n, k = 0;

double x, s = 0;

cin >> n;

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

cin >> x;

if (x > 0) {

s += x;

k++;

}

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

string str = to_string(s);

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

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

return 0;

}

Решение

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

Ссылки

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

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

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

Related Images:

e-olymp 1485. Серия степеней матриц

26/01/2019 by Инна Литвиненко

Задача

По заданной матрице A размера n×n и положительному целому значению $k$ вычислить сумму $S = A + A^2+ A^3 + … + A^k.$

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

Первая строка содержит три положительных целых числа $n (n ≤ 30)$, $k (k ≤ 10^9)$ и $m (m < 10^4)$. Каждая из следующих $n$ строк содержит $n$ неотрицательных целых чисел меньших $32768$, задающих элементы матрицы $A$ в порядке возрастания строк.

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

Вывести элементы матрицы $S$ по модулю $m$ в таком же виде как и входная матрица $A$.

Тесты

№	Ввод	Вывод
1	2 2 4 0 1 1 1	1 2 2 3
2	4 7 2 3 5 12 10 8 9 2 16 7	1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0
3	5 10 78 7 6 0 1 6 12 9 1 1 8 1 1 3 1 9 8 5 34 1 7 5 5 5 5 5	2 67 36 32 48 2 6 10 49 65 67 14 58 4 29 64 54 33 45 46 41 4 50 8 55
4	3 2 4 3 3 3 3 3 3 3 3 3	2 2 2 2 2 2 2 2 2
5	5 100 1000 1846 4675 8090 4539 1234 4567 7453 9564 6548 1111 5674 9876 5432 1010 1515 0 478 3 11 0 68303 7777 32767 14 8008	614 7 945 925 381 22 332 981 689 527 351 627 130 686 420 340 628 819 758 629 913 426 396 871 91

Код

#include <iostream>
using namespace std;

struct matrix {
    int mat[31][31];
};

long n, m;
matrix E; //единичная матрица

matrix mul(matrix A, matrix B) {
    matrix C;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            C.mat[i][j] = 0;
            for (int v = 0; v < n; v++)
                C.mat[i][j] += A.mat[i][v] * B.mat[v][j] % m;
        }
    return C;
}

matrix sum(matrix A, matrix B) { 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            A.mat[i][j] += B.mat[i][j] % m;
    return A;
}

matrix power(matrix A, int k) { 
    if (k == 1)
        return A;
    matrix B = power(A, k / 2);
    B = mul(B, B);
    if (k % 2 != 0)
        B = mul(B, A);
    return B;
}

matrix res(matrix A, int k) {
    if (k == 1)
        return A;
    if (k % 2 == 0) {
        matrix B = res(A, k / 2);
        return mul(sum(power(A, k / 2), E), B);
    }
    else {
        matrix B = res(A, k / 2);
        matrix C = power(A, (k + 1) / 2);
        return sum(C, mul(B, sum(C, E)));
    }
}

int main() {
    long long k;
    matrix A;
    cin >> n >> k >> m;
    for (int i = 0; i < n; i++) {
        E.mat[i][i] = 1;
        for (int j = 0; j < n; j++) 
            cin >> A.mat[i][j];
    }
    matrix ans = res(A, k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
           if (j != 0)
                cout << " ";
            cout << ans.mat[i][j] % m;
        }
        cout << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

struct matrix {

int mat[31][31];

};

long n, m;

matrix E; //единичная матрица

matrix mul(matrix A, matrix B) {

matrix C;

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

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

C.mat[i][j] = 0;

for (int v = 0; v < n; v++)

C.mat[i][j] += A.mat[i][v] * B.mat[v][j] % m;

}

return C;

}

matrix sum(matrix A, matrix B) {

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

for (int j = 0; j < n; j++)

A.mat[i][j] += B.mat[i][j] % m;

return A;

}

matrix power(matrix A, int k) {

if (k == 1)

return A;

matrix B = power(A, k / 2);

B = mul(B, B);

if (k % 2 != 0)

B = mul(B, A);

return B;

}

matrix res(matrix A, int k) {

if (k == 1)

return A;

if (k % 2 == 0) {

matrix B = res(A, k / 2);

return mul(sum(power(A, k / 2), E), B);

}

else {

matrix B = res(A, k / 2);

matrix C = power(A, (k + 1) / 2);

return sum(C, mul(B, sum(C, E)));

}

int main() {

long long k;

matrix A;

cin >> n >> k >> m;

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

E.mat[i][i] = 1;

for (int j = 0; j < n; j++)

cin >> A.mat[i][j];

}

matrix ans = res(A, k);

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

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

if (j != 0)

cout << " ";

cout << ans.mat[i][j] % m;

}

cout << "\n";

}

return 0;

}

Решение

Для решения данной задачи опишем матрицу как структуру и функциями зададим простейшие операции над матрицами — сложение и умножение. Результат обеих функций будем будем брать по модулю $m$, чтоб уменьшить числа, с которыми работаем.

Далее создадим функцию быстрого возведения в степень. $A^k$ представим как $\left(A^2\right)^\frac{k}{2}$ при четном $k$ и $A × \left(A^2\right)^{\frac{k — 1}{2}}$ в противном случае. Такой алгоритм позволяет значительно уменьшить количество умножений.

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

Все, что еще необходимо сделать — вывести результат по модулю $m$.

Замечание

Тесты на e-olymp требуют отсутствия пробела после последнего столбца.

Ссылки

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

Код задачи на Ideone

Related Images:

e-olymp 919. Номер на 3

24/01/2019 by Лиза Севастьянова

Задача

Условие

Задана последовательность действительных чисел $a_{1}$, $a_{2}$,…, $a_{n}$. Определить сумму и количество положительных элементов, индексы которых делятся на $3$ без остатка.

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

В первой строке задано количество элементов $n$ ($n \leq 100$) в последовательности. В следующей строке находится $n$ вещественных чисел, значение каждого из которых по модулю не превышает $100$.

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

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

Тесты

№	Входные данные	Выходные данные
1	6 6 7.5 2.1 2.0 0 -3	1 2.10
2	3 12 0.33 -14	0 0.00
3	1 -3.4	0 0.00
4	12 0 15.3 -1 144 0.333 17.5 -69 456 2.5 0 3 13	3 33.00

Решение

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

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

#include <iostream>
#include <iomanip> // для setprecision()
using namespace std;

int main() {
    int n; // количество элементов последовательности
    cin >> n;
    int num = 0; // счётчик количества выбранных элементов
    double sum = 0; // сумма выбранных элементов
    for (int i = 1; i <= n; i++) { // цикл для просмотра всех элементов последовательности
        double a; // элемент последовательности
        cin >> a;
        if ((i%3) == 0 and a > 0) { // проверка на соответствие условиям
            num++;
            sum += a;
        }
    }
    cout << num << " " << fixed << setprecision(2) << sum << endl;
    return 0;
}

#include <iostream>

#include <iomanip> // для setprecision()

using namespace std;

int main() {

int n; // количество элементов последовательности

cin >> n;

int num = 0; // счётчик количества выбранных элементов

double sum = 0; // сумма выбранных элементов

for (int i = 1; i <= n; i++) { // цикл для просмотра всех элементов последовательности

double a; // элемент последовательности

cin >> a;

if ((i%3) == 0 and a > 0) { // проверка на соответствие условиям

num++;

sum += a;

}

cout << num << " " << fixed << setprecision(2) << sum << endl;

return 0;

}

Ссылки

Related Images:

e-olymp 908. Те, что делятся на 6

26/12/2018 by Евгений Рудницкий

Задача: Те, что делятся на 6

Для [latex]N[/latex] целых чисел определить сумму и количество положительных чисел, которые делятся на 6 без остатка.

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

В первой строке задано количество чисел [latex]N[/latex]$\left(1 \leq N \leq 100\right)$, в следующей строке через пробел заданы сами числа, значения которых по модулю не превышают $10000$.

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

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

Тесты

Ввод	Вывод
3 12 15 18	2 30
4 -10 -15 42 -24	1 42
2 6 0	1 6
3 -6 -12 -32	0 0

Решение

Заводим 2 переменные: сумму и количество. Каждый раз, когда мы читаем число, проверяем положительно ли оно и делится ли на 6 (Обычно желательно сначала проверять наимение вероятное условие, т.к. программа реже будет лишний раз проверять второе условие и, как следствие, сделает меньше действий, но в этой задачи это особой роли не играет из-за малого ввода), если оба условия выполняются, добавляем к счетчику 1, а к сумме введенное число. По окончанию ввода выводим сумму и количество через пробел.

#include <iostream>
using namespace std;

int main() {
  int n, q, s, a;
  cin >> n;
  s = 0;
  q = 0;
  for (int i = 0; i < n; i++) {
    cin >> a;
    if ((a % 6 == 0) && (a > 0)) {
      q++;
      s += a;
    }
  }
  cout << q << ' ' << s << endl;
}

#include <iostream>

using namespace std;

int main() {

int n, q, s, a;

cin >> n;

s = 0;

q = 0;

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

cin >> a;

if ((a % 6 == 0) && (a > 0)) {

q++;

s += a;

}

cout << q << ' ' << s << endl;

}

Ссылки

Related Images:

e-olymp 8653. Прибавить вычесть и умножить

22/12/2018 by Николь Метри

Задача

Пусть x — переменная, изначально равная 0. Промоделируйте выполнение следующих операций над ней:

add a: прибавить значение a к x;
subtract a: вычесть значение a из x;
multiply a: умножить x на a;

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

Каждая строка содержит операцию и значение. Промоделируйте все операции. Значение переменной x при выполнении каждой операции не превышает по модулю $10^9$.

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

Выведите результирующее значение переменной x.

Тесты

№	Ввод	Вывод
1	add 2 subtract 5 subtract 1 multiply -3	12
2	subtract 5 multiply -5 add 5	30
3	add 6 add 543 multiply 23	12627
4	multiply 45678 add 3	3
5	subtract 58 add 38 multiply -1 add 100	120

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

#include <iostream>
using namespace std;

int main() {
    int x = 0, a;
    string s;
    while (cin >> s){
        cin >> a;
        if (s == "multiply") {
            x*=a;
        }
        else if (s == "subtract") {
            x-=a;
        }
        else {
            x+=a;
        }
    }
    cout << x;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x = 0, a;

string s;

while (cin >> s){

cin >> a;

if (s == "multiply") {

x*=a;

}

else if (s == "subtract") {

x-=a;

}

else {

x+=a;

}

cout << x;

return 0;

}

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

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

Ссылки

Related Images:

e-olymp 8519. Сумма четных цифр

21/11/2018 by Алина Гук

Задача взята с сайта e-olymp.

Задача

Задано длинное число. Найти сумму его четных цифр.

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

Одно натуральное число $n (n ≤ 10^{100} )$.

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

Вывести сумму четных цифр числа $n$.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	2345	6
2	3458937487534533459	32
3	888888888888888888888888888888	240

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

#include <iostream>
using namespace std;

int main() {
    char c; 
    int sum = 0;
    while(cin >> c) 
        if((c - '0') % 2 == 0) 
            sum += (c - '0');
    cout << sum << '\n';
    return 0;
}

#include <iostream>

using namespace std;

int main() {

char c;

int sum = 0;

while(cin >> c)

if((c - '0') % 2 == 0)

sum += (c - '0');

cout << sum << '\n';

return 0;

}

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

Переменная c — является переменной типа char, что означает, что cin в этом случае будет считывать по одному символу с потока. По этой причине, чтобы решить данную задачу, нужно считывать заданное число с помощью cin в цикле while до тех пор, пока происходит ввод данных с клавиатуры. Проверяя каждую цифру введенного числа на четность, будем прибавлять четные к переменной sum.
Для работы с символом c как с числом, будем писать c - '0'.

Ссылки

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

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

Related Images:

Сумма делителей — 2

12/07/2018 by Алиса Ворохта

Задача

Профессор из тридевятого царства решил, что посчитать сумму делителей числа $n$ до $10^{10}$ сможет любой троечник, поэтому усложнил для Кости задачу, дав числа с большим количеством цифр. Но наш герой не хотел сдаваться, уж больно он хотел стать отличником.
Костя очень просит Вас помочь ему в этом деле, ведь он помнит, как успешно Вы справились с предыдущей задачей.

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

Одно целое число $n \left(1 \leqslant n < 10^{15}\right).$

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

Выведите сумму делителей числа $n.$

Тесты

Входные данные	Выходные данные
$100000000000031$	$100000000000032$
$10000019$	$10000020$
$400001520001444$	$700002730002667$
$9$	$13$
$304250263527210$	$1281001468723200$
$94083986096100$	$457766517350961$
$1234567898765$	$1517681442816$
$100000000000000$	$249992370597277$
$562949953421312$	$1125899906842623$
$81795$	$161280$
$9999999999999$	$14903272088640$
$997$	$998$
$1325$	$1674$
$2468013$	$3290688$
$951641320$	$2447078400$
$71675429738641$	$71695352830464$
$1100000000033$	$1200000000048$
$6300088$	$11859480$
$98$	$171$
$9102837465$	$15799834440$

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

#include <iostream>
#include <map>
using namespace std;
int main ()
{
    long long n, sumOfDivisors = 1;
    cin >> n;
    map<long long, long long> primeDivInPow;
    for(long long i = 2; i * i <= n; i++){
        while(n % i == 0){
            if(primeDivInPow.find(i) == primeDivInPow.end()){
                primeDivInPow[i] = 1;
            }
            primeDivInPow[i] *= i;
            n /= i;
        }
    }
    if(n != 1){
        primeDivInPow[n] = n;
    }
    for(map<long long, long long>::iterator p = primeDivInPow.begin(); p != primeDivInPow.end(); p++){
        sumOfDivisors *= (p -> second - 1) / (p -> first - 1) + p -> second;
    }
    cout << sumOfDivisors;
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main ()

{

long long n, sumOfDivisors = 1;

cin >> n;

map<long long, long long> primeDivInPow;

for(long long i = 2; i * i <= n; i++){

while(n % i == 0){

if(primeDivInPow.find(i) == primeDivInPow.end()){

primeDivInPow[i] = 1;

}

primeDivInPow[i] *= i;

n /= i;

}

if(n != 1){

primeDivInPow[n] = n;

}

for(map<long long, long long>::iterator p = primeDivInPow.begin(); p != primeDivInPow.end(); p++){

sumOfDivisors *= (p -> second - 1) / (p -> first - 1) + p -> second;

}

cout << sumOfDivisors;

return 0;

}

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

Пусть $n$ имеет каноническое разложение $n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots p_k^{\alpha_k},$ где $p_1 < p_2 < \ldots <p_k$ — простые делители числа $n$, $\alpha_1, \alpha_2,\ldots, \alpha_k \in \mathbb {N}$. Тогда сумма натуральных делителей числа $n$ равна $\sigma\left(n\right) = \left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\times$$\times\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right).$
Доказательство.
Рассмотрим произведение:
$\left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right)$
Если раскрыть скобки, то получим сумму членов ряда:
$p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_k^{\beta_k},$ где $0\leqslant\beta_m\leqslant\alpha_m \left(m = 1, 2, \ldots, k\right)$
Но такие члены являются делителями $n$, причем каждый делитель входит в сумму только один раз. Поэтому рассмотренное нами произведение равно сумме всех делителей $n,$ т.е. равно $\sigma\left(n\right).$ Итак, $\sigma\left(n\right)$ можно вычислить по нашей формуле. С другой стороны, каждая сумма $1 + p_m + p_m^2+\ldots+p_m^{\alpha_m}$ является суммой геометрической прогрессии с первым членом $1$ и знаменателем $p_m$. Поэтому иначе данную формулу можно переписать так:
$$\sigma\left(n\right) = \frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdot\ldots\cdot\frac{p_k^{\alpha_k+1}-1}{p_k-1}.$$
Для того, чтобы не вычислять $p_k^{\alpha_k+1}$, перепишем данную формулу в следующем виде:
$$\sigma\left(n\right) = \left(\frac{p_1^{\alpha_1}-1}{p_1-1}+p_1^{\alpha_1}\right)\cdot\left(\frac{p_2^{\alpha_2}-1}{p_2-1}+p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(\frac{p_k^{\alpha_k}-1}{p_k-1}+p_k^{\alpha_k}\right).$$

Ссылки

Код решения

Related Images:

Сумма делителей

11/07/2018 by Алиса Ворохта

Задача

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

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

Одно целое число $n \left(1 \leqslant n < 10^{10}\right).$

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

Выведите сумму делителей числа $n.$

Тесты

Входные данные	Выходные данные
$12$	$28$
$239$	$240$
$1234$	$1854$
$6$	$12$
$1000000007$	$1000000008$
$44100$	$160797$
$223092870$	$836075520$
$2147483648$	$4294967295$
$678906$	$1471002$
$1111111$	$1116000$
$9876543210$	$27278469036$
$99460729$	$99470703$
$5988$	$14000$
$1$	$1$
$1348781387$	$1617960960$
$135792$	$406224$
$5402250$	$17041284$
$375844500$	$1259767236$
$1000000000$	$2497558338$
$2357947691$	$2593742460$

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

#include <iostream>
#include <map>
using namespace std;
int main ()
{
    long long n, sumOfDivisors = 1;
    cin >> n;
    map<long long, long long> primeDivInPow;
    for(long long i = 2; i * i <= n; i++){
        while(n % i == 0){
            if(primeDivInPow.find(i) == primeDivInPow.end()){
                primeDivInPow[i] = 1;
            }
            primeDivInPow[i] *= i;
            n /= i;
        }
    }
    if(n != 1){
        primeDivInPow[n] = n;
    }
    for(map<long long, long long>::iterator p = primeDivInPow.begin(); p != primeDivInPow.end(); p++){
        sumOfDivisors *= (p -> second * p -> first - 1) / (p ->first - 1);
    }
    cout << sumOfDivisors;
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main ()

{

long long n, sumOfDivisors = 1;

cin >> n;

map<long long, long long> primeDivInPow;

for(long long i = 2; i * i <= n; i++){

while(n % i == 0){

if(primeDivInPow.find(i) == primeDivInPow.end()){

primeDivInPow[i] = 1;

}

primeDivInPow[i] *= i;

n /= i;

}

if(n != 1){

primeDivInPow[n] = n;

}

for(map<long long, long long>::iterator p = primeDivInPow.begin(); p != primeDivInPow.end(); p++){

sumOfDivisors *= (p -> second * p -> first - 1) / (p ->first - 1);

}

cout << sumOfDivisors;

return 0;

}

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

Ссылки

Код решения

Related Images:

e-olymp 1128. Проблема Лонги

14/05/2018 by Алиса Ворохта

Задача

Лонги хорошо разбирается в математике, он любит задумываться над трудными математическими задачами, которые могут быть решены при помощи некоторых изящных алгоритмов. И вот такая задачка возникла:
Дано целое число [latex]n[/latex] [latex](1 < n < 231)[/latex], Вы должны вычислить [latex]\sum\limits_{i=1}^n gcd [/latex] для всех [latex] 1 ≤ i ≤ n[/latex].
"О, я знаю, я знаю!" — воскликнул Лонги! А знаете ли Вы? Пожалуйста, решите её.

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

Каждая строка содержит одно число [latex]n[/latex].

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

Для каждого значения [latex]n[/latex] следует вывести в отдельной строке сумму [latex]\sum\limits_{i=1}^n gcd [/latex] для всех [latex] 1 ≤ i ≤ n[/latex].

Тесты

Входные данные	Выходные данные
[latex]2[/latex] [latex]6[/latex]	$3$ $15$
[latex]1[/latex] [latex]50[/latex] [latex]100[/latex]	$1$ $195$ $520$
[latex]7[/latex] [latex]4791[/latex] [latex]12345678[/latex] [latex]478900[/latex]	$13$ $15965$ $170994915$ $4980040$
[latex]123[/latex] [latex]7777[/latex] [latex]157423949[/latex] [latex]904573[/latex] $2147483648$	$405$ $54873$ $613124817$ $1809145$ $35433480192$

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

#include <iostream>
using namespace std;
 
int main() {
    long long n, gcd, primeNumInPow, power;
    while(cin >> n)
    {
        gcd = 1;
        for(long long i = 2; i * i <= n; i++) {
            if(n % i == 0) {
                power = 0; primeNumInPow = 1;
                while(n % i == 0) {
                    power++;
                    primeNumInPow *= i;
                    n /= i;
                }
                gcd *= (power + 1)*primeNumInPow - power*primeNumInPow/i;
            }
        }       
        if (n > 1) gcd *= (2*n - 1);
        cout << gcd << endl;
    }
  return 0;
}

#include <iostream>

using namespace std;

int main() {

long long n, gcd, primeNumInPow, power;

while(cin >> n)

{

gcd = 1;

for(long long i = 2; i * i <= n; i++) {

if(n % i == 0) {

power = 0; primeNumInPow = 1;

while(n % i == 0) {

power++;

primeNumInPow *= i;

n /= i;

}

gcd *= (power + 1)*primeNumInPow - power*primeNumInPow/i;

}

if (n > 1) gcd *= (2*n - 1);

cout << gcd << endl;

}

return 0;

}

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

Согласно свойству НОД, если некоторые числа [latex]a_1[/latex] и [latex]a_2[/latex] взаимно просты, то [latex]\gcd \left(a_1 \cdot a_2, c\right) = \gcd \left(a_1, c\right) \cdot \gcd \left(a_2, c\right)[/latex], где [latex]c[/latex] — некоторая константа. Если же вместо [latex]c[/latex] взять [latex]i[/latex] ([latex] 1 ≤ i ≤ a_1 \cdot a_2[/latex]) и просуммировать по [latex]i[/latex] обе части равенства, получим:
[latex]\sum\limits_{i=1}^{a_1 \cdot a_2} \gcd \left(a_1 \cdot a_2, i\right) = \sum\limits_{i=1}^{a_1 \cdot a_2} \left(\gcd \left(a_1, i\right) \cdot \gcd \left(a_2, i\right)\right) = \sum\limits_{i=1}^{a_1} \gcd \left(a_1, i\right) \cdot \sum\limits_{i=1}^{a_2} \gcd \left(a_2, i\right)[/latex].
Значит мы можем данное число представить как произведение простых в некоторых степенях. Эти числа, очевидно, будут взаимно простыми, из чего следует возможность применения данного свойства и последующего суммирования по [latex]i[/latex].
Теперь докажем, что для любого простого числа [latex]p[/latex] в степени [latex]a\geqslant 1[/latex] верно следующее равенство:
[latex]\sum\limits_{i=1}^{p^a} \gcd\left(p^a, i\right) = \left(a + 1\right)\cdot p^a — a \cdot p^{a-1} [/latex].
Обозначим $\sum\limits_{i=1}^{r} \gcd\left(r, i\right)$ как $g\left(r\right)$.
База индукции:
[latex]a = 1[/latex]:
$$g\left(p\right) = \gcd\left(p, 1\right) + \gcd\left(p, 2\right) + \ldots + \gcd\left(p, p\right) = \left(p — 1 \right) + p = 2 \cdot p — 1.$$
Если [latex]a = 2[/latex]:
$$g\left(p^{2}\right) = \gcd\left(p^{2}, 1\right) + \gcd\left(p^{2}, 2\right) + \ldots + \gcd\left(p^{2}, p\right) + \gcd\left(p^{2}, p + 1\right) + \ldots + \\ + \gcd\left(p^{2}, 2 \cdot p\right) + \ldots + \gcd\left(p^{2}, p^{2}\right) = 1 + 1 + \ldots + p + 1 + \ldots + p + \ldots + p^{2} = \\ = \left( p^{2} — p \right) + p \cdot \left( p — 1 \right) + p^{2} = 3 \cdot p^{2} — 2\cdot p.$$
Для любых $a \geqslant 2$:
$$g\left(p^{a}\right) = \sum\limits_{j=1}^{p^{a-1}} \gcd\left(p^a, j\right) + \sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a, j\right) + p^{a} =g\left(p^{a — 1}\right) + p^{a} + \\ + \sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a — 1, j\right).$$
Причем:
$$\sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a — 1, j\right) = \sum\limits_{j=1}^{p^{a} — p^{a-1} — 1} \gcd\left(p^{a — 1}, j\right) = \\ = \sum\limits_{j=1}^{p^{a} — p^{a-1}} \gcd\left(p^{a — 1}, j\right) — p^{a — 1} = \left( p — 1\right)\cdot g\left(p^{a-1}\right) — p^{a-1}.$$
Откуда следует:
$$g\left(p^{a}\right) = p^{a} — p^{a-1} + p\cdot g\left(p^{a-1}\right).$$
Предположение индукции:
Пусть [latex]a = b[/latex]:
$$g\left(p^{b}\right) = \left(b + 1\right) \cdot p^b — b \cdot p^{b-1}.$$
Шаг индукции:
Пусть [latex]a = b + 1[/latex]:
$$g\left(p^{b + 1}\right) = p^{b + 1} — p^{b} + p\cdot g\left(p^{b}\right) = p^{b + 1} — p^{b} + p\cdot \left[\left(b+1\right) \cdot p^{b} + b\cdot p^{b-1}\right] = \\ = \left(b + 2\right)\cdot p^{b+1} — \left(b + 1\right)\cdot p^{b}.$$

Ссылки

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

Related Images:

e-olymp 520. Сумма всех

26/12/2017 by Даниил Крутоголов

Сумма всех

Вычислите сумму всех заданных чисел.

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

Содержит [latex]n[/latex] [latex] (1 ≤ n ≤ 10^5) [/latex] целых чисел. Все числа не превосходят [latex]10^9[/latex] по абсолютной величине.

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

Выведите сумму всех заданных чисел.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]2[/latex] [latex]4[/latex]	[latex]6[/latex]
2	[latex]3[/latex]	[latex]3[/latex]
3	[latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]2[/latex] [latex]1[/latex]	[latex]9[/latex]
4	[latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]4[/latex]	[latex]10[/latex]
5	[latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]0[/latex]	[latex]0[/latex]

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

#include <iostream>
 
using namespace std;
 
int main() {
    long x;
    long sum = 0;
    while (cin >> x){
        sum+= x;
    }
    cout << sum;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long x;

long sum = 0;

while (cin >> x){

sum+= x;

}

cout << sum;

return 0;

}

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

Пользователь вводит числа до тех пор, пока программа не завершит работу. Как только это случается, программа выдаёт ответ в виде суммы всех ранее введённых чисел. Также, стоит использовать переменную типа long из-за того, что сумма чисел может быть довольно большой и явно превышать максимальное допустимое значение для переменной типа int.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

Related Images:

e-olymp 1000. Задача a + b

20/12/2017 by Александра Рябова

Задача

Вычислите сумму [latex]\textbf {a + b}[/latex].

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

В каждой строке задано два целых числа [latex]\textbf{a}[/latex] и [latex]\textbf{b}[/latex] ([latex] \bigl| \textbf {a} \bigr|, \bigl| \textbf {b} \bigr| \textbf {≤ 30000}[/latex]).

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

Для каждого теста выведите сумму [latex]\textbf {a + b}[/latex] в отдельной строке.

Тесты

Входные данные	Выходные данные
$4$ $8$ $5$ $0$ $-6$ $8$	$12$ $5$ $2$
$-3$ $3$	$0$
$12$ $8$ $10$ $10$	$20$ $20$
$30000$ $30000$ $3000$ $3000$ $300$ $300$ $30$ $30$ $3$ $3$	$60000$ $6000$ $600$ $60$ $6$
$10$ $23$ $613$ $2$ $-200$ $300$	$33$ $615$ $100$

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

#include <iostream>
using namespace std;

int main() {
    int a, b;
    while (cin >> a >> b)
    {
        cout << a+b << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b;

while (cin >> a >> b)

{

cout << a+b << "\n";

}

return 0;

}

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

Пока вводятся пары чисел, они считываются и на экран выводится их сумма, затем курсор переходит на новую строку.

Ссылки

Условие задачи на сайте E-Olymp
Код решения задачи

Related Images:

e-olymp 542. Поставка содовой воды

13/12/2017 by Карина Миловская

Задача

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

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

Три целых неотрицательных числа [latex]e[/latex], [latex]f[/latex], [latex]c[/latex], где [latex]e[/latex] ([latex]e < 1000[/latex]) — количество пустых бутылок, имеющихся у Тима в начале дня, [latex]f[/latex] ([latex]f < 1000[/latex]) — количество пустых бутылок, найденных в течение дня, и [latex]c[/latex] ([latex]1 < c < 2000[/latex]) — количество пустых бутылок, необходимых для покупки новой бутылки.

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

Сколько бутылок содовой воды смог выпить Тим, когда его замучила жажда?

Тесты

Входные данные	Выходные данные
[latex]9[/latex] [latex]0[/latex] [latex]3[/latex]	[latex]4[/latex]
[latex]5[/latex] [latex]5[/latex] [latex]2[/latex]	[latex]9[/latex]
[latex]0[/latex] [latex]8[/latex] [latex]4[/latex]	[latex]2[/latex]
[latex]22[/latex] [latex]0[/latex] [latex]4[/latex]	[latex]7[/latex]

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

#include <iostream>
using namespace std;

int main() { 
    int e, f, c;
    cin >> e >> f >> c;
    cout << (int)((e + f)/(c - 1 + 0.0001));
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int e, f, c;

cin >> e >> f >> c;

cout << (int)((e + f)/(c - 1 + 0.0001));

return 0;

}

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

Можно считать, что изначально у Тима имеется [latex]e+f[/latex] пустых бутылок. Допустим, у него есть хотя бы [latex]c[/latex] бутылок, необходимых для покупки новой, Тим идет и меняет их на одну полную бутылку. Затем выпивает её, после чего общее количество пустых у него уменьшается на [latex]c-1[/latex]. То есть за [latex]e+f[/latex] пустых бутылок он сможет выпить [latex]\frac{e+f}{c-1}[/latex] бутылок содовой воды. Нам также следует добавить к [latex]c-1[/latex] маленькую константу [latex]a = 0.0001[/latex] для корректировки значения, чтобы в случае когда количество бутылок кратно [latex]c-1[/latex], Тиму нельзя было взять новую бутылку с недостающим количеством пустых бутылок для этого, следовательно, он должен выпить на одну бутылку меньше. В результате выводим целое число бутылок содовой воды, которые Тим смог выпить, когда его замучила жажда.

Ссылки

Условие задачи на e-olymp
Код решения на ideone