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

Related Images:

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

Related Images:

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

Related Images:

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

Related Images:

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

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-olymp 7460. Поездка на экскурсию

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

Задача

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