e-olymp 15. Мышка и зернышки

17/06/2017 by Валентина Андриеш

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

В индийском храме пол прямоугольной формы выложен одинаковыми квадратными плитками 1 х 1, на каждую из которых высыпано от 0 до k зернышек (k ≤ 30000). Размеры пола m х n. Мышка выбегает из левого нижнего угла пола храма и двигается к входу в другую норку, расположенную в противоположном углу. Мышка может двигаться только вправо или вперед, собирая все зернышки с плитки, на которой она находится.

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

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

Первая строка содержит числа m и n – размеры пола (1 ≤ m, n ≤ 100). Далее идет m строк, начиная сверху, в каждой из которых размещено n чисел – количество зернышек на соответствующей плитке.

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

Вывести маршрут движения мышки в формате: RRFFFRF (F – шаг вперед, R – шаг вправо).

Тесты:

Входные данные	Выходные данные
2 3 3 2 4 1 5 1	RFR
4 4 34 5 7 8 7 8 9 23 1 2 909 54 3 4 8 0	RRFRFF
7 8 23 4 7 8 94 23 5 6 2 9 7 56 83 5 44 2 1 2 3 4 5 6 7 8 8 7 6 5 4 32 2 1 90 87 3 5 4 3 2 5 28 75 60 94 33 3 2 7 76 92000 402 28 3 2 11 200	RFRRFFFFRFRRR

Код на С++:

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
    int m,n;
    long long X[100][100];
    string ans;
    cin>>n>>m;
    for (int i=n-1; i>=0; i--){
        for (int j=0; j<m; j++)cin>>X[i][j];
    }
    for(int i=1;i<n;i++)X[i][0]=X[i][0]+X[i-1][0];
    for(int j=1;j<m;j++)X[0][j]=X[0][j]+X[0][j-1];
    for (int i=1; i<n; i++){
        for (int j=1; j<m; j++) X[i][j]=X[i][j]+max(X[i - 1][j], X[i][j - 1]);
    }
    int k=n-1, t=m-1;
    while (k>0 || t>0){
        if (k>0 && t>0){
            if (X[k-1][t]>X[k][t-1]){
                ans+="F";
                k--;
            }
            else{
                ans+="R";
                t--;    
            } 
        }
        else if (k==0){
            ans+="R";
            t--;
        }
        else if (t==0){
            ans+="F";
            k--;
        }
    }
    reverse(ans.begin(),ans.end());
    cout<<ans;
    return 0;
}

#include <iostream>

#include <algorithm>

#include <string>

using namespace std;

int main() {

int m,n;

long long X[100][100];

string ans;

cin>>n>>m;

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

for (int j=0; j<m; j++)cin>>X[i][j];

}

for(int i=1;i<n;i++)X[i][0]=X[i][0]+X[i-1][0];

for(int j=1;j<m;j++)X[0][j]=X[0][j]+X[0][j-1];

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

for (int j=1; j<m; j++) X[i][j]=X[i][j]+max(X[i - 1][j], X[i][j - 1]);

}

int k=n-1, t=m-1;

while (k>0 || t>0){

if (k>0 && t>0){

if (X[k-1][t]>X[k][t-1]){

ans+="F";

k--;

}

else{

ans+="R";

t--;

}

else if (k==0){

ans+="R";

t--;

}

else if (t==0){

ans+="F";

k--;

}

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

cout<<ans;

return 0;

}

Код на Java:

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        long[][] X = new long[100][100];
        String ans = new String("");
        for (int i=n-1; i>=0; i--){
            for (int j=0; j<m; j++)X[i][j]=in.nextLong();
        }
        for(int i=1;i<n;i++)X[i][0]=X[i][0]+X[i-1][0];
        for(int j=1;j<m;j++)X[0][j]=X[0][j]+X[0][j-1];
        for (int i=1; i<n; i++){
            for (int j=1; j<m; j++) X[i][j]=X[i][j]+Math.max(X[i - 1][j], X[i][j - 1]);
        }
        int k=n-1, t=m-1;
        while (k>0 || t>0){
            if (k>0 && t>0){
                        if (X[k-1][t]>X[k][t-1]){
                            ans+="F";
                            k--;
                        }
                        else{
                            ans+="R";
                            t--;    
                        }
            }
                    else if (k==0){
                        ans+="R";
                        t--;
            }
            else if (t==0){
                        ans+="F";
                        k--;
            }
        }
        String reverse = new StringBuffer(ans).reverse().toString();
        System.out.println(reverse);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int n=in.nextInt();

int m=in.nextInt();

long[][] X = new long[100][100];

String ans = new String("");

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

for (int j=0; j<m; j++)X[i][j]=in.nextLong();

}

for(int i=1;i<n;i++)X[i][0]=X[i][0]+X[i-1][0];

for(int j=1;j<m;j++)X[0][j]=X[0][j]+X[0][j-1];

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

for (int j=1; j<m; j++) X[i][j]=X[i][j]+Math.max(X[i - 1][j], X[i][j - 1]);

}

int k=n-1, t=m-1;

while (k>0 || t>0){

if (k>0 && t>0){

if (X[k-1][t]>X[k][t-1]){

ans+="F";

k--;

}

else{

ans+="R";

t--;

}

else if (k==0){

ans+="R";

t--;

}

else if (t==0){

ans+="F";

k--;

}

String reverse = new StringBuffer(ans).reverse().toString();

System.out.println(reverse);

}

Описание решения задачи:

Представим пол индийского храма в виде двумерного массива. Т.к по условию движение мышки начинается с левого нижнего угла, при заполнении произойдет сдвиг, где позиция с изначальным номером [latex][n-1][0][/latex] примет позицию под номером [latex][0][0][/latex] и так далее пока данный сдвиг не достигнет плитки с номером [latex][n-1][0][/latex], где станет клеткой [latex][n-1][m-1][/latex]. Далее с помощью обхода в несколько циклов пересчитаем ячейки массива [latex]X[/latex] так, чтобы [latex]X[i][j][/latex] содержало максимальное количество зернышек, которое можно собрать по достижении плитки [latex](i, j)[/latex]. Переместимся в конец массива, в позицию под номером [latex]X[n-1][m-1][/latex]. Двигаясь в начальную клетку по закону, что предыдущая клетка слева или снизу должна содержать максимальное количество зернышек из всех возможных путей мыши, записываем в строку соответствующую букву, которая указывает на сделанный ход. По достижению цели мы получаем строку почти с готовым ответом. Перевернем ее, и теперь она указывает правильный путь не с конца в начало, а с начала в конец, что и требовалось. Выведем ответ.

Код задачи на с++
Код задачи на Java
Засчитанное решение на C++
Засчитанное решение на Java

Related Images:

Вычисление математических выражений

06/06/2017 by Валентина Андриеш

Условие задачи:
Пусть дана строка, которая является математическим выражением, содержащим числа, переменные и различные операции. Требуется вычислить его значение.

Помимо создания прототипа работы элементарного калькулятора, рассмотрим решение одной из подзадач — «Многочлен», найденную на просторах сайта e-olymp.

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

В первой строке входного файла записано математическое выражение. Между операндами используются бинарные операторы ([latex]+[/latex], [latex]–[/latex], [latex]\ast[/latex], [latex]/[/latex], [latex]\wedge[/latex]) и унарный знак ([latex]–[/latex]). Если данное выражение представляет собой многочлен, то каждый одночлен записывается как [Коэффициент*]x[^Степень] или [Коэффициент], где [Коэффициент] — натуральное число, не превосходящее 100, x — символ переменной (всегда маленькая латинская буква [latex]x[/latex]), [Степень] — натуральное число, не превосходящее 4. Параметры, взятые в квадратные скобки, могут быть опущены. Во второй строке будет записано одно целое число — значение x. Все числа в исходном файле по модулю не превосходят 100. Количество одночленов не более 10 (могут быть одночлены одинаковой степени).

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

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

Тесты:

Входные данные		Выходные данные
16-(4^3+52/2)		-74
-2+x^1-3x^2+x^2+100x^3-2*x	-7	-34393
-2x^2+16x^3-x	(-3)^4	8489853
x^2-5x+15-8x^4	0	15

Код на с++:

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

 //в этой функции рассмотрим все возможные операции, что могут встретиться в строке
bool operation(char c){
    return c=='+' || c=='-' || c=='*' ||  c=='/' || c=='^';
}

//данная функция будет возвращать приоритет поступившей операции
int prioritet(char op){ 
    if(op<0) return 3;
    else{
        if(op == '+' || op == '-')return 1;
        else if(op == '*' || op == '/' )return 2;
        else if(op == '^')return 4;
        else return -1;
    }
}

//следующая функция описывает принцип работы каждого оператора
void action(vector<long> &value, char op){
    if(op<0){                            //для унарных операций
        long unitar=value.back();
        value.pop_back();
        if(-op=='-')value.push_back(-unitar);
    }
    else{                               //для бинарных операций
        long right = value.back();
        value.pop_back();
        long left = value.back();
        value.pop_back();
        if(op=='+')value.push_back(left+right);
        else if(op=='-')value.push_back(left-right);
        else if(op=='*')value.push_back(left*right);
        else if(op=='/')value.push_back(left/right);
        else if(op=='^')value.push_back(pow(left,right));
    }
}

long calculus(string &formula){
    bool unary=true;        //создадим булевскую переменную, для распределения операторов на унарные и бинарные
    vector<long>value;        //заведем массив для целых чисел
    vector<char>op;           //и соответственно для самых операторов
    for(int i=0; i<formula.size(); i++){
            if(formula[i]=='('){    //если текущий элемент — открывающая скобка, то положим её в стек
                op.push_back('(');  
                unary=true;
            }
            else if(formula[i]==')'){
                while(op.back()!='('){  //если закрывающая скобка - выполняем все операции, находящиеся внутри этой скобки
                    action(value, op.back());
                    op.pop_back();
                }
                op.pop_back();
                unary=false;
            }
            else if(operation(formula[i])){ //если данный элемент строки является одни из выше перечисленных операндов,то
                char zn=formula[i];
                if(unary==true)zn=-zn; //придает отрицательное значение, для распознавания функции унарности оператора 
                while(!op.empty() && prioritet(op.back())>=prioritet(zn)){
                    action(value, op.back());   //выполняем сами алгебраические вычисления, где все уже операции упорядочены  
                    op.pop_back();              //в одном из стеков по строгому убыванию приоритета, если двигаться от вершины
                }
                op.push_back(zn);
                unary=true;
            }
            else{
                string number;      //заведем строку для найденных числовых операндов
                while(i<formula.size() && isdigit(formula[i]))number+=formula[i++];//распознаем их с помощью библиотечной функции строк
                i--;
                value.push_back(atol(number.c_str()));//поместим в наш стек с числовыми выражениями
                unary=false;
            }
        }
    while(!op.empty()){     //выполним еще не использованные операции в стеке 
        action(value, op.back());
        op.pop_back();
    }
    return value.back(); //получим на выходе значение выражения
}
    
int main() {
    string formula,x; //введем две строки: сам многочлен/числовое выражение и по необходимости значение переменной 
    cin>>formula>>x;
    if(x[0]=='-'){  //для слаженной работы унитарного минуса при отрицательном значении переменной, заключим его в скобки
        x.insert(x.begin(),'(');
        x.insert(x.end(),')');
    }
    int size=2*formula.size();  //зададим максимальный размер строки с учетом замены переменной
    for(int i=0; i<size; i++){
        if(formula[i]=='x'){
            formula.erase(i,1);
            formula.insert(i,x);//проведем замену
        }
    }
    cout<<calculus(formula);  //выведем ответ
    return 0;
}

100

101

#include <iostream>

#include <vector>

#include <string>

#include <cmath>

using namespace std;

//в этой функции рассмотрим все возможные операции, что могут встретиться в строке

bool operation(char c){

return c=='+' || c=='-' || c=='*' || c=='/' || c=='^';

}

//данная функция будет возвращать приоритет поступившей операции

int prioritet(char op){

if(op<0) return 3;

else{

if(op == '+' || op == '-')return 1;

else if(op == '*' || op == '/' )return 2;

else if(op == '^')return 4;

else return -1;

}

//следующая функция описывает принцип работы каждого оператора

void action(vector<long> &value, char op){

if(op<0){ //для унарных операций

long unitar=value.back();

value.pop_back();

if(-op=='-')value.push_back(-unitar);

}

else{ //для бинарных операций

long right = value.back();

value.pop_back();

long left = value.back();

value.pop_back();

if(op=='+')value.push_back(left+right);

else if(op=='-')value.push_back(left-right);

else if(op=='*')value.push_back(left*right);

else if(op=='/')value.push_back(left/right);

else if(op=='^')value.push_back(pow(left,right));

}

long calculus(string &formula){

bool unary=true; //создадим булевскую переменную, для распределения операторов на унарные и бинарные

vector<long>value; //заведем массив для целых чисел

vector<char>op; //и соответственно для самых операторов

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

if(formula[i]=='('){ //если текущий элемент — открывающая скобка, то положим её в стек

op.push_back('(');

unary=true;

}

else if(formula[i]==')'){

while(op.back()!='('){ //если закрывающая скобка - выполняем все операции, находящиеся внутри этой скобки

action(value, op.back());

op.pop_back();

}

op.pop_back();

unary=false;

}

else if(operation(formula[i])){ //если данный элемент строки является одни из выше перечисленных операндов,то

char zn=formula[i];

if(unary==true)zn=-zn; //придает отрицательное значение, для распознавания функции унарности оператора

while(!op.empty() && prioritet(op.back())>=prioritet(zn)){

action(value, op.back()); //выполняем сами алгебраические вычисления, где все уже операции упорядочены

op.pop_back(); //в одном из стеков по строгому убыванию приоритета, если двигаться от вершины

}

op.push_back(zn);

unary=true;

}

else{

string number; //заведем строку для найденных числовых операндов

while(i<formula.size() && isdigit(formula[i]))number+=formula[i++];//распознаем их с помощью библиотечной функции строк

i--;

value.push_back(atol(number.c_str()));//поместим в наш стек с числовыми выражениями

unary=false;

}

while(!op.empty()){ //выполним еще не использованные операции в стеке

action(value, op.back());

op.pop_back();

}

return value.back(); //получим на выходе значение выражения

}

int main() {

string formula,x; //введем две строки: сам многочлен/числовое выражение и по необходимости значение переменной

cin>>formula>>x;

if(x[0]=='-'){ //для слаженной работы унитарного минуса при отрицательном значении переменной, заключим его в скобки

x.insert(x.begin(),'(');

x.insert(x.end(),')');

}

int size=2*formula.size(); //зададим максимальный размер строки с учетом замены переменной

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

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

formula.erase(i,1);

formula.insert(i,x);//проведем замену

}

cout<<calculus(formula); //выведем ответ

return 0;

}

Описание решения задачи:

В основе решения данной задачи лежит алгоритм, который переводит математические выражения в обратную польскую нотацию, что в дальнейшем позволяет решать данные выражения. Особенностью данной записи, в отличие от привычных нам, является постфиксная форма представления, где операторы математической формулы размещены после своих операндов.
Рассмотрим само решение. На входе программа получает две строки: одна из них представляет само математическое выражение/многочлен — [latex]formula[/latex] и при необходимости вторую — [latex]x[/latex], где передается значение переменной, использованной в многочлене. Если же на вход поступил не многочлен, данная строка сразу же идет на преобразование из инфиксной формы(оператор размещен между операндами) в постфиксную. В ином случае, с помощью встроенных библиотечных функций класса [latex]string[/latex] мы заменяем все переменные на вторую строку [latex]x[/latex] и выполняем точно такую же работу. Разберем ближе сам алгоритм преобразования строки и ее подсчета. Заведём два стека: [latex]value[/latex] — для чисел, [latex]op[/latex] — операций и скобок. Для второго стека является основным предусловие, что все операции упорядочены в нём по строгому убыванию приоритета, если двигаться от вершины стека. Будем идти слева направо по выражению в обратной польской нотации; если текущий элемент — число, то кладём на вершину стека [latex]value[/latex] его значение; если же текущий элемент — операция, то достаём из стека два верхних элемента (или один, если операция унарная), применяем к ним операцию, и результат кладём обратно в стек. Итого в [latex]value[/latex] останется один элемент — значение выражения.

Код задачи на с++
Засчитанное решение на e-olymp

Related Images:

e-olymp 1947. Конденсация графа

25/05/2017 by Валентина Андриеш

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

Для заданного ориентированного графа найти количество ребер в его конденсации.

Конденсацией орграфа G называют такой орграф G’, вершинами которого служат компоненты сильной связности G, а дуга в G’ присутствует только если существует хотя бы одно ребро между вершинами, входящими в соответствующие компоненты связности.

Конденсация графа не содержит кратных ребер.

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

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

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

Количество ребер в конденсации графа.

Тесты:

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

#include <iostream>
#include <vector>
#include <set>

using namespace std;

struct vertex{          
    int used,colour;
    vector<int>graph,graph_transposed;
};

void dfs_g(int v, vector<vertex>&components, vector<int>&list){
    components[v].used = 1;
    for (int i = 0; i < components[v].graph.size(); i++){
        if(components[components[v].graph[i]].used!=1) dfs_g(components[v].graph[i],components,list);
    }
    list.push_back(v);
}

void dfs_tg(int v, int color, vector<vertex>&components){
    components[v].used=2;
    components[v].colour=color;
    for (int i=0; i<components[v].graph_transposed.size(); i++){
        if (components[components[v].graph_transposed[i]].used != 2)dfs_tg(components[v].graph_transposed[i],color,components);
    }
}

int main(){
    int n,m,color=0,answer=0;
    cin>>n>>m;
    vector<int>list(n);
    vector<vertex>components(n);
    set<int>ribs[10000];
    for(int i=0; i<m; i++){
        int a,b;
        cin>>a>>b;
        components[a-1].graph.push_back(b-1);
        components[b-1].graph_transposed.push_back(a-1);
    }

    for (int i=0; i<n; i++){
        if (components[i].used!=1)dfs_g(i,components,list);
    }
    for (int i=list.size()-1; i>=0; i--){
        if (components[list[i]].used != 2){
            dfs_tg(list[i], color, components);
            color++;
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<components[i].graph.size(); j++){
            if(components[i].colour!=components[components[i].graph[j]].colour){
                ribs[components[i].colour].insert(components[components[i].graph[j]].colour);
            }
        }
    }
    for(int i=0; i<10000; i++)answer+=ribs[i].size();
    cout<<answer;
    return 0;
}

#include <iostream>

#include <vector>

#include <set>

using namespace std;

struct vertex{

int used,colour;

vector<int>graph,graph_transposed;

};

void dfs_g(int v, vector<vertex>&components, vector<int>&list){

components[v].used = 1;

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

if(components[components[v].graph[i]].used!=1) dfs_g(components[v].graph[i],components,list);

}

list.push_back(v);

}

void dfs_tg(int v, int color, vector<vertex>&components){

components[v].used=2;

components[v].colour=color;

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

if (components[components[v].graph_transposed[i]].used != 2)dfs_tg(components[v].graph_transposed[i],color,components);

}

int main(){

int n,m,color=0,answer=0;

cin>>n>>m;

vector<int>list(n);

vector<vertex>components(n);

set<int>ribs[10000];

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

int a,b;

cin>>a>>b;

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

components[b-1].graph_transposed.push_back(a-1);

}

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

if (components[i].used!=1)dfs_g(i,components,list);

}

for (int i=list.size()-1; i>=0; i--){

if (components[list[i]].used != 2){

dfs_tg(list[i], color, components);

color++;

}

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

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

if(components[i].colour!=components[components[i].graph[j]].colour){

ribs[components[i].colour].insert(components[components[i].graph[j]].colour);

}

for(int i=0; i<10000; i++)answer+=ribs[i].size();

cout<<answer;

return 0;

}

Описание решения задачи:

Компонентой сильной связности называется такое подмножество вершин C, что любые две вершины этого подмножества достижимы друг из друга. Отсюда следует, что конденсация это граф, получаемый из исходного графа сжатием каждой компоненты сильной связности в одну вершину. Отсюда имеем структуру [latex]vertex[/latex]. Основным фундаментом данного алгоритма является следующая теорема: Пусть [latex]C[/latex] и [latex]{C}'[/latex] — две различные компоненты сильной связности, и пусть в графе конденсации между ними есть ребро ([latex]C[/latex],[latex]C'[/latex]). Тогда время выхода из [latex]C[/latex] будет больше, чем время выхода из [latex]{C}'[/latex]. Базируясь на этом, выполним серию обходов в глубину с помощью функции [latex]dfs[/latex] _ [latex]g[/latex], посещая весь граф. С визитом всех вершин графа,запоминаем для каждой время выхода, записывая это в созданный [latex]list[/latex]. Далее строится транспонированный граф. Запускаем серию обходов в глубину(функция [latex]dfs[/latex] _ [latex]tg[/latex]) этого графа в порядке, определяемом списком [latex]list[/latex] (а именно, в обратном порядке, т.е. в порядке уменьшения времени выхода). Каждое множество вершин, достигнутое в результате рекурсивного запуска обхода, и будет очередной компонентой сильной связности. Окрасим все вершины каждой сильной компоненты связности в один уникальный цвет, для этого зададим в структуре параметр [latex]colour[/latex]. Число цветов окраски будет равно количеству компонент сильной связности. Далее перебираем все ребра исходного графа. Если ребро соединяет вершины разного цвета, то оно принадлежит конденсации графа. Для каждого ребра ([latex]a[/latex], [latex]b[/latex]), для которого [latex]components[a].colour[/latex] [latex]≠[/latex] [latex]components[b].colour[/latex], занесем во множество [latex]ribs[/latex] данную пару. Количество элементов во множестве [latex]ribs[/latex] будет равняться числу ребер в конденсации графа.

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

Related Images:

6130. Дек неограниченного размера

21/05/2017 by Валентина Андриеш

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

push_front

Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back

Извлечь из дека последний элемент. Программа должна вывести его значение.

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Размер дека должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций pop_front, pop_back, front, back программа должна проверять, содержится ли в деке хотя бы один элемент. Если во входных данных встречается операция pop_front, pop_back, front, back, и при этом дек пуст, то программа должна вместо числового значения вывести строку error.

Тесты

Входные данные	Выходные данные
push_front 1	ok
push_back 9	ok
push_front 2	ok
push_back 3	ok
size	4
pop_front	2
pop_back	3
size	2
front	1
back	9
clear	ok
size	0
back	error
exit	bye

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

struct Node{                //структура звена списка 
    int value;          //передаваемое значение
    Node *next, *prev;      //указатели на следующий и предыдущий элементы
};

struct deque{
    Node *head=nullptr;     //инициализация начала и конца списка, размера дека 
    Node *tail=nullptr;
    int count=0;
    void push_back(int num){
        Node* element=new Node; //выделение памяти под новый элемент структуры
        element->value=num;  //добавляем значение в структуру
        count++;
        if(!head){          //если список пуск
            head=element;       //т.к элемент единственный, 
            tail=head;      //он является и хвостом и головой
        }
        else{
            element->prev=tail; //предыдущий элемент списка относительно добавленного, будет последним(хвостом)
            tail->next=element; //следующий элемент за хвостом это добавляемый элемент списка
            tail=element;       //присваивание элементу статуса хвоста
        }
        cout<<"ok"<<endl;
    }
    void push_front(int num){
        Node *element=new Node;
        element->value=num;
        count++;
        if(!head){
            head=element;
            tail=head;
        }
        else{
            element->next=head;      //следующий элемент за добавляемым элементом является хвост
            head->prev=element;      //перед головой находится добавляемый элемент
            head=element;           //присваивание элементу статуса головы
        }
        cout<<"ok"<<endl;
    }
    void pop_back(){
        if(count!=0){               //если дек не пустой
            cout<<tail->value<<endl;
            if(count>1){         //если в деке находится больше одного элемента
                Node *element=tail;     //указываем на то, что будет использоваться хвост
                tail=tail->prev; //присваиваем статус хвоста предыдущему элементу
                tail->next=nullptr;     //указываем на то, что за элементом пусто
                delete element;     //удаляем бывший хвост
                count--;        //уменьшаем размер дека
            }
            else{               //если в деке находится всего один элемент
                head=tail=0;        //присваиваем ему значение ноль
                count--;        //уменьшаем размер дека
            }
        }
        else cout<<"error"<<endl;
    }
    void pop_front(){
        if(count!=0){
            cout<<head->value<<endl;
            if(head->next){          //если в деке больше одного элемента 
                Node *element=head; //указываем на то, что будем использовать голову
                head=head->next; //присваиваем статус головы следующему за бывшей головой элементу 
                head->prev=nullptr;  //указываем на то, что перед головой пусто
                delete element;     //удаляем бывшую голову
                count--;        //уменьшаем размер дека
            }
            else if(head==tail){    //если элемент один в деке
                head->next=nullptr;  //указываем, что за головой пусто
                head=nullptr;       //указываем на то, что голова тоже пуста
                delete head;        //удаляем единственный элемент
                count=0;        //присваиваем ноль размеру дека
            }
        }
        else cout<<"error"<<endl;
    }
    void back(){
        if(count!=0)cout<<tail->value<<endl; //выводим значение хвоста
        else cout<<"error"<<endl;
    }
    void front(){
        if(count!=0)cout<<head->value<<endl; //выводим значение головы
        else cout<<"error"<<endl;
    }
    void size(){
        cout<<count<<endl;          //выводим размер дека
    }
    void clear(){
        count=0;               //присваиваем размеру дека ноль
        cout<<"ok"<<endl;
        while(head)             //цикл: пока по адресу головы что-то лежит
     {
         tail=head->next;        //присваиваем статус хвоста следующему элементу, что лежит за головой 
         delete head;           //удаляем первый элемент дека
         head=tail;             //указываем на то, что хвост принимает статус головы
     }
    }
    void exit(){
        cout<<"bye";
    }
};

int main() {
    deque deq;
    string str;
    while(cin>>str){
        if(str=="push_front"){
            int num;
            cin>>num;
            deq.push_front(num);
        }
        if(str=="push_back"){
            int num;
            cin>>num;
            deq.push_back(num);
        }
        if(str=="pop_front")deq.pop_front();
        if(str=="pop_back")deq.pop_back();
        if(str=="clear")deq.clear();
        if(str=="size")deq.size();
        if(str=="front")deq.front();
        if(str=="back")deq.back();
        if(str=="exit"){
            deq.exit();
            break;
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include <iostream>

#include <string>

using namespace std;

struct Node{ //структура звена списка

int value; //передаваемое значение

Node *next, *prev; //указатели на следующий и предыдущий элементы

};

struct deque{

Node *head=nullptr; //инициализация начала и конца списка, размера дека

Node *tail=nullptr;

int count=0;

void push_back(int num){

Node* element=new Node; //выделение памяти под новый элемент структуры

element->value=num; //добавляем значение в структуру

count++;

if(!head){ //если список пуск

head=element; //т.к элемент единственный,

tail=head; //он является и хвостом и головой

}

else{

element->prev=tail; //предыдущий элемент списка относительно добавленного, будет последним(хвостом)

tail->next=element; //следующий элемент за хвостом это добавляемый элемент списка

tail=element; //присваивание элементу статуса хвоста

}

cout<<"ok"<<endl;

}

void push_front(int num){

Node *element=new Node;

element->value=num;

count++;

if(!head){

head=element;

tail=head;

}

else{

element->next=head; //следующий элемент за добавляемым элементом является хвост

head->prev=element; //перед головой находится добавляемый элемент

head=element; //присваивание элементу статуса головы

}

cout<<"ok"<<endl;

}

void pop_back(){

if(count!=0){ //если дек не пустой

cout<<tail->value<<endl;

if(count>1){ //если в деке находится больше одного элемента

Node *element=tail; //указываем на то, что будет использоваться хвост

tail=tail->prev; //присваиваем статус хвоста предыдущему элементу

tail->next=nullptr; //указываем на то, что за элементом пусто

delete element; //удаляем бывший хвост

count--; //уменьшаем размер дека

}

else{ //если в деке находится всего один элемент

head=tail=0; //присваиваем ему значение ноль

count--; //уменьшаем размер дека

}

else cout<<"error"<<endl;

}

void pop_front(){

if(count!=0){

cout<<head->value<<endl;

if(head->next){ //если в деке больше одного элемента

Node *element=head; //указываем на то, что будем использовать голову

head=head->next; //присваиваем статус головы следующему за бывшей головой элементу

head->prev=nullptr; //указываем на то, что перед головой пусто

delete element; //удаляем бывшую голову

count--; //уменьшаем размер дека

}

else if(head==tail){ //если элемент один в деке

head->next=nullptr; //указываем, что за головой пусто

head=nullptr; //указываем на то, что голова тоже пуста

delete head; //удаляем единственный элемент

count=0; //присваиваем ноль размеру дека

}

else cout<<"error"<<endl;

}

void back(){

if(count!=0)cout<<tail->value<<endl; //выводим значение хвоста

else cout<<"error"<<endl;

}

void front(){

if(count!=0)cout<<head->value<<endl; //выводим значение головы

else cout<<"error"<<endl;

}

void size(){

cout<<count<<endl; //выводим размер дека

}

void clear(){

count=0; //присваиваем размеру дека ноль

cout<<"ok"<<endl;

while(head) //цикл: пока по адресу головы что-то лежит

{

tail=head->next; //присваиваем статус хвоста следующему элементу, что лежит за головой

delete head; //удаляем первый элемент дека

head=tail; //указываем на то, что хвост принимает статус головы

}

void exit(){

cout<<"bye";

}

};

int main() {

deque deq;

string str;

while(cin>>str){

if(str=="push_front"){

int num;

cin>>num;

deq.push_front(num);

}

if(str=="push_back"){

int num;

cin>>num;

deq.push_back(num);

}

if(str=="pop_front")deq.pop_front();

if(str=="pop_back")deq.pop_back();

if(str=="clear")deq.clear();

if(str=="size")deq.size();

if(str=="front")deq.front();

if(str=="back")deq.back();

if(str=="exit"){

deq.exit();

break;

}

return 0;

}

Описание решения задачи:
Для решения данной задачи использовался двунаправленный линейный список. Каждый узел ДЛС содержит два поля указателей — на следующий и на предыдущий узел. Для этого в задаче была создана структура [latex]Node[/latex]. Указателем на адрес начала списка и конца, соответственно, выступают узлы [latex]head[/latex] и [latex]tail[/latex], изначально инициализированные нулем.

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

Условие задачи
Код задачи на с++
Засчитанное решение

Related Images:

Ю 2.27. Шашечный эндшпиль

19/05/2017 by Валентина Андриеш

Задача из сборника задач по программированию Юркина А.Г. 2002 г.
Условие задачи:
В шашечном эндшпиле остались белая дамка и две черных пешки, позиции которых известны. Ход белых. Сможет ли дамка срубить одну или сразу обе пешки?
Continue reading →

Related Images:

A322. Максимальная сумма делителей

17/12/2016 by Валентина Андриеш

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

Входные данные:
— [latex]n[/latex] — промежуток чисел(от 1 до [latex]n[/latex]);

Выходные данные:
— [latex]max[/latex] _ [latex]sum[/latex] — максимальная сумма делителей числа на этом промежутке;
— [latex]max[/latex] _ [latex]number[/latex] — натуральное число с этой суммой;

Тесты:

[latex]n[/latex]	[latex]max[/latex] _ [latex]number[/latex]	[latex]max[/latex] _ [latex]sum[/latex]
100	96	252
8743	8400	30752
23000	22680	87120

Код на языке C++:

#include <iostream>
#include <cmath>
using namespace std;
 
int sum_dividers(int n){
    int sum=0;
    for(int i=1; i<sqrt(n); i++){
        if((n%i)==0)sum+=i+(n/i);
    }
    int i=sqrt(n);
    if(i*i==n)sum+=i;
    return sum;
}
 
int main() {
    int n;
    cin>>n;
    int max_sum=0;
    int max_number=0;
    int j;
    for(j=1; j<=n; j++){
        int s=sum_dividers(j);
        if(max_sum<s){
            max_sum=s;
            max_number=j;
        }
    }
    cout<<max_number<<" "<<max_sum;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int sum_dividers(int n){

int sum=0;

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

if((n%i)==0)sum+=i+(n/i);

}

int i=sqrt(n);

if(i*i==n)sum+=i;

return sum;

}

int main() {

int n;

cin>>n;

int max_sum=0;

int max_number=0;

int j;

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

int s=sum_dividers(j);

if(max_sum<s){

max_sum=s;

max_number=j;

}

cout<<max_number<<" "<<max_sum;

return 0;

}

Код на языке Java:

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

class Ideone
{
    static int sum_dividers(int n){
        int sum=0;
            for(int i=1; i<Math.sqrt(n); i++){
                    if((n%i)==0)sum+=i+(n/i);
            }
            double i=Math.round(Math.sqrt(n));
            if(i*i==n)sum+=i;
            return sum;
    }
    
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int max_sum=0;
        int max_number=0;
        int j;
        for(j=1; j<=n; j++){
            int s=sum_dividers(j);
            if(max_sum<s){
                        max_sum=s;
                        max_number=j;
            }
        }
        System.out.println(max_number+" "+max_sum);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

static int sum_dividers(int n){

int sum=0;

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

if((n%i)==0)sum+=i+(n/i);

}

double i=Math.round(Math.sqrt(n));

if(i*i==n)sum+=i;

return sum;

}

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

{

Scanner in = new Scanner(System.in);

int n=in.nextInt();

int max_sum=0;

int max_number=0;

int j;

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

int s=sum_dividers(j);

if(max_sum<s){

max_sum=s;

max_number=j;

}

System.out.println(max_number+" "+max_sum);

}

Решение задачи:
Для нахождения суммы делителей используется функция [latex]sum[/latex] _ [latex]dividers[/latex], которая в созданном цикле сначала находит все делители числа, а после суммирует их, присваивая значение переменной [latex]sum[/latex]. Создав в главной функции [latex]main[/latex] еще один цикл со счетчиком от 1 до [latex]n[/latex], подставляю в предыдущую функцию [latex]sum[/latex] _ [latex]dividers[/latex] все натуральные числа на выбранном промежутке. C помощью свободных переменных [latex]max[/latex] _ [latex]sum[/latex] и [latex]max[/latex] _ [latex]number[/latex] нахожу максимальное значение сумм и соответствующее ему натуральное число.

Код программы на C++: Ideone
Код программы на Java: Ideone
Условия задачи(стр.134): 322

Related Images:

MS13. Решение квадратных уравнений

16/12/2016 by Валентина Андриеш

Условие задачи:
Каждая четвёрка чисел входного потока представляет собой квадратное уравнение в такой форме $ax^2+bx+c=d.$ Выпишите через запятую решения этих уравнений (если это возможно).

Тесты:

Входной поток чисел	Корни уравнений
1 -6 8 0 1 12 20 0	2, 4; -10, -2;
1 1 -6 -2 1 -2 10 0	-2.56155, 1.56155; нет корней;
2 -0.5 2.2 0 5 0 -25 0	нет корней; -2.23607, 2.23607;

Код на языке C++:

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

int main() {
    double a, b, c, d, D;
    double x1,x2,x3;
    while(cin>>a>>b>>c>>d){
        D=b*b-4*a*(c-d);
        if(D>0)
        {
            x1=(-b-sqrt(D))/(2*a);
            x2=(-b+sqrt(D))/(2*a);
            cout<<x1<<", "<<x2<<"; ";
        }
        else
        {
            if(D==0)
            {
                x3=(-b)/(2*a);
                cout<<x3<<"; ";
            }
            else cout<<"нет корней"<<"; ";
        }
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double a, b, c, d, D;

double x1,x2,x3;

while(cin>>a>>b>>c>>d){

D=b*b-4*a*(c-d);

if(D>0)

{

x1=(-b-sqrt(D))/(2*a);

x2=(-b+sqrt(D))/(2*a);

cout<<x1<<", "<<x2<<"; ";

}

else

{

if(D==0)

{

x3=(-b)/(2*a);

cout<<x3<<"; ";

}

else cout<<"нет корней"<<"; ";

}

return 0;

}

Код на языке Java:

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        double a,b,c,d,D;
        double x1,x2,x3;
        Scanner in = new Scanner(System.in);
        while (in.hasNextDouble()){
                    a = in.nextDouble();
            b = in.nextDouble();
                    c = in.nextDouble();
                    d = in.nextDouble();
                    D=b*b-4*a*(c-d);
                    if(D>0){
                        x1=(-b-Math.sqrt(D))/(2*a);
                        x2=(-b+Math.sqrt(D))/(2*a);
                        System.out.println(x1+" "+x2+";");
                    }
                    else{
                        if(D==0){
                            x3=(-b)/(2*a);
                            System.out.println(x3+";");
                        }
                        else System.out.println("нет корней;");
                    }
                }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

double a,b,c,d,D;

double x1,x2,x3;

Scanner in = new Scanner(System.in);

while (in.hasNextDouble()){

a = in.nextDouble();

b = in.nextDouble();

c = in.nextDouble();

d = in.nextDouble();

D=b*b-4*a*(c-d);

if(D>0){

x1=(-b-Math.sqrt(D))/(2*a);

x2=(-b+Math.sqrt(D))/(2*a);

System.out.println(x1+" "+x2+";");

}

else{

if(D==0){

x3=(-b)/(2*a);

System.out.println(x3+";");

}

else System.out.println("нет корней;");

}

Решение задачи:
Для решения этой задачи используется цикл, который выполняется до тех пор, пока в потоке подряд расположены четыре числа, четыре коэффициента, которые стоят перед неизвестными в квадратном уравнении классического вида: [latex]ax^{2}\pm bx\pm c=d[/latex]. Для самого нахождения корней использовалась известная формула [latex]x_{1,2}=\frac{-b-\sqrt{b^{2} \pm 4a(c-d)}}{2a}[/latex]. В коде, для удобства, она была разделена на две части: нахождение дискриминанта [latex]D[/latex] и нахождение самих корней, что возможно (на вещественной числовой оси) лишь при условии [latex]D>0[/latex].

Решение задачи на C++: Ideone
Решение задачи на Java: Ideone

Related Images:

D2575. Сумма ряда

30/10/2016 by Валентина Андриеш

Условие задачи:
Найти сумму сходящегося ряда: [latex]\frac{\cos x-\cos 2x}{1}+\frac{\cos 2x -\cos 3x}{2}+\cdots+\frac{\cos nx-\cos(n+1)x}{n}+\cdots[/latex]

Входные данные:
[latex]x[/latex] — константа;
[latex]number[/latex] — номер искомой частичной суммы;

Выходные данные:
[latex]value[/latex] — значения необходимых слагаемых;
[latex]partial[/latex] _ [latex]amount[/latex] — искомая частичная сумма;

Тесты:

[latex]x[/latex]	[latex]number[/latex]	[latex]value[/latex]	[latex]partial[/latex] _ [latex]amount[/latex]
10	3	-1.24715 0.126915 0.27373	-0.846508
100	4	0.375131 0.254642 0.167733 0.0896382	0.887145
5	5	1.12273 -0.0396918 -0.389257 -0.14578 0.16739	0.715395

Код на языке C++:

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

int main() {
    int number;
    double x;
    cin>>x>>number;
    double value;
    double partial_amount=0;
    int n=1;
    while(n<=number){
        value=(cos((n*x))-cos(((n+1)*x)))/n;
        cout<<value<<" ";
        partial_amount+=value;
        n++;
    }
    cout<<endl;
    cout<<partial_amount;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int number;

double x;

cin>>x>>number;

double value;

double partial_amount=0;

int n=1;

while(n<=number){

value=(cos((n*x))-cos(((n+1)*x)))/n;

cout<<value<<" ";

partial_amount+=value;

n++;

}

cout<<endl;

cout<<partial_amount;

return 0;

}

Код на языке Java:

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        int number=in.nextInt();
        double x=in.nextDouble();
        double value;
        double partial_amount=0;
        int n=1;
        while(n<=number){
            value=(Math.cos((n*x))-Math.cos(((n+1)*x)))/n;
            System.out.println(value + " " );
            partial_amount+=value;
            n++;
        }
        System.out.println("\n"+partial_amount);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int number=in.nextInt();

double x=in.nextDouble();

double value;

double partial_amount=0;

int n=1;

while(n<=number){

value=(Math.cos((n*x))-Math.cos(((n+1)*x)))/n;

System.out.println(value + " " );

partial_amount+=value;

n++;

}

System.out.println("\n"+partial_amount);

}

Решение задачи:
Под словом «ряд» в математическом анализе понимают сумму бесконечного числа слагаемых. Зададим цикл с счетчиком [latex]n[/latex] от 1 до заданного пользователем числа [latex]number[/latex]. Именно такое количество необходимых слагаемых [latex]value=\frac{\cos nx -\cos (n+1)x}{n}[/latex] будет найдено на каждом шаге цикла для последующего суммирования и нахождения искомой частичной суммы.

Код задачи на C++: Ideone
Код задачи на Java: Ideone

Related Images:

KM139. Параллелограмм

01/10/2016 by Валентина Андриеш

Задача из журнала «Квант» №4 1972 г.
Из вершины [latex]B[/latex] параллелограмма [latex]ABCD[/latex] проведены его высоты [latex]BK[/latex] и [latex]BH[/latex]. Выразите расстояние от точки [latex]B[/latex] до точки пересечения высот треугольника [latex]BKH[/latex] через длины отрезков [latex]KH = a[/latex] и [latex]BD = b[/latex].

Входные данные:
Длины отрезков [latex]a[/latex], [latex]b[/latex]

Выходные данные:
Расстояние от точки [latex]B[/latex] до точки [latex]O[/latex] — точки пересечения высот треугольника [latex]BKH[/latex] ([latex]c[/latex])

Тесты:

b	a	c
10	6	8
5	3	4
3	5	inf (Infinity)

Код программы на С++:

#include <iostream>
#include <cmath>
#include <limits>
using namespace std;
int main() {
    double b,a;
    double inf = std::numeric_limits<double>::infinity();
    double c;
    cin>>b>>a;
    c=(b<a)?inf:sqrt(b*b-a*a);
    cout<<c;
    return 0;
}

#include <iostream>

#include <cmath>

#include <limits>

using namespace std;

int main() {

double b,a;

double inf = std::numeric_limits<double>::infinity();

double c;

cin>>b>>a;

c=(b<a)?inf:sqrt(b*b-a*a);

cout<<c;

return 0;

}

Код программы на Java:

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        double b=in.nextDouble();
        double a=in.nextDouble();
        double inf = 1.0 / 0;
        double c;
        c=(b<a)?inf:Math.sqrt(b*b-a*a);
        System.out.println(c);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

double b=in.nextDouble();

double a=in.nextDouble();

double inf = 1.0 / 0;

double c;

c=(b<a)?inf:Math.sqrt(b*b-a*a);

System.out.println(c);

}

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

Рассмотрим параллелограмм [latex]ABCD[/latex]. Проведем высоты [latex]BH[/latex] и [latex]BK[/latex] соответственно к сторонам [latex]AD[/latex] и [latex]DC[/latex]. Соединив точки [latex]K[/latex] и [latex]H[/latex] линией, получаем треугольник [latex]BKH[/latex]. В нем проведем три высоты [latex]BD[/latex], [latex]HM[/latex], [latex]KE[/latex] к сторонам [latex]HK[/latex], [latex]BK[/latex], [latex]HB[/latex]. Точкой пересечения высот в треугольнике является точка [latex]O[/latex].
Проведем в параллелограмме высоту [latex]DL[/latex] к стороне [latex]BC[/latex]. Соединив точки [latex]L[/latex] и [latex]K[/latex] получаем треугольник [latex]LDK[/latex]. Если сдвинуть (параллельно) треугольник [latex]BHO[/latex] так, чтобы точка [latex]H[/latex] попала в точку [latex]D[/latex], то он полностью совпадет с треугольником [latex]LKD[/latex], поскольку отрезок [latex]HO[/latex] параллелен и равен [latex]DK[/latex], а отрезок [latex]BH[/latex] параллелен и равен [latex]LD[/latex]. Следовательно, [latex]BO=LK[/latex] и два треугольника равны.
Рассмотрим прямоугольный треугольник [latex]HKL[/latex], в котором сторона [latex]HK=a[/latex] и [latex]HL=b[/latex] по условию. По теореме Пифагора отыщем сторону KL: [latex]KL=\sqrt[]{b^{2}-a^{2}}[/latex].
Так как треугольник [latex]BOH[/latex] и треугольник [latex]LKD[/latex] равны, получаем что [latex]KL=BO[/latex]

Решение задачи на C++
Решение задачи на Java

Условие задачи можно найти здесь: http://www.kvant.info/zkm_tex/zkm_main.pdf

Related Images:

ML 36. Движение катера

27/09/2016 by Валентина Андриеш

Задача. Катер движется по течению реки из пункта в A в пункт B и обратно с собственной скоростью [latex]v[/latex] км/час. Скорость течения постоянна — [latex]u[/latex] км/час. Расстояние между пунктами составляет [latex]s[/latex] км. Для любых неотрицательных действительных значений расстояния и скоростей вычислите время в пути.

Решение. Пусть катер движется со скоростью [latex]v[/latex] км/час, соответственно, учитывая скорость течения [latex]u[/latex] км/час, скорость катера движущегося по течению равна [latex]v+u[/latex] км/час и против течения — [latex]v-u[/latex] км/час. Используя физическую формулу [latex]t=\frac{s}{v}[/latex], где [latex]t[/latex]-время, [latex]s[/latex]-путь, [latex]v[/latex]-скорость, можем выразить время всего пути [latex]t=\frac{s}{v+u}+\frac{s}{v-u}[/latex]. Так как физическая величина [latex]t[/latex] всегда больше 0, и по математическому свойству делитель дроби не должен равняться нулю, имеем ограничение: [latex]v>u[/latex];

Решение на языке C++ имеет вид:

#include <iostream>
#include <limits> 
using namespace std; 
int main() 
{ 
    double u, v, s, t; 
    double inf = std::numeric_limits<double>::infinity(); 
    cin >> u >> v >> s;
    t = (v <= u) ? inf : s / ( v + u ) + s / ( v - u );
    cout << t; 
    return 0; 
}