Category Archives: 3. Циклы

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

Циклы

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

Циклические, повторяющиеся много раз однотипные вычисления позволяют наилучшим образом продемонстрировать вычислительные возможности компьютеров. Ради этого их изначально и создавали. В задачах этого раздела желательно снова перечитать параграф 5.4 из праймера посвященный «итерационным операторам» (так они назвали семейство из нескольких операторов цикла). Часть 5.4.3 можете пока пропустить, поскольку мы еще не изучали структур данных для которых … Continue reading →

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

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

Цифры
Младший бит
Постоянная сумма цифр
Садовник
Большая точность
Дракон
Змей Горыныч
Уровень палиндромности
Нумерация
Битовое представление
Часы
Счастливые билеты
Роботы — сложная задача, предлагается всем желающим
Юный садовод
Максимум
Баксы в банке
Циклические сдвиги
Минимальная сумма цифр
Просто Фибоначчи
Превращение
Увеличить на 2
Двоичные числа
Интересное произведение
Кружок хорового пения
Очень просто!!!
Юные программисты
Коды Грея — только не перемудрите. Если выходит значительно больше 20 строчек кода,
то лучше остановиться и подумать.
Кубики — 3 —
используйте битовые операции для смены предположения о потере кубика для каждой из 52-х букв
Степень симметрии
Сколько можно?
«Зеркально простые» числа
Max — Min

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

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:

OCPC-2021. Задача B. Палиндромонойя (код решения)

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

Условие

Студент Илья, постоялец палаты номер 101 заведения «Покосившийся Скворечник», попавший сюда во время сессии на почве экзамена по программированию, убеждён, что его повсюду преследуют затаившиеся палиндромы. «Они среди нас! Как же вы этого не замечаете?!» – то и дело слышат от него нянечки Алла и Анна. По убеждению Ильи, палиндром – это слово, читающееся одинаково, как слева направо, так и справа налево. Если же на первый взгляд слово таковым не является, то студент не опускает рук и переносит буквы по одной из начала слова в конец, пока оно не станет палиндромом. Если из слова таким образом удалось получить палиндром за 0 или более операций, Илья называет его затаившимся палиндромом, после чего студент начинает бегать по потолку с воплями отчаяния, чем доставляет неудобства окружающим. Например, Илью может довести до исступления слово «масса», ведь из него можно получить «самас», перенеся 3 буквы из начала в конец. Главврач хочет выкинуть из палаты номер 101 Илью, но вместо этого выкинет все предметы, названия которых являются затаившимися палиндромами. Осталось только проверить их все, а здесь без программы не обойтись!

На ввод поступает строка, содержащая одно слово, длиной от 1 до 100 латинских строчных букв.

Выведите одну строку: «yes» без кавычек, если предмет с этим названием стоит выбросить и «no» без кавычек, если его стоит оставить в палате номер 101.

Тесты

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

array	yes
iliya	no
anna	yes
cbaabcb	yes
arrya	no
anana	yes
bcdcbaa	yes

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

#include <iostream>
#include <string>
using namespace std;
bool palindrome (string const *s) {
    for (int i = 0; i < (*s).size() / 2; ++i) {
        if ((*s)[i] != (*s)[(*s).size() - i - 1]) return false;
    }
    return true;
}
int main() {
    string s;
    cin >> s;
    for (int i = 0; i <= s.length(); i++) {
        s += s[0];
        s.erase(s.begin());
        if (palindrome(&s)) {
            cout << "yes";
            return 0;
        }
    }
    cout << "no";
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

bool palindrome (string const *s) {

for (int i = 0; i < (*s).size() / 2; ++i) {

if ((*s)[i] != (*s)[(*s).size() - i - 1]) return false;

}

return true;

}

int main() {

string s;

cin >> s;

for (int i = 0; i <= s.length(); i++) {

s += s[0];

s.erase(s.begin());

if (palindrome(&s)) {

cout << "yes";

return 0;

}

cout << "no";

return 0;

}

Решение №1

Проверять, является ли входное слово «затаившимся палиндромом» можно непосредственно перенося буквы из начала в конец и каждый раз проверяя, не стало ли слово палиндромом. Для удобства можно написать отдельную функцию, которая будет проверять, является ли слово палиндромом.

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

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

int main() {
    string s;
    cin >> s;
    int n = s.length();
    //дублируем строку, чтобы иметь возможность просмотреть все циклические перестановки
    s += s;
    const int p = 31;
    vector <long long> p_pow (2*n); //вектор степеней числа p
    p_pow[0] = 1;
    for (int i = 1; i < 2*n; ++i) p_pow[i] = p * p_pow[i-1];
    long long P1 = 0, P2 = 0;
    for (int i = 0; i < n; ++i) {
        P1 += (s[i] - 'a' + 1) * p_pow[i];
        P2 += (s[n - i - 1] - 'a' + 1) * p_pow[i];
    }
    if (P1 == P2) {
        bool check = true;
        for (int i = 0; i < n; ++i)
            if (s[i] != s[n - i - 1]) check = false;
        if (check) {
            cout << "yes";
            return 0;
        }
    }
    for (int i = 0; i < n; ++i) {
        P1 += (s[i+n] - 'a' + 1)*p_pow[i+n] - (s[i] - 'a' + 1)*p_pow[i];
        P2 = (P2 - (s[i] - 'a' + 1)*p_pow[n + i - 1]) * p_pow[2] + (s[i+n]-'a' + 1) * p_pow[i+1];
        if (P1 == P2) {
            bool check = true;
            for (int j = i + 1; j < i + 1 + n; ++j)
                if (s[j] != s[2*i + 1 + n - j]) check = false;
            if (check) {
                cout << "yes";
                return 0;
            }
        }
    }
    cout << "no";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

string s;

cin >> s;

int n = s.length();

//дублируем строку, чтобы иметь возможность просмотреть все циклические перестановки

s += s;

const int p = 31;

vector <long long> p_pow (2*n); //вектор степеней числа p

p_pow[0] = 1;

for (int i = 1; i < 2*n; ++i) p_pow[i] = p * p_pow[i-1];

long long P1 = 0, P2 = 0;

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

P1 += (s[i] - 'a' + 1) * p_pow[i];

P2 += (s[n - i - 1] - 'a' + 1) * p_pow[i];

}

if (P1 == P2) {

bool check = true;

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

if (s[i] != s[n - i - 1]) check = false;

if (check) {

cout << "yes";

return 0;

}

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

P1 += (s[i+n] - 'a' + 1)*p_pow[i+n] - (s[i] - 'a' + 1)*p_pow[i];

P2 = (P2 - (s[i] - 'a' + 1)*p_pow[n + i - 1]) * p_pow[2] + (s[i+n]-'a' + 1) * p_pow[i+1];

if (P1 == P2) {

bool check = true;

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

if (s[j] != s[2*i + 1 + n - j]) check = false;

if (check) {

cout << "yes";

return 0;

}

cout << "no";

return 0;

}

Решение №2

Для решения задачи можно воспользоваться техникой хеширования строк. Изначально продублируем строку, поскольку тогда все циклические перестановки исходной строки будут подстроками длины $n$ продублированной строки, где $n$ — длина исходной строки.
Можно сначала сравнить хеши исходного слова и «перевернутого» к нему. Далее будем строить значения полиномиальных хешей, умноженных на $p$ в соответствующей степени, всех следующих подстрок длины $n$ и «перевернутых» к ним.
Заметим, что вычислять значение хеша «перевернутой» строки можно без её копирования, поскольку отличается она от «прямой строки только тем, что степени числа $p$ умножаются на преобразованые коды соответствующих символов строки в обратном порядке. Поэтому для вычисления хеша следующей «перевернутой» подстроки надо вычесть из предыдущего значения элемент с наибольшей степенью числа $p$, домножить полученное значение на $ p^2 $, т.к. мы, с одной стороны, решили смещать края подстроки, для которой мы проверяем на палиндром, умножая её хеш на соответствующую степень числа $p$, а с другой — текущая предпоследняя степень должна стать последней (из-за того, что рассматривается перевёрнутая подстрока и новый символ к ней присоединяется «в начало»).

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

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

#include <iostream>
#include <vector>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = s.length();
    s += s;
    int len = s.length();
    vector <int> d (len);
    int l = 0, r = -1;
    if (n % 2) {
        for (int i = 0; i < len; ++i) {
            d[i] = (i > r)? 1 : min(d[l + r - i], r - i + 1);
            while (i - d[i] >= 0 and i + d[i] < len and s[i - d[i]] == s[i + d[i]])
                d[i]++;
            if (i + d[i] - 1 > r) {
                r = i + d[i] - 1;
                l = i - d[i] + 1;
            }
            if (r - l + 1 >= n) {
                cout << "yes";
                return 0;
            }
        }
    }
    else {
        for (int i = 0; i < len; ++i) {
            d[i] = (i > r)? 0 : min(d[l + r - i + 1], r - i + 1);
            while (i - d[i] - 1 >= 0 and i + d[i] < len and s[i - d[i] - 1] == s[i + d[i]])
                d[i]++;
                if (i + d[i] - 1 > r) {
                    r = i + d[i] - 1;
                    l = i - d[i];
                }
            if (r - l >= n) {
                cout << "yes";
                return 0;
            }
        }
    }
    cout << "no";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

string s;

cin >> s;

int n = s.length();

s += s;

int len = s.length();

vector <int> d (len);

int l = 0, r = -1;

if (n % 2) {

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

d[i] = (i > r)? 1 : min(d[l + r - i], r - i + 1);

while (i - d[i] >= 0 and i + d[i] < len and s[i - d[i]] == s[i + d[i]])

d[i]++;

if (i + d[i] - 1 > r) {

r = i + d[i] - 1;

l = i - d[i] + 1;

}

if (r - l + 1 >= n) {

cout << "yes";

return 0;

}

else {

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

d[i] = (i > r)? 0 : min(d[l + r - i + 1], r - i + 1);

while (i - d[i] - 1 >= 0 and i + d[i] < len and s[i - d[i] - 1] == s[i + d[i]])

d[i]++;

if (i + d[i] - 1 > r) {

r = i + d[i] - 1;

l = i - d[i];

}

if (r - l >= n) {

cout << "yes";

return 0;

}

cout << "no";

return 0;

}

Решение №3

Для решения задачи можно воспользоваться алгоритмом Манакера. Алгоритм позволяет находить все подпалиндромы строки, поэтому мы снова продублируем строку и будем искать в ней подпалиндром, длина которого равна длине $n$ исходной строки. Заметим, что нам достаточно проверять подпалиндомы, четность длины которых совпадает с четностью $n$. Далее будем сравнивать расстояние между концами $l$ и $r$ текущего палиндрома с $n$ (расстояние между концами может быть и больше $n$, т.к. мы уже определили, что четность этих величин будет совпадать, а если в строке найден подпалиндром длиной $s$, то существуют подпалиндромы и длиной $s-2$, $s-4$, … ).

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

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

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

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

Related Images:

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$-й дом — ограблен.

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

Ссылки

Related Images:

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

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

Условие

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

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

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

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

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

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

Тесты

№

Ввод

Вывод

955

4

137

318

3028

300

39

40

71

50

Код

#include <iostream>

using namespace std;

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

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

#include <iostream>

using namespace std;

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

{

int count = 0;

number /= 10;

while (number != 0) {

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

number /= 10;

}

return count;

}

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

{

int sum = 0;

while (number != 0) {

sum += number % 10;

number /= 10;

}

return sum;

}

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

{

number /= 10;

bool ok = false;

while (number != 0) {

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

number /= 10;

}

return ok;

}

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

{

int count = 0;

while (number != 0) {

count++;

number /= 10;

}

return count;

}

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

{

int a = kol_vo(number);

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

}

int main() {

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

int t;

cin >> t;

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

int ni;

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

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

int kol_vo1 = kol_vo(ni);

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

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

int a = ni;

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

int b[kol_vo1];

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

b[i] = a % 10;

a /= 10;

}

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

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

bool ok = false;

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

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

else {

ok = false;

break;

}

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

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

}

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

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

bool ok2 = false;

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

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

}

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

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

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

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

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

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

t--;

}

Решение

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

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

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

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

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

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

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

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

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

Ссылки

Related Images:

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

Related Images:

e-olymp 7254. Отрезки

13/03/2021 by Євген Константинов

Задача

Петя очень любит игрушки в форме геометрических фигур. Недавно он заметил, что среди его игрушек нет ни одного треугольника. Это очень огорчило Петю, поэтому он отправился в ближайший магазин с целью покупки новенького треугольника. В магазине Пете сказали, что все треугольники уже давно раскупили, но в наличии есть [latex]N[/latex] прямых отрезков.

Отрезки пронумерованы последовательными натуральными числами, начиная с единицы. Отрезок номер [latex]i[/latex] характеризуется двумя числами — длиной [latex]L_i[/latex] и ценой [latex]C_i[/latex]. Петя очень умный, поэтому знает, что желаемый треугольник он может сложить из трех отрезков. Более того, наш герой знает, что треугольник возможно сложить только из таких трех отрезков, среди которых длина любого отрезка строго меньше суммарной длины двух других. Итак, мальчик решил купить ровно три таких отрезка. Разумеется, он хочет сэкономить как можно больше денег на мороженое, поэтому стремится потратить как можно меньше денег на покупку треугольника.

Задание

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

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

В первой строке входного файла записано единственное число [latex]N[/latex] — количество отрезков. В следующих [latex]N[/latex] строках записана информация о самих отрезках. Каждая такая строка содержит соответствующие [latex]L_i[/latex] [latex](1 \leqslant L_i \leqslant 10^9)[/latex] и [latex]C_i[/latex]. Цены образуют перестановку чисел от [latex]1[/latex] до [latex]N[/latex], то есть являются попарно различными натуральными числами, не превосходящими [latex]N[/latex].

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

Выходной файл должен содержать единственное число — минимальную стоимость трех отрезков, из которых можно сложить треугольник, либо «-1» (кавычки для наглядности) в том случае, если выбрать ровно три таких отрезка невозможно.

Тесты

№	Входные данные	Выходные данные
1	4 1 1 2 2 3 3 4 4	9

Код

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

//Структура для представления одного отрезка
struct Line {
    int price;
    int length;
};

//Функция сортировщик по цене в порядке возрастания
bool comparator_price (Line i, Line j) { 
    return i.price < j.price;
}

int main() {
    int n, price, length, cheapest = INT_MAX;
    cin >> n;
    Line lines_by_price[n];
    
    for (int i = 0; i < n; i++) {
        Line l;
        cin >> length >> price;
        l.price = price;
        l.length = length;
        lines_by_price[i] = l;
    }
    
    //Сортируем все отрезки по цене, чтобы была возможность "отсечь"
    //слишком дорогие отрезки, когда цена одного(или двух) будет 
    //больше текущей минимальной
    sort(&lines_by_price[0], &lines_by_price[n], comparator_price);
    
    for (int i = 0; i < n; i++) {
        Line first_side = lines_by_price[i];
        if (first_side.price > cheapest) break;
        vector<Line> sides = {};
        //Перебираем все возможные тройки отрезков, отсекая
        //слишком дорогие, основываясь на сортировке по цене
        //и текущей минимальной цене
        for (int j = 0; j < n; j++) {
            if (lines_by_price[j].price != first_side.price && lines_by_price[j].length <= first_side.length) {
                sides.push_back(lines_by_price[j]);
                Line second_side = lines_by_price[j];
                if (first_side.price + second_side.price > cheapest) break;
                for (auto third_side: sides) {
                    if ((third_side.length != second_side.length && third_side.price != second_side.price) 
                    && first_side.length < second_side.length + third_side.length 
                    && second_side.length < first_side.length + third_side.length 
                    && third_side.length < second_side.length + first_side.length) {
                        if (first_side.price + second_side.price + third_side.price < cheapest) {
                            cheapest = first_side.price + second_side.price + third_side.price;
                        }
                        break;
                    }
                }
            }
        }
    }
    //Если ни одна тройка отрезков не подошла, значит составить
    //треугольник невозможно - выводим "-1"
    if (cheapest == INT_MAX) cheapest = -1;
    cout << cheapest;
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

#include <climits>

using namespace std;

//Структура для представления одного отрезка

struct Line {

int price;

int length;

};

//Функция сортировщик по цене в порядке возрастания

bool comparator_price (Line i, Line j) {

return i.price < j.price;

}

int main() {

int n, price, length, cheapest = INT_MAX;

cin >> n;

Line lines_by_price[n];

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

Line l;

cin >> length >> price;

l.price = price;

l.length = length;

lines_by_price[i] = l;

}

//Сортируем все отрезки по цене, чтобы была возможность "отсечь"

//слишком дорогие отрезки, когда цена одного(или двух) будет

//больше текущей минимальной

sort(&lines_by_price[0], &lines_by_price[n], comparator_price);

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

Line first_side = lines_by_price[i];

if (first_side.price > cheapest) break;

vector<Line> sides = {};

//Перебираем все возможные тройки отрезков, отсекая

//слишком дорогие, основываясь на сортировке по цене

//и текущей минимальной цене

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

if (lines_by_price[j].price != first_side.price && lines_by_price[j].length <= first_side.length) {

sides.push_back(lines_by_price[j]);

Line second_side = lines_by_price[j];

if (first_side.price + second_side.price > cheapest) break;

for (auto third_side: sides) {

if ((third_side.length != second_side.length && third_side.price != second_side.price)

&& first_side.length < second_side.length + third_side.length

&& second_side.length < first_side.length + third_side.length

&& third_side.length < second_side.length + first_side.length) {

if (first_side.price + second_side.price + third_side.price < cheapest) {

cheapest = first_side.price + second_side.price + third_side.price;

}

break;

}

//Если ни одна тройка отрезков не подошла, значит составить

//треугольник невозможно - выводим "-1"

if (cheapest == INT_MAX) cheapest = -1;

cout << cheapest;

return 0;

}

Решение

Для начала запишем все отрезки в массив в виде структур. Отсортируем их по цене в порядке возрастания, чтобы позже иметь возможность «отсекать» слишком дорогие отрезки. Далее мы начинаем перебирать все возможные тройки отрезков. На первом уровне цикла ставим условный оператор. Если на [latex]n[/latex]-ой итерации цикла будет отрезок с ценой больше текущей наименьшей цены треугольника, то мы можем выходить из массива и выводить текущую минимальную стоимость, т.к. все последующие отрезки будут дороже (пользуемся сортировкой и тем, что цены отрезков образуют перестановку от [latex]1[/latex] до [latex]N[/latex]). Далее на втором и третьем уровнях цикла мы также перебираем все отрезки от дешевых к дорогим и при обнаружении тройки отрезков, цена которых меньше текущей минимальной, записываем их в переменную [latex]cheapest[/latex]. При этом на втором уровне цикла проверяем, не больше ли сумма цен двух отрезков текущей минимальной, чтобы не проверять лишние тройки.

Ссылки

Related Images:

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.

Related Images:

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

Related Images:

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

Related Images:

E-Olymp 568. Средняя зарплата

22/12/2020 by Diana Kunitsyna

Условие

На некотором предприятии работает некоторое количество работников, но не менее двух: директора и главного бухгалтера. Известно также, что количество работающих не превышает 1000. Зная заработные платы кождого работника определить среднюю зарплату на предприятии.

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

Заработные платы работников (не обязательно в одной строке) в гривнах.

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

Средняя зарплата на предприятии в гривнах с точностью 2 знака после десятичной точки.

Тесты

№	Входные данные	Выходные данные
1	100.50 300.50	200.50
2	800 950 600.25 200.50	637.69
3	1000 1200.50 790 600 980	914.10

Код

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

int main() {
  int n = 0;
  double z;
  double sum = 0;
  while (cin >> z) {
    sum += z;
    n++;
  }
  cout << std::fixed << std::setprecision(2) << sum / n;
  return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

int n = 0;

double z;

double sum = 0;

while (cin >> z) {

sum += z;

n++;

}

cout << std::fixed << std::setprecision(2) << sum / n;

return 0;

}

Решение

Для того чтобы посчитать среднюю зарплату, нам нужно знать сумму зарплат всех работников sum и количество работающих n. Прибавляем к сумме зарплаты z до тех пор, пока есть что считывать из вводных данных. В тоже время считаем количество раз, чтобы узнать, сколько всего работников на предприятии. Выводим среднее арифметическое и указываем количество цифр после запятой.

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

Related Images:

e-olymp 1602. НОК двух натуральных чисел

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

Задача

Найдите $НОК$ (наименьшее общее кратное) двух натуральных чисел.

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

Два натуральных числа $a$ и $b$ $(a, b < 2 \cdot 10^9)$.

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

Вывести $НОК$ чисел $a$ и $b$.

Тесты

№	Входные данные	Выходные данные
1	42 24	168
2	32 14	224
3	101 45	4545

Код

#include <iostream>
using namespace std;
 
long int GCD(int num1, int num2) 
{
    if(num1 == num2) return num1;
    while(num1 && num2)
    {
        if(num1 > num2) num1 %= num2;
        else num2 %= num1;
    }
    return num1+num2;
}
 
int main() {
    long int num1, num2, gcd;
    cin >> num1 >> num2;
    gcd = GCD(num1, num2);
    cout << num1*num2/gcd;
    return 0;
}

#include <iostream>

using namespace std;

long int GCD(int num1, int num2)

{

if(num1 == num2) return num1;

while(num1 && num2)

{

if(num1 > num2) num1 %= num2;

else num2 %= num1;

}

return num1+num2;

}

int main() {

long int num1, num2, gcd;

cin >> num1 >> num2;

gcd = GCD(num1, num2);

cout << num1*num2/gcd;

return 0;

}

Решение

Пусть есть два числа $n_1$ и $n_2$. $НОК$($n_1$, $n_2$) можно вычислить по формуле $НОК(n_1, n_2)={{n_1\cdot n_2}\over{НОД(n_1, n_2)}}$. Тогда задача сводится к нахождению $НОД$ двух чисел, который вычисляется алгоритмом Евклида:
$1$. Большее число делится на меньшее.
$2$. Если остаток от деления равен нулю, то меньшее число и есть $НОД$.
$3$. Если есть остаток, то большее число заменяется на остаток от деления и все действия повторяются.
После завершения цикла в одной переменной содержится ноль, а другая равна $НОД$, но поскольку неизвестно, которая из переменных равна $НОД$, то возвращается их сумма.

Ссылки

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

Related Images:

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

Related Images:

e-olymp 1243. Наименьшее общее кратное

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

Условие

Наименьшим общим кратным ($НОК$) множества натуральных чисел называется такое наименьшее натуральное число, которое делится на каждое число в этом множестве. Например, $НОК$ чисел $5$, $7$ и $15$ равно $105$.

Вам необходимо найти $НОК$ $m$ заданных чисел.

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

Первая строка содержит количество тестов. Каждый тест состоит из одной строки и содержит числа $m$ $n_1$ $n_2$ $n_3$ $\ldots$ $n_m$, где $m$($1 \leqslant m \leqslant 100$) — количество заданных чисел, $n_1$ $\ldots$ $n_m$ — сами числа. Все числа натуральные и лежат в границах $32$-битового целого.

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

Для каждого теста в отдельной строке вывести соответствующее значение $НОК$. Все выводимые числа лежат в границах $32$-битового целого.

Тесты

№	ввод	вывод
1	2 3 5 7 15 6 4 10296 936 1287 792 1	105 10296
2	3 1 36 5 2 2 2 2 2 5 987 1597 2584 4181 6765 10946 17711	36 2 38400890173772280
3	0

Код

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

int main() {
    int n, m;
    cin >>n;
    for(int i=0; i<n; i++) {
        cin >>m;
        int temp, ans;
        cin >>ans;
        for(int j=1; j<m; j++) {
            cin >>temp;
            ans = ans/__gcd(ans, temp)*temp;
        }
        cout <<ans <<endl;
    }
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n, m;

cin >>n;

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

cin >>m;

int temp, ans;

cin >>ans;

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

cin >>temp;

ans = ans/__gcd(ans, temp)*temp;

}

cout <<ans <<endl;

}

Код с алгоритмом Евклида

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

int gcd(int a, int b) {
  while(a and b) {
    if(a>b)
      a %= b;
    else
      b %= a;
  }
  return a+b;
}

int main() {
    int n, m;
    cin >>n;
    for(int i=0; i<n; i++) {
        cin >>m;
        int temp, ans;
        cin >>ans;
        for(int j=1; j<m; j++) {
            cin >>temp;
            ans = ans/gcd(ans, temp)*temp;
        }
        cout <<ans <<endl;
    }
}

#include <iostream>

#include <algorithm>

using namespace std;

int gcd(int a, int b) {

while(a and b) {

if(a>b)

a %= b;

else

b %= a;

}

return a+b;

}

int main() {

int n, m;

cin >>n;

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

cin >>m;

int temp, ans;

cin >>ans;

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

cin >>temp;

ans = ans/gcd(ans, temp)*temp;

}

cout <<ans <<endl;

}

Решение

$\DeclareMathOperator{\lcm}{lcm}$
$НОК$ ($\lcm$) проще всего считается по формуле $\operatorname {lcm}(a,b)={\frac {|a\cdot b|}{\operatorname {gcd}(a,b)}}$, где $\gcd$ — $НОД$. Для $\lcm$ от более чем двух чисел справедлива следующая формула: $\operatorname {lcm}(a_{1},a_{2},\ldots ,a_{n})=\operatorname {lcm}(\operatorname {lcm}(a_{1},a_{2},\ldots ,a_{{n-1}}),a_{n})$, из которой видно, что подсчёт $\lcm$ от $n$ чисел сводится к вычислению $n-1$-ого $\lcm$ от очередного числа и предыдущего результата вычислений.

$НОД$ ($\gcd$) в коде считается при помощи стандартной функции __gcd(a, b) из стандартной библиотеки algorithm в первом варианте кода или по алгоритму Евклида во втором.

Ссылки

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 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

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 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";

}

Ссылки

Related Images:

e-olymp 4739. Решето Эратосфена

08/12/2020 by Oleksandr.Ivanov

Задача

По заданным числам $a$ и $b$ вывести все простые числа в интервале от $a$ до $b$ включительно.

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

Два числа $a$ и $b \ (1 \leqslant a \leqslant b \leqslant 100000)$.

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

Вывести в одной строке все простые числа в интервале от $a$ до $b$ включительно.

Тесты

№	Входные данные	Выходные данные	Объяснение
1	2 2	2
2	1 100	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
3	50 100	53 59 61 67 71 73 79 83 89 97
4	10 2		Неправильно, так как противоречит условию ($a \leqslant b$)
5	99900 100000	99901 99907 99923 99929 99961 99971 99989 99991
6	-15 -6	-13 -11 -7	Неправильно, так как противоречит условию ($1 \leqslant a \leqslant b \leqslant 100000$)

Код

#include <iostream>
#include <cmath>

using namespace std;


bool eratosthenesSieve(int currentNumber) {
    /*
    Describe the function that checks if the number is prime and returns a boolean value.
    This function is based on the "sieve of Eratosthenes" algorithm.
    True - if the number is prime, false - normal.
    */
    
    // If the number equals to 1 or if it even, return false. And if it equals to 2, return true.
    if (currentNumber == 2 or currentNumber == 3) {
        return true;
    } else if (!(currentNumber % 2) or !(currentNumber % 3) or currentNumber == 1) {
        return false;
    }
    
    // If the number has the divider from 5 to the root of this number with the second step return false.
    for (int divider = 5; divider <= sqrt(currentNumber); divider += 2) {
        if (!(currentNumber % divider)) {
            return false;
        }
    }
    
    // In all other situations, return true.
    return true;
}


void printSequenceOfPrimeNumbers(int beginning, int ending) {
    /*
    This function prints all prime numbers in a line.
    It contains a loop that starts and ends with the given values.
    */

    for (int sequenceElement = beginning; sequenceElement <= ending; sequenceElement += 1) {
        if (eratosthenesSieve(sequenceElement)) {
            cout << sequenceElement << " ";
        }
    }
}


int main() {
    /*
    Receive the beginning and end of the sequence.
    */
    
    int beginning, ending;
    cin >> beginning >> ending;
    
    // Calling the function.
    printSequenceOfPrimeNumbers(beginning, ending);

    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

bool eratosthenesSieve(int currentNumber) {

Describe the function that checks if the number is prime and returns a boolean value.

This function is based on the "sieve of Eratosthenes" algorithm.

True - if the number is prime, false - normal.

// If the number equals to 1 or if it even, return false. And if it equals to 2, return true.

if (currentNumber == 2 or currentNumber == 3) {

return true;

} else if (!(currentNumber % 2) or !(currentNumber % 3) or currentNumber == 1) {

return false;

}

// If the number has the divider from 5 to the root of this number with the second step return false.

for (int divider = 5; divider <= sqrt(currentNumber); divider += 2) {

if (!(currentNumber % divider)) {

return false;

}

// In all other situations, return true.

return true;

}

void printSequenceOfPrimeNumbers(int beginning, int ending) {

This function prints all prime numbers in a line.

It contains a loop that starts and ends with the given values.

for (int sequenceElement = beginning; sequenceElement <= ending; sequenceElement += 1) {

if (eratosthenesSieve(sequenceElement)) {

cout << sequenceElement << " ";

}

int main() {

Receive the beginning and end of the sequence.

int beginning, ending;

cin >> beginning >> ending;

// Calling the function.

printSequenceOfPrimeNumbers(beginning, ending);

return 0;

}

Решение

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

Это решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых.

Рассуждение:
— Все четные числа, не считая двойки, — составные, то есть не являются простыми, так как делятся не только на себя и единицу, а также еще на $2$.
— Все числа кратные трем, кроме самой тройки, — составные, так как делятся не только на самих себя и единицу, а также еще на $3$.
— Число $4$ уже выбыло из игры, так как делится на $2$.
— Число $5$ простое, так как его не делит ни один простой делитель, стоящий до него.
— Если число не делится ни на одно простое число, стоящее до него, значит оно не будет делиться ни на одно сложное число, стоящее до него.

В моем коде, указанном выше, была реализована функция-фильтр, которая, по большей части, реализовывает метод перебора делителей и проверяет: есть ли делители числа, кроме его самого, вплоть до корня из этого числа. И если остатки от деления не равны $0$, то мы возвращаем истину, что означает: число простое.

Таким же образом, проверяем все остальные числа из промежутка от $n$ до $m$ и выводим полученную последовательность на экран.

Ссылки

Related Images:

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

Related Images:

e-olymp 7110. Весы

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

Задача

Измерение веса предмета осуществляется с помощью лабораторных весов. С помощью набора из $7$ гирь весом $1$ г, $3$ г, $9$ г, $27$ г, $81$ г, $243$ г и $729$ г можно измерить вес любого предмета с целым весом от $1$ до $1093$ г единственным способом. Например, для измерения предмета весом $4$ г необходимо на одну чашу положить гири в $1$ и $3$ г, а на другую сам предмет, а, скажем, для предмета весом $68$ г на чашку с ним добавляются гири в $1$, $3$ и $9$ г, а на другую — гиря в $81$ г.

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

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

Одно натуральное число $x \ (1 \leqslant x \leqslant 1000)$ — вес предмета.

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

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

Тесты

№	Входные данные	Выходные данные
1	4	2
2	68	4
3	27	1
4	555	5
5	1000	4

Код

#include <iostream>
#define NUM 3
#define POW 729
using namespace std;
 
int nearest(int weight) {
    for (int i = 1; i < POW; i*=NUM){
        if (abs(i - weight) < abs(i*NUM - weight)) {
            return i;
        }
    }
}
 
int main() {
  int right_bowl, left_bowl = 0, count = 0;
  cin >> right_bowl;
  while (right_bowl != left_bowl) {
    if (right_bowl > left_bowl) {
            left_bowl += nearest(abs(right_bowl - left_bowl));
        }
    else right_bowl += nearest(abs(right_bowl - left_bowl));
    count++;
  }
  cout << count;
}

#include <iostream>

#define NUM 3

#define POW 729

using namespace std;

int nearest(int weight) {

for (int i = 1; i < POW; i*=NUM){

if (abs(i - weight) < abs(i*NUM - weight)) {

return i;

}

int main() {

int right_bowl, left_bowl = 0, count = 0;

cin >> right_bowl;

while (right_bowl != left_bowl) {

if (right_bowl > left_bowl) {

left_bowl += nearest(abs(right_bowl - left_bowl));

}

else right_bowl += nearest(abs(right_bowl - left_bowl));

count++;

}

cout << count;

}

Решение

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

Ссылки

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