e-olymp 8534. Хлопці на ім’я Валя

09/12/2018 by Наталья Федина

Задача

У літньому таборі $n$ дітей. Серед будь-яких $L$ дітей є хоча б одна дівчинка. Серед будь-яких $v$ дітей є дитина на ім’я Валя (це ім’я можуть мати і хлопчик, і дівчинка). Напишіть програму, що визначає умову наявності в таборі хоча б одного Валентина.

Вхідні дані

$100≤n≤200$, $40≤L≤140$, $20≤v≤70$. Вхідні дані ввести зі стандартного пристрою введення в один рядок, розділяючи значення пропусками.

Вихідні дані

На стандартний пристрій виведення вивести $1$, якщо відповідь на питання умови стверджувальне. Інакше вивести $0$.

Тесты

Входные данные	Выходные данные
110 80 27	1
100 70 30	1
70 50 30	0
85 35 20	1
90 50 50	0

Код програми

#include <iostream>
using namespace std;

int main() {
	int n, v, l;
	cin >> n >> v >> l;
	cout << (n > v + l - 1);
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, v, l;

cin >> n >> v >> l;

cout << (n > v + l - 1);

return 0;

}

Решение

Так як серед $v$ дітей точно знайдеться Валя, то нам необхідно, щоб $n — v + 1$ було додатним. Іншими словами, дітей було більше, ніж достатня для Валь їх кількість. Але так як Валею може бути ще й дівчинка, необхідно, щоб ця різниця була більшою, ніж $l$. Таким чином, завжди знайдеться Валя з інших $v$ дітей, хоча б один з яких не увійшов в $l$. Звідси і формула: $n>v+ l-1$ або $n> = l + v$.

e-olymp

ideone

Related Images:

e-olymp 8522. Делимость

17/10/2018 by Андрей Зиновьев

Задача

Заданы два натуральных числа $a$ и $b$. Проверьте, делится ли $a$ на $b$.

Входные данные: Два натуральных числа $a$ и $b$ $(1 \le a, b \le 10^9)$

Выходные данные: Если $a$ не делится на $b$ нацело, вывести в одной строке частное и остаток от деления $a$ на $b$. Иначе вывести "Divisible".

Тесты

$a$	$b$	Вывод программы
15	3	Divisible
12	7	1 5
15	23	0 15
1000000000	889879	1123 665883

Continue reading →

Related Images:

e-olymp 8372. Составить треугольник

28/09/2018 by Алина Гук

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

Задача

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

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

Три натуральных числа $a, b, c (1 ≤ a, b, c ≤ 1000)$ — длины трех отрезков.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 6 7	YES
2	3 7 4	NO
3	16 24 32	YES
4	54 1 100	NO
5	1 1 1	YES

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

#include <iostream>
using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  cout << (a < b + c && b < a + c && c < a + b ? "YES" : "NO");
  return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, c;

cin >> a >> b >> c;

cout << (a < b + c && b < a + c && c < a + b ? "YES" : "NO");

return 0;

}

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

#include <iostream>
using namespace std;
 
int main() {
  int a, b, c;
  cin >> a >> b >> c;
  bool condition = (a < b + c && b < a + c && c < a + b); 
  cout  << (char)(condition * 'Y' + !condition * 'N')
        << (char)(condition * 'E' + !condition * 'O')
        << (char)(condition * 'S' + !condition * ' ');
  return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, c;

cin >> a >> b >> c;

bool condition = (a < b + c && b < a + c && c < a + b);

cout << (char)(condition * 'Y' + !condition * 'N')

<< (char)(condition * 'E' + !condition * 'O')

<< (char)(condition * 'S' + !condition * ' ');

return 0;

}

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

Пусть $a, b, c$ – длины трех отрезков. Из них можно составить невырожденный треугольник, если длина каждых двух отрезков больше длины третьего (это условие известно как неравенство треугольника): | $b$ | < | $a$ | + | $c$ | \begin{cases} b + c > a\\a + c > b\\a + b > c\end{cases}

Ссылки

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

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

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

Related Images:

e-olymp 3867. Ленивый Мишка

23/09/2018 by Иван Киреев

Задача. Ленивый Мишка

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

На мытье посуды уйдет [latex]t_1[/latex] секунд
Пропылесосить квартиру можно за [latex]t_2[/latex] секунд
Процесс игры с Маринкой займет [latex]t_3[/latex] секунд

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

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

Три целых числа [latex]t_1[/latex], [latex]t_2[/latex], [latex]t_3[/latex] ([latex]1 ≤ t_1, t_2, t_3 ≤ 1000[/latex]).

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

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

Тесты

№	Ввод	Вывод
1	1 7 2	1
2	100 45 1	1
3	66 9 888	9
4	5 800 4	4
5	25 46 25	25
6	13 10 12	10
7	999 995 1000	995

Решение 1

Мишка выбирает мамино поручение, что занимает наименьшее количество времени. Нам дано время за которое Мишка выполнит данные поручения. Найдём из них наименьшее и выведем на экран. Воспользуемся функцией int min (int, int); из библиотеки cmath.

Код 1

#include <iostream>
#include <cmath>

using namespace std;

int main ()
{
    short t1, t2, t3;
    cin >> t1 >> t2 >> t3;
    cout << min (min (t1, t2), t3); //Находим минимум 3х переменных и выводим.
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main ()

{

short t1, t2, t3;

cin >> t1 >> t2 >> t3;

cout << min (min (t1, t2), t3); //Находим минимум 3х переменных и выводим.

return 0;

}

Решение 2

Для нахождения минимума трёх чисел заведём переменную min и воспользуемся логическим ветвлением.

Код 2

#include <iostream>

using namespace std;

int main ()
{
    short t1, t2, t3, min;
    cin >> t1 >> t2 >> t3;
    min = t1; //Переменная отвечающая за минимальное значение.
    if (t2 < min) min = t2;
    if (t3 < min) min = t3;
    cout << min;
    return 0;
}

#include <iostream>

using namespace std;

int main ()

{

short t1, t2, t3, min;

cin >> t1 >> t2 >> t3;

min = t1; //Переменная отвечающая за минимальное значение.

if (t2 < min) min = t2;

if (t3 < min) min = t3;

cout << min;

return 0;

}

Ссылки

Первое решение

Второе решение

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

Компиляция первого решения

Компиляция второго решения

Related Images:

e-olymp 76. Новый шкаф

15/02/2018 by Томас Пасенченко

Задача

Заданы размеры прямоугольной двери [latex]a[/latex], [latex]b[/latex] и размеры шкафа, который имеет форму прямоугольного параллелепипеда [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Можно ли пронести шкаф сквозь дверь, если проносить его разрешается так, чтобы каждое ребро шкафа было параллельно или перпендикулярно стороне двери.

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

Пять действительных чисел [latex]a[/latex], [latex]b[/latex], [latex]x[/latex], [latex]y[/latex], [latex]z[/latex] ( [latex] 0\;\lt\;a,\;b,\;x,\;y,\;z\;\lt\;10[/latex] ).

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

Вывести [latex]1[/latex], если шкаф можно свободно пронести сквозь дверь и [latex]0[/latex] в противоположном случае.

Тесты

Входные данные	Выходные данные
[latex]5\;7\;4\;6\;8[/latex]	[latex]1[/latex]
[latex]1\;4\;2\;3\;6[/latex]	[latex]0[/latex]
[latex]2.9\;6.7\;5.1\;3.7\;1.0[/latex]	[latex]1[/latex]
[latex]4\;6\;6\;4\;3[/latex]	[latex]1[/latex]
[latex]1.5\;8\;9.9\;2\;7.5[/latex]	[latex]0[/latex]
[latex]2\;2\;2\;2\;2[/latex]	[latex]0[/latex]
[latex]2\;3\;7\;8\;8[/latex]	[latex]0[/latex]
[latex]5\;6\;2\;4\;3.5[/latex]	[latex]1[/latex]

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

#include <iostream>
using namespace std;
 
int main() {
    // Новый шкаф
    double a, b, x, y, z;
    cin >> a >> b >> x >> y >> z;
    if ((x < a && y < b) || (y < a && x < b) || (y < a && z < b) || 
    (z < a && y < b) || (x < a && z < b) || (z < a && x < b)) {
        cout << 1;
    } else {
        cout << 0;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

// Новый шкаф

double a, b, x, y, z;

cin >> a >> b >> x >> y >> z;

if ((x < a && y < b) || (y < a && x < b) || (y < a && z < b) ||

(z < a && y < b) || (x < a && z < b) || (z < a && x < b)) {

cout << 1;

} else {

cout << 0;

}

return 0;

}

Решение

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

Имеем шесть возможных вариантов ширины и высоты грани шкафа — [latex](x,y)[/latex], [latex](y,x)[/latex], [latex](y,z)[/latex], [latex](z,y)[/latex], [latex](x,z)[/latex], [latex](z,x)[/latex]

Сравнивая их с размерами двери определяем, можно ли пронести шкаф сквозь дверь.

Ссылки

Условия задачи на e-olymp
Код задачи на ideone

Related Images:

e-olymp 12. Поврежденная картина

13/01/2018 by Андрей Святозар Чернецкий

Задача

Римская цифра [latex]I[/latex], стоявшая на полу комнаты в точке с координатами [latex]X_0[/latex], [latex]Y_0[/latex], [latex]0[/latex] не выдержала отношения к решению задачи «Римские цифры» и упала на пол. Поскольку нижний конец был прикреплен шарнирно, то он остался на месте, а верхний оказался в точке с координатами [latex]X_1[/latex], [latex]Y_1[/latex], [latex]0[/latex]. В комнате стояла строго вертикально бумажная картина. Зная координаты концов нижнего основания [latex]X_2[/latex], [latex]Y_2[/latex], [latex]0[/latex] и [latex]X_3[/latex], [latex]Y_3[/latex], [latex]0[/latex] и высоту картины [latex]H[/latex] найти длину «разрыва бумаги» на картине.

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

Во входной строке записано 9 чисел [latex]X_0, Y_0, X_1, Y_1, X_2, Y_2, X_3, Y_3, H[/latex]. Все входные данные — целые числа, модуль которых не превышает [latex]10^9[/latex].

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

Программа выводит единственное число – искомую величину с точностью до [latex]0.001[/latex].

Тесты

Входные данные	Выходные данные
1 1 6 1 4 0 4 5 6	4.000
0 0 6 0 2 0 5 0 5	2.397
2 0 5 0 0 0 6 0 5	4.172
0 0 5 0 2 0 6 0 1	2.058
0 0 10 0 2 0 6 0 1	0.000

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

struct t {
    double x, y;
    t() {
        x = 0;
        y = 0;
    }
    t(double x, double y) {
        this->x = x;
        this->y = y;
    }
    t operator+(t &tt) { return t(this->x + tt.x, this->y + tt.y); }
        
    t operator-(t &tt) { return t(this->x - tt.x, this->y - tt.y); }

    bool operator==(t &p) { return ((x == p.x) && (y == p.y)); }

    bool operator!=(t &p) { return !(*this == p); }

    bool t_is_line_segment(t &t1, t &t2) {
        t t3 = *this;
        t a = t2 - t1;
        t b = t3 - t1;
        double sa = a.x * b.y - b.x * a.y;
        if (sa > 0.0) return false;
        if (sa < 0.0) return false;
        if ((a.x * b.x < 0.0) || (a.y * b.y < 0.0)) return false;
        if (a.length() < b.length()) return false;
        if (t1 == t3) return false;
        if (t2 == t3) return false;
        return true;
    }
    double distance(const t &p) {
        double a = this->x - p.x;
        double b = this->y - p.y;
        return sqrt(a * a + b * b);
    }

    double length(void) { return sqrt(x * x + y * y); }
};

struct line {
    double a, b, c;
    line(const t &t1, const t &t2) {
    a = t1.y - t2.y;
    b = t2.x - t1.x;
    c = t1.x * t2.y - t2.x * t1.y;
    }
};

bool intersect(const line &l1, const line &l2, t &res) {
    if (l1.a * l2.b == l2.a * l1.b)
    return false;
    double g = l1.a * l2.b - l2.a * l1.b;
    res.x = -(l1.c * l2.b - l2.c * l1.b) / g;
    res.y = -(l1.a * l2.c - l2.a * l1.c) / g;
    return true;
}

int main() {

    t x0, x1, x2, x3, m; // m точка пересечения

    double h = 6, answer = 0;

    cin >> x0.x >> x0.y >> x1.x >> x1.y >> x2.x >> x2.y >> x3.x >> x3.y >> h;
    double x0x1_d = x0.distance(x1);
    if (((x3.y - x2.y) * (x0.x - x1.x) - (x3.x - x2.x) * (x0.y - x1.y)) == 0) {
        if (x0.t_is_line_segment(x2, x3)) {
            if (x1.t_is_line_segment(x2, x3)) {
                if (x0x1_d <= h) {
                    answer = M_PI * x0x1_d/2;
                } else {
                    answer = x0x1_d * asin(h / x0x1_d);
                }
            } else {
                if (x2.t_is_line_segment(x1, x3)) { 
                                            if (x0x1_d <= h) answer = x0x1_d * asin(x0.distance(x2) / x0x1_d);
                                            else if (x0x1_d * x0x1_d <= h * h + x0.distance(x2) * x0.distance(x2)){
                                                        answer = x0x1_d * (asin (h / x0x1_d) - acos(x0.distance(x2) / x0x1_d));
                                            }
                                } else {
                                            if (x0x1_d <= h) answer = x0x1_d * asin(x0.distance(x3) / x0x1_d);
                                            else if (x0x1_d * x0x1_d <= h * h + x0.distance(x3) * x0.distance(x3)){
                                                        answer = x0x1_d * (asin (h / x0x1_d) - acos(x0.distance(x3) / x0x1_d));
                                            }
                }
            }
        } else {
            double a;
            if (x1.t_is_line_segment(x2, x3)) {
                a = min(x0.distance(x2), x0.distance(x3));
                if (x0x1_d < sqrt(a * a + h * h)) {
                    answer = x0x1_d * acos(a / x0x1_d);
                } else {
                    answer = x0x1_d * asin(a / x0x1_d);
                }
            } else {
                a = max(x0.distance(x2), x0.distance(x3));
                if (x0x1_d < sqrt(a * a + h * h)) {
                    answer = x0x1_d * (asin(h / x0x1_d) - acos(a / x0x1_d));
                }
            }
        }
    } else {
        line l10(x0, x1), l23(x2, x3);
        if (intersect(l10, l23, m)) {
            if (m.t_is_line_segment(x2, x3)) {
                double x0m_d = m.distance(x0);
                answer = sqrt(x0x1_d * x0x1_d - x0m_d * x0m_d);
                if (answer > h) answer = h;
            }
        }
    }
    cout << fixed << setprecision(3) << answer << endl;
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

#include <cmath>

#include <iomanip>

#include <iostream>

using namespace std;

struct t {

double x, y;

t() {

x = 0;

y = 0;

}

t(double x, double y) {

this->x = x;

this->y = y;

}

t operator+(t &tt) { return t(this->x + tt.x, this->y + tt.y); }

t operator-(t &tt) { return t(this->x - tt.x, this->y - tt.y); }

bool operator==(t &p) { return ((x == p.x) && (y == p.y)); }

bool operator!=(t &p) { return !(*this == p); }

bool t_is_line_segment(t &t1, t &t2) {

t t3 = *this;

t a = t2 - t1;

t b = t3 - t1;

double sa = a.x * b.y - b.x * a.y;

if (sa > 0.0) return false;

if (sa < 0.0) return false;

if ((a.x * b.x < 0.0) || (a.y * b.y < 0.0)) return false;

if (a.length() < b.length()) return false;

if (t1 == t3) return false;

if (t2 == t3) return false;

return true;

}

double distance(const t &p) {

double a = this->x - p.x;

double b = this->y - p.y;

return sqrt(a * a + b * b);

}

double length(void) { return sqrt(x * x + y * y); }

};

struct line {

double a, b, c;

line(const t &t1, const t &t2) {

a = t1.y - t2.y;

b = t2.x - t1.x;

c = t1.x * t2.y - t2.x * t1.y;

}

};

bool intersect(const line &l1, const line &l2, t &res) {

if (l1.a * l2.b == l2.a * l1.b)

return false;

double g = l1.a * l2.b - l2.a * l1.b;

res.x = -(l1.c * l2.b - l2.c * l1.b) / g;

res.y = -(l1.a * l2.c - l2.a * l1.c) / g;

return true;

}

int main() {

t x0, x1, x2, x3, m; // m точка пересечения

double h = 6, answer = 0;

cin >> x0.x >> x0.y >> x1.x >> x1.y >> x2.x >> x2.y >> x3.x >> x3.y >> h;

double x0x1_d = x0.distance(x1);

if (((x3.y - x2.y) * (x0.x - x1.x) - (x3.x - x2.x) * (x0.y - x1.y)) == 0) {

if (x0.t_is_line_segment(x2, x3)) {

if (x1.t_is_line_segment(x2, x3)) {

if (x0x1_d <= h) {

answer = M_PI * x0x1_d/2;

} else {

answer = x0x1_d * asin(h / x0x1_d);

}

} else {

if (x2.t_is_line_segment(x1, x3)) {

if (x0x1_d <= h) answer = x0x1_d * asin(x0.distance(x2) / x0x1_d);

else if (x0x1_d * x0x1_d <= h * h + x0.distance(x2) * x0.distance(x2)){

answer = x0x1_d * (asin (h / x0x1_d) - acos(x0.distance(x2) / x0x1_d));

}

} else {

if (x0x1_d <= h) answer = x0x1_d * asin(x0.distance(x3) / x0x1_d);

else if (x0x1_d * x0x1_d <= h * h + x0.distance(x3) * x0.distance(x3)){

answer = x0x1_d * (asin (h / x0x1_d) - acos(x0.distance(x3) / x0x1_d));

}

} else {

double a;

if (x1.t_is_line_segment(x2, x3)) {

a = min(x0.distance(x2), x0.distance(x3));

if (x0x1_d < sqrt(a * a + h * h)) {

answer = x0x1_d * acos(a / x0x1_d);

} else {

answer = x0x1_d * asin(a / x0x1_d);

}

} else {

a = max(x0.distance(x2), x0.distance(x3));

if (x0x1_d < sqrt(a * a + h * h)) {

answer = x0x1_d * (asin(h / x0x1_d) - acos(a / x0x1_d));

}

} else {

line l10(x0, x1), l23(x2, x3);

if (intersect(l10, l23, m)) {

if (m.t_is_line_segment(x2, x3)) {

double x0m_d = m.distance(x0);

answer = sqrt(x0x1_d * x0x1_d - x0m_d * x0m_d);

if (answer > h) answer = h;

}

cout << fixed << setprecision(3) << answer << endl;

return 0;

}

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

Эта задача интересна тем, что для ее решения необходимо смоделировать большое количество разнообразных взаиморасположений картины и буквы. Далее будут использоваться следующие обозначения: [latex]X_0[/latex]- основание буквы, [latex]X_1[/latex] — ее вершины, [latex]X_2[/latex] и [latex]X_3[/latex] — координаты основания картины, [latex]H[/latex] — высота картины.

1. [latex]X_0 X_1[/latex] и [latex]X_2 X_3[/latex] лежат на одной прямой

1.1. [latex]X_0[/latex] принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.1.1. [latex]X_1[/latex]принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.1.1.1 [latex]X_0[/latex][latex]X_1[/latex] не превышает [latex]H[/latex]

В таком случае искомая величина — дуга [latex]O X1[/latex], равная [latex]\frac{1}{4} [/latex] длины окружности с радиусом, равным высоте буквы: [latex]O[/latex][latex]X_1[/latex] = [latex]\frac{П\times X_0 X_1}{2} [/latex]

1.1.1.2 [latex]X_0[/latex][latex]X_1[/latex] больше, чем [latex]H[/latex]

в таком случае нам необходимо найти дугу [latex]NX_1[/latex],для этого умножив радиус на величину центрального угла: [latex]NX_1[/latex] =[latex]X_0 X_1 \times \arcsin \frac {H}{X_0 X_1}[/latex]

1.1.2 [latex]X_1[/latex] не принадлежит [latex]X_2 X_3[/latex]

1.1.2.1.[latex]X_2[/latex] принадлежит [latex]X_0 X_1[/latex]

1.1.2.1.1. [latex]X_0 X_1[/latex] не превышает [latex]H[/latex]

В таком случае нам нужно найти дугу [latex]OM[/latex] по схожему с случаем 1.1.1.2 алгоритму: [latex]OM[/latex] = [latex]X_0 X_1 \times \arcsin \frac{X_0 X_3} {X_0 X_1} [/latex]

1.1.2.1.2. [latex]X_0[/latex][latex]X_1[/latex] больше [latex]H[/latex]

1.1.2.1.2.1. [latex]X_0 X_1 < \sqrt{X_0 X_2^2 + H^2} [/latex]

В таком случае искомая величина равна дуге [latex]MN[/latex]= [latex]X_0 X_1 \times (\arcsin \frac{H}{X_0 X_1} — \arccos \frac{X_0 X_3} {X_0 X_1}))

1.1.2.2. данный случай аналогичен предыдущему.Единственное различие заключается в том,что точки [latex]X_2[/latex] и [latex]X_3[/latex] меняются местами в формулах.

1.2 [latex]Х_0[/latex] не принадлежит [latex]X_2[/latex][latex]X_3[/latex]

1.2.1 [latex]X_1[/latex]принадлежит [latex]X_2[/latex][latex]X_3[/latex]

введем новую переменную [latex]A[/latex], равную расстоянию от [latex]X_0[/latex] до картины.

1.2.1.1 [latex]X_0 X_1[/latex] меньше, чем [latex]\sqrt{A^2 + H^2}[/latex]

В данном случае нам нужно найти дугу [latex]M X_1[/latex] = [latex]X_0 X_1 \times \arccos \frac{A}{X_0 X_1}[/latex]

1.2.1.2 [latex]X_0[/latex][latex]X_1[/latex] не меньше, чем [latex]\sqrt{A^2 + H^2}[/latex]

в этом случае нам нужно найти дугу [latex]МХ_1[/latex]= [latex]X_0 X_1 \times \arcsin \frac{A}{X_0 X_1}[/latex]

1.2.2. обе вершины цифры не принадлежат картине

Обозначим через [latex]A[/latex] расстояние от [latex]X_0[/latex] до дальней вершины картины.

1.2.2.1. [latex]X_0 X_1 < \sqrt{A^2 + H^2} [/latex]

Искомая величина — дуга [latex]MN[/latex] = [latex]X_0 X_1\times (\arcsin \frac{H}{X_0 X_1} — \arccos \frac{A}{X_0 X_1})[/latex]

2. [latex]X_0 X_1[/latex] и [latex]X_2 X_3[/latex] не лежат на одной прямой

2.1. [latex]X_0 X_1[/latex] пересекает [latex]X_2 X_3[/latex]

В этом случае длина разрыва будет равна длине отрезка [latex]MN[/latex] либо высоте картины, если она окажется меньше вышеупомянутого отрезка.

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

Ссылки

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

Related Images:

e-olimp 1610. Зайцы в клетках

27/12/2017 by Бондаренко Кирилл

Зайцы в клетках

Всем известен, так называемый, принцип Дирихле, который формулируется следующим образом:

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

В данной задаче мы рассмотрим более общий случай этого классического математического факта. Пусть имеется [latex]n[/latex] клеток и [latex]m[/latex] зайцев, которых рассадили по этим клеткам. Вам требуется расcчитать максимальное количество зайцев, которое гарантированно окажется в одной клетке.

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

В одной строке заданы два натуральных числа [latex]n[/latex] и [latex]m[/latex] [latex](1 ≤ n, m ≤ 10^9)[/latex].

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

Максимальное количество зайцев, которое гарантированно окажется в одной клетке.

Тесты

Входные данные	Выходные данные
3 50	17
5 5	1
1070 589	1
34 49	2

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

#include <iostream>
using namespace std;

int main() {
    int n, m;
    double k;
    cin >> n >> m;
    k = m / n;
    if (k >= 1)cout << (m + n - 1) / n;
    else cout << 1;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

double k;

cin >> n >> m;

k = m / n;

if (k >= 1)cout << (m + n - 1) / n;

else cout << 1;

return 0;

}

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

Пусть [latex]n[/latex] — количество клеток, и [latex]m[/latex] — количество зайцев.
Найдем отношение [latex]\frac{m}{n}[/latex]. Если это отношение больше либо равно единице то [latex]{m}\geq{n}[/latex] и мы имеем ответ. [latex]\frac{(m+n-1)}{n}[/latex] — это формула выводит ответ в целом виде, если он целый, и округляет в большую сторону, если он дробный. Иначе [latex]{m}\leq{n}[/latex] и максимальное гарантированное количество зайцев в одной клетке равно единице. Это следует из условия задачи.

Условие задачи на e-olimp
Код решения ideon

Related Images:

e-olymp 143. Точка и треугольник

26/12/2017 by Александра Филистович

Точка и треугольник

Принадлежит ли точка [latex]O[/latex] треугольнику [latex]ABC[/latex]?

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

Содержит координаты точек [latex]O, A, B, C[/latex]. Числовые значения не превышают по модулю 100.

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

Вывести 1, если точка [latex]O[/latex] принадлежит треугольнику [latex]ABC[/latex] и 0 в противоположном случае.

№	Входные данные	Выходные данные
1	2 6 -9 3 8 1 5 11	1
2	-13 10 -12 5 99 80 17 13	0
3	98 -50 -87 7 5 3 23 17	0
4	5 15 7 12 5 3 2 54	1
5	2 2 3 1 1 3 9 11	1

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

#include <iostream>
using namespace std;
 
int main() {
 double x0,x1,x2,x3,y0,y1,y2,y3;
 double z1,z2,z3;
 cin>>x0>>y0>>x1>>y1>>x2>>y2>>x3>>y3;
 z1 = (x1 - x0) * (y2 - y1) - (x2 - x1) * (y1 - y0);
 z2 = (x2 - x0) * (y3 - y2) - (x3 - x2) * (y2 - y0);
 z3 = (x3 - x0) * (y1 - y3) - (x1 - x3) * (y3 - y0);
 if ((z1>=0 && z2>=0 && z3>=0) || (z1<=0 && z2<=0 && z3<=0)) cout<<"1";
 else cout<<"0";
 return 0;
}

#include <iostream>

using namespace std;

int main() {

double x0,x1,x2,x3,y0,y1,y2,y3;

double z1,z2,z3;

cin>>x0>>y0>>x1>>y1>>x2>>y2>>x3>>y3;

z1 = (x1 - x0) * (y2 - y1) - (x2 - x1) * (y1 - y0);

z2 = (x2 - x0) * (y3 - y2) - (x3 - x2) * (y2 - y0);

z3 = (x3 - x0) * (y1 - y3) - (x1 - x3) * (y3 - y0);

if ((z1>=0 && z2>=0 && z3>=0) || (z1<=0 && z2<=0 && z3<=0)) cout<<"1";

else cout<<"0";

return 0;

}

Решение

Для того, чтобы точка [latex]M[/latex] принадлежала треугольнику, заданному точками [latex]D([/latex]$x_{1}$,$y_{1}$[latex]), [/latex] [latex]E([/latex]$x_{2}$,$y_{2}$[latex]), [/latex][latex]F([/latex]$x_{3}$,$y_{3}$[latex]), [/latex] необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше либо равно нулю или же меньше либо равно нуля. Пользуясь формулой для косого произведения, запишем произведения векторов.
[$\overline{DE}$,$\overline{MD}$]=($x_{1}$-$x_{0}$) $\cdot$ ($y_{2}$-$y_{1}$)-($x_{2}$-$x_{1}$) $\cdot$ ($y_{1}$-$y_{0}$)
[$\overline{EF}$,$\overline{ME}$]=($x_{2}$-$x_{0}$) $\cdot$ ($y_{3}$-$y_{2}$)-($x_{3}$-$x_{2}$) $\cdot$ ($y_{2}$-$y_{0}$)
[$\overline{FD}$,$\overline{MF}$]=($x_{3}$-$x_{0}$) $\cdot$ ($y_{1}$-$y_{3}$)-($x_{1}$-$x_{3}$) $\cdot$ ($y_{3}$-$y_{0}$)
Если [$\overline{DE}$,$\overline{MD}$], [$\overline{EF}$,$\overline{ME}$] и [$\overline{FD}$,$\overline{MF}$] больше либо равно нулю или же меньше либо равно нуля, то точка принадлежит треугольнику.

Ссылки

Ссылка на Ideone
Ссылка на e-olymp

Related Images:

e-olymp 72. Дорога домой

26/12/2017 by Павел Жуков

Задача

Бедный Иа

Возвращаясь домой, после захватывающей игры в гостях у Винни Пуха, ослик Иа решил немного прогуляться. Поскольку во время прогулки он все время думал о своем приближавшемся дне рождения, то не заметил, как заблудился. Известно, что ослик во время прогулки всегда передвигается по определенному алгоритму: в начале прогулки он всегда начинает движение на северо-восток, делает при этом один шаг (перемещаясь при этом в точку [latex]left langle 1,1 right rangle[/latex]), потом меняет направление и двигается на юго-восток, далее на юго-запад, на северо-запад и так далее. При каждом изменении направления ослик всегда делает на [latex]n[/latex] шагов больше, чем было сделано до изменения направления.

Когда ослик все же решил возвратится домой, то обнаружил, что зашел глубоко в лес. Надвигалась ночь и Иа захотел поскорее попасть домой. Помогите узнать, удастся ли сегодня ослику попасть домой до заката солнца, если известно, что солнце зайдет через [latex]t[/latex] часов, а скорость передвижения ослика [latex]v[/latex] шагов в час (длина шага у ослика постоянна). Известно, что движение ослик начинал из точки с координатами [latex]left langle 0,0 right rangle[/latex], а его дом расположен в точке [latex]left langle x_{h},y_{h} right rangle[/latex], и направление движения он менял [latex]k[/latex] раз.

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

В первой строке задано четыре целых числа [latex]n[/latex], [latex]k[/latex], [latex]t[/latex], [latex]v[/latex] [latex](0leq n,k,t,vleq 100)[/latex]
. Во второй строке размещено два целых числа [latex]x_{h}[/latex], [latex]y_{h}[/latex] – координаты домика ослика [latex](-10^5leq x_{h}, y_{h}leq 10^5)[/latex]
.

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

Вывести Good night Ia, если ослик успеет дойти домой до заката солнца или Poor Ia в противоположном случае.

Тесты

Входные данные	Выходные данные
[latex]1[/latex] [latex]5[/latex] [latex]3[/latex] [latex]2[/latex] [latex]5[/latex] [latex]7[/latex]	Good night Ia
[latex]5[/latex] [latex]2[/latex] [latex]3[/latex] [latex]9[/latex] [latex]15[/latex] [latex]15[/latex]	Good night Ia
[latex]4[/latex] [latex]4[/latex] [latex]3[/latex] [latex]20[/latex] [latex]105[/latex] [latex]-105[/latex]	Poor Ia
[latex]3[/latex] [latex]4[/latex] [latex]2[/latex] [latex]3[/latex] [latex]40[/latex] [latex]-20[/latex]	Good night Ia
[latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex] [latex]-24[/latex] [latex]0[/latex]	Poor Ia
[latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex] [latex]-23[/latex] [latex]0[/latex]	Good night Ia

Первый вариант кода программы

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    long int n, k, t, v, hx, hy;
    long int x = 0, y = 0;
    cin >> n >> k >> t >> v;
    cin >> hx >> hy;
    for(long int i = 0; i <= k; i++){
         if(i%4 == 0){ 
             x += 1 + n*i;
             y += 1 + n*i; 
         } else if (i%4 == 1){ 
             x += 1 + n*i;
             y -= 1 + n*i; 
         } else if(i%4 == 2){
             x -= 1 + n*i; 
             y -= 1 + n*i; 
         } else if(i%4 == 3){ 
             x -= 1 + n*i; 
             y += 1 + n*i; 
         } 
    } 
    if(t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){
        cout << "Good night Ia";
    } else {
        cout << "Poor Ia";
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

long int n, k, t, v, hx, hy;

long int x = 0, y = 0;

cin >> n >> k >> t >> v;

cin >> hx >> hy;

for(long int i = 0; i <= k; i++){

if(i%4 == 0){

x += 1 + n*i;

y += 1 + n*i;

} else if (i%4 == 1){

x += 1 + n*i;

y -= 1 + n*i;

} else if(i%4 == 2){

x -= 1 + n*i;

y -= 1 + n*i;

} else if(i%4 == 3){

x -= 1 + n*i;

y += 1 + n*i;

}

if(t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){

cout << "Good night Ia";

} else {

cout << "Poor Ia";

}

return 0;

}

Второй вариант кода программы

#include <iostream>
using namespace std;

int main() {
    long int n, k, t, v, hx, hy;
    cin >> n >> k >> t >> v >> hx >> hy;
    long int s1, s2, s3, s4;
    long int m1, m2, m3, m4;
    m1 = ((k + 1) % 4 >= 1) ? (k + 1) / 4 + 1 : (k + 1) / 4;
    m2 = ((k + 1) % 4 >= 2) ? (k + 1) / 4 + 1 : (k + 1) / 4;
    m3 = ((k + 1) % 4 >= 3) ? (k + 1) / 4 + 1 : (k + 1) / 4;
    m4 = (k + 1) / 4;
    s1 = (1 + (m1 - 1) * 2 * n) * m1;
    s2 = (1 + n + 2 * n * (m2 - 1)) * m2;
    s3 = (1 + 2 * n + 2 * n * (m3 - 1)) * m3;
    s4 = (1 + 3 * n + 2 * n * (m4 - 1)) * m4;
    long int x = s1 + s2 - s3 - s4, y = s1 - s2 - s3 + s4;
    if (t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){
        cout << "Good night Ia";
    } else {
        cout << "Poor Ia";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long int n, k, t, v, hx, hy;

cin >> n >> k >> t >> v >> hx >> hy;

long int s1, s2, s3, s4;

long int m1, m2, m3, m4;

m1 = ((k + 1) % 4 >= 1) ? (k + 1) / 4 + 1 : (k + 1) / 4;

m2 = ((k + 1) % 4 >= 2) ? (k + 1) / 4 + 1 : (k + 1) / 4;

m3 = ((k + 1) % 4 >= 3) ? (k + 1) / 4 + 1 : (k + 1) / 4;

m4 = (k + 1) / 4;

s1 = (1 + (m1 - 1) * 2 * n) * m1;

s2 = (1 + n + 2 * n * (m2 - 1)) * m2;

s3 = (1 + 2 * n + 2 * n * (m3 - 1)) * m3;

s4 = (1 + 3 * n + 2 * n * (m4 - 1)) * m4;

long int x = s1 + s2 - s3 - s4, y = s1 - s2 - s3 + s4;

if (t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){

cout << "Good night Ia";

} else {

cout << "Poor Ia";

}

return 0;

}

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

Вариант 1

Разделим решение задачи на две части: поиск местоположения Иа после прогулки и расчет пути домой.
Имеем следующую формулу вычисления вектора нахождения Иа после прогулки:
[latex]sumlimits_{i=0}^k f(i, n)[/latex], где [latex]n[/latex] — изменение количества шагов Иа в каждой итерации, [latex]k[/latex] — cколько раз он менял движение, и функции:

[latex]f(x,y) = begin{cases} left langle1 + xy, 1 + xyright rangle & textit{if } xvdots 4 = 0 \ left langle1 + xy, (-1) cdot (1 + xy)right rangle & textit{if } xvdots 4 = 1 \ left langle(-1) cdot (1 + xy), (-1) \cdot (1 + xy)right rangle & textit{if } xvdots 4 = 2 \ left langle(-1) cdot (1 + xy), 1 + xyright rangle & textit{if } xvdots 4 = 3 end{cases}[/latex]

То есть, результат функции [latex]f(x,y)[/latex] это вектор, на который передвинулся Иа в итерации номер [latex]x[/latex] с изменением шага [latex]y[/latex], а результат [latex]sumlimits_{i=0}^k f(i, n)[/latex] — это вектор [latex]left langle a,b right rangle[/latex] местоположения Иа в конце прогулки. Теперь нужно посчитать расстояние между местоположением Иа и его домом. Считаем из вектора [latex]left langle a,b right rangle[/latex] и вектора [latex]left langle x_{h},y_{h} right rangle[/latex]:

$$sqrt{(x_{h} — a)^2 + (y_{h} — b)^2}$$

И считаем максимальное расстояние, которое может пройти Иа до заката солнца. Тут нужно учесть то, что скорость в условии измеряется в шагах в час, а шаг это расстояние между [latex]left langle 0,0 right rangle[/latex] и [latex]left langle 1,1 right rangle[/latex], то есть — [latex]sqrt{2}[/latex].

$$ sqrt{2} tv$$

Итого, выводим Good night Ia, если [latex]2t^2v^2 geq (x_{h} — a)^2 + (y_{h} — b)^2[/latex] и Poor Ia в противном случае.

Вариант 2

Если рассмотреть каждое направление спирали, как элемент арифметической прогрессии, то можно следующим образом получить алгоритм решения данной задачи с вычислительной сложностью [latex]O(1)[/latex]. Используем сумму арифметической прогрессии $S = displaystylefrac{a_1 + a_m}{2}$, где $a_m = 1+(m-1)d$

Для направления на северо-восток:
$$a_1 = 1, d = 4n Rightarrow S_{1}=frac{1 + 1 +4n(m_1-1)}{2}Rightarrow S_{1} = m_1(1+2n(m_1-1)),$$
где $m_1 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=1$ иначе, $m_1=displaystylefrac{k+1}{4}$

Для направления на юго-восток:
$$a_2 = 1+n, d = 4n Rightarrow S_{2} = m_2(1+n+2n(m_2-1)),$$
где $m_2 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=2$ иначе, $m_2=displaystylefrac{k+1}{4}$

Для направления на юго-запад:
$$a_3 = 1+2n, d = 4n Rightarrow S_{3} = m_3(1+2n+2n(m_3-1)),$$
где $m_3 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=3$ иначе, $m_3=displaystylefrac{k+1}{4}$

Для направления на северо-запад:
$$a_4 = 1+3n, d = 4n Rightarrow S_{4} = m_4(1+3n+2n(m_4-1)),$$
где $m_4 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=4$ иначе, $m_4=displaystylefrac{k+1}{4}$

Тогда, для вычисления координат [latex]left langle x,y right rangle[/latex] воспользуемся следующей формулами:
$$x = S_{1} + S_{2} — S_{3} — S_{4}$$
$$y = S_{1} — S_{2} — S_{3} + S_{4}$$
Последующие вычисления эквивалентны первому варианту решения.

Ссылки

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

Related Images:

e-olymp 1210. Очень просто!!!

04/12/2017 by Вадим Гордийчук

Задача

По заданным числам [latex]n[/latex] и [latex]a[/latex] вычислить значение суммы: [latex]\sum\limits_{i=1}^{n} {i \cdot a^i}[/latex]

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

Два натуральных числа [latex]n[/latex] и [latex]a[/latex].

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

Значение суммы. Известно, что оно не больше [latex]10^{18}[/latex].

Тесты

Входные данные	Выходные данные
3 3	102
4 4	1252
9 3	250959
7 14	785923166
1009 1	509545

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

#include <iostream>
using namespace std;

int main()
{
    unsigned long long int n, a, answer;
    cin >> n >> a;
    if (a > 1)
    {
        answer = n*a;
        for(unsigned long long int i = n-1; i > 0; --i)
            answer = (answer+i)*a;
    }
    else
        answer = n*(n+1)/2;
    cout << answer;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

unsigned long long int n, a, answer;

cin >> n >> a;

if (a > 1)

{

answer = n*a;

for(unsigned long long int i = n-1; i > 0; --i)

answer = (answer+i)*a;

}

else

answer = n*(n+1)/2;

cout << answer;

return 0;

}

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        long n = in.nextInt(), a = in.nextInt(), ans;
        if (a > 1)
        {
            ans = n*a;
            for(long i = n-1; i > 0; --i)
                ans = (ans+i)*a;
        }
        else
            ans = n*(n+1)/2;
        System.out.println(ans);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

long n = in.nextInt(), a = in.nextInt(), ans;

if (a > 1)

{

ans = n*a;

for(long i = n-1; i > 0; --i)

ans = (ans+i)*a;

}

else

ans = n*(n+1)/2;

System.out.println(ans);

}

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

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

Для получения качественного решения распишем ряд подробно:
[latex]A[/latex] [latex]=[/latex] [latex]\sum\limits_{i=1}^{n} {i \cdot a^i}[/latex] [latex]=[/latex] [latex]a+2a^2+3a^3+\ldots+\left( n-1 \right) a^{n-1}+na^{n}[/latex] [latex]=[/latex] [latex]na^{n}[/latex] [latex]+[/latex] [latex]\left( n-1 \right)a^{n-1}[/latex] [latex]+[/latex] [latex]\ldots[/latex] [latex]+[/latex] [latex]3a^{3}[/latex] [latex]+[/latex] [latex]2a^2[/latex] [latex]+[/latex] [latex]a[/latex].
Очевидно, что из полученного выражения можно вынести [latex]a[/latex] за скобки. Применим данную операцию:
[latex]A[/latex] [latex]=[/latex] [latex] \left( na^{n-1}+\left( n-1 \right)a^{n-2}+\ldots+3a^{2}+2a+1\right) \cdot a[/latex]
Из полученной формулы видно, что аналогичное действие можно применить вновь, для внутреннего выражения [latex]na^{n-1}[/latex] [latex]+[/latex] [latex]\left( n-1 \right)a^{n-2}[/latex] [latex]+[/latex] [latex]\ldots[/latex] [latex]+[/latex] [latex]3a^{2}[/latex] [latex]+[/latex] [latex]2a[/latex]. Получим:
[latex]A[/latex] [latex]=[/latex] [latex] \left( \left( na^{n-2}+\left( n-1 \right)a^{n-3}+\ldots+3a+2 \right) \cdot a +1 \right) \cdot a[/latex].
После конечного количества вынесений за скобки, получим:
[latex]A[/latex] [latex]=[/latex] [latex]\left( \left( \ldots \left( \left(na+\left(n-1\right)\right) \cdot a + \left(n-2\right) \right) \ldots+2\right) \cdot a +1\right) \cdot a[/latex].

Таким образом, решение данной задачи сводится к вычислению суммы «изнутри» скобок.

Но из-за того, что в условии подано ограничение только на сумму, программа с реализованным вычислением суммы изнутри и асимптотикой [latex]O \left( n \right)[/latex] не пройдёт все тесты системы www.e-olymp.com в силу частного случая [latex]a = 1[/latex], так как значение [latex]n[/latex] может быть для него достаточно большим, ибо числа [latex]a[/latex] и [latex]n[/latex] компенсируют друг-друга по отношению к максимальному значению суммы. Но в случае [latex]a = 1[/latex] сумма данного ряда является суммой арифметической прогрессии, а именно — натурального ряда. Для вычисления этой суммы существует формула [latex]\sum\limits_{i=1}^{n} {i} = \frac{n \left( n+1 \right)}{2}[/latex]. Этот частный случай легко отсеять.

Асимптотика программы: [latex]const[/latex] при [latex]a = 1[/latex], и [latex]O \left( n \right)[/latex] иначе.

Ссылки

Related Images:

e-olymp 112. Торт

26/11/2017 by Илья Черноморец

В честь дня рождения наследника Тутти королевский повар приготовил огромный праздничный торт, который был подан на стол Трем Толстякам. Первый толстяк сам мог бы целиком его съесть за $t_1$ часов, второй — за $t_2$ часов, а третий — за $t_3$ часов.

Сколько времени потребуется толстякам, чтобы съесть весь праздничный торт вместе?

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

Единственная строка содержит три целых неотрицетельных числа $t_1$, $t_2$ и $t_3$, каждое из которых не превосходит $10000$.

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

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

TESTS

$t_1$	$t_2$	$t_3$	$t$
3	3	3	1.00
4	67	50	3.51
228.22	8	2.28	1.76
1577	157.7	15.77	14.21

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

#include<iostream>
#include<iomanip>

using namespace std;
int main(){
    double t1,t2,t3;
    cin >> t1 >> t2 >> t3;
    double t;
    t = (t1*t2*t3) / (t1*t2 + t1*t3 + t2*t3);
    if(t1*t2*t3 == 0) cout<<0;
        else cout<<fixed<<setprecision(2)<<t;
    return 0;
}

#include<iostream>

#include<iomanip>

using namespace std;

int main(){

double t1,t2,t3;

cin >> t1 >> t2 >> t3;

double t;

t = (t1*t2*t3) / (t1*t2 + t1*t3 + t2*t3);

if(t1*t2*t3 == 0) cout<<0;

else cout<<fixed<<setprecision(2)<<t;

return 0;

}

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

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

int main() {
    double t1, t2, t3;
    cin >> t1 >> t2 >> t3;
    double t = 1 / (1 / t1 + 1 / t2 + 1 / t3) ;
    cout << setprecision(2) << fixed << t;
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

double t1, t2, t3;

cin >> t1 >> t2 >> t3;

double t = 1 / (1 / t1 + 1 / t2 + 1 / t3) ;

cout << setprecision(2) << fixed << t;

return 0;

}

Решение с ветвлением

Первый толстяк ест со скоростью один торт за $t_1$ часов. Аналогично и с остальными толстяками. Тогда из торта следует вычесть те части, которые съест каждый, чтобы торта не осталось. Получается уравнение
$1-\frac{t}{t_1}-\frac{t}{t_2}-\frac{t}{t_3}=0;$
$\frac{t}{t_1}+\frac{t}{t_2}+\frac{t}{t_3}=1;$
$\frac{tt_2t_3+tt_1t_3+tt_1t_2}{t_1t_2t_3}=1;$
$t\left(t_1t_2+t_2t_3+t_1t_3\right)=t_1t_2t_3;$
$t = \frac{t_1t_2t_3}{t_1t_2+t_2t_3+t_1t_3};$
Рассматриваем случай, при котором одна из переменных равна нулю, тогда выводим ноль. В противном случае выводим значение $t$ с округлением до сотых.

Решение без ветвления

Так как по условию задачи первый толстяк съедает весь торт за $t_1$ часа, второй — за $t_2$ часа и третий — за $t_3$ часа, то их скорость поедания торта составит $\frac{1}{t_1}$, $\frac{1}{t_2}$ и $\frac{1}{t_3}$ торта в час соответсвенно. Если толстяки будут есть торт одновременно, то в час они будут съедать $\left(\frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3}\right)$ часть торта. Тогда весь торт будет съеден за $\frac{1}{\frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3}}$ часов.
Затем нужно вывести результат, округлённый до двух десятичных знаков. Для этого воспользуемся функцией setprecision() и её аргументом fixed

cout << setprecision(2) << fixed << t;

1	cout << setprecision(2) << fixed << t;

Ссылки

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

Related Images:

e-olymp 1078. Степень строки

11/05/2017 by Вадим Гордийчук

Задача

Обозначим через [latex]a \cdot b[/latex] конкатенацию строк [latex]a[/latex] и [latex]b[/latex].

Например, если [latex]a =[/latex]«abc» и [latex]b =[/latex]«def» то [latex]a \cdot b =[/latex]«abcdef».

Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:
[latex]a^{0} =[/latex]«» (пустая строка)
[latex]a^{n+1} = a \cdot a^{n}[/latex]

По заданной строке [latex]s[/latex] необходимо найти наибольшее значение [latex]n[/latex], для которого [latex]s = a^{n}[/latex] для некоторой строки [latex]a[/latex].

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

Каждый тест состоит из одной строки [latex]s[/latex], содержащей печатные (отображаемые) символы. Строка [latex]s[/latex] содержит не менее одного и не более миллиона символов.

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

Для каждой входной строки [latex]s[/latex] вывести в отдельной строке наибольшее значение [latex]n[/latex], для которого [latex]s[/latex] = [latex]a^{n}[/latex] для некоторой строки [latex]a[/latex].

Тесты

Входные данные	Выходные данные
abcabc gcdgcd gcgcgc gggggg hhhh	2 2 3 6 4
BbbbBbbbBbbb dogdogdog aaaaaaaa cstring	3 3 8 1

Код программы (c-string)

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

unsigned int cstringpow(const char *s)
{
    unsigned int answer = 1;
    const unsigned int size = strlen(s);
    for (unsigned int i = 1; i < size/2+1; ++i)
    {
        /*
        Ищем предполагаемую степень для ответа, которая
        обязательно является делителем длины строки.
        */
        if (size % i == 0)
        {
            bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна
            for (int j = 0; j < size-i; j += i)
            {
                //сравниваем блоки строки
                if (strncmp(s+j, s+j+i, i) != 0)
                {
                    not_broken = 0;
                    break;
                }
            }
            if (not_broken)
            {
                //Если предполагаемая степень строки оказалась верной, возвращаем её.
                answer = size/i;
                break;
            }
        }
    }
    return answer;
}

int main()
{
    char s[1000010]; //Выделяем память для строк
    while (cin >> s)
        cout << cstringpow(s) << endl;
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

unsigned int cstringpow(const char *s)

{

unsigned int answer = 1;

const unsigned int size = strlen(s);

for (unsigned int i = 1; i < size/2+1; ++i)

{

Ищем предполагаемую степень для ответа, которая

обязательно является делителем длины строки.

if (size % i == 0)

{

bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна

for (int j = 0; j < size-i; j += i)

{

//сравниваем блоки строки

if (strncmp(s+j, s+j+i, i) != 0)

{

not_broken = 0;

break;

}

if (not_broken)

{

//Если предполагаемая степень строки оказалась верной, возвращаем её.

answer = size/i;

break;

}

return answer;

}

int main()

{

char s[1000010]; //Выделяем память для строк

while (cin >> s)

cout << cstringpow(s) << endl;

return 0;

}

Решение задачи (c-string)

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

Для решения поставленной задачи используем функцию cstringpow, которая в качестве аргумента принимает строку, и возвращает её степень. Реализуем эту функцию следующим образом: вначале ищем делители значения переменной size (с использованием счётчика i в цикле), в которую было предварительно была сохранена длина строки, полученная функцией strlen. Числа, которые будут получатся из выражения size/i, будут предполагаемой максимальной степенью строки. Естественно, они будут находится в порядке убывания.
Найденные счётчиком делители будут представлять из себя длины подстрок, на которые можно полностью разбить данную строку. Затем, используя функцию strncmp, сравниваем каждую подстроку. В случае, если какие-то из подстрок не совпали, то предположенная максимальная степень строки не является верной, и необходимо искать следующую. Иначе (если несовпадающих подстрок не найдено, то) значение выражения size/i будет ответом на поставленную задачу. В крайнем случае, необходимое разбиение строки не будет найдено, и тогда совокупностью одинаковых подстрок будет сама строка, а следовательно её степень равна [latex]1[/latex].

Код программы (string)

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

unsigned int stringpow(const string &s)
{
    unsigned int answer = 1;
    const unsigned int size = s.size();
    for (unsigned int i = 1; i < size/2+1; ++i)
    {
        /*
        Ищем предполагаемую степень для ответа, которая
        обязательно является делителем длины строки.
        */
        if (size % i == 0)
        {
            bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна
            for (int j = 0; j < size-i; j += i)
            {
                //сравниваем блоки строки
                if (s.compare(j, i, s, j+i, i) != 0)
                {
                    not_broken = 0;
                    break;
                }
            }
            
            if (not_broken)
            {
                //Если предполагаемая степень строки оказалась верной, возвращаем её.
                answer = size/i;
                break;
            }
        }
    }
    return answer;
}

int main()
{
    string s; //Выделяем переменную класса "строка"
    while (cin >> s)
        cout << stringpow(s) << endl;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

unsigned int stringpow(const string &s)

{

unsigned int answer = 1;

const unsigned int size = s.size();

for (unsigned int i = 1; i < size/2+1; ++i)

{

Ищем предполагаемую степень для ответа, которая

обязательно является делителем длины строки.

if (size % i == 0)

{

bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна

for (int j = 0; j < size-i; j += i)

{

//сравниваем блоки строки

if (s.compare(j, i, s, j+i, i) != 0)

{

not_broken = 0;

break;

}

if (not_broken)

{

//Если предполагаемая степень строки оказалась верной, возвращаем её.

answer = size/i;

break;

}

return answer;

}

int main()

{

string s; //Выделяем переменную класса "строка"

while (cin >> s)

cout << stringpow(s) << endl;

return 0;

}

import java.util.*;
import java.io.*;

public class Main
{
    public static int stringpow(String s)
    {
        int answer = 1;
        int size = s.length();
        for(int i = 1; i < size/2+1; ++i)
        {
            /*
            Ищем предполагаемую степень для ответа, которая
            обязательно является делителем длины строки.
            */
            if (size % i == 0)
            {
                boolean not_broken = true; //предполагаем, что выбранная степень строки максимальна
                String current = s.substring(0, i);
                for(int j = 0; j < size-i; j += i)
                {
                    //сравниваем блоки строки
                    if (!(current.equals(s.substring(j+i, j+2*i))))
                    {
                        not_broken = false;
                        break;
                    }
                }
            
                if (not_broken)
                {
                    answer = size/i;
                    break;
                }
            }
        }
        return answer;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        String S; //Выделяем переменную класса "строка"
        while(in.hasNextLine())
        {
            S = in.nextLine();
            out.println(stringpow(S));
        }

        out.flush();
    }
}

import java.util.*;

import java.io.*;

public class Main

{

public static int stringpow(String s)

{

int answer = 1;

int size = s.length();

for(int i = 1; i < size/2+1; ++i)

{

Ищем предполагаемую степень для ответа, которая

обязательно является делителем длины строки.

if (size % i == 0)

{

boolean not_broken = true; //предполагаем, что выбранная степень строки максимальна

String current = s.substring(0, i);

for(int j = 0; j < size-i; j += i)

{

//сравниваем блоки строки

if (!(current.equals(s.substring(j+i, j+2*i))))

{

not_broken = false;

break;

}

if (not_broken)

{

answer = size/i;

break;

}

return answer;

}

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

String S; //Выделяем переменную класса "строка"

while(in.hasNextLine())

{

S = in.nextLine();

out.println(stringpow(S));

}

out.flush();

}

Решение задачи (string)

Решение задачи с использованием класса string аналогично. Единственное отличие — замена функций strlen и strncmp, предназначенных для работы с c-string, на эквивалентные им методы класса string size и compare.

Ссылки

Related Images:

e-olymp 3358. Чёрный ящик

05/05/2017 by Вадим Гордийчук

Задача

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

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

Первая строка содержит количество событий [latex]n[/latex] [latex]\left(1 \le n \le 2 \times 10^{5} \right)[/latex]. Каждая из следующих n строк содержит описание одного события:

[latex]+ x[/latex] — положен листок с числом [latex]x[/latex] [latex]\left(1 \le x \le 10^{6} \right)[/latex];
[latex]- x[/latex] — исчез листок с числом [latex]x[/latex] (гарантируется, что в ящике был хотя бы один листок с числом [latex]x[/latex]).

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

Вывести в точности [latex]n[/latex] строк — по одной для каждого события. Каждая строка должна содержать одно число — ответ к задаче. Если после какого-то события ящик оказался пуст, следует вывести [latex]0[/latex].

Тесты

Входные данные	Выходные данные
3 + 1 — 1 + 2	1 0 2
6 + 1 + 1000000 — 1 + 4 + 4 — 1000000	1 1 1000000 4 4 4
8 + 71 + 91 + 99 + 71 — 71 — 91 — 71 — 99	71 71 71 71 71 71 99 0

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

#include <iostream>
using namespace std;

template <class POINTER_TYPE, class TYPE> class segment_tree
{
    TYPE *SegmentTree;
    POINTER_TYPE base_capacity = 0;
    TYPE (*g)(TYPE, TYPE);
    TYPE neutral;
 
    TYPE result_on_segment_in
    (
        POINTER_TYPE v, POINTER_TYPE tl,
        POINTER_TYPE tr, POINTER_TYPE l,
        POINTER_TYPE r
    )
    {
        if (l > r) return neutral;
        else if (l == tl && r == tr) return SegmentTree[v];
        else
        {
            POINTER_TYPE tm = (tl + tr) / 2;
            return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),
            result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));
        }
    }
 
    void make_monoid_and_fill_rest(TYPE *NewTree, const POINTER_TYPE &n, TYPE f(TYPE, TYPE), const TYPE &neutr)
    {
        g = f;
        neutral = neutr;
        for(POINTER_TYPE i = base_capacity+n; i < 2*base_capacity; ++i)
        {
            NewTree[i] = neutral;
        }
        for(POINTER_TYPE i = base_capacity-1; i > 0; --i)
        {
            NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);
        }
        SegmentTree = NewTree;
    }
 
    void fix_capacity(const POINTER_TYPE &base_array_size)
    {
        for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);
    }
 
    public:
    void read_and_construct(const POINTER_TYPE amount_of_elements, TYPE preprocessing_function(const POINTER_TYPE&), TYPE f(TYPE, TYPE), const TYPE neutr)
    {
        fix_capacity(amount_of_elements);
        TYPE *NewTree = new TYPE[base_capacity*2];
        for(POINTER_TYPE i = 0; i < amount_of_elements; ++i)
        {
            NewTree[base_capacity+i] = preprocessing_function(i);
        }
        make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);
    }
 
    void assign(const POINTER_TYPE index, const TYPE new_value)
    {
        SegmentTree[base_capacity+index] = new_value;
        for (POINTER_TYPE i = (base_capacity+index)/2; i > 0; i /= 2)
        {
            SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);
        }
    }
 
    TYPE result_on_segment (POINTER_TYPE l, POINTER_TYPE r)
    {
        return result_on_segment_in(1, 0, base_capacity-1, l, r);
    }
};

struct leaf
{
    unsigned int number, amount;
    leaf()
    {
        number = 2000000;
        amount = 0;
    }

    leaf(unsigned int a)
    {
        number = a, amount = 0;
    }
};

leaf max_leafs(leaf a, leaf b)
{
    return
    (a.amount == b.amount) ?
        (a.number < b.number) ? a : b
    :
        (a.amount > b.amount) ? a : b;
}

leaf constructor(const unsigned int &i)
{
    return leaf(i);
}

int main()
{
    segment_tree <unsigned int, leaf> box;
    box.read_and_construct(1000001, constructor, max_leafs, leaf());

    unsigned int n, index;
    char operation;
    leaf tmp;

    scanf("%u\n", &n); ++n;
    while (--n)
    {
        scanf("%c %u\n", &operation, &index);
        tmp = box.result_on_segment(index, index);
        if (operation == '+') ++tmp.amount;
        else --tmp.amount;
        box.assign(index, tmp);
        printf("%u\n", (box.result_on_segment(0, 1000000)).number);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

#include <iostream>

using namespace std;

template <class POINTER_TYPE, class TYPE> class segment_tree

{

TYPE *SegmentTree;

POINTER_TYPE base_capacity = 0;

TYPE (*g)(TYPE, TYPE);

TYPE neutral;

TYPE result_on_segment_in

(

POINTER_TYPE v, POINTER_TYPE tl,

POINTER_TYPE tr, POINTER_TYPE l,

POINTER_TYPE r

)

{

if (l > r) return neutral;

else if (l == tl && r == tr) return SegmentTree[v];

else

{

POINTER_TYPE tm = (tl + tr) / 2;

return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),

result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));

}

void make_monoid_and_fill_rest(TYPE *NewTree, const POINTER_TYPE &n, TYPE f(TYPE, TYPE), const TYPE &neutr)

{

g = f;

neutral = neutr;

for(POINTER_TYPE i = base_capacity+n; i < 2*base_capacity; ++i)

{

NewTree[i] = neutral;

}

for(POINTER_TYPE i = base_capacity-1; i > 0; --i)

{

NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);

}

SegmentTree = NewTree;

}

void fix_capacity(const POINTER_TYPE &base_array_size)

{

for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);

}

public:

void read_and_construct(const POINTER_TYPE amount_of_elements, TYPE preprocessing_function(const POINTER_TYPE&), TYPE f(TYPE, TYPE), const TYPE neutr)

{

fix_capacity(amount_of_elements);

TYPE *NewTree = new TYPE[base_capacity*2];

for(POINTER_TYPE i = 0; i < amount_of_elements; ++i)

{

NewTree[base_capacity+i] = preprocessing_function(i);

}

make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);

}

void assign(const POINTER_TYPE index, const TYPE new_value)

{

SegmentTree[base_capacity+index] = new_value;

for (POINTER_TYPE i = (base_capacity+index)/2; i > 0; i /= 2)

{

SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);

}

TYPE result_on_segment (POINTER_TYPE l, POINTER_TYPE r)

{

return result_on_segment_in(1, 0, base_capacity-1, l, r);

}

};

struct leaf

{

unsigned int number, amount;

leaf()

{

number = 2000000;

amount = 0;

}

leaf(unsigned int a)

{

number = a, amount = 0;

}

};

leaf max_leafs(leaf a, leaf b)

{

return

(a.amount == b.amount) ?

(a.number < b.number) ? a : b

(a.amount > b.amount) ? a : b;

}

leaf constructor(const unsigned int &i)

{

return leaf(i);

}

int main()

{

segment_tree <unsigned int, leaf> box;

box.read_and_construct(1000001, constructor, max_leafs, leaf());

unsigned int n, index;

char operation;

leaf tmp;

scanf("%u\n", &n); ++n;

while (--n)

{

scanf("%c %u\n", &operation, &index);

tmp = box.result_on_segment(index, index);

if (operation == '+') ++tmp.amount;

else --tmp.amount;

box.assign(index, tmp);

printf("%u\n", (box.result_on_segment(0, 1000000)).number);

}

return 0;

}

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

Проанализируем задачу: так как требуется вывести число, которое встречается чаще всего на листках, находящихся в ящике после запроса удаления/добавления, а если таких чисел несколько, то вывести наименьшее, то задачу можно переформулировать следующим образом:

«Даётся последовательность (массив) объектов leaf [latex]x_{1}[/latex], [latex]x_{2}[/latex], [latex]x_{3}[/latex], [latex]\ldots[/latex], [latex]x_{999999}[/latex], [latex]x_{1000000}[/latex], представляющих из себя пару (number, amount)[latex]=x_{i}=\left(i, a_{i}\right) \in {\mathbb{N}_{0}}^{2}[/latex], где первые элементы пар [latex]i[/latex] представляет из себя число/номер листка, а вторые элементы [latex]a_{i}[/latex] — число листков с этим номером. Изначально все элементы пар [latex]a_{i}[/latex] равны нулю (так как изначально ящик пуст). Для запросов первого типа [latex]+ x[/latex] необходимо увеличивать на единицу число [latex]a_{i}[/latex] объекта, у которого номер [latex]i[/latex] равен [latex]x[/latex], а для запросов второго типа — уменьшать. Для каждого запроса необходимо вывести число [latex]j[/latex], удовлетворяющее условию [latex]j = \min\limits_{i \in \mathbb{K}}{i}[/latex], где [latex]\mathbb{K} = \{i \mid a_{i} = \max\limits_{k \in \{1, 2, \ldots, 1000000\}}{a_{k}} \}[/latex]».

Иными словами, число [latex]i[/latex] соответствует некоторому элементу [latex]x_{i} = \left(i, a_{i}\right)[/latex], который в свою очередь определяется операцией такой, что [latex]i[/latex] и [latex]a_{i}[/latex] удовлетворяют приведённым выше условиям. Очевидно, что данная операция является ассоциативной (как объединение минимума и максимума на заданных множествах), а потому для решения задачи воспользуемся универсальным деревом отрезков.

Создадим дерево отрезков box методом read_and_construct из объектов leaf. Так как нумерация листков начинается с единицы, а их число не превышает [latex]10^{6}[/latex], зададим размер базы дерева отрезков [latex]10^{6}+1[/latex], добавив неё элемент с индексом [latex]0[/latex]. Модифицируем метод read_and_construct таким образом, чтобы в функцию-препроцессор передавался номер элемента [latex]i[/latex], дабы была возможность задавать элементам [latex]x_{i}[/latex] их первоначальные значения [latex]\left(i, 0\right)[/latex]. Вышеупомянутую операцию назовём max_leafs и определим таким образом, чтобы она принимала два аргумента [latex]x_{i} = \left(i, a_{i}\right)[/latex] и [latex]x_{j} = \left(j, a_{j}\right)[/latex] и возвращала тот из них, у которого значение [latex]a[/latex] является большим, а в случае равенства этих значений — аргумент с меньшим индексом. Нейтральным элементом относительно данной операции будет, очевидно, пара [latex]\left(+\infty, 0\right)[/latex], но в силу того, что номера элементов не превышают [latex]10^6[/latex], вместо неё мы будем пользоваться парой [latex]\left(2 \times 10^{6}, 0\right)[/latex].

Далее при запросах вида [latex]+ x[/latex] будем увеличивать соответствующее значение [latex]a_{x}[/latex] пары [latex]\left(x, a_{x}\right)[/latex] на единицу, а при запросах вида [latex]- x[/latex] — уменьшать. Для обоих запросов будем выводить номер заданного листка, который удовлетворяет приведённым в задаче условиям, с использованием метода result_on_segment на всём отрезке [latex]\left[0, 10^{6}\right][/latex]. Ответом для каждого запроса будет значение number пары, которую вернёт метод.

Примечание: ситуация когда ящик становится пустым нигде не обрабатывается, но в силу того, что мы определили массив на отрезке [latex]\left[0, 10^{6}\right][/latex] вместо [latex]\left[1, 10^{6}\right][/latex] в нём всегда есть пара [latex]\left(0, 0\right)[/latex] (листки с номером [latex]0[/latex], число (значение [latex]b[/latex]) которых всегда равно [latex]0[/latex] в силу того, что листки с номером [latex]0[/latex] в ящик не добавляются). Так как определённая нами операция всегда возвращает минимальный номер листка, число которого максимально, то в случае, когда ящик пуст (т.е. значения всех [latex]a_{i} = 0, i = 0, 1, \ldots, 10^{6}[/latex]) будет выводится номер листка [latex]0[/latex]. Этот побочный эффект данного нами определения массива решает эту ситуацию и завершает решение задачи.

Ссылки

Related Images:

KM2. Радиус окружностей, удовлетворяющих условию

19/10/2016 by Вадим Гордийчук

Задача

Дана сфера радиуса [latex]1[/latex]. На ней расположены равные окружности [latex]\gamma_0[/latex], [latex]\gamma_1[/latex], [latex]\ldots[/latex], [latex]\gamma_n[/latex] радиуса [latex]r \left(n \ge 3\right)[/latex]. Окружность [latex]\gamma_0[/latex] касается всех окружностей [latex]\gamma_1[/latex], [latex]\ldots[/latex], [latex]\gamma_n[/latex]; кроме того, касаются друг друга окружности [latex]\gamma_1[/latex] и [latex]\gamma_2[/latex]; [latex]\gamma_2[/latex] и [latex]\gamma_3[/latex]; [latex]\ldots[/latex]; [latex]\gamma_n[/latex] и [latex]\gamma_1[/latex].
При каких [latex]n[/latex] это возможно? Вычислить соответствующий радиус [latex]r[/latex].

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

Количество окружностей [latex]n[/latex].

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

Радиус окружностей [latex]r[/latex].

Тесты

Входные данные ([latex]n[/latex])	Выходные данные ([latex]r[/latex])
3	0.816497
4	0.707107
5	0.525731
6	Solution does not exist.

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

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

int main() {
    unsigned int n; double s_2, r;
    cin >> n;
    if ((n < 3) || (n > 5)) cout << "Solution does not exist." << endl;
    else
    {
        s_2 = sin(M_PI/n);
        s_2 *= s_2; //Возведение синуса во вторую степень.
        r = sqrt(1 - 1/(4.0*s_2));
        cout << r << endl;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

unsigned int n; double s_2, r;

cin >> n;

if ((n < 3) || (n > 5)) cout << "Solution does not exist." << endl;

else

{

s_2 = sin(M_PI/n);

s_2 *= s_2; //Возведение синуса во вторую степень.

r = sqrt(1 - 1/(4.0*s_2));

cout << r << endl;

}

return 0;

}

import java.util.*;

public class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        
        if ((n < 3) || (n > 5)) System.out.println("Solution does not exist.");
        else
        {
            double s_2 = Math.sin(Math.PI / n);
            s_2 *= s_2;
            double r = Math.sqrt(1-1/(4.0*s_2));
            System.out.println(r);
        }
    }
}

import java.util.*;

public class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

if ((n < 3) || (n > 5)) System.out.println("Solution does not exist.");

else

{

double s_2 = Math.sin(Math.PI / n);

s_2 *= s_2;

double r = Math.sqrt(1-1/(4.0*s_2));

System.out.println(r);

}

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

Каждой окружности на сфере можно сопоставить её «центр на сфере» — конец радиуса сферы, проходящего через центр окружности (никогда не лежащий на сфере). Эту точку мы будем называть «центром» окружности в кавычках, подчёркивающих, что это не «обычный» центр (рис. 2, а).

Заметим для точности, что такого определённого «центра» нет у окружностей больших кругов сферы. Но окружности, о которых идёт речь в условии задачи, заведомо не могут иметь радиус [latex]1[/latex], потому что окружности двух больших кругов не могут друг друга касаться, — они всегда пересекают друг друга в двух диаметрально противоположных точках сферы.

Точка касания двух окружностей, расположенных на сфере (см. рис. 2, б), лежит в плоскости [latex]P[/latex], проходящей через центры окружностей и центр сферы. Действительно, обе окружности симметричны относительно плоскости [latex]P[/latex], и если бы они имели общую точку по одну сторону плоскости [latex]P[/latex], то должны были бы иметь и симметричную ей общую точку по другую сторону [latex]P[/latex], а у них всего одна общая точка. Если эти окружности имеют один и тот же радиус [latex]r[/latex], то расстояние между их «центрами» равно [latex]2r[/latex], потому что на окружности большого круга, получающейся в пересечении сферы и плоскости [latex]P[/latex] (рис. 2, в), диаметры наших окружностей (чёрные отрезки) и отрезок, соединяющий их «центры» (красный), стягивают равные дуги.

Пусть [latex]A_0[/latex], [latex]A_1[/latex], [latex]A_2[/latex], [latex]\ldots[/latex], [latex]A_n[/latex] — «центры» окружностей [latex]\gamma_0[/latex], [latex]\gamma_1[/latex], [latex]\ldots[/latex], [latex]\gamma_n[/latex], о которых идёт речь в условии задачи. Тогда [latex]A_0 A_1=A_0 A_2=\ldots=A_0 A_n=A_1 A_2=A_2 A_3=\ldots=A_n A_1=2r[/latex], другими словами, [latex]A_0 A_1 A_2 \ldots A_n[/latex] — правильная [latex]n[/latex]-угольная пирамида с вершиной [latex]A_0[/latex], у которой все боковые грани — равносторонние треугольники со сторонами равными [latex]2r[/latex]. Итак, достаточно построить пирамиду, для которой выполнены эти условия, тогда точки [latex]A_0[/latex], [latex]A_1[/latex], [latex]\ldots[/latex], [latex]A_n[/latex] будут определять окружности радиуса [latex]r[/latex], с «центрами» [latex]A_0[/latex], [latex]A_1[/latex], [latex]\ldots[/latex], [latex]A_n[/latex], которые, очевидно, удовлетворяют условию задачи.

Поскольку сумма плоских углов выпуклого [latex]n[/latex]-гранного угла с вершиной [latex]A_0[/latex] меньше [latex]360^\circ[/latex]:
[latex]n\cdot60^\circ=[/latex]∠[latex]A_1 A_0 A_2+[/latex]∠[latex]A_2 A_0 A_3+\ldots+[/latex]∠[latex]A_n A_0 A_1<360^\circ[/latex], то [latex]n<6[/latex]. Для [latex]n=3[/latex], [latex]4[/latex] и [latex]5[/latex] нетрудно построить нужные пирамиды.

Пусть [latex]O[/latex] — центр сферы. Высота пирамиды [latex]h[/latex] и длина её рёбер [latex]2r[/latex] находятся из следующих соображений: радиус [latex]K A_1[/latex] основания пирамиды — катет [latex]\bigtriangleup A_0 K A_1[/latex] и боковая сторона [latex]\bigtriangleup A_1 K A_2[/latex], где ∠[latex]A_1 K A_2=2 \pi / n[/latex] (рис. 3, а , б),
[latex]\sqrt{4 r^2-h^2 \sin \frac{\pi}{n}}=r[/latex]

Из [latex]\bigtriangleup A_0 O A_1[/latex] имеем [latex]r=\frac{h}{2r}[/latex].

Отсюда [latex]h=2 r^2[/latex], [latex]r=\sqrt{1-\frac{1}{4 \sin^2 \frac{\pi}{n}}}[/latex]

Таким образом,
при [latex]n=3[/latex]: [latex]r=\sqrt{\frac{2}{3}}[/latex] [latex]\left( \sin \frac{\pi}{3}=\frac{\sqrt{3}}{2} \right)[/latex]
при [latex]n=4[/latex]: [latex]r=\sqrt{\frac{1}{2}}[/latex] [latex]\left( \sin \frac{\pi}{4}=\frac{\sqrt{2}}{2} \right)[/latex]
при [latex]n=5[/latex]: [latex]r=\sqrt{\frac{1-\sqrt{5}}{2}}[/latex]
(формулу [latex]\sin \frac{\pi}{5}=\frac{\sqrt{10-2 \sqrt{5}}}{4}[/latex] можно вывести из рисунка 4, с помощью которого строятся правильный десятиугольник и правильный пятиугольник).

Рисунки, использованные в решении

Рисунок 2:

Рисунок 3:

Рисунок 4:

Научно-популярный журнал «Квант», 1970 год, №7, страницы 51-53

Итоги:
Выведенная во время решения формула [latex]r=\sqrt{1-\frac{1}{4 \sin^2 \frac{\pi}{n}}}[/latex] справедлива только при [latex]n=3[/latex], [latex]4[/latex], [latex]5[/latex]. В случае, если задать значения больше этих, то выражение под корнем примет отрицательное значение, а в рамках данной задачи это будет говорить об отсутствии решения. Значения же меньше будут недопустимы, что было указано в условии.
Таким образом, программа выведет сообщение об отсутствии решения, если заданные значения [latex]n[/latex] отличны от вышеупомянутых. Если же условия будут соблюдаться, то задача выведет соответствующее значение радиуса.

Ссылки

Related Images:

KM63

06/10/2016 by Курьянов Павел

Задача М63 из журнала «Квант» №1 за 1971 год, стр.39. Автор А.А. Кириллов.
Можно ли из плиток размером 1х2 сложить четырехугольник размером [latex] M\times N [/latex] так, чтоб при этом не было ни одного прямого «шва», соединяющего стороны квадрата и идущие по краям плиток.

Изображение как на рисунке не годиться так как тут есть «шов» [latex] AB [/latex].

Входные данные
Размеры четырёхугольника [latex] M [/latex] и [latex] N [/latex].

Выходные данные
Возможно ли это сделать [latex] Yes [/latex] или не возможно [latex] No [/latex].

Тесты

вводимые данные		выводимые данные
M	N	возможно \|\| не возможно
2	16	no
6	6	no
66	69	yes
16	5	yes
99	71	no
7	7	no
78	77	yes
7	8	yes

Код задачи

#include <iostream>
using namespace std;

int main() {
    long long m,n;
    cin>>m>>n;
    if ( (m>=5 && n>=5 && ((m*n)%2==0) )) {  
        if (m==6 && n==6) {
            cout<<"No";// согласно решению задачи
            return 0;
        }
        cout<<"Yes";//согласно общему решению
    }
    else{ 
        cout<<"No";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long m,n;

cin>>m>>n;

if ( (m>=5 && n>=5 && ((m*n)%2==0) )) {

if (m==6 && n==6) {

cout<<"No";// согласно решению задачи

return 0;

}

cout<<"Yes";//согласно общему решению

}

else{

cout<<"No";

}

return 0;

}

Решение
Легко доказать, что прямоугольники [latex] {2\times m}, [/latex] [latex] {3\times m}, [/latex] [latex] {4\times m} [/latex] разрезать таким образом нельзя. Если же [latex] {m\geq{5}}, [/latex] [latex] {n\geq{5}} [/latex] и [latex] mn [/latex] четно (последнее условие разумеется необходимо), то во всех случаях кроме [latex]{6\times 6}[/latex] нужное разбиение существует.
Ссылки
ideone

Related Images:

e-olymp 1077. Java против C++

27/02/2016 by Женя Максимова

Задача. Сторонники языков Java и C++ часто спорят о том, какой язык лучше для решения олимпиадных задач. Одни говорят, что в Java есть масса полезных библиотек для работы со строками, хорошо реализованы механизмы чтения и вывода данных, а так же радует встроенные возможности для реализации длинной арифметики. С другой стороны, С++ является классическим языком, скорость выполнения программ благодаря существующим компиляторам (например, Intel Compiler 10.0) гораздо выше, чем у Java.

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

В языке Java принято первое слово, входящее в название переменной записывать с маленькой латинской буквы, следующее слово идет с большой буквы (только первая буква слова большая), слова не имеют разделителей и состоят только из латинских букв. Например, правильные записи переменных в Java могут выглядеть следующим образом: javaIdentifier, longAndMnemonicIdentifier, name,nEERC.

В языке C++ для описания переменных используются только маленькие латинские символы и символ «_», который отделяет непустые слова друг от друга. Примеры: java_identifier, long_and_mnemonic_identifier, name, n_e_e_r_c.

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

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

Во входном файле задано наименование переменной длиной не более [latex]100[/latex] символов.

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

В выходной файл требуется вывести аналог имени переменной в другом языке. Т.е. если переменная представлена в формате Java, то следует перевести в формат C++ и наоборот. В том случае, когда имя переменной не соответствует ни одному из вышеописанных языков, следует вывести «Error!«.

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

Тесты

Test	Input	Output
1	java_word	javaWord
2	cppWorD	cpp_wor_d
3	simpleword	simpleword
4	two__underscores	Error!
5	_underscore_in_the_beginning	Error!
6	underscore_in_the_end_	Error!
7	UppercaseInTheBeginning	Error!
8	mixed_Style	Error!

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

#include <iostream>
#include <cstring>
using namespace std;
const int START = 0; //start state
const int CONTINUE = 1; //common prefix identifier state
const int JAVAWORD = 2; //2-4 intermediate states
const int CPPWORD = 3;
const int CPPDEL = 4; //CPP-delimeter
const int JAVA = 5; //5-10 final states
const int CPP = 6;
const int UNIVERSAL = 7;
const int JAVAERR = 8; //Error in JAVA
const int CPPERR = 9; //Error in CPP
const int ERROR = 10;
char var[101];
char result[203] = {'\0'}; //fill the resulting string with zero code characters
int reslen = 0; //the length of the resulting string
int state;
bool is_small(char c) //supporting function
{
  return ('a'<= c && c <= 'z');
}
bool is_big(char c) //supporting function
{
  return ('A'<= c && c <= 'Z');
}
bool is_underscore(char c) //supporting function
{
  return (c == '_');
}
int selection_of_style(char * var, size_t len) //determines preliminary type of string
{
  char c=var[0];
  state = START;
  if(is_small(c))
    {
      state = CONTINUE;
    }
  if(is_big(c))
    {
      state = ERROR;
      return state;
    }
  if(is_underscore(c))
    {
      state = ERROR;
      return state;
    }
  for (int i=1; i<len; i++)
    {
      c=var[i];
      if(is_small(c)) state = state;
      if(is_big(c))
        {
          state = JAVAWORD;
          return state;
        }
      if(is_underscore(c))
        {
          state = CPPWORD;
          return state;
        }
    }
  //if(state == CONTINUE)
  //in the end os the word we are still in the state CONTINUE
  state = UNIVERSAL;
  return state;
}
int is_java(char * var, size_t len)//check if the word is a correct java variable
{
  for (int i=0; i<len; i++)
    {
      char c = var[i];
      if(is_small(c))
        {
          state = state;
        }
      if(is_big(c))
        {
          state = state;
        }
      if(is_underscore(c))
        {
          state = JAVAERR;
          return state;
        }
    }
  if(state == JAVAWORD)
    {
      state = JAVA;
    }
  return state;
}
int is_cpp(char * var, size_t len) //check if the word is a correct cpp variable
{
  for (int i=0; i<len; i++)
    {
      char c = var[i];
      if(is_small(c))
        {
          if(state == CPPDEL)
            {
              state = CPPWORD;
            }
          else
            state = state;
        }
      if(is_big(c))
        {
          state = JAVAERR;
          return state;
        }

      if(is_underscore(c))
        {
          if(state == CPPDEL)
            {
              state = CPPERR;
              return state;
            }
          state = CPPDEL;
        }
    }
  if(state == CPPWORD)
    {
      state = CPP;
    }
  if(state == CPPDEL) //underscore in the end is an error too
    {
      state = CPPERR;
    }
  return state;
}
void java_to_cpp(char * var, size_t len) //function-translator
{
  for(int i=0; i<len; i++)
    {
      char c = var[i];
      if(is_small(c))
        {
          result[reslen++] = var[i]; //append character to resulting string
        }
      if(is_big(c))
        {
          result[reslen++] = '_';
          result[reslen++] = var[i]+32;
        }
    }
}
void cpp_to_java(char * var, size_t len) //function-translator
{
  for(int i=0; i<len; i++)
    {
      char c = var[i];
      if(is_small(c))
        {
          result[reslen++] = var[i];
        }
      if(is_underscore(c))
        {
          result[reslen++]=var[++i]-32;
        }
    }
}
int main()
{
  cin >> var;
  size_t len = strlen(var);
  state = selection_of_style(var, len);
  if(state == ERROR)
    {
      cout << "Error!" << endl;
      return 0;
    }
  if(state == JAVAWORD)
    state = is_java(var,len);
  if(state == CPPWORD)
    state = is_cpp(var,len);
  if (state == UNIVERSAL)
    {
      cout << var << endl;
      return 0;
    }
  if(state == JAVAERR)
    {
      cout << "Error!" << endl;
      return 0;
    }
  if(state == CPPERR)
    {
      cout << "Error!" << endl;
      return 0;
    }
  if(state == JAVA)
    {
      java_to_cpp(var,len);
      cout << result;
      return 0;
    }
  if(state==CPP)
    {
      cpp_to_java(var,len);
      cout << result;
      return 0;
    }
  return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

#include <iostream>

#include <cstring>

using namespace std;

const int START = 0; //start state

const int CONTINUE = 1; //common prefix identifier state

const int JAVAWORD = 2; //2-4 intermediate states

const int CPPWORD = 3;

const int CPPDEL = 4; //CPP-delimeter

const int JAVA = 5; //5-10 final states

const int CPP = 6;

const int UNIVERSAL = 7;

const int JAVAERR = 8; //Error in JAVA

const int CPPERR = 9; //Error in CPP

const int ERROR = 10;

char var[101];

char result[203] = {'\0'}; //fill the resulting string with zero code characters

int reslen = 0; //the length of the resulting string

int state;

bool is_small(char c) //supporting function

{

return ('a'<= c && c <= 'z');

}

bool is_big(char c) //supporting function

{

return ('A'<= c && c <= 'Z');

}

bool is_underscore(char c) //supporting function

{

return (c == '_');

}

int selection_of_style(char * var, size_t len) //determines preliminary type of string

{

char c=var[0];

state = START;

if(is_small(c))

{

state = CONTINUE;

}

if(is_big(c))

{

state = ERROR;

return state;

}

if(is_underscore(c))

{

state = ERROR;

return state;

}

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

{

c=var[i];

if(is_small(c)) state = state;

if(is_big(c))

{

state = JAVAWORD;

return state;

}

if(is_underscore(c))

{

state = CPPWORD;

return state;

}

//if(state == CONTINUE)

//in the end os the word we are still in the state CONTINUE

state = UNIVERSAL;

return state;

}

int is_java(char * var, size_t len)//check if the word is a correct java variable

{

for (int i=0; i<len; i++)

{

char c = var[i];

if(is_small(c))

{

state = state;

}

if(is_big(c))

{

state = state;

}

if(is_underscore(c))

{

state = JAVAERR;

return state;

}

if(state == JAVAWORD)

{

state = JAVA;

}

return state;

}

int is_cpp(char * var, size_t len) //check if the word is a correct cpp variable

{

for (int i=0; i<len; i++)

{

char c = var[i];

if(is_small(c))

{

if(state == CPPDEL)

{

state = CPPWORD;

}

else

state = state;

}

if(is_big(c))

{

state = JAVAERR;

return state;

}

if(is_underscore(c))

{

if(state == CPPDEL)

{

state = CPPERR;

return state;

}

state = CPPDEL;

}

if(state == CPPWORD)

{

state = CPP;

}

if(state == CPPDEL) //underscore in the end is an error too

{

state = CPPERR;

}

return state;

}

void java_to_cpp(char * var, size_t len) //function-translator

{

for(int i=0; i<len; i++)

{

char c = var[i];

if(is_small(c))

{

result[reslen++] = var[i]; //append character to resulting string

}

if(is_big(c))

{

result[reslen++] = '_';

result[reslen++] = var[i]+32;

}

void cpp_to_java(char * var, size_t len) //function-translator

{

for(int i=0; i<len; i++)

{

char c = var[i];

if(is_small(c))

{

result[reslen++] = var[i];

}

if(is_underscore(c))

{

result[reslen++]=var[++i]-32;

}

int main()

{

cin >> var;

size_t len = strlen(var);

state = selection_of_style(var, len);

if(state == ERROR)

{

cout << "Error!" << endl;

return 0;

}

if(state == JAVAWORD)

state = is_java(var,len);

if(state == CPPWORD)

state = is_cpp(var,len);

if (state == UNIVERSAL)

{

cout << var << endl;

return 0;

}

if(state == JAVAERR)

{

cout << "Error!" << endl;

return 0;

}

if(state == CPPERR)

{

cout << "Error!" << endl;

return 0;

}

if(state == JAVA)

{

java_to_cpp(var,len);

cout << result;

return 0;

}

if(state==CPP)

{

cpp_to_java(var,len);

cout << result;

return 0;

}

return 0;

}

Алгоритм

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

Для удобства я изобразила этот алгоритм в виде схемы:

*круговая стрелочка означает, что мы остаемся в этом же состоянии.

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

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

Отдельно следует поговорить о состоянии CPP delimeter. Оно используется для контроля количества подчеркиваний. Если в нашей предполагаемой С++ переменной встречается подчеркивание, ей сразу же присваивается данное состояние, чтобы, при наличии второго подчеркивания сразу же перевести ее в состояние Error in CPP.

Финальные состояния отмечены зеленым цветом. В них мы переходим только после окончания строки непосредственно из предыдущего состояния. Переход в состояние Universal означает, что исходная строка состоит исключительно из маленьких букв и подходит как для языка Java, так и для C++.

Определив стандарт, к которому принадлежит переменная, мы вызываем блок перевода. Результат всегда записываем в отдельную переменную. В случае Java мы снова последовательно перебираем все символы строки и заменяем каждую встретившуюся большую букву на подчеркивание и эту же букву в маленьком регистре. Размер строки в этом случае увеличивается на количество больших букв в ее исходном варианте. В случае же С++ мы удаляем каждое подчеркивание, сдвигая все последующие символы, а первый из них переводим в большой регистр. Очевидно, что размер строки в этом случае будет уменьшен на количество подчеркиваний.

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

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

Related Images:

Mif2

03/10/2015 by Настя Панько

Даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Получить [latex]max (x, y, z)[/latex].

#include <iostream>
using namespace std;
     
int main() {
    double x, y, z;
    cin >> x >> y >> z;
    double max = z;
    if ( y > max ){
    	y = max;
    }
    if ( x > max ){
    	x = max;
    }
    cout << max << endl; 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double x, y, z;

cin >> x >> y >> z;

double max = z;

if ( y > max ){

y = max;

}

if ( x > max ){

x = max;

}

cout << max << endl;

return 0;

}

Тесты

Входные даные			Выходные даные
x	y	z
3	5	9	9
23	32	53	53
73	80	90	90
97	100	110	110
220	298	393	393

Решение

Пусть даны действительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Нужно получить [latex]max(x,y,z)[/latex]. Для этого вводим [latex]x[/latex], [latex]y[/latex], [latex]z[/latex]. Предполагаем, что z хранит максимальное значение. Затем, используя оператор if, сравниваем y, x. Выводим максимальное значение.

Код программы ideone.com

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

Related Images:

Mif 17.12

01/10/2015 by Настя Филипчук

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

Принадлежит ли точка [latex] (x;y) [/latex] фигуре на рисунке?

Код

#include <iostream>
using namespace std;
int main(){
	double x,y,a;
	cin >> x >> y;
	a=x*x+y*y;
	if (((x>=0)&&(y>=0) && (a<=36))|| ((x>=0)&&(y<=0) && (y>=x-6)))
		cout << "Yes";
	else
		cout << "No";
	return 0;
}

#include <iostream>

using namespace std;

int main(){

double x,y,a;

cin >> x >> y;

a=x*x+y*y;

if (((x>=0)&&(y>=0) && (a<=36))|| ((x>=0)&&(y<=0) && (y>=x-6)))

cout << "Yes";

else

cout << "No";

return 0;

}

Тесты

Входные данные		Выходные данные
x	y
9	0	No
-5	3	No
1	2	Yes
-3	5	Yes
1	-1	Yes
4	-4	No

Решение

Сначала ищем длину отрезка ([latex] a [/latex]) от начала координат к точке [latex] (x;y) [/latex] по формуле: [latex]\sqrt{{({x}_{0}-x)}^{2}+{({y}_{0}-y)}^{2}}[/latex], где [latex]({x}_{0};{y}_{0})[/latex] — координаты начала координат.
Дальше проверяем, если [latex]a^{2}\leq 36[/latex] (т.е. точка находится в круге, т.к радиус четверти круга равен 6, а, возведя [latex]a[/latex] в квадрат, радиус также нужно возвести в квадрат) и [latex] (x;y) [/latex] находятся в первой четверти координат, то программа выводит «Yes» (можем возвести радиус ([latex] a=\sqrt{x^{2}+y^{2}} [/latex] )в квадрат,т.к. радиус не может быть отрицательным).
Также, если сумма [latex] x + y [/latex] в четвертой четверти координат не превышает 6, то точка принадлежит треугольнику и программа выводит «Yes».
В том случае, если тока не принадлежит фигуре, программа выводит «No».

Ссылки

Условие задачи;
Код программы на Ideone.com.

Related Images:

Ю2.29

30/09/2015 by Молоканов Юрий

Условие

Для заданного [latex]0 \le n \le 200[/latex], рассматриваемого как возраст человека, вывести фразу вида: «Мне 21 год», «Мне 32 года», «Мне 12 лет».

Тестирование

№	Входные данные	Выходные данные
1	0	Мне 0 лет
2	1	Мне 1 год
3	14	Мне 14 лет
4	24	Мне 24 года
5	111	Мне 111 лет
6	151	Мне 151 год
7	200	Мне 200 лет

Код

#include <iostream>
using namespace std;

int main() {
	int n;	// Переменная для возраста
	cin >> n;
	cout << "Мне " << n << (n%10>4||n%10<1||n%100/10==1?" лет":(n%10>1?" года":" год"));	// Тернарные операции для определения нужной формы слова "год"
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n; // Переменная для возраста

cin >> n;

cout << "Мне " << n << (n%10>4||n%10<1||n%100/10==1?" лет":(n%10>1?" года":" год")); // Тернарные операции для определения нужной формы слова "год"

return 0;

}

Решение

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

В первой сотне лет:

в первом десятке лет, до 5 лет употребляется слово «год»: 1 год, 2 года, 3 года, 4 года, а от 5 лет до 10 лет употребляется слово «лет»: 5 лет, …, 10 лет;

во втором десятке лет употребляется слово «лет»: 11 лет, 12 лет, …, 20 лет;

от третьего до 9-го десятка лет, в первых четырёх годах десятка употребляется слово «год»: 21 год, 22 года, 23 года, 24 года, а в остальных годах десятка употребляется слово «лет»: 25 лет, …, 29 лет, 30 лет.

В следующих сотнях лет повторяется порядок первой сотни лет.

Таким образом, форма слова зависит от того, на какие две цифры заканчивается возраст. Составим алгоритм из двух проверок:

Если число заканчивается на [latex]0[/latex] или цифру, превышающую [latex]4[/latex], или если вторая с конца цифра этого числа — [latex]1[/latex], то выводим слово «лет» и завершаем программу; иначе переходим ко второй проверке.
Если последняя цифра числа превышает [latex]1[/latex] (то есть является одной из следующих: [latex]2[/latex], [latex]3[/latex], [latex]4[/latex]), то выводим слово «года»; иначе выводим слово «год».

Наконец, реализуем вышеописанный алгоритм в виде двух вложенных одна в другую тернарных операций:

cout << "Мне " << n << (n%10>4||n%10<1||n%100/10==1?" лет":(n%10>1?" года":" год"));

1	cout << "Мне " << n << (n%10>4\|\|n%10<1\|\|n%100/10==1?" лет":(n%10>1?" года":" год"));

Ссылки

Код программы на Ideone.com;

Правила употребления слова «год».

Related Images:

Mif 16

29/09/2015 by Сплошнов Кирилл

Условие :

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

Решение :

Команда ветвления (конструкция «if {} else {}» или тернарный оператор «?» ) разделяет код программы с какого-то момента ровно на 2 независимых алгоритма (даже при отсутствии блока «else {}», так как программа продолжает выполняться в зависимости от того, сработал блок «if {}», или нет). Таким образом, если понимать под «вариантов поведения» изолированный блок кода, выполняемый при совпадении набора условий, чтобы разбить программу на [latex]n[/latex] таких независимых вариантов, нужно использовать ровно [latex]n — 1[/latex] условную операцию.

Тесты :

Входные данные	12	7	1	0
Выходные данные	11	6	0	Ошибка ввода

Код :

#include <iostream>
using namespace std;

int main() 
{
	int n;
	cin >> n;
	if (n > 0)
		cout << n - 1 << endl;
	else
		cout << "Ошибка ввода" << endl;
	return 0;
}