Category Archives: 3. Циклы

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

Циклы

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

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

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

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

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

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

e-olymp 8377. Стойкое число

21/02/2019 by Дмитрий Калинин

Задача

По числу $x$ определим $p(x)$ как произведение его цифр. Рассмотрим последовательность $x$, $p(x)$, $p(p(x))$… Стойкостью $x$ назовем индекс (начиная с $0$) первого однозначного числа в этой последовательности. Например, из $99$ получим последовательность $99$, $9 · 9 = 81$, $8 · 1 = 8$. Стойкость числа $99$ равна $2$. По заданному числу $n$ определите его стойкость.

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

Каждая строка содержит одно целое число $n (0 \leqslant n \leqslant 2 · 10^9)$.

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

Для каждого значения $n$ выведите в отдельной строке его стойкость.

Решение

Опишем функцию $p(x)$, которая будет считать произведение цифр числа $x$. Для этого в функции заводим дополнительную переменную, например, $t$, равную единице, которую будем циклично домножать на остаток от деления $x$ на $10$, а $x$ уменьшать на разряд до тех пор, пока $x$ не попадёт в разряд единиц. Получившееся значение $t$ снова передаём в функцию $p(x)$ в качестве аргумента. Продолжим действия, описанные выше, до тех пор пока значение $t$ не будет находиться в разряде единиц. Индекс последней итерации функции и будет искомой стойкостью числа $x$.

Тесты

№	Ввод	Вывод
1	99 268 6	2 4 0
2	796 1 100	5 0 1
3	2356951 53 9892	2 2 3

Код

#include <iostream>
using namespace std;
 
int p(int x) {
    int t = 1;
    while (x != 0) {
        t *= x % 10;
        x = x / 10;
    }
    return t;
}
 
int main() {
    int x;
    while (cin >> x) {
        int i = 0;
        while (x / 10 != 0) {
            x = p(x);
            i++;
        }
        cout << i << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int p(int x) {

int t = 1;

while (x != 0) {

t *= x % 10;

x = x / 10;

}

return t;

}

int main() {

int x;

while (cin >> x) {

int i = 0;

while (x / 10 != 0) {

x = p(x);

i++;

}

cout << i << endl;

}

return 0;

}

Код для считывания строками

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

string f(string x) {
    int mult = 1;
    for (int i = 0; i < x.length(); i++) {
        mult *= int(x.at(i)) - int('0');
    }
    string result = to_string(mult);
    return result;
}

int main() {
    string inp;
    while (cin >> inp) {
        int count = 0;
        while (inp.length() > 1) {
            inp = f(inp);
            count++;
        }
        cout << count << endl;
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

string f(string x) {

int mult = 1;

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

mult *= int(x.at(i)) - int('0');

}

string result = to_string(mult);

return result;

}

int main() {

string inp;

while (cin >> inp) {

int count = 0;

while (inp.length() > 1) {

inp = f(inp);

count++;

}

cout << count << endl;

}

return 0;

}

Код c-string

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

int f(char* str, int i) {
    if (i == 0)
        return int(str[i]) - int('0');
    else
        return (int(str[i]) - int('0')) * f(str, i - 1);
}

int main() {
    char str[10];
    int t;
    while (cin >> str) {
        int count = 0;
        while (strlen(str) > 1) {
            int k = strlen(str) - 1;
            t = f(str, k);
            memset(str, 0, sizeof(str) / sizeof(str[0]));
            sprintf(str, "%d", t);
            count++;
        }
        cout << count << endl;
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int f(char* str, int i) {

if (i == 0)

return int(str[i]) - int('0');

else

return (int(str[i]) - int('0')) * f(str, i - 1);

}

int main() {

char str[10];

int t;

while (cin >> str) {

int count = 0;

while (strlen(str) > 1) {

int k = strlen(str) - 1;

t = f(str, k);

memset(str, 0, sizeof(str) / sizeof(str[0]));

sprintf(str, "%d", t);

count++;

}

cout << count << endl;

}

return 0;

}

Ссылки

Continue reading →

Related Images:

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

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

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

В нашем варианте мы начнем с того, что выстроим в круг $N$ человек, пронумерованных числами от $1$ до $N$, и будем исключать каждого $k$-ого до тех пор, пока не уцелеет только один человек. (Например, если $N=10$, $k=3$, то сначала умрет $3$-й, потом $6$-й, затем $9$-й, затем $2$-й, затем $7$-й, потом $1$-й, потом $8$-й, за ним — $5$-й, и потом $10$-й. Таким образом, уцелеет $4$-й.)

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

Во входном файле даны натуральные числа $N$ и $k$. $1≤N≤500$, $1≤k≤100$.

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

Выходной файл должен содержать единственное число — номер уцелевшего человека.

Тесты

№	Ввод	Вывод
1	10 3	4
2	500 100	480
3	50 10	36
4	1 1	1
5	41 3	31

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

#include <iostream>
using namespace std;

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

#include <iostream>

using namespace std;

int main() {

int n, k, p;

cin >> n >> k;

int person = 0;

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

cout << person+1;

return 0;

}

Решение

Все люди в кругу пронумерованы от $0$ до $N-1$, началом будет person = 0 . Нужно исключить $person+(k-1)$ человека. Начальная позиция следующего раунда $person + k$. Но если номер исключенного человека $N-1$, следующая начальная позиция $N$, что выходит за пределы круга, по-этому мы берем остаток от деления на количество оставшихся в живых людей: (person + k) % count .

Таким образом круг уменьшается на одного человека, при этом номер уцелевшего в круге размера $N$ равняется номеру в получившемся круге размера $N-1$. Предполагаем, что это работает и в обратную сторону: берем круг размером count = 2, высчитываем, кто будет в начальной позиции в следующем раунде. count в таком случае количество не убитых, а живых, и оно увеличивается с каждым раундом до $N$. В конце прибавляем $1$, потому что в начале все значения были сдвинуты.

Ссылки

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

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

Related Images:

e-olymp 6264. Энергетический магнат

01/02/2019 by Виктор Иванов

Задача

Маленький Вася играет в новую компьютерную игру — пошаговую стратегию «Энергетический магнат».

Правила игры достаточно просты:

- Доска содержит [latex]n[/latex] слотов, расположенных в линию.
- Имеется набор электростанций, каждая из которых занимает один или два слота подряд, и производит одну единицу энергии.
- Каждый ход игры позволяет построить одну новую электростанцию, ее можно расположить на доске в любом месте по Вашему усмотрению. Если для новой электростанции нет места, Вы можете удалить некоторые старые электростанции.
- После выполнения каждого хода компьютер вычисляет количество энергии, производимой расположенными на доске электростанциями, и добавляет его к общему количеству очков в игре.

Пример №1.

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

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

Первая строка содержит число [latex]n \left(1\leqslant n\leqslant 1000 \right)[/latex] — количество слотов на доске. Вторая строка содержит строку [latex]s[/latex]. [latex]i[/latex]-ый символ строки равен [latex]1[/latex], если Вы можете построить однослотовую электростанцию в [latex]i[/latex]-ом раунде, и символ [latex]2[/latex], если Вы можете построить двуслотовую электростанцию в [latex]i[/latex]-ом раунде. Количество раундов в игре не превосходит [latex]100000[/latex].

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

Вывести одно число — наибольшее количество очков, которое можно достичь.

Тесты

№	Вхлодные данные	Выходные данные
1	3 21121	10
2	2 12	2
3	2 211	4

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

#include <iostream>
using namespace std;

int main() {
    long n, c, res = 0, num = 0; //num - количество двуслотовых электростанций.
    long temp;  //temp - количество свободных слотов.
    cin >> n;
    temp = n;
    char s;
    while(cin >> s) {
        c = (s - '0');
        num += (c == 2) ? 1 : 0;
        if (temp - c < 0 && num >= 1) {
            temp += (2 - c);
            num -= 1;
        }
        else if (temp - c >= 0) {
            temp -= c;
        }
        res += (num < 1) ? (n - temp) : (n - temp - num);
    }
    cout << res;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long n, c, res = 0, num = 0; //num - количество двуслотовых электростанций.

long temp; //temp - количество свободных слотов.

cin >> n;

temp = n;

char s;

while(cin >> s) {

c = (s - '0');

num += (c == 2) ? 1 : 0;

if (temp - c < 0 && num >= 1) {

temp += (2 - c);

num -= 1;

}

else if (temp - c >= 0) {

temp -= c;

}

res += (num < 1) ? (n - temp) : (n - temp - num);

}

cout << res;

return 0;

}

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

Будем увеличивать num на 1, если встречается двуслотовая электростанция. Если нет свободных слотов [latex]temp — c\lt0[/latex] и [latex]num\geqslant1[/latex], то вместо двуслотовой ставим станцию, которая в этом ходе должна быть [latex]temp += (2 — c)[/latex] и вычитаем одно очко. В итоге смотрим, если двуслотовых электростанций нет [latex]num\gt 1[/latex], то считаем однослотовые: [latex]n — temp[/latex], а если они есть, то: [latex]n — temp — num[/latex].

Ссылки

Условие задачи на e-olymp
Код программы ideone

Related Images:

e-olymp 1215. Камень, ножницы или бумага?

27/12/2018 by Лиза Севастьянова

Задача

Условие

Камень > ножницы > бумага > камень > ножницы > …

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

Камень всегда побеждает Ножницы (Камень раздавливает Ножницы)
Ножницы всегда побеждают Бумагу (Ножницы режут Бумагу)
Бумага всегда бьет Камень (Бумага покрывает Камень)

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

Первая строка содержит количество тестов $t$ ($0 < t < 1000$). Первая строка каждого теста содержит количество раундов $n$ ($0 < n < 100$), сыгранных в игру Камень, Ножницы, Бумага. Каждая из следующих $n$ строк содержит одну из заглавных букв $R$ (Камень), $P$ (Бумага) или $S$ (Ножницы), пробел и снова заглавную букву $R$, $P$ или $S$. Первая буква обозначает выбор первого игрока, вторая буква — выбор второго игрока.

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

Для каждого теста в отдельной строке вывести имя победителя (Player 1 или Player 2). Если игра заканчивается вничью, вывести TIE.

Тесты

№	Входные данные	Выходные данные
1	3 2 R P S R 3 P P R S S R 1 P R	Player 2 TIE Player 1
2	1 1 S P	Player 1
3	2 3 S P P S R R 2 P R S R	TIE TIE
4	4 1 R P 2 R P S R 3 R P S R P S 4 P R R S P S S S	Player 2 Player 2 Player 2 Player 1

Решение

Для решения задачи необходимо сравнить выбор первого и второго игрока в каждом раунде каждого теста.
Подсчитываем количество побед для игроков во всех раундах теста. Получаем победителя для каждого теста.
В данной реализации используем вложенные циклы. Вводим переменную $t$ — количество тестов. Затем задаём цикл, в котором вводим новую переменную $n$ — количество раундов для каждого теста. Этот цикл будет работать, пока не проверим все тесты. Так же заводим два счётчика sum1 и sum2, которые будут подсчитывать победы первого и второго игрока. Задаём ещё один цикл, который будет выполняться, пока не проверим все раунды для каждого теста. В нём вводим выбор первого игрока и выбор второго игрока. Сравниваем данные значения согласно правилам победы, которые описаны в условии. В случае победы первого игрока увеличиваем переменную sum1 на единицу, в случае победы второго — sum2 на единицу. После завершения циклов сравниваем переменные sum1 и sum2, выводим соответствующие результаты.

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

#include <iostream>
using namespace std;

int main() {
    int t; // количество тестов
    cin >> t;
    for (int i = 0; i < t; i++) { // цикл для тестов
        int n; // количество раундов
        cin >> n;
        int sum1 = 0, sum2 = 0; // счётчики побед первого и второго игроков
        for (int j = 0; j < n; j++) { // цикл для раундов
            char p1, p2; // выбор первого и второго игроков
            cin >> p1 >> p2;
            if ((p2 == 'R' and p1 == 'S') or (p2 == 'S' and p1 == 'P') or (p2 == 'P' and p1 == 'R')) {
                sum2++;
            } else if (p1 != p2) {
                sum1++;
            }
        }
        if (sum1 > sum2) {
            cout << "Player 1" << endl;
        } else if (sum2 > sum1) {
            cout << "Player 2" << endl;
        } else cout << "TIE" << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int t; // количество тестов

cin >> t;

for (int i = 0; i < t; i++) { // цикл для тестов

int n; // количество раундов

cin >> n;

int sum1 = 0, sum2 = 0; // счётчики побед первого и второго игроков

for (int j = 0; j < n; j++) { // цикл для раундов

char p1, p2; // выбор первого и второго игроков

cin >> p1 >> p2;

if ((p2 == 'R' and p1 == 'S') or (p2 == 'S' and p1 == 'P') or (p2 == 'P' and p1 == 'R')) {

sum2++;

} else if (p1 != p2) {

sum1++;

}

if (sum1 > sum2) {

cout << "Player 1" << endl;

} else if (sum2 > sum1) {

cout << "Player 2" << endl;

} else cout << "TIE" << endl;

}

return 0;

}

Ссылки

Related Images:

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

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

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

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

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

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

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

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

Тесты

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

Решение

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

#include <iostream>
using namespace std;

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

#include <iostream>

using namespace std;

int main() {

int n, q, s, a;

cin >> n;

s = 0;

q = 0;

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

cin >> a;

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

q++;

s += a;

}

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

}

Ссылки

Related Images:

e-olymp 3766. Тысячелетие

25/12/2018 by Никита Шпилевский

Задача

Мудрый король решил ввести новый календарь. «Завтра будет первый день календаря, то есть день [latex]1[/latex] месяца [latex]1[/latex] года [latex]1[/latex]. Каждый год состоит из [latex]10[/latex] месяцев, с [latex]1[/latex] по [latex]10[/latex], и начинается с большого месяца. Обычный год начинается с большого месяца, за которым следует малый месяц, затем большой месяц и так далее один за другим. То есть первый месяц большой, второй малый, третий большой, …, десятый, он же последний, малый. Большой месяц состоит из [latex]20[/latex] дней, а малый месяц из [latex]19[/latex] дней. Однако годы, кратные трем, то есть год [latex]3[/latex], год [latex]6[/latex], год [latex]9[/latex] и так далее, состоит из [latex]10[/latex] больших месяцев и ни одного малого.»

Много времени прошло со дня введения календаря, и для празднования дня тысячелетия [latex]([/latex]год [latex]1000[/latex], месяц [latex]1[/latex], день [latex]1[/latex][latex])[/latex] решено было организовать королевскую лотерею, победителями которой станут те, кто прожил столько же дней, какое число выпадет в лотерее. Напишите программу, которая поможет людям вычислить количество дней от их дня рождения до дня тысячелетия.

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

Входные данные имеют следующий формат:

n
Y₁ M₁ D₁
Y₂ M₂ D₂
…
Y_n M_n D_n

Первая строка задает количество тестов [latex]n, \left ( n \leq 100 \right )[/latex]. Далее следуют n тестов, каждый из которых представляет собой одну строку с тремя натуральными числами [latex]Y_{i}\left ( Y_{i}< 1000 \right ), M_{i} \left ( M_{i}< 10 \right )[/latex] и [latex]D_{i} \left ( D_{i}\leq 20 \right )[/latex], задающих соответственно год, месяц и день рождения некоторого человека в нотации королевского календаря.

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

Для каждой даты рождения следует вывести в отдельной строке количество дней, прошедших со дня рождения (включительно) до дня тысячелетия (не включительно).

Тесты

№	Ввод	Вывод
1	2 1 1 1 344 3 1	196470 128976
2	3 696 5 1 182 9 5 998 8 7	59710 160715 252
3	2 344 2 19 696 4 19	128977 59712
4	1 999 10 20	1

Код

#include <iostream>
using namespace std;

int main() {
    short n;
    int  Y, M, D, daysAmount;
    const int bigMonth = 20, smallMonth = 19, bigYear = 200, smallYear = 195;
    cin >> n;
    for(int i = 0; i < n; i++) {
        daysAmount = 0;
        cin >> Y >> M >> D;
        if(Y % 3 == 0) daysAmount += (10 - M) * 20 + (20 - D); 
        else{
            if(M % 2 == 0) daysAmount += (smallMonth - D); 
            else daysAmount += (bigMonth - D);
            for(int month = (M + 1); month <= 10; month++) {
                if(month % 2 == 0) daysAmount += smallMonth;
                else daysAmount += bigMonth;
            }
        }
        for(int year = (Y + 1); year < 1000; year++) {
            if((year % 3) == 0) daysAmount += bigYear;
            else daysAmount += smallYear;
        }
        cout << daysAmount + 1 << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

short n;

int Y, M, D, daysAmount;

const int bigMonth = 20, smallMonth = 19, bigYear = 200, smallYear = 195;

cin >> n;

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

daysAmount = 0;

cin >> Y >> M >> D;

if(Y % 3 == 0) daysAmount += (10 - M) * 20 + (20 - D);

else{

if(M % 2 == 0) daysAmount += (smallMonth - D);

else daysAmount += (bigMonth - D);

for(int month = (M + 1); month <= 10; month++) {

if(month % 2 == 0) daysAmount += smallMonth;

else daysAmount += bigMonth;

}

for(int year = (Y + 1); year < 1000; year++) {

if((year % 3) == 0) daysAmount += bigYear;

else daysAmount += smallYear;

}

cout << daysAmount + 1 << endl;

}

return 0;

}

Решение

Запишем большой месяц (20 дней) и малый месяц (19 дней) соответственно в константы bigMonth и smallMonth, а также большой год (200 дней) и малый год (195 дней) соответственно в bigYear и smallYear. Затем проходим по циклу for n раз. Проверяем, если год, в котором родился человек, кратен 3, считаем количество полных прожитых человеком месяцев (каждый месяц — 30 дней) первого после рождения года, а также дни месяца, в котором он родился. В противном случае ( else) прибавляем дни каждого полного месяца, проверяя, большой он, и малый. Затем добавляем дни первого прожитого человеком месяца, так же учитывая его длительность. После этого проходим по циклу for, начальной итерацией которого является ( Y + 1), потому что дни года рождения мы посчитали ранее. За каждый год, номер которого кратен 3, добавляем 200 дней, а за некратный — 195. В конце выводим количество полученных дней +1, так как должны посчитать их количество включительно с днем рождения.

#include <iostream>
using namespace std;
 
int main() {
    short n;
    int  Y, M, D, daysAmount, multipleThree, notMultipleThree, lifeYears;
    const int bigMonth = 20, smallMonth = 19, bigYear = 200, smallYear = 195;
    cin >> n;
    for(int i = 0; i < n; i++) {
        daysAmount = 0;
        cin >> Y >> M >> D;
        lifeYears = 1000 - (Y + 1);
        if(lifeYears < 3 && lifeYears > 0) multipleThree = 1;
        else multipleThree = lifeYears / 3;
        if(lifeYears > 3 && lifeYears % 3 != 0)daysAmount += 5;
        notMultipleThree = lifeYears - multipleThree;
        daysAmount += multipleThree * bigYear + notMultipleThree * smallYear;
        if(Y % 3 == 0) {
              daysAmount += (10 - M) * bigMonth;
              daysAmount += bigMonth - D;
        }
        else {
            if(M % 2 != 0) {
                daysAmount += ( (10 - (M + 1)) / 2 ) * (bigMonth + smallMonth) + smallMonth;
                daysAmount += (bigMonth - D);
            }
            else {
                daysAmount += ( (10 - M) / 2 ) * (bigMonth + smallMonth);
                daysAmount += (smallMonth - D);
            }
        }
        cout << daysAmount + 1<< endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

short n;

int Y, M, D, daysAmount, multipleThree, notMultipleThree, lifeYears;

const int bigMonth = 20, smallMonth = 19, bigYear = 200, smallYear = 195;

cin >> n;

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

daysAmount = 0;

cin >> Y >> M >> D;

lifeYears = 1000 - (Y + 1);

if(lifeYears < 3 && lifeYears > 0) multipleThree = 1;

else multipleThree = lifeYears / 3;

if(lifeYears > 3 && lifeYears % 3 != 0)daysAmount += 5;

notMultipleThree = lifeYears - multipleThree;

daysAmount += multipleThree * bigYear + notMultipleThree * smallYear;

if(Y % 3 == 0) {

daysAmount += (10 - M) * bigMonth;

daysAmount += bigMonth - D;

}

else {

if(M % 2 != 0) {

daysAmount += ( (10 - (M + 1)) / 2 ) * (bigMonth + smallMonth) + smallMonth;

daysAmount += (bigMonth - D);

}

else {

daysAmount += ( (10 - M) / 2 ) * (bigMonth + smallMonth);

daysAmount += (smallMonth - D);

}

cout << daysAmount + 1<< endl;

}

return 0;

}

Решение

Снова проходим по циклу for n раз. Однако, теперь считаем дни без помощи циклов. В переменную lifeYears записываем годы жизни -1 , так как дни года рождения мы посчитаем далее. Затем, в if проверяем, находится ли количество прожитых лет в диапазоне от 1 до 3. Если да, то в переменную multipleThree записываем 1 — количество лет, кратных трем, то есть 999 год. В else multipleThree приравниваем к lifeYears, деленую на 3. В следующем if проверяем, больше ли количество лет трех. Если да, прибавляем 5 дней за больший 999 год. Затем, в переменную notMultipleThree записываем количество лет, не кратных трем. В следующей строке прибавляем ко дням жизни годы, умноженные на соответствующие им количества в каждом. После, в if проверяем, кратен ли год рождения 3. Если да, Находим количество полных прожитых месяцев, и умножаем его на bigMonth. Далее, находим дни, прожитые в месяц рождения. В else проверяем, родился ли человек в нечетном месяце. Если да, добавляем к дням количество дней, вычисляющееся по формуле, записанной в коде, если нет — аналогично. В конце, выводим количество дней +1, так как должны посчитать их количество включительно с днем рождения.

Ссылки

Related Images:

e-olymp 4192. Олимпиада

25/12/2018 by Анна Неделева

Задача

На олимпиаду по информатике прибыло $n$ команд, каждая из которых состоит из $a_i$ мальчиков и $b_i$ девочек $(1 ≤ i ≤ n)$. Для проживания имеются одинаковые комнаты по $m$ мест в каждой. Какое наименшее количество комнат достаточно для размещения участников олимпиады, если мальчиков с девочками селить вместе запрещено?

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

Первая строка содержит числа $n$ и $m$. Каждая следующая из $n$ строк содержит пару чисел $a_i$ , $b_i$ $(1 ≤ i ≤ n)$. Все числовые значения целые неотрицательные и не превышают $100$.

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

Вывести наименьшее необходимое количество комнат.

Тесты

№	Входные данные	Выходные данные
1	2 3 2 1 3 2	3
2	3 5 5 8 2 3 6 1	6
3	2 2 1 1 1 3	3
4	4 2 1 3 5 1 2 7 3 1	12
5	7 2 5 6 3 4 2 5 1 3 9 3 8 7 6 4	33

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

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

int main() {
    int n, m, a, b, k = 0, l = 0;
    cin >> n >> m;
    while (n--) {
        cin >> a >> b;
        k += a;
        l += b;
    }
    cout << (k + m - 1) / m + (l + m - 1) / m ;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n, m, a, b, k = 0, l = 0;

cin >> n >> m;

while (n--) {

cin >> a >> b;

k += a;

l += b;

}

cout << (k + m - 1) / m + (l + m - 1) / m ;

return 0;

}

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

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

Ссылки

Related Images:

e-olymp 75. Пираты и монеты

24/12/2018 by Даниил Мозгунов

Задача

[latex]n[/latex] пиратам удалось справедливо разделить клад из [latex]m[/latex] золотых монет — каждый получил свою часть согласно своему пиратскому рангу и стажу. Самый молодой пират взял [latex]a[/latex] монет, а каждый следующий пират брал на одну монету больше, чем предыдущий его коллега. Последним был капитан, которому досталось вдвое больше от запланированного, очевидно, что после него монет больше не осталось.

Сколько было пиратов вместе с капитаном, если известны [latex]a[/latex] и [latex]m[/latex]. Так как капитан без команды просто пират, то [latex]n > 1[/latex].

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

Два натуральных числа [latex]a[/latex] и [latex]m[/latex] ([latex]1 \leq a \leq 100, m < 15150[/latex]). Входные данные корректны.

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

Количество пиратов [latex]n[/latex].

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 25	3
2	3 24	4
3	4 38	5
4	5 55	6
5	6 75	7

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    double a, m, n, b, c, d;
    cin>>a>>m; 
    b = 2 * a + 1;
    c = 2 * a - 2 - 2 * m;
    d = b * b - 4 * c;
    n = ( -b + sqrt(d) ) / 2;
    cout<<n;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double a, m, n, b, c, d;

cin>>a>>m;

b = 2 * a + 1;

c = 2 * a - 2 - 2 * m;

d = b * b - 4 * c;

n = ( -b + sqrt(d) ) / 2;

cout<<n;

return 0;

}

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

Для решения задачи воспользуемся формулой арифметической прогрессии, которая в данном случае равна: [latex](2a + n — 1)\frac{n}{2} + a + n — 1[/latex]. Отсюда получаем квадратное уравнение : [latex]\frac{n^{2}}{2} + n(a + \frac{1}{2}) + a — 1 = m[/latex], упростим и получим: [latex]n^{2} + 2an + n + 2a — 2 = 2m[/latex]. В коде задаем чему равно [latex]b[/latex], [latex]c[/latex] и [latex]d[/latex]. Где [latex]b[/latex] и [latex]c[/latex] — коэффициенты квадратного уравнения, а [latex]d[/latex] — дискриминант квадратного уравнения, который вычисляем по формуле: [latex]b^{2} — 4c[/latex]. Они нужны для нахождения корня данного квадратного уравнения. При этом ответом на задачу будет только один корень квадратного уравнения, так как количество пиратов не может принимать отрицательное значение. Поэтому вычисляем корень квадратного уравнения по формуле: [latex]\frac{-b + \sqrt{b}}{2}[/latex], тем самым получаем ответ на нашу задачу.

Код программы (с циклом)

#include <iostream>
using namespace std;

int main() {
    unsigned int a, m, n = 0;
    cin>>a>>m;
    while (m - 2 * a != 0){
            m -= a;
            a ++;
            n ++;
    }
    cout<<n + 1;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned int a, m, n = 0;

cin>>a>>m;

while (m - 2 * a != 0){

m -= a;

a ++;

n ++;

}

cout<<n + 1;

return 0;

}

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

В данном способе используем цикл. Как он работает: в условии цикла задаем проверку, когда наступит очередь капитана и будет выполнятся равенство вида [latex]m — 2a = 0[/latex] цикл прекратит свою работу. Пока это равенство не будет выполнятся цикл будет выполнять работу арифметической прогрессии, постоянно увеличивая количество монет [latex]a[/latex] на каждого пирата при этом, вычитая каждый раз из общего клада [latex]m[/latex], также, пока не выполняется данное равенство, считаем количество пиратов [latex]n[/latex], путем прибавления [latex]n + 1[/latex], пока работает цикл. И когда цикл прекращает свою работу, в конце учитываем капитана и к полученному количеству пиратов [latex]n[/latex] прибавляем [latex]n + 1[/latex]. И получаем ответ на нашу задачу.

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

#include <iostream>
using namespace std;
 
int f(int a, int m, int n = 0) {
    if (m - 2*a == 0) {
        return n + 1;
    }
    else {
        return f(a + 1, m - a, n + 1);
    }
}
 
int main() {
    int a, m;
    cin >> a >> m;
    cout << f(a, m);
    return 0;
}

#include <iostream>

using namespace std;

int f(int a, int m, int n = 0) {

if (m - 2*a == 0) {

return n + 1;

}

else {

return f(a + 1, m - a, n + 1);

}

int main() {

int a, m;

cin >> a >> m;

cout << f(a, m);

return 0;

}

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

В данном способе воспользуемся рекурсивной функцией и условными операторами. Как это работает: внутри рекурсивной функции расписываем условные операторы, которые определяют равенством [latex]m — 2a = 0[/latex] — когда наступила очередь капитана, а пока это условие не выполняется, функция будет вызывать сама себя пока это условие не удовлетворится, функция каждый раз вызывается с новыми параметрами соответственно. Где [latex]a[/latex] — количество монет даваемое пиратам, увеличивается по рангу каждого пирата, [latex]m[/latex] — клад, от него отнимаем текущее [latex]a[/latex], и [latex]n[/latex] — количество пиратов, считаем пиратов. И в конце выводит количество пиратов. Задача решена.

Ссылки

Related Images:

e-olymp 8373. Перевернутая башня

23/12/2018 by Богдан Павлов

Задача

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

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

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

Номер комнаты [latex]n (1\leqslant n \leqslant 2\cdot10^{9})[/latex].

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

Выведите два целых числа: номер этажа и номер комнаты на этаже если считать слева.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1	1 1
2	5	3 2
3	35	11 5
4	31	11 1
5	2000000000	1650964 845

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

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int n; // номер комнаты
    int rooms_per_floor = 1; // кол-во комнат на этаже
    int temp = 0;
    int rooms = 0; // общее количество комнат
    int floor = 0; // этаж, на котором будет находиться комната #n
    cin >> n;
    while(n>0){
        if(rooms_per_floor == temp){
            temp = 0;
            rooms_per_floor++;
        }
        else if(n-rooms_per_floor>0){
            rooms+=rooms_per_floor;
            temp++;
            floor++;
            n-=rooms_per_floor;
        }
        else break;
    }
    cout << floor+1 << " " << n;
    return 0; 
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n; // номер комнаты

int rooms_per_floor = 1; // кол-во комнат на этаже

int temp = 0;

int rooms = 0; // общее количество комнат

int floor = 0; // этаж, на котором будет находиться комната #n

cin >> n;

while(n>0){

if(rooms_per_floor == temp){

temp = 0;

rooms_per_floor++;

}

else if(n-rooms_per_floor>0){

rooms+=rooms_per_floor;

temp++;

floor++;

n-=rooms_per_floor;

}

else break;

}

cout << floor+1 << " " << n;

return 0;

}

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

Для решения данной задачи я воспользовался циклом while, в котором на каждой итерации, проверял будет ли значение выражения n-rooms_per_floor больше нуля. Если оно было больше нуля, то из n вычиталось количество комнат на текущем этаже, а если меньше нуля, то цикл прерывался. После изменений, выполненных в цикле, переменная n соответствует номеру комнату на этаже, а переменная floor, которая равна количеству вычитаний из n, соответствует этажу, на котором находится комната. К ней в конце необходимо добавить единицу, так как в этой переменной не учитывается «текущий» этаж.

Ссылки

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

Related Images:

e-olymp 1519. Коды Грея

23/12/2018 by Дарья Найденова

Задача

Френк Грей. Bell Lab 1930

Бинарные коды Грея генерируются следующим образом. Рассмотрим последовательность
0
1
Отобразим строки вниз относительно горизонтальной черты, припишем к первой половине строк спереди 0, а ко второй отображенной половине 1. Получим последовательность:
00
01
11
10
Продолжая процесс, на следующем шаге получим последовательность из 8 чисел. Справа от кода находится его десятичное значение
000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4
Приведенные последовательности называются кодами Грея длины $n = 1, 2, 3$. Всего существует $2n$ разных кодов длины $n$. Каждые два соседних кода отличаются одним битом.

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

Первая строка содержит количество тестов $n$ (не более 250000). Каждая следующая строка содержит два числа: $n$ $(1 ≤ n ≤ 30)$ и $k$ $(0 ≤ k < 2^n)$.

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

Для каждого теста в отдельной строке вывести число, которое находится в $k$ — ой позиции последовательности кодов Грея длины $n$.

Тесты

№	Входные данные	Выходные данные
1	14 1 0 1 1 2 0 2 1 2 2 2 3 3 0 3 1 3 2 3 3 3 4 3 5 3 6 3 7	0 1 0 1 3 2 0 1 3 2 6 7 5 4
2	3 2 1 1 2 3 3	1 1 2
3	1 0 0	0
4	2 2 3 1 3	2 1

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

#include <iostream>
using namespace std;
 
int f(int n, int k) {
    if (!n) return 0;
    int tmp = 1 << (n - 1);
    if (k < tmp) return f(n - 1, k);
    return tmp + f(n - 1, (1 << n) - 1 - k);
}
 
int main() {
    int N, n, k;
    cin >> N;
    for (int i = N; i > 0; i--)  {
        cin >> n >> k;
        cout << f(n,k) << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int f(int n, int k) {

if (!n) return 0;

int tmp = 1 << (n - 1);

if (k < tmp) return f(n - 1, k);

return tmp + f(n - 1, (1 << n) - 1 - k);

}

int main() {

int N, n, k;

cin >> N;

for (int i = N; i > 0; i--) {

cin >> n >> k;

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

}

return 0;

}

Решение

В случае, если значение бинарного кода находится в первой части последовательности, т.е. $x$ < $2^{n-1}$, то ищем число, стоящее в позиции $k$ кода Грея длины $n-1$. В другом же случае ищем число, прибавив к
$2^{n-1}$ число в позиции $2^n-k-1$ длины $n-1$. Оформим данный алгоритм в виде рекурсивной функции.

e-olymp

ideone

Related Images:

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

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

Задача

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

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

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

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

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

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

Тесты

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

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

#include <iostream>
using namespace std;

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

#include <iostream>

using namespace std;

int main() {

int x = 0, a;

string s;

while (cin >> s){

cin >> a;

if (s == "multiply") {

x*=a;

}

else if (s == "subtract") {

x-=a;

}

else {

x+=a;

}

cout << x;

return 0;

}

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

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

Ссылки

Related Images:

e-olymp 273. Возведение в степень

22/12/2018 by Михаил Бутник

Задача

По трем натуральным числам [latex]a[/latex], [latex]b[/latex] и [latex]m[/latex] вычислить значение [latex]a^b\mod m[/latex].

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

Три натуральных числа [latex]a[/latex], [latex]b[/latex], [latex]m[/latex] [latex]\left(1 \leqslant a, m \leqslant 10^9, 2 \leqslant b \leqslant 10^7\right)[/latex].

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

Вывести [latex]a^b\mod m[/latex].

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1 2 100	1
2	100 2 1000000	10000
3	2 3 50	8
4	9 2 1	0
5	9 2 25	6

Код с циклом

#include <iostream>
using namespace std;
long binpow (long a, long n, long m) {
    long res = 1;
    while (n) {
        if (n & 1) {
            res *= a;
            res %= m;
        }
        a *= (a % m);
        a %= m;
        n >>= 1;
    }
    return res % m;
}
 
int main() {
    long a, b, m;
    cin >> a >> b >> m;
    cout << binpow (a, b, m);
    return 0;
}

#include <iostream>

using namespace std;

long binpow (long a, long n, long m) {

long res = 1;

while (n) {

if (n & 1) {

res *= a;

res %= m;

}

a *= (a % m);

a %= m;

n >>= 1;

}

return res % m;

}

int main() {

long a, b, m;

cin >> a >> b >> m;

cout << binpow (a, b, m);

return 0;

}

Код с ветвлением

#include <iostream>
using namespace std;
long binpow (long a, long n, long m) {
    if (n == 0)
        return 1 % m;
    if (n % 2 == 1)
        return (binpow (a, n - 1, m) * a) % m;
    else {
        return binpow ((a * a) % m, n/2, m);
    }
}
 
int main() {
    long a, b, m;
    cin >> a >> b >> m;
    cout << binpow (a, b, m);
    return 0;
}

#include <iostream>

using namespace std;

long binpow (long a, long n, long m) {

if (n == 0)

return 1 % m;

if (n % 2 == 1)

return (binpow (a, n - 1, m) * a) % m;

else {

return binpow ((a * a) % m, n/2, m);

}

int main() {

long a, b, m;

cin >> a >> b >> m;

cout << binpow (a, b, m);

return 0;

}

Решение

Для решения этой задачи я воспользовался функцией бинарного возведения в степень binpow () (рекурсивной для программы с ветвлением и нерекурсивной для программы с циклом). Это приём, позволяющий возводить любое число в [latex]n[/latex]-ую степень за [latex]O(\log n)[/latex] умножений. В этой функции при возведении я дополнительно применял операцию деление с остатком к результату res и возводимому числу a для того, чтобы получить решение.

Запустить код с циклом (ideone) можно здесь
Запустить код с ветвлением (ideone) можно здесь
Задача на E-olymp

Related Images:

e-olymp 7228. Сколько шестерок?

21/12/2018 by Яна Юрковская

Задача

Сколько раз будет использована цифра $6$, если записать подряд последовательные натуральные числа от $a$ до $b$?

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

Два натуральных числа $a$ и $b$ [latex](1 ≤ a, b ≤ 10^9)[/latex].

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

Количество цифр $6$ в последовательных натуральных числах от $a$ до $b$.

Тесты

№	Ввод	Вывод
1	5 256	46
2	56 110	16
3	27357 43577	5852
4	368325775 56	296285528
5	584937543 984938576	420000314

Код

#include <iostream>
using namespace std;

int count_six(int input){
    int rez = 0, mem = 1, length = 0, exp_10 = 1;
    short num;
    while(input > 0){
        num = input % 10;//узнаём последний знак в числе
        input /= 10;//убираем последний разряд из числа
        if (num < 6) rez += num * exp_10 * length; //к результату добавим количество шестёрок в данном разряде
        else if (num == 6) rez += num * exp_10 * length + mem; //к результату добавим количество шестёрок в данном разряде плюс уже пройденное нами число+1
        else rez += num * exp_10 * length + exp_10 * (length == 0? 1 : 10); //к результату добавим количество шестёрок в предыдущем разряде
        if (length != 0) exp_10 *= 10; //проверяем количество пройденных разрядов 
        mem += num * exp_10; //запоминаем пройденное число
        length++; //отмечаем пройденный разряд
    }
    return rez;
}

int main() {
    int a, b;
    cin >> a >> b;
    if (a > b) swap(a, b);
    cout << count_six(b) - count_six(a - 1);
    return 0;
}

#include <iostream>

using namespace std;

int count_six(int input){

int rez = 0, mem = 1, length = 0, exp_10 = 1;

short num;

while(input > 0){

num = input % 10;//узнаём последний знак в числе

input /= 10;//убираем последний разряд из числа

if (num < 6) rez += num * exp_10 * length; //к результату добавим количество шестёрок в данном разряде

else if (num == 6) rez += num * exp_10 * length + mem; //к результату добавим количество шестёрок в данном разряде плюс уже пройденное нами число+1

else rez += num * exp_10 * length + exp_10 * (length == 0? 1 : 10); //к результату добавим количество шестёрок в предыдущем разряде

if (length != 0) exp_10 *= 10; //проверяем количество пройденных разрядов

mem += num * exp_10; //запоминаем пройденное число

length++; //отмечаем пройденный разряд

}

return rez;

}

int main() {

int a, b;

cin >> a >> b;

if (a > b) swap(a, b);

cout << count_six(b) - count_six(a - 1);

return 0;

}

Решение

Выписав и посчитав количества шестёрок от $1$ до [latex]10, 100, 1000, …[/latex] Мы обнаружим закономерность, они равны [latex]1, 20, 300, …[/latex] соответственно.

Доказательство проведем по математической индукции.

Для [latex]n = 1[/latex] [latex]countSix(10^1) = 1[/latex].
Для [latex]n ≤ k[/latex] $countSix(10^{k}) = k \cdot 10^{k-1}$
Для [latex]n = k+1[/latex] $countSix(10^{k+1}) = k\cdot10^{k-1}\cdot10+10^k = (k+1)\cdot10^k$

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

Ссылки

Related Images:

e-olymp 6777. Автобус

19/12/2018 by Наталья Федина

Задача

Автобус с $n$ пассажирами открывает двери на автобусной остановке. В точности половина пассажиров плюс полпассажира выходит. На следующей остановке снова половина пассажиров плюс полпассажира выходит из автобуса. Так продолжается $k$ остановок. Зная, что на последней остановке автобус стал пустым, и никто не пострадал во время поездки, определите начальное количество людей $n$ в автобусе.

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

Первая строка содержит количество тестов $t$. Каждый тест содержит в отдельной строке количество остановок $k(1 \leq k \leq 30).$

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

Для каждого теста вывести в отдельной строке начальное количество пассажиров.

Тесты

	Входные данные	Выходные данные
1	2 1 3	1 7
2	3 0 15 12	0 32767 4095
3	7 5 8 10 19 4 1 9	31 255 1023 524287 15 1 511
4	4 23 17 2 8	8388607 131071 3 255

Код

#include <iostream>
using namespace std;

int main() {
    int n;
    int k;
    cin >> n;
    while (n-- > 0) {
        cin >> k;
        cout << (1 << k) - 1 << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

int k;

cin >> n;

while (n-- > 0) {

cin >> k;

cout << (1 << k) - 1 << endl;

}

return 0;

}

Решение

Число пассажиров обязано быть нечётным, так как если бы оно было чётным, то какого-то пассажира пришлось бы резать пополам, что противоречит условию.
На последней остановке должен выйти всего один пассажир, потому что обязательно из автобуса выйдет пол пассажира и половина от всех едущих, и при этом автобус опустеет.
Значит:
$$\frac{x}{2} + 0.5 = x$$
$$\frac{x}{2} = x — 0.5$$
$$x = 2x — 1$$
$$x = 1,$$
где $x$ — число пассажиров в автобусе.
Тогда на предпоследней остановке было:
$$x = x_0 + \frac{x}{2} + 0.5$$
$$\frac{x}{2} = x_0 + 0.5$$
$$x = 2(x_0 + 0.5) = 2x_0 + 1,$$
где $x_0$ — число пассажиров оставшихся в автобусе. Значит $x = 3$
И так далее. А значит на $k$-ой остановке перед выходом пассажиров было:
$x = 2\cdot \left(2\cdot\left(2\cdot\left( \cdots 2\cdot\left(0\right) + 1\right) + \ldots +1\right) + 1\right) + 1$ или $x = 2^n \cdot 0 + 2^{n-1} + \ldots + 2 + 1$
Свернём по формуле суммы геометрической прогрессии, где $b = 1$ и $q = 2.$
[latex]S_k = \frac{b\left(q^k -1\right)}{q-1} = 2^{k} — 1.[/latex]

Ссылки

Related Images:

e-olymp 8380. Эскалатор

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

Задача: Эскалатор

В Баку вскоре откроется новая станция метро. Эскалатор в метро состоит из n ступенек, пронумерованных целыми числами от $1$ до $n$. На ступеньках с номерами, кратными десяти, а также на первой и последней ступеньке, пишут их номера. При записи номера на каждую записанную цифру уходит одно и то же количество краски.

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

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

Одно целое число $n\;\left(1 \leq n \leq 10^{18}\right)$ — количество ступеней эскалатора.

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

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

Тесты

Ввод	Вывод
1000000000000000000	1788888888888888908
242	67
250	67
999	292
1000	293
1	1
2	2

Решение

Идея решения заключается в том чтобы искать количество помеченных ступенек на отрезках $10-99,100-999,\ldots,10^{x}-\left(10^{x+1}-1\right).$ Легко понять что помеченных ступенек $9\cdot 10^{x}.$ Это суть метода, а остальное это реализация, которую я покажу в программе.

#include <iostream>
using namespace std;
#define ll long long
int main() {
  ll n, q = 0, s = 1/*учитываем первую ступеньку*/, d = 0, d1 = 0;
  cin >> n;
  if (n == 1){cout << 1;return 0;}
//важный частный случай,где первая ступенька последняя 
  bool n1 = (n % 10 != 0);
//что бы не забыть про последнюю ступеньку
  ll n2 = n / 10;
//кол-во помеченных ступенек без учета первой и последней
  while (n > 9) {
    n /= 10;
    q++;//с каждым десятком кол-во цифр в числе растет
    s += (d - d1) * q;//реализация указанной выше идеи
    d1 = d;
    d = d * 10 + 9;//числа, которые я уже учел
  }
  n2 -= (d) / 10;//помеченные не учтеные ступеньки
  q++;
  s += n2 * q;
  s += n1 * q;//считаем последнюю ступеньку
  cout << s;
  return 0;
}

#include <iostream>

using namespace std;

#define ll long long

int main() {

ll n, q = 0, s = 1/*учитываем первую ступеньку*/, d = 0, d1 = 0;

cin >> n;

if (n == 1){cout << 1;return 0;}

//важный частный случай,где первая ступенька последняя

bool n1 = (n % 10 != 0);

//что бы не забыть про последнюю ступеньку

ll n2 = n / 10;

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

while (n > 9) {

n /= 10;

q++;//с каждым десятком кол-во цифр в числе растет

s += (d - d1) * q;//реализация указанной выше идеи

d1 = d;

d = d * 10 + 9;//числа, которые я уже учел

}

n2 -= (d) / 10;//помеченные не учтеные ступеньки

q++;

s += n2 * q;

s += n1 * q;//считаем последнюю ступеньку

cout << s;

return 0;

}

Ссылки

Related Images:

e-olymp 4721. Отличник Вася

29/11/2018 by Александр Мога

Задача

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

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

Номер Васиного билетика [latex]n (0 \le n \le 9999)[/latex].

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

Выведите количество пятёрок, которое получит Вася.

Тесты

Вход	Выход
3533	1
5555	4
2521	1
5185	2
1682	0

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

#include <iostream>
using namespace std;

int main() {
	char c; 
	int k=0; // счётчик пятёрок
	while (cin >> c) // читаем номер билетика посимвольно
		if(c=='5') k++; // считаем количество пятёрок
	cout << k;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

char c;

int k=0; // счётчик пятёрок

while (cin >> c) // читаем номер билетика посимвольно

if(c=='5') k++; // считаем количество пятёрок

cout << k;

return 0;

}

Решение

Читаем номер билетика из потока ввода посимвольно, и в случае нахождения пятёрки — инкрементируем счётчик.

Ссылки

e-olymp

ideone

Related Images:

e-olymp 8514. Never drink too much!

26/11/2018 by Руслан Масальский

The task is taken from e-olymp

Task

Mahmoud together with his friends visited Georgia. They would stay in a hotel at Rustavelli. When the cowboys reached the hotel, they hung their hats in the entrance and settled in. The beer bottles on the table could not escape from Mahmoud’s attention when passing through the corridor. At the suggestion of Mahmoud, all the cowboys began drinking. They drank too much, thus none of them was mindful. Then they decided going downtown. On the way out, everyone had a hat on, but they mixed up the hats as they were so drunk.

The man who is able to have on his own hat while he is drunk is considered clever and who is not able to do so is considered stupid.

You are given the number of cowboys — n (including Mahmoud). You should find in how many ways the cowboys may have on the hats so that all of them are stupid. Two ways are considered different if there is at least one cowboy who has a hat in this case and another hat in the other case.

As the answer may become very large, you should output the result modulo 10⁹ + 7.

Input

Given the number of cowboys — n (1 ≤ n ≤ 10⁷).

Output

The answer to the problem as specified above.

Tests

№	Inputs	Outputs
1	1	0
2	4	9
3	9	133349
4	555	335132588
5	10000000	824182295

Code

#include <bits/stdc++.h> 
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"
using namespace std;
 
int32_t main() {
    IOS;
    int n, m = 1e9 + 7;
    cin >> n;
    if(n == 1){
        cout << 0;
        return 0;
    }
    int res = n%2==0? 1 : -1;
    int prev = res;
    for (int i = n - 1; i >1; i--) {
        res += prev * (-i - 1 +m) % m;
        prev *= (-i - 1);
        prev = (prev + m) % m;
        res = (res + m) % m;
    }
    cout << res;
    return 0;
}

#include <bits/stdc++.h>

#define int long long

#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define endl "\n"

using namespace std;

int32_t main() {

IOS;

int n, m = 1e9 + 7;

cin >> n;

if(n == 1){

cout << 0;

return 0;

}

int res = n%2==0? 1 : -1;

int prev = res;

for (int i = n - 1; i >1; i--) {

res += prev * (-i - 1 +m) % m;

prev *= (-i - 1);

prev = (prev + m) % m;

res = (res + m) % m;

}

cout << res;

return 0;

}

Solution

We have all possible permutations [latex]C_n^0 \cdot n![/latex] , minus one fixed (one of them is not stupid) we get [latex]C_n^0 \cdot n!-C_n^1 \cdot (n-1)![/latex] but we subtract for minimum fixed pair (two of them are not stupid) we need to add them [latex]C_n^0 \cdot n!-C_n^1 \cdot (n-1)! + C_n^2 \cdot (n-2)! [/latex] etc.
So the [latex]k[/latex] member is [latex]C_n^k \cdot (n-k)! \cdot (-1)^k[/latex] Let`s find the attitude of [latex]k[/latex] member to the previous one. It`s [latex]-k -1[/latex] The last one will be [latex]-1[/latex] it depends on parity of [latex]n[/latex].
First two are the same ( [latex]n![/latex] ) so we skip them, but in this case we need to check if[latex]n[/latex] equals [latex]1[/latex] And next we make a loop to find the answer by multiplying start value and add it to the answer.
The complexity is [latex]O(n)[/latex]

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

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

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

Задача

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

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

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

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

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

Тесты

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

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

#include <iostream>
using namespace std;

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

#include <iostream>

using namespace std;

int main() {

char c;

int sum = 0;

while(cin >> c)

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

sum += (c - '0');

cout << sum << '\n';

return 0;

}

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

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

Ссылки

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

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

Related Images:

e-olymp 2060 Сказка о яблоке

20/11/2018 by Николай Козиний

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

Задача

Однажды царь наградил крестьянина яблоком из своего сада. Пошёл крестьянин к саду и видит: весь сад огорожен $n$ заборами, в каждом заборе только одни ворота, и в каждых воротах стоит сторож. Подошёл крестьянин к первому сторожу и показал царский указ, а сторож ему в ответ: «Иди возьми, но при выходе отдашь мне половину тех яблок, что несёшь, и ещё одно». То же ему сказали и второй, и третий сторож и т.д. Сколько яблок должен взять крестьянин, чтобы после расплаты со сторожами у него осталось одно яблоко?

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

Количество заборов $n (1 \leqslant n \leqslant 62)$ в саду.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1	4
2	3	22
3	30	50331646
4	60	3458764513820540926
5	62	13835058055282163710

Решение

Циклы

Последовательность необходимых количеств яблок задается формулой $x_{n+1}=2 \cdot (x_{n}+1);x_{1}=1.$ Мы можем поочередно вычислять элементы последовательности через цикл.

#include <iostream>
int main() {
    int n;
    std::cin>>n;
    unsigned long long k = 1;
    for(int i = 0; i<n; i++)k = (k + 1) * 2;
    std::cout<<k;
}

#include <iostream>

int main() {

int n;

std::cin>>n;

unsigned long long k = 1;

for(int i = 0; i<n; i++)k = (k + 1) * 2;

std::cout<<k;

}

Линейное решение

Преобразуем исходное выражение для $x_{n+1}=2 \cdot x_{n}+2.$ Можно видеть, что каждая следующая итерация увеличивает степень всех двоек входящих в предыдущую на 1 и добавляет 2. Выпишем формулу для $x_{n+m}=2^{m}x_n+2^{m-1}x_n+\cdots+2.$ Можно увидеть, что $x_{n+m}$ содержит слагаемое $2^{m}x$, а так же сумму слагаемых вида $\displaystyle \sum_{i=1}^{m}2^i \displaystyle.$ Если учесть, что $x_{1}=1$, то $\displaystyle x_n=2^{n}+ \sum_{i=1}^{n}2^i \displaystyle=2^{n+1}+2^n-2=2^{n}\cdot(2+1) -2.$ Следовательно формула $n$-го члена — [latex]x_n=3\cdot 2^n-2.[/latex]

#include <iostream>
int main() {
    int n;
    std::cin>>n;
    unsigned long long t = 2;
    std::cout<<3*(t<<n-1)-2;
}

#include <iostream>

int main() {

int n;

std::cin>>n;

unsigned long long t = 2;

std::cout<<3*(t<<n-1)-2;

}

Решения на ideone

Related Images:

e-olymp 8595. Собаки и обезьяны

15/11/2018 by Владислав Бебик

Задача

У Барыша есть $n$ собак и $m$ обезьян. Он хочет выстроить их в одну линию. Но он не хочет, чтобы в каком-либо месте стояло подряд две собаки или две обезьяны, потому что в таком случае они начинают драться. Сколько существует различных вариантов построения, таких чтобы ни обезьяны, ни собаки не дрались. Ответ выведите по модулю $10^{9}+7$. Имейте в виду, что собаки и обезьяны между собой различаются.

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

Два числа $n$ и $m$ $\left(1 \leq n, m \leq 10^{5}\right)$.

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

Выведите количество различных вариантов построения обезьян и собак по модулю $10^{9}+7$.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	2 2	8
2	3 2	12
3	1 8	0
4	100000 100000	530123477
5	99999 100000	768947656

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

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

int main() {
    int n,m,k;
    long long f=1,p=1000000007;
    cin >> n >> m;
    if (abs(n-m)>1) cout << "0";
    else {
        k=min(n,m);
        for (int i=1; i<=k; i++) { 
            f=f*i;
            if (f>=p) f=f%p;
        }
        f=f*f;
        if (f>=p) f=f%p;
        if (n==m) f=2*f;
        else f=f*max(n,m);
        if (f>=p) f=f%p;
        cout << f;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n,m,k;

long long f=1,p=1000000007;

cin >> n >> m;

if (abs(n-m)>1) cout << "0";

else {

k=min(n,m);

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

f=f*i;

if (f>=p) f=f%p;

}

f=f*f;

if (f>=p) f=f%p;

if (n==m) f=2*f;

else f=f*max(n,m);

if (f>=p) f=f%p;

cout << f;

}

return 0;

}

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

В данной задаче три случая. Если разница между количеством собак и обезьян превышает один, то будет невозможно разместить их так, чтобы собаки с обезьянами чередовались. Количество размещений собак равно $n!.$ Количество размещений обезьян равно $m!.$ Если количество одинаково, то сначала может быть как собака, так и обезьяна. Поэтому ответом будет $2n!m!$ и выведем ответ по модулю $10^{9}+7$. В остальных случаях будет ответом $n!m!$ и выведем ответ по модулю $10^{9}+7$. Последний случай, значит, что разница между количеством собак и обезьян это $1$. Промежуточные вычисления будут иметь тип long long, так как в промежуточных вычислениях, число может быстро увеличиваться. Поэтому после каждого умножения будем искать остаток при делении числа на $10^{9}+7$, если число будет превышать $10^{9}+7$.

Ссылки

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

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