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

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

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

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

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

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

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

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

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

e-olymp 1142. Деление на ноль или…

12/12/2019 by Лаура Казарян

Задача

Как известно, делить на ноль нельзя. А может еще на что-то делить нельзя? Это Вам и предстоит выяснить.

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

В единственной строке задано два целых знаковых 32-битовых числа $a$ и $b$.

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

Выведите значение частного, полученного в результате деления $a$ на $b$. Если деление произвести невозможно, вывести ERROR.

Тесты

№	Входные данные	Выходные данные
1	8 4	2
2	6 0	ERROR
3	0 4	0
4	613 18	34
5	9197 10000	0

Код

#include <iostream>
using namespace std;

int main() {
    long a, b;
    cin >> a >> b;
    if (b != 0) cout << a/b;
    else cout << "ERROR";
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long a, b;

cin >> a >> b;

if (b != 0) cout << a/b;

else cout << "ERROR";

return 0;

}

Решение

В задаче, единственной невозможной операцией является деление на ноль. Это условие можно проверить с помощью условных операторов if и else. Также, так как $a$ и $b$ являются целыми 32-битными числами, необходимо использовать тип переменных long.

Ссылки

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

Related Images:

e-olymp 7612. Алекс и квадраты оригами

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

Задача

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

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

В одной строке два целых числа [latex] h [/latex] и [latex] w [/latex] [latex] \left ( 1\leqslant h,w\leqslant 1000 \right ) [/latex] — высота и ширина куска бумаги.

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

Выведите одно действительное число — наибольшую длину стороны квадратов. Всегда можно вырезать три одинаковых квадрата из листа бумаги размером [latex] h \times w[/latex] так, чтобы их стороны были параллельны сторонам листа.
Ответ следует вывести с точностью не меньше трех десятичных знаков.

Тесты

Входные данные	Выходные данные
30 11	10.0000
8 3	2.6667
210 297	105.0000
60 59	29.5000
250 100	83.3333

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

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

int main() {
    double h, w, ans = 0;
    cin >> h >> w;
    if (w < h) {
        swap (w, h);
    }
    ans = ( w >= 3 * h ? h : max (h / 2, w / 3) );
    cout << fixed << setprecision(4) << ans;
}

#include <iostream>

#include <algorithm>

#include <cmath>

#include <iomanip>

using namespace std;

int main() {

double h, w, ans = 0;

cin >> h >> w;

if (w < h) {

swap (w, h);

}

ans = ( w >= 3 * h ? h : max (h / 2, w / 3) );

cout << fixed << setprecision(4) << ans;

}

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
 
int main() {
    double h, w, tmp = 0,  ans = 0;
    cin >> h >> w;
    if (w < h) {
        tmp = h;
        h = w;
        w = tmp;
    }
    if (w >= 3 * h) {
        ans = h;
    }
    else {
        ans = max (h / 2, w / 3);
    }
    cout << fixed << setprecision(4) << ans;
}

#include <iostream>

#include <cmath>

#include <iomanip>

using namespace std;

int main() {

double h, w, tmp = 0, ans = 0;

cin >> h >> w;

if (w < h) {

tmp = h;

h = w;

w = tmp;

}

if (w >= 3 * h) {

ans = h;

}

else {

ans = max (h / 2, w / 3);

}

cout << fixed << setprecision(4) << ans;

}

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

Допустим, что [latex] w [/latex] всегда больше чем [latex] h [/latex] . Из условия следует, что варианта расположения данных квадратов два:

В первом случае ответом будет [latex] \max\left ( \frac{h}{2}, \frac{w}{3} \right ) [/latex]. Во втором же, ответом будет [latex] h [/latex] .

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

В первом коде программы используется используется библиотека
#include <algorithm> , которая включает в себя функцию swap() , так же, используется библиотека #include <cmath> , которая включает в себя функцию max() .
Для вывода ответа с точностью не меньше трех десятичных знаков используется библиотека
#include <iomanip> и манипуляторы fixed и setprecision() .

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

Related Images:

e-olymp 8352. Такси

03/12/2019 by Виктория Крачилова

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

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

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

Три натуральных числа, не превосходящих 100 — количество пассажиров в первой, второй и третьей маршрутках соответственно.

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

Выведите одно число — наименьшее количество пассажиров, которое требуется пересадить. Если это невозможно, выведите слово IMPOSSIBLE (заглавными буквами).

Тесты

№	Ввод	Вывод
1	1 2 3	1
2	6 7 4	IMPOSSIBLE
3	18 10 2	8
4	54 10 96	IMPOSSIBLE
5	27 27 27	0

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

#include <iostream>
using namespace std;

int main() {
    int b1, b2, b3;
    cin >> b1 >> b2 >> b3;
    if ((b1 + b2 + b3) % 3 != 0) {
        cout << "IMPOSSIBLE" << endl;
    }
    else {
        int average; // среднее арифметическое
        int count = 0; // наименьшее количество пассажиров, которое требуется пересадить
        average = (b1 + b2 + b3) / 3;
        if (b1 > average) count += b1 - average;
        if (b2 > average) count += b2 - average;
        if (b3 > average) count += b3 - average;
        cout << count << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int b1, b2, b3;

cin >> b1 >> b2 >> b3;

if ((b1 + b2 + b3) % 3 != 0) {

cout << "IMPOSSIBLE" << endl;

}

else {

int average; // среднее арифметическое

int count = 0; // наименьшее количество пассажиров, которое требуется пересадить

average = (b1 + b2 + b3) / 3;

if (b1 > average) count += b1 - average;

if (b2 > average) count += b2 - average;

if (b3 > average) count += b3 - average;

cout << count << endl;

}

return 0;

}

Решение

Мы сможем рассадить пассажиров поровну в три маршрутки только тогда, когда их общее количество кратно трем. Если это условие не выполняется, выводим на экран слово IMPOSSIBLE.

Иначе вычисляем среднее арифметическое исходного количества пассажиров каждой маршрутки по формуле: $\frac{b_{1}+b_{2}+b_{3}}{3}$ и находим минимальное количество пересаживаемых пассажиров, суммируя только положительные отклонения от среднего арифметического.

Ссылки

Related Images:

e-olymp 8891. Ровно одно условие из двух

01/12/2019 by Владислав Стасюк

Задача

Для заданного целого числа $n$ вывести YES, если выполняется ровно одно из следующих условий и NO в противном случае.

число $n$ четное.
число $n$ отрицательное и кратное трем.

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

Одно целое число $n$.

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

Вывести YES или NO в зависимости от выполнения условий.

Тесты

ВВОД	ВЫВОД
22	YES
7	NO
-30	NO
-9	YES
0	YES

Код (как делать можно, но не нужно)

#include <iostream>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    if((n % 2 == 0 and (n >= 0 or n % 3 != 0)) or (n % 3 == 0 and n < 0 and n % 2 != 0)){
        cout << "YES";
    }
    else{
        cout << "NO";
    } 
    
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

if((n % 2 == 0 and (n >= 0 or n % 3 != 0)) or (n % 3 == 0 and n < 0 and n % 2 != 0)){

cout << "YES";

}

else{

cout << "NO";

}

return 0;

}

Код (как делать можно и нужно)

#include <iostream>
using namespace std;
int main() {
    int n; 
    cin >> n;
    cout << ((n%2 == 0) == (n%3 == 0 and n<0)? "NO": "YES");
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

cout << ((n%2 == 0) == (n%3 == 0 and n<0)? "NO": "YES");

}

Решение

Если оба условия выполняются или оба не выполняются, то нужно вывести «NO», а иначе — «YES».

В первом случае проверяем четность числа $n$.
Во втором случае проверяем кратность трем и является ли $n$ отрицательным.
В обеих случаях исключаем варианты, когда оба условия могли бы выполнятся, то есть исключаем отрицательные числа и кратность трем для первого, и четность числа для второго случая.

Ссылки
e-olymp
ideone

Related Images:

e-olymp 8893. Каждое условие из двух

01/12/2019 by Олег Сторожев

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

Для заданного целого числа $n$ вывести YES, если выполняется каждое из следующих условий и NO в противном случае.

Число $n$ кратное трем;
Число $n$ четное и двузначное.

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

Одно целое число $n$.

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

Вывести YES или NO в зависимости от выполнения условий.

Тесты

№	Входные данные	Выходные данные
1	12	YES
2	27	NO
3	-12	YES
4	60	YES
5	10	NO
6	00000012	YES

Код

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int n;
    cin >> n;
    if (abs(n) >= 10 && abs(n) < 100 && n % 6 == 0){
        cout << "YES";
    }
    else {
        cout << "NO";
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n;

cin >> n;

if (abs(n) >= 10 && abs(n) < 100 && n % 6 == 0){

cout << "YES";

}

else {

cout << "NO";

}

return 0;

}

Решение

У нас дана целочисленная переменная $n$. Для решения данной задачи надо проверить выполняет ли переменная все условия чтобы выводилось YES.

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

Если выполняются все условия, то выводим YES, в остальных случаях NO. Задача решена

Ссылки

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

Related Images:

e-olymp 9081. Автомобілі

30/11/2019 by Артем Рогулин

Завдання

Троє водіїв вирішили опробувати нове шосе. Перший їхав зі сталою швидкістю $v_1$ км/год. протягом $t_1$ годин. Другий їхав зі сталою швидкістю $v_2$ км/год. протягом $t_2$ годин, третій – зі сталою швидкістю $v_3$ км/год. протягом $t_3$ годин. Хто з них проїхав найдовший шлях?

Вхідні дані

В одному рядку через пропуск ввести на стандартний пристрій введення значення $v_1$, $v_2$, $v_3$, $t_1$, $t_2$, $t_3$. Інтервал значень швидкостей – від $30$ до $100$ км/год. включно. Час у дорозі – з інтервалу $[1;15]$ годин.

Вихідні дані

Якщо найдовший шлях проїхав один водій, вивести на стандартний пристрій введення номер водія. Якщо найдовший шлях проїхали два або три водія, треба ввести в одному рядку через пропуск їх номери у порядку зростання.

Тести

№	Вхідні дані	Вихідні дані
1.	38 9 54 5 62 3	1
2.	30 9 45 6 90 3	1 2 3
3.	30 15 45 5 50 9	1 3
4.	50 6 42 14 84 7	2 3

Код програми

#include <iostream>
using namespace std;
 
int main() {
    int v1, v2, v3; // Змінні, де будемо зберігати швидкості водіїв
    int t1, t2, t3; // Час, який вони їхали
    int s1, s2, s3; // І відстань
    int max_; // Також, змінну, де буде зберігатися максимальна відстань
    cin >> v1 >> t1; // Прочитуємо швидкість і час для кожного водія
    cin >> v2 >> t2; 
    cin >> v3 >> t3;
    s1 = v1 * t1; // Знаходимо відстань, яку проїхав кожен з них
    s2 = v2 * t2; 
    s3 = v3 * t3;
    max_ = max(max(s1, s2), s3); // Виявляємо максимальну відстань
    if ( s1 == max_ )  // Перевіряючи, чи є пройдена відстань максимальною
        cout << "1 "; // Виводимо номер відповідного водія
    if ( s2 == max_ )
        cout << "2 ";
    if ( s3 == max_ )
        cout << 3;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int v1, v2, v3; // Змінні, де будемо зберігати швидкості водіїв

int t1, t2, t3; // Час, який вони їхали

int s1, s2, s3; // І відстань

int max_; // Також, змінну, де буде зберігатися максимальна відстань

cin >> v1 >> t1; // Прочитуємо швидкість і час для кожного водія

cin >> v2 >> t2;

cin >> v3 >> t3;

s1 = v1 * t1; // Знаходимо відстань, яку проїхав кожен з них

s2 = v2 * t2;

s3 = v3 * t3;

max_ = max(max(s1, s2), s3); // Виявляємо максимальну відстань

if ( s1 == max_ ) // Перевіряючи, чи є пройдена відстань максимальною

cout << "1 "; // Виводимо номер відповідного водія

if ( s2 == max_ )

cout << "2 ";

if ( s3 == max_ )

cout << 3;

return 0;

}

Пояснення

Відповіддю до задачі є номери водіїв, що проїхали максимальну відстань. Для цього треба використати формулу, знайому всім ще зі школи: $S = Vt$. Після знаходження відстані пройденої кожним водієм, ми знаходимо максимальну серед них. Далі нам залишається тільки виводити у порядку зростання номери водіїв, які пройшли максимальну відстань.

Примітка: Швидкість і час вводяться попарно для кожного водія.

Посилання

Related Images:

e-olymp 845. Открытка и конверт

25/06/2019 by Максим Евчук

Задача

Даны размеры прямоугольных открытки и конверта. Требуется определить, поместится ли открытка в конверт.

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

В первой строке находятся размеры открытки, во второй — размеры конверта. Размеры открытки и конверта — целые положительные числа, не превосходящие $100.$

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

Если открытку можно вложить в конверт, вывести $Possible,$ если нет — вывести $Impossible$.

Тесты

№	Входные данные	Выходные данные
1	1 10 9 9	Possible
2	20 40 2 4	Possible
3	50 20 40 40	Impossible
4	10 4 5 5	Impossible

#include <cmath>

#include <iostream>

using namespace std;

int main() {
  int H, W, h, w, t, d2;
  cin >> h >> w >> H >> W;
  if (W < H) {
    t = W;
    W = H;
    H = t;
  }
  if (h >= w) {
    t = h;
    h = w;
  } else t = w;
  d2 = t * t + h * h;
  if (h <= H and t <= W or H * sqrt(d2 - W * W) + W * sqrt(d2 - H * H) <= t * t - h * h) cout << "Possible";
  else cout << "Impossible";
  return 0;
}

#include <cmath>

#include <iostream>

using namespace std;

int main() {

int H, W, h, w, t, d2;

cin >> h >> w >> H >> W;

if (W < H) {

t = W;

W = H;

H = t;

}

if (h >= w) {

t = h;

h = w;

} else t = w;

d2 = t * t + h * h;

if (h <= H and t <= W or H * sqrt(d2 - W * W) + W * sqrt(d2 - H * H) <= t * t - h * h) cout << "Possible";

else cout << "Impossible";

return 0;

}

Второй способ решения

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

int main() {
  int H, W, h, w;
  cin >> h >> w >> H >> W;
  int t = max(H, W);
  H = min(H, W);
  W = t;
  t = max(h, w);
  h = min(h, w);
  w = t;
  int d2 = w * w + h * h;
  if (h <= H and w <= W or H * sqrt(d2 - W * W) + W * sqrt(d2 - H * H) <= w * w - h * h)
    cout << "Possible";
  else cout << "Impossible";
  return 0;
}

#include <cmath>

#include <iostream>

using namespace std;

int main() {

int H, W, h, w;

cin >> h >> w >> H >> W;

int t = max(H, W);

H = min(H, W);

W = t;

t = max(h, w);

h = min(h, w);

w = t;

int d2 = w * w + h * h;

if (h <= H and w <= W or H * sqrt(d2 - W * W) + W * sqrt(d2 - H * H) <= w * w - h * h)

cout << "Possible";

else cout << "Impossible";

return 0;

}

Код без условных операторов

#include <cmath> 
#include 

#include 

using namespace std;

int main() {
  int H, W, h, w;
  cin >> h >> w >> H >> W;
  int t = max(H, W);
  H = min(H, W);
  W = t;
  t = max(h, w);
  h = min(h, w);
  w = t;
  int d2 = w * w + h * h;
  (h <= H and w <= W or H * sqrt(d2 - W * W) + W * sqrt(d2 - H * H) <= w * w - h * h) and cout << "Possible";
  !(h <= H and w <= W or H * sqrt(d2 - W * W) + W * sqrt(d2 - H * H) <= w * w - h * h) and cout << "Impossible";
  return 0;
}

#include <cmath>

#include

using namespace std;

int main() {

int H, W, h, w;

cin >> h >> w >> H >> W;

int t = max(H, W);

H = min(H, W);

W = t;

t = max(h, w);

h = min(h, w);

w = t;

int d2 = w * w + h * h;

(h <= H and w <= W or H * sqrt(d2 - W * W) + W * sqrt(d2 - H * H) <= w * w - h * h) and cout << "Possible";

!(h <= H and w <= W or H * sqrt(d2 - W * W) + W * sqrt(d2 - H * H) <= w * w - h * h) and cout << "Impossible";

return 0;

}

Решение
Объявляем и вводим переменные $H$, $W$, $h$, $w$, где будем хранить длины открыток и конверта. Потом находим наибольшую сторону конверта и открытки, найдем диагональ конверта. Пользуясь тем, что мы знаем точно какие варианты «Possible» ставим выводим их, а в противном случае «Impossible».Утверждение: если выполняются четыре тривиальных неравенства: — то открытку в конверт можно вставить тогда и только тогда, когда можно расположить один из противоположных концов открытки на нижнем основании конверта, а второй — на верхнем и при этом открытка помещается в конверт. Из утверждения следует, что открытку нужно «поднять» на максимальный угол и посмотреть, входит ли открытка в таком положении в конверт, то есть меньше ли горизонтальное измерение «поднятой» открытки, чем ширина конверта.

Ссылки

ideone
e-olymp
e-olymp
ideone
ideone (без условных операторов)
e-olymp

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. Далі знаходимо довжину стрічки і її ціну з огляду на знижки. Також необхідно зробити перевірку, чи буде вигідніше придбати стрічку на таку кількість грошей, яке буде відповідати умовам знижки.

Related Images:

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

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

Задача

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

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

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

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

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

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

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

Тесты

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

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

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

#include<iostream>

using namespace std;

#define MAX 1000000000000000000

int main()

{

long long a, b, x;

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

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

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

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

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

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

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

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

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

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

if (possible_ans1 < 0)

possible_ans1 = MAX;

if (possible_ans2 < 0)

possible_ans2 = MAX;

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

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

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

return 0;

}

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

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

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

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

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

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

#include <iostream>

#include <cmath>

using namespace std;

int main() {

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

cin >> a >> b >> x;

s=a+b;

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

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

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

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

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

return 0;

}

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

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

Related Images:

e-olymp-1456. Барбос и Мухтар

26/12/2018 by Александр Довгань

Задача Барбос и Мухтар

Условие

На одной Большой Поляне росли два Больших Дерева – Большой Дуб и Большой Платан. К Большому Дубу были привязаны две собаки Барбос, длина цепи которого была равна $x$ метров, и Мухтар, длина его цепи $y$ метров. Однажды Барбосу надоело сидеть рядом с Мухтаром и он отбежал от Большого Дуба натянув свою цепь, Мухтар следуя примеру Барбоса, тоже решил подальше отбежать от Большого Дуба и тоже натянул свою цепь. Так они и сидели с натянутыми цепями, пока не заметили, что сидят на концах Прямой Тропы, на которой рос Большой Платан. Еще они заметили, что расстояние от Большого Дуба до Большого Платана равно расстоянию от Большого Дуба до Прямой Тропы. Также они не могли не заметить, что Барбосу в $z$ раз дальше бежать до Большого Платана по Прямой Тропе, чем Мухтару.

Каждая собака на Большой Поляне знает, что Большие Деревья – это материальные точки, а Прямая Тропа – отрезок прямой.

Помогите Барбосу и Мухтару узнать расстояние от Большого Дуба до Большого Платана.

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

Три вещественных числа $x$, $y$, $z$ (0 < $x, y, z $<[latex]10^7[/latex]) .

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

Вывести расстояние от Большого Дуба до Большого Платана с 9 десятичными знаками. Если это расстояние найти невозможно, то вывести слово IMPOSSIBLE.

№	Входные данные	Выходные данные
1	12 23 3	24.023426067
2	11 10 120	9.999927078
3	1 3 3	3.162277660

Решение

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

int main() {
    double x,y,z;
    double zero=0;
    cin>>y>>x>>z;
    if ((x==y)or(z==1)){
        cout<<"IMPOSSIBLE";
    }else if(z==0){
        cout<<y;
    }else {
        cout<<fixed;
        cout<<setprecision(9);
        zero=(y*y-x*x*z*z)/double(1-z*z);
        cout<<sqrt(zero);
    }
    return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main() {

double x,y,z;

double zero=0;

cin>>y>>x>>z;

if ((x==y)or(z==1)){

cout<<"IMPOSSIBLE";

}else if(z==0){

cout<<y;

}else {

cout<<fixed;

cout<<setprecision(9);

zero=(y*y-x*x*z*z)/double(1-z*z);

cout<<sqrt(zero);

}

return 0;

}

Решение

Пусть о — расстояние между Дубом и большим Платаном. После введения $x$, $y$ и $z$ проверяем первое условие if: если длины цепей Барбоса и Мухтара совпадают, то, когда обе собаки добежали до прямой тропы, треугольник, образованный их натянутыми цепями и прямой тропой является равнобедренным. Расстояние от Дуба до прямой тропы — высота треугольника, проведенная его основанию. Также основание высоты — Большой Платан (по условию). По свойству высоты, проведенной из вершины равнобедренного треугольника к его основанию, получим, что расстояние от Барбоса до Большого Платана равно расстоянию от Мухтара до Большого Платана, что противоречит условию (Барбосу в $z$ раз больше бежать до Большого Платана по Прямой Тропе, чем Мухтару). Также равенство расстояний до Большого Платана мы проверяем далее в условии: $(z==1)$. Если $z$ равен $1$, то эти отрезки равны, и утверждение, написанное выше, будет неверным. Проходя эту проверку, мы смотрим, удовлетворяют ли введенные данные условию задачи. Если утверждения в if выполняются — выводим IMPOSSIBLE, так как условия задачи не выполняются. В противном случае пропускаем первый if — данные введены корректно. Следующий условный оператор проверяет, равен ли $z$ нулю. Если да, то выводим y, потому что в таком случае расстояние от Дуба до Бльшого Платана равно длине цепи Мухтара. Именно Мухтара, так как, по условию, Барбосу бежать до Большого Платана дольше. Если данное условие не выполняется, вычисляем расстояние между деревьями по формуле: $\frac{(yy-xxzz)}{double(1-zz)}$
Затем выводим расстояние, округлив его до 9 знаков после запятой .

Ссылки

Ссылка на e-olymp

Ссылка на ideone

Related Images:

e-olymp 3766. Тысячелетие

25/12/2018 by Никита Шпилевский

Задача

Мудрый король решил ввести новый календарь. «Завтра будет первый день календаря, то есть день [latex]1[/latex] месяца [latex]1[/latex] года [latex]1[/latex]. Каждый год состоит из [latex]10[/latex] месяцев, с [latex]1[/latex] по [latex]10[/latex], и начинается с большого месяца. Обычный год начинается с большого месяца, за которым следует малый месяц, затем большой месяц и так далее один за другим. То есть первый месяц большой, второй малый, третий большой, …, десятый, он же последний, малый. Большой месяц состоит из [latex]20[/latex] дней, а малый месяц из [latex]19[/latex] дней. Однако годы, кратные трем, то есть год [latex]3[/latex], год [latex]6[/latex], год [latex]9[/latex] и так далее, состоит из [latex]10[/latex] больших месяцев и ни одного малого.»

Много времени прошло со дня введения календаря, и для празднования дня тысячелетия [latex]([/latex]год [latex]1000[/latex], месяц [latex]1[/latex], день [latex]1[/latex][latex])[/latex] решено было организовать королевскую лотерею, победителями которой станут те, кто прожил столько же дней, какое число выпадет в лотерее. Напишите программу, которая поможет людям вычислить количество дней от их дня рождения до дня тысячелетия.

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

Входные данные имеют следующий формат:

n
Y₁ M₁ D₁
Y₂ M₂ D₂
…
Y_n M_n D_n

Первая строка задает количество тестов [latex]n, \left ( n \leq 100 \right )[/latex]. Далее следуют n тестов, каждый из которых представляет собой одну строку с тремя натуральными числами [latex]Y_{i}\left ( Y_{i}< 1000 \right ), M_{i} \left ( M_{i}< 10 \right )[/latex] и [latex]D_{i} \left ( D_{i}\leq 20 \right )[/latex], задающих соответственно год, месяц и день рождения некоторого человека в нотации королевского календаря.

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

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

Тесты

№	Ввод	Вывод
1	2 1 1 1 344 3 1	196470 128976
2	3 696 5 1 182 9 5 998 8 7	59710 160715 252
3	2 344 2 19 696 4 19	128977 59712
4	1 999 10 20	1

Код

#include <iostream>
using namespace std;

int main() {
    short n;
    int  Y, M, D, daysAmount;
    const int bigMonth = 20, smallMonth = 19, bigYear = 200, smallYear = 195;
    cin >> n;
    for(int i = 0; i < n; i++) {
        daysAmount = 0;
        cin >> Y >> M >> D;
        if(Y % 3 == 0) daysAmount += (10 - M) * 20 + (20 - D); 
        else{
            if(M % 2 == 0) daysAmount += (smallMonth - D); 
            else daysAmount += (bigMonth - D);
            for(int month = (M + 1); month <= 10; month++) {
                if(month % 2 == 0) daysAmount += smallMonth;
                else daysAmount += bigMonth;
            }
        }
        for(int year = (Y + 1); year < 1000; year++) {
            if((year % 3) == 0) daysAmount += bigYear;
            else daysAmount += smallYear;
        }
        cout << daysAmount + 1 << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

short n;

int Y, M, D, daysAmount;

const int bigMonth = 20, smallMonth = 19, bigYear = 200, smallYear = 195;

cin >> n;

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

daysAmount = 0;

cin >> Y >> M >> D;

if(Y % 3 == 0) daysAmount += (10 - M) * 20 + (20 - D);

else{

if(M % 2 == 0) daysAmount += (smallMonth - D);

else daysAmount += (bigMonth - D);

for(int month = (M + 1); month <= 10; month++) {

if(month % 2 == 0) daysAmount += smallMonth;

else daysAmount += bigMonth;

}

for(int year = (Y + 1); year < 1000; year++) {

if((year % 3) == 0) daysAmount += bigYear;

else daysAmount += smallYear;

}

cout << daysAmount + 1 << endl;

}

return 0;

}

Решение

Запишем большой месяц (20 дней) и малый месяц (19 дней) соответственно в константы bigMonth и smallMonth, а также большой год (200 дней) и малый год (195 дней) соответственно в bigYear и smallYear. Затем проходим по циклу for n раз. Проверяем, если год, в котором родился человек, кратен 3, считаем количество полных прожитых человеком месяцев (каждый месяц — 30 дней) первого после рождения года, а также дни месяца, в котором он родился. В противном случае ( else) прибавляем дни каждого полного месяца, проверяя, большой он, и малый. Затем добавляем дни первого прожитого человеком месяца, так же учитывая его длительность. После этого проходим по циклу for, начальной итерацией которого является ( Y + 1), потому что дни года рождения мы посчитали ранее. За каждый год, номер которого кратен 3, добавляем 200 дней, а за некратный — 195. В конце выводим количество полученных дней +1, так как должны посчитать их количество включительно с днем рождения.

#include <iostream>
using namespace std;
 
int main() {
    short n;
    int  Y, M, D, daysAmount, multipleThree, notMultipleThree, lifeYears;
    const int bigMonth = 20, smallMonth = 19, bigYear = 200, smallYear = 195;
    cin >> n;
    for(int i = 0; i < n; i++) {
        daysAmount = 0;
        cin >> Y >> M >> D;
        lifeYears = 1000 - (Y + 1);
        if(lifeYears < 3 && lifeYears > 0) multipleThree = 1;
        else multipleThree = lifeYears / 3;
        if(lifeYears > 3 && lifeYears % 3 != 0)daysAmount += 5;
        notMultipleThree = lifeYears - multipleThree;
        daysAmount += multipleThree * bigYear + notMultipleThree * smallYear;
        if(Y % 3 == 0) {
              daysAmount += (10 - M) * bigMonth;
              daysAmount += bigMonth - D;
        }
        else {
            if(M % 2 != 0) {
                daysAmount += ( (10 - (M + 1)) / 2 ) * (bigMonth + smallMonth) + smallMonth;
                daysAmount += (bigMonth - D);
            }
            else {
                daysAmount += ( (10 - M) / 2 ) * (bigMonth + smallMonth);
                daysAmount += (smallMonth - D);
            }
        }
        cout << daysAmount + 1<< endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

short n;

int Y, M, D, daysAmount, multipleThree, notMultipleThree, lifeYears;

const int bigMonth = 20, smallMonth = 19, bigYear = 200, smallYear = 195;

cin >> n;

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

daysAmount = 0;

cin >> Y >> M >> D;

lifeYears = 1000 - (Y + 1);

if(lifeYears < 3 && lifeYears > 0) multipleThree = 1;

else multipleThree = lifeYears / 3;

if(lifeYears > 3 && lifeYears % 3 != 0)daysAmount += 5;

notMultipleThree = lifeYears - multipleThree;

daysAmount += multipleThree * bigYear + notMultipleThree * smallYear;

if(Y % 3 == 0) {

daysAmount += (10 - M) * bigMonth;

daysAmount += bigMonth - D;

}

else {

if(M % 2 != 0) {

daysAmount += ( (10 - (M + 1)) / 2 ) * (bigMonth + smallMonth) + smallMonth;

daysAmount += (bigMonth - D);

}

else {

daysAmount += ( (10 - M) / 2 ) * (bigMonth + smallMonth);

daysAmount += (smallMonth - D);

}

cout << daysAmount + 1<< endl;

}

return 0;

}

Решение

Снова проходим по циклу for n раз. Однако, теперь считаем дни без помощи циклов. В переменную lifeYears записываем годы жизни -1 , так как дни года рождения мы посчитаем далее. Затем, в if проверяем, находится ли количество прожитых лет в диапазоне от 1 до 3. Если да, то в переменную multipleThree записываем 1 — количество лет, кратных трем, то есть 999 год. В else multipleThree приравниваем к lifeYears, деленую на 3. В следующем if проверяем, больше ли количество лет трех. Если да, прибавляем 5 дней за больший 999 год. Затем, в переменную notMultipleThree записываем количество лет, не кратных трем. В следующей строке прибавляем ко дням жизни годы, умноженные на соответствующие им количества в каждом. После, в if проверяем, кратен ли год рождения 3. Если да, Находим количество полных прожитых месяцев, и умножаем его на bigMonth. Далее, находим дни, прожитые в месяц рождения. В else проверяем, родился ли человек в нечетном месяце. Если да, добавляем к дням количество дней, вычисляющееся по формуле, записанной в коде, если нет — аналогично. В конце, выводим количество дней +1, так как должны посчитать их количество включительно с днем рождения.

Ссылки

Related Images:

e-olymp 8526. Условный оператор — 3

24/12/2018 by Митя Лисовец

Задача

Вычислите значение [latex]y[/latex] в соответствии со следующим условием:

[latex]y = \begin{cases}
x+5, x<-4 \\
x^2-3x, -4\leq x\leq 7 \\
x^3+2x, x> 7
\end{cases}[/latex]

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

Одно целое число [latex]x\left ( -100\leq x\leq 100 \right )[/latex].

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

Выведите значение [latex]y[/latex] в соответствии с заданным условием.

Тесты

№	Ввод	Вывод
1	-8	-3
2	5	10
3	81	531603
3	-76	-71

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

#include <iostream>
using namespace std;

int main() {
    int x = 0, y = 0;
    cin >> x;
    if(x<-4) cout << x + 5 << endl;
    else if(x>=-4 && x<=7) cout << x*x - 3*x << endl;
    else if(x>7)cout << x*x*x + 2*x << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x = 0, y = 0;

cin >> x;

if(x<-4) cout << x + 5 << endl;

else if(x>=-4 && x<=7) cout << x*x - 3*x << endl;

else if(x>7)cout << x*x*x + 2*x << endl;

}

return 0;

}

Решение

Используем условные операторы для того, чтобы определить в каком диапазоне находится [latex]x\left ( x< -4,-4\leq x\leq 7,x> 7 \right )[/latex] и в соответствии с условием задачи подставляем [latex]x[/latex] в определенное уравнение.

Ссылки

Related Images:

e-olymp 75. Пираты и монеты

24/12/2018 by Даниил Мозгунов

Задача

[latex]n[/latex] пиратам удалось справедливо разделить клад из [latex]m[/latex] золотых монет — каждый получил свою часть согласно своему пиратскому рангу и стажу. Самый молодой пират взял [latex]a[/latex] монет, а каждый следующий пират брал на одну монету больше, чем предыдущий его коллега. Последним был капитан, которому досталось вдвое больше от запланированного, очевидно, что после него монет больше не осталось.

Сколько было пиратов вместе с капитаном, если известны [latex]a[/latex] и [latex]m[/latex]. Так как капитан без команды просто пират, то [latex]n > 1[/latex].

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

Два натуральных числа [latex]a[/latex] и [latex]m[/latex] ([latex]1 \leq a \leq 100, m < 15150[/latex]). Входные данные корректны.

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

Количество пиратов [latex]n[/latex].

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 25	3
2	3 24	4
3	4 38	5
4	5 55	6
5	6 75	7

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    double a, m, n, b, c, d;
    cin>>a>>m; 
    b = 2 * a + 1;
    c = 2 * a - 2 - 2 * m;
    d = b * b - 4 * c;
    n = ( -b + sqrt(d) ) / 2;
    cout<<n;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double a, m, n, b, c, d;

cin>>a>>m;

b = 2 * a + 1;

c = 2 * a - 2 - 2 * m;

d = b * b - 4 * c;

n = ( -b + sqrt(d) ) / 2;

cout<<n;

return 0;

}

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

Для решения задачи воспользуемся формулой арифметической прогрессии, которая в данном случае равна: [latex](2a + n — 1)\frac{n}{2} + a + n — 1[/latex]. Отсюда получаем квадратное уравнение : [latex]\frac{n^{2}}{2} + n(a + \frac{1}{2}) + a — 1 = m[/latex], упростим и получим: [latex]n^{2} + 2an + n + 2a — 2 = 2m[/latex]. В коде задаем чему равно [latex]b[/latex], [latex]c[/latex] и [latex]d[/latex]. Где [latex]b[/latex] и [latex]c[/latex] — коэффициенты квадратного уравнения, а [latex]d[/latex] — дискриминант квадратного уравнения, который вычисляем по формуле: [latex]b^{2} — 4c[/latex]. Они нужны для нахождения корня данного квадратного уравнения. При этом ответом на задачу будет только один корень квадратного уравнения, так как количество пиратов не может принимать отрицательное значение. Поэтому вычисляем корень квадратного уравнения по формуле: [latex]\frac{-b + \sqrt{b}}{2}[/latex], тем самым получаем ответ на нашу задачу.

Код программы (с циклом)

#include <iostream>
using namespace std;

int main() {
    unsigned int a, m, n = 0;
    cin>>a>>m;
    while (m - 2 * a != 0){
            m -= a;
            a ++;
            n ++;
    }
    cout<<n + 1;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned int a, m, n = 0;

cin>>a>>m;

while (m - 2 * a != 0){

m -= a;

a ++;

n ++;

}

cout<<n + 1;

return 0;

}

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

В данном способе используем цикл. Как он работает: в условии цикла задаем проверку, когда наступит очередь капитана и будет выполнятся равенство вида [latex]m — 2a = 0[/latex] цикл прекратит свою работу. Пока это равенство не будет выполнятся цикл будет выполнять работу арифметической прогрессии, постоянно увеличивая количество монет [latex]a[/latex] на каждого пирата при этом, вычитая каждый раз из общего клада [latex]m[/latex], также, пока не выполняется данное равенство, считаем количество пиратов [latex]n[/latex], путем прибавления [latex]n + 1[/latex], пока работает цикл. И когда цикл прекращает свою работу, в конце учитываем капитана и к полученному количеству пиратов [latex]n[/latex] прибавляем [latex]n + 1[/latex]. И получаем ответ на нашу задачу.

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

#include <iostream>
using namespace std;
 
int f(int a, int m, int n = 0) {
    if (m - 2*a == 0) {
        return n + 1;
    }
    else {
        return f(a + 1, m - a, n + 1);
    }
}
 
int main() {
    int a, m;
    cin >> a >> m;
    cout << f(a, m);
    return 0;
}

#include <iostream>

using namespace std;

int f(int a, int m, int n = 0) {

if (m - 2*a == 0) {

return n + 1;

}

else {

return f(a + 1, m - a, n + 1);

}

int main() {

int a, m;

cin >> a >> m;

cout << f(a, m);

return 0;

}

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

В данном способе воспользуемся рекурсивной функцией и условными операторами. Как это работает: внутри рекурсивной функции расписываем условные операторы, которые определяют равенством [latex]m — 2a = 0[/latex] — когда наступила очередь капитана, а пока это условие не выполняется, функция будет вызывать сама себя пока это условие не удовлетворится, функция каждый раз вызывается с новыми параметрами соответственно. Где [latex]a[/latex] — количество монет даваемое пиратам, увеличивается по рангу каждого пирата, [latex]m[/latex] — клад, от него отнимаем текущее [latex]a[/latex], и [latex]n[/latex] — количество пиратов, считаем пиратов. И в конце выводит количество пиратов. Задача решена.

Ссылки

Related Images:

e-olymp 839. Пересечение отрезков

24/12/2018 by Анна Неделева

Задача

Два отрезка на плоскости заданы целочисленными координатами своих концов в декартовой системе координат.

Требуется определить, существует ли у них общая точка.

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

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

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

Вывести слово $Yes$, если общая точка есть, или слово $No$ в противном случае.

Тесты

№	Входные данные	Выходные данные
1	0 0 1 0 1 0 1 1	Yes
2	0 0 1 0 2 0 3 0	No
3	7 4 1 1 1 1 3 2	Yes
4	-9725 -8992 9812 9925 -9999 7011 8122 -9248	Yes
5	-9999 -1 10000 1 0 0 0 1	No

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

С ветвлением:

#include <iostream>
#include <cmath>
#define E 1e-5
using namespace std;

double length(double x1, double y1, double x2, double y2){
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

bool is_include(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, double x, double y){
    return (
        abs(length(x1, y1, x, y) - length(x1, y1, x2, y2) + length(x, y, x2, y2)) <= E
    &&
        abs(length(x3, y3, x, y) - length(x3, y3, x4, y4) + length(x, y, x4, y4)) <= E
    );
}

bool is_overlap(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    return(
        abs(length(x1, y1, x3, y3) - length(x1, y1, x2, y2) + length(x3, y3, x2, y2)) <= E
    ||
        abs(length(x1, y1, x4, y4) - length(x1, y1, x2, y2) + length(x4, y4, x2, y2)) <= E
    ||
        abs(length(x3, y3, x1, y1) - length(x3, y3, x4, y4) + length(x1, y1, x4, y4)) <= E
    ||
        abs(length(x3, y3, x2, y2) - length(x3, y3, x4, y4) + length(x2, y2, x4, y4)) <= E
    );
}

int main() {
    long x1, y1, x2, y2, x3, y3, x4, y4;
    double x, y;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
    long long ky1, kx1, b1, ky2, kx2, b2;
    ky1 = y2 - y1;
    ky2 = y4 - y3;
    kx1 = x2 - x1;
    kx2 = x4 - x3;
    b1 = x1 * y2 - x2 * y1;
    b2 = x3 * y4 - x4 * y3;
    if (kx1 * ky2 == kx2 * ky1) {
        if (
            b1 * ky2 != b2 * ky1
        && 
            b1 * kx2 != b2 * kx1
        ) cout << "No";
        else if (is_overlap(x1, y1, x2, y2, x3, y3, x4, y4)) cout << "Yes";
        else cout << "No";
    } else {
        y = (double)(b2 * ky1 - b1 * ky2) / (double)(kx1 * ky2 - kx2 * ky1);
        x = (double)(b1 * kx2 - b2 * kx1) / (double)(ky1 * kx2 - ky2 * kx1);
        if (is_include(x1, y1, x2, y2, x3, y3, x4, y4, x, y)) cout << "Yes";
        else cout << "No";
    }
    return 0;
}

#include <iostream>

#include <cmath>

#define E 1e-5

using namespace std;

double length(double x1, double y1, double x2, double y2){

return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));

}

bool is_include(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, double x, double y){

return (

abs(length(x1, y1, x, y) - length(x1, y1, x2, y2) + length(x, y, x2, y2)) <= E

abs(length(x3, y3, x, y) - length(x3, y3, x4, y4) + length(x, y, x4, y4)) <= E

);

}

bool is_overlap(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {

return(

abs(length(x1, y1, x3, y3) - length(x1, y1, x2, y2) + length(x3, y3, x2, y2)) <= E

abs(length(x1, y1, x4, y4) - length(x1, y1, x2, y2) + length(x4, y4, x2, y2)) <= E

abs(length(x3, y3, x1, y1) - length(x3, y3, x4, y4) + length(x1, y1, x4, y4)) <= E

abs(length(x3, y3, x2, y2) - length(x3, y3, x4, y4) + length(x2, y2, x4, y4)) <= E

);

}

int main() {

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

double x, y;

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

long long ky1, kx1, b1, ky2, kx2, b2;

ky1 = y2 - y1;

ky2 = y4 - y3;

kx1 = x2 - x1;

kx2 = x4 - x3;

b1 = x1 * y2 - x2 * y1;

b2 = x3 * y4 - x4 * y3;

if (kx1 * ky2 == kx2 * ky1) {

if (

b1 * ky2 != b2 * ky1

b1 * kx2 != b2 * kx1

) cout << "No";

else if (is_overlap(x1, y1, x2, y2, x3, y3, x4, y4)) cout << "Yes";

else cout << "No";

} else {

y = (double)(b2 * ky1 - b1 * ky2) / (double)(kx1 * ky2 - kx2 * ky1);

x = (double)(b1 * kx2 - b2 * kx1) / (double)(ky1 * kx2 - ky2 * kx1);

if (is_include(x1, y1, x2, y2, x3, y3, x4, y4, x, y)) cout << "Yes";

else cout << "No";

}

return 0;

}

без ветвления:

#include <iostream>
#include <cmath>
#define E 1e-5
using namespace std;

double length(double x1, double y1, double x2, double y2){
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

bool is_include(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, double x, double y){
    return (
        abs(length(x1, y1, x, y) - length(x1, y1, x2, y2) + length(x, y, x2, y2)) <= E
    &&
        abs(length(x3, y3, x, y) - length(x3, y3, x4, y4) + length(x, y, x4, y4)) <= E
    );
}

bool is_overlap(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    return(
        abs(length(x1, y1, x3, y3) - length(x1, y1, x2, y2) + length(x3, y3, x2, y2)) <= E
    ||
        abs(length(x1, y1, x4, y4) - length(x1, y1, x2, y2) + length(x4, y4, x2, y2)) <= E
    ||
        abs(length(x3, y3, x1, y1) - length(x3, y3, x4, y4) + length(x1, y1, x4, y4)) <= E
    ||
        abs(length(x3, y3, x2, y2) - length(x3, y3, x4, y4) + length(x2, y2, x4, y4)) <= E
    );
}

int main() {
    long x1, y1, x2, y2, x3, y3, x4, y4;
    double x, y;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
    long long ky1, kx1, b1, ky2, kx2, b2;
    ky1 = y2 - y1;
    ky2 = y4 - y3;
    kx1 = x2 - x1;
    kx2 = x4 - x3;
    b1 = x1 * y2 - x2 * y1;
    b2 = x3 * y4 - x4 * y3;
    (kx1 * ky2 == kx2 * ky1) && (
        (
            b1 * ky2 != b2 * ky1
        && 
            b1 * kx2 != b2 * kx1
        ) && (cout << "No")
        || (is_overlap(x1, y1, x2, y2, x3, y3, x4, y4)) && (cout << "Yes") 
        || (cout << "No")
    ) || (
        y = (double)(b2 * ky1 - b1 * ky2) / (double)(kx1 * ky2 - kx2 * ky1),
        x = (double)(b1 * kx2 - b2 * kx1) / (double)(ky1 * kx2 - ky2 * kx1),
        (is_include(x1, y1, x2, y2, x3, y3, x4, y4, x, y)) && (cout << "Yes")
        || (cout << "No")
    );
    return 0;
}

#include <iostream>

#include <cmath>

#define E 1e-5

using namespace std;

double length(double x1, double y1, double x2, double y2){

return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));

}

bool is_include(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, double x, double y){

return (

abs(length(x1, y1, x, y) - length(x1, y1, x2, y2) + length(x, y, x2, y2)) <= E

abs(length(x3, y3, x, y) - length(x3, y3, x4, y4) + length(x, y, x4, y4)) <= E

);

}

bool is_overlap(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {

return(

abs(length(x1, y1, x3, y3) - length(x1, y1, x2, y2) + length(x3, y3, x2, y2)) <= E

abs(length(x1, y1, x4, y4) - length(x1, y1, x2, y2) + length(x4, y4, x2, y2)) <= E

abs(length(x3, y3, x1, y1) - length(x3, y3, x4, y4) + length(x1, y1, x4, y4)) <= E

abs(length(x3, y3, x2, y2) - length(x3, y3, x4, y4) + length(x2, y2, x4, y4)) <= E

);

}

int main() {

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

double x, y;

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

long long ky1, kx1, b1, ky2, kx2, b2;

ky1 = y2 - y1;

ky2 = y4 - y3;

kx1 = x2 - x1;

kx2 = x4 - x3;

b1 = x1 * y2 - x2 * y1;

b2 = x3 * y4 - x4 * y3;

(kx1 * ky2 == kx2 * ky1) && (

(

b1 * ky2 != b2 * ky1

b1 * kx2 != b2 * kx1

) && (cout << "No")

|| (is_overlap(x1, y1, x2, y2, x3, y3, x4, y4)) && (cout << "Yes")

|| (cout << "No")

) || (

y = (double)(b2 * ky1 - b1 * ky2) / (double)(kx1 * ky2 - kx2 * ky1),

x = (double)(b1 * kx2 - b2 * kx1) / (double)(ky1 * kx2 - ky2 * kx1),

(is_include(x1, y1, x2, y2, x3, y3, x4, y4, x, y)) && (cout << "Yes")

|| (cout << "No")

);

return 0;

}

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

Чтобы проверить пересекаются ли заданные отрезки построим прямые, которым они принадлежат, затем найдём точку их пересечения и проверим принадлежит ли она каждому из отрезков.
Для построения прямых воспользуемся формулой прямой проходящей через две точки и немного её преобразуем:
$\frac{x — x_1}{x_2 — x_1} = \frac{y — y_1}{y_2 — y_1}$ ~ $(x — x_1) \cdot (y_2 — y_1) = (y — y_1) \cdot (x_2 — x_1)$ ~ $x \cdot (y_2 — y_1) — y_2 \cdot x_1 + y_1 \cdot x_1 = y \cdot (x_2 — x_1) — x_2 \cdot y_1 + x_1 \cdot y_1$ ~ $y \cdot (x_2 — x_1) = x \cdot (y_2 — y_1) + x_2 \cdot y_1 — x_1 \cdot y_2$.
Обозначим за $k_x$ множитель при $x$, за $k_y$ множитель при $y$, а всё остальное за $b$. Тогда имеем уравнение вида:
$y \cdot k_y = x \cdot k_x + b$, таких у нас будет 2:

$y \cdot k_{y_1} = x \cdot k_{x_1} + b_1$
$y \cdot k_{y_2} = x \cdot k_{x_2} + b_2$

Теперь рассмотрим несколько случаев:
1. Прямые параллельны, следовательно могут не иметь точки пересечения или совпадать.
Проверим совпадают ли $b_1$ и $b_2$. Так как уравнения не сокращены на НОД, то рассмотрим равенство отношений $b_1$ и $b_2$ на $k_{y_1}$, $k_{x_1}$ и $k_{y_2}$, $k_{x_2}$ соответственно. Если они равны, то прямые совпадают. Иначе не имеют точек пересечения, а следовательно и отрезки тоже не пересекаются.
Когда прямые совпадают, необходимо проверить, что отрезки на этой прямой имеют хоть какую-то общую точку. Каждый из концов каждого отрезка проверим на вхождение в другой. Если такое вхождение есть, то отрезки пересекаются, иначе нет.
2. Прямые не параллельны, а следовательно имеют точку пересечения.
Тогда, решив систему двух линейных уравнений в общем виде получим что:

$x = \frac{b_1 \cdot k_{x_2} — b_2 \cdot k_{x_1}}{k_{y_1} \cdot k_{x_2} — k_{x_1} \cdot k_{y_2}}$
$y = \frac{b_2 \cdot k_{y_1} — b_1 \cdot k_{y_2}}{k_{x_1} \cdot k_{y_2} — k_{y_1} \cdot k_{x_2}}$

Осталось проверить находится ли точка с координатами $(x, y)$ в каждом из отрезков. Для этого просуммируем расстояния от этой точки до границ каждого отрезка и сравним с длинами отрезков. Если суммы соответственно совпали с длинами, то отрезки пересекаются, иначе — нет.

Ссылки

Related Images:

e-olymp 8521. Условный оператор — 2

23/12/2018 by Даниил Кадзевич

Задача

Вычислите значение y в соответствии со следующим условием:

[latex]y=\begin{cases}x^{3} + 5x, x\geq 10\\\ x^{2} — 2x + 4 , x < 10\end{cases}[/latex]

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

Одно целое число [latex] x(-10000 ≤ x ≤ 10000)[/latex].

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

Выведите значение y в соответствии с заданным условием.

Тесты

№	Ввод	Вывод
1	2	4
2	20	8100
3	100	1000500
3	-5	39

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

#include <iostream>

using namespace std;

long long int f(int x) {
    return (x >= 10) ? (x*x*x + x*5) : (x*x - 2*x + 4);
}

int main() {
    int x;
    cin >> x;
    cout << f(x) << endl;
    return 0;
}

#include <iostream>

using namespace std;

long long int f(int x) {

return (x >= 10) ? (x*x*x + x*5) : (x*x - 2*x + 4);

}

int main() {

int x;

cin >> x;

cout << f(x) << endl;

return 0;

}

Решение

Используем тернарный оператор для проверки [latex]x\geq 10[/latex].

Ссылки

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

#include <iostream>

using namespace std;

int main() {
    long long int x;
    cin >> x;
    (x >= 10) && (cout << (x*x*x + x*5) << endl);
    (x < 10) && (cout << (x*x - 2*x + 4) << endl);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long int x;

cin >> x;

(x >= 10) && (cout << (x*x*x + x*5) << endl);

(x < 10) && (cout << (x*x - 2*x + 4) << endl);

return 0;

}

Решение

Используем логический оператор && так как он не вычисляет второе условие, если первое ложно.

Ссылки

Related Images:

e-olymp 1623. Чётные и нечётные числа

23/12/2018 by Елена Шихова

Задача

Дано три целых числа $a$, $b$, $c$. Определить, есть ли среди них хотя бы одно чётное и хотя бы одно нечётное число.

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

Числа $a$, $b$, $c$, не превышающие по модулю $10000$ (числа могут быть отрицательными).

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

Вывести «YES» или «NO».

Тесты

#	Входные данные	Выходные данные
1	3 4 5	YES
2	7 7 7	NO
3	2 3 50	YES
4	-1 -3 5	NO
5	10 5 -2	YES

Код решения

#include <iostream>
using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << ((a % 2 + b % 2 + c % 2 != 0) and (a % 2 + b % 2 + c % 2 != 3) ? "YES":"NO");
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, c;

cin >> a >> b >> c;

cout << ((a % 2 + b % 2 + c % 2 != 0) and (a % 2 + b % 2 + c % 2 != 3) ? "YES":"NO");

return 0;

}

Решение

Проверяем, есть ли среди введенных чисел хотя бы одно четное и хотя бы одно нечетное. При выполнении обоих условий, выводим «YES», в другом случае «NO».

Related Images:

e-olymp 8654. Целочисленное умножение

22/12/2018 by Николай Козиний

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

Задача

Даны три целых числа $a, b, c.$ Вычислить значение выражения $a \cdot b \text{ mod } c.$

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

Три целых положительных числа $a, b, c \left( a, b, c < 2^{63} \right).$

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

Вывести значение выражения $ a \cdot b \text{ mod } c.$

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	2 3 2	0
2	11 3 2	1
3	123456789 987654321 17	0
4	5000400000023 23000400400500 100000000070707	68238553233174
5	10000018585 10000000000005 101020304050607080	85850050000993845

Решение

Для решения задачи напишем рекурсивную функцию умножения, основанную на том, что [latex]\displaystyle a\cdot b =\displaystyle[/latex][latex] \begin{cases}\left(a+a\right)\cdot\frac{b}{2} &\text{} b\equiv_{2} 0 \\a+a\cdot\left(b-1\right) & \text{} b \not \equiv_{2} 0\ \end{cases}.[/latex] Поскольку максимальное значение из условия задачи в два раза меньше максимального числа из 64-битных беззнаковых чисел и[latex]\left(a\cdot b\right)\text{ mod } c =\left(a\text{ mod } с \cdot b\text { mod }c\right)\text{ mod }c,[/latex] мы можем на каждом шагу применять к $a$ и $b$ операцию остатка от деления на $c$ , за счет чего произведение никогда не будет превосходить $2^{64}-1$.

include <iostream>
unsigned long long mult(unsigned long long x,unsigned long long y,unsigned long long const z){
    if(y == 1)return x % z;
    else if(y == 0)return 0;
    else if( y & 1 )return (x % z + mult(x % z,(y - 1) % z,z))%z;
    else return mult((x + x)%z,(y / 2) % z,z);
 
}
int main() {
    unsigned long long a,b,c;
    std::cin >> a >> b >> c;
    std::cout << mult(a,b,c);
}

include <iostream>

unsigned long long mult(unsigned long long x,unsigned long long y,unsigned long long const z){

if(y == 1)return x % z;

else if(y == 0)return 0;

else if( y & 1 )return (x % z + mult(x % z,(y - 1) % z,z))%z;

else return mult((x + x)%z,(y / 2) % z,z);

}

int main() {

unsigned long long a,b,c;

std::cin >> a >> b >> c;

std::cout << mult(a,b,c);

}

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

Related Images:

e-olymp 774. Торт

22/12/2018 by Виктор Иванов

Задача

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

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

Содержит три натуральных числа: радиус стола [latex]r \left(1\leqslant r\leqslant 1000 \right)[/latex], ширину [latex]w[/latex] и длину [latex]l[/latex] торта [latex] \left(1\leqslant w \leqslant l \leqslant 1000\right)[/latex].

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

Вывести слово [latex]YES[/latex], если торт помещается на стол, и слово [latex]NO[/latex] в противном случае.

Тесты

№	Входные данные	Выходные данные
1	38 40 60	YES
2	35 20 70	NO
3	50 60 80	YES
4	30 60 90	NO

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

с ветвлением:

#include <iostream>

using namespace std;
int main() {
    int r, w, l;
    cin >> r >> w >> l;
    cout << (w * w + l * l <= 4 * r * r ? "YES" : "NO");
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int r, w, l;

cin >> r >> w >> l;

cout << (w * w + l * l <= 4 * r * r ? "YES" : "NO");

return 0;

}

без ветвления:

#include <iostream>
using namespace std;

bool myBool(int x, int y, int z) {
    return(x * x + y * y <= 4 * z * z);
}

int main() {
    int r, w, l;
    cin >> r >> w >> l;
    myBool(w, l, r) && cout << "YES";
    !myBool(w, l, r) && cout << "NO";
    return 0;
}

#include <iostream>

using namespace std;

bool myBool(int x, int y, int z) {

return(x * x + y * y <= 4 * z * z);

}

int main() {

int r, w, l;

cin >> r >> w >> l;

myBool(w, l, r) && cout << "YES";

!myBool(w, l, r) && cout << "NO";

return 0;

}

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

Вписанный в окружность прямоугольник

Для того, чтобы узнать, помещается торт на столе или нет, необходимо найти диагональ прямоугольного торта. Зная длину и ширину прямоугольника, находим диагональ по теореме Пифагора. Если она равна или меньше диаметра стола $AB^2$ + $AD^2$ <= 4$OD^2$, значит торт помещается, и пишем "YES". Если диагональ больше диаметра стола, пишем "NO".

Ссылки

Условие задачи на e-olymp
Код программы с ветвлением на ideone
Код программы без ветвления на ideone

Related Images:

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

22/12/2018 by Михаил Бутник

Задача

По трем натуральным числам [latex]a[/latex], [latex]b[/latex] и [latex]m[/latex] вычислить значение [latex]a^b\mod m[/latex].

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

Три натуральных числа [latex]a[/latex], [latex]b[/latex], [latex]m[/latex] [latex]\left(1 \leqslant a, m \leqslant 10^9, 2 \leqslant b \leqslant 10^7\right)[/latex].

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

Вывести [latex]a^b\mod m[/latex].

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1 2 100	1
2	100 2 1000000	10000
3	2 3 50	8
4	9 2 1	0
5	9 2 25	6

Код с циклом

#include <iostream>
using namespace std;
long binpow (long a, long n, long m) {
    long res = 1;
    while (n) {
        if (n & 1) {
            res *= a;
            res %= m;
        }
        a *= (a % m);
        a %= m;
        n >>= 1;
    }
    return res % m;
}
 
int main() {
    long a, b, m;
    cin >> a >> b >> m;
    cout << binpow (a, b, m);
    return 0;
}

#include <iostream>

using namespace std;

long binpow (long a, long n, long m) {

long res = 1;

while (n) {

if (n & 1) {

res *= a;

res %= m;

}

a *= (a % m);

a %= m;

n >>= 1;

}

return res % m;

}

int main() {

long a, b, m;

cin >> a >> b >> m;

cout << binpow (a, b, m);

return 0;

}

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

#include <iostream>
using namespace std;
long binpow (long a, long n, long m) {
    if (n == 0)
        return 1 % m;
    if (n % 2 == 1)
        return (binpow (a, n - 1, m) * a) % m;
    else {
        return binpow ((a * a) % m, n/2, m);
    }
}
 
int main() {
    long a, b, m;
    cin >> a >> b >> m;
    cout << binpow (a, b, m);
    return 0;
}

#include <iostream>

using namespace std;

long binpow (long a, long n, long m) {

if (n == 0)

return 1 % m;

if (n % 2 == 1)

return (binpow (a, n - 1, m) * a) % m;

else {

return binpow ((a * a) % m, n/2, m);

}

int main() {

long a, b, m;

cin >> a >> b >> m;

cout << binpow (a, b, m);

return 0;

}

Решение

Для решения этой задачи я воспользовался функцией бинарного возведения в степень binpow () (рекурсивной для программы с ветвлением и нерекурсивной для программы с циклом). Это приём, позволяющий возводить любое число в [latex]n[/latex]-ую степень за [latex]O(\log n)[/latex] умножений. В этой функции при возведении я дополнительно применял операцию деление с остатком к результату res и возводимому числу a для того, чтобы получить решение.

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

Related Images:

e-olymp 8528. Система глобальнейшего позиционирования

17/12/2018 by Таисия Ткачева

Задача

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

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

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

В первой строке находятся три пары чисел $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$, $x_{3}$ и $y_{3}$ — координаты вышек. Во второй строке находятся три неотрицательных числа — расстояния до соответствующих вышек. Все входные числа целые и по модулю не превышают $50$.

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

Если не существует такого местоположения объекта, что расстояния до вышек соответствовали бы данным, то выведите в единственное слово «Impossible». Иначе выведите два числа — координаты объекта с точностью до шести знаков после запятой.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	0 4 2 6 5 0 2 2 5	2.000000 4.000000
2	2 2 0 1 1 1 2.828427 1 1.4142135	0.000000 0.000000
3	-5 3 -3 3 -2 4 3 1 1	-2.000000 3.000000
4	0 0 2 1 2 -2 0.841722586 2 2	0.677124 -0.500000
5	0 0 10 0 5 6 7 7 1	Impossible

Код программы (Линейные вычисления)

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

int main() {
    double eps = 1e-6;
    double x1, y1, x2, y2, x3, y3, r1, r2, r3, x, y;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> r1 >> r2 >> r3;
    x = ((y2 - y1) * (r2 * r2 - r3 * r3 - y2 * y2 + y3 * y3 - x2 * x2 + x3 * x3) - (y3 - y2) * (r1 * r1 - r2 * r2 - y1 * y1 + y2 * y2 - x1 * x1 + x2 * x2)) / (2 * ((y3 - y2) * (x1 - x2)  - (y2 - y1) * (x2 - x3)));
    y = ((x2 - x1) * (r2 * r2 - r3 * r3 - x2 * x2 + x3 * x3 - y2 * y2 + y3 * y3) - (x3 - x2) * (r1 * r1 - r2 * r2 - x1 * x1 + x2 * x2 - y1 * y1 + y2 * y2)) / (2 * ((x3 - x2) * (y1 - y2)  - (x2 - x1) * (y2 - y3)));
    ((abs((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y) - r1 * r1) < eps) && (cout << fixed << setprecision (6) << x << " " << y << endl)) || ((abs((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y) - r1 * r1) >= eps) && (cout << "Impossible" << endl)); 
    return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main() {

double eps = 1e-6;

double x1, y1, x2, y2, x3, y3, r1, r2, r3, x, y;

cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> r1 >> r2 >> r3;

x = ((y2 - y1) * (r2 * r2 - r3 * r3 - y2 * y2 + y3 * y3 - x2 * x2 + x3 * x3) - (y3 - y2) * (r1 * r1 - r2 * r2 - y1 * y1 + y2 * y2 - x1 * x1 + x2 * x2)) / (2 * ((y3 - y2) * (x1 - x2) - (y2 - y1) * (x2 - x3)));

y = ((x2 - x1) * (r2 * r2 - r3 * r3 - x2 * x2 + x3 * x3 - y2 * y2 + y3 * y3) - (x3 - x2) * (r1 * r1 - r2 * r2 - x1 * x1 + x2 * x2 - y1 * y1 + y2 * y2)) / (2 * ((x3 - x2) * (y1 - y2) - (x2 - x1) * (y2 - y3)));

((abs((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y) - r1 * r1) < eps) && (cout << fixed << setprecision (6) << x << " " << y << endl)) || ((abs((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y) - r1 * r1) >= eps) && (cout << "Impossible" << endl));

return 0;

}

Код программы (Ветвления)

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
 
int main() {
    double eps = 1e-6;
    double x1, y1, x2, y2, x3, y3, r1, r2, r3, x, y;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> r1 >> r2 >> r3;
    x = ((y2 - y1) * (r2 * r2 - r3 * r3 - y2 * y2 + y3 * y3 - x2 * x2 + x3 * x3) - (y3 - y2) * (r1 * r1 - r2 * r2 - y1 * y1 + y2 * y2 - x1 * x1 + x2 * x2)) / (2 * ((y3 - y2) * (x1 - x2)  - (y2 - y1) * (x2 - x3)));
    y = ((x2 - x1) * (r2 * r2 - r3 * r3 - x2 * x2 + x3 * x3 - y2 * y2 + y3 * y3) - (x3 - x2) * (r1 * r1 - r2 * r2 - x1 * x1 + x2 * x2 - y1 * y1 + y2 * y2)) / (2 * ((x3 - x2) * (y1 - y2)  - (x2 - x1) * (y2 - y3)));
    if (abs((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y) - r1 * r1) < eps) cout << fixed << setprecision (6) << x << " " << y << endl;
    else cout << "Impossible" << endl; 
    return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main() {

double eps = 1e-6;

double x1, y1, x2, y2, x3, y3, r1, r2, r3, x, y;

cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> r1 >> r2 >> r3;

if (abs((x1 - x) * (x1 - x) + (y1 - y) * (y1 - y) - r1 * r1) < eps) cout << fixed << setprecision (6) << x << " " << y << endl;

else cout << "Impossible" << endl;

return 0;

}

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

Для решения данной задачи нужно найти точку пересечения трёх окружностей, следовательно получаем систему из трёх уравнений окружностей, а именно:

[latex]\begin{cases}(x_{1} — x)^{2} + (y_{1} — y)^{2} = r_{1}^{2},\\(x_{2} — x)^{2} + (y_{2} — y)^{2} = r_{2}^{2}, \\(x_{3} — x)^{2} + (y_{3} — y)^{2} = r_{3}^{2};\end{cases}[/latex]

где $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$, $x_{3}$ и $y_{3}$ — координаты вышек, $r_{1}$, $r_{2}$ и $r_{3}$ — расстояния до соответствующих вышек, $x$ и $y$ — координаты объекта.

После применения формул сокращённого умножения многочленов, получим систему вида:

[latex]\begin{cases}x_1^2-2x_{1}x+x^{2}+y_1^2-2y_{1}y+y^{2}=r_1^2, & (1)\\x_2^2-2x_{2}x+x^{2}+y_2^2-2y_{2}y+y^{2}=r_2^2, & (2)\\x_3^2-2x_{3}x+x^{2}+y_3^2-2y_{3}y+y^{2}=r_3^2; & (3)\end{cases}[/latex]

Отнимем от первого уравнения второе и от второго уравнения третье, получим:

[latex]\begin{cases}x_1^2-x_2^2-2x_{1}x+2x_{2}x+y_1^2-y_2^2-2y_{1}y+2y_{2}y=r_1^2-r_2^2, & (1)-(2)\\x_2^2-x_3^2-2x_{2}x+2x_{3}x+y_2^2-y_3^2-2y_{2}y+2y_{3}y=r_2^2-r_3^2; & (2)-(3)\end{cases}[/latex]

Далее выражаем $x$ и $y$:

[latex]\begin{cases}2y(y_{2}-y_{1})=r_1^2-r_2^2-x_1^2+x_2^2+2x_{1}x-2x_{2}x-y_1^2+y_2^2,\\2y(y_{3}-y_{2})=r_2^2-r_3^2-x_2^2+x_3^2+2x_{2}x-2x_{3}x-y_2^2+y_3^2;\end{cases}[/latex] [latex]\begin{cases}2x(x_{2}-x_{1})=r_1^2-r_2^2-y_1^2+y_2^2+2y_{1}y-2y_{2}y-x_1^2+x_2^2,\\2x(x_{3}-x_{2})=r_2^2-r_3^2-y_2^2+y_3^2+2y_{2}y-2y_{3}y-x_2^2+x_3^2;\end{cases}[/latex] [latex]\begin{cases}y=\frac{r_1^2-r_2^2-x_1^2+x_2^2+2x_{1}x-2x_{2}x-y_1^2+y_2^2}{2(y_{2}-y_{1})},\\y=\frac{r_2^2-r_3^2-x_2^2+x_3^2+2x_{2}x-2x_{3}x-y_2^2+y_3^2}{2(y_{3}-y_{2})};\end{cases}[/latex] [latex]\begin{cases}x=\frac{r_1^2-r_2^2-y_1^2+y_2^2+2y_{1}y-2y_{2}y-x_1^2+x_2^2}{2(x_{2}-x_{1})},\\x=\frac{r_2^2-r_3^2-y_2^2+y_3^2+2y_{2}y-2y_{3}y-x_2^2+x_3^2}{2(x_{3}-x_{2})};\end{cases}[/latex]

Приравняем соответствующие координаты объекта, получим систему вида:

[latex]\begin{cases}\frac{r_1^2-r_2^2-x_1^2+x_2^2+2x_{1}x-2x_{2}x-y_1^2+y_2^2}{2(y_{2}-y_{1})}=\frac{r_2^2-r_3^2-x_2^2+x_3^2+2x_{2}x-2x_{3}x-y_2^2+y_3^2}{2(y_{3}-y_{2})},\\\frac{r_1^2-r_2^2-y_1^2+y_2^2+2y_{1}y-2y_{2}y-x_1^2+x_2^2}{2(x_{2}-x_{1})}=\frac{r_2^2-r_3^2-y_2^2+y_3^2+2y_{2}y-2y_{3}y-x_2^2+x_3^2}{2(x_{3}-x_{2})};\end{cases}[/latex]

Находим координаты объекта:

[latex]\begin{cases} \begin{split} 2(y_{3}-y_{2})(r_1^2-r_2^2-x_1^2+x_2^2+2x_{1}x-2x_{2}x-y_1^2+y_2^2)= \\ =2(y_{2}-y_{1})(r_2^2-r_3^2-x_2^2+x_3^2+2x_{2}x-2x_{3}x-y_2^2+y_3^2),\\2(x_{3}-x_{2})(r_1^2-r_2^2-y_1^2+y_2^2+2y_{1}y-2y_{2}y-x_1^2+x_2^2)= \\ =2(x_{2}-x_{1})(r_2^2-r_3^2-y_2^2+y_3^2+2y_{2}y-2y_{3}y-x_2^2+x_3^2); \end{split} \end{cases}[/latex] [latex]\begin{cases} \begin{split} 2(y_{3}-y_{2})(2x_{1}x-2x_{2}x)-2(y_{2}-y_{1})(2x_{2}x-2x_{3}x) = \\ =2(y_{2}-y_{1})(r_2^2-r_3^2-x_2^2+x_3^2-y_2^2+y_3^2)-\\-2(y_{3}-y_{2})(r_1^2-r_2^2-x_1^2+x_2^2-y_1^2+y_2^2),\\2(x_{3}-x_{2})(2y_{1}y-2y_{2}y)-2(x_{2}-x_{1})(2y_{2}y-2y_{3}y)= \\ =2(x_{2}-x_{1})(r_2^2-r_3^2-y_2^2+y_3^2-x_2^2+x_3^2)-\\-2(x_{3}-x_{2})(r_1^2-r_2^2-y_1^2+y_2^2-x_1^2+x_2^2);\end{split}\end{cases}[/latex] [latex]\begin{cases} \begin{split} 4x(y_{3}-y_{2})(x_{1}-x_{2})-4x(y_{2}-y_{1})(x_{2}-x_{3})= \\ =2(y_{2}-y_{1})(r_2^2-r_3^2-x_2^2+x_3^2-y_2^2+y_3^2)-\\-2(y_{3}-y_{2})(r_1^2-r_2^2-x_1^2+x_2^2-y_1^2+y_2^2),\\4y(x_{3}-x_{2})(y_{1}-y_{2})-4y(x_{2}-x_{1})(y_{2}-y_{3})= \\ =2(x_{2}-x_{1})(r_2^2-r_3^2-y_2^2+y_3^2-x_2^2+x_3^2)-\\-2(x_{3}-x_{2})(r_1^2-r_2^2-y_1^2+y_2^2-x_1^2+x_2^2);\end{split}\end{cases}[/latex] [latex]\begin{cases}x=\frac{2((y_{2}-y_{1})(r_2^2-r_3^2-x_2^2+x_3^2-y_2^2+y_3^2)-(y_{3}-y_{2})(r_1^2-r_2^2-x_1^2+x_2^2-y_1^2+y_2^2))}{4((y_{3}-y_{2})(x_{1}-x_{2})-(y_{2}-y_{1})(x_{2}-x_{3}))},\\y=\frac{2((x_{2}-x_{1})(r_2^2-r_3^2-y_2^2+y_3^2-x_2^2+x_3^2)-(x_{3}-x_{2})(r_1^2-r_2^2-y_1^2+y_2^2-x_1^2+x_2^2))}{4((x_{3}-x_{2})(y_{1}-y_{2})-(x_{2}-x_{1})(y_{2}-y_{3}))};\end{cases}[/latex] [latex]\begin{cases}x=\frac{(y_{2}-y_{1})(r_2^2-r_3^2-x_2^2+x_3^2-y_2^2+y_3^2)-(y_{3}-y_{2})(r_1^2-r_2^2-x_1^2+x_2^2-y_1^2+y_2^2)}{2((y_{3}-y_{2})(x_{1}-x_{2})-(y_{2}-y_{1})(x_{2}-x_{3}))},\\y=\frac{(x_{2}-x_{1})(r_2^2-r_3^2-y_2^2+y_3^2-x_2^2+x_3^2)-(x_{3}-x_{2})(r_1^2-r_2^2-y_1^2+y_2^2-x_1^2+x_2^2)}{2((x_{3}-x_{2})(y_{1}-y_{2})-(x_{2}-x_{1})(y_{2}-y_{3}))}.\end{cases}[/latex]

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

Ссылки

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

Код программы (Линейные вычисления)

Код программы (Ветвления)