e-olymp 6388. Муха Фон-Неймана

22/12/2019 by Кирилл Колесник

Задача

Следующая задача была предложена Джону Фон-Нейману:

Два велосипедиста [latex]a[/latex] и [latex]b[/latex] начинают поездку навстречу друг другу в одно и то же время с мест, находящихся на расстоянии [latex]250[/latex] друг от друга, [latex]a[/latex] движется со скоростью [latex]10[/latex] миль в час, [latex]b[/latex] движется со скоростью [latex]15[/latex] миль в час. В это же время муха взлетает с колеса велосипедиста [latex]a[/latex] и движется навстречу к [latex]b[/latex], затем разворачивается и летит обратно. Пока велосипедисты приближаются друг к другу, муха продолжает летать между ними, касаясь каждый раз переднего колеса велосипедистов, пока, наконец, не будет раздавлена колесами встретившихся велосипедов. Так как муха летает быстрее каждого из велосипедистов, она совершает бесконечное количество полетов, при этом пройдя конечное расстояние (бесконечный ряд сходится). Какое расстояние пролетела муха?

Фон-Нейман немедленно вычислил бесконечный ряд (в уме!), и получил верный ответ: [latex]200[/latex] миль.

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

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

Первая строка содержит количество тестов [latex]p (1 \leqslant p \leqslant 1000)[/latex].

Каждый тест состоит из одной строки, содержащей пять чисел: номер теста [latex]n[/latex] и четыре действительных числа: начальное расстояние между велосипедистами [latex]d (10 \leqslant d \leqslant 1000)[/latex], скорость первого велосипедиста [latex]a (1 \leqslant a \leqslant 30)[/latex] в милях в час, скорость второго велосипедиста [latex]b (1 \leqslant b \leqslant 30)[/latex] в милях в час и скорость мухи [latex]f (a \leqslant b < f \leqslant 50)[/latex] в милях в час.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 1 250 10 15 20 2 10.7 3.5 4.7 5.5 3 523.7 15.3 20.7 33.3 4 1000 30 30 50 5 500 15 15 25	1 200.00 2 7.18 3 484.42 4 833.33 5 416.67

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

#include <iostream>
using namespace std;
 
int main() {
    double p, d, a, b, f, t, flyDist;
    int n;
    cin >> p;
    for (int i = 0; i < p; i++){
        cin >> n >> d >> a >> b >> f;
        t = d / (a + b);
        flyDist = f * t;
        cout.precision(2);
        cout << fixed << n << " " << flyDist << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double p, d, a, b, f, t, flyDist;

int n;

cin >> p;

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

cin >> n >> d >> a >> b >> f;

t = d / (a + b);

flyDist = f * t;

cout.precision(2);

cout << fixed << n << " " << flyDist << endl;

}

return 0;

}

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

Безусловно, многие ознакомленные с курсом математического анализа люди (или же юные подражатели Фон-Неймана) после ознакомления с условием задачи мгновенно подумали о сумме сходящегося бесконечного ряда. Однако, если абстрагироваться от пестрых намеков содержания и попробовать мыслить менее глобально, можно прийти к куда более простому варианту решения. На самом деле под витиеватой формулировкой таится обыкновенная задача на движение с некоторым дополнительным фактором!

Согласно условию, велосипедисты [latex]a[/latex] и [latex]b[/latex] двигаются навстречу друг другу, а следовательно их скорость сближения (общая скорость) будет равна сумме скоростей каждого из велосипедистов: [latex]a + b[/latex]. По знакомой из школьного курса математики формуле [latex]S = V \times t[/latex] (тогда [latex]t = \frac { S }{ V }[/latex]), разделив расстояние между велосипедистами [latex]d[/latex] на их скорость сближения, найдем время [latex]t[/latex], спустя которое велосипедисты встретятся: [latex]t = d / (a + b)[/latex]. Муха, перелетающая с одного колеса на другое со скоростью [latex]f[/latex] достигнет момента своей погибели ровно тогда же, когда встретятся велосипедисты, то есть спустя то же время [latex]t[/latex]. Тогда, умножив скорость мухи на это время, то есть [latex]f\times t[/latex], получим расстояние [latex]flyDist[/latex], преодолённое мухой.
Для корректной реализации кода задачи сначала считываем количество тестов [latex]p[/latex], затем создаём цикл, внутри которого считываем все необходимые для вышеописанных действий переменные, производим нужные вычисления и, с помощью функции cout.precision и замечания fixed, выводим номер теста и его результат с точностью до двух десятичных знаков.

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

Related Images:

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

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

Задача

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

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

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

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

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

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

Тесты

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

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

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

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

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

int n;

double sum = 0;

cin >> n;

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

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

}

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

}

Решение

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

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

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

Ссылки

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

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

Related Images:

e-olymp 8680. Чётные соседи

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

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

Задана последовательность целых чисел. Подсчитать количество элементов, у которых чётные соседи.

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

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

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

Вывести в одной строке количество элементов последовательности с чётными соседями.

Тесты

№	Входные данные	Выходные данные
1	6 1 2 3 4 5 6	2
2	9 3 6 3 5 2 9 1 2 5	0
3	3 2 1 2	1
4	6 13 24 54 66 44 77	2
5	4 100 224 666 222	2

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

#include <iostream>
using namespace std;

int main(){
    int i=1, n, prev, pres, fut, count = 0;
    cin >> n;
    cin >> prev; //вводим предыдущий элемент
    cin >> pres; //вводим текущий элемент
    while ((cin >> fut) && (i<n)) {
        if (prev % 2 == 0 && fut % 2 == 0) 
            count++;
        prev = pres; //приравниваем предыдущий к текущему
        pres = fut; //приравниваем текущий к будущему
        i++;
    }
    cout << count;
    return 0;
}

#include <iostream>

using namespace std;

int main(){

int i=1, n, prev, pres, fut, count = 0;

cin >> n;

cin >> prev; //вводим предыдущий элемент

cin >> pres; //вводим текущий элемент

while ((cin >> fut) && (i<n)) {

if (prev % 2 == 0 && fut % 2 == 0)

count++;

prev = pres; //приравниваем предыдущий к текущему

pres = fut; //приравниваем текущий к будущему

i++;

}

cout << count;

return 0;

}

Решение

Идея решения задачи состоит в том, чтобы создать три переменные: $prev$ (предыдущий), $pres$ (настоящий, текущий) и $fut$ (будущий). Затем в цикле мы перезаписываем эти переменные т.е.: настоящий становится прошлым, будущий настоящим, а новый будущий мы читаем из cin. Так же, в ходе решения задачи обнаружилась проблема с чтением количества элементов. Допустим, если мы записали, что $n=6$, а дальше ввели $10$ элементов, то количество элементов с чётными соседями будет считаться для $10$ элементов. Чтобы избежать этого мы ограничиваем количество читаемых элементов с помощью счётчика i++ и цикла while.

Ссылки

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

Related Images:

e-olymp 8283. Музыка

14/12/2019 by Евгений Радчин

Задача

Малыши и малышки очень любили музыку, а Гусля был замечательный музыкант. У него были разные музыкальные инструменты, и он часто играл на них. Их было много, поэтому он развесил их на стенах своей комнаты. Инструмент, расположенный справа от входной двери имел номер $1$, дальше они нумеровались по кругу, а последний инструмент с номером $n$ висел слева от этой двери.

Малыши часто просили его научить играть на каком-нибудь инструменте. Гусля не отказывал, но сначала предлагал взять инструмент с первым номером, а если ученику хотелось играть на другом, то он выбирал шестой следующий по кругу и так далее. Напишите программу, которая определяла номер попытки, с которой ученик мог получить желаемый инструмент с номером $k$.

Например, если количество инструментов $n = 11$, то последовательность будет следующей: $(1) 2 3 4 5 6 (7) 8 9 10 11 1 (2) 3 4 5 6 7 (8) 9 10 11 1 2 (3) 4 5$ …, то есть при $k = 3$ инструмент с номером $3$ можно было бы получить с пятой попытки.

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

Два натуральных числа $n$ и $k$ $(1 \leqslant k \leqslant n \leqslant 100)$.

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

Вывести номер попытки, в который «выпадал» инструмент с номером $k$. Если это никогда не происходило, следует вывести $0$.

Тесты

№	Входные данные	Выходные данные
1	11 3	5
2	6 2	0
3	13 13	3
4	9 8	0
5	5 5	5

Код

#include <iostream>  
using namespace std;

int main() {
    int quantity, instrument, counter = 1;
    cin >> quantity >> instrument;
    if ((quantity == 6 && instrument != 1) || (quantity == instrument && quantity % 2 == 0)) {
        cout << 0;
    } else if (quantity == instrument) {
        for (int num = 1; num % quantity != 0; num += 6) {
            if (num != 1 && num % quantity == 1) {
                cout << 0;
                return 0;
            } else {
                counter++;
            }   
        }
        cout << counter;
    } else {
        for (int num = 1; num % quantity != instrument; num += 6) {
            if (num != 1 && num % quantity == 1) {
                cout << 0;
                return 0;
            } else {
                counter++;
            }   
        }
        cout << counter;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int quantity, instrument, counter = 1;

cin >> quantity >> instrument;

if ((quantity == 6 && instrument != 1) || (quantity == instrument && quantity % 2 == 0)) {

cout << 0;

} else if (quantity == instrument) {

for (int num = 1; num % quantity != 0; num += 6) {

if (num != 1 && num % quantity == 1) {

cout << 0;

return 0;

} else {

counter++;

}

cout << counter;

} else {

for (int num = 1; num % quantity != instrument; num += 6) {

if (num != 1 && num % quantity == 1) {

cout << 0;

return 0;

} else {

counter++;

}

cout << counter;

}

return 0;

}

Решение

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

Если пользователь вводит разные числа.
Если пользователь вводит одинаковые числа.

В первом случае мы рассматриваем две ситуации:
1) если пользователь вводит количество инструментов $6$, то единственным решением будет инструмент под номером $1$, так как Гусля выбирает инструменты через $6$ штук по кругу;
2) если количество инструментов не равно $6$ то мы реализовываем алгоритм нахождения номера путем деления с остатком, а именно: если текущее число при делении на количество инструментов не дает в остатке искомый номер, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае мы нашли число попыток.
Еще здесь, так же, как и во втором случае, есть подводный камень: если мы уже сделали какое-то количество попыток и текущее число при делении на количество инструментов дает в остатке $1$, мы никогда не попадем на нужный нам номер инструмента.

Во втором случае мы также рассматриваем две ситуации:
1) если количество инструментов делится нацело на $2$, то нам никогда не выпадет нужный инструмент;
2) если текущее число при делении на количество инструментов не дает в остатке $0$, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае ответ найден.
Также не забываем про подводный камень, указанный выше.

Ссылки

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

Related Images:

e-olymp 5041. Синтаксический анализ вещественных чисел

14/12/2019 by Илья Балицкий

Задача

Напишите программу, которая считывает строку и проверяет, содержит ли она действительное число. Действительное число может содержать десятичную точку или показатель степени (начинающийся с $ e $ или $ E $), или и то и то одновременно. Также число может содержать обыкновенный набор десятичных цифр. Если число содержит десятичную точку, то должна присутствовать хотя бы одна цифра с каждой стороны точки. Перед числом или экспонентой может находиться плюс или минус (или одновременно и там и там) (без пробелов после знака). Экспонентой является целое число (не содержит десятичной запятой). Пробелы могут присутствовать до или после числа, но не внутри него. Обратите внимание, что границ диапазона входных чисел не существует, но для простоты будем предполагать, что входные строки содержат не более $ 1000 $ символов.

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

Первая строка содержит количество тестов $ t $. Дальше следует $ t $ строк, каждая из которых содержит одно число.

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

Вывести $ t $ строк, каждая из которых содержит слово $ LEGAL $ или $ ILLEGAL $.

Тесты

№	Входные данные	Выходные данные
1.	2 1.5e+2 3.	LEGAL ILLEGAL
2.	4 752.45e+24 0.762e. -0.355.6432e	LEGAL ILLEGAL ILLEGAL
3.	1 -652.32e+45	LEGAL
4.	3 542.512e+3 123.456E+42 123.456.789	LEGAL LEGAL ILLEGAL

Код

#include <iostream>
using namespace std;
 
bool isdigit(char x) { // проверка, является ли символ числом
    return (x >= '0' && x <= '9'? 1: 0);
}
 
bool isreal(char* x) { // сама функция синтаксического анализа
    if ((!isdigit(*x))||(*x == '+' || *x == '-' && !isdigit(*++x))) return 0;
    while (isdigit(*x)) ++x; // счетчик сдвигает указатель до символа, отличного от числа
    if (*x == '.' && !isdigit(*++x)) return 0;
    while (isdigit(*x))++x;
    if ((*x == 'e' || *x == 'E')&&((*++x == '+' || *x == '-')&&(!isdigit(*++x)))) return 0;
    while (isdigit(*x)) ++x;
    return *x == 0; // закончилось ли число
}
 
int main() {
    char x[1001];
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) { // сама проверка
        cin >> x; // ввод игнорирует пробелы, которые по условию могут быть до и после числа
        cout << (isreal(x) ? "LEGAL" : "ILLEGAL") << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

bool isdigit(char x) { // проверка, является ли символ числом

return (x >= '0' && x <= '9'? 1: 0);

}

bool isreal(char* x) { // сама функция синтаксического анализа

if ((!isdigit(*x))||(*x == '+' || *x == '-' && !isdigit(*++x))) return 0;

while (isdigit(*x)) ++x; // счетчик сдвигает указатель до символа, отличного от числа

if (*x == '.' && !isdigit(*++x)) return 0;

while (isdigit(*x))++x;

if ((*x == 'e' || *x == 'E')&&((*++x == '+' || *x == '-')&&(!isdigit(*++x)))) return 0;

while (isdigit(*x)) ++x;

return *x == 0; // закончилось ли число

}

int main() {

char x[1001];

int n;

cin >> n;

for (int i = 0;i < n;i++) { // сама проверка

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

cout << (isreal(x) ? "LEGAL" : "ILLEGAL") << "\n";

}

return 0;

}

Решение

Для решения задачи нам понадобится функция idigit() проверки того, является ли символ цифрой. В STL существует одноименная функция, которая выполняет ту же самую задачу, однако для практики, я написал свою. В функции анализа вещественных чисел isreal() нужно указать условия, при которых синтаксис будет нарушен. Т.е. не будут выполнены условия, описанные в задаче. Затем, если в символьном массиве не было замечено ошибок — возвратить trueв основную функцию. Важно то, что в числе не должно по условию быть других символов кроме «e», «E», «.», «+», «-» и цифр. Что касается окаймляющих пробелов, то при вводе строки через cin они игнорируются.

Ссылки

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

Related Images:

e-olymp 6387. Острова в потоке данных

13/12/2019 by Нина Хоробрых

Задача

Задана последовательность целых чисел $a_{1}, a_{2}, a_{3}, \ldots, a_{n}$. Островом в последовательности называется набор последовательно идущих чисел, каждый из которых больше элементов, находящихся перед и после самой подпоследовательности. В приведенных ниже примерах каждый остров в последовательности обозначен внизу скобкой. Скобка острова, который находится в другом острове, находится под соответствующей скобкой.

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

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

Первая строка содержит количество тестов $p \ (1 \leqslant p \leqslant 1000)$.

Каждый тест состоит из одной строки. Она содержит номер теста $k$, за которым следует $15$ неотрицательных целых чисел, разделенных пробелом. Первое и последнее число последовательности равны $0$. Каждое число отличается от предыдущего не более чем на $1$.

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

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

Тесты

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

Код

#include <iostream>
using namespace std;
#define AMNT 15
 
int main() {
    int p, k;
    int current, previous; 
    cin >> p;
    while ( p--) {
        cin >> k; 
        int isl = 0; 
        cin >> current;       // ввод 1-го элемента последовательности
        previous = current;     
        for ( int j = 1; j < AMNT ; j++ ){
            cin >> current;        //ввод остальных элементов
            if ( current > previous ) { 
                isl++;
            }
            previous = current;
        }
        cout << k << " " << isl << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

#define AMNT 15

int main() {

int p, k;

int current, previous;

cin >> p;

while ( p--) {

cin >> k;

int isl = 0;

cin >> current; // ввод 1-го элемента последовательности

previous = current;

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

cin >> current; //ввод остальных элементов

if ( current > previous ) {

isl++;

}

previous = current;

}

cout << k << " " << isl << endl;

}

return 0;

}

Решение

Для решения задачи следует выявить закономерность образования острова в последовательности. Рассмотрим подробно.
Начнем с набора наибольших чисел в последовательности. С двух сторон от него идут числа, меньшие на $1$, которые образуют между собой уже другой остров. И так пока по краям не будут нули. Соответственно, чтобы узнать количество островов в последовательности, необходимо посчитать сколько раз элемент последовательности (подпоследовательности) больше предыдущего.

Ссылки

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

Related Images:

e-olymp 798. Платформы

12/12/2019 by Анна Цивинская

Условие

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю у героя уходит $|y_{2} — y_{1}|$ энергии, где $y_{1}$ и $y_{2}$ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3\cdot\left|y_{2} — y_{1}\right|$ энергии.

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

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

Первая строка содержит количество платформ $n (2 \leqslant n \leqslant 100000)$, вторая $n$ целых чисел, значения которых не превышают по модулю $400$ — высоты платформ.

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

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

Тесты

№	Ввод	Вывод
1	4 1 2 3 30	29 4 1 2 3 4
2	2 7 23	16 2 1 2
3	5 0 1 0 1 0	0 3 1 3 5

Код

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

#define MAX 100001

int main() {
    int amount_of_pltf;
    int heights[MAX], energy[MAX], platforms[MAX], list_of_pltf[MAX];
    cin >> amount_of_pltf;
    for (int i = 1; i <= amount_of_pltf; i++) cin >> heights[i];
    
    energy[1] = 0;
    energy[2] = abs(heights[2] - heights[1]);
    platforms[1] = -1;
    platforms[2] = 1;
    
    //В цикле вычисляем значения ячеек energy[j] и platforms[j](3 ≤ j ≤ amount_of_pltf)
    for (int j = 3; j <= amount_of_pltf; j++){
        if((energy[j-1] + abs(heights[j] - heights[j-1])) < (energy[j-2] + 3 * abs(heights[j] - heights[j-2]))){
            energy[j] = energy[j-1] + abs(heights[j] - heights[j-1]);
            platforms[j] = j - 1;
        } else {
            energy[j] = energy[j-2] + 3 * abs(heights[j] - heights[j-2]);
            platforms[j] = j - 2;
        }
    }
    
    //В переменной final_amount вычисляем конечное количество платформ, по которым нужно пройти.
    int final_amount = 0;
    for (int l = amount_of_pltf; l > 0; l = platforms[l]) list_of_pltf[final_amount++] = l;
    
    cout << energy[amount_of_pltf] << "\n" << final_amount << "\n";
    for(int k = final_amount - 1; k >= 0; k--) cout << list_of_pltf[k] << " ";
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

#define MAX 100001

int main() {

int amount_of_pltf;

int heights[MAX], energy[MAX], platforms[MAX], list_of_pltf[MAX];

cin >> amount_of_pltf;

for (int i = 1; i <= amount_of_pltf; i++) cin >> heights[i];

energy[1] = 0;

energy[2] = abs(heights[2] - heights[1]);

platforms[1] = -1;

platforms[2] = 1;

//В цикле вычисляем значения ячеек energy[j] и platforms[j](3 ≤ j ≤ amount_of_pltf)

for (int j = 3; j <= amount_of_pltf; j++){

if((energy[j-1] + abs(heights[j] - heights[j-1])) < (energy[j-2] + 3 * abs(heights[j] - heights[j-2]))){

energy[j] = energy[j-1] + abs(heights[j] - heights[j-1]);

platforms[j] = j - 1;

} else {

energy[j] = energy[j-2] + 3 * abs(heights[j] - heights[j-2]);

platforms[j] = j - 2;

}

//В переменной final_amount вычисляем конечное количество платформ, по которым нужно пройти.

int final_amount = 0;

for (int l = amount_of_pltf; l > 0; l = platforms[l]) list_of_pltf[final_amount++] = l;

cout << energy[amount_of_pltf] << "\n" << final_amount << "\n";

for(int k = final_amount - 1; k >= 0; k--) cout << list_of_pltf[k] << " ";

return 0;

}

Решение

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

Прыжок с платформы на соседнюю. Затрачивается $|y_{2} — y_{1}|$ энергии. В дальнейшем для упрощения этот вид прыжка будет называться «обычным».
Суперприём — прыжок, позволяющий перескочить через платформу. В этом случае затрачивается $3·|y_{2} — y_{1}|$ энергии. Далее по тексту этот прием будет называться «суперпрыжок».

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

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

Чтобы вывести список платформ, по которым мы прошли, мы записываем в новый массив номера платформ начиная с последнего значения массива platforms[amount_of_pltf]. Там же, с помощью счетчика считаем общее количество платформ.

Ссылки

Related Images:

e-olymp 1966. Большой плюс

08/12/2019 by Даниил Кадочников

Условие

На сайте в таблице результатов соревнований, проводимых по правилам ACM (Association for Computing Machinery), верно решённая задачка оценивается плюсом. Но он какой-то маленький. Выведите большой плюс из звёздочек.

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

Целое число [latex]n[/latex] ([latex]1 \leqslant n \leqslant 100[/latex]).

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

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

№

Ввод

Вывод

.*.
***
.*.

.*.

***

.*.

..*..
..*..
*****
..*..
..*..

..*..

*****

..*..

Решение

Задача задана немного нетривиально: не указано, каким образом число [latex]n[/latex] должно влиять на выходные данные. Однако по приведённым в условии примерам легко понять, что [latex]2n+1[/latex] — это ширина и высота плюса из звёздочек.

Печатать будем по строкам, для этого создадим главный цикл. Существует два случая: когда нужно вывести полную строку звёздочек (если [latex]u=n[/latex], то есть мы находимся в середине плюса) и когда нужно вывести обычную строку, состоящую из [latex]2n[/latex] точек и звёздочки посередине. В первом случае распечатываем [latex]2n+1[/latex] звёздочек. Во втором с помощью условия в цикле выводим звёздочку, если [latex]i=n[/latex] (центр строки), при других [latex]i[/latex] точки.

Тесты

№

Ввод

Вывод

....*....
....*....
....*....
....*....
*********
....*....
....*....
....*....
....*....

....*....

*********

....*....

......*......
......*......
......*......
......*......
......*......
......*......
*************
......*......
......*......
......*......
......*......
......*......
......*......

......*......

*************

......*......

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

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    for(int u=0; u<n*2+1; u++) {
        if(u==n) {
            for(int j=0; j<n*2+1; j++) cout << '*';
        }
        else {
            for(int i=0; i<n*2+1; i++) {
                if(i==n) cout << '*';
                else cout << '.';
            }
        }
        cout << endl;
    }   
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

for(int u=0; u<n*2+1; u++) {

if(u==n) {

for(int j=0; j<n*2+1; j++) cout << '*';

}

else {

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

if(i==n) cout << '*';

else cout << '.';

}

cout << endl;

}

return 0;

}

Related Images:

e-olimp 1658. Факториал

04/12/2019 by Елизавета Савицкая

Задача

Вычислите факториал числа.

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

Одно целое число [latex]n[/latex] ([latex] 0 \leqslant n \leqslant 20[/latex]).

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

Выведите значение [latex]n! = 1 · 2 · 3 · … · n.[/latex]

Тесты

Входные данные	Выходные данные
3	6
0	1
20	2432902008176640000

Код № 1

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

#include <iostream>

using namespace std;

int main() {

int n;

long factorial = 1;

cin >> n;

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

factorial *= i;

}

cout << factorial;

}

Решение № 1

Факториал натурального числа [latex]n[/latex] определяется как произведение всех натуральных чисел от [latex]1[/latex] до [latex]n[/latex] включительно.

Код № 2

#include <iostream>
using namespace std;

long factorial (int a) {
   if (a == 0)
      return 1;
   else
      return a*factorial(a - 1);
}

int main() {
   int a, n;
   cin >> n;
   cout << factorial(n);
   return 0;
}

#include <iostream>

using namespace std;

long factorial (int a) {

if (a == 0)

return 1;

else

return a*factorial(a - 1);

}

int main() {

int a, n;

cin >> n;

cout << factorial(n);

return 0;

}

Решение № 2

Также факториал числа можно найти при помощи рекурсивной функции (функции, которая вызывает сама себя).

Ссылки

Условие задачи на E-Olymp
Код задачи № 1 на Ideone
Код задачи № 2 на Ideone

Related Images:

e-olymp 8688. Количество чисел без 8

05/06/2019 by Андрей Зиновьев

Задача

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

Входные данные:
В первой строке задано число $n$ $(1 \le n \le 10^{18})$.

Выходные данные:
Выведите одно число — количество чисел от $1$ до $n$, в записи которых нет цифры $8$.

Тесты

Входные данные	Вывод программы
10	9
25833798135522720	4918510377816614
88888888888888	20334926626631

Continue reading →

Related Images:

e-olymp 8701. Кузнечик-попрыгунчик

24/05/2019 by Богдан Павлов

Задача

Кузнечик-попрыгунчик долго сидел на отметке [latex]0[/latex] числовой прямой, так долго, что придумал инновационную методологию своего перемещения. Такую, что за каждую итерацию движения он выполняет ровно два прыжка, перемещаясь сначала на [latex]a[/latex], а затем на [latex]b[/latex] единичных отрезков по числовой прямой, причем, если число положительное, то он движется вправо, а если отрицательное, то влево. Продолжительность прыжка в секундах равна соответствующему количеству единичных отрезков, на которое переместится кузнечик.

Например, если [latex]a = 3[/latex], а [latex]b = — 2[/latex], то через [latex]3[/latex] сек. он будет на отметке [latex]3[/latex], а через [latex]5[/latex] сек. от начала движения попадет на отметку [latex]1[/latex]. Далее, на [latex]8[/latex] секунде переместится на отметку [latex]4[/latex], а на [latex]10[/latex] секунде вернется на [latex]2[/latex].

При заданных [latex]a[/latex] и [latex]b[/latex] найти сколько необходимо времени в секундах, чтобы допрыгать до отметки x числовой прямой или вывести [latex]-1[/latex], если это невозможно.

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

Целочисленные значения [latex]a[/latex], [latex]b[/latex], [latex]x[/latex] — в одной строке через пробел. Значение по модулю не превышают [latex]10^{9}[/latex].

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

Ответ на задачу.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	3 -2 1	5
2	100 200 0	0
3	-10 -20 -900	900
4	5 -6 3	27
5	1 3 10	-1

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

#include<iostream>
using namespace std;
#define MAX 1000000000000000000
int main()
{
    long long a, b, x;
    cin >> a >> b >> x; // ввод переменных
 
    if (!x) return (cout << 0 << endl, 0); // проверяем, не равен ли x 0(тогда не нужно совершать никаких прыжков)
 
    if(a+b==0) if(x==a) return(cout << a << endl,0); // так же проверяем не будет ли суммой дистанций прыжков 0,
    // если будет, то проверяем, можно ли за первый прыжок добраться до точки x
 
    long long possible_ans1 = MAX, possible_ans2 = MAX; // объявляем две переменные, соответветствующие двум способам добраться до точки x
 
    if (!((x - a) % (a + b)))// проверяем первый способ, если можно добраться за n(a+b) + a прыжков, где n - количество совершенных прыжков
        possible_ans1 = ((x - a) / (a + b)) * (abs(a) + abs(b)) + abs(a);
 
    if (!(x % (a + b))) // проверяем второй способ, если до x можно добраться n(a+b) прыжков
        possible_ans2 = x / (a + b) * (abs(a) + abs(b));
 
    // если невозможно добраться каким-либо из способов, то присваиваем соответствующей переменной значение MAX
    if (possible_ans1 < 0) 
        possible_ans1 = MAX;    
    if (possible_ans2 < 0) 
        possible_ans2 = MAX;
 
    if (possible_ans1 == MAX && possible_ans2 == MAX) // если невозможно добраться никаким из способов, то выводим -1, в отличном случае
        return (cout << -1 << endl, 0); // выводим минимум из возможных ответов
    cout << min(possible_ans1, possible_ans2) << endl;
    return 0;
}

#include<iostream>

using namespace std;

#define MAX 1000000000000000000

int main()

{

long long a, b, x;

cin >> a >> b >> x; // ввод переменных

if (!x) return (cout << 0 << endl, 0); // проверяем, не равен ли x 0(тогда не нужно совершать никаких прыжков)

if(a+b==0) if(x==a) return(cout << a << endl,0); // так же проверяем не будет ли суммой дистанций прыжков 0,

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

long long possible_ans1 = MAX, possible_ans2 = MAX; // объявляем две переменные, соответветствующие двум способам добраться до точки x

if (!((x - a) % (a + b)))// проверяем первый способ, если можно добраться за n(a+b) + a прыжков, где n - количество совершенных прыжков

possible_ans1 = ((x - a) / (a + b)) * (abs(a) + abs(b)) + abs(a);

if (!(x % (a + b))) // проверяем второй способ, если до x можно добраться n(a+b) прыжков

possible_ans2 = x / (a + b) * (abs(a) + abs(b));

// если невозможно добраться каким-либо из способов, то присваиваем соответствующей переменной значение MAX

if (possible_ans1 < 0)

possible_ans1 = MAX;

if (possible_ans2 < 0)

possible_ans2 = MAX;

if (possible_ans1 == MAX && possible_ans2 == MAX) // если невозможно добраться никаким из способов, то выводим -1, в отличном случае

return (cout << -1 << endl, 0); // выводим минимум из возможных ответов

cout << min(possible_ans1, possible_ans2) << endl;

return 0;

}

Решение задачи (с использованием условных операторов)

Для решения данной задачи сначала проверим не находимся ли мы уже в точке [latex]0[/latex], после проверим не равна ли сумма дистанций прыжков [latex]0[/latex], если равна, то также проверим можно ли добраться до точки x за один прыжок a. Если возможно выводим a. После проверяем возможность добраться до точки x двумя способами:

Сначала добравшись до точки x-a прыжками вида a+b, а после совершив один прыжок на дистанцию a
Добраться до точки x исключительно прыжками вида a+b

Если одним из способов невозможно добраться, то присваиваем переменной соответствующей потраченному времени MAX, а после выводим минимум из переменных possible_ans1, possible_ans2(в случае, если обеими способами невозможно добраться, т.е. обе переменные равны MAX выводим -1).

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

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    long long a,b,x,s,t,ans=-1;
    cin >> a >> b >> x;
    s=a+b;
    t=abs(a)+abs(b);
    (!x) && cout << 0 || 
    (x==a) && cout << abs(a) ||
    !((x - a) % (s)) && ((x - a) / (s)) * (t) + abs(a) >= 0 && cout << ((x - a) / (s)) * (t) + abs(a) ||
    !(x % (s)) && x / (s) * (t) >= 0 && cout << x / (s) * (t) || cout << -1;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

long long a,b,x,s,t,ans=-1;

cin >> a >> b >> x;

s=a+b;

t=abs(a)+abs(b);

(!x) && cout << 0 ||

(x==a) && cout << abs(a) ||

!((x - a) % (s)) && ((x - a) / (s)) * (t) + abs(a) >= 0 && cout << ((x - a) / (s)) * (t) + abs(a) ||

!(x % (s)) && x / (s) * (t) >= 0 && cout << x / (s) * (t) || cout << -1;

return 0;

}

Решение задачи (без использования условных операторов)

Заранее вычислим значения s(пройденное расстояние за один прыжок вида a+b) и t(время, потраченное на один прыжок вида a+b). После поочередно проверим выполнение всех условий, описанных ранее. При выполнении какого-либо из условий, выводим соответствующее время, если ни одно из условий не выполнилось то выводим [latex]-1[/latex].

Related Images:

e-olymp 497. Лентяй

21/05/2019 by Андрей Зиновьев

Задача

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

Входные данные:
Первая строка содержит количество тестов. Каждый тест состоит из количество предметов $n$ $(1 \le n \le 100)$, которые нужно сдать Валере. Далее идет $n$ строк, каждая из которых состоит из двух чисел $a$ и $b$ $(1 \le a \le b \le 31)$, задающих интервал работы очередного преподавателя.

Выходные данные:
Для каждого теста вывести в отдельной строке "YES" если возможно встретить всех преподавателей за один день, или "NO", если это невозможно.

Тесты

Входные данные	Вывод программы
2 1 1 2 2 1 2 3 4	YES NO
1 1 5 6	YES
2 2 1 4 7 9 3 1 30 2 5 5 10	NO YES

Continue reading →

Related Images:

e-olymp 2322. Столбцы

28/04/2019 by Михаил Бутник

Столбцы

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

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

В первой строке задано число [latex]x[/latex], не превышающее по модулю 2 [latex]\cdot[/latex] 10⁹. Во второй строке задано число [latex]n \left(1 \leqslant n \leqslant 100\right)[/latex]. Каждая из следующих [latex]n[/latex] строк содержит [latex]n[/latex] целых чисел, не превышающих по модулю 2 [latex]\cdot[/latex] 10⁹ — числа в ячейках таблицы.

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

Для каждого столбца в отдельной строке выведите YES, если в нем есть число [latex]x[/latex], и NO в противном случае.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1 2 0 1 0 0	NO YES
2	23 3 23 0 23 21 12 23 11 13 23	YES NO YES
3	7 1 0	NO
4	13 3 13 33 75 23 45 31 13 13 13	YES YES YES

Код

#include <iostream>
using namespace std; 
 
int arr[101];
int main() {
    long long x, c;
    cin >> x;
    int n, i = 0;
    cin >> n;
    while (cin >> c) {
        if (c == x) {
            arr[i % n]++;
        }
        i++;
    }
    for (int i = 0; i < n; i++) {
        if (arr[i] > 0) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int arr[101];

int main() {

long long x, c;

cin >> x;

int n, i = 0;

cin >> n;

while (cin >> c) {

if (c == x) {

arr[i % n]++;

}

i++;

}

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

if (arr[i] > 0) {

cout << "YES" << endl;

}

else {

cout << "NO" << endl;

}

return 0;

}

Решение

Для решения этой задачи заведём массив на [latex]n[/latex] элементов, в котором каждый элемент будет счётчиком соответствующего столбца. В цикле будем смотреть все элементы и, если нам встретится элемент [latex]x[/latex], увеличим соответствующий счётчик. Затем в другом цикле смотрим счётчик каждого столбца, если он больше нуля, то выводим YES, иначе — NO.

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

Related Images:

Коды Грея

06/03/2019 by Иван Дуков

Задача

Frank Gray (13 September 1887 – 23 May 1969) was a physicist and researcher at Bell Labs who made numerous innovations in television, both mechanical and electronic

Коды Грея получили своё название по имени Франка Грея (Frank Gray), физика из Bell Telephone Laboratories, который в 1930-х годах изобрёл метод, в настоящее время используемый для передачи цветного телевизионного сигнала, совместно с существующими методами передачи и получения чёрно-белого сигнала; т.е. при получении цветного сигнала чёрно-белым приёмником изображение выводится оттенками серого цвета.
Хотя существует множество различных вариантов кодов Грея, рассмотрим только один: «двоичный отражённый (рефлексный) код Грея». Именно этот код обычно имеется в виду, когда говорят о неконкретном «коде Грея».
Отображённый двоичный код Грея строится следующим образом. Начинаем со строк [latex]0[/latex] и [latex]1[/latex], которые представляют соответственно целые числа [latex]0[/latex] и [latex]1[/latex].
[latex]0[/latex] [latex]1[/latex] Возьмём отражение этих строк относительно горизонтальной оси после приведённого списка и поместим [latex]1[/latex] слева от новых записей списка, а слева от уже имевшихся разместим [latex]0[/latex].
[latex]00[/latex] [latex]01[/latex] [latex]11[/latex] [latex]10[/latex] Таким образом получен отражённый код Грея для [latex]n = 2[/latex]. Чтобы получить код для [latex]n = 3[/latex], повторим описанную процедуру и получим:
[latex]000[/latex] [latex]001[/latex] [latex]011[/latex] [latex]010[/latex] [latex]110[/latex] [latex]111[/latex] [latex]101[/latex] [latex]100[/latex] При таком способе построения легко увидеть по индукции по [latex]n[/latex], что, во-первых, каждая из [latex]2n[/latex] комбинаций битов появляется в списке, причём только один раз; во-вторых, при переходе от одного элемента списка к рядом стоящему изменяется только один бит; в-третьих, только один бит изменяется при переходе от последнего элемента списка к первому. Коды Грея, обладающие последним свойством называются циклическими, и отражённый код Грея обязательно является таковым.
Для каждого заданного числа [latex]k[/latex] вывести десятичное значение [latex]k[/latex]-го кода Грея.

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

Во входном файле содержится некоторый набор тестовых данных, каждое число [latex]k[/latex] ([latex]0 ≤ k ≤ 10^{18}[/latex]) в наборе задано в отдельной строке. Количество наборов данных в одном тесте не превышает [latex]10^5[/latex].

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

Для каждого заданного числа [latex]k[/latex] вывести в отдельной строке десятичное значение [latex]k[/latex]-го кода Грея.

Тесты

№	Входные данные	Выходные данные
1	3	2
	14	9
	5	7
	12	10
2	0	0
	72	108
	265	397
	4781	7163
	50642	42811
3	1010234	581415
	96721758	119682801
	640214927	893162568
	2456987013	3679188807
	51027963402	60418988303
	1000000000000000000	797398725282889728

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

#include <iostream>

using namespace std;

int main() {
    unsigned long int k;
    while (cin >> k) {
        cout <<  (k  ^ (k >> 1)) << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned long int k;

while (cin >> k) {

cout << (k ^ (k >> 1)) << endl;

}

return 0;

}

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

Объявляем переменную [latex]k[/latex] ([latex]0 ≤ k ≤ 10^{18}[/latex]) типа unsigned long int для считывания чисел из входного потока. Цикл while работает столько раз, сколько чисел во входном потоке (по условию задачи их количество [latex]\le 10^5[/latex]). В цикле вычисляется Код Грея числа [latex]k[/latex] путем побитовой операции «исключающее ИЛИ», применимого к [latex]k[/latex] и к результату побитового сдвига [latex]k[/latex] на [latex]1[/latex] бит вправо ([latex]k \gg 1[/latex]).
Ссылка на алгоритм ниже.

Ссылки

Code Gray: theory
e-olymp
ideone

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 458. Черно-белая графика

24/12/2018 by Юлиана Боурош

Задача

Одна из базовых задач компьютерной графики – обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной $w$ и высотой $h,$ разбитых на $w × h$ единичных квадратов, каждый из которых имеет либо белый, либо черный цвет. Такие единичные квадраты называются пикселами. В памяти компьютера сами изображения хранятся в виде прямоугольных таблиц, содержащих нули и единицы.

Во многих областях очень часто возникает задача комбинации изображений. Одним из простейших методов комбинации, который используется при работе с черно-белыми изображениями, является попиксельное применение некоторой логической операции. Это означает, что значение пиксела результата получается применением этой логической операции к соответствующим пикселам аргументов. Логическая операция от двух аргументов обычно задается таблицей истинности, которая содержит значения операции для всех возможных комбинаций аргументов. Например, для операции «ИЛИ» эта таблица выглядит так.

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

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

Первая строка содержит два целых числа $w$ и $h$ $(1 \leq w, h \leq 100).$ Последующие $h$ строк описывают первое изображение и каждая из этих строк содержит $w$ символов, каждый из которых равен нулю или единице. Далее следует описание второго изображения в аналогичном формате. Последняя строка содержит описание логической операции в виде четырех чисел, каждое из которых – ноль или единица. Первое из них есть результат применения логической операции в случае, если оба аргумента нули, второе – результат в случае, если первый аргумент ноль, второй единица, третье – результат в случае если первый аргумент единица, второй ноль, а четвертый – в случае, если оба аргумента единицы.

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

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

Тесты

	Входные данные	Выходные данные
1	5 3 01000 11110 01000 10110 00010 10110 0110	11110 11100 11110
2	2 3 010 111 000 101 1010	11 10 10
3	4 4 1111 0101 0000 1110 0011 0101 0111 1111 0011	1111 0101 0000 1110
4	3 6 100011 000111 000000 111011 001100 010101 1000	000 100 110 000 101 010

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

( использован одномерный массив)

#include <iostream>
using namespace std;

bool my_operation (bool a, bool b, bool* res) {
    if (!a and !b) return res[0];
    else if (!a and b) return res[1];
    else if (a and !b) return res[2];
    else return res[3];
}

int main() {
    int w, h, n;
    bool truth_t[4];
    cin >> w >> h;
    n = w * h;
    bool *first_t = new bool [n];
    bool *second_t = new bool [n];
    char c;
    for (int i = 0; i < n; i++) {
        cin >> c;
        first_t[i] = (c == '1' ? true : false);
    }
    for (int i = 0; i < n; i++) {
        cin >> c;
        second_t[i] = (c == '1' ? true : false);
    }
    for (int i = 0; i < 4; i++) {
        cin >> c;
        truth_t[i] = (c == '1' ? true : false);
    }
    for (int i = 0; i < n; i++) {
        if (i != 0 && i % w == 0)
        cout << endl;
        cout << my_operation(first_t[i], second_t[i], truth_t);
    }
    return 0;
}

#include <iostream>

using namespace std;

bool my_operation (bool a, bool b, bool* res) {

if (!a and !b) return res[0];

else if (!a and b) return res[1];

else if (a and !b) return res[2];

else return res[3];

}

int main() {

int w, h, n;

bool truth_t[4];

cin >> w >> h;

n = w * h;

bool *first_t = new bool [n];

bool *second_t = new bool [n];

char c;

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

cin >> c;

first_t[i] = (c == '1' ? true : false);

}

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

cin >> c;

second_t[i] = (c == '1' ? true : false);

}

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

cin >> c;

truth_t[i] = (c == '1' ? true : false);

}

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

if (i != 0 && i % w == 0)

cout << endl;

cout << my_operation(first_t[i], second_t[i], truth_t);

}

return 0;

}

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

(использован двумерный массив)

#include <iostream>
using namespace std;

bool my_operation (bool a, bool b, bool* res) {
    if (!a and !b) return res[0];
    else if (!a and b) return res[1];
    else if (a and !b) return res[2];
    else return res[3];
}

int main() {
    int w, h;
    bool truth_t[4];
    cin >> w >> h;
    bool **first_t = new bool *[h];
    bool **second_t = new bool *[h];
    for (int i = 0; i < h; i++) {
        first_t[i] = new bool [w];
        second_t[i] = new bool [w];
    }
    char c;
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++) {
            cin >> c;
            first_t[i][j] = (c == '1' ? true : false);
        }
    }
    for (int i = 0; i < h; i++){ 
        for (int j = 0; j < w; j++) {
            cin >> c;
            second_t[i][j] = (c == '1' ? true : false);
        }
    }
    for (int i = 0; i < 4; i++) {
        cin >> c;
        truth_t[i] = (c == '1' ? true : false);
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cout << my_operation(first_t[i][j], second_t[i][j], truth_t);
        }
        if (i < h - 1) cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

bool my_operation (bool a, bool b, bool* res) {

if (!a and !b) return res[0];

else if (!a and b) return res[1];

else if (a and !b) return res[2];

else return res[3];

}

int main() {

int w, h;

bool truth_t[4];

cin >> w >> h;

bool **first_t = new bool *[h];

bool **second_t = new bool *[h];

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

first_t[i] = new bool [w];

second_t[i] = new bool [w];

}

char c;

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

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

cin >> c;

first_t[i][j] = (c == '1' ? true : false);

}

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

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

cin >> c;

second_t[i][j] = (c == '1' ? true : false);

}

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

cin >> c;

truth_t[i] = (c == '1' ? true : false);

}

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

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

cout << my_operation(first_t[i][j], second_t[i][j], truth_t);

}

if (i < h - 1) cout << endl;

}

return 0;

}

Решение

Объявляем два булевых динамических массива под две пиксельные таблицы и один статический для таблицы истинности, вводим входные данные. Затем поочерёдно сравниваем соответствующие элементы массивов с помощью функции my_operation, которая принимает две переменные a и b булевского типа и булев массив res с таблицей истинности, и возвращает соответствующее значение из таблицы для комбинации значений a и b. Результат сравнения выводим.

Ссылки

Одномерный массив
- ideone.com
- e-olymp.com
Двумерный массив
- ideone.com
- e-olymp.com

Related Images:

e-olymp 1753. Младший бит

23/12/2018 by Юлиана Боурош

Задача

Для заданного положительного целого $A$ $(1 \leq A \leq 100),$ вывести младший бит $A$.

Например, если $A = 26$, то его мы можем записать в двоичном виде, как $11010$, и младший бит $A$ есть $10$, и на выходе должно быть $2.$

Другой пример выглядит следующим образом: при $A = 88$, это число $A$ мы можем записать в двоичной форме $1011000$, младший бит в $A$ есть $1000,$ и на выходе должно быть $8.$

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

Каждая строка входных данных содержит только одно целое число $A$ $(1 \leq A \leq 100).$ Строка, содержащая «0» означает конец ввода, и эта строка не является частью входных данных.

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

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

Тесты

	Входные данные	Выходные данные
1	26 88 0	2 8
2	99 45 66 20	1 1 2 4
3	100 0 6	4
4	66 33 98 42 84 39	2 1 2 2 4 1

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

#include <iostream>
using namespace std;

int main() {
    int a;
    while (cin >> a && a != 0) {
        int LSB = 1; // Least Significant Bit
        while ((a & LSB) == 0){
            LSB = LSB << 1;
        }
        cout << LSB << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a;

while (cin >> a && a != 0) {

int LSB = 1; // Least Significant Bit

while ((a & LSB) == 0){

LSB = LSB << 1;

}

cout << LSB << endl;

}

return 0;

}

Решение

Объявляем переменную a. Начинается цикл while, условием окончания которого будет введённая a, неравная нулю. В цикле объявляем переменную LSB = 1, после чего начинается новый цикл while, который сдвигает бит LSB влево, пока выражение побитовой конъюнкции a & LSB нулевое. Соответственно, как только выражение будет ненулевым — будет найден первый общий бит, который и будет младшим битом числа a. Его и выводим.

Ссылки

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 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 479. Вышивка “крестиком”

28/11/2018 by Владимир Дроздин

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

Задача

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

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

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

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

Макеты, в порядке, перечисленном во входном файле, разделенные пустой строкой.

Тесты

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

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

2 3 5

X X
X
X X

X X
X X
X
X X
X X

1 9

X X
X X
X X
X X
X
X X
X X
X X
X X

Код

#include <iostream>
using namespace std;
 
int main() {
    int n, x;
    cin >> n;
    for (int l = 0; l < n; l ++){
        cin >> x;
        for (int j = 0; j < x; j ++){
            for (int i = 0; (i <= j) or (i <= x - 1 - j); i ++){
                if ((i == j) or (j == x - 1 - i)) cout << "X";
                else cout << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, x;

cin >> n;

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

cin >> x;

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

for (int i = 0; (i <= j) or (i <= x - 1 - j); i ++){

if ((i == j) or (j == x - 1 - i)) cout << "X";

else cout << " ";

}

cout << endl;

}

cout << endl;

}

return 0;

}

Решение

В данной задаче будем использовать потоковую обработку. Сначала считываем количество макетов [latex] n [/latex]. Затем в цикле for (int l = 0; l < n; l ++); считываем номера узоров. Выводить [latex] X [/latex] будем по диагоналям (справа налево и наоборот). Однако, стоит учесть, что после последнего символа [latex] X [/latex] в строке, выводить пробел не стоит. В условии задачи данный факт не фигурирует, однако, если же сделать иначе, то задача на сайте e-olymp не пройдет. Из этого вытекает, что пробелы должны располагаться исключительно до последнего крестика в строке. Для этого во внутреннем цикле ставим соответсвующее условие, чтобы при достижении последнего крестика в строке осуществлялся переход на другую строку, если это возможно. Также стоит не забыть, что между разными узорами нужно пропускать строку.