e-olymp 972. Сортировка времени

20/06/2019 by Виктор Иванов

Задача

Отсортируйте время согласно заданному критерию.

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

Сначала задано число $n$ $\left(1 \leqslant n \leqslant 100 \right),$ а затем $n$ моментов времени. Каждый момент времени задается $3$ целыми числами — часы (от $0$ до $23$), минуты (от $0$ до $60$), и секунды (от $0$ до $60$).

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

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

Тесты

№	Входные данные	Выходные данные
1	4 10 20 30 7 30 00 23 59 59 13 30 30	7 30 0 10 20 30 13 30 30 23 59 59
2	5 12 40 45 23 56 12 7 45 34 8 23 34 2 56 45	2 56 45 7 45 34 8 23 34 12 40 45 23 56 12
3	3 23 56 45 21 45 54 6 45 23	6 45 23 21 45 54 23 56 45

Код 1

#include <iostream>
using namespace std;
int a[101], b[101], c[101], d[101];
 
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i];
        d[i] = a[i] * 3600 + b[i] * 60 + c[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (d[i] > d[j]) {
                swap(a[i], a[j]);
                swap(b[i], b[j]);
                swap(c[i], c[j]);
                swap(d[i], d[j]);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] << " " << b[i] << " " << c[i] << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int a[101], b[101], c[101], d[101];

int main() {

int n;

cin >> n;

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

cin >> a[i] >> b[i] >> c[i];

d[i] = a[i] * 3600 + b[i] * 60 + c[i];

}

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

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

if (d[i] > d[j]) {

swap(a[i], a[j]);

swap(b[i], b[j]);

swap(c[i], c[j]);

swap(d[i], d[j]);

}

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

cout << a[i] << " " << b[i] << " " << c[i] << endl;

}

return 0;

}

Код 2

#include <iostream>
using namespace std;
 
struct unsortedtime {
    int hours;
    int minutes;
    int seconds;
};
 
bool operator > (const unsortedtime &a, const unsortedtime &b) {
    bool res = false;
    if (a.hours > b.hours) res = true;
    else if (a.hours == b.hours) {
        if (a.minutes > b.minutes) res = true;
        else if (a.minutes == b.minutes) {
            if (a.seconds > b.seconds) res = true;
        }
    }
    return res;
};
 
int main() {
    int n;
    cin >> n;
    unsortedtime *a = new unsortedtime[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i].hours >> a[i].minutes >> a[i].seconds;
    }
    for (int k = 2; k <= n; k++) {
        for (int i = 0; i <= n - k; i++) {
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << a[i].hours << " " << a[i].minutes << " " << a[i].seconds << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

struct unsortedtime {

int hours;

int minutes;

int seconds;

};

bool operator > (const unsortedtime &a, const unsortedtime &b) {

bool res = false;

if (a.hours > b.hours) res = true;

else if (a.hours == b.hours) {

if (a.minutes > b.minutes) res = true;

else if (a.minutes == b.minutes) {

if (a.seconds > b.seconds) res = true;

}

return res;

};

int main() {

int n;

cin >> n;

unsortedtime *a = new unsortedtime[n];

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

cin >> a[i].hours >> a[i].minutes >> a[i].seconds;

}

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

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

if (a[i] > a[i + 1]) {

swap(a[i], a[i + 1]);

}

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

cout << a[i].hours << " " << a[i].minutes << " " << a[i].seconds << endl;

}

return 0;

}

Решение задачи (код 1)

Для решения задачи переведём в секунды каждый момент времени и введём их в массив d[i]. Далее, в этом массиве проверяем какой элемент больше if (d[i] > d[j]) и упорядочиваем эти элементы в порядке возрастания используя swap().

Решение задачи (код 2)

Для решение задачи вторым способом создадим структуру unsortedtime. Каждый элемент в этой структуре будет соответствовать часу, минуте, секунде. После чего создадим оператор > , в котором будем сравнивать моменты времени. В случае необходимости будем менять их местами, используя функцию swap(). В результате выведем с помощью цикла моменты времени, упорядоченные в порядке неубывания.

Ссылки

Условие задачи на e-olymp
Код программы (1) на ideone
Код программы (2) на ideone

Related Images:

e-olymp 8678. Birches

05/06/2019 by Виктор Иванов

Task

The State National Park $Q$ recently acquired a beautiful birch avenue consisting of $n$ trees. Each tree has a height of $H_i$.

International Classification of national parks is a list of the most beautiful nature reserves in the world. Used to rank parks such a thing as $distinctiveness$ which is understood as the number of pairs ($i$, $j$), for which the observed ratio of $H_i$ $mod$ $H_j$ = $k$, where $k$ is a special number, which is selected by the Expert Council of the international organization of national parks.

What $distinctiveness$ has national park state $Q$?

Input

The first line has two positive integers $n$ and $k$ [latex]\left(1\leqslant n\leqslant 10^5, 0\leqslant k\leqslant 10^6\right)[/latex] — the number of trees in the national park and a special number of the advisory council, respectively.

The second line has $n$ numbers $H_i$ [latex]\left(1\leqslant H_i\leqslant 10^6\right)[/latex] — the height of the trees in the park.

Output

In the single line print $Q$ national park $distinctiveness$.

Tests

№	Input	Output
1	5 1 1 2 3 4 5	8
2	6 2 2 6 7 8 10 14	8
3	15 6 1 4 5 6 9 13 15 16 19 20 2124 27 45 49	14
4	7 3 1 5 7 8 9 23 46	2
5	10 15 23 26 67 79 82 110 118 200 450 900	2

Program code

#include <iostream>
#define SIZE 1000001
using namespace std;

long long n, k, a, cnt[SIZE], i, j, x = 0;
int main() {
    cin >> n >> k;
    for (i = 0; i < n; ++i) {
        cin >> a;
        ++cnt[a];
    }
    for (i = k + 1; i < SIZE; ++i) {
        if (cnt[i] > 0) {
            for (j = k; j < SIZE; j += i) //add each time k + 1
                if (cnt[j] > 0) {
                    if (i == j) {
                        x += cnt[i] * (cnt[i] - 1);
                    }
                    else {
                        x += cnt[j] * cnt[i];
                    }
            }
        }
    }
    cout << x << endl;
}

#include <iostream>

#define SIZE 1000001

using namespace std;

long long n, k, a, cnt[SIZE], i, j, x = 0;

int main() {

cin >> n >> k;

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

cin >> a;

++cnt[a];

}

for (i = k + 1; i < SIZE; ++i) {

if (cnt[i] > 0) {

for (j = k; j < SIZE; j += i) //add each time k + 1

if (cnt[j] > 0) {

if (i == j) {

x += cnt[i] * (cnt[i] - 1);

}

else {

x += cnt[j] * cnt[i];

}

cout << x << endl;

}

Solution

To solve this problem, we will count the number of identical elements, while entering the array. Next, if $i$ and $j$ were met more than $0$ times and $i$ is not equal $j$, we add the counter x + = cnt [j] * cnt [i], and if $i$ = $j$ — x + = cnt [i] * (cnt [i] - 1).

e-olymp 6264. Энергетический магнат

01/02/2019 by Виктор Иванов

Задача

Маленький Вася играет в новую компьютерную игру — пошаговую стратегию «Энергетический магнат».

Правила игры достаточно просты:

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

Пример №1.

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

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

Первая строка содержит число [latex]n \left(1\leqslant n\leqslant 1000 \right)[/latex] — количество слотов на доске. Вторая строка содержит строку [latex]s[/latex]. [latex]i[/latex]-ый символ строки равен [latex]1[/latex], если Вы можете построить однослотовую электростанцию в [latex]i[/latex]-ом раунде, и символ [latex]2[/latex], если Вы можете построить двуслотовую электростанцию в [latex]i[/latex]-ом раунде. Количество раундов в игре не превосходит [latex]100000[/latex].

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

Вывести одно число — наибольшее количество очков, которое можно достичь.

Тесты

№	Вхлодные данные	Выходные данные
1	3 21121	10
2	2 12	2
3	2 211	4

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

#include <iostream>
using namespace std;

int main() {
    long n, c, res = 0, num = 0; //num - количество двуслотовых электростанций.
    long temp;  //temp - количество свободных слотов.
    cin >> n;
    temp = n;
    char s;
    while(cin >> s) {
        c = (s - '0');
        num += (c == 2) ? 1 : 0;
        if (temp - c < 0 && num >= 1) {
            temp += (2 - c);
            num -= 1;
        }
        else if (temp - c >= 0) {
            temp -= c;
        }
        res += (num < 1) ? (n - temp) : (n - temp - num);
    }
    cout << res;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long n, c, res = 0, num = 0; //num - количество двуслотовых электростанций.

long temp; //temp - количество свободных слотов.

cin >> n;

temp = n;

char s;

while(cin >> s) {

c = (s - '0');

num += (c == 2) ? 1 : 0;

if (temp - c < 0 && num >= 1) {

temp += (2 - c);

num -= 1;

}

else if (temp - c >= 0) {

temp -= c;

}

res += (num < 1) ? (n - temp) : (n - temp - num);

}

cout << res;

return 0;

}

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

Будем увеличивать num на 1, если встречается двуслотовая электростанция. Если нет свободных слотов [latex]temp — c\lt0[/latex] и [latex]num\geqslant1[/latex], то вместо двуслотовой ставим станцию, которая в этом ходе должна быть [latex]temp += (2 — c)[/latex] и вычитаем одно очко. В итоге смотрим, если двуслотовых электростанций нет [latex]num\gt 1[/latex], то считаем однослотовые: [latex]n — temp[/latex], а если они есть, то: [latex]n — temp — num[/latex].

Ссылки

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

Related Images:

e-olymp 1509. Раздел королевства.

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

Задача

Король страны Геометрии в заботах. У него есть три сына, которые постоянно ссорятся. Король применял разные методы примерения, но все напрасно. И это его очень беспокоило.

«А что если разделить королевство?» подумал король. Он пригласил советников и описал свой план. Король открыл карту.

Королевство имеет форму треугольника с вершинами [latex]A, B, C[/latex]. Король провел линию от [latex]B[/latex] к [latex]E[/latex] ([latex]E[/latex] — произвольная точка на отрезке [latex]AC[/latex]) и линию от [latex]C[/latex] к [latex]F [/latex]([latex]F[/latex] — произвольная точка на отрезке [latex]AB[/latex]). Пересечение [latex]BE[/latex] и [latex]CF[/latex] обозначено через [latex]X[/latex].

Теперь образовалось четыре части — [latex]a[/latex] (треугольник [latex]BFX[/latex]), [latex]b[/latex] (треугольник [latex]BCX[/latex]), [latex]c[/latex] (треугольник [latex]CEX[/latex]) и [latex]d[/latex] (четырехугольник [latex]AEXF[/latex]). Король решил отдать области[latex] a[/latex], [latex]b[/latex], [latex]c[/latex] трем сыновьям. А область [latex]d[/latex] станет новым королевством.

Вы — главный советник. Король сообщает Вам значения [latex]a, b, c[/latex]. Вам необходимо найти значение [latex]d[/latex]. Если его найти невозможно, то сообщить об этом.

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

Состоит из не более чем [latex]1000[/latex] тестов. Каждый тест содержит три неотрицательных действительных числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] (разделенных пробелом). Входные данные заканчиваются тестом у которого [latex]a = -1[/latex] и он не обрабатывается.

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

Для каждого теста вывести его номер, начиная с [latex]1[/latex]. В следующей строке вывести [latex]d[/latex] (величина области королевства после раздела) округленное до [latex]4[/latex] десятичных знаков или ‘Poor King!’ (без кавычек) если значение [latex]d[/latex] определить невозможно. Формат выходных данных показан в примере.

Тесты

№	Входные данные	Выходные данные
1	1 2 1	Set 1: 2.0000
2	2 4 2	Set 2: 4.0000
3	1 3 3	Set 3: 5.0000
4	-1 0 0

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

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

int main () {
    double a, b, c, d, d1, d2;
    int l = 0;
    while (cin >> a >> b >> c && a!= -1.0) {
        d1 = a * c / b;
        l++;
        if (b > d1) {
            d2 = (c + d1) * (a + d1) / (b - d1);
            cout << fixed << setprecision(4) << "Set" << " " << l << ':' << endl;
            cout << d1 + d2<< endl;
        }
        else cout << "Set" << " " << l << ':' << endl << "Poor King!" << endl;
    }
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main () {

double a, b, c, d, d1, d2;

int l = 0;

while (cin >> a >> b >> c && a!= -1.0) {

d1 = a * c / b;

l++;

if (b > d1) {

d2 = (c + d1) * (a + d1) / (b - d1);

cout << fixed << setprecision(4) << "Set" << " " << l << ':' << endl;

cout << d1 + d2<< endl;

}

else cout << "Set" << " " << l << ':' << endl << "Poor King!" << endl;

}

return 0;

}

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

Для решения задачи соединим точки [latex]F[/latex] и [latex]E[/latex] линией. Получили два треугольника: [latex]d1[/latex] и [latex]d2[/latex]. Искомую площадь [latex]d[/latex] будем искать как сумму площадей [latex]d1[/latex] и [latex]d2[/latex]. Треугольники [latex]BFO[/latex] и [latex]EFO[/latex] имеют общее основание [latex]FO[/latex]. Следовательно их площади [latex]d1[/latex] и [latex]a[/latex] относятся как высоты, опущенные из вершин [latex]E[/latex] и [latex]B[/latex] на прямую [latex]FO[/latex]. Аналогично треугольники [latex]BCO[/latex] и [latex]ECO[/latex] имеют общее основание [latex]OF[/latex]. Значит их площади [latex]c[/latex] и [latex]b[/latex] относятся как высоты, опущенные из вершин [latex]E[/latex] и [latex]B[/latex] на прямую [latex]CO[/latex]. То есть $\frac{d_1}{a}=\frac{c}{b}$. Отсюда $d_1=\frac{ac}{b}$. Теперь рассмотрим треугольники [latex]CAF[/latex] и [latex]CBF[/latex] с основаниями [latex]AF[/latex] и [latex]BF[/latex]. Они имеют одинаковую высоту, опущенную из вершины [latex]С[/latex] на прямую [latex]AB[/latex]. Следовательно площади этих треугольников относятся как длины сторон [latex]AF[/latex] и [latex]BF[/latex]. Аналогично треугольники [latex]EAF[/latex] и [latex]EBF[/latex] имеют основания [latex]AF[/latex] и [latex]BF[/latex]. Они имеют одинаковую высоту, опущенную из вершины [latex]E[/latex] на прямую [latex]AB[/latex]. Площади этих треугольников относятся как длины сторон [latex]AF[/latex] и [latex]BF[/latex]. Тогда $$\frac{AF}{BF}=\frac{S_{\blacktriangle} CAF}{S\blacktriangle CBF}=\frac{c+d_1+d_2}{a+b}$$. $$\frac{AF}{BF}=\frac{S\blacktriangle EAF}{S\blacktriangle EBF}=\frac{d_2}{a+d_1}$$. Следовательно $\frac{c+d_1+d_2}{a+b}=\frac{d_2}{a+d_1}$. Поскольку [latex]d1[/latex] уже найдено, то имеем равенство с одним неизвестным [latex]d2[/latex] : $$d_2=\frac{(c+d_1)(a+d_1)}{b-d_1}$$. Если [latex]b \leqslant d1[/latex], то решения не существует.

Ссылки

Условие задачи на 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".