Category Archives: 1. Линейные вычисления

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

Линейные вычисления

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

Это первая практическая тема при изучении программирования. Предварительно следует проработать как минимум главу 2 и 4 учебника С.Липпмана. Обратите внимание, что умница-переводчик и операции и операторы называет одинаково операторами. Т.е. каждый раз встречая в главе 4 слово «оператор» выполняйте замену на «операция». Или сразу читайте английский вариант, где operator = операция, а statement = оператор. … Continue reading →

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

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

Площадь прямоугольника — самая простая тренировочная задача.
A xor B — более простая чем предыдущая.
Спортсмен
Простая задача?
Спички
Скидки — используйте функции min() и max() из cmath
Бабочка-санитар
Анфиса и цветы
Новое блюдо Анфисе — 2
Номер квартиры
Квадрат и точки
Зоопарк
Белые кубики
Произведение цифр
Три грибника
Кольцо
Разложение трицифрового числа
Пирожки
Сколько до Нового Года?
Километровые столбы (Mileposts)
Нечетные разряды
Гринвіцький годинник
Крейсерская скорость
Стартовая скорость
Часы
Сломанные часы
Поездка на экскурсию

При решении задач этого раздела запрещается использовать какие-либо другие средства вроде ветвлений, циклов, тернарных операций и другие материалы последующих разделов курса. В этом запрете смысл головоломки некоторых задач. Попробуйте приложить все усилия, чтобы решить в этом стиле следующие задачи: 1, 8, 10, 51, 57, 63, 67, 126, 133, 146, 157, 248, 421, 472, 478, 519, 542, 906, 920, 924, 926, 932, 935, 939, 945, 949, 990, 1474, 1610, 2059, 2071, 2262, 2364, 2860, 3604, 3609, 4716, 4717, 5175, 5868, 6275, 7336, 7337, 7366, 7367, 7369, 7401, 7460, 7612, 7943, 7944. Возможно с какой-то из задач я ошибся и построить формулу её решения не получится. Но особенно на это рассчитывать не приходится — почти все задачи я перепроверил.

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

OCPC2021. Задача A. Колёса деда Панаса (код решения)

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

Условие

Дед Панас, постоялец палаты номер 17 заведения «Покосившийся Скворечник», срочно должен был принять свои таблетки умиротворения. К сожалению, нянечка рассыпала их по столу и теперь дед Панас твёрдо уверен, что он – Генри Форд, а на столе лежат колёса, из которых нужно собирать автомобили и мотоциклы. Сосед деда Панаса, дед Архип, также не дождавшийся своих таблеток, убеждён, что он – Блез Паскаль, и, заметив, что колёс на столе четное количество, донимает нянечку вопросом: «Сколькими способами можно распределить эти колёса между автомобилями и мотоциклами так, чтобы не оставалось лишних?» Поскольку дед Архип не уймётся, пока не получит ответа, и будет мешать нянечке собирать таблетки со стола, на помощь позвали вас и просят подсказать ей правильный ответ.

На ввод поступает единственное целое четное число $n$ $(2 \leqslant n \leqslant 10^9)$ – количество таблеток на столе.

Выведите одно число – количество способов распределить колёса между автомобилями и мотоциклами. Помните, что для автомобиля нужно $4$ колеса, для мотоцикла – $2$. Два способа считаются различными, если в одном из них количество автомобилей не совпадает с количеством автомобилей в другом; то же самое справедливо и для мотоциклов.

Тесты

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

6	2
2	1
12	4
1000000000	250000001

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

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    cout << ((n / 4) + 1);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

cout << ((n / 4) + 1);

return 0;

}

Решение

Некоторое количество колёс уходит на автомобили, а все остальные — на мотоциклы. Тогда заметим, что каждому способу разделить колёса между автомобилями и мотоциклами соответствует количество автомобилей, которые используются в этом разделении. Всего мы можем взять от $0$ до $\frac{n}{4}$ автомобилей включительно (целочисленное деление).

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

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

Related Images:

OCPC2021 A: Колёса деда Панаса

13/11/2021 by Мазурок Игорь Евгеньевич

Вы можете зарегистрироваться и решать эту задачу здесь.

Ограничение времени:	`500 мс`
Ограничение реального времени:	`5 с`
Ограничение памяти:	`256M`

Колёса деда Панаса

На ввод поступает единственное целое четное число n (2 ≤ n ≤ 10⁹) – количество таблеток на столе.

Выведите одно число – количество способов распределить колёса между автомобилями и мотоциклами. Помните, что для автомобиля нужно 4 колеса, для мотоцикла – 2. Два способа считаются различными, если в одном из них количество автомобилей не совпадает с количеством автомобилей в другом; то же самое справедливо и для мотоциклов.

Примеры

Входные данные	Результат работы
6	2

Видеоразбор решения здесь.

Related Images:

e-olymp 7232. Комплектация компьютеров

21/12/2020 by Куліш Марія

Задача

В наличии есть такие системные блоки: $a_1$ поддерживают только VGA интерфейс, $a_2$ поддерживают только DVI и $a_3$ поддерживают оба интерфейса VGA и DVI. Аналогично по мониторам: $b_1$ поддерживают только VGA, $b_2$ — только DVI, $b_3$ — оба интерфейса.

Какое наибольшее количество компьютерных комплектов возможно собрать, если в каждом комплекте у системного блока с монитором должен быть совместимый графический интерфейс?

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

В первой строке три числа $a_1, a_2$ и $a_3$ и во второй строке три числа $b_1,b_2$ и $b_3$ — целые неотрицательные.

Причем $ 0 \leqslant a_1, a_2, a_3, b_1, b_2, b_3 \leqslant 100$ и $a_1+a_2+a_3$ $=$ $b_1+b_2+b_3$.

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

Ответ к задаче.

Тесты

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

Код

#include <iostream>

using namespace std;


int complect(int & b, int & a) {
  int com = min(a, b);
  a -= com;
  b -= com;
  return com;
}
int main() {
  int a1, a2, a3, b1, b2, b3, c;//c-все возможные комплекты
  cin >> a1 >> a2 >> a3 >> b1 >> b2 >> b3;
  c = 0;
  c += complect(a1, b1);
  c += complect(a2, b2);
  c += complect(a1, b3);
  c += complect(a2, b3);
  c += complect(a3, b3);
  c += complect(b1, a3);
  c += complect(b2, a3);

  cout << c;
  return 0;
}

#include <iostream>

using namespace std;

int complect(int & b, int & a) {

int com = min(a, b);

a -= com;

b -= com;

return com;

}

int main() {

int a1, a2, a3, b1, b2, b3, c;//c-все возможные комплекты

cin >> a1 >> a2 >> a3 >> b1 >> b2 >> b3;

c = 0;

c += complect(a1, b1);

c += complect(a2, b2);

c += complect(a1, b3);

c += complect(a2, b3);

c += complect(a3, b3);

c += complect(b1, a3);

c += complect(b2, a3);

cout << c;

return 0;

}

Решение

Составим все комбинации системных блоков с мониторами, у которых есть совместимый графический интерфейс. Порядок составления комплектов важен. Сначала посчитаем сколько можно составить комплектов $а_1$ с $b_1$ и $a_2$ с $b_2$, так как они поддерживают только один тип интерфейса. Далее посчитаем возможные комплекты $а_1$ с $b_3$, $a_2$ с $b_3$ и $a_3$ с $b_3$ $a_3$ с $b_1$ и $a_3$ с $b_2$ из оставшегося оборудования. Выведем общее количество компьютерных комплектов.

Ссылки

Код в 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 8538. Калькулятор

07/08/2020 by Александр Розин

Условие

Калькулятор Ильи выполняет два действия: умножает текущее число на три и прибавляет к нему единицу. На калькуляторе сейчас число $1$. Помогите Илье определить наименьшее количество действий, после которой он получит число $n$.

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

Одно число $n$ $\left(10\leq n\leq 10^9\right)$.

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

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

Тесты

№	Входные данные	Выходные данные
1	1447	16
2	18	3
3	111	6

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

#include <iostream>
using namespace std;
 
int main() {
    long long n;
    int k = 0;
    cin >> n;
    while (n > 0) {
        k += n%3 + 1;
        n /= 3;
    } 
    cout << k - 2;
}

#include <iostream>

using namespace std;

int main() {

long long n;

int k = 0;

cin >> n;

while (n > 0) {

k += n%3 + 1;

n /= 3;

}

cout << k - 2;

}

Решение

Решим данную задачу от обратного. Пусть нам дано число $n$ и нам надо из него получить $1$, задействовав как можно меньше операций. Для этого объявим цикл while(), который будет работать до тех пор, пока наше число $n$ будет строго больше $0$. Внутри цикла опишем следующее решение: пусть k будет счётчиком нажатий на кнопки калькулятора и изначально равняется $0$. Тогда, при каждом шаге цикла мы к счётчику будем прибавлять остаток от деления на $3$. n%3 — именно столько раз нам потребуется отнять $1$ от $n$ чтобы можно было нацело разделить на $3$. Далее, делим $n$ на $3$ и это потребует еще одного нажатия (что и происходит в строке $9$). Так как в условии цикла мы написали, что $n > 0$, то мы пройдём лишнюю итерацию и к счётчику прибавятся два лишних шага. Поэтому, при выводе ответа, от $k$ отнимаем $2$.

Related Images:

e-olymp 8659. Байтик та шахи

11/06/2020 by Паша Мацалышенко

Задача

Вкотре запізнившись на урок, Байтик, проходячи повз ігрову кімнату, помітив шахову дошку. Порахував усі клітинки на ній, і йому стало цікаво: скільки різних квадратів зі стороною $k(1 \leqslant k \leqslant n)$ можна розмістити на дошці розміру $n$.

Вхідні дані

Натуральне число $n$ $( n\leqslant 10000)$ розмір шахової дошки.

Вихідні дані

Єдине число – кількість різних квадратів, які можна розмістити на шаховій дошці.

Тести

№	Входные данные	Выходные данные
1	3	14
2	10	385
3	99	328350
4	999	332833500
5	10000	333383335000

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

#include <iostream>
using namespace std;

int main() {
    long int n;
    cin >> n;
    long int result;
    result = n*(n + 1)*(2*n + 1)/6;
    cout << result;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long int n;

cin >> n;

long int result;

result = n*(n + 1)*(2*n + 1)/6;

cout << result;

return 0;

}

Рішення

Вирішити цю задачу можна за допомогою квадратного пірамідального числа — числа, яке висловлює кількість квадратів з різними сторонами в сітці $n$*$n$. Загальна формула для пірамідального числа порядку $n$: $\sum\limits_{k = 1}^{n} k^{2} = \frac{n(n+1)(2n+1)}{6}$. Використаємо виведену формулу для лінійного обчислення, щоб не використовувати цикли і зменшити час роботи програми.

Посилання

Related Images:

e-olymp-8841. Цифра 2

03/05/2020 by Евгений Фищук

На входе программы имеется натуральное число $n$ ($n \gt 9$). Нужно вывести предпоследнюю справа цифру (разряд десятков) числа $n$.

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

Натуральное число $n$ ($n \gt 9$).

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

Цифра разряда десятков числа $n$.

Тесты

№	Входные данные	Выходные данные
1	27	2
2	102	0
3	1234	3
4	34867	6

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int result = (n / 10) % 10;
    cout << result;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int result = (n / 10) % 10;

cout << result;

return 0;

}

Решение

Чтобы получить разряд десятков введенного числа надо поделить число на $10$ и взять остаток от деления на $10$.

Ссылки

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

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

Related Images:

e-olymp 8851. Число навпаки

15/02/2020 by Нина Хоробрых

Умова задачі

Записати чотиризначне натуральне число в зворотному порядку.

Вхідні дані

Задане чотиризначне натуральне число.

Вихідні дані

Відповідь до задачі.

Тести

№	Входные данные	Выходные данные
1	1234	4321
2	1984	4891

Розвязок №1

#include <iostream>
using namespace std;

int main() {
    int num, a, b, c, d;
    cin >> num;
    a = num % 10;
    b = num / 10 % 10;
    c = num / 100 % 10;
    d = num / 1000;
    cout << a << b << c << d;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int num, a, b, c, d;

cin >> num;

a = num % 10;

b = num / 10 % 10;

c = num / 100 % 10;

d = num / 1000;

cout << a << b << c << d;

return 0;

}

Для отримання потрібного числа, відділимо кожну цифру та привласнемо до неї змінну. Виводимо у потрібному порядку.

Розвязок №2

#include <iostream>
using namespace std;
 
int main() {
    string num;
    cin >> num;
    for (int i = 3; i >= 0; i-- )  {
        cout << num[i];
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string num;

cin >> num;

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

cout << num[i];

}

return 0;

}

Представимо вводиме число як строку. Виводимо у циклі від третього до останньго елемента.

Посилання

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

Related Images:

e-olymp 398. Торт для Серёжи

30/01/2020 by Дмитрий Воротов

Задача

Мама испекла Серёже на день рождения большой и вкусный круглый торт и поручила ему самому его разрезать. У него в распоряжении есть достаточно длинный нож, позволяющий делать разрез по всему торту, однако так как общение с режущими инструментами всегда таит в себе определенные опасности, Серёжа хочет сделать минимальное количество разрезов так, чтобы всем гостям досталось хотя бы по одному кусочку. Естественно, при этом он должен не забыть, что и ему должен за праздничным столом достаться хотя бы один кусочек маминого торта, но при этом Серёжу абсолютно не интересует, какого размера и формы будут куски торта – для него главное, чтобы они все имели такую же толщину, как и испеченный мамой торт.

Учтите, что гостей к Серёже может придти достаточно много.

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

Одно число – количество гостей $n$ $(n < 210000001)$.

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

Искомое количество разрезов $k$.

Тесты

№	Входные данные	Выходные данные
1	3	2
2	0	0
3	120	15
4	210000000	20494

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    cout << round(sqrt(2 * n));
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n;

cin >> n;

cout << round(sqrt(2 * n));

return 0;

}

Решение

Максимального количества кусков можно достичь в том случае, когда каждый новый разрез будет пересекать все предыдущие. Таким образом новым $k$-ым сечением мы разрежем $k$ кусков торта на две части, а к общему количеству кусочков прибавится ровно $k$ новых. Заметим, что имениннику всегда достанется кусок, который не считается новым. Множество всех новых кусков составит арифметическую прогрессию: $0,1, 2, 3 … k-1, k$ значит общее количество кусочков для гостей вычисляется как сумма арифметической прогрессии $\mathbf{n = \frac{i^{2}+k}{2}}$. Тогда $\mathbf{k =\left \lceil \frac{-1+\sqrt{1+8n}}{2} \right \rceil }$.

Эту формулу немного можно упростить, в результате получим $\mathbf{k =\left [ \sqrt{2n}\right ]}$

Ссылки

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

Код решения ideone

Related Images:

e-olymp 123. Количество нулей у факториала

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

Задача

Найти количество нулей в конце записи факториала числа $n$.

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

Одно число $n$ $(1 \leqslant n \leqslant2\cdot10^9)$

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

Количество нулей в конце записи $n!$

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1	0
2	7	1
3	12	2
4	100	24
5	306	75
6	5000	1249

Код

#include <iostream> 
using namespace std;
int main() { 
    long long n, m = 5, s = 0; 
    cin >> n; 
    while(n >= m){
        s = s + (n / m); 
        m = m * 5;
    }
    cout << s;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long n, m = 5, s = 0;

cin >> n;

while(n >= m){

s = s + (n / m);

m = m * 5;

}

cout << s;

return 0;

}

Решение

Каждый нуль в конце искомого числа возникает от произведения чисел 2 и 5 — других вариантов нет. Очевидно, множителей 5 будет меньше множителей 2. Значит, количество нулей определяется исключительно количеством множителей-пятерок. Один такой множитель содержат числа 5, 10, 15, 20, 25, …, $n$ — всего их насчитывается $\frac{n}{5}$. Два множителя содержат числа 25, 50, …, $n$ всего их $\frac{n}{5^2}$.Три множителя содержат $\frac{n}{5^3}$.Складывая количество множителей с учетом их повторения, найдем общее их количество:

$\lfloor\frac{n}{5}\rfloor+\lfloor\frac{n}{5^2}\rfloor+\lfloor\frac{n}{5^3}\rfloor+\ldots+\lfloor\frac{n}{5^k}\rfloor$

Суммирование происходит до тех пор, пока очередное слагаемое не станет равным 0.

Ссылки

Формула разложения на простые множители

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

Код на Ideone

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

Related Images:

e-olymp 7934. Коробка для свічок

21/12/2019 by Іра Лотоцька

Умова задачі

Маргарита любить свої дні народження. Вона дійсно щаслива, коли задуває свічки під мелодію «Happy Birthday». Кожного року, починаючи з досягнення нею чотирьохрічного віку, вона складає свої свічки з дня народження (по одній за кожен рік віку) в коробку для свічок. Її молодший брат Тео почав робити те ж саме у віці трьох років. Коробки Маргарити і Тео та свічки в них виглядають однаково.

Одного разу Маргарита вирішила порахувати, скільки свічок в неї у коробці:

Ні, ні, ні! Я молодша цього!

Вона щойно зрозуміла, що Тео кинув в її коробку декілька свічок з його днів народжень. Чи можете ви допомогти Маргариті виправити кількість свічок в її коробці?

Маючи різницю у віці між Маргаритою і Тео, кількість свічок в коробці Маргарити та число свічок в коробці Тео, визначте, скільки свічок Маргариті потрібно вийняти з її коробки, щоб в ній була потрібна кількість.

Вхідні дані

Перший рядок — число [latex] d (1 ⩽ d ⩽ 20) [/latex] — різниця у віці між Маргаритою і Тео.

Другий рядок — число [latex]m (4 ⩽ m < 1000)[/latex] — кількість свічок в коробці Маргарити.

Третій рядок — число [latex]t (0 ⩽ t < 1000)[/latex] — кількість свічок в коробці Тео.

Вихідні дані

Виведіть число свічок, яке Маргариті потрібно вийняти з її коробки, щоб в ній була правильна кількість.

Тести

№	ВХІДНІ ДАНІ	ВИХІДНІ ДАНІ
1	2 26 8	4
2	4 48 3	9
3	7 110 14	11
4	10 568 78	139
5	13 800 37	211

Код програми

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

int main() {
    int d, m, t;
    int x, discriminator, sum, superfluous;
    cin >> d >> m >> t;
    sum = m + t; //рахуємо кількість свічок у двох коробках
    pow (x, 2) + (1 - d) * x + (pow (d, 2) - d - 18 - 2 * sum) / 2;
    discriminator = pow (1 - d, 2) - 2 * (pow (d, 2) - d - 18 - 2 * sum);
    x = ( (d - 1) + sqrt (discriminator) ) / 2; //вік Маргарити в момент перевірки вмісту коробки
    superfluous = m - ( (4 + x) * (x - 3) ) / 2; //зайва кількість свічок в коробці Маргарити
    cout << superfluous; //виводимо відповідь
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int d, m, t;

int x, discriminator, sum, superfluous;

cin >> d >> m >> t;

sum = m + t; //рахуємо кількість свічок у двох коробках

pow (x, 2) + (1 - d) * x + (pow (d, 2) - d - 18 - 2 * sum) / 2;

discriminator = pow (1 - d, 2) - 2 * (pow (d, 2) - d - 18 - 2 * sum);

x = ( (d - 1) + sqrt (discriminator) ) / 2; //вік Маргарити в момент перевірки вмісту коробки

superfluous = m - ( (4 + x) * (x - 3) ) / 2; //зайва кількість свічок в коробці Маргарити

cout << superfluous; //виводимо відповідь

return 0;

}

Розв’язання

Нехай [latex] x [/latex] — кількість років Маргарити в момент перевірки вмісту коробки зі свічками, тоді [latex] x — d [/latex] — вік Тео в цей момент. Правильна кількість свічок в коробці Маргарити — [latex] \frac{(4+x)(x-3)}{2} [/latex] та коробці Тео [latex] \frac{(3+x-d)(x-d-2)}{2} [/latex] (як суми членів арифметичної прогресії). Правильна кількість свічок в обох коробках дорівнюватиме сумі свічок, що наявна в коробці Маргарити і Тео, відповідно [latex] m + t [/latex]. Складемо рівняння, яке після ряду перетворень набуде квадратного виду [latex] ax^2+bx+c=0 [/latex] — [latex]x^2 + (1 — d) x + \frac{d^ 2 — d — 18 — 2 (m + t)}{2} = 0[/latex]. Знайдемо дискримінант [latex] b^2-4ac [/latex], а потім корінь рівняння за формулою [latex] \frac{-b+\sqrt{D}}{2a}[/latex], тому [latex]x = \frac{(d-1) + \sqrt{D}}{2}[/latex], причому [latex]\frac{-b — \sqrt{D}}{2a} [/latex] — не є потрібним розв’язком, адже набуватиме від’ємного значення. Тепер віднімемо від свічок, які Маргарита знайшла в коробці їx правильну кількість. Отже, зайвими будуть [latex]m — \frac{(4+x)(x — 3)}{2}[/latex] свічок.

Посилання

Задача на сайті e-olymp

Код розв’язання на ideone

Зараховаваний роз’язок

Related Images:

e-olymp 8638. Дописать тройку

19/12/2019 by Андрей Мартынюк

Задача

Дано трёхзначное число $ n $. Дописать к нему слева и справа цифру $ 3 $.

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

Одно трехзначное число $ n $ .

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

Дописать к числу $ n $ слева и справа цифру $ 3 $. Вывести полученное число.

Тесты

№	Входные данные	Выходные данные
1.	333	33333
2.	261	32613
3.	123	31233
4.	060	30603

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

Первый вариант

#include <iostream>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    n = (n * 10) + 30003;
    cout << n;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

n = (n * 10) + 30003;

cout << n;

return 0;

}

Второй вариант

#include <iostream>
using namespace std;
 
int main() {
    int n, t;
    cin >> n;
    t = 3;
    cout << t << n << t << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, t;

cin >> n;

t = 3;

cout << t << n << t << endl;

return 0;

}

Объяснение

Дано любое трёхзначное число. Нужно дописать $ 3 $ к нему слева и справа.

К первому варианту кода

Умножаем число на $ 10 $ и прибавляем $ 30003 $.

Ко второму варианту кода

Просто дописываем $ 3 $ слева и справа сразу в выводе.

Ссылки

Задача на e-olymp
Ideone (первый вариант кода)
Ideone (второй вариант кода)

Related Images:

e-olymp 8841. Цифра 2

15/12/2019 by Богдан Диденко

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

На входе программы имеется натуральное число [latex]n (n > 9)[/latex]. Нужно вывести предпоследнюю справа цифру (разряд десятков) числа [latex]n[/latex].

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

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

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

Цифра разряда десятков числа [latex] n [/latex].

Тесты:

№	Входные данные	Выходные данные
1	10	1
2	197	9
3	4638	3
4	72410	1
5	6543732	3

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

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    cout << (n / 10) % 10;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

cout << (n / 10) % 10;

return 0;

}

Решение:

Идея данного решения заключается в том, чтобы с помощью целочисленного деления числа [latex]n (n > 9)[/latex] на 10 избавиться от последней цифры в числе [latex]n[/latex]. Затем вычисляем остаток от деления для того, чтобы осталась последняя цифра полученного числа, которая и является предпоследней цифрой справа (разряд десятков) в числе [latex]n[/latex].

Ссылки:

Задача на e-olymp

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

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

Related Images:

e-olymp 9406. Професор і батарейки

10/12/2019 by Іра Лотоцька

Умова задачі

У професора на столі лежали упаковки батарейок. У кожній по [latex] a [/latex] штук. Коли професор взяв по [latex] b [/latex] батарейок з кожної упаковки — на столі залишилося всього [latex] c [/latex] батарейок.

Скільки упаковок з батарейками було на столі?

Вхідні дані

Три натуральні числа [latex] a [/latex], [latex] b [/latex], [latex] c [/latex].

Вихідні дані

Вивести кількість упаковок з батарейками, які лежали на столі.

Тести

№	ВХІДНІ ДАНІ	ВИХІДНІ ДАНІ
1	6 3 15	5
2	12 10 6	3
3	150 130 220	11
4	60 56 512	128
5	702 67 3175	5

Код програми

#include <iostream>
using namespace std;
 
int main() {
    int a, b, c, n;
    cin >> a >> b >> c;
    n = c / ( a - b ); //рахуємо кількість упаковок з батарейками 
    cout << n; //виводимо відповідь
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, c, n;

cin >> a >> b >> c;

n = c / ( a - b ); //рахуємо кількість упаковок з батарейками

cout << n; //виводимо відповідь

return 0;

}

Розв’язання

Нехай [latex] n [/latex] — кількість упаковок батарейок. [latex] a-b [/latex] — це кількість батарейок, яка залишилась в кожній упаковці. Відомо, що всього залишилось [latex] c [/latex] батарейок, тоді [latex] n = \frac{c}{a-b} [/latex] — кількість упаковок батарейок.

Посилання

Задача на сайті e-olymp

Код розв’язання на ideone

Зараховаваний роз’язок

Related Images:

e-olymp 9405. Профессор и шары

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

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

Для праздника Профессор купил голубые, красные и жёлтые воздушные шары. Всего $n$ штук. Жёлтых и голубых вместе — $a$. Красных и голубых — $b$ штук.

Сколько голубых, красных и жёлтых шаров купил Профессор?

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

Три натуральных числа $n$, $a$, $b$.

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

В одной строке выведите количество голубых, красных и жёлтых шаров, которые купил Профессор.

Тесты

№	Входные данные	Выходные данные
1	10 6 8	4 4 2
2	12 8 10	6 4 2
3	14 10 12	8 4 2
4	16 14 12	10 2 4

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

#include <iostream>
using namespace std;

int main()
{
    int n, a, b, blue, yellow, red; 
    cin >> n >> a >> b; 
    blue = b + a - n; //считаем кол-во синих шаров
    red = b - blue; //считаем кол-во красных шаров
    yellow = a - blue; //считаем кол-во жёлтых шаров
    cout << blue <<" "<< red <<" "<< yellow; 
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n, a, b, blue, yellow, red;

cin >> n >> a >> b;

blue = b + a - n; //считаем кол-во синих шаров

red = b - blue; //считаем кол-во красных шаров

yellow = a - blue; //считаем кол-во жёлтых шаров

cout << blue <<" "<< red <<" "<< yellow;

return 0;

}

Решение

Для решения задачи необходимо вывести формулу для вычисления количества жёлтых ($y$), синих ($u$) и красных ($r$) шаров. Из условия имеем, что:

$$\left.\begin{matrix}
&u&+&y&=a&\\
&r&+&u&=b&\\
&r&+&u&+&y&=n&
\end{matrix}\right\}$$

Выразим $r$ и $y$ через $u$:

$$\left.\begin{matrix}
r=&b&-&u&\\
y=&a&-&u&
\end{matrix}\right\}$$

Подставим эти значения в формулу $r+u+y=n$:

$n=b-u+u+a-u$

$u$ и $-u$ взаимоуничтожатся и мы получим, что:

$n=a+b-u$

Теперь выведем формулу для вычисления количества синих шаров:

$u=b+a-n$

Ссылки

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

Related Images:

e-olymp 8842. Цифра 3

05/12/2019 by Катя Романцова

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

На входе программы имеется натуральное число [latex] n (n > 99) [/latex]. Нужно вывести третью цифру (разряд сотен) числа [latex] n [/latex].

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

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

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

Цифра разряда сотен числа [latex] n [/latex].

Тесты:

№	Ввод	Вывод
1	512	5
2	7826	8
3	90285	2
4	12479056	0
5	18942793357	3

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

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    cout >> (n / 100) % 10;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long n;

cin >> n;

cout >> (n / 100) % 10;

return 0;

}

Решение:

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

разделим данное натуральное число на [latex] 100 [/latex] и получаем количество сотен в числе: либо однозначное число (цифру), либо многозначное;
так как мы хотим получить простую сотню (однозначное число), мы находим остаток от полученного числа при делении на [latex] 10 [/latex].

Ссылки:

Задача на E-Olymp

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

Засчитанное решение на E-Olymp

Related Images:

e-olymp 9080. Три богатыря

04/12/2019 by Паша Мацалышенко

Задача

Три богатыря шли из Бразилии в Киевскую Русь. Шли они со скоростью [latex]n[/latex] метров в минуту и должны пройти расстояние [latex]r[/latex] километров. Сколько дней им понадобится для преодоления пути?

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

Два натуральных числа [latex]n[/latex] и [latex]r[/latex] [latex]\left(n, r \leqslant10^{4}\right)[/latex]

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

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

Тесты

№	Входные данные	Выходные данные
1	1 10	7
2	2 8	3
3	4 70	13
4	5 68	10
5	3 12	3

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

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

int main() {
    int n, r;
    cin >> n >> r;
    cout << ceil(r / n * 1.44);
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n, r;

cin >> n >> r;

cout << ceil(r / n * 1.44);

return 0;

}

Решение

Ответом к задаче будет количество дней, за которое богатыри проделают путь. То есть нам просто надо поделить путь на скорость. Но загвоздка задачи состоит в том, что скорость дана в метрах в минуту, а нам надо перевести в километры в сутки. В одних сутках [latex]1440[/latex] минут, в километре [latex]1000[/latex] метров. Выполнив математические преобразования, получаем, что надо заданное значение скорости умножить на [latex]1.44[/latex]. Выводим результат деления пути на скорость, умноженную на [latex]1.44[/latex]. Так как получится нецелый результат, округляем значение в сторону большего с помощью функции ceil() , предварительно подключив библиотеку cmath .

Ссылки

Related Images:

e-olymp 8254. Номера отеля

02/12/2019 by Таня Осипенко

Задача

Отель имеет $n$ этажей. Лобби, ресторан и тренажерный зал расположены на первом этаже. Номера находятся со 2-го по $n$-ый этажи. На каждом этаже расположено $m$ стандартных номеров. Если каждый стандартный номер вмещает 3 гостя, какое наибольшее количество гостей может поместиться во всех стандартных номерах отеля?

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

Два натуральных числа $n$ и $m$ ($n, m\leqslant10^6$).

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

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

Тесты

№	Входные данные	Выходные данные
1	5 10	120
2	3 1	6
3	2 5	15
4	7 2	36
5	20001 450000	270000000000

Код

#include <iostream>
using namespace std;

int main() {
    long n, m; // Объявляем переменные (кол-во этажей и номеров на каждом из них)
    cin >> n >> m; // считываем входные данные
    cout << (n - 1) * m * 3; // выводим ответ
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long n, m; // Объявляем переменные (кол-во этажей и номеров на каждом из них)

cin >> n >> m; // считываем входные данные

cout << (n - 1) * m * 3; // выводим ответ

return 0;

}

Решение

Для решения данной задачи выводим формулу $(n-1) \cdot m \cdot 3$, первый из сомножителей — количество этажей, на которых располагаются номера, второй — количество номеров на каждом из указанных этажей, третий — максимальное количество гостей в каждом номере. Заметим, что по условию на первом этаже номера отсутствуют, поэтому первый сомножитель в формуле будет на единицу меньше, чем количество этажей в отеле.

Ссылки

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

Related Images:

e-olymp 9518. Точное движение

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

Задача

Амелия изучает моделирование. Она увлекается моделями с подвижными деталями.

В качестве своего первого задания она сделала прямоугольную коробку размером $2$ $×$ $n$, которая содержит две параллельные рейки и прямоугольный брусок на каждой из них. Короткий брусок имеет размер $1$ $×$ $a$, а длинный имеет размер $1$ $×$ $b$. Длинный брусок имеет стопор на каждом конце, а короткий всегда находится между этими двумя стопорами.

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

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

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

Три целых числа $a$, $b$ и $n$ $($$1$ $\leqslant$ $a$ $<$ $b$ $\leqslant$ $n$ $\leqslant$ $10$^$7$$)$.

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

Вывести одно целое число — минимальное количество ходов, которое должна сделать Амелия.

Тесты

№	Входные данные	Выходные данные
1	1 3 6	5
2	2 4 9	7
3	13 45 153	9
4	4 16 43	7

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

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

int main()
{
    int a, b, n, k;
    cin >> a >> b >> n;
    k = ceil((double)(n - b) / (b - a));
    cout << (2 * k + 1);
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

int a, b, n, k;

cin >> a >> b >> n;

k = ceil((double)(n - b) / (b - a));

cout << (2 * k + 1);

return 0;

}

Решение

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

Длинный брусок, что бы он оказался в конце коробки, суммарно нужно переместить на $n$$-$$b$. Каждый раз мы перемещаем его на $b$$-$$a$ (необходимое расстояние что бы левые концы брусков совпали и дальше перемещать его было невозможно). Тогда количество перемещений длинного бруска это результат деления всего расстояния $n$$-$$b$ на шаг $b$$-$$a$. Так как в результате может выйти нецелое число, результат необходимо округлить до большего целого. Обозначим это число как $k$ $=$$\lceil $$\frac{n-b}{b-a}$$\rceil$.

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

Тогда суммарное количество ходов будет $2$$k$$+$$1$.

Ссылки

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

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

Related Images:

e-olymp 8649. Емблема (Emblem)

20/06/2019 by Blyshchyk

Умова

До проведення $N$-ї ярмарки «Мікротехнології у макропрограмуванні» дизайнери розробили емблему, у якій на квадрат розміром $N \times N$ дм «ставився зверху» квадрат розміром $\left(N-1\right) \times \left(N-1\right)$ дм і так далі. Зверху був квадрат $1 \times 1.$ В цілому організаторам емблема сподобалася, але вони забажали «прикрасити» її золотистою стрічкою, яка йшла б від лівого нижнього кута до правого верхнього, потім по верхньому краю і спускалася до правого нижнього кута (див. малюнок). У найближчому магазині можна було купити стрічку за ціною $Р$ грн. за дм, але відпускалися стрічки тільки з цілою кількістю дм. У той же час магазин пропонував знижку $10\%$, якщо покупка коштувала не менше $100$ грн. і $15\%$ при покупці від $1000$ грн. Скільки щонайменше доведеться заплатити за цю «прикрасу»? Нагадаємо, що на декартовій площині довжина відрізку між точками $\left(x_{1};y_{1}\right)$ та $\left(x_{2};y_{2}\right)$ обчислюється за формулою: $d=\sqrt{\left(\left(x_{2}-x_{1}\right)^{2}+\left(y_{2}-y_{1}\right)^{2} \right)}.$

Вхідні дані:

Програма вводить два натуральних числа $N$ – номер ярмарки та $P$ -ціна стрічки у гривнях за дм $\left(1 \leqslant N \leqslant 100\right).$

Вихідні дані:

Ціна стрічки у копійках (щоб не працювати з дробовими числами).

Тести:

Вхідні дані	Вихідні дані
2 13	9360
5 10	28800
100 1	858670
1 5	2000
12 3	42660

Рішення:

#include 
#include 
using namespace std;

int main() {
    long long N, P;
    cin >> N >> P;
    double h, l, d, lenta, price;
    h = (1+N)*N*0.5;
    l = 0.5 + N*0.5;
    d = sqrt(h*h + l*l);
    lenta = ceil(d + d + 1);
    price = lenta * P;
    if (price >= 1000) {
        price *= 85;
    }
    else if (price >= 100) {
        price *= 90;
    }
    else {
        price *= 100;
    }
    if (ceil(100./P) > lenta and price > 90*ceil(100./P)*P){
        price = 90*ceil(100./P)*P;
    }
    else if (ceil(1000./P) > lenta and price > 85*ceil(1000./P)*P) {
        price = 85*ceil(1000./P)*P;
    }
    cout << price;
}

#include

using namespace std;

int main() {

long long N, P;

cin >> N >> P;

double h, l, d, lenta, price;

h = (1+N)*N*0.5;

l = 0.5 + N*0.5;

d = sqrt(h*h + l*l);

lenta = ceil(d + d + 1);

price = lenta * P;

if (price >= 1000) {

price *= 85;

}

else if (price >= 100) {

price *= 90;

}

else {

price *= 100;

}

if (ceil(100./P) > lenta and price > 90*ceil(100./P)*P){

price = 90*ceil(100./P)*P;

}

else if (ceil(1000./P) > lenta and price > 85*ceil(1000./P)*P) {

price = 85*ceil(1000./P)*P;

}

cout << price;

}

Пояснення: Спочатку необхідно знайти довжину діагоналі, для цього, умовно ми можемо продовжити саму верхню пряму в праву і ліву сторону до того моменту поки її довжина не стане не менш ніж $N$ дм, а потім починаючи з лівого нижнього кута куба $N \times N$ провести перпендикуляр до цієї прямої. Так у нас вийде прямокутний трикутник, в якому h (знаходимо за формулою $n$-перших членів арифметичної прогресії $S_{n} = \frac{a_{1}+a_{n}}{2} \cdot n$) та l — катети, тоді за теоремою Піфагора можемо знайти діагональ d. Далі знаходимо довжину стрічки і її ціну з огляду на знижки. Також необхідно зробити перевірку, чи буде вигідніше придбати стрічку на таку кількість грошей, яке буде відповідати умовам знижки.