e-olymp 1108. Червячные дыры

06/06/2016 by Грешилов Константин

Условие:

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

Червячные дыры являются односторонними.
Время путешествия по любому тоннелю равно нулю.
Червячная дыра имеет два конца, каждый из которых находится в звездной системе.
Звездная система в своих границах может иметь несколько концов червячных дыр.
По некоторой неизвестной причине начиная с нашей Солнечной системы всегда можно достигнуть любую другу звездную систему перемещаясь некоторой последовательностью червячных дыр (возможно, это потому что Земля является центром универсума).
Между любой парой звездных систем существует не более одной червячной дыры в любом из направлений.
Оба конца червячной дыры не могут находиться в одной звездной системе.
Каждая червячная дыра перемещает путешественника на определенное константное количество лет вперед или назад. Например, одна дыра может переместить на 15 лет в будущее, а другая на 42 года в прошлое.

Известный физик, живущий на Земле, хочет использовать червячные дыры для исследования теории Большого Взрыва. Поскольку двигатель искривления пространства еще не изобретен, невозможно напрямую путешествовать между звездными системами. Однако это можно делать при помощи червячных дыр.

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

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

Первая строка содержит количество звездных систем n (1 ≤ n ≤ 1000) и количество червячных дыр m (0 ≤ m ≤ 2000). Звездные системы пронумерованы от 0 (наша солнечная система) до n — 1. Каждая червячная дыра описывается в отдельной строке и содержит три целых числа x, y и t. Эти числа указывают на возможность передвижения из звездной системы с номером x в звездную систему с номером y, при этом время изменяется на t (-1000 ≤ t ≤ 1000) лет.

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

Cтрока содержит информацию, возможно ли в заданном множестве систем попасть в минус бесконечность во времени используя червячные дыры. Выводить следует строку «possible» или «not possible«.

Тесты:

Входные данные	Выходные данные
3 3 0 1 1000 1 2 15 2 1 -42	possible
4 4 0 1 10 1 2 20 2 3 30 3 0 -60	not possible
3 3 0 1 -100 1 2 1 2 1 0	not possible

Решение:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct canal {
    int x, y, t;
};
 
int main() {
    int n, m;
    vector <canal> canals;
    cin >> n >> m;
    canal r;
    for (int i=0; i < m; i++)
    {
        cin >> r.x >> r.y >> r.t;
        canals.push_back(r);
    }
    const int INF = 2000000;
    vector <int> distance (n);
    int x;
    for (int i = 0; i < n; i++) {
        x = -1;
        for (int j = 0; j < m; j++)
            if (distance[canals[j].y] > distance[canals[j].x] + canals[j].t) {
                distance[canals[j].y] = max (-INF, distance[canals[j].x] + canals[j].t);
                x = canals[j].y;
            }
    }
 
    if (x == -1)
        cout << "not possible" << endl;
    else {
        cout << "possible" << endl;
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

struct canal {

int x, y, t;

};

int main() {

int n, m;

vector <canal> canals;

cin >> n >> m;

canal r;

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

{

cin >> r.x >> r.y >> r.t;

canals.push_back(r);

}

const int INF = 2000000;

vector <int> distance (n);

int x;

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

x = -1;

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

if (distance[canals[j].y] > distance[canals[j].x] + canals[j].t) {

distance[canals[j].y] = max (-INF, distance[canals[j].x] + canals[j].t);

x = canals[j].y;

}

if (x == -1)

cout << "not possible" << endl;

else {

cout << "possible" << endl;

}

return 0;

}

Описание решения:

Решение данной задачи сводится к нахождению отрицательного цикла в ориентированном графе. Необходимо воспользоваться алгоритмом Форда-Беллмана. Создадим вектор на [latex]n[/latex] элементов и заполним его нулями. Алгоритм основан на том, что если в графе размерностью [latex]n[/latex] элементов нет отрицательных циклов, то после [latex]n-1[/latex] прохождения, изменения в массива кратчайших расстояний не будет. Поэтому, будем выполнять следующее [latex]n[/latex] раз:

Возьмем первое ребро из вектора [latex]canals[/latex], и проведем сравнение: если исходная длина пути конца данного ребра из исходного вектора [latex]distance[/latex] больше, чем сумма длины пути начала вектора и стоимости прохода по данному ребру [latex]canals[].t[/latex], то изменим в векторе [latex]distance[/latex] элемент с номером конца исходного ребра, и изменим индикатор изменений [latex]x[/latex], чтобы показать, что в ходе данного прохода были внесены изменения.
Переходим к следующему ребру.

Если после во время последнего прохода ни разу не была изменена переменная [latex]x[/latex], то это значит, что в графе нет циклов отрицательной длины, и тогда выводим «not possible». Иначе, выводим «possible».

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

Код решения на ideone.com.

Related Images:

e-olymp 1948. Топологическая сортировка

06/06/2016 by Грешилов Константин

Условие:
Дан ориентированный невзвешенный граф. Необходимо топологически отсортировать его вершины.

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

В первой строке содержатся количество вершин [latex]n[/latex] (1 ≤ [latex]n[/latex] ≤ 100000) и количество рёбер [latex]m[/latex] (1 ≤[latex]m[/latex] ≤ 100000) в графе. В следующих [latex]m[/latex] строках перечислены рёбра графа, каждое из которых задаётся парой чисел — номерами начальной и конечной вершины.

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

Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, то вывести -1.

Тесты:

Входные данные	Выходные данные
6 6 1 2 3 2 4 2 2 5 6 5 4 6	4 6 3 1 2 5
2 2 1 2 2 1	-1
4 5 1 2 1 3 3 4 2 4 1 4	1 3 2 4
4 5 1 2 1 3 3 4 2 4 4 1	-1

Решение:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cyclic (int v, int &cycle_st, vector <int> *graph, vector <int> &color ) { //проверка графа на цикличность
    color[v] = 1;
    for (size_t i = 0; i < graph[v].size(); ++i) {
        int to = graph[v][i];
        if (color[to] == 0) { //если в вершину не входили ни разу
            if (cyclic (to, cycle_st, graph,  color))  return true;
        }
        else if (color[to] == 1) { //если в указанную вершину ранее входили, то значит, что найден цикл
            cycle_st = to; // и меняем значение индикатора 
            return true; 
        }
    }
    color[v] = 2; //указываем, что в вершину больше ни разу входить не будем
    return false;
}
void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer) {
    used[v] = true; //указываем, что использовали данную вершину
    for (int i=0; i < graph[v].size(); i++) {
        int to = graph[v][i]; //по списку проходим по всем вершинам, к которым можно пройти от вершины v
        if (!used[to])//и если вершину не рассматривали, то применяем алгоритм поиска в глубину для неё
            dfs (to, graph, used, answer);
    }
    answer.push_back (v+1); // заносим вершину в вектор, хранящий результат
}
 
void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer) {
    for (int i = 0; i < n; i++) //указываем, что ни одна вершина не была использована
        used[i] = false;
    for (int i = 0; i < n; i++)
        if (!used[i]) //если в ходе предыдущий операций вершина не использовалась
            dfs (i, graph, used, answer); // то вызываем для неё алгоритм поиска в глубину
    reverse (answer.begin(), answer.end());
}

int main() {
    int n, m; // число вершин и ребер
    cin >> n >> m;
    int a, b;
    vector <int> graph[100001]; // граф
    vector <bool> used (n);
    vector<int> answer;
    vector<int> color (n,0); //массив, хранящий кол-во посещений для данной вершины.
    int cycle_st = -1;
    for (int i = 0; i < m; i++){
            cin >> a >> b;
            graph[a-1].push_back(b-1);
        }
    for (int i = 0; i < n; i++){
        if (cyclic(i, cycle_st, graph, color)) //проверка графа на ацикличность
            break;
    }
    if (cycle_st != -1){ 
        cout << "-1";
    }
    else{
        topological_sort(n, graph, used, answer);
        for (int i = 0; i < answer.size(); i++)
        {
            cout << answer[i] << " "; 
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

bool cyclic (int v, int &cycle_st, vector <int> *graph, vector <int> &color ) { //проверка графа на цикличность

color[v] = 1;

for (size_t i = 0; i < graph[v].size(); ++i) {

int to = graph[v][i];

if (color[to] == 0) { //если в вершину не входили ни разу

if (cyclic (to, cycle_st, graph, color)) return true;

}

else if (color[to] == 1) { //если в указанную вершину ранее входили, то значит, что найден цикл

cycle_st = to; // и меняем значение индикатора

return true;

}

color[v] = 2; //указываем, что в вершину больше ни разу входить не будем

return false;

}

void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer) {

used[v] = true; //указываем, что использовали данную вершину

for (int i=0; i < graph[v].size(); i++) {

int to = graph[v][i]; //по списку проходим по всем вершинам, к которым можно пройти от вершины v

if (!used[to])//и если вершину не рассматривали, то применяем алгоритм поиска в глубину для неё

dfs (to, graph, used, answer);

}

answer.push_back (v+1); // заносим вершину в вектор, хранящий результат

}

void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer) {

for (int i = 0; i < n; i++) //указываем, что ни одна вершина не была использована

used[i] = false;

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

if (!used[i]) //если в ходе предыдущий операций вершина не использовалась

dfs (i, graph, used, answer); // то вызываем для неё алгоритм поиска в глубину

reverse (answer.begin(), answer.end());

}

int main() {

int n, m; // число вершин и ребер

cin >> n >> m;

int a, b;

vector <int> graph[100001]; // граф

vector <bool> used (n);

vector<int> answer;

vector<int> color (n,0); //массив, хранящий кол-во посещений для данной вершины.

int cycle_st = -1;

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

cin >> a >> b;

graph[a-1].push_back(b-1);

}

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

if (cyclic(i, cycle_st, graph, color)) //проверка графа на ацикличность

break;

}

if (cycle_st != -1){

cout << "-1";

}

else{

topological_sort(n, graph, used, answer);

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

{

cout << answer[i] << " ";

}

cout << endl;

}

return 0;

}

Описание решения:

Для решения данной задачи необходимо было воспользоваться алгоритмом топологической сортировки, посредством поиcка в глубину. Чтобы применить данный алгоритм, необходимо было проверить граф на ацикличность с помощью алгоритма поиска в глубину. Это было реализовано функцией [latex]cyclic[/latex], которая проходила по всему графу в поиске цикла. Если цикл был найден, то функция меняла значение переменной [latex]cycle_st[/latex]. Далее, если цикл был найден, то программа выводить -1, иначе применяется алгоритм топологической сортировки, реализованный в двух функциях:

void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer)

20	void dfs (int v, vector <int> *graph, vector<bool> &used, vector <int> &answer)

void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer)

30	void topological_sort(int n, vector <int> *graph, vector<bool> &used, vector <int> &answer)

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

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

Код решения на ideone.com.

Related Images:

A298

25/05/2016 by Грешилов Константин

Условие взято со сборника задач С.Абрамова и др.

Задача

Даны целые числа [latex]a_1,\ldots,a_n[/latex],[latex]b_1,\ldots,b_n[/latex]. Преобразовать последовательность [latex]b_1,\ldots,b_n[/latex] по правилу: если [latex] a_i \leq 0[/latex], то [latex]b_i[/latex] увеличить в 10 раз, иначе [latex]b_i[/latex] заменить нулем [latex](i=1,\ldots,n[/latex]). Данные принимать до конца входного потока.

Тесты:

№	Входные данные	Выходные данные
1	-1 0 12 4 5 0 1 2 3 4 5 6	-1 0 12 4 5 0 10 20 0 0 0 60
2	0 2147483647	0 21474836470
3	1 2 3 4 5 6 7 8 0 0 1 2 3 4 5 6 7 8 9 10	1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 90 100

Решение:

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

int main() {
    vector <long long> a;
    long long b;
    while (cin >> b)
    {
        a.push_back(b);
    }
    for (int i = 0; i < a.size()/2; i++)
    {
        if(a[i] <= 0)
        {
            a[a.size()/2 + i] *= 10;
        }
        else
        {
            a[a.size()/2 + i] = 0;
        }
    }
    for (auto c : a)
    {
        cout << c << " ";
    }
    cout << endl;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <long long> a;

long long b;

while (cin >> b)

{

a.push_back(b);

}

for (int i = 0; i < a.size()/2; i++)

{

if(a[i] <= 0)

{

a[a.size()/2 + i] *= 10;

}

else

{

a[a.size()/2 + i] = 0;

}

for (auto c : a)

{

cout << c << " ";

}

cout << endl;

return 0;

}

Описание решения:

При решении данной задачи был использован тип данных [latex]long long[/latex], так как было необходимо охватить как можно больший диапазон значений. Заданные последовательности чисел будем хранить в одном векторе [latex]a[/latex], где последним элементов первой последовательности будем элемент под номером [latex]a.size()/2-1[/latex]. Отсюда, в цикле будем просматривать каждый элемент первой последовательности. Если данный элемент не положителен, то увеличим в 10 раз соответствующий элемент второй последовательности, иначе, присвоим ему значение нуля. Номер в векторе соответствующего элемента из второй последовательности можно найти по формуле [latex]a.size()/2+i[/latex], где [latex]i[/latex] — это номер элемента из первой последовательности. После прохода по всей первой последовательности, выведем весь вектор на экран.

Код можно запустить и опробовать здесь.

Related Images:

MLoop 8

19/05/2016 by Грешилов Константин

Условие:

Вычислите с точностью [latex]\varepsilon[/latex] значение функции [latex]f(x)=e^x[/latex]. При вычислениях допустимо использовать только арифметические операции.

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

В единственной строке указаны два числа, разделенные пробелом: аргумент функции [latex]x[/latex] и точность [latex]\varepsilon[/latex].

Тесты:

Входные данные		Выходные данные
[latex]x[/latex]	[latex]\varepsilon[/latex]	Результат
1	0.1	2.70833
1	0.001	2.71825
12	0.072	2.4155e+07

Решение:

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

int main() {
    double x, e;
    cin>>x>>e;
    double result=1;
    double component=1;
    for (int i=1; abs(component)>=e; i++)
    {
        component*=(x/i);
        result+=component;
    }
    cout<<result<<endl;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double x, e;

cin>>x>>e;

double result=1;

double component=1;

for (int i=1; abs(component)>=e; i++)

{

component*=(x/i);

result+=component;

}

cout<<result<<endl;

return 0;

}

Описание решения:

Для нахождения значения функции [latex]f(x)=e^x[/latex] (экспоненты) с точностью [latex]\varepsilon[/latex] воспользуемся формулой разложения Тейлора: [latex]f(x)=e^x=1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots =\sum_{n=0}^{x^n}, x\in \mathbb{C}[/latex]. Запишем рекуррентное соотношение для нахождения каждого последующего члена: [latex]x_{n}=x_{n-1}\cdot\frac{x}{n}[/latex].Для нахождения искомого результата, будем прибавлять к значению [latex]result[/latex] новые члены до тех пор, пока они по модулю не станут меньше, чем [latex]\varepsilon[/latex].

Ссылка на код.

Related Images:

e-olymp 2034. WERTYU

19/05/2016 by Грешилов Константин

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

Обычная ошибка при наборе состоит в том, что вы помещаете ваши руки на клавиатуру на один ряд правее верной позиции. Тогда «Q» печатается как «W«, «J» печатается как «K» и т.д. Ваша задача состоит в расшифровке сообщения, напечатанного таким образом.

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

Входные данные состоят из нескольких строк текста. Каждая строка может содержать цифры, пробелы, прописные буквы (кроме Q, A, Z) и знаки препинания, показанные выше [кроме обратной кавычки (`)]. Клавиши, обозначенные словами [Tab, BackSp, Control и т.д.], не представлены во входных данных.

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

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

Тесты:

Входные данные	Выходные данные
O S, GOMR YPFSU/	I AM FINE TODAY.
JS;=0—	HAL-9000
OY OD S MOVR MOHJY GPT VPFOMH	IT IS A NICE NIGHT FOR CODING

Решение:

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

int main() {
    string x;
    string y="`1234567890-=QWERTYUIOP[]\ASDFGHJKL;'ZXCVBNM,./";
    while(getline(cin,x)) {
        size_t found;
        for (int i=0; i<x.length(); i++) {
            if (x[i]==' ') {
                cout<<" ";
            } else {
                found=y.find_first_of(x[i]);
                cout<<y[found-1];
            }
        }
        cout<<endl;
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string x;

string y="`1234567890-=QWERTYUIOP[]\ASDFGHJKL;'ZXCVBNM,./";

while(getline(cin,x)) {

size_t found;

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

if (x[i]==' ') {

cout<<" ";

} else {

found=y.find_first_of(x[i]);

cout<<y[found-1];

}

cout<<endl;

}

return 0;

}

Описание решения:

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

while(getline(cin,x))

8	while(getline(cin,x))

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

Если данный символ пробел — то выведем его на экран.
Иначе, с помощью функции [latex]find[/latex]_[latex]first[/latex]_[latex]of()[/latex] найдем номер вхождения данного символа в проверочном массиве [latex]y[/latex], и выведем предыдущий элемент из этого массива.
Повторяем пункты 1, 2 до тех пор, пока не дойдем до конца строки [latex]x[/latex]. После этого перейдем на новую строку с помощью команды [latex]endl[/latex].

Условие задачи на сайте e-olymp.com можно найти здесь.

Решение, что зашло на 100%.

Код решения можно проверить здесь.

Related Images:

Mif 17.18

30/09/2015 by Грешилов Константин

Условие:

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

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

Два числа — координаты точки.

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

Слово «Yes», если точка принадлежит фигуре, в противном случае -«No».

Тесты:

[latex]x[/latex]	[latex]y[/latex]	Result
6	0	Yes
0	0	Yes
5	2	No
-6	1	No

#include <iostream>
using namespace std;

int main() {
	double x,y;
	cin>>x>>y;
	if ((x>=0 && y>=0 && (x+y)<=6)||(x<=0 && y<=0 && (x+y)>=-6))
	cout<<"Yes"<<endl;
	else 
	cout<<"No"<<endl;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double x,y;

cin>>x>>y;

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

cout<<"Yes"<<endl;

else

cout<<"No"<<endl;

return 0;

}

Описание решения:

Точка будет принадлежит фигуре тогда и только тогда, когда будут выполняться группы условий: или оба числа не отрицательные и их сумма не превышает 6, или оба числа не положительные, и их сумма не меньше 6. если одно из этих условий выполняется, то выводим «Yes», а иначе — «No».

Здесь решенная задача на сайте ideone.com.

Related Images:

Ю2.30. Отрезки на плоскости

30/09/2015 by Грешилов Константин

Задача взята со сборника задач Юркина А. Г.

Условие:

Найти расстояние между двумя произвольно заданными на плоскости отрезками.

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

8 чисел, пары координат каждого конца отрезков.

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

Минимальное расстояние между отрезками.

Тесты:

[latex]x_1[/latex]	[latex]y_1[/latex]	[latex]x_2[/latex]	[latex]y_2[/latex]	[latex]x_3[/latex]	[latex]y_3[/latex]	[latex]x_4[/latex]	[latex]y_4[/latex]	Минимальное расстояние
0	0	2	2	1	1	0	3	0
1	2	3	2	2	1	2	0	1
1	1	3	1	1	2.5	3	2.5	1.5
1	-1	3	-1	1	2.5	3	3.5	3.5

Решение:

#include <iostream>
#include <cmath>
#include <algorithm>//библиотека, содержащая функции min и max
using namespace std;
double perpendicularx(double x1,double y1, double x2, double y2, double x3, double y3) //функция, которая высчитывает значение абциссы проекции точки на прямую, содержащую отрезок
{
	double x;
	x=(-x1*(y2-y1)*(y2-y1)+x3*(x2-x1)*(x2-x1)-y1*y2+y1*y1)/((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1));
	return x;
}
double perpendiculary(double x1,double y1, double x2, double y2, double x3, double y3, double x)//функция, которая высчитывает значение абциссы проекции точки на прямую, содержащую отрезок
{
	double y;
	y=(x-x1)*(y2-y1)/(x2-x1)+y1;
	return y;
}
int main() {
	double x, y, x1, x2, x3, x4, y1, y2, y3, y4, temp;
	cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
	double mini=sqrt((x3-x1)*(x3-x1)+(y3-y1)*(y3-y1)); //предположим, что минимальное значение, это расстояние от конца одного отрезка до конца другого
	temp=sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2)); //для каждой пары концов разных отрезков высчитываем расстояние между ними
	if (temp<mini)//если оно меньше минимума
	mini=temp;//то меняем минимум
	temp=sqrt((x4-x1)*(x4-x1)+(y4-y1)*(y4-y1));//повторяем для каждой пары концов разных отрезков
	if (temp<mini)
	mini=temp;
	temp=sqrt((x4-x2)*(x4-x2)+(y4-y2)*(y4-y2));
	if (temp<mini)
	mini=temp;
	x=perpendicularx(x1, y1, x2, y2, x3, y3);//получаем абциссу проекции конца одного отрезка на другой 
	y=perpendiculary(x1, y1, x2, y2, x3, y3, x);//ординату
	if ((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1)==0) //в случае, если равно нулю, абцисса будет равна бесконечности, а это возможно в том случае, если конец отрезка совпадает с его проекцией на другой отрезок
	{
		x=x3; // для корректных вычислений приравниваем абциссы и ординаты точки с её проекцией
		y=y3;
	}
	if (x>=min(x1,x2)&&x<=max(x1,x2)&&y>=min(y1,y2)&&y<=max(y1,y2)) //если проекция лежит на отрезке заданном
	{
		temp=sqrt((x3-x)*(x3-x)+(y3-y)*(y3-y));//то проверяем, будет ли расстояние от конца отрезка до её проекции меньше, чем текущий минимум
		if (temp<mini)
		mini=temp;//если да, то меняем значение минимума
	}
	x=perpendicularx(x1, y1, x2, y2, x4, y4); // далее повторяемя для трех других концов отрезков
	y=perpendiculary(x1, y1, x2, y2, x4, y4, x);
	if ((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1)==0)
	{
		x=x4;
		y=y4;
	}
	if (x>=min(x1,x2)&&x<=max(x1,x2)&&y>=min(y1,y2)&&y<=max(y1,y2))
	{
		temp=sqrt((x4-x)*(x4-x)+(y4-y)*(y4-y));
		if (temp<mini)
		mini=temp;
	}
	x=perpendicularx(x3, y3, x4, y4, x1, y1);
	y=perpendiculary(x3, y3, x4, y4, x1, y1, x);
	if ((x4-x3)*(x4-x3)-(y4-y3)*(y4-y3)==0)
	{
		x=x1;
		y=y1;
	}
	if (x>=min(x3,x4)&&x<=max(x3,x4)&&y>=min(y3,y4)&&y<=max(y3,y4))
	{
		temp=sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y));
		if (temp<mini)
		mini=temp;
	}
	x=perpendicularx(x3, y3, x4, y4, x2, y2);
	y=perpendiculary(x3, y3, x4, y4, x2, y2, x);
	if ((x4-x3)*(x4-x3)-(y4-y3)*(y4-y3)==0)
	{
		x=x2;
		y=y2;
	}
	if (x>=min(x3,x4)&&x<=max(x3,x4)&&y>=min(y3,y4)&&y<=max(y3,y4))
	{
		temp=sqrt((x2-x)*(x2-x)+(y2-y)*(y2-y));
		if (temp<mini)
		mini=temp;
	}
	cout<<mini<<endl; // выводим минимальное расстояние и переходим на новую строку
	return 0;
}

#include <iostream>

#include <cmath>

#include <algorithm>//библиотека, содержащая функции min и max

using namespace std;

double perpendicularx(double x1,double y1, double x2, double y2, double x3, double y3) //функция, которая высчитывает значение абциссы проекции точки на прямую, содержащую отрезок

{

double x;

x=(-x1*(y2-y1)*(y2-y1)+x3*(x2-x1)*(x2-x1)-y1*y2+y1*y1)/((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1));

return x;

}

double perpendiculary(double x1,double y1, double x2, double y2, double x3, double y3, double x)//функция, которая высчитывает значение абциссы проекции точки на прямую, содержащую отрезок

{

double y;

y=(x-x1)*(y2-y1)/(x2-x1)+y1;

return y;

}

int main() {

double x, y, x1, x2, x3, x4, y1, y2, y3, y4, temp;

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

double mini=sqrt((x3-x1)*(x3-x1)+(y3-y1)*(y3-y1)); //предположим, что минимальное значение, это расстояние от конца одного отрезка до конца другого

temp=sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2)); //для каждой пары концов разных отрезков высчитываем расстояние между ними

if (temp<mini)//если оно меньше минимума

mini=temp;//то меняем минимум

temp=sqrt((x4-x1)*(x4-x1)+(y4-y1)*(y4-y1));//повторяем для каждой пары концов разных отрезков

if (temp<mini)

mini=temp;

temp=sqrt((x4-x2)*(x4-x2)+(y4-y2)*(y4-y2));

if (temp<mini)

mini=temp;

x=perpendicularx(x1, y1, x2, y2, x3, y3);//получаем абциссу проекции конца одного отрезка на другой

y=perpendiculary(x1, y1, x2, y2, x3, y3, x);//ординату

if ((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1)==0) //в случае, если равно нулю, абцисса будет равна бесконечности, а это возможно в том случае, если конец отрезка совпадает с его проекцией на другой отрезок

{

x=x3; // для корректных вычислений приравниваем абциссы и ординаты точки с её проекцией

y=y3;

}

if (x>=min(x1,x2)&&x<=max(x1,x2)&&y>=min(y1,y2)&&y<=max(y1,y2)) //если проекция лежит на отрезке заданном

{

temp=sqrt((x3-x)*(x3-x)+(y3-y)*(y3-y));//то проверяем, будет ли расстояние от конца отрезка до её проекции меньше, чем текущий минимум

if (temp<mini)

mini=temp;//если да, то меняем значение минимума

}

x=perpendicularx(x1, y1, x2, y2, x4, y4); // далее повторяемя для трех других концов отрезков

y=perpendiculary(x1, y1, x2, y2, x4, y4, x);

if ((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1)==0)

{

x=x4;

y=y4;

}

if (x>=min(x1,x2)&&x<=max(x1,x2)&&y>=min(y1,y2)&&y<=max(y1,y2))

{

temp=sqrt((x4-x)*(x4-x)+(y4-y)*(y4-y));

if (temp<mini)

mini=temp;

}

x=perpendicularx(x3, y3, x4, y4, x1, y1);

y=perpendiculary(x3, y3, x4, y4, x1, y1, x);

if ((x4-x3)*(x4-x3)-(y4-y3)*(y4-y3)==0)

{

x=x1;

y=y1;

}

if (x>=min(x3,x4)&&x<=max(x3,x4)&&y>=min(y3,y4)&&y<=max(y3,y4))

{

temp=sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y));

if (temp<mini)

mini=temp;

}

x=perpendicularx(x3, y3, x4, y4, x2, y2);

y=perpendiculary(x3, y3, x4, y4, x2, y2, x);

if ((x4-x3)*(x4-x3)-(y4-y3)*(y4-y3)==0)

{

x=x2;

y=y2;

}

if (x>=min(x3,x4)&&x<=max(x3,x4)&&y>=min(y3,y4)&&y<=max(y3,y4))

{

temp=sqrt((x2-x)*(x2-x)+(y2-y)*(y2-y));

if (temp<mini)

mini=temp;

}

cout<<mini<<endl; // выводим минимальное расстояние и переходим на новую строку

return 0;

}

Описание решения:

При решении задачи использовались переменные типа [latex]double[/latex], так как в условии не поставлено ограничение на координаты концов отрезков, а тип [latex]double[/latex] существенно расширяет диапазон вводимых значений. Решение данной задачи сводится к тому, чтобы найти расстояния между концами разных отрезков и длины перпендикуляров, опущенных с концов одного отрезка на другой. Поэтому, условно разобьем задачу на два пункта:

1.Нахождение расстояния между концами двух отрезков.

2.Нахождение длины перпендикуляров, опущенных с концов одного отрезка на другой.

1.Расстояние между двумя точками [latex]M_1(mx_1,my_1), M_2(mx_2,my_2)[/latex] находится по формуле [latex]\sqrt{(mx_2-mx_1)^2+(my_2-my_1)^2}[/latex]. Сначала, переменной [latex]mini[/latex] присваиваем значение расстояния между первой парой концов отрезков:

mini=sqrt((x3-x1)*(x3-x1)+(y3-y1)*(y3-y1));

20	mini=sqrt((x3-x1)(x3-x1)+(y3-y1)(y3-y1));

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

После 4 проверок получаем минимальное расстояние между концами двух отрезков.

После этого переходим к пункту 2.

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

Продемонстрируем решение для отрезка с координатами [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex], и точки с координатами [latex](x_3, y_3)[/latex]

Первое уравнение имеет вид [latex](x-x_1)/(x_2-x_1)=(y-y_1)/(y_2-y_1)[/latex], а второе : [latex]-(x_2-x_1)/(y_2-y_1)*(x-x_3)=y-y_3[/latex]. Решив эту систему, получаем, что

x=(-x1*(y2-y1)*(y2-y1)+x3*(x2-x1)*(x2-x1)-y1*y2+y1*y1)/((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1))

8	x=(-x1(y2-y1)(y2-y1)+x3(x2-x1)(x2-x1)-y1y2+y1y1)/((x2-x1)(x2-x1)-(y2-y1)(y2-y1))

y=(x-x1)*(y2-y1)/(x2-x1)+y1

14	y=(x-x1)*(y2-y1)/(x2-x1)+y1

Если делитель в [latex]x[/latex] равен нулю, то это означает, что проекция лежит на начале перпендикуляра, то есть они совпадают, и в таком случае присваиваем координатам проекции значения координат точки, с которой опускался перпендикуляр.

Получили абсциссу и ординату проекции точки на отрезок. Необходимо проверить, принадлежит ли эта проекция отрезку, для этого воспользуемся функциями [latex]min[/latex] и [latex]max[/latex], чтобы определить большие из координат отрезка, и операций сравнения:

if (x>=min(x1,x2)&&x<=max(x1,x2)&&y>=min(y1,y2)&&y<=max(y1,y2))

37	if (x>=min(x1,x2)&&x<=max(x1,x2)&&y>=min(y1,y2)&&y<=max(y1,y2))

Если условия выполняются, то находим длину перпендикуляра по аналогии с расстоянием между концами отрезков, и сравниваем с [latex]mini[/latex]. Если длина меньше, то меняем значение минимума.

Так как все шаги нахождения повторяются 4 раза, то вынесем их в отдельные функции, которые высчитывают значения для каждой координаты проекции:

double perpendicularx(double x1,double y1, double x2, double y2, double x3, double y3) //функция, которая высчитывает значение абциссы проекции точки на прямую, содержащую отрезок
{
	double x;
	x=(-x1*(y2-y1)*(y2-y1)+x3*(x2-x1)*(x2-x1)-y1*y2+y1*y1)/((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1));
	return x;
}
double perpendiculary(double x1,double y1, double x2, double y2, double x3, double y3, double x)//функция, которая высчитывает значение абциссы проекции точки на прямую, содержащую отрезок
{
	double y;
	y=(x-x1)*(y2-y1)/(x2-x1)+y1;
	return y;
}

{

double x;

x=(-x1*(y2-y1)*(y2-y1)+x3*(x2-x1)*(x2-x1)-y1*y2+y1*y1)/((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1));

return x;

}

{

double y;

y=(x-x1)*(y2-y1)/(x2-x1)+y1;

return y;

}

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

Выводим его на экран и переходим на новую строку с помощью команды [latex]endl[/latex].

Здесь код программы на сайте ideone.com.

Related Images:

e-olymp 36. Змей Горыныч

29/09/2015 by Грешилов Константин

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

Условие:

В некотором царстве жил Змей Горыныч. У него было [latex]N[/latex] голов и [latex]M[/latex] хвостов. Иван-царевич решил уничтожить губителя человеческих душ, для чего ему его кума Баба Яга подарила волшебный меч, так как только им можно убить Змея Горыныча. Если отрубить одну голову, то на её месте вырастает новая, если отрубить хвост, то вместо него вырастет 2 хвоста. Если отрубить два хвоста, то вырастает 1 голова, и только когда отрубить 2 головы, то не вырастет ничего. Змей Горыныч гибнет только в том случае, когда ему отрубить все головы и все хвосты. Определить минимальное количество ударов мечом, нужное для уничтожения Змея Горыныча.

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

Два числа [latex]N[/latex], [latex]M[/latex] ([latex]0[/latex] [latex]<=[/latex][latex]N[/latex], [latex]M[/latex][latex]<=[/latex][latex]1000[/latex]).

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

Единственное число – минимальное количество ударов мечом, или -1, если уничтожить Змея Горыныча невозможно.

Тесты:

N	M	Количество ударов
3	3	9
3	0	-1
0	9	12
0	0	0
3	2	3
19	114	95

Решение

#include <iostream>
using namespace std;

int main() {
	int N, M, count = 0;
	cin>>N>>M;
	if ((N%2!=0)&&(M==0)) //здесь проверяется, возможно ли убить Горыныча
	{
		cout<<"-1"<<endl;// вывод "-1" в противном случае
	}
	else 
	{
		while ((N>0)||(M>0)) //цикл будет выполняться до тех пор, пока существует хоть одна голова или хвост
		{
			if (M%2==1) //если хвостов нечетное количество, то посредством отрубания одного хвоста увеличиваем число их на 1
			{
				count++;// здесь и далее таким образом будет увеличиваться счетчик надрезов
				M++;
			}
			if ((N%2==1)&&(M>=2)) //если голов нечетное количество, то отрубая два хвоста увеличиваем количество голов на 1
			{
				M-=2;
				N++;
				count++;
			}
			if ((M%2==0)&&(N%2==0)&&((N+(M/2))%2==0)) //если число голов и хвостов четное, и если количество хвостов при делении на два дает четное число
			{
				count=count+M/2+((N+M/2)/2);//то увеличиваем счетчик надрезов
				N=0;
				M=0;//и обнуляем количество голов и хвостов для выхода их цикла
			}
			else  //если не выполняется какое-либо из условий прошлого ветвления, то увеличиваем количество хвостов на 1
			{
				M++;
				count++;
			}
		}
		cout<<count<<endl;//выводим количество ударов
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int N, M, count = 0;

cin>>N>>M;

if ((N%2!=0)&&(M==0)) //здесь проверяется, возможно ли убить Горыныча

{

cout<<"-1"<<endl;// вывод "-1" в противном случае

}

else

{

while ((N>0)||(M>0)) //цикл будет выполняться до тех пор, пока существует хоть одна голова или хвост

{

if (M%2==1) //если хвостов нечетное количество, то посредством отрубания одного хвоста увеличиваем число их на 1

{

count++;// здесь и далее таким образом будет увеличиваться счетчик надрезов

M++;

}

if ((N%2==1)&&(M>=2)) //если голов нечетное количество, то отрубая два хвоста увеличиваем количество голов на 1

{

M-=2;

N++;

count++;

}

if ((M%2==0)&&(N%2==0)&&((N+(M/2))%2==0)) //если число голов и хвостов четное, и если количество хвостов при делении на два дает четное число

{

count=count+M/2+((N+M/2)/2);//то увеличиваем счетчик надрезов

N=0;

M=0;//и обнуляем количество голов и хвостов для выхода их цикла

}

else //если не выполняется какое-либо из условий прошлого ветвления, то увеличиваем количество хвостов на 1

{

M++;

count++;

}

cout<<count<<endl;//выводим количество ударов

}

return 0;

}

Описание решения:

При решении данной задачи было рассмотрено несколько случаев.

Змея Горыныча убить невозможно. Это возможно только в том случае, когда у него нечетное количество голов, и нет ни одного хвоста, так как при наличии хотя бы одного хвоста становится возможным увеличение количества хвостов и голов до необходимого, путем отрубания одного, или двух хвостов соответственно. Чтобы определить возможность уничтожения Змея, делаем проверку: если количество голов нечетное и хвостов нет, то выводим «-1». Если эти условия не выполняются, то переходим ко второму пункту решения.

Змей Горыныч может быть убит. Это означает, что у Змея есть хотя бы один хвост, или четное количество голов. В таком случае, мы работаем внутри цикла, при каждом проходе которого проверяется, выполняются ли описанные выше условия:

while ((N>0)||(M>0)) //цикл будет выполняться до тех пор, пока существует хоть одна голова или хвост

13	while ((N>0)\|\|(M>0)) //цикл будет выполняться до тех пор, пока существует хоть одна голова или хвост

Горыныча можно убить тогда и только тогда, когда при отрубании всех хвостов получается четное количество голов. Отсюда, необходимо, чтобы у Змея было четное количество хвостов, и сумма голов и количества хвостов, деленного на два, была четным числом. Поэтому будем работать по простому алгоритму:

Если количество хвостов [latex]M[/latex] нечетное, то отрубаем один хвост, на месте которого вырастает два новых, и увеличиваем счетчик ударов [latex]count[/latex] на один.
Если количество голов нечетное, и хвостов больше одного, то отрубаем два хвоста, тем самым увеличивая количество голов на 1, и увеличиваем счетчик.
Если количество голов и хвостов четное, и если количество хвостов при делении на два дает четное число, то мы увеличиваем счетчик на [latex]M/2+((N+M/2)/2)[/latex], и приравниваем количество голов и хвостов нулю.
Если какое-то из условий пункта 3 не выполняется, то увеличиваем количество хвостов на 1, и увеличиваем счетчик ударов.
Повторяем алгоритм до тех пор, пока не убьем Горыныча.

После выхода из цикла в счетчике [latex]count[/latex] находится минимальное число ударов, необходимое для уничтожения Змея Горыныча. Выводим его на экран, и переходим на новую строку с помощью команды [latex]endl[/latex].

Здесь код программы на сайте ideone.com.

Для перехода к странице на e-olimp с полностью выполненным данным заданием щелкните здесь.

Related Images:

ML 20

27/09/2015 by Грешилов Константин

Задача

Найти площадь кольца, внутренний радиус которого равен [latex]r[/latex], а внешний – [latex]R[/latex] ([latex]r<R[/latex]).

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

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

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

Единственное число — площадь кольца.

Тесты:

R	r	Площадь кольца
3	2	15.708
12.921	7.903	328.28
25	3.5	1925.01
10.2531	1	327.122

Решение:

#include <iostream>
#include <cmath> 
using namespace std;
int main() {
    double R, r;
    cin>>R>>r;
    cout<<R*R*M_PI-r*r*M_PI<<endl;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double R, r;

cin>>R>>r;

cout<<R*R*M_PI-r*r*M_PI<<endl;

return 0;

}

Описание решения:

При решении данной задачи использовались две переменные типа [latex]double[/latex]. Так как в постановке задачи не было указано, какими могут быть числа, то для обхвата наибольшего диапазона чисел разумно использовать именно этот тип данных. Помимо этого, была использована константа из математической библиотеки [latex]cmath[/latex], а именно, константа числа [latex]\pi[/latex]: [latex]M[/latex]_[latex]PI[/latex].

Чтобы найти площадь кольца, образованного двумя окружностями, необходимо найти площадь круга, образованного внешним радиусом кольца, по формуле [latex]\pi\cdot R^2[/latex], и площадь круга, образованного внутренним радиусом кольца, по формуле [latex]\pi\cdot r^2[/latex]. Затем, из площади большего круга вычесть площадь меньшего.

Получаем формулу: [latex]\pi\cdot R^2 — \pi\cdot r^2[/latex]. Подставляя в формулу переменные и константы, получаем:

R*R*M_PI-r*r*M_PI

7	RRM_PI-rrM_PI

После выполнения всех операций перейдем на новую строку с помощью команды [latex]endl[/latex].

Здесь код программы на сайте ideone.com.

Related Images:

e-olymp 906. Произведение цифр

14/09/2015 by Грешилов Константин

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

Условие

Задано трицифровое число. Определить произведение его цифр.

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

В единственной строке заданное трицифровое число.

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

В единственной строке произведение цифр заданного числа.

Тесты

#	Входные данные	Результат
1	235	30
2	106	0
3	111	1

Решение

#include <iostream>
using namespace std;
int main() {
	int num = 0;
	cin>>num;
	cout<<(num / 100)*((num / 10) % 10)*(num % 10)<<endl;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int num = 0;

cin>>num;

cout<<(num / 100)*((num / 10) % 10)*(num % 10)<<endl;

return 0;

}

Описание решения

Для решения данной задачи необходимо задать переменную num, которая будет хранить в себе вводимые данные. Так как будут приниматься целочисленные данные, то используем тип данных int. Далее необходимо разбить исходное число на три цифры и перемножить их между собой.

Для разбиения на цифры воспользуемся формулой:

(num / 100)*((num / 10) % 10)*(num % 10)

10	(num / 100)((num / 10) % 10)(num % 10)

В данной формуле в первом множителе мы получаем первую цифру, во втором — вторую, и в третьем соответственно третью.

После выполнения всех операций перейдем на новую строку с помощью команды endl.

Для перехода к странице на e-olimp с полностью выполненным данным заданием щелкните здесь.

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Author Archives: Грешилов Константин

e-olymp 1108. Червячные дыры

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

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

Related Images:

e-olymp 1948. Топологическая сортировка

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

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

Related Images:

A298

Related Images:

MLoop 8

Related Images:

e-olymp 2034. WERTYU

Related Images:

Mif 17.18

Related Images:

Ю2.30. Отрезки на плоскости

Related Images:

e-olymp 36. Змей Горыныч

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

Related Images:

ML 20

Related Images:

e-olymp 906. Произведение цифр

Условие

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

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

Тесты

Решение

Описание решения

Related Images: