e-olymp 2667. Змейка

26/06/2019 by Дмитрий Калинин

Задача

Напишите программу, которая выводит элемент из строки $x$ и столбца $y$ матрицы размера $n × m$, которая заполнена змейкой:

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

Даны натуральные числа $n, m, x, y (1 \leqslant x \leqslant n \leqslant 50, 1 \leqslant y \leqslant m\leqslant 50)$. Здесь $n$- количество строк матрицы, $m$ — количество столбцов матрицы, $x$ и $y$ — номера строки и столбца искомого элемента.

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

Вывести элемент из строки $x$ и столбца $y$.

Решение

Для решения создаётся матрица в представлении массива размера $n* m$, который заполняется следующим образом: если текущая строка матрицы нечётная, то элемент массива принимает значение номера строки, умноженного на количество $m$ столбцов матрицы плюс номер текущего столбца, а если текущая строка — чётная, то текущему элементу массива присваивается значение, равное произведению увеличенного на единицу номера $n$ строки на количество $m$ столбцов матрицы минус увеличенный на единицу номер текущего столбца. Для вывода значения матрицы по двум координатам мы используем элемент массива с индексом равным сумме координаты $y$ на произведение координаты $x$ на количество столбцов $m$, которое используется для «прыжка» через необходимое количество строк.

Тесты

№	Ввод	Вывод
1	5 2 3 1	4
2	4 5 3 1	10
3	50 48 45 20	2131

Код

#include <iostream>
using namespace std;

int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    x--, y--;
    int *arr = new int[n * m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            arr[i * m + j] = (i % 2 == 0 ? i * m + j : (i + 1) * m - (j + 1)); 
        }
    }
    cout << arr[x * m + y];
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m, x, y;

cin >> n >> m >> x >> y;

x--, y--;

int *arr = new int[n * m];

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

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

arr[i * m + j] = (i % 2 == 0 ? i * m + j : (i + 1) * m - (j + 1));

}

cout << arr[x * m + y];

return 0;

}

Ссылки

Related Images:

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

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

Задача

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

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

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

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

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

Решение

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

Тесты

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

Код

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

#include <iostream>

using namespace std;

int p(int x) {

int t = 1;

while (x != 0) {

t *= x % 10;

x = x / 10;

}

return t;

}

int main() {

int x;

while (cin >> x) {

int i = 0;

while (x / 10 != 0) {

x = p(x);

i++;

}

cout << i << endl;

}

return 0;

}

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

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

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

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

#include <iostream>

#include <string>

using namespace std;

string f(string x) {

int mult = 1;

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

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

}

string result = to_string(mult);

return result;

}

int main() {

string inp;

while (cin >> inp) {

int count = 0;

while (inp.length() > 1) {

inp = f(inp);

count++;

}

cout << count << endl;

}

return 0;

}

Код c-string

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

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

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

#include <iostream>

#include <cstring>

using namespace std;

int f(char* str, int i) {

if (i == 0)

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

else

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

}

int main() {

char str[10];

int t;

while (cin >> str) {

int count = 0;

while (strlen(str) > 1) {

int k = strlen(str) - 1;

t = f(str, k);

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

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

count++;

}

cout << count << endl;

}

return 0;

}

Ссылки

Continue reading →

Related Images:

e-olimp 8596. Путешествие с запада на восток

27/12/2018 by Дмитрий Калинин

Задача

Есть $n$ городов, стоящих на прямой с запада на восток. Города пронумерованы от $1$ до $n$, в порядке с запада на восток. Каждая точка на прямой имеет свою одномерную координату, и точка ближе к востоку имеет большую координату. Координата $i$-го города — $x_i$.

Сейчас Вы находитесь в $1$ городе, и хотите посетить все города. У вас есть два способа путешествовать:

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

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

Первая строка содержит три числа $n (2 \leqslant n \leqslant 10^5)$, $a$ и $b (1 \leqslant a, b \leqslant 10^9)$. Следующая строка содержит $n$ целых чисел $x_1, x_2, … , x_n (1 \leqslant x_i \leqslant 10^9)$. Для всех $i (1 \leqslant i \leqslant n-1)$ имеет место неравенство $x_i <x_{i+1}$

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

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

Решение

Наименьший уровень усталости набирается при кратчайшем пути через все города — последовательном посещении всех городов по порядку и использовании оптимального способа передвижения. Для выбора способа передвижения мы считаем расстояние между следующим пунктом путешествия и нашим нынешним местоположением — $x_{i+1}-x_i$ ($1 \leqslant i \leqslant n-1$). После этого мы сравниваем прибавку к уровню усталости при переходе между городами — $(x_{i+1}-x_i) · a$ и при телепортации $b$, после чего прибавляем меньшее значение к нынешнему уровню усталости.

Тесты

№	Ввод	Вывод
1	4 2 5 1 2 5 7	11
2	7 1 100 40 43 45 105 108 115 124	84
3	7 1 2 24 35 40 68 72 99 103	12
4	5 6 30 100 104 105 192 201	90

Код

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

int main()
{
    long long n, a, b, x, x0, fatique = 0;
    cin >> n >> a >> b;
    cin >> x0; //ввод координат первого города
    n--; //поскольку мы в первом городе, нам остаётся посетить n-1 город
    while (n--) {
        cin >> x;
        fatique += min(a * (x - x0), b); //увеличение усталости на меньшую величину
        x0 = x;
    }
    cout << fatique;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

long long n, a, b, x, x0, fatique = 0;

cin >> n >> a >> b;

cin >> x0; //ввод координат первого города

n--; //поскольку мы в первом городе, нам остаётся посетить n-1 город

while (n--) {

cin >> x;

fatique += min(a * (x - x0), b); //увеличение усталости на меньшую величину

x0 = x;

}

cout << fatique;

}

Ссылки

Related Images:

e-olymp 8531. Делимость на числа

03/10/2018 by Дмитрий Калинин

Задача

Задано натуральное число [latex]n.[/latex] Делится ли оно одновременно на [latex] a\ [/latex] и на [latex] b?[/latex]?

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

Три натуральных числа [latex] n, a, b,[/latex] не больших [latex] 10^{9}.[/latex]

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

Выведите «YES» если [latex] n\ [/latex] делится одновременно на [latex] a\ [/latex] и на [latex] b\ [/latex]. Выведите «NO» иначе.

Тесты

№	Ввод	Вывод
1	12 4 6	YES
2	10 5 6	NO
3	1056 22 6	YES
4	98 103 5	NO

Решение

Проверим делимость [latex] n\ [/latex] на [latex] a\ [/latex] и [latex] b.[/latex] Число $n$ делится одновременно на $a$ и $b$ тогда, когда и остаток от деления $n$ на $a$ равен $0$ ( n % a == 0), и остаток от деления $n$ на $b$ равен $0$ ( n % b == 0).

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

#include <iostream>
using namespace std;

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    cout << ( ( (n % a == 0) && (n % b == 0) )? "YES": "NO");
    /* Делаем проверку делимости n одновременно на a и b,
    и, в зависимости от результата, при помощи тернарной операции выводим ответ */ 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, a, b;

cin >> n >> a >> b;

cout << ( ( (n % a == 0) && (n % b == 0) )? "YES": "NO");

/* Делаем проверку делимости n одновременно на a и b,

и, в зависимости от результата, при помощи тернарной операции выводим ответ */

return 0;

}

Код без использования ветвления

#include <iostream>
using namespace std;

int main() {
    int n, a, b, result;
    cin >> n >> a >> b;
    /* Используем небольшой трюк, который заключается в том,
    что cout в логических выражениях имеет значение 1 (true)*/
    ( ( (n % a == 0) && (n % b == 0) ) && (cout << "YES") );
    ( ( (n % a != 0) || (n % b != 0) ) && (cout << "NO") );
    return 0;
}