e-olymp 1079. Удаление букв

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

Задача

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

Найдите максимально возможную длину полученного слова.

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

Каждый тест состоит из одной строки, содержащей два заданных слова, разделенных пробелом. Длина каждого слова от $1$ до $200$ символов. Всего имеется не более $10$ тестов.

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

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

Тесты

Входные данные	Выходные данные
AAABBB ABABAB AXYAAZ CCCXCCCYCCCZCC	4 3
AAAAA BBBBB	0
ABABA BCACB	3
STRING GNIRTS	1

String

#include <iostream>
 
using namespace std;
 
int main() {
    string x, y;
    int A[2][1001];
    while (cin >> x  >> y ) 
    {
        for (int i = 0; i < 2; i++){
            for (int j = 0; j < 1001; j++){
                A[i][j] = 0;        
            }
        }
        for (int i = 0; i < x.size(); i++){
            for (int j = 0; j < y.size(); j++){
                if (x[i] == y[j]) A[i % 2][(j + 1)] = 1 + A[(i + 1) % 2][j];
                else A[i % 2][j + 1] = max(A[(i + 1) % 2][j + 1], A[i % 2][j]);
            }
        }
        cout <<  A[(x.size() + 1) % 2][y.size()] << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string x, y;

int A[2][1001];

while (cin >> x >> y )

{

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

for (int j = 0; j < 1001; j++){

A[i][j] = 0;

}

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

for (int j = 0; j < y.size(); j++){

if (x[i] == y[j]) A[i % 2][(j + 1)] = 1 + A[(i + 1) % 2][j];

else A[i % 2][j + 1] = max(A[(i + 1) % 2][j + 1], A[i % 2][j]);

}

cout << A[(x.size() + 1) % 2][y.size()] << endl;

}

return 0;

}

C-String

#include <iostream>
#include <cstring>
 
using namespace std;
 
int main() {
    string x, y;
    int A[2][1001];
    while (cin >> x  >> y ) 
    {
        for (int i = 0; i < 2; i++){
            for (int j = 0; j < 1001; j++){
                A[i][j] = 0;        
            }
        }
        for (int i = 0; i < x.length(); i++){
            for (int j = 0; j < y.length(); j++){
                if (x[i] == y[j]) A[i % 2][(j + 1)] = 1 + A[(i + 1) % 2][j];
                else A[i % 2][j + 1] = max(A[(i + 1) % 2][j + 1], A[i % 2][j]);
            }
        }
        cout <<  A[(x.length() + 1) % 2][y.length()] << endl;
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

string x, y;

int A[2][1001];

while (cin >> x >> y )

{

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

for (int j = 0; j < 1001; j++){

A[i][j] = 0;

}

for (int i = 0; i < x.length(); i++){

for (int j = 0; j < y.length(); j++){

if (x[i] == y[j]) A[i % 2][(j + 1)] = 1 + A[(i + 1) % 2][j];

else A[i % 2][j + 1] = max(A[(i + 1) % 2][j + 1], A[i % 2][j]);

}

cout << A[(x.length() + 1) % 2][y.length()] << endl;

}

return 0;

}

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

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

Ссылки

Условие задачи на сайте E-Olymp
код задачи (string) на Ideone
код задачи (c-string) на Ideone
описание расстояния Левенштейна на Wikipedia

Андрей Святозар Чернецкий

e-olymp 2671. Сапер

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

Задача

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

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

Даны числа $N$ и $M$ (целые, положительные, не превышают $32$) — количество строк и столбцов в поле соответственно, далее число $W$ (целое, неотрицательное, не больше $100$) — количество мин на поле, далее следует $W$ пар чисел, координаты мины на поле (первое число — строка, второе число — столбец).

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

Требуется вывести на экран поле. Формат вывода указан в примере.

Тесты

Входные данные	Выходные данные
3 2 2 1 1 2 2	* 2 2 * 1 1
2 2 0	0 0 0 0
10 10 5 1 1 3 3 5 5 7 7 9 9	* 1 0 0 0 0 0 0 0 0 1 2 1 1 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 1 1 2 1 1 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 1 1 2 1 1 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 1 1 2 1 1 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 1 1 1
1 1 1 1 1	*
32 32 10 1 1 2 2 4 4 4 3 3 4 5 5 27 28 30 30 22 31 32 32	* 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 * 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 4 * 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 * * 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 * 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 * 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 *

#include <iostream>
using namespace std;
 
int main(){
    int n, m, bomb, count = 0;
    cin >> n >> m >> bomb;
    char A[34][34];
    int x, y;
    for (int i = 0; i < n + 2; i++){ 
        for (int j = 0; j < m + 2; j++){ 
            A[i][j] = '0';
        }
    }
    for (int i = 0; i < bomb; i++){
        cin >> x >> y;
        A[x][y] = '*';
    }
    for (int i = 1; i < n + 1; i++){
        for (int j = 1; j < m + 1; j++){ 
            if (A[i][j] != '*'){
                if (A[i-1][j] == '*') count++;
                if (A[i-1][j-1] == '*') count++;
                if (A[i-1][j+1] == '*') count++;
                if (A[i+1][j+1] == '*') count++;
                if (A[i+1][j-1] == '*') count++;
                if (A[i+1][j] == '*') count++;
                if (A[i][j-1] == '*') count++;
                if (A[i][j+1] == '*') count++;
                cout << count;
                count = 0;
            }
            else cout << A[i][j];
            if (j != m) cout << " ";
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main(){

int n, m, bomb, count = 0;

cin >> n >> m >> bomb;

char A[34][34];

int x, y;

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

for (int j = 0; j < m + 2; j++){

A[i][j] = '0';

}

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

cin >> x >> y;

A[x][y] = '*';

}

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

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

if (A[i][j] != '*'){

if (A[i-1][j] == '*') count++;

if (A[i-1][j-1] == '*') count++;

if (A[i-1][j+1] == '*') count++;

if (A[i+1][j+1] == '*') count++;

if (A[i+1][j-1] == '*') count++;

if (A[i+1][j] == '*') count++;

if (A[i][j-1] == '*') count++;

if (A[i][j+1] == '*') count++;

cout << count;

count = 0;

}

else cout << A[i][j];

if (j != m) cout << " ";

}

cout << endl;

}

return 0;

}

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

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

Ссылки

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

код задачи на ideone

Андрей Святозар Чернецкий

e-olymp 239. Треугольники

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

Задача

На плоскости задано [latex]n[/latex] точек с целочисленными координатами. Никакие три точки не лежат на одной прямой. Определить [latex]k[/latex] — количество треугольников с вершинами в заданных точках и целочисленной площадью.

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

В первой строке содержится число [latex]n[/latex]. В последующих [latex]n[/latex] строках содержаться пары целых чисел — координаты очередной точки [latex](x_i, y_i)[/latex]. Известно, что [latex]0 < n, |x_i|,|y_i| \leq 5000 [/latex].

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

Искомое число [latex]k[/latex].

Тесты

Входные данные	Выходные данные
5 2 -1 3 0 0 4 -3 0 -2 1	6
5 0 0 2 4 6 6 10 34 -42 -48	10
4 0 0 0 1 1 0 1 1	0
8 0 0 2 2 1 1 3 3 0 1 2 1 1 0 1 2	24
5 0 0 0 1 -1 0 -1 -1 3 -3	3

#include <iostream>
using namespace std;
 
int main() {
    unsigned int n, x1, x2, x3, y1, y2, y3, A [4] = {0, 0, 0, 0};
    unsigned long long c = 0;
    cin >> n;
    for (int i = 0; i < n; i ++){
        cin >> x1 >> y1;
        if(x1 % 2 == 0 and y1 % 2 == 0) A [0] ++;
        else if(x1 % 2 == 1 and y1 % 2 == 0) A [1] ++;
        else if(x1 % 2 == 0 and y1 % 2 == 1) A [2] ++;
        else A [3] ++;
    }
    for(int i = 0; i < 4; i ++){
        for(int  j= 0; j < 4; j ++){
            if (i == j) c += A[i] * (A[i] - 1) * (A[i] - 2) / 6;
            else c += A[i] * (A[i] - 1) * A[j] / 2;
        }       
    }
    cout << c;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned int n, x1, x2, x3, y1, y2, y3, A [4] = {0, 0, 0, 0};

unsigned long long c = 0;

cin >> n;

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

cin >> x1 >> y1;

if(x1 % 2 == 0 and y1 % 2 == 0) A [0] ++;

else if(x1 % 2 == 1 and y1 % 2 == 0) A [1] ++;

else if(x1 % 2 == 0 and y1 % 2 == 1) A [2] ++;

else A [3] ++;

}

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

for(int j= 0; j < 4; j ++){

if (i == j) c += A[i] * (A[i] - 1) * (A[i] - 2) / 6;

else c += A[i] * (A[i] - 1) * A[j] / 2;

}

cout << c;

return 0;

}

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

Учитывая теорему Пика, получаем, что площадь каждого из треугольников, которые можно составить, либо равна целому числу, либо помимо целой части содержит [latex]\frac{1}{2}[/latex]. Нас интересует лишь четность псевдоскалярного(косого) произведения. Берем у всех координат остаток от деления на [latex]2[/latex]. Получаем не более [latex]4[/latex] различных точек: [latex] (0;0), (0;1), (1;0), (1;1)[/latex]. Составляем все возможные треугольники из полученных точек, и считаем те, у которых формула дает четное число, учитывая количество координат каждого типа.

Ссылки

Условие задачи на сайте E-Olymp

код задачи на Ideone

описание теоремы Пика на Wikipedia

описание псевдоскалярного произведения на Wikipedia

Андрей Святозар Чернецкий

e-olymp 1154. Кружок хорового пения

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

Задача

В некотором учебном заведении функционирует кружок хорового пения. Начало кружка всегда происходит единообразно: по сигналу руководителя кружка все [latex]N[/latex] участников становятся в круг и каждый [latex]M[/latex]-й для распевки поёт гамму.

Руководитель кружка заметил, что размять голосовые связки не всегда удаётся всем участникам кружка. По заданным [latex]N[/latex] и [latex]M[/latex] помогите ему определить, или в очередной раз в разминке примут участие все участники хора.

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

Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай расположен в отдельной строке и содержит два целых числа [latex]N[/latex] и [latex]M[/latex]. ([latex]1 ≤ N, M ≤ 103[/latex]).

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

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

Тесты

Входные данные	Выходные данные
1000 1000 1 1	NO YES
2 5 3 7 14 15 49 37	YES YES YES YES
14 16 891 6 441 9 777 111	NO NO NO NO
4 1 6 3	YES NO

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int n, m;
    while (cin >> n >> m) cout << (__gcd (n, m) == 1? "YES" : "NO") << endl;
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n, m;

while (cin >> n >> m) cout << (__gcd (n, m) == 1? "YES" : "NO") << endl;

return 0;

}

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

Пусть у нас есть [latex]N[/latex] певцов. Пронумеруем их по порядку от [latex]0[/latex] до [latex]N — 1[/latex]. Распевается каждый [latex]M[/latex]-й. И пусть НОД ([latex]M, N) = k \geq 2[/latex]. Тогда, например, [latex]k — 1[/latex]-ый певец никогда не распоется. На рисунке ниже приведен пример. [latex]6[/latex] певцов, распевается каждый [latex]2[/latex], начиная из верхнего левого угла при смене по часовой стрелке. Переливающимся кружочком обозначен поющий в данный момент певец.

Докажем, что если [latex]M[/latex] и [latex]N[/latex] взаимно просты, то все участники распоются. Для начала заметим, что при [latex]i[/latex]-ой смене (где [latex]i[/latex] некоторое натуральное число) очередь вернется к участнику, с которого распевка начиналась,то есть смена циклическая. Поскольку НОД ([latex]M, N) = 1 [/latex], то НОК ([latex]M, N) = M*N [/latex], то есть распевающий сменится [latex]N[/latex] раз для завершения цикла. Покажем, что ни один из певцов не споет более [latex]1[/latex] раза. Пусть есть некоторый [latex]k[/latex]-ый распевающий, очередь которого наступила более [latex]1[/latex] раза за время цикла. Однако, как и для первого распевающего, очередь для [latex]k[/latex] наступит через [latex]N[/latex] смен, то есть после завершения цикла. Получили опровержение. Значит каждый распоется не более [latex]1[/latex] раза. Теперь, учитывая количество смен, получим, что каждый распоется ровно [latex]1[/latex] раз. В случае, когда НОД ([latex]M, N) \geq 2 [/latex] получим, что за цикл распоется менее, чем [latex]N[/latex] участников хора.

Ссылки

Условие задачи на сайте E-Olymp

код задачи на Ideone

Андрей Святозар Чернецкий

e-olymp 338. Моя любимая, несократимая…

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

Задача

“Название задачи можно напевать на мотив марша или строевой песни…”

Сколько существует правильных несократимых дробей на промежутке [[latex]0[/latex]..[latex]1[/latex]], знаменатель которых не превышает [latex]n[/latex]?

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

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

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

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

Тесты

Входные данные	Выходные данные
1	0
10000	30397485
5	9
80	1965
37	431
5168	8119803
9973	30237929

#include <iostream>

using namespace std;

int euler_f (int n) { 
    int result = n;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            while (n % i == 0) n /= i; 
            result -= result / i; 
        } 
    }
    if (n > 1) result -= result / n; 
    return result;
}

int main() {
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 2; i <= n; ++i) {
        sum += euler_f(i);
    }
    cout << sum;
    return 0;
}

#include <iostream>

using namespace std;

int euler_f (int n) {

int result = n;

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

if (n % i == 0) {

while (n % i == 0) n /= i;

result -= result / i;

}

if (n > 1) result -= result / n;

return result;

}

int main() {

int n;

cin >> n;

int sum = 0;

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

sum += euler_f(i);

}

cout << sum;

return 0;

}

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

Для решения данной задачи вопользуемся функцией Эйлера [latex] \varphi (n)[/latex], равной количеству натуральных чисел, меньших [latex]n[/latex] и взаимно простых с ним. Очевидно, что количество правильных несократимых дробей со знаменателем [latex]n[/latex] равно [latex] \varphi (n)[/latex]. И тогда количество правильных дробей со знаменателем, не превыщающим [latex]n[/latex] равно [latex] \sum\limits_{i=2}^{n}{\varphi (n)}[/latex] (тут мы учли, что при [latex]i[/latex] = 1 знаменатель дроби равен 1 и дробь не будет правильной).

Ссылки

Условие задачи на сайте E-Olymp

код задачи на Ideone

описание функции Эйлера на Wikipedia

Андрей Святозар Чернецкий

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
Код решения

Андрей Святозар Чернецкий

e-olymp 7460. Поездка на экскурсию

14/11/2017 by Андрей Святозар Чернецкий

Задача

Ученики 10-Б класса на осенние каникулы решили поехать на экскурсию в столицу. Зная количество мальчиков [latex]n[/latex] и девочек [latex]m[/latex], определить, сколько необходимо заказать комнат в отеле, в котором имеются комнаты на [latex]k[/latex] мест каждая, при условии что мальчиков и девочек поселять вместе запрещено.

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

В одной строке записаны три числа [latex]n[/latex], [latex]m[/latex], [latex]k[/latex] ([latex]n, m, k ≤ 100[/latex]).

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

Вывести одно число — количество комнат, которое необходимо забронировать в отеле.
Continue reading →

Андрей Святозар Чернецкий

Задача

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

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

Тесты

String

C-String

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

Ссылки

Задача

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

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

Тесты

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

Ссылки

Задача

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

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

Тесты

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

Ссылки

Задача

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

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

Тесты

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

Ссылки

Задача

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

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

Тесты

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

Ссылки

Задача

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

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

Тесты

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

Ссылки

Задача

<img class="details-image alignright" src="https://i1.wp.com/cpp.mazurok.com/wp-content/uploads/2017/11/11506759-large1.jpg?resize=276%2C184" alt="" width="276" height="184" data-recalc-dims="1" />

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

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