Category Archives: 3. Циклы

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

Циклы

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

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

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

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

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

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

e-olymp 8532. Печать квадратов и кубов

11/11/2018 by Владислав Шеванов

Задача

Заданы два целых числа $a$ и $b$. Выведите квадраты и кубы всех целых чисел от $a$ до $b$ включительно.

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

Два целых числа $a$ и $b$ [latex](0 \le a \le b \le 10000)[/latex].

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

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

Тесты

Входные данные	Выходные данные
5 10	25 36 49 64 81 100 1000 729 512 343 216 125
120 123	14400 14641 14884 15129 1860867 1815848 1771561 1728000
9995 10000	99900025 99920016 99940009 99960004 99980001 100000000 1000000000000 999700029999 999400119992 999100269973 998800479936 998500749875
0 3	0 1 4 9 27 8 1 0
25 27	625 676 729 19683 17576 15625

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

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    for (long long int i = a; i <= b; i++)
        cout << i * i << ' ';
    cout << endl;
    for (long long int j = b; j >= a; j--)
        cout << j * j * j << ' ';
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b;

cin >> a >> b;

for (long long int i = a; i <= b; i++)

cout << i * i << ' ';

cout << endl;

for (long long int j = b; j >= a; j--)

cout << j * j * j << ' ';

return 0;

}

Решение

Ввожу $a$ и $b$, создаю цикл вывода по возрастанию квадратов чисел из промежутка, и с новой строки — кубы по убыванию.

Ссылки

Ideone

e-olymp

Related Images:

e-olymp 8362. Множители

28/10/2018 by Инна Литвиненко

Задача

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

Например, если $n = 7$, то ответом будет число $6$, как наибольшее число, имеющее в своем разложении $2$ простых множителя $2$ и $3$.

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

Одно целое число $n$ $(1 ≤ n ≤ 2^{31}- 1)$.

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

Вывести одно искомое число.

Тесты

№	Ввод	Вывод
1	1	1
2	10	8
3	100	96
4	363	256
5	2147483647	1610612736

Код программы с использованием цикла

#include <iostream>
using namespace std;

int main() {
    long long int n, a = 2, b = 3;
    cin >> n;
    if (n <= 3) cout << n;
    else {
        while (a * 2 <= n) a *= 2;
        while (b * 2 <= n) b *= 2;
        cout << max(a, b);
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long int n, a = 2, b = 3;

cin >> n;

if (n <= 3) cout << n;

else {

while (a * 2 <= n) a *= 2;

while (b * 2 <= n) b *= 2;

cout << max(a, b);

}

return 0;

}

Код программы с использованием условных операторов

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

int main()
{
    long long n;
    cin >> n;
    if (n <= 3)
        cout << n;
    else {
        long long pow, a = 2, b = 3;
        pow = log(n) / log(2);
        a = a << (pow - 1);
        b = b << (pow - 1);
        if (a <= n && b <= n)
            cout << max(a, b);
        else if (a > n)
            cout << b;
        else
            cout << a;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

long long n;

cin >> n;

if (n <= 3)

cout << n;

else {

long long pow, a = 2, b = 3;

pow = log(n) / log(2);

a = a << (pow - 1);

b = b << (pow - 1);

if (a <= n && b <= n)

cout << max(a, b);

else if (a > n)

cout << b;

else

cout << a;

}

return 0;

}

Решение

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

Заметим, что если заданное число будет единицей, двойкой или тройкой, то его и надо вывести на экран.

Условные операторы

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

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

Из двух полученных в результате наших действий чисел выберем наибольшее не превосходящее входные данные.

Цикл

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

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

Ссылки

Задача множители на e-olymp

Решение задачи на Ideone циклом

Решение задачи на Ideone условными операторами

Related Images:

e-olymp 2061. Юные программисты

19/10/2018 by Кирилл Веремйов

Задача

Известно, что в школе не менее чем $k_{1}$учеников, но не более чем $k_{2}$ учеников. Также известно, что каждый мальчик дружит с $n$ девочками, а каждая девочка с $m$ мальчиками. Какое минимальное количество учеников может быть в школе, и сколько в школе мальчиков и девочек?

Юные программисты, как Вы видите, до сих пор решают эту задачку. Помогите им.

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

В первой строке входного файла находится $4$ числа, разделённых пробелами: $k_{1}$, $k_{2}$, $n$ и $m$. Все входные данные натуральные числа, не превышающие $10000$, $k_{1}\leq k_{2}$.

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

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

Тесты

Входные данные	Выходные данные
20 30 4 5	27 15 12
5 10000 54 44	98 44 54
1 10000 100 100	200 100 100
1 2 1 1	2 1 1
100 120 2 3	100 60 40
50 50 25 25	50 25 25
9900 10000 99 56	9920 3584 6336
9999 10000 9998 2	10000 2 9998
101 110 2 3	105 63 42

Решение

#include <iostream>
using namespace std;
 
int main() {
    int k1, k2, m, n; 
    int x = 0, y = 0, M = 10001; 
//x-мальчики, y-девочки, M- минимальное из вариантов количества учеников (10001 сначала, чтобы первый раз прошло условие внутри цикла) 
    cin >> k1 >> k2 >> n >> m; 
 
    for(int i = 0; i <= k2; i++){
        for(int j = k1-i; j <= k2; j++){ //j=k1-i, так как сумма i+j должна быть хотя бы k1. Рассматривать варианты меньше, смысла не имеет
/* M>i+j— если сумма меньше предыдущего из меньших, то перезаписываем переменные, если больше- пропускаем. i*j== количество дружащих пар.
 k1<=i+j — общее число учеников должно быть больше или равно k1 и меньше, либо равно k2 (i+j<=k2). Количество мальчиков в классе должно
 быть больше либо равно количеству, которое требуется девочкам для дружбы (i>=m), аналогично с девочками (i>=n)*/
            if(M > i + j && i * n == j * m  && k1 <= i + j && i + j <= k2 && i>=m && j>=n){ 
                x = i; 
                y = j;
                M = i+j;
            }
        }
    }   
    cout<< x + y << " " << x << " " << y << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k1, k2, m, n;

int x = 0, y = 0, M = 10001;

//x-мальчики, y-девочки, M- минимальное из вариантов количества учеников (10001 сначала, чтобы первый раз прошло условие внутри цикла)

cin >> k1 >> k2 >> n >> m;

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

for(int j = k1-i; j <= k2; j++){ //j=k1-i, так как сумма i+j должна быть хотя бы k1. Рассматривать варианты меньше, смысла не имеет

/* M>i+j— если сумма меньше предыдущего из меньших, то перезаписываем переменные, если больше- пропускаем. i*j== количество дружащих пар.

k1<=i+j — общее число учеников должно быть больше или равно k1 и меньше, либо равно k2 (i+j<=k2). Количество мальчиков в классе должно

быть больше либо равно количеству, которое требуется девочкам для дружбы (i>=m), аналогично с девочками (i>=n)*/

if(M > i + j && i * n == j * m && k1 <= i + j && i + j <= k2 && i>=m && j>=n){

x = i;

y = j;

M = i+j;

}

cout<< x + y << " " << x << " " << y << endl;

return 0;

}

Объяснение

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

e-olymp

ideone

Related Images:

e-olymp 1452. Кролики

14/10/2018 by Владимир Дроздин

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

Задача

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

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

Первая строка содержит количество месяцев [latex] n [/latex] [latex] (0 ≤ n ≤ 100) [/latex], вторая — число кроликов [latex] k [/latex] [latex] (0 ≤ k ≤ 10000) [/latex], которое съедал монстр.

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

Определить количество кроликов, которое будет находиться на планете ТТВ через [latex] n [/latex] месяцев после поселения туда первого кролика. Известно, что результат для любого теста всегда не больше [latex] 2 \cdot 10^9 [/latex].

Тесты

#	Входные данные	Выходные данные
1	0 10	1
2	1 10	2
3	10 7	128
4	7 128	12
5	30 0	1073741824
6	29 29	2
7	20 20	16
8	90 90	64

Cпособ 1 (с циклом)

Код

#include <iostream>
using namespace std;
 
int main() {
    long int r = 1, n, k;
    cin >> n >> k;
    for (int i = n; i > 0; i--){
        if (r > k) r -= k;
        r *= 2;
    }
    cout << r;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long int r = 1, n, k;

cin >> n >> k;

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

if (r > k) r -= k;

r *= 2;

}

cout << r;

return 0;

}

Решение

Известно, что изначально на планете был один кролик. Создадим цикл, который будет высчитывать популяцию кроликов на планете через [latex] n [/latex] месяцев после прибытия. Цикл будет работать до тех пор, пока количество месяцев будет больше нуля. В нем будем высчитывать популяцию кроликов по простой формуле [latex] r = r \cdot 2 [/latex], где [latex] r [/latex] — количество кроликов. Если же количество кроликов, съедаемых монстром в начале месяца строго больше того количества, которое уже есть на планете, то от этой популяции отнимем [latex] k [/latex]кроликов : [latex] r = r[/latex] $-$ [latex] k [/latex]. Внутри цикла также не забываем от данного количества [latex] n [/latex] месяцев отнимать по одному каждый раз.

Способ 2 (без цикла)

Код

#include <iostream>
using namespace std;

int f2(long int r, long int n, long int k){
    if (n == 0) return r;
    if (r <= k) return f2(r * 2, n - 1, k);
    return f2(2 * (r-k), n - 1, k);
}   

int main() {
    long int n, k, r = 1;
    cin >> n >> k;
    cout << f2(r, n, k);
    return 0;
}

#include <iostream>

using namespace std;

int f2(long int r, long int n, long int k){

if (n == 0) return r;

if (r <= k) return f2(r * 2, n - 1, k);

return f2(2 * (r-k), n - 1, k);

}

int main() {

long int n, k, r = 1;

cin >> n >> k;

cout << f2(r, n, k);

return 0;

}

Решение

Сам алгоритм похож на 1 способ, однако здесь мы будем использовать рекурсивную функцию, а не цикл. Функция int f2(); будет вызывать сама себя до тех пор, пока количество месяцев [latex] n [/latex] не станет равным нулю.

Ссылки

Засчитанное решение на e-olymp.

1 Код в ideone.

2 Код в ideone.

Related Images:

e-olymp 891. Покупка цветов

14/10/2018 by Иван Киреев

Задача. Покупка цветов

На День учителя Вася решил купить букет цветов. В магазине продаются ромашки по $a$ рублей за штуку и гладиолусы по $b$ рублей за штуку ($a < b$). У Васи есть $c$ рублей. Он хочет составить букет из максимально возможного количества цветов, и при этом потратить как можно больше денег. Другими словами, из всех букетов с максимально возможным количеством цветов он хочет выбрать самый дорогой, но не дороже $c$ рублей. Помогите ему вычислить стоимость такого букета.

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

Три целых числа $a$, $b$, $c$ ($1 ≤ a < b ≤ 100, 0 ≤ c ≤ 1000$).

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

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

Тесты

№	Ввод	Вывод
1	5 7 0	0
2	3 5 10	9
3	2 3 11	11
4	48 64 306	304
5	17 20 100	100
6	13 15 260	260
7	29 53 999	986
8	17 28 16	0
7	75 100 1000	1000

Решение

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

Далее, что бы найти решение для оставшихся вариантов, необходимо найти наибольшую сумму стоимостей максимального количества цветов не превышающую $c$ рублей. Максимальное количество цветов n будет равно количеству цветов с минимальной стоимостью которое можно купить за имеющиеся у Васи деньги. ($c / a$).

Что бы оптимизировать код будем проверять условия в цикле с обоих концов (меняя местами количество ромашек и гладиолусов), таким образом мы выполним его за в 2 раза меньшее количество проходов и быстрее найдём максимум. А так же при равенстве искомого значения с его максимально возможным остановим проверку.

Код

#include <iostream>
using namespace std;

int main() {
    int a, b, c, max;
    cin >> a >> b >> c;
    if (c % a == 0) max = c;
    else {
        int n = c / a; // максимальное количество цветков
        max = 0;
        for (int i = 0; i <= (n / 2) && max != c; i++) {
            int first = (n - i) * b +  i * a;
            if (first > max && first <= c) max = first;
            int second = (n - i) * a +  i * b;
            if (second > max && second <= c) max = second;
        } 
    }
    cout << max;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, c, max;

cin >> a >> b >> c;

if (c % a == 0) max = c;

else {

int n = c / a; // максимальное количество цветков

max = 0;

for (int i = 0; i <= (n / 2) && max != c; i++) {

int first = (n - i) * b + i * a;

if (first > max && first <= c) max = first;

int second = (n - i) * a + i * b;

if (second > max && second <= c) max = second;

}

cout << max;

return 0;

}

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

Решение

Код на ideone

Related Images:

e-olymp 8533. Числа с разными цифрами

04/10/2018 by Никита Семерня

Задача

Выведите все четырехзначные числа от $a$ до $b$, содержащие разные цифры.

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

Два целых числа $a$ и $b$ ([latex]1000 \le a \le b \le 9999[/latex]).

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

Выведите в одной строке все числа от $a$ до $b$ с разными цифрами.

Тесты

Входные данные	Выходные данные
2000 2015	2013 2014 2015
9875 9999	9875 9876
1000 1234	1234
3612 3612	3612
8800 8888	Standart output is empty
1000 1000	Standart output is empty

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

#include <iostream>
using namespace std;
 
int main() {        
    int x, y;                               // границы поиска
    cin >> x >> y;                          
    for (int i = x; i < y + 1; i++){
        int a = i / 1000;                   // цифры 
        int b = (i / 100) % 10;
        int c = (i / 10) % 10;
        int d = i % 10;
        if ( (a != b) && (a != c)           // проверка разности
        && (a != d) && (b != c)
        && (b != d) && (c != d) )
            cout << i << ' ';
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x, y; // границы поиска

cin >> x >> y;

for (int i = x; i < y + 1; i++){

int a = i / 1000; // цифры

int b = (i / 100) % 10;

int c = (i / 10) % 10;

int d = i % 10;

if ( (a != b) && (a != c) // проверка разности

&& (a != d) && (b != c)

&& (b != d) && (c != d) )

cout << i << ' ';

}

return 0;

}

Решение

Для каждого числа из заданного промежутка [latex][a;b][/latex] выделяем его цифры и сравниваем их между собой. Искомые числа будут состоять из неравных между собой цифр.

Ссылки

Ideone

e-olymp

Related Images:

e-olymp 446. Ровные делители

18/09/2018 by Александр Дьяченко

Задача

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

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

Натуральное число $n \space (1 ≤ n ≤ 10^{6})$.

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

Выведите искомое количество ровных делителей числа $n$.

Тесты

Входные данные	Выходные данные
5	1
20	2
200	6
653	1
5982	4

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

#include <iostream>
using namespace std;

int main() {
    unsigned n, q = 0;
    cin >> n;
    for (int m = 1; m <= n; m++)
        if (n / m == n % m)
            q += 1;
    cout << q;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned n, q = 0;

cin >> n;

for (int m = 1; m <= n; m++)

if (n / m == n % m)

q += 1;

cout << q;

return 0;

}

Решение

Для решения этой задачи сперва введем переменную q, в которой будем хранить количество ровных делителей числа $n$. Затем запустим цикл, который будет проверять каждое из чисел от $1$ до $n$ включительно, является ли оно ровным делителем. Если условие выполняется, то увеличиваем значение, хранящееся в q на единицу. После цикла выведем искомое на экран.

Ссылки

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

Related Images:

Строчная таблица

11/07/2018 by Костя Григорян

Задача

В тридесятом государстве объявлено соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер $1 \times n$. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Задача участников — начертить таблицу наименьшей высоты и вычислить ширину каждой ячейки. Алиса очень хочет победить, но она плохо знает математику, поэтому она просит Вас помочь ей в этом непростом деле.

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

Первая строка содержит натуральное число $n, \ (1 \leqslant n \leqslant 100).$ Вторая строка содержит $n$ натуральных чисел — $s_1, s_2, \cdots , s_{n-1}, s_n$ — минимальные площади каждой ячейки $(1 \leqslant s_i \leqslant 100).$

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

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

Тесты

Входные данные	Выходные данные
$3$	$0.1333 \ 0.3333 \ 0.5333$
$2 \ 5 \ 8$
$6$	$0.0736 \ 0.2638 \ 0.3313 \ 0.0736 \ 0.1963 \ 0.0613$
$12 \ 43 \ 54 \ 12 \ 32 \ 10$
$2$	$0.3333 \ 0.6667$
$1 \ 2$
$3$	$0.3333 \ 0.3333 \ 0.3333$
$10 \ 10 \ 10$
$7$	$0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.1250 \ 0.2500$
$1 \ 1 \ 1 \ 1 \ 1 \ 1 \ 2$
$1$	$1.0000$
$2$
$4$	$0.5102 \ 0.1735 \ 0.2653 \ 0.0510$
$100 \ 34 \ 52 \ 10$
$2$	$0.9901 \ 0.0099$
$100 \ 1$
$6$	$0.0702 \ 0.2515 \ 0.3158 \ 0.0351 \ 0.1287 \ 0.1988$
$12 \ 43 \ 54 \ 6 \ 22 \ 34$
$2$	$0.5000 \ 0.5000$
$2 \ 2$
$10$	$0.0182 \ 0.0364 \ 0.0545 \ 0.0727 \ 0.0909 \ 0.1091 \ 0.1273 \ 0.1455 \ 0.1636 \ 0.1818$
$1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 \ 10$
$3$	$0.0098 \ 0.9804 \ 0.0098$
$1 \ 100 \ 1$

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

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long double s[n], h=0;
    for(int i=0; i<n; i++)
    {
        cin >> s[i];
        h+=s[i];
    }
    for(int i=0; i<n; i++)
    {
        cout.precision(4);
        cout << fixed << s[i]/h << " ";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

long double s[n], h=0;

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

{

cin >> s[i];

h+=s[i];

}

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

{

cout.precision(4);

cout << fixed << s[i]/h << " ";

}

return 0;

}

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

Пусть $h=\displaystyle\frac{1}{\gamma}$ — высота таблицы, а $x_1, \ x_2, \ \cdots, \ x_{n-1}, \ 1-x_1-x_2- \cdots -x_{n-1}$ – ширина каждой клетки. Тогда $\displaystyle\frac{x_1}{\gamma} \geqslant s_1, \ \displaystyle\frac{x_2}{\gamma} \geqslant s_2, \ \cdots, \ \displaystyle\frac{x_{n-1}}{\gamma} \geqslant s_{n-1}, \ \displaystyle\frac{1-x_1-x_2- \cdots -x_{n-1}}{\gamma} \geqslant s_n.$ Получаем $x_1 \geqslant s_1\gamma, \ x_2 \geqslant s_2\gamma, \ \cdots, \ x_{n-1} \geqslant s_{n-1}\gamma, \ 1-x_1-x_2- \cdots -x_{n-1} \geqslant s_n\gamma.$
Сделаем из неравенств равенства: $x_1=s_1\gamma+\varepsilon_1, \ x_2=s_2\gamma+\varepsilon_2, \ \cdots, \ x_{n-1}=s_{n-1}\gamma+\varepsilon_{n-1}.$
Имеем
$1-(s_1\gamma+\varepsilon_1)-(s_2\gamma+\varepsilon_2)- \cdots -(s_{n-1}\gamma+\varepsilon_{n-1}) \geqslant s_n\gamma \\
1 \geqslant (s_1+s_2+ \cdots +s_{n-1}+s_n)\gamma+\varepsilon_1+\varepsilon_2+ \cdots +\varepsilon_{n-1}
\\
\gamma \leqslant \displaystyle\frac{1-\varepsilon_1-\varepsilon_2- \cdots -\varepsilon_{n-1}}{s_1+s_2+ \cdots +s_{n-1}+s_n}.$
Максимальное значение $\gamma$ достигается при $\varepsilon_1=\varepsilon_2= \cdots =\varepsilon_{n-1}=0.$ Следовательно $\gamma \leqslant \displaystyle\frac{1}{s_1+s_2+ \cdots +s_{n-1}+s_n},$ а $h=s_1+s_2+ \cdots +s_{n-1}+s_n.$ Тогда ширина каждой ячейки будет равняться $\displaystyle\frac{s_i}{h}$

Ссылки

Код решения

Related Images:

e-olymp 2814. Быстрое возведение в степень.

03/07/2018 by Никита Пушкин

Задача

Быстрое возведение в степень

Очень часто возникает задача эффективного вычисления $x^{n}$ по данным $x$ и $n$, где $n$ — положительное целое число.
Предположим, например, что необходимо вычислить $x^{16}$. Можно просто начать с $x$ и 15 раз умножить его на $x$. Но тот же ответ можно получить всего за четыре умножения, если несколько раз возвести в квадрат получающийся результат, последовательно вычисляя $x^{2}$, $x^{4}$, $x^{8}$, $x^{16}$.
Эта же идея, в целом, применима к любому значению $n$ следующим образом. Запишем $n$ в виде числа в двоичной системе счисления (убирая нули слева). Затем заменим каждую «1» парой символов SX, а каждый «0» — символом S и вычеркнем крайнюю слева пару символов SX. Результат представляет собой правило вычисления $x^{n}$, в котором «S» трактуется как операция возведения в квадрат, а «X» — как операция умножения на $x$. Например, $n = 23$ имеет двоичное представление $10111$. Таким образом, мы формируем последовательность SXSSXSXSX, из которой удаляем начальную пару SX для получения окончательного правила SSXSXSX. Это правило гласит, что необходимо «возвести в квадрат, возвести в квадрат, умножить на $x$, возвести в квадрат, умножить на $x$, возвести в квадрат и умножить на $x$», т.е. последовательно вычислить значения $x^{2}$, $x^{4}$, $x^{5}$, $x^{10}$, $x^{11}$, $x^{22}$, $x^{23}$.

Вам нужно для заданного n сформулировать соответствующее правило быстрого возведения числа $x$ в степень $x^{n}$

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

Одно натуральное число $n$, не превышающее $2 \cdot 10^{9}$.

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

Выведите строку для правила возведения числа $x$ в степень $n$ для получения $x^{n}$.

Тесты

#	Входные данные	Выходные данные
1	23	SSXSXSX
2	1
3	16	SSSS
4	1000000	SXSXSXSSXSSSSSXSSSXSSSSSS
5	2018	SXSXSXSXSXSSSSXS

#include <iostream>

using namespace std;

int main() {
    long long n, k = 0;
    cin >> n;
    int c = 0;
    while (n > 1) {
        long long bit = n & 1;
        n >>= 1;
        k <<= 1;
        k |= bit;
        c += 1;
    }
    while (c--) {
        long long bit = k & 1;
        k >>= 1;
        cout << (bit == 0 ? "S" : "SX");
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long n, k = 0;

cin >> n;

int c = 0;

while (n > 1) {

long long bit = n & 1;

n >>= 1;

k <<= 1;

k |= bit;

c += 1;

}

while (c--) {

long long bit = k & 1;

k >>= 1;

cout << (bit == 0 ? "S" : "SX");

}

return 0;

}

Решение

С помощью первого цикла while в переменную $k$ записываем перевернутый двоичный код числа $n$. Переменную $c$ используем как счётчик кол-ва бит в $n$. Во втором цикле while выводим S или SX если правый бит $0$ или $1$ соответственно, теряя при это последнюю $1$ как и сказано по условию задачи.

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

Related Images:

e-olymp 2817. Двоичные числа

28/06/2018 by Павел Жуков

Задача

Для заданного положительного целого числа $n$, распечатать позиции всех $1$ в двоичном его представлении. Позиция младшего бита имеет номер $0$.
Позиции $1$ в двоичном представлении числа $13$ — это $0$, $2$, $3$.
Напишите программу, которая для каждого набора данных:

читает натуральное число $n$,
вычисляет позиции $1$ в двоичном представлении $n$,
выводит результат.

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

В первой строке входного файла содержится одно натуральное число $d$, указывающее количество наборов входных данных, $1 \leq d \leq 10$. Входные данные заданы ниже.

Каждый набор данных состоит ровно из одной строки, содержащей ровно одно целое число $n$, $0 \leq n \leq 10^6$.

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

Вывод должен состоять ровно из $d$ строк — по одной строке для каждого набора входных данных.

Строка $i$, $1 \leq i \leq d$, должна содержать возрастающую последовательность целых чисел, разделенных одним пробелом — позиции $1$ в двоичном представлении $i$-го числа, полученного во входных данных.

Тесты

Входные данные	Выходные данные
$3$ $17$ $7$ $5$	$0$ $4$ $0$ $1$ $2$ $0$ $2$
$4$ $1945$ $1337$ $1000000$ $999999$	$0$ $3$ $4$ $7$ $8$ $9$ $10$ $0$ $3$ $4$ $5$ $8$ $10$ $6$ $9$ $14$ $16$ $17$ $18$ $19$ $0$ $1$ $2$ $3$ $4$ $5$ $9$ $14$ $16$ $17$ $18$ $19$
$10$ $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$	$0$ $1$ $0$ $1$ $2$ $0$ $2$ $1$ $2$ $0$ $1$ $2$ $3$ $0$ $3$

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

#include <iostream>
using namespace std;

int main() {
    int d;
    cin >> d;
    for (int j = 0; j < d; ++j){ 
        int n; 
        bool w = false;
        cin >> n;
        for (int i = 0; n>0; ++i){
            if (n % 2 == 1){
                if(w) cout << " ";
                w = true;
                cout << i;
                        }
            n /= 2;
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int d;

cin >> d;

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

int n;

bool w = false;

cin >> n;

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

if (n % 2 == 1){

if(w) cout << " ";

w = true;

cout << i;

}

n /= 2;

}

cout << endl;

}

return 0;

}

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

Для решения этой задачи нужно понять, что остаток от деления $n$ на $2$ это последняя цифра в двоичном коде числа $n$, а деление целочисленной переменной $n$ на $2$ это отбрасывание последней цифры в двоичном коде. Цикл с счетчиком $i$ до момента, как $n$ не станет равняться $0$, очевиден, как и внешний цикл от $0$ до $d$, который реализовывает $d$ итераций ввода числа $n$. Стоит отметить, что тесты на e-olymp (все, кроме первого) чувствительны к пробелам в конце строки, из-за чего появляется необходимость каким-то образом его избежать.

Ссылки

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

Related Images:

e-olymp 1494. Санта Клаус

09/05/2018 by Томас Пасенченко

Задача

Санта Клаус

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

Помогите Санте, составьте список детей, чьи подарки надо положить в третий мешок.

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

Первая строка входного файла содержит три целых числа: [latex]n[/latex] — число детей, [latex]m[/latex] и [latex]k[/latex] — число подарков в первом и втором мешке соответственно [latex](1\leq n,\;m,\;k\leq 100;m+k\leq n)[/latex]. Вторая строка входного файла содержит [latex]m[/latex] целых чисел — номера детей, подарки для которых лежат в первом мешке. Третья строка входного файла содержит [latex]k[/latex] целых чисел — номера детей, подарки для которых лежат во втором мешке.

Гарантируется что Эльфы положили для каждого ребенка не более одного подарка. Номера всех детей являются целыми положительными числами не превосходящими [latex]n[/latex]. Все дети должны получить подарок на Рождество, иначе Санта расстроится.

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

В первой строке выведите одно число [latex]a[/latex] — сколько подарков должно быть в третьем мешке. Во второй строке выведите в произвольном порядке [latex]a[/latex] чисел — номера детей, которым эти подарки должны быть доставлены.

Тесты

Входные данные	Выходные данные
2 1 1 2 1	0
3 1 2 1 2 3	0
7 2 1 7 3 1	4 2 4 5 6
100 14 4 2 93 30 56 17 19 75 22 23 5 49 11 8 33 91 40 81 54	82 1 3 4 6 7 9 10 12 13 14 15 16 18 20 21 24 25 26 27 28 29 31 32 34 35 36 37 38 39 41 42 43 44 45 46 47 48 50 51 52 53 55 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 76 77 78 79 80 82 83 84 85 86 87 88 89 90 92 94 95 96 97 98 99 100
10 3 5 2 5 8 3 7 1 4 9	2 6 10
61 40 5 61 20 5 3 4 9 8 49 31 20 33 35 34 61 1 32 53 51 7 21 44 46 47 2 60 50 19 25	36 5 6 10 11 12 13 14 15 16 17 18 22 23 24 26 27 28 29 30 36 37 38 39 40 41 42 43 45 48 52 54 55 56 57 58 59
12 3 3 1 2 3 11 10 8	6 4 5 6 7 9 12

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

#include <iostream>
using namespace std;

int main() {
    int n, m, k, num;
    cin >> n >> m >> k;
    bool children[n];
    for (int i = 0; i < n; i++) {
        children[i] = false;
    }
    for (int i = 0; i < m + k; i++) {
        cin >> num;
        num--;
        children[num] = true;
    }
    cout << (n - m - k) << "\n";
    for (int i = 0; i < n; i++) {
        if (!children[i]) {
            cout << (i + 1) << " ";
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m, k, num;

cin >> n >> m >> k;

bool children[n];

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

children[i] = false;

}

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

cin >> num;

num--;

children[num] = true;

}

cout << (n - m - k) << "\n";

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

if (!children[i]) {

cout << (i + 1) << " ";

}

return 0;

}

Решение

Создадим массив типа bool , в котором каждому [latex]i[/latex]-ому ребёнку соответствует элемент с индексом [latex]i — 1[/latex], принимающий значение [latex]0[/latex], если для ребёнка ещё нет подарка, и [latex]1[/latex], если подарок уже имеется в одном из мешков. Далее, отмечаем детей, подарки для которых уже лежат в мешках. Наконец, выводим номера тех детей, подарки для которых не были найдены ни в одном из мешков.

Ссылки

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

Related Images:

e-olymp 338. Моя любимая, несократимая…

09/05/2018 by Андрей Святозар Чернецкий

Задача

“Название задачи можно напевать на мотив марша или строевой песни…”

Сколько существует правильных несократимых дробей на промежутке [[latex]0[/latex]..[latex]1[/latex]], знаменатель которых не превышает [latex]n[/latex]?

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

Натуральное число [latex]n[/latex] ([latex]n < 10001[/latex]).

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

Вывести количество правильных несократимых дробей на промежутке [[latex]0..1[/latex]], знаменатель которых не превышает [latex]n[/latex].

Тесты

Входные данные	Выходные данные
1	0
10000	30397485
5	9
80	1965
37	431
5168	8119803
9973	30237929

#include <iostream>

using namespace std;

int euler_f (int n) { 
    int result = n;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            while (n % i == 0) n /= i; 
            result -= result / i; 
        } 
    }
    if (n > 1) result -= result / n; 
    return result;
}

int main() {
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 2; i <= n; ++i) {
        sum += euler_f(i);
    }
    cout << sum;
    return 0;
}

#include <iostream>

using namespace std;

int euler_f (int n) {

int result = n;

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

if (n % i == 0) {

while (n % i == 0) n /= i;

result -= result / i;

}

if (n > 1) result -= result / n;

return result;

}

int main() {

int n;

cin >> n;

int sum = 0;

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

sum += euler_f(i);

}

cout << sum;

return 0;

}

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

Для решения данной задачи вопользуемся функцией Эйлера [latex] \varphi (n)[/latex], равной количеству натуральных чисел, меньших [latex]n[/latex] и взаимно простых с ним. Очевидно, что количество правильных несократимых дробей со знаменателем [latex]n[/latex] равно [latex] \varphi (n)[/latex]. И тогда количество правильных дробей со знаменателем, не превыщающим [latex]n[/latex] равно [latex] \sum\limits_{i=2}^{n}{\varphi (n)}[/latex] (тут мы учли, что при [latex]i[/latex] = 1 знаменатель дроби равен 1 и дробь не будет правильной).

Ссылки

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

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

описание функции Эйлера на Wikipedia

Related Images:

e-olymp 842. Разложение на простые множители

14/04/2018 by Иван Василевский

Условие задачи
Вывести представление целого числа [latex] n [/latex] в виде произведения простых чисел.

Входные данные
Единственное число [latex] n [/latex] [latex] (2 ≤ n ≤ 2^{31} — 1). [/latex]

Выходные данные
Вывести список простых множителей в порядке не убывания, разделённых знаком [latex] «*» [/latex] .
Continue reading →

Related Images:

e-olymp 1489. Шоколад

13/04/2018 by Илья Черноморец

Задача

Петя очень любит шоколад. И Маша очень любит шоколад. Недавно Петя купил шоколадку и теперь хочет поделиться ею с Машей. Шоколадка представляет собой прямоугольник $n \cdot m$, который полностью состоит из маленьких шоколадных долек — прямоугольников $2 \cdot 1$.

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

Помогите Пете поделиться шоколадкой с Машей.

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

В первой строке входного файла два целых числа $n$ и $m$ ($1 \le n, m \le 20$, хотя бы одно из чисел $n$ и $m$ — четно). Далее следуют $n$ строк по $m$ чисел в каждой — номера долек, в которые входят соответствующие кусочки шоколадки. Дольки имеют номера от $1$ до $\frac{n \cdot m}{2}$, и никакие две дольки не имеют одинаковые номера.

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

В выходной файл выведите «$Yes$», если Петя может разломать шоколадку, не повредив дольки. Иначе выведите «$No$».

TESTS

Входные данные	Выходные данные
2 3 1 1 2 3 3 2	Yes
5 6 1 2 2 3 3 4 1 5 6 7 7 4 8 5 6 9 10 10 8 11 11 9 12 13 14 14 15 15 12 13	No
4 7 1 1 2 5 8 11 6 2 14 4 7 3 9 5 3 7 10 6 13 2 3 4 3 8 12 5 7 7	Yes

Код решения

#include <iostream>
using namespace std;


bool BreakRow (int **chocolate, int n, int m){
  for (int i = 0; i < n - 1; i++){
    bool okRow = true;
    for (int j = 0; j < m; j++){
      if(chocolate[i][j] == chocolate [i + 1][j]){okRow = false;break;}
    }
    if (okRow) return true;
  }
  return false;
}
bool BreakColumn (int **chocolate, int n, int m){
  for (int i = 0; i < m - 1; i++){
    bool okColumn = true;
    for (int j = 0; j < n; j++){
      if(chocolate[j][i] == chocolate[j][i + 1]){okColumn = false;break;}
    }
    if (okColumn) return true;
  }
  return false;
}

int check (int **chocolate, int n, int m){
  if ( BreakRow(chocolate, n, m) || BreakColumn (chocolate, n, m)) cout<<"Yes";
  else cout<<"No";
}

int main() {
  int n, m;
  cin >> n >> m;
  int **chocolate = new int* [n];
  for(int i = 0; i < n; ++i){
    chocolate[i] = new int[m];
  }
  for( int i = 0; i < n;  i++){
    for(int j = 0; j < m; j++){
      cin >> chocolate [i][j];
    }
  }
  check(chocolate, n, m);
  return 0;
}

#include <iostream>

using namespace std;

bool BreakRow (int **chocolate, int n, int m){

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

bool okRow = true;

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

if(chocolate[i][j] == chocolate [i + 1][j]){okRow = false;break;}

}

if (okRow) return true;

}

return false;

}

bool BreakColumn (int **chocolate, int n, int m){

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

bool okColumn = true;

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

if(chocolate[j][i] == chocolate[j][i + 1]){okColumn = false;break;}

}

if (okColumn) return true;

}

return false;

}

int check (int **chocolate, int n, int m){

if ( BreakRow(chocolate, n, m) || BreakColumn (chocolate, n, m)) cout<<"Yes";

else cout<<"No";

}

int main() {

int n, m;

cin >> n >> m;

int **chocolate = new int* [n];

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

chocolate[i] = new int[m];

}

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

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

cin >> chocolate [i][j];

}

check(chocolate, n, m);

return 0;

}

Решение

Для решения данной задачи нужно представить шоколадку как двухмерный массив и проверить, можно ли разломать плитку шоколада ровно, то есть одинаковое ли количество «строк» и «столбцов» шоколада. Если так, то возвращается значение true, и false в обратном случае. Для этого были созданы функции BreakRow и BreakColumn с возвращаемым значением типа bool. Затем стоит проверить возвращаемое значение. Если одна из функций принимает значение true, то выводим положительный ответ. В противном случае ответ отрицательный.

Ссылки

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

Related Images:

e-olimp 2864. Табулирование функции

04/04/2018 by Антон Джашимов

Задача

Напишите программу, которая выводит на экран таблицу значений функции [latex]y = 3\sin\left(x\right) [/latex] на промежутке от [latex]a[/latex] до [latex]b[/latex] включительно с шагом [latex]h[/latex].

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

В одной строке через пробел заданы три вещественных числа [latex]a[/latex], [latex]b[/latex] и [latex]h[/latex].

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

В каждой строке выведите по два числа [latex]x[/latex] и [latex]y[/latex] соответственно, по возрастанию [latex]x[/latex] с тремя десятичными знаками.

Тесты

Входные данные	Выходные данные
1 2 0.5	1.000 2.524 1.500 2.992 2.000 2.728
0 0 1	0.000 0.000
20 10 5	10.000 -1.632 15.000 1.951 20.000 2.739
-3 -1 1	-3.000 -0.423 -2.000 -2.728 -1.000 -2.524

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

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main() {
    double a, b, h;
    cin >> a >> b>> h;
    for (double x = a; x <= b; x += h) {
        cout << fixed << setprecision(3) <<x<< " " << 3 * sin(x) << endl;
    }
    return 0;
}

#include <iostream>

#include <cmath>

#include <iomanip>

using namespace std;

int main() {

double a, b, h;

cin >> a >> b>> h;

for (double x = a; x <= b; x += h) {

cout << fixed << setprecision(3) <<x<< " " << 3 * sin(x) << endl;

}

return 0;

}

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

Подключим модули cmath, чтобы использовать функцию синус, и iomanip, для установления точности ответа. Далее, с помощью цикла от [latex]a[/latex] до [latex]b[/latex] с шагом [latex]h[/latex] выведем на экран таблицу значений функции на заданном промежутке.

Ссылки

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

Код решения

Related Images:

e-olymp 622. Единицы

21/01/2018 by Бондаренко Кирилл

Единицы

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

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

Одно целое число [latex]n[/latex] [latex](0 ≤ n ≤ 2\cdot10^9)[/latex].

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

Вывести количество единиц в двоичной записи числа [latex]n[/latex].

Тесты

Входные данные	Выходные данные
20	2
0	0
1	1
5	2
2000000000	13

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

#include <iostream>
using namespace std;

int main() {
    int k=0, n;
    cin >> n;
    while (n > 0){   
        k += (n % 2);
        n = n / 2;
    }
    cout << k;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k=0, n;

cin >> n;

while (n > 0){

k += (n % 2);

n = n / 2;

}

cout << k;

return 0;

}

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

Алгоритм заключается в последовательном делении заданного числа [latex]n[/latex] на [latex]2[/latex] и нахождении количества остатков от деления (по условию), равных единице. Полагаем начальное количество единиц [latex]k[/latex] равное нулю. Затем, нужно прибавить остаток от деления к имеющемуся у нас [latex]k[/latex]. Если остаток равен единице то мы получим [latex]k+1[/latex] что нам и требуется.

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

Related Images:

e-olymp 340. Раз – горох, два – горох…

02/01/2018 by Карина Миловская

Задача

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

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

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

В первой строке натуральное четное число [latex]M[/latex] – количество украденных стручков, [latex]2 ≤ M ≤ 1000[/latex].

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

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

Тесты

Входные данные	Выходные данные
[latex]6[/latex]	[latex] \\ 6 \; 0 \\ 2 \; 4[/latex]
[latex]11[/latex]	[latex]\\ 11\;0 \\ 7\;4 \\ 3\;8[/latex]
[latex]18[/latex]	[latex]\\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16[/latex]

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

#include <iostream>
using namespace std;
 
int main() {
    int a, b = 0;
    cin >> a;
    while (a >= 0) {
        cout << a << " " << b << "\n";
        a -= 4; b += 4;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b = 0;

cin >> a;

while (a >= 0) {

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

a -= 4; b += 4;

}

return 0;

}

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

Пусть [latex]a[/latex] — количество стручков, принесенных Хомой и [latex]b[/latex] — количество стручков, принесенных Сусликом. Так как по условию задачи Хома таскал только по четыре стручка, мы будем считать [latex]a = a-4[/latex] и [latex]b = b + 4[/latex], чтобы таким образом перебрать все возможные сочетания количеств стручков, принесенных Сусликом и Хомой. Также воспользуемся циклом while, который будет повторять действие, описанное выше, до тех пор, пока [latex]a \geq 0[/latex]. В ответе выводим все возможные сочетания количеств стручков, принесенных друзьями по одному в строке, упорядоченные по убыванию первого числа.

Ссылки

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

Related Images:

e-olymp 9. N-значные числа

02/01/2018 by Андрей Лисовой

Задача

Найти количество [latex]N[/latex]-значных чисел, у которых сумма цифр равна их произведению. Вывести наименьшее среди таких чисел для заданного [latex]N[/latex] ([latex]N < 10[/latex]).

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

Число [latex]N[/latex] не превышающее [latex]10[/latex].

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

В выходном файле через пробел вывести [latex]2[/latex] числа: количество искомых чисел и наименьшее среди них.

Тесты

Входные данные	Выходные данные
[latex]1[/latex]	[latex]10[/latex] [latex]0[/latex]
[latex]2[/latex]	[latex]1[/latex] [latex]22[/latex]
[latex]4[/latex]	[latex]12[/latex] [latex]1124[/latex]
[latex]5[/latex]	[latex]40[/latex] [latex]11125[/latex]
[latex]9[/latex]	[latex]144[/latex] [latex]111111129[/latex]

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

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

int Sum(int a) {
    int sum=0;
    while(a>0) {
        sum+=a%10;
        a/=10;
    }
    return sum;
}

int Mult(int a) {
    int mult=1;
    while(a>0) {
        mult*=a%10;
        a/=10;
    }
    return mult;
}

int main() {
    int n,ch=0,sum=0,mult=0,a;
    bool b=true;
    cin>>n;
    if(n==1) cout<<10<<" "<<0;
    else {
        if(n>1 and n<8) {
            for(int i=pow(10,n-1); i<pow(10,n); i++) {
                sum=Sum(i);
                mult=Mult(i);
                if((sum==mult) and b==true) {a=i;ch++;b=false;}
                else {
                    if(sum==mult) ch++;
                }
            }
            cout<<ch<<" "<<a;
        }
        else {
            if(n==8) cout<<224<<" "<<11111128;
            if(n==9) cout<<144<<" "<<111111129;
        }
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int Sum(int a) {

int sum=0;

while(a>0) {

sum+=a%10;

a/=10;

}

return sum;

}

int Mult(int a) {

int mult=1;

while(a>0) {

mult*=a%10;

a/=10;

}

return mult;

}

int main() {

int n,ch=0,sum=0,mult=0,a;

bool b=true;

cin>>n;

if(n==1) cout<<10<<" "<<0;

else {

if(n>1 and n<8) {

for(int i=pow(10,n-1); i<pow(10,n); i++) {

sum=Sum(i);

mult=Mult(i);

if((sum==mult) and b==true) {a=i;ch++;b=false;}

else {

if(sum==mult) ch++;

}

cout<<ch<<" "<<a;

}

else {

if(n==8) cout<<224<<" "<<11111128;

if(n==9) cout<<144<<" "<<111111129;

}

return 0;

}

Решение задачи (Цикл)

Для решения задачи напишем функции [latex]Sum[/latex] и [latex]Mult[/latex]. Первая считает сумму цифр [latex]N[/latex]-значного числа, а вторая — произведение цифр. С помощью цикла создаем последовательность [latex]N[/latex]-значных чисел и вводим каждое из них в функции [latex]Sum[/latex] и [latex]Mult[/latex]. Если возращаемые значения равны между собой, то мы выводим данное число и присваиваем переменной [latex]b[/latex] значение [latex]false[/latex]. Также продолжаем считать количество [latex]N[/latex]-значных чисел у которых сумма цифр равна их произведению. Также создаем случаи, когда [latex]N=1[/latex], [latex]N=8[/latex] и [latex]N=9[/latex], ибо в цикле эти значения долго считаются. Задача решена.

Код программы (Массив)

#include <iostream>
using namespace std;

int main() {
    int x[18]= {10,0,1,22,6,123,12,1124,40,11125,30,111126,84,1111127,224,11111128,144,111111129};
    int n;
    cin>>n;
    cout<<x[2*n-2]<<" "<<x[2*n-1];
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x[18]= {10,0,1,22,6,123,12,1124,40,11125,30,111126,84,1111127,224,11111128,144,111111129};

int n;

cin>>n;

cout<<x[2*n-2]<<" "<<x[2*n-1];

return 0;

}

Решение задачи (Массив)

Для решения задачи заранее просчитали все ответы и записали их в массив [latex]x[/latex]. Так как ответы идут подряд составили формулу для вывода искомых значений: для количества чисел у которых сумма цифр совпадает с их произведением — [latex]2n-2[/latex], для минимального числа — [latex]2n-1[/latex]. Задача решена (также задачу можно решить с помощью циклов).

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com (цикл)
Код решения на ideone.com (массив)

Related Images:

e-olymp 2807. Кубики — 3

31/12/2017 by Валерия Ларикова

Задача

Дома у Витека было [latex]2[/latex] одинаковых набора кубиков из английских букв, но во время очередной уборки один из кубиков затерялся. Помогите Витеку определить, какой же из кубиков отсутствует в одном из наборов.

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

В первой строке задано количество найденных Витеком кубиков [latex]n (1 ≤ n ≤ 10^5)[/latex], а во второй строке [latex]n[/latex] символов, изображённых на каждом из кубиков.

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

Выведите букву, изображённую на потерявшемся кубике, либо сообщение [latex] «Ok»[/latex], если Витек ошибся и ни один из кубиков не потерялся.

Тесты

#	Входные данные	Выходные данные
1	5 abcac	b
2	8 ryirhiyh	Ok
3	3 AVA	V
4	6 DjkjDk	Ok
5	7 LnCsCnL	s

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

#include <iostream>
#include <string>//данная библиотека содержит методы и переменные для работы со строками
using namespace std;

int main() {
    int n;
    cin >> n;
    if (n % 2 == 0) cout << "Ok";
    else {
        int x[200];
        for ( int i = 65; i <= 122; i++)
            x[i] = 0;
        char c;
        while ((c = cin.get()) != EOF)
            x[c]++;
        for (int i = 'A'; i <= 'z'; i++)
            if (x[i] % 2 != 0) 
                c = i;
        cout << c;
    }
    return 0;
}

#include <iostream>

#include <string>//данная библиотека содержит методы и переменные для работы со строками

using namespace std;

int main() {

int n;

cin >> n;

if (n % 2 == 0) cout << "Ok";

else {

int x[200];

for ( int i = 65; i <= 122; i++)

x[i] = 0;

char c;

while ((c = cin.get()) != EOF)

x[c]++;

for (int i = 'A'; i <= 'z'; i++)

if (x[i] % 2 != 0)

c = i;

cout << c;

}

return 0;

}

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

Для того, чтобы решить задачу, мы проверяем четное ли количество кубиков, найденных Витеком. Если условие выполняется, то выводим на экран сообщение с текстом [latex] «Ok»[/latex]. Если нет, то рассматриваем второй случай. Создаем массив, в котором будем хранить количество кубиков для каждой буквы. Обнуляем ячейки массива, в которых будут храниться данные. Далее мы будем считывать символы в соответствии с их числовыми кодами. После прочтения входного потока, найдем элемент массива с нечетным числом вхождений и выведем его на экран.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

Related Images:

e-olymp 27. Циклические сдвиги

30/12/2017 by Мороз Дима

Задача

Циклический сдвиг

Запишем целое десятичное число $n$ в двоичной системе счисления и образуем все левые циклические сдвиги числа $n$, у которых первая цифра числа переносится в конец.

Например, если $n = 11$, то в двоичной системе это $1011$_$2$, его циклические сдвиги: $0111$_$2$, $1110$_$2$, $1101$_$2$, $1011$_$2$. Максимальное значение $m$ у всех полученных таким образом чисел будет иметь число $1110$_$2$ $=$ $14$_$10$.

Для заданного числа $n$ определить максимальное значение $m$.

Входные данные: одно число $n \left(1 ≤ n ≤ 2 \cdot 10^9\right)$.

Выходные данные: искомое число $m$.

Тесты

Входные данные	Выходные данные
11	14
23	30
256	256
257	384
34132	43664

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

#include <iostream>
using namespace std;

int main(){
    unsigned long in_val, tmp_val, power = 1;
    cin >> in_val;
    tmp_val = in_val;
    while(tmp_val){
        tmp_val /= 2;
        power *= 2;
    }
    tmp_val = in_val;
    unsigned long max_val = in_val;
    do{
        in_val = in_val << 1;
        in_val = in_val % power + (in_val >= power ? 1 : 0);
        if (max_val < in_val) max_val = in_val;
    }while (tmp_val != in_val );
    cout << max_val << endl;
    
    return 0;
}

#include <iostream>

using namespace std;

int main(){

unsigned long in_val, tmp_val, power = 1;

cin >> in_val;

tmp_val = in_val;

while(tmp_val){

tmp_val /= 2;

power *= 2;

}

tmp_val = in_val;

unsigned long max_val = in_val;

do{

in_val = in_val << 1;

in_val = in_val % power + (in_val >= power ? 1 : 0);

if (max_val < in_val) max_val = in_val;

}while (tmp_val != in_val );

cout << max_val << endl;

return 0;

}

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

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

Возможный вариант решения задачи

Возможно избавиться от первого цикла путем нахождения количества двоичных разрядов кратных степени двойки с помощью:
1. взятия логарифма числа по основанию $2$ с последующим округлением до целого;
2. возведение двойки в степень, полученную выше, и увеличенную на единицу.
То есть $2^{\lfloor \log_{2}n \rfloor + 1}$.

Тогда код будет выглядеть так:

#include <iostream>
#include <math.h>
using namespace std;

int main(){
    unsigned long in_val, tmp_val;
    cin >> in_val;
    tmp_val = in_val;
    unsigned long power;
    power = pow(2, floor(log2(in_val)) + 1);
    tmp_val = in_val;
    unsigned long max_val = in_val;
    do{
        in_val = in_val << 1;
        in_val = in_val % power + (in_val >= power ? 1 : 0);
        if(max_val < in_val){
            max_val = in_val;
        }
    }while(tmp_val != in_val);
    cout << max_val << endl;

    return 0;
}