Category Archives: 2. Программы с ветвлением

Программы с простым ветвлением процесса выполнения в зависимости от некоторых условий. Ветвления в них обычно реализуются условным оператором или тернарной операцией.

Программы с ветвлением

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

В этом разделе нам придется писать программы в которых вычислительный процесс проходит по-разному в зависимости от выполнения или нарушения некоторого условия. Условия будут иногда довольно сложные. Организовать такое ветвление мы можем либо при помощи условного выражения (тернарной операции __?__:__), либо при помощи условного оператора (if(__)…else…). Обратите внимание, что если в зависимости от некоторого условия значение … Continue reading →

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

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

Поврежденная картина — очень хорошая задача для тренировки, масса различных ситуаций, которые нужно учесть. Но не все предусмотрено в тестах и неправильная программа может успешно пройти проверку. Требует знания основ школьного курса геометрии.
Две окружности —
задача аналогична предыдущей, но существенно проще.
Паук и муха
Количество участников олимпиады
Новый шкаф
Сыр для Анфисы
Компакт-диски
Среднее число
Торт
Олимпиада
Номер квартиры
Прямоугольник
Скидки — НЕ используйте функции min() и max()
Точка и треугольник
Отрезок и окружности
Уровень учебных достижений
Первая или последняя?
Какой треугольник?
Квадратное уравнение
Прямоугольный или нет?
Какая четверть?
Время года
Параллелограмм
Интересная сумма
Прямоугольник

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

OCPC-2021. Задача D. Столовая (код решения)

20/01/2024 by Александр Мармалюк

Условие

В столовой заведения «Покосившийся Скворечник» имеется ровно $k$ тарелок, а в самом заведении – $n$ палат. По старой традиции, чтобы постояльцы не пугались новых знакомых и не обменивались симптомами, их приводят в столовую так, чтобы одновременно там находились только обитатели одной палаты. При этом, порядок посещения столовой палатами строго зафиксирован – от меньшего номера к большему.

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

Первая строка ввода содержит два целых числа $n$ и $k$ $(1 \leqslant n \leqslant 10^5, 1 \leq k \leqslant 10^5)$ – количество палат и тарелок, соответственно. Следующие n строк содержат по 2 целых числа $a_i$ и $bi$ $(0 \leqslant a_i + b_i \leqslant k)$ – количество постояльцев в очередной палате, моющих и не моющих за собой посуду, соответственно.

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

Тесты

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

2 4 1 2 1 1	3
4 10 2 6 4 5 1 1 2 2	8
3 12 2 8 1 4 0 1	5
3 5 2 2 1 3 0 5	0

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

#include <iostream>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    int dirty = 0;
    for (int i = 0; i < n; ++i) {
        int wash, not_wash; //кол-во моющих и не моющих за собой постояльцев
        cin >> wash >> not_wash;
        if (not_wash < dirty) {
            int free_dirty = dirty - not_wash; //оставшиеся грязные тарелки
            dirty -= min(wash, free_dirty);
        }
        else
        if (not_wash > dirty)
            dirty = not_wash;
    }
    cout << k - dirty;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, k;

cin >> n >> k;

int dirty = 0;

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

int wash, not_wash; //кол-во моющих и не моющих за собой постояльцев

cin >> wash >> not_wash;

if (not_wash < dirty) {

int free_dirty = dirty - not_wash; //оставшиеся грязные тарелки

dirty -= min(wash, free_dirty);

}

else

if (not_wash > dirty)

dirty = not_wash;

}

cout << k - dirty;

return 0;

}

Решение

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

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

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

Решение задачи на ideone.com

Ссылка на контест

Related Images:

OCPC-2021. Задача G. Электрик возвращается (код решения)

22/12/2021 by Александр Мармалюк

Условие

Электрик Геннадий, постоялец палаты номер 404 заведения «Покосившийся Скворечник», прокрался ночью к ближайшей ЛЭП, чтобы наконец воплотить в жизнь свой план – отрезать кусок провода, находящийся между двумя соседними опорами, и отомстить лживой розетке из предыдущей задачи.

Он планирует реализовать это следующим образом: сначала просто забраться на вершину одной из опор, отрезать провод, закреплённый там, после чего спуститься на некоторую высоту вниз, возможно до земли. Далее Геннадий рассчитывает воспользоваться способностями человека-паука, которые, по его убеждению, открылись в нём после недавнего удара током: он выстрелит паутиной в некоторую произвольную точку соседнего столба, оттолкнется от первого столба и спустится по дуге окружности либо до второго столба, либо до земли. Разница высот в начале и конце такого спуска не должна превышать некоторую величину $l$, иначе наш новоявленный человек-паук рискует слишком сильно разогнаться и превратиться в человека-лепёшку. Затем электрик поднимется на вершину второго столба, чтобы отрезать закреплённый там провод, и спустится на землю.

Высоты столбов – $h_1$ и $h_2$, расстояние между ними – $d$. Геннадий не очень любит лазать вверх, поэтому он хочет разработать план таким образом, чтобы суммарная дистанция подъёмов была минимально возможной. Раз уж Вы взялись помогать ему, то доведите начатое до конца!

Единственная строка ввода содержит четыре целых числа $d$, $h_1, h_2, l$ $(1 \leqslant d, h_1, h_2, l \leqslant 10^6)$.

Выведите одно число – минимальную суммарную дистанцию подъёма Геннадия с точностью не хуже $10^-5$.

Тесты

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

5 5 5 5	10.00000
4 5 8 5	10.00000
4 8 5 1	13.00000
3 4 6 1	9.00000
15 2 7 8	9.00000
2 5 7 11	7.82843
1 35 38 2	38.16228

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

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main() {
    double h1, h2, l, d, a, b, r;
    cin >> d >> a >> b >> l;
    h1 = min(a,b);
    h2 = max(a,b);
    double res = h1;
    h1 = min (h1, (h2 - ((d*d - l*l)/(2*l))));
    if (h1 < 0) r = h2;
    else r = (sqrt(d*d + (h2-h1)*(h2-h1)));
    res += min(r, h2);
    cout << fixed << setprecision(5) << res;
    return 0;
}

#include <iostream>

#include <cmath>

#include <iomanip>

using namespace std;

int main() {

double h1, h2, l, d, a, b, r;

cin >> d >> a >> b >> l;

h1 = min(a,b);

h2 = max(a,b);

double res = h1;

h1 = min (h1, (h2 - ((d*d - l*l)/(2*l))));

if (h1 < 0) r = h2;

else r = (sqrt(d*d + (h2-h1)*(h2-h1)));

res += min(r, h2);

cout << fixed << setprecision(5) << res;

return 0;

}

Решение

Во-первых, поймем, что выгоднее сначала забраться на более низкий столб. Действительно, предположим, $h_1 \gt h_2$ и начинать электрик Геннадий будет с первого столба.

Заметим, что если Геннадий применит навыки человека-паука, то не сможет оказаться на втором столбе выше, чем $h_2-d$ (т.е. не выше точки $E_1$), поскольку перелетать он будет по дуге окружности, радиус которой не меньше $d$. С другой стороны, начиная с более низкого столба, он сможет перелететь в точку $E_3$ (предполагаем, что возможность воспользоваться способностью есть). При этом $H_1E_3=H_1H_2$.
Теперь сравним суммарное расстояние подъемов вверх по столбам. Если начинать с более высокого, то: $AH_1+H_2E_1=AE+H_1E+EH_2$.

С другой стороны, начиная с более низкого, получим:
$BH_2+E_3H_1=BH_2+H_1H_2$.
Заметим, что $BH_2=AE$, а по неравенству треугольника $H_1E+EH_2 \gt H_1H_2$. Отсюда и получаем, что начинать с более низкого столба экономнее.
В случае же, когда способность человека-паука применить нельзя или с её помощью Геннадий спускается до земли, не имеет значения, с какого столба начинать. Поэтому будем считать, что $h_1 \leqslant h_2$.

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

Для удобства обозначим $h_2-h_1$ через $\Delta h$, а отрезок $H_1H_2$ через $r$.
Чтобы была возможность использовать способность человека-паука, мы хотим добиться того, чтобы выполнялось следующее неравенство:
$$r — \Delta h \leqslant l $$.
Будем считать, что $h_1$ — это не высота первого столба, а высота, с которой Геннадий перелетать на второй столб (понятно, что ради удовлетворения ограничения $l$ Геннадий может только начать спускаться вниз).

Из треугольника $\Delta EH_1H_2$ выражаем $r$ :
$$r = \sqrt{d^2+\Delta h^2}.$$

Тогда неравенство принимает вид:
$$\sqrt{d^2+\Delta h^2)-\Delta h} \leqslant l,$$
$$d^2+\Delta h^2 \leqslant \frac{d^2 — l^2}{2l},$$
$$h_1 \leqslant h_2 — \frac{d^2 — l^2}{2l}.$$

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

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

Далее остается вычислить длину паутины по формуле $ r = \sqrt{d^2+\Delta h^2},$ принимая в качестве $h_1$ высоту, с которой надо стрелять паутиной, и прибавить полученную величину к высоте первого столба.

Решение задачи на ideone.com

Ссылка на контест

Related Images:

e-olymp 7239. «Все, Степан! Ти мене дістав!»

23/12/2020 by Жук Світлана

Задача

Степан нещодавно відпочивав у Японії і привіз звідти нову жувальну гумку. На першій парі в університеті він поділився гумкою зі своїм товаришем. Дочекавшись моменту, коли лектор повернувся до дошки, на рахунок «три — чотири» хлопці дружньо почали надувати бульбашки. Відомо, що Степан надуває бульбашку до максимально можливого розміру за час $t_1$, після чого бульбашка миттєво лопається, і Степан починає надувати бульбашку заново з тією ж швидкістю. Товариш Степана робить те ж саме за час $t_2$.

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

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

Наприклад, якщо $t_1 = 2$, $t_2 = 3$, то буде відбуватись наступне:

Степан надуває бульбашку з моменту часу $t = 0$ до моменту часу $t = 2$, потім бульбашка лопається, і він надуває бульбашку знову — з моменту часу $t = 2$ до моменту часу $t = 4$, а потім ще раз — з моменту часу $t = 4$ до $t = 6$.

Товариш Степана надуває бульбашку з $t = 0$ до $t = 3$ і ще раз з $t = 3$ до $t = 6$.

В момент часу $t = 6$ бульбашки лопаються одночасно в обох студентів, викладач повертається і каже: «Все, Степан! Ти мене дістав!».

Формат вхідних даних

Перший рядок вхідного файлу містить два цілих числа $t_1, t_2 (1 \leqslant t_1, t_2 \leqslant 10^9).$

Формат вихідних даних

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

Тести

№	Вхідні дані	Вихідні дані
1	2 3	6
2	1 16	16
3	10 10	10
4	100000000 150000000	300000000
5	17 41	697

Код

#include <iostream>

using namespace std;
 
long nod (int a, int b)  {
    return b == 0 ? a : nod (b, a % b);
}
 
int main() {
    int t1, t2;
    cin >> t1 >> t2;
    cout <<  t1 * (t2 / nod (t1, t2));
    return 0;
}

#include <iostream>

using namespace std;

long nod (int a, int b) {

return b == 0 ? a : nod (b, a % b);

}

int main() {

int t1, t2;

cin >> t1 >> t2;

cout << t1 * (t2 / nod (t1, t2));

return 0;

}

Розв’язання

алгоритмом Евкліда,

Посилання

Задача на e-olymp
Код на ideone
Зараховане розв’язання на e-olymp

Related Images:

e-olymp 4720. Новая игра Серёжи

22/12/2020 by Кулік Віталій

Задача

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

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

Помогите Серёже понять, расстроится он или нет.

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

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

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

Программа должна выводить слово «SAD», если Серёжа расстроится (когда точка попадает на границу Серёжа считает её принадлежащей чёрному листу, потому что не любит расстраиваться), и «HAPPY» — в обратном случае.

Тесты

№	Входные данные	Выходные данные
1	2 10 5 3 4 4 6 1 2 9	HAPPY
2	2 10 5 3 4 4 6 1 6 3	SAD
3	0 0 0 0 1 1 1 1 0 0	HAPPY
4	1 3 3 1 2 3 4 1 3 2	SAD
5	1 3 3 1 2 3 4 1 2 2	HAPPY

Код

#include <iostream>
using namespace std;

struct dot
{
    int x, y;
    dot(){
        cin >> x >> y;
    }
};
struct square
{
    dot upper_left, lower_right;
    bool is_point_on(dot &p) const
    {
        return p.x < lower_right.x and p.x > upper_left.x and p.y < upper_left.y and p.y > lower_right.y;
    }
    bool is_point_in(dot &p) const
    {
        return p.x <= lower_right.x and p.x >= upper_left.x and p.y <= upper_left.y and p.y >= lower_right.y;
    }
};

int main() {
    square black, white;
    dot point;
    cout << ((black.is_point_in(point) and not white.is_point_on(point))?"HAPPY":"SAD");
}

#include <iostream>

using namespace std;

struct dot

{

int x, y;

dot(){

cin >> x >> y;

}

};

struct square

{

dot upper_left, lower_right;

bool is_point_on(dot &p) const

{

return p.x < lower_right.x and p.x > upper_left.x and p.y < upper_left.y and p.y > lower_right.y;

}

bool is_point_in(dot &p) const

{

return p.x <= lower_right.x and p.x >= upper_left.x and p.y <= upper_left.y and p.y >= lower_right.y;

}

};

int main() {

square black, white;

dot point;

cout << ((black.is_point_in(point) and not white.is_point_on(point))?"HAPPY":"SAD");

}

Сокращенный код

#include <iostream>
using namespace std;

int main() {
    int bl_up_x, bl_up_y, bl_dw_x, bl_dw_y;
    int wh_up_x, wh_up_y, wh_dw_x, wh_dw_y;
    int p_x, p_y;
    cin >> bl_up_x >> bl_up_y >> bl_dw_x >> bl_dw_y;
    cin >> wh_up_x >> wh_up_y >> wh_dw_x >> wh_dw_y;
    cin >> p_x >> p_y;
    bool is_in_black = p_x <= bl_dw_x and p_x >= bl_up_x and p_y <= bl_up_y and p_y >= bl_dw_y;
    bool is_in_white = p_x < wh_dw_x and p_x > wh_up_x and p_y < wh_up_y and p_y > wh_dw_y;
    cout << (is_in_black and not is_in_white ? "HAPPY" : "SAD");
}

#include <iostream>

using namespace std;

int main() {

int bl_up_x, bl_up_y, bl_dw_x, bl_dw_y;

int wh_up_x, wh_up_y, wh_dw_x, wh_dw_y;

int p_x, p_y;

cin >> bl_up_x >> bl_up_y >> bl_dw_x >> bl_dw_y;

cin >> wh_up_x >> wh_up_y >> wh_dw_x >> wh_dw_y;

cin >> p_x >> p_y;

bool is_in_black = p_x <= bl_dw_x and p_x >= bl_up_x and p_y <= bl_up_y and p_y >= bl_dw_y;

bool is_in_white = p_x < wh_dw_x and p_x > wh_up_x and p_y < wh_up_y and p_y > wh_dw_y;

cout << (is_in_black and not is_in_white ? "HAPPY" : "SAD");

}

Решение

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

Ссылки

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

Related Images:

e-olymp 1602. НОК двух натуральных чисел

22/12/2020 by Федяєва Євгенія

Задача

Найдите $НОК$ (наименьшее общее кратное) двух натуральных чисел.

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

Два натуральных числа $a$ и $b$ $(a, b < 2 \cdot 10^9)$.

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

Вывести $НОК$ чисел $a$ и $b$.

Тесты

№	Входные данные	Выходные данные
1	42 24	168
2	32 14	224
3	101 45	4545

Код

#include <iostream>
using namespace std;
 
long int GCD(int num1, int num2) 
{
    if(num1 == num2) return num1;
    while(num1 && num2)
    {
        if(num1 > num2) num1 %= num2;
        else num2 %= num1;
    }
    return num1+num2;
}
 
int main() {
    long int num1, num2, gcd;
    cin >> num1 >> num2;
    gcd = GCD(num1, num2);
    cout << num1*num2/gcd;
    return 0;
}

#include <iostream>

using namespace std;

long int GCD(int num1, int num2)

{

if(num1 == num2) return num1;

while(num1 && num2)

{

if(num1 > num2) num1 %= num2;

else num2 %= num1;

}

return num1+num2;

}

int main() {

long int num1, num2, gcd;

cin >> num1 >> num2;

gcd = GCD(num1, num2);

cout << num1*num2/gcd;

return 0;

}

Решение

Пусть есть два числа $n_1$ и $n_2$. $НОК$($n_1$, $n_2$) можно вычислить по формуле $НОК(n_1, n_2)={{n_1\cdot n_2}\over{НОД(n_1, n_2)}}$. Тогда задача сводится к нахождению $НОД$ двух чисел, который вычисляется алгоритмом Евклида:
$1$. Большее число делится на меньшее.
$2$. Если остаток от деления равен нулю, то меньшее число и есть $НОД$.
$3$. Если есть остаток, то большее число заменяется на остаток от деления и все действия повторяются.
После завершения цикла в одной переменной содержится ноль, а другая равна $НОД$, но поскольку неизвестно, которая из переменных равна $НОД$, то возвращается их сумма.

Ссылки

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

Related Images:

e-olymp 1243. Наименьшее общее кратное

20/12/2020 by Максим Ливитчук

Условие

Наименьшим общим кратным ($НОК$) множества натуральных чисел называется такое наименьшее натуральное число, которое делится на каждое число в этом множестве. Например, $НОК$ чисел $5$, $7$ и $15$ равно $105$.

Вам необходимо найти $НОК$ $m$ заданных чисел.

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

Первая строка содержит количество тестов. Каждый тест состоит из одной строки и содержит числа $m$ $n_1$ $n_2$ $n_3$ $\ldots$ $n_m$, где $m$($1 \leqslant m \leqslant 100$) — количество заданных чисел, $n_1$ $\ldots$ $n_m$ — сами числа. Все числа натуральные и лежат в границах $32$-битового целого.

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

Для каждого теста в отдельной строке вывести соответствующее значение $НОК$. Все выводимые числа лежат в границах $32$-битового целого.

Тесты

№	ввод	вывод
1	2 3 5 7 15 6 4 10296 936 1287 792 1	105 10296
2	3 1 36 5 2 2 2 2 2 5 987 1597 2584 4181 6765 10946 17711	36 2 38400890173772280
3	0

Код

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

int main() {
    int n, m;
    cin >>n;
    for(int i=0; i<n; i++) {
        cin >>m;
        int temp, ans;
        cin >>ans;
        for(int j=1; j<m; j++) {
            cin >>temp;
            ans = ans/__gcd(ans, temp)*temp;
        }
        cout <<ans <<endl;
    }
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n, m;

cin >>n;

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

cin >>m;

int temp, ans;

cin >>ans;

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

cin >>temp;

ans = ans/__gcd(ans, temp)*temp;

}

cout <<ans <<endl;

}

Код с алгоритмом Евклида

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

int gcd(int a, int b) {
  while(a and b) {
    if(a>b)
      a %= b;
    else
      b %= a;
  }
  return a+b;
}

int main() {
    int n, m;
    cin >>n;
    for(int i=0; i<n; i++) {
        cin >>m;
        int temp, ans;
        cin >>ans;
        for(int j=1; j<m; j++) {
            cin >>temp;
            ans = ans/gcd(ans, temp)*temp;
        }
        cout <<ans <<endl;
    }
}

#include <iostream>

#include <algorithm>

using namespace std;

int gcd(int a, int b) {

while(a and b) {

if(a>b)

a %= b;

else

b %= a;

}

return a+b;

}

int main() {

int n, m;

cin >>n;

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

cin >>m;

int temp, ans;

cin >>ans;

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

cin >>temp;

ans = ans/gcd(ans, temp)*temp;

}

cout <<ans <<endl;

}

Решение

$\DeclareMathOperator{\lcm}{lcm}$
$НОК$ ($\lcm$) проще всего считается по формуле $\operatorname {lcm}(a,b)={\frac {|a\cdot b|}{\operatorname {gcd}(a,b)}}$, где $\gcd$ — $НОД$. Для $\lcm$ от более чем двух чисел справедлива следующая формула: $\operatorname {lcm}(a_{1},a_{2},\ldots ,a_{n})=\operatorname {lcm}(\operatorname {lcm}(a_{1},a_{2},\ldots ,a_{{n-1}}),a_{n})$, из которой видно, что подсчёт $\lcm$ от $n$ чисел сводится к вычислению $n-1$-ого $\lcm$ от очередного числа и предыдущего результата вычислений.

$НОД$ ($\gcd$) в коде считается при помощи стандартной функции __gcd(a, b) из стандартной библиотеки algorithm в первом варианте кода или по алгоритму Евклида во втором.

Ссылки

Related Images:

e-olymp 1679. Честная цепочка

19/12/2020 by Максим Ливитчук

Условие

В подземных норах в долине рядом со скалами Крейд-Моор долгое время жили в мире и согласии два гномьих племени. Гномы обоих племен работали в шахтах, добывая драгоценные камни. Первое племя добывало исключительно изумруды, а второе племя — рубины. Однажды в честь великого праздника Файрвинд гномы решили принести в дар своей богине Мирабель цепочку из изумрудов и рубинов. Самые искусные кузнецы обоих племен работали над созданием этой цепочки, собирая на ней один за одним драгоценные камни. Но как только работа была окончена, решили вожди племен пересчитать камни каждого вида. Ведь если каких-то камней окажется меньше, то богиня может отвернуться от племени, которое пожадничало. Чтобы избежать подобных последствий, было решено подарить некоторый непустой фрагмент цепочки (то есть цепь, состоящую из нескольких камней, расположенных друг за другом в исходной цепочке), в котором будет рубинов ровно столько же, сколько и изумрудов. Возможно это может быть сделано несколькими способами. Для того, чтобы узнать сколько таких способов существует, гномы обратились за помощью к вам.

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

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

В единственной строке задается последовательность камней в исходной цепочке: символ E обозначает изумруд, символ R — рубин. Количество символов в строке не превышает $500000$.

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

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

Тесты

№	ввод	вывод
1	REER	3
2	REERREER	12
3	RRRRRRRR	0
4	EREREERERERREREREEERERERERERRREREREERERERERE	273
5	REEERREE	7

Код

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

int main() {
    int cnt = 0;
    char buf;
    map<int, long long> mp;
    mp[0] = 1;
    while(cin >>buf) {
        if(buf=='R')
            cnt++;
        else
            cnt--;
        mp[cnt]++;
    }
    long long answer = 0;
    for(auto e: mp) {
        answer += e.second*(e.second-1)/2;
    }
    cout <<answer;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

int cnt = 0;

char buf;

map<int, long long> mp;

mp[0] = 1;

while(cin >>buf) {

if(buf=='R')

cnt++;

else

cnt--;

mp[cnt]++;

}

long long answer = 0;

for(auto e: mp) {

answer += e.second*(e.second-1)/2;

}

cout <<answer;

}

Компактный код

#include 
#include <map>
using namespace std;
 
int main() {
    int cnt = 0;
    char buf;
    map mp;
    mp[0] = 1;
    while(cin >>buf) mp[buf=='R'?++cnt:--cnt]++;
    long long a = 0;
    for(auto e: mp) a += e.second*(e.second-1)/2;
    cout <<a;
}

#include

#include <map>

using namespace std;

int main() {

int cnt = 0;

char buf;

map mp;

mp[0] = 1;

while(cin >>buf) mp[buf=='R'?++cnt:--cnt]++;

long long a = 0;

for(auto e: mp) a += e.second*(e.second-1)/2;

cout <<a;

}

Решение

Составим массив из $n+1$ чисел, каждое из которых будет располагаться в месте возможного начала или конца фрагмента цепочки, который гномы должны вручить богине. Число в самом начале цепочки возьмём равным $0$, а все следующие числа будут представлять из себя количество R минус количество E, встречающихся в фрагменте с начала до этого числа.

Наглядный пример такого массива для пятого примера (подписан как cnt)

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

Выделенные в том же примере фрагменты с началом и концом в 0 и -2

Так как нам не важны конкретные правильные фрагменты, а только их суммарное количество, нам будет достаточно знать, сколько раз в массиве встречается то или иное число. В коде эту информацию хранит ассоциативная таблица mp. Запись mp[cnt]++; создаёт новый равный нулю элемент по ключу cnt, если раньше в структуре его не было, после чего инкрементирует значение.
Сам же массив воспроизводится на ходу из ввода, в переменной cnt. В конце программы количество фрагментов считается как сумма $\frac{n(n-1)}{2}$, где $n$ — mp[i] для всех встречавшихся в массиве чисел.

Ссылки

Related Images:

e-olymp 7095. Факторіали

13/12/2020 by Федяєва Євгенія

Задача

Президент Першого національного Банку майор Томаса Б. Кiнгмена кожну ніч перекладає вміст сейфів, у яких клієнти банку зберігають свої коштовності. Грабіжникам це також відомо, і тому вони орендували один із сейфів у цьому банку й чекають, поки президент перекладе в їхній сейф щось цінне. Таким чином до їхніх рук потрапила скринька з коштовностями самого майора! Тепер у грабіжників є всього лиш кілька годин для того, щоб відкрити кодовий замок з трьох цифр, забрати цінності й повернути скриньку назад, щоб ніхто навіть не дізнався, що пограбування взагалі відбулося.

Знаючи пристасть майора до великих чисел, грабіжники переконані, що кодом є три послідовні цифри числа $N!$, що записують безпосередньо перед нулями наприкінці запису числа $N!$. Наприклад:

при $N$ = $7$ кодом буде $504$, бо $7!$ = $5040$;
при $N$ = $17$ кодом буде $096$, бо $17!$ = $355687428096000$.

За даним натуральним числом $N$ знайти три послідовні цифри числа $N!$, що записують безпосередньо перед нулями наприкінці запису числа $N!$.

Вхідні дані

Вхідний файл містить єдине ціле число $N$. $(7 \leqslant N \leqslant 1000000000)$.

Вихідні дані

Вихідний файл має містити рівно три цифри — шуканий код.

Тесты

№	Входные данные	Выходные данные
1	7	504
2	17	096
3	50	512
4	1000000000	144

Код

#include <iostream>

#define COEF 10000000
#define TEN 10

using namespace std;

unsigned int arr[] = { 1, 94194688,80754176,28792576,93638144,44194688,16269824,94550272,61946112,68933632,
                       68754176,19323648,22612992,36351232,57997312,66792576,2167808,95748096,88043776,
                       37690112,65638144,99247872,80831232,42968832,38960896,2194688,36401664,29433088,
                       21091328,35679232,40269824,3200512,39416576,62174976,23727104,49750272,52626176,
                       72337664,68916224,93513984,25146112,14722816,60257024,2170112,13989632,28933632,
                       91983872,29619968,23259904,52859904,2354176,61171456,14485248,81225984,93129472,
                       98123648,42294528,83940096,91339008,90945024,77812992,83786752,30308352,33122816,
                       709376,45551232,13495552,4053504,28486912,65094912,93197312,79194112,80894208,
                       48729344,89670656,26832576,59147776,51826688,14217984,72698112,10487808,29000448,
                       21455616,72560128,94383616,23588096,83462144,14917632,85698816,11810304,3083776,
                       84299264,11034368,6525952,27101696,68170112,92235008,45980416,15386112,44244224,
                       3398144 };
int main()
{
    int N;
    unsigned long long factorial = 1;
    cin >> N;
    int idx = N/COEF;
    factorial = arr[idx];
    int start = !N%COEF ? idx*COEF : idx*COEF + 1;
    if (N % COEF != 0)
    {
        for(int i = start; i <= N; i++)
        {
            factorial *= i;
            while(factorial % TEN == 0) factorial /= TEN;
            factorial %= COEF;
        }
    }
    factorial %= TEN*TEN*TEN;
    cout << factorial/(TEN*TEN) << (factorial/TEN)%TEN << factorial%TEN;
    return  0;
}

#include <iostream>

#define COEF 10000000

#define TEN 10

using namespace std;

unsigned int arr[] = { 1, 94194688,80754176,28792576,93638144,44194688,16269824,94550272,61946112,68933632,

68754176,19323648,22612992,36351232,57997312,66792576,2167808,95748096,88043776,

37690112,65638144,99247872,80831232,42968832,38960896,2194688,36401664,29433088,

21091328,35679232,40269824,3200512,39416576,62174976,23727104,49750272,52626176,

72337664,68916224,93513984,25146112,14722816,60257024,2170112,13989632,28933632,

91983872,29619968,23259904,52859904,2354176,61171456,14485248,81225984,93129472,

98123648,42294528,83940096,91339008,90945024,77812992,83786752,30308352,33122816,

709376,45551232,13495552,4053504,28486912,65094912,93197312,79194112,80894208,

48729344,89670656,26832576,59147776,51826688,14217984,72698112,10487808,29000448,

21455616,72560128,94383616,23588096,83462144,14917632,85698816,11810304,3083776,

84299264,11034368,6525952,27101696,68170112,92235008,45980416,15386112,44244224,

3398144 };

int main()

{

int N;

unsigned long long factorial = 1;

cin >> N;

int idx = N/COEF;

factorial = arr[idx];

int start = !N%COEF ? idx*COEF : idx*COEF + 1;

if (N % COEF != 0)

{

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

{

factorial *= i;

while(factorial % TEN == 0) factorial /= TEN;

factorial %= COEF;

}

factorial %= TEN*TEN*TEN;

cout << factorial/(TEN*TEN) << (factorial/TEN)%TEN << factorial%TEN;

return 0;

}

Решение

Поскольку процесс расчёта факториала больших чисел занимает много времени, его можно ускорить использованием массива факториалов некоторых чисел. Полное значение факториала не нужно, поэтому массив содержит последние $8$ ненулевых цифр значений факториалов чисел, кратных $10000000$, которые можно получить с помощью следующего кода:

#include <iostream>
#define TEN 10
using namespace std;
int main()
{
    int N = 1000000000, count = 1;
    unsigned long long factorial = 1;
    for(int i = 1; i <= N; i++)
    {
        factorial *= i;
        while(factorial%TEN == 0) factorial /= TEN;
        factorial %= 100000000;
        if (i % 10000000 == 0) {cout << factorial << ","; count++;}
        if (count == TEN) {cout << endl; count = 1;}
    }
    return  0;
}

#include <iostream>

#define TEN 10

using namespace std;

int main()

{

int N = 1000000000, count = 1;

unsigned long long factorial = 1;

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

{

factorial *= i;

while(factorial%TEN == 0) factorial /= TEN;

factorial %= 100000000;

if (i % 10000000 == 0) {cout << factorial << ","; count++;}

if (count == TEN) {cout << endl; count = 1;}

}

return 0;

}

Если на входе — число $N$, меньшее $10000000$, его факториал рассчитывается обычным циклом, попутно отбрасывая ненужные цифры высших разрядов. В конце выводятся искомые последние три цифры факториала числа $N$. Если на входе — число $N$, большее $10000000$, выбирается соответствующее значение из массива по индексу $N/10000000$, и далее с помощью цикла считается произведение оставшихся чисел из $N!$. С уменьшением кратности чисел, факториалы которых содержатся в массиве, увеличивается скорость выполнения программы.

Ссылки

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

Related Images:

e-olymp 4739. Решето Эратосфена

08/12/2020 by Oleksandr.Ivanov

Задача

По заданным числам $a$ и $b$ вывести все простые числа в интервале от $a$ до $b$ включительно.

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

Два числа $a$ и $b \ (1 \leqslant a \leqslant b \leqslant 100000)$.

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

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

Тесты

№	Входные данные	Выходные данные	Объяснение
1	2 2	2
2	1 100	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
3	50 100	53 59 61 67 71 73 79 83 89 97
4	10 2		Неправильно, так как противоречит условию ($a \leqslant b$)
5	99900 100000	99901 99907 99923 99929 99961 99971 99989 99991
6	-15 -6	-13 -11 -7	Неправильно, так как противоречит условию ($1 \leqslant a \leqslant b \leqslant 100000$)

Код

#include <iostream>
#include <cmath>

using namespace std;


bool eratosthenesSieve(int currentNumber) {
    /*
    Describe the function that checks if the number is prime and returns a boolean value.
    This function is based on the "sieve of Eratosthenes" algorithm.
    True - if the number is prime, false - normal.
    */
    
    // If the number equals to 1 or if it even, return false. And if it equals to 2, return true.
    if (currentNumber == 2 or currentNumber == 3) {
        return true;
    } else if (!(currentNumber % 2) or !(currentNumber % 3) or currentNumber == 1) {
        return false;
    }
    
    // If the number has the divider from 5 to the root of this number with the second step return false.
    for (int divider = 5; divider <= sqrt(currentNumber); divider += 2) {
        if (!(currentNumber % divider)) {
            return false;
        }
    }
    
    // In all other situations, return true.
    return true;
}


void printSequenceOfPrimeNumbers(int beginning, int ending) {
    /*
    This function prints all prime numbers in a line.
    It contains a loop that starts and ends with the given values.
    */

    for (int sequenceElement = beginning; sequenceElement <= ending; sequenceElement += 1) {
        if (eratosthenesSieve(sequenceElement)) {
            cout << sequenceElement << " ";
        }
    }
}


int main() {
    /*
    Receive the beginning and end of the sequence.
    */
    
    int beginning, ending;
    cin >> beginning >> ending;
    
    // Calling the function.
    printSequenceOfPrimeNumbers(beginning, ending);

    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

bool eratosthenesSieve(int currentNumber) {

Describe the function that checks if the number is prime and returns a boolean value.

This function is based on the "sieve of Eratosthenes" algorithm.

True - if the number is prime, false - normal.

// If the number equals to 1 or if it even, return false. And if it equals to 2, return true.

if (currentNumber == 2 or currentNumber == 3) {

return true;

} else if (!(currentNumber % 2) or !(currentNumber % 3) or currentNumber == 1) {

return false;

}

// If the number has the divider from 5 to the root of this number with the second step return false.

for (int divider = 5; divider <= sqrt(currentNumber); divider += 2) {

if (!(currentNumber % divider)) {

return false;

}

// In all other situations, return true.

return true;

}

void printSequenceOfPrimeNumbers(int beginning, int ending) {

This function prints all prime numbers in a line.

It contains a loop that starts and ends with the given values.

for (int sequenceElement = beginning; sequenceElement <= ending; sequenceElement += 1) {

if (eratosthenesSieve(sequenceElement)) {

cout << sequenceElement << " ";

}

int main() {

Receive the beginning and end of the sequence.

int beginning, ending;

cin >> beginning >> ending;

// Calling the function.

printSequenceOfPrimeNumbers(beginning, ending);

return 0;

}

Решение

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

Это решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых.

Рассуждение:
— Все четные числа, не считая двойки, — составные, то есть не являются простыми, так как делятся не только на себя и единицу, а также еще на $2$.
— Все числа кратные трем, кроме самой тройки, — составные, так как делятся не только на самих себя и единицу, а также еще на $3$.
— Число $4$ уже выбыло из игры, так как делится на $2$.
— Число $5$ простое, так как его не делит ни один простой делитель, стоящий до него.
— Если число не делится ни на одно простое число, стоящее до него, значит оно не будет делиться ни на одно сложное число, стоящее до него.

В моем коде, указанном выше, была реализована функция-фильтр, которая, по большей части, реализовывает метод перебора делителей и проверяет: есть ли делители числа, кроме его самого, вплоть до корня из этого числа. И если остатки от деления не равны $0$, то мы возвращаем истину, что означает: число простое.

Таким же образом, проверяем все остальные числа из промежутка от $n$ до $m$ и выводим полученную последовательность на экран.

Ссылки

Related Images:

e-olymp 7110. Весы

02/12/2020 by Натан Чачко

Задача

Измерение веса предмета осуществляется с помощью лабораторных весов. С помощью набора из $7$ гирь весом $1$ г, $3$ г, $9$ г, $27$ г, $81$ г, $243$ г и $729$ г можно измерить вес любого предмета с целым весом от $1$ до $1093$ г единственным способом. Например, для измерения предмета весом $4$ г необходимо на одну чашу положить гири в $1$ и $3$ г, а на другую сам предмет, а, скажем, для предмета весом $68$ г на чашку с ним добавляются гири в $1$, $3$ и $9$ г, а на другую — гиря в $81$ г.

Определите, сколько гирь из данного набора необходимо использовать для взвешивания предмета заданного веса.

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

Одно натуральное число $x \ (1 \leqslant x \leqslant 1000)$ — вес предмета.

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

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

Тесты

№	Входные данные	Выходные данные
1	4	2
2	68	4
3	27	1
4	555	5
5	1000	4

Код

#include <iostream>
#define NUM 3
#define POW 729
using namespace std;
 
int nearest(int weight) {
    for (int i = 1; i < POW; i*=NUM){
        if (abs(i - weight) < abs(i*NUM - weight)) {
            return i;
        }
    }
}
 
int main() {
  int right_bowl, left_bowl = 0, count = 0;
  cin >> right_bowl;
  while (right_bowl != left_bowl) {
    if (right_bowl > left_bowl) {
            left_bowl += nearest(abs(right_bowl - left_bowl));
        }
    else right_bowl += nearest(abs(right_bowl - left_bowl));
    count++;
  }
  cout << count;
}

#include <iostream>

#define NUM 3

#define POW 729

using namespace std;

int nearest(int weight) {

for (int i = 1; i < POW; i*=NUM){

if (abs(i - weight) < abs(i*NUM - weight)) {

return i;

}

int main() {

int right_bowl, left_bowl = 0, count = 0;

cin >> right_bowl;

while (right_bowl != left_bowl) {

if (right_bowl > left_bowl) {

left_bowl += nearest(abs(right_bowl - left_bowl));

}

else right_bowl += nearest(abs(right_bowl - left_bowl));

count++;

}

cout << count;

}

Решение

Пусть предмет располагается на правой чаше весов. Тогда на левой чаше первым делом мы должны расположить ближайшую по весу гирю. Если этой гири оказывается недостаточно для уравновешивания весов, тогда мы добавляем на левую чашу еще одну гирю, вес которой будет ближе всех к разности весов на чашах. Повторяем операцию, пока чаши не уравняются. Если же вес левой чаши будет больше правой, то по такому же принципу добавляем гири на правую чашу. И с каждым добавлением гири увеличиваем счетчик, значение которого выводится при уравновешивании весов. И хоть такой ход решения не полностью удовлетворяет условию задачи, так как в некоторых случаях одни и те же гири используются дважды, тем не менее ответ всегда будет совпадать с ответом решения исходной задачи. Это было проверено с помощью сайта, который сравнил результаты работы двух программ, которые выдают все ответы моего решения и правильного.

Ссылки

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

Related Images:

e-olymp 9066. Кружок стрельбы

03/03/2020 by Владислав Гринькив

Задача

После успешного обучения Атрея стрельбе из лука «Когтя» Фэй решила не останавливаться на достигнутом и открыть целый кружок стрельбы из лука.

На занятие кружка пришли $n$ учеников. Фэй пронумеровала их целыми числами от $1$ до $n$. В начале занятия ученики встали вдоль координатной прямой, заблаговременно нарисованной на полу, причем i-й ученик стоял в точке с координатой $x_i$. Получилось так, что координаты учеников строго возрастали, то есть $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

У каждого из учеников есть свой волшебный лук, который характеризуется своей дальностью $r_i$ и силой $c_i$. Оба параметра — целые положительные числа. Когда ученик совершает выстрел из лука, магический снаряд начинает лететь вдоль координатной прямой в сторону увеличения координаты. Снаряд летит до тех пор, пока его сила положительна. В момент выстрела сила заряда равна силе лука, из которого совершается выстрел. Каждый раз, когда снаряд пролетает очередные $r_i$ единиц расстояния вдоль прямой, он теряет одну единицу силы.

Если ученик произвел выстрел, и снаряд, выпущенный им, достиг следующего по порядку вдоль прямой ученика, снаряд прекращает свой полет, а ученик, которого достиг снаряд, внезапно решает, что ему тоже надо произвести выстрел, и совершает его. Ученик совершит выстрел, даже если снаряд достиг его, имея силу $0$.

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

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

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

Первая строка содержит количество учеников $n$ $(1 \leqslant n \leqslant 1000)$ на кружке Фэй.

Каждая из следуюших $n$ строк содержит три целых числа $x_i$, $r_i$ и $c_i$ ($1 \leqslant x_i \leqslant 10^9$, $1 \leqslant r_i$, $c_i \leqslant 100$) — координату очередного ученика, а также дальность и силу его лука соответственно. Гарантируется, что $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

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

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

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 1 3 3 5 1 2 8 2 3 10 1 2 11 3 2	2
2	6 1 3 5 4 2 2 7 4 3 10 1 2 11 3 2 13 4 3	1

Код

#include <iostream>
using namespace std;
struct archerProfile {
  unsigned long x;
  unsigned long r;
  unsigned int c;
}archer[1000];
int main(){ 
  int n;
  int commands = 1;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> archer[i].x >> archer[i].r >> archer[i].c;
  }
  for (int i = 0; i < n - 1; i++) {
    unsigned long long distanceBetweenArchers = archer[i + 1].x - archer[i].x;
    if (distanceBetweenArchers > archer[i].c * archer[i].r) {
      commands += 1;
    }
  }
  cout << commands;
  return 0;
}

#include <iostream>

using namespace std;

struct archerProfile {

unsigned long x;

unsigned long r;

unsigned int c;

}archer[1000];

int main(){

int n;

int commands = 1;

cin >> n;

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

cin >> archer[i].x >> archer[i].r >> archer[i].c;

}

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

unsigned long long distanceBetweenArchers = archer[i + 1].x - archer[i].x;

if (distanceBetweenArchers > archer[i].c * archer[i].r) {

commands += 1;

}

cout << commands;

return 0;

}

Решение

Для решения задачи, мы должны найти расстояние между лучниками, то есть $x_{i+1}-x_i$, после чего найти максимальное расстояние, которое пролетит стрела у $x_{i}$ лучника умножив силу его лука $c_i$ и расстояние $r_i$, после чего сделать проверку, если расстояние между лучниками больше чем максимальное расстояние которое пролетит стрела, то мы дадим команду совершить ещё один выстрел.

Ссылки

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

Related Images:

e-olymp 1288. n-значные числа

02/02/2020 by Владислав Стасюк

Задача:

Сколько натуральных $n$ -значных чисел начинаются с цифры $a$ или цифры $b$?

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

Заданы три целых числа: натуральное $n$ [latex](0 \lt n \leqslant 10^6)[/latex] и целые $a$ и $b$. Все данные, как и само условие задачи, заданы в десятичной системе счисления.

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

Вывести количество натуральных $n$ -значных чисел, которые начинаются с цифры $a$ или цифры $b$.

Тесты:

Ввод	Вывод
3 3 4	200
1 2 2	1
4 0 0	0
10 9 9	1000000000

Код:

#include <iostream>
using namespace std;

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    string s;
    if (a + b == 0) cout << 0 << endl;
    else
    {
        if ((a == b) or !(a * b)) cout << 1;
        else cout << 2;
        for (int i = 0; i < n - 1; i++) s += '0';
        cout << s << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, a, b;

cin >> n >> a >> b;

string s;

if (a + b == 0) cout << 0 << endl;

else

{

if ((a == b) or !(a * b)) cout << 1;

else cout << 2;

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

cout << s << endl;

}

return 0;

}

Решение:

Среди однозначных чисел с каждой цифры начинается только одно число.
Среди двухзначных чисел с одной цифры начинается уже десять чисел.
Среди трехзначных — сто и так далее. Легко заметить закономерность, что в количестве чисел, начинающихся с определенной цифры, единица всегда остается, а к ней приписывают $n-1$ нулей, где $n$ — количество разрядов.
Если мы ищем количество чисел начинающихся уже с двух разных цифр, то единица меняется на двойку, а количество нулей сохраняется.

Отсюда и решение задачи — последовательная проверка всех вариантов и вывод ответа.

Ссылки:

e-olymp
ideone

Related Images:

e-olymp 1206. f91

29/01/2020 by Владислав Гринькив

Задача

МакКарти — известный теоретик компьютерных наук. В одной из своих работ он определил рекурсивную функцию $f_{91}$, которая определена для всякого натурального числа $n$ следующим образом:

Если $n\leqslant100$, то $f_{91}\left(n\right) = f_{91}\left(f_{91}\left(n+11\right)\right)$;

Если $n\geqslant101$, то $f_{91}\left(n\right) = n-10$.

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

Натуральное число $n$, не большее $1000000$.

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

Значение $f_{91}\left(n\right)$.

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5	91
2	27	91
3	91	91
4	100	91
5	102	92
6	180	170

Код

#include <iostream>
using namespace std;
long f91(long n) {
  if(n <= 100){
    return 91;
  }
  else {
    return n - 10;
  }
}
int main() {
  long n;
  cin >> n;
  cout << f91(n);
  return 0;
}

#include <iostream>

using namespace std;

long f91(long n) {

if(n <= 100){

return 91;

}

else {

return n - 10;

}

int main() {

long n;

cin >> n;

cout << f91(n);

return 0;

}

Решение

Для решения задачи создадим функцию $f_{91}\left(n\right)$ которая в зависимости от значения $n$ будет выдавать нам разные значение, а имеено:
если $n\leqslant100$, то $f_{91}\left(n\right) = f_{91}\left(f_{91}\left(n+11\right)\right)$;
если $n\geqslant101$, то $f_{91}\left(n\right) = n-10$.
Так же, мы можем проследить законномерность того, что если $n\leqslant100$ функция $f_{91}\left(n\right)$ будет выдавть $91$, заметив это можно будет заменить сложную, но при этом красивую рекурсивную функцию на более простое и практичное решение и получить следущие соотношение:
$f_{91}\left(n\right) = \begin{cases} 91, & n\leqslant100;\\ n-10, & n\geqslant101; \end{cases}$

Ссылки

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

Related Images:

e-olymp 8663. Задача про множення

09/01/2020 by Эвелина Алексютенко

Задача

На уроці математики Байтик навчився множити, і почав застосовувати цю операцію з різними числами. Наприклад, розкладав число на цифри і знаходив добуток цифр. І тут він задумався, який найбільший добуток цифр серед натуральних чисел, що не перевищує [latex]N[/latex]. Допоможіть розв’язати задачу.

Вхідні дані

Одне число [latex]N(1\leqslant N\leqslant 2\times 10^{9})[/latex].

Вихідні дані

Максимальний добуток цифр серед чисел, що не перевищують [latex]N[/latex].

Тести

Вхідні дані	Вихідні дані
57	36
1000	729
7999	5103
28994	10368
4876	2268

Код програми

#include <iostream>
using namespace std;

int multiplication(int x) {
    int mul = 1;
    while(x != 0) {
        mul *= x % 10;
        x /= 10;
    }
    return mul;
}
int main() {
  int n;
  cin >> n;
  int maxmul = multiplication(n);  
  int copy = n;
  int i = 10;
  while(n != 0) {
      int temporary_number = (copy / (i / 10)) % 10;
      int left = copy / i;
      int right = copy % (i / 10);
      if(temporary_number != 9) {
        temporary_number = 9;
        copy = ((left - 1) * 10 + temporary_number) * (i / 10) + right;
      }
      n /= 10;
      i *= 10;
      int mul = multiplication(copy);
      if(maxmul < mul) maxmul = mul;
    }  
    cout << maxmul; 
}

#include <iostream>

using namespace std;

int multiplication(int x) {

int mul = 1;

while(x != 0) {

mul *= x % 10;

x /= 10;

}

return mul;

}

int main() {

int n;

cin >> n;

int maxmul = multiplication(n);

int copy = n;

int i = 10;

while(n != 0) {

int temporary_number = (copy / (i / 10)) % 10;

int left = copy / i;

int right = copy % (i / 10);

if(temporary_number != 9) {

temporary_number = 9;

copy = ((left - 1) * 10 + temporary_number) * (i / 10) + right;

}

n /= 10;

i *= 10;

int mul = multiplication(copy);

if(maxmul < mul) maxmul = mul;

}

cout << maxmul;

}

Алгоритм

Складність задачі полягає в обмеженості у часі.

Знайдемо добуток цифр заданого числа.
Змінемо останню цифру на [latex]9[/latex] та віднімемо [latex]1[/latex] від попереднього розряду. Визначаємо поточний добуток цифр отриманого числа. Повторюємо цю операцію з наступними розрядами числа.
Порівнюємо поточний добуток з максимальним.

Приклад:

Приклад розкладу числа на різних етапах алгоритму:

Посилання

Задача на e-olymp
Зарахований розв’язок
Код на ideone

Related Images:

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

04/01/2020 by Владислав Гринькив

Задача

Вычислить значение $a^b$.

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

Два натуральных числа $a$ и $b$.

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

Выведите значение $a^b$, если известно что оно не превосходит $10^{18}$.

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1 100	1
2	2 10	1024
3	3 7	2187
4	8 9	134217728
5	10 10	10000000000
6	100 9	1000000000000000000

Код

#include <iostream>
using namespace std;

long pow(long a, long b) {
  if(b == 0){
    return 1;
  }
  if(b % 2 == 0){
    return pow(a * a, b / 2);
  }
  return a * pow(a, b - 1);
}

int main() {
  long a, b;
  cin >> a >> b;
  cout << pow(a,b);
  return 0;
}

#include <iostream>

using namespace std;

long pow(long a, long b) {

if(b == 0){

return 1;

}

if(b % 2 == 0){

return pow(a * a, b / 2);

}

return a * pow(a, b - 1);

}

int main() {

long a, b;

cin >> a >> b;

cout << pow(a,b);

return 0;

}

Решение

Для решения задачи создадим функцию «pow()», заметим, что для любого числа $a$ и чётного числа $b$ выполнимо очевидное тождество (следующее из ассоциативности операции умножения):
$$a^b = \left(a^2\right)^{\frac{b}{2}}= \left(a\cdot a\right)^{\frac{b}{2}}$$
Оно и является основным в методе бинарного возведения в степень. Действительно, для чётного $b$ мы показали, как, потратив всего одну операцию умножения, можно свести задачу к вдвое меньшей степени.
Осталось понять, что делать, если степень b нечётна. Здесь мы поступаем очень просто: перейдём к степени b-1, которая будет уже чётной:
$$a^b = a^{b-1} \cdot a$$
Итак, мы фактически нашли рекуррентную формулу: от степени $b$ мы переходим, если она чётна, к $\frac{b}{2}$, а иначе — к $b-1$.

Примечание

Задача требует использование быстрого алгоритма, так как прямое умножение $b$ раз для возведение в $b$-ю слишком медленно, из-за большого количества перемножений. Алгоритм быстрого возведения в степень — это предназначенный для возведения числа в натуральную степень за меньшее число умножений, чем это требуется в определении степени.

Ссылки

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

Related Images:

e-olymp 365. Рамка

21/12/2019 by Александр Рапчинский

Задача

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

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

Заданы через пробел $8$ чисел — координаты начала и конца отрезка и координаты противоположных углов рамки. Координаты — целые числа, не превышающие по модулю $35000$.

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

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

Тесты

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

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

#include <iostream>
#include <algorithm>
using namespace std;
 
int distance(int a, int b, int c, int d) {
    int ans = 0;
    if (a > b) {
        swap(a, b);
    }
    if (c > d) {
        swap(c, d);
    }
    if (b < c || a > d) {
        ans = 0;
    } 
    else {
        int l = 0, r = 0;
        l = max(a, c);
        r = min(b, d);
        ans = r - l;
    }
    return ans;
}
 
int main() {
    int x1, y1, x2, y2, x3, y3, x4, y4;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
    if (x1 != x2) {
        cout << (y1 < max(y3, y4) && y1 > min(y3, y4) ? distance(x1, x2, x3, x4) : 0); 
    }
    else {
        cout << (x1 < max(x3, x4) && x1 > min(x3, x4) ? distance(y1, y2, y3, y4) : 0);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int distance(int a, int b, int c, int d) {

int ans = 0;

if (a > b) {

swap(a, b);

}

if (c > d) {

swap(c, d);

}

if (b < c || a > d) {

ans = 0;

}

else {

int l = 0, r = 0;

l = max(a, c);

r = min(b, d);

ans = r - l;

}

return ans;

}

int main() {

int x1, y1, x2, y2, x3, y3, x4, y4;

cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

if (x1 != x2) {

cout << (y1 < max(y3, y4) && y1 > min(y3, y4) ? distance(x1, x2, x3, x4) : 0);

}

else {

cout << (x1 < max(x3, x4) && x1 > min(x3, x4) ? distance(y1, y2, y3, y4) : 0);

}

return 0;

}

Решение

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

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

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

Обозначим искомую длину как $ans$, тогда $ans = min(x_{2}, x_{4})-max(x_{1}, x_{3})$.

Для ординат $ans = min(y_{2}, y_{4})-max(y_{1}, y_{3})$.

Ссылки

Условие задачи на 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 9107. Не разделяйте атом!

14/12/2019 by Владислав Шиманский

Задача

Два сумасшедших (и злых) ученых, профессор Зум и доктор Ужасный, только что получили [latex] n [/latex] атомов очень редкого элемента, которым они хотят поделиться между собой. Они решили сыграть в следующую игру:

Сначала профессор делит атомы на две непустые группы. Затем доктор берет одну группу и использует ее для своих злых целей, а другую разделяет на две непустые части. Затем профессор берет одну из частей и снова делит другую на две части, возвращая ее доктору. Игра продолжается — с каждым ходом ученый берет одну из частей и разделяет другую — пока один из игроков не будет вынужден разделить один атом. Это приводит к взрыву, и неудачный сплиттер проигрывает игру (вероятно, с его жизнью).

Зная количество атомов [latex] n [/latex], определите, кто из злодеев выживет в игре.

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

Первая строка содержит количество тестов [latex] z [/latex] [latex]left(1 leqslant zleqslant50right)[/latex] . Далее следуют описания тестов.

Каждый тест содержит одно целое число [latex] n [/latex] [latex]left(1 leqslant n leqslant10^{6}right)[/latex] — начальное количество атомов.

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

Для каждого теста выведите строку, содержащую один символ: ‘A‘, если профессор выиграет игру, и ‘B‘, если победит доктор

Тесты

№	Входные данные	Выходные данные
1	2 5 6	B A
2	2 2 17	A B
3	2 11 15	B B
4	2 12 16	A A
5	3 101 110 111	B A B

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

#include <iostream>
using namespace std;

int main() {
    int z, n;
    cin >> z;
    for ( int i = 0; i < z; i++ ) {
        cin >> n;
        if ( n % 2 == 0 ) { // Проверка на чётность
            cout << "A" << endl;
        }
        else {
            cout << "B" << endl;
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int z, n;

cin >> z;

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

cin >> n;

if ( n % 2 == 0 ) { // Проверка на чётность

cout << "A" << endl;

}

else {

cout << "B" << endl;

}

return 0;

}

Решение

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

Ссылки

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 1327. Ладьи на шахматной доске

14/12/2019 by Эвелина Алексютенко

Задача

Ещё в детстве маленького Гарика заинтересовал вопрос: а сколькими способами на шахматной доске размером [latex]n \times n[/latex] можно расставить [latex] n [/latex] ладей так, чтобы они не били друг друга. Он очень долго решал эту задачку для каждого варианта, а когда решил — бросил шахматы.

А как быстро Вы управитесь с этой задачкой?

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

Размер шахматной доски — натуральное число, не превышающее [latex] 1000 [/latex].

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

Выведите ответ, найденный Гариком.

Тесты

Входные данные	Выходные данные
2	2
10	3628800
500	122013682599111006870123878542304692625357434280319284219241 358838584537315388199760549644750220328186301361647714820358 416337872207817720048078520515932928547790757193933060377296 085908627042917454788242491272634430567017327076946106280231 045264421887878946575477714986349436778103764427403382736539 747138647787849543848959553753799042324106127132698432774571 554630997720278101456108118837370953101635632443298702956389 662891165897476957208792692887128178007026517450776841071962 439039432253642260523494585012991857150124870696156814162535 905669342381300885624924689156412677565448188650659384795177 536089400574523894033579847636394490531306232374906644504882 466507594673586207463792518420045936969298102226397195259719 094521782333175693458150855233282076282002340262690789834245 171200620771464097945611612762914595123722991334016955236385 094288559201872743379517301458635757082835578015873543276888 868012039988238470215146760544540766353598417443048012893831 389688163948746965881750450692636533817505547812864000000000 000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000
999	402387260077093773543702433923003985719374864210714632543799 910429938512398629020592044208486969404800479988610197196058 631666872994808558901323829669944590997424504087073759918823 627727188732519779505950995276120874975462497043601418278094 646496291056393887437886487337119181045825783647849977012476 632889835955735432513185323958463075557409114262417474349347 553428646576611667797396668820291207379143853719588249808126 867838374559731746136085379534524221586593201928090878297308 431392844403281231558611036976801357304216168747609675871348 312025478589320767169132448426236131412508780208000261683151 027341827977704784635868170164365024153691398281264810213092 761244896359928705114964975419909342221566832572080821333186 116811553615836546984046708975602900950537616475847728421889 679646244945160765353408198901385442487984959953319101723355 556602139450399736280750137837615307127761926849034352625200 015888535147331611702103968175921510907788019393178114194545 257223865541461062892187960223838971476088506276862967146674 697562911234082439208160153780889893964518263243671616762179 168909779911903754031274622289988005195444414282012187361745 992642956581746628302955570299024324153181617210465832036786 906117260158783520751516284225540265170483304226143974286933 061690897968482590125458327168226458066526769958652682272807 075781391858178889652208164348344825993266043367660176999612 831860788386150279465955131156552036093988180612138558600301 435694527224206344631797460594682573103790084024432438465657 245014402821885252470935190620929023136493273497565513958720 559654228749774011413346962715422845862377387538230483865688 976461927383814900140767310446640259899490222221765904339901 886018566526485061799702356193897017860040811889729918311021 171229845901641921068884387121855646124960798722908519296819 372388642614839657382291123125024186649353143970137428531926 649875337218940694281434118520158014123344828015051399694290 153483077644569099073152433278288269864602789864321139083506 217095002597389863554277196742822248757586765752344220207573 630569498825087968928162753848863396909959826280956121450994 871701244516461260379029309120889086942028510640182154399457 156805941872748998094254742173582401063677404595741785160829 230135358081840096996372524230560855903700624271243416909004 153690105933983835777939410970027753472000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000

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

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
vector<int> multiply (const vector<int> &s, int b, int base) {
  vector<int> c;
  int carry = 0;
  for (int i = 0; i < s.size(); i++) {
    long long res = (long long)s[i] * b + carry;
    carry = res / 1000;
    c.push_back(res % base);    
  }
  if (carry > 0) { // если в разряде переноса все еще остались цифры
    c.push_back(carry);
  }
  return c;
}
int main() {
  int n;
  int base = 1000;
  cin >> n;
  vector<int> res;
  res.push_back(0);
  res.push_back(1);
  for (int i = 1; i < n; i++) {
    res = multiply(res, i + 1, base);
  }
  cout << res[res.size() - 1];
  for (int i = res.size() - 2; i >= 1; i--) {
    cout << setw(3) << setfill('0') << res[i];
  }
}

#include <iostream>

#include <vector>

#include <iomanip>

using namespace std;

vector<int> multiply (const vector<int> &s, int b, int base) {

vector<int> c;

int carry = 0;

for (int i = 0; i < s.size(); i++) {

long long res = (long long)s[i] * b + carry;

carry = res / 1000;

c.push_back(res % base);

}

if (carry > 0) { // если в разряде переноса все еще остались цифры

c.push_back(carry);

}

return c;

}

int main() {

int n;

int base = 1000;

cin >> n;

vector<int> res;

res.push_back(0);

res.push_back(1);

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

res = multiply(res, i + 1, base);

}

cout << res[res.size() - 1];

for (int i = res.size() - 2; i >= 1; i--) {

cout << setw(3) << setfill('0') << res[i];

}

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

string multiplication (string x, int y) { 
    int carry = 0, temporary = 0;
    string answer = "";
    for (int i = x.size() - 1; i >= 0; i--) {
    temporary = int(x[i] - '0') * y + carry;
    carry = temporary / 10;
    answer = char(temporary % 10 + '0') + answer;
}
while (carry) {
    answer = char(carry % 10 + '0') + answer;
    carry /= 10;
}
return answer;
}
int main() {
    int n;
    string s = "1";
    cin >> n;
    for (int i = 2; i <= n; i++) {
         s = multiplication(s, i);
    } 
    cout << s << endl;
}

#include <iostream>

#include <string>

using namespace std;

string multiplication (string x, int y) {

int carry = 0, temporary = 0;

string answer = "";

for (int i = x.size() - 1; i >= 0; i--) {

temporary = int(x[i] - '0') * y + carry;

carry = temporary / 10;

answer = char(temporary % 10 + '0') + answer;

}

while (carry) {

answer = char(carry % 10 + '0') + answer;

carry /= 10;

}

return answer;

}

int main() {

int n;

string s = "1";

cin >> n;

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

s = multiplication(s, i);

}

cout << s << endl;

}

Алгоритм решения

Алгоритм решения данной задачи заключается в том, что нужно вычислить [latex]n! = 1\times 2\times 3\times \cdots\times n [/latex] , используя длинную арифметику ( умножение длинного числа на короткое ).
Иллюстрация для восьми ладей:

В коде № 1 разбиваем вектор на ячейки по три цифры. Но, некоторые ячейки могут иметь менее чем три цифры. С учетом того, что перенос может состоять не из трех цифр, следует выводить результат так: cout << setw(3) << setfill('0') << res[i];.
В коде № 2 разбиваем строку посимвольно.

Детали реализации

Безусловно, для использования векторов и строк нам понадобятся соответствующие библиотеки: #include <vector> и #include <string>.
Для вывода данных в коде № 1 стоит подключить библиотеку #include <iomanip>.

Ссылки :
Задача на e-olymp
Код № 1 на ideone
Код № 2 на ideone
Засчитанное решение № 1
Засчитанное решение № 2