e-olymp 8544. Квадраты чисел

19/12/2019 by Кирилл Избаш

Задача

Выведите квадраты всех натуральных чисел не больших [latex]n[/latex] в возрастающем порядке.

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

Одно натуральное число [latex]n[/latex] [latex](n \leqslant 10^9)[/latex]

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

Выведите список квадратов всех натуральных чисел не больших [latex]n[/latex] в возрастающем порядке.

Тесты

Входные данные	Выходные данные
1	1
16	1 4 9 16
93	1 4 9 16 25 36 49 64 81
100	1 4 9 16 25 36 49 64 81 100

Код

#include <iostream>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    for(int i = 1; i * i <= n; i++) cout << i * i << ' '; 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

for(int i = 1; i * i <= n; i++) cout << i * i << ' ';

return 0;

}

Решение

Воспользуемся циклом, в котором заведем переменную [latex]i[/latex] и будем перечислять числа [latex]1, 4, 9, …, i^2[/latex], пока [latex]i^2[/latex] не будет больше [latex]n[/latex]. Выводим последовательно квадраты натуральных чисел в одной строке.

Ссылки

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

Related Images:

e-olymp 904. Увеличить на 2

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

Задача

Задана последовательность целых чисел. Увеличить на $2$ каждый ее неотрицательный элемент.

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

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

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

Вывести в одной строке $n$ чисел: новые значения элементов последовательности в том же порядке, в котором они были заданы.

Тесты

	Входные данные	Выходные данные
1	4 1 2 3 -4	3 4 5 -4
2	7 7 -3 4 -2 5 0 -1	9 -3 6 -2 7 0 -1
3	5 6 -12 28 -32 -1	8 -12 30 -32 -1
4	3 -2 -3 -4	-2 -3 -4

Код

#include <iostream>
using namespace std;
 
int main() {
    int k, x; 
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> x;
        cout << (x < 0? x: x + 2) << " ";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k, x;

cin >> k;

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

cin >> x;

cout << (x < 0? x: x + 2) << " ";

}

return 0;

}

Решение

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

Ссылки

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 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 3912. Реверс удавов

20/04/2018 by Мороз Дима

Задача

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

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

Первая строка содержит одно число $N (1 ≤ N ≤ 100000)$ – количество удавов. В следующих $N$ строках написаны имена удавов в том порядке, в котором они ползут. Имя удава – строчка, содержащая не более $10$ маленьких латинских букв.

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

Выведите единственную строку – название стаи после команды «Реверс».

Тесты

Входные данные	Выходные данные
3 abc def ghi	ghidefabc
3 zxcgh i db	dbizxcgh
4 mn kjl iu ghj	ghjiukjlmn
8 kdh jg lqwoc kfxvk iduhx nsh s kjwyv	kjwyvsnshiduhxkfxvklqwocjgkdh

Код программы (string)

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

int main () 
{
    int N;
    cin >> N;
    string flock[N];
    for (int i = 0; i < N; i++)
        cin >> flock[i];
    for (int i = N - 1; i >= 0; i--)
        cout << flock[i];
    
    return 0;
}

#include <iostream>

#include <string.h>

using namespace std;

int main ()

{

int N;

cin >> N;

string flock[N];

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

cin >> flock[i];

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

cout << flock[i];

return 0;

}

Решение задачи (string)

Записываем каждого удава в одномерный массив flock типа string размера N, а затем выводим его, начиная с конца.

Код программы (c-string)

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

#define boa_name_size 11

int main() 
{
    int N;
    cin >> N;
    char **flock = new char *[N]; // Создаем массив в N строк
    for (int i = 0; i <= N; i++)
        flock[i] = new char[boa_name_size]; // Под каждую строку выделяем массив в boa_name_size символов
    for (int i = 0; i <= N; i++)
        cin.getline(flock[i], boa_name_size);
    for (int i = N; i > 0; i--) 
        cout << flock[i];
    
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

#define boa_name_size 11

int main()

{

int N;

cin >> N;

char **flock = new char *[N]; // Создаем массив в N строк

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

flock[i] = new char[boa_name_size]; // Под каждую строку выделяем массив в boa_name_size символов

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

cin.getline(flock[i], boa_name_size);

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

cout << flock[i];

return 0;

}

Решение задачи (c-string)

Записываем каждого удава в динамический массив flock типа char размера $N$ $\times$ boa_name_size, где boa_name_size – это константа, размером в $11$ символов, которую определяем с помощью директивы #define в начале программы. Не $10$, а $11$ потому что в нуль-терминированных строках (c-string) последний символ – символ конца строки '\0'.
Далее выводим наш массив с последней строки до первой.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com (string)
Решение задачи на ideone.com (c-string)

Related Images:

e-olymp 6350. Изированная вода

09/01/2018 by Мороз Дима

Задача

Изированная вода

В Бердичеве ещё в советские времена продавалась знаменитая изированная вода. Собственно это была обычная газировка на разлив, но продавал её Изя, поэтому и воду все называли изированной. Продавец газировки был человеком не только очень умным и добродушным, но и очень сообразительным. О складе его ума говорит хотя бы тот факт, что у него было $2$ диплома о высшем образовании: он закончил физмат пединститута и мехмат университета, а о сообразительности – то, что имея два диплома, он продавал газировку и довольно успешно. Старожилы утверждают, что попить его газировки прилетали в те времена даже с самой Москвы…

Изя, герой задачи

С постоянными покупателями, и не только с ними, Изя был очень общительным человеком, и иногда, как говорится «под настроение клиента», задавал им свои задачки на сообразительность, которых у него в запасе было великое множество. Одна из подобных его задачек приведена в задаче «Покупка воды». Задав подобную задачку, он ждал от клиента быстрого, сообразительного и, главное, верного ответа на неё, если же ответ запаздывал, или был не верным, Изя всегда говорил что-то типа: «Молодой человек, придёте завтра – Вы сегодня не заслужили на обслуживание». Естественно, это была шутка и клиент всё равно имел возможность приобрести очень вкусную изированную воду.

Перед тем как сформулировать наш вопрос, напомним задачку, упоминаемую выше: «Стоимость бутылки воды, учитывая стоимость пустой бутылки, составляет $1$ руб. $20$ коп., а стоимость пустой бутылки – $20$ коп. Сколько бутылок воды можно выпить на $N$ руб., учитывая, что пустые бутылки можно сдавать, и на полученные деньги приобретать новые бутылки воды?».

Нас же будет интересовать ответ на следующий вопрос: «А сколько покупателей услышали сегодня от Изи фразу «Приходите завтра!»?».

Входные данные
В первой строке входных данных находится единственное число $N (1 ≤ N ≤ 10^6)$ — количество покупателей, которым Изя задавал упоминаемую в условии задачку.

В последующих $N$ строках задано через пробел $N$ пар чисел, первое из которых — количество денег в кошельке перед началом операции «Покупка ГазВоды», а второе — ответ покупателя.

Все входные данные — целые неотрицательные числа, не превышающие $10^9$.

Выходные данные
Вывести единственное число — количество покупателей, услышавших от продавца ответ «Придёте завтра» и при этом ответили неправильно. Подсчитывать же тех, кто долго думал, не обязательно, за Вас это сделает проверяющая система вердиктом TL (Time Limited).

Тесты

Входные данные	Выходные данные
5 2 1 2 2 1 2 1 1 2 1	3
3 45 45 38 37 12 10	2
3 5 4 7 6 3 2	0
2 1280 1280 1900 1899	1
7 1 1 2 2 3 2 6 5 6 6 7 3 2 2	5

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

#include <iostream>
using namespace std;

int main() {
    unsigned int n;
    cin >> n;
    unsigned int a, b, j = 0;
    for (n; n > 0; n--) {
        cin >> a >> b;
        if (b != a - 1) j++;
    }
    cout << j;
    
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned int n;

cin >> n;

unsigned int a, b, j = 0;

for (n; n > 0; n--) {

cin >> a >> b;

if (b != a - 1) j++;

}

cout << j;

return 0;

}

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

Для решения этой задачи необходимо решить задачу «Покупка воды». Решение очень простое: количество бутылок воды, которое можно выпить на $n$ грн. равно $n — 1$.

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