e-olymp 4853. Кратчайший путь

26/06/2018 by Андрей Лисовой

Задача

Задан неориентированный граф.
Найдите кратчайший путь от вершины $a$ до вершины $b.$

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

В первой строке находится два целых числа $n$ и $m$ $(1 \leqslant n \leqslant 50000,$ $1 \leqslant m \leqslant 100000)$ — количества вершин и рёбер соответственно. Во второй строке заданы целые числа $a$ и $b$ — стартовая и конечная вершина соответственно. Далее идут $m$ строк, описывающие рёбра.

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

Если пути между $a$ и $b$ нет, то выведите $-1.$ Иначе выведите в первой строке длину $l$ кратчайшего пути между этими двумя вершинами в рёбрах, а во второй строке выведите $l + 1$ число — вершины этого пути.

Тесты

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

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

#include <iostream>
#include <vector>
using namespace std;
 
int n,m,a,b,count = 0;
vector<vector<int> > graf; vector<int> ver; vector<int> family; bool ok = false; vector<int> ans; vector<bool> popa;
 
int bfs(int beg, int end){ // функция которая добавляет вершины в вектор вершин,которые мы просмотрим,и помечает их как уже проверенные
    count++;
    if(beg == end){
        ok = true;
        return 1;
    }else{
        for(int i = graf[beg].size() - 1;i >= 0;i--){
            if(!popa[graf[beg][i]]){
                ver.push_back(graf[beg][i]);
                family.push_back(beg);
                popa[graf[beg][i]] = true;
            }
        }
    }
    return 0;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    cin >> a >> b;
    for(int i = 0 ; i <= n; i++){ // создаем векто ввекторов
            graf.push_back(ans);
            popa.push_back(false);
    }
    ver.push_back(a);family.push_back(a);
    for(int i = 0; i < m; i++){ //в вектор вершины добавляем те вершины,с которым она связанна 
        int x,y;
        cin >> x >> y;
        if(x != y){ // проверка на петлю
            graf[x].push_back(y);
            graf[y].push_back(x);
        }
    }
    if(!graf[a].empty()){ //если вершины начала не изолированна 
        while(!ok && count < ver.size() ){ //цикл,пока мы не найдем конечную вершину,или если мы не прошли все вершины в векторе "плана"
            if(bfs(ver[count],b)){ //если мы нашли выход,то начать восстанавливать пути
                count--;// Нам надо начать с последней вершины,а это count - 1 вершина
                int p = 1; //Новая переменная,которая нужна,для нахождения первого вхождения "отца" данной вершины
                ans.push_back(b);//вектор ответа
                while(ver[count] != a){ // пока не дошли до начальной вершины
                    while(ver[p] != family[count]){//двигаемся слева пройденных по вектору вершин плана,и ищем первое вхождение вершины ОТЦА
                        p++;
                    }
                    ans.push_back(ver[p]);//добавляем в ответ вершину,из которой мы попали в предыдущую (отца)
                    count = p;// теперь ищем отца отца и так далее,пока не дойдем до начальной вершины 
                    p = 1;
                }
            }
        }
        if(ans.size() > 0){ // если вектор ответа не пуст(имеет хотябы одну вершины из пути)
            cout << ans.size()-1 << endl;
            for(int i = ans.size()-1; i >= 0; i--){
                cout << ans[i] << " "; // выводим ответ справа на лево,так сказано в условии
            }
        }else{ // иначе -1
            cout << "-1\n";
        }
    }else{//если начальная вершина изолирована,то сразу выводим -1
        cout << "-1\n";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int n,m,a,b,count = 0;

vector<vector<int> > graf; vector<int> ver; vector<int> family; bool ok = false; vector<int> ans; vector<bool> popa;

int bfs(int beg, int end){ // функция которая добавляет вершины в вектор вершин,которые мы просмотрим,и помечает их как уже проверенные

count++;

if(beg == end){

ok = true;

return 1;

}else{

for(int i = graf[beg].size() - 1;i >= 0;i--){

if(!popa[graf[beg][i]]){

ver.push_back(graf[beg][i]);

family.push_back(beg);

popa[graf[beg][i]] = true;

}

return 0;

}

int main() {

ios::sync_with_stdio(false);

cin >> n >> m;

cin >> a >> b;

for(int i = 0 ; i <= n; i++){ // создаем векто ввекторов

graf.push_back(ans);

popa.push_back(false);

}

ver.push_back(a);family.push_back(a);

for(int i = 0; i < m; i++){ //в вектор вершины добавляем те вершины,с которым она связанна

int x,y;

cin >> x >> y;

if(x != y){ // проверка на петлю

graf[x].push_back(y);

graf[y].push_back(x);

}

if(!graf[a].empty()){ //если вершины начала не изолированна

while(!ok && count < ver.size() ){ //цикл,пока мы не найдем конечную вершину,или если мы не прошли все вершины в векторе "плана"

if(bfs(ver[count],b)){ //если мы нашли выход,то начать восстанавливать пути

count--;// Нам надо начать с последней вершины,а это count - 1 вершина

int p = 1; //Новая переменная,которая нужна,для нахождения первого вхождения "отца" данной вершины

ans.push_back(b);//вектор ответа

while(ver[count] != a){ // пока не дошли до начальной вершины

while(ver[p] != family[count]){//двигаемся слева пройденных по вектору вершин плана,и ищем первое вхождение вершины ОТЦА

p++;

}

ans.push_back(ver[p]);//добавляем в ответ вершину,из которой мы попали в предыдущую (отца)

count = p;// теперь ищем отца отца и так далее,пока не дойдем до начальной вершины

p = 1;

}

if(ans.size() > 0){ // если вектор ответа не пуст(имеет хотябы одну вершины из пути)

cout << ans.size()-1 << endl;

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

cout << ans[i] << " "; // выводим ответ справа на лево,так сказано в условии

}

}else{ // иначе -1

cout << "-1\n";

}

}else{//если начальная вершина изолирована,то сразу выводим -1

cout << "-1\n";

}

return 0;

}

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

Раз нам надо найти кратчайший путь, то будем использовать BFS — поиск в ширину. Мы будем постепенно просматривать вершины, внося в «план» те вершины с которыми они связанны и которые еще не внесены в «план». Для удобства используем вектора. В начале создаем вектор векторов, как бы это тавтологически не звучало, для этого я использовал вектор ответа, как объект, который добавлялся в вектор graf, выступающий в роли графа, причем мы добавляем сразу к вершинам graf[x].pushback(y);. То есть $x$-ая вершина получает связь с вершиной $y,$ и наоборот, поскольку граф неориентированный. После чего, проверяем связанна ли начальная вершина хоть с кем-нибудь, если да, то работаем циклом while, пока не наткнемся на начальную вершину, или все вершины в «плане» не будут пройдены. Если мы дошли до конечной вершины, то функция bfs вернет $1,$ что запустит тело if и мы начнем восстанавливать путь. Для этого мы заводили дополнительный вектор family в который по мере добавления в «план», также добавлялись и вершины «отцы»(откуда пришла $i$-ая вершина). Восстановленный путь записываем в вектор ans. После чего while прекращает свою работу и мы переходим к выводу результата. Если вектор ответа пуст, то выводим $-1,$ иначе выводим количество вершин, участвующих в построении пути и сам путь. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

Related Images:

e-olymp 1477. Наибольшее среднее

25/06/2018 by Андрей Лисовой

Задача

На доске выписаны $n$ целых чисел. Все они пронумерованы от $1$ до $n.$ Разрешается выбрать два произвольных числа, вытереть оба с доски и написать новое число, равное их среднему арифметическому. Новое число получает номер $n + 1.$ После этого снова выбираются два числа и вместо них записывается их среднее арифметическое, которому дается номер $n + 2$ и т.д. Так продолжается до тех пор, пока на доске не останется только одно число. Чем больше будет это число, тем более успешной считается последовательность действий.

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

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

В первой строке записано целое число $n$ $(1 \leqslant n \leqslant 10^5).$ Во второй строке задаются $n$ целых чисел, которые были первоначально записаны на доске. Все числа лежат в диапазоне от $-10000$ до $10000.$

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

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

Тесты

Входные данные	Выходные данные
$3$ $7\;2\;4$	$2\;3$ $1\;4$
$4$ $6\;2\;7\;1$	$2\;4$ $1\;5$ $3\;6$
$4$ $12\;4\;7\;2$	$2\;4$ $3\;5$ $1\;6$
$5$ $234\;2\;5\;54\;5$	$2\;3$ $5\;6$ $4\;7$ $1\;8$

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

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

int main() {
    multimap <double,int> multimap;
    int n;
    cin >> n;
    int element;
    for(int i = 1; i <= n; i++) {
        cin >> element;
        multimap.insert(pair<double,int>(element, i));
    }
    while(multimap.size() != 1) {
        pair<double,int> x = *multimap.begin();
        multimap.erase(multimap.begin());
        pair<double,int> y = *multimap.begin();
        multimap.erase(multimap.begin());
        cout << min(x.second, y.second) << " " << max(x.second, y.second) << endl;
        multimap.insert(pair<double,int>((x.first + y.first) / 2, ++n));
    }
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

multimap <double,int> multimap;

int n;

cin >> n;

int element;

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

cin >> element;

multimap.insert(pair<double,int>(element, i));

}

while(multimap.size() != 1) {

pair<double,int> x = *multimap.begin();

multimap.erase(multimap.begin());

pair<double,int> y = *multimap.begin();

multimap.erase(multimap.begin());

cout << min(x.second, y.second) << " " << max(x.second, y.second) << endl;

multimap.insert(pair<double,int>((x.first + y.first) / 2, ++n));

}

return 0;

}

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

Для решения задачи создаем multimap, затем циклом вводим туда пары, где первое значение — это число с потока, а второе — его номер. После этого мы сохраняем первые два значения из multimap, выводим их номера и находим среднее число. Добавляем в multimap пару, где первое значение — это найденное средние двух чисел, а второе — номер. В конце концов мы получим, что в multimap будет всего одна пара и цикл остановит свою работу. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

Related Images:

e-olymp 1607. Число в обратном порядке

24/05/2018 by Андрей Лисовой

Задача

Запишите целое неотрицательное число $n$ в обратном порядке.

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

Одно целое неотрицательное $64$-х разрядное число.

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

Выведите число в обратном порядке.

Тесты

Входные данные	Выходные данные
$1234$	$4321$
$100$	$001$
$34567$	$76543$
$10983743$	$34738901$
$98352374234$	$43247325389$

Код программы(String)

#include <iostream>
using namespace std;

int main() {
    string s;
    cin>>s;
    for(int i=s.length()-1; i>=0; i--) {
        cout<<s[i];
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string s;

cin>>s;

for(int i=s.length()-1; i>=0; i--) {

cout<<s[i];

}

return 0;

}

Решение задачи(String)

Для решения задачи вводим строку. Узнаем ее длину с помощью функции s.length(), затем циклом выводим строку в обратном порядке. Задача решена.

Код программы(C-string)

#include <iostream>
using namespace std;

int main() {
    char x[64];
    int length=0;
    while(cin>>x[length]) {
        length++;
    }
    for(int i=length-1; i>=0; i--) {
        cout<<x[i];
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

char x[64];

int length=0;

while(cin>>x[length]) {

length++;

}

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

cout<<x[i];

}

return 0;

}

Решение задачи(C-string)

Для решения задачи вводим входные данные в массив x[64]. При вводе считаем какое количество символов заполнилось в массив. Затем от этого числа( length) начинаем цикл, который выводит массив в обратном порядке. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com(String)
Код решения на ideone.com(C-string)

Related Images:

e-olymp 4557. Одинокий король

13/05/2018 by Андрей Лисовой

Задача

Одинокий король долго бродил по бесконечной шахматной доске. Известна последовательность из [latex]n[/latex] его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.) — возможные ходы короля показаны на рисунке снизу.

Определите, побывал ли король дважды на одном и том же поле за свои [latex]n[/latex] ходов.

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

В первой строке задано общее число ходов короля [latex]n[/latex] [latex](0 ≤ n ≤ 1000)[/latex]. В последующих [latex]n[/latex] строках заданы направления перемещения короля: строка под номером [latex]i + 1[/latex] задаёт направление перемещения короля на [latex]i[/latex]-ом ходу.

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

Выведите единственное число — номер хода, на котором король впервые попал на какую-то клетку во второй раз. Если же такое событие не произошло, то в первой строке выведите сообщение «Ok» (без кавычек), а во второй — манхэттенское расстояние между начальной и конечной точками путешествия одинокого короля.

Напоминаем, что манхэттенское расстояние между точками с координатами [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex] определяется по формуле: [latex]d = |x_2 — x_1| + |y_2 — y_1|[/latex].

Тесты

Входные данные	Выходные данные
[latex]5[/latex] [latex]1[/latex] [latex]2[/latex] [latex]4[/latex] [latex]7[/latex] [latex]4[/latex]	[latex]4[/latex]
[latex]5[/latex] [latex]1[/latex] [latex]2[/latex] [latex]4[/latex] [latex]6[/latex] [latex]4[/latex]	[latex]Ok[/latex] [latex]2[/latex]
[latex]8[/latex] [latex]3[/latex] [latex]3[/latex] [latex]7[/latex] [latex]7[/latex] [latex]5[/latex] [latex]5[/latex] [latex]3[/latex] [latex]3[/latex]	[latex]3[/latex]
[latex]7[/latex] [latex]2[/latex] [latex]4[/latex] [latex]2[/latex] [latex]8[/latex] [latex]8[/latex] [latex]1[/latex] [latex]5[/latex]	[latex]Ok[/latex] [latex]3[/latex]
[latex]12[/latex] [latex]2[/latex] [latex]3[/latex] [latex]4[/latex] [latex]1[/latex] [latex]3[/latex] [latex]2[/latex] [latex]5[/latex] [latex]6[/latex] [latex]8[/latex] [latex]2[/latex] [latex]1[/latex] [latex]7[/latex]	[latex]10[/latex]

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

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

int x[2001][2001];

int main() {
    int n;
    cin>>n;
    int move;
    int xPos=1001, yPos=1001;
    for(int i=0; i<n; i++) {
        cin>>move;
        if(x[xPos][yPos]==1) { 
            cout<<i;
            return 0;
        }
        else x[xPos][yPos]=1;
        if(move==1) {
            xPos--;
            yPos++;
        }
        if(move==2) {
            yPos++;
        }
        if(move==3) {
            xPos++;
            yPos++;
        }
        if(move==4) {
            xPos++;
        }
        if(move==5) {
            xPos++;
            yPos--;
        }
        if(move==6) {
            yPos--;
        }
        if(move==7) {
            xPos--;
            yPos--;
        }
        if(move==8) {
            xPos--;
        }
    }
    cout<<"Ok"<<endl<<abs(xPos-1001)+abs(yPos-1001);
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int x[2001][2001];

int main() {

int n;

cin>>n;

int move;

int xPos=1001, yPos=1001;

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

cin>>move;

if(x[xPos][yPos]==1) {

cout<<i;

return 0;

}

else x[xPos][yPos]=1;

if(move==1) {

xPos--;

yPos++;

}

if(move==2) {

yPos++;

}

if(move==3) {

xPos++;

yPos++;

}

if(move==4) {

xPos++;

}

if(move==5) {

xPos++;

yPos--;

}

if(move==6) {

yPos--;

}

if(move==7) {

xPos--;

yPos--;

}

if(move==8) {

xPos--;

}

cout<<"Ok"<<endl<<abs(xPos-1001)+abs(yPos-1001);

return 0;

}

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

Создаем глобальный массив(изначально заполненный нулями). Задаем координаты короля по центру int xPos=1001, yPos=1001;. Затем в цикле вводим все ходы короля и проверяем был ли он уже в этой ячейке, если нет — ставим [latex]1[/latex], и вводим ход короля и задаем ему новые координаты, если да — выводим номер хода и завершаем программу. Если король ни разу не попал на ячейку, в которой уже был, то программа находим манхэттенское расстояние между начальными координатами и конечными. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

Related Images:

e-olymp 4281. Невнимательность

02/01/2018 by Андрей Лисовой

Задача

Степан успешно прошёл собеседование и вот уже как четыре месяца работает в одной из самых престижных ИТ компаний. Пришло время сдавать проект менеджеру и Степан, как настоящий студент, всё делает в последнюю ночь перед сдачей. Набирает текст Степан необычно очень быстро, но невнимательно. Вот и в этот раз последнюю часть текста он набрал не обратив внимания, что случайно нажал клавишу [latex]caps[/latex] [latex]lock[/latex]. Таким образом большие буквы были набраны маленькими, а маленькие — большими. Другие символы он набрал верно. Степан настолько устал, что нет сил исправить ошибки, и он решил несколько часов поспать.

Помогите Степану, пока он спит, напишите программу, которая исправляет невнимательно набранный текст.

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

В одной строке содержится невнимательно набранный Степаном текст. В строке не более [latex]500[/latex] символов.

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

Вывести исправленный текст.

Тесты

Входные данные	Выходные данные
[latex]sCHOOL[/latex]	[latex]School[/latex]
[latex]hOME[/latex]	[latex]Home[/latex]
[latex]hAPPY[/latex] [latex]nEW[/latex] [latex]yEAR[/latex]	[latex]Happy[/latex] [latex]New[/latex] [latex]Year[/latex]
[latex]uNIVERSITY[/latex]	[latex]University[/latex]
[latex]mERRY[/latex] [latex]cHRISTMAS[/latex]	[latex]Merry[/latex] [latex]Christmas[/latex]

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

#include <iostream>
#include <cctype>
using namespace std;
 
int main() {
    char a;
    while((a = cin.get()) != EOF){
              if(islower(a)) a = toupper(a);
              else a = tolower(a);
              cout << a;
    }
    return 0;
}

#include <iostream>

#include <cctype>

using namespace std;

int main() {

char a;

while((a = cin.get()) != EOF){

if(islower(a)) a = toupper(a);

else a = tolower(a);

cout << a;

}

return 0;

}

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

Для решения задачи использовали библиотеку cctype. Вводим по одному символу до конца ввода и проверяем каким регистром написан символ c помощью функции islower(a). Меняем его на обратный ( функция toupper(a) или tolower(a) ) и выводим символ. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

Related Images:

e-olymp 9. N-значные числа

02/01/2018 by Андрей Лисовой

Задача

Найти количество [latex]N[/latex]-значных чисел, у которых сумма цифр равна их произведению. Вывести наименьшее среди таких чисел для заданного [latex]N[/latex] ([latex]N < 10[/latex]).

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

Число [latex]N[/latex] не превышающее [latex]10[/latex].

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

В выходном файле через пробел вывести [latex]2[/latex] числа: количество искомых чисел и наименьшее среди них.

Тесты

Входные данные	Выходные данные
[latex]1[/latex]	[latex]10[/latex] [latex]0[/latex]
[latex]2[/latex]	[latex]1[/latex] [latex]22[/latex]
[latex]4[/latex]	[latex]12[/latex] [latex]1124[/latex]
[latex]5[/latex]	[latex]40[/latex] [latex]11125[/latex]
[latex]9[/latex]	[latex]144[/latex] [latex]111111129[/latex]

Код программы (Цикл)

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

int Sum(int a) {
    int sum=0;
    while(a>0) {
        sum+=a%10;
        a/=10;
    }
    return sum;
}

int Mult(int a) {
    int mult=1;
    while(a>0) {
        mult*=a%10;
        a/=10;
    }
    return mult;
}

int main() {
    int n,ch=0,sum=0,mult=0,a;
    bool b=true;
    cin>>n;
    if(n==1) cout<<10<<" "<<0;
    else {
        if(n>1 and n<8) {
            for(int i=pow(10,n-1); i<pow(10,n); i++) {
                sum=Sum(i);
                mult=Mult(i);
                if((sum==mult) and b==true) {a=i;ch++;b=false;}
                else {
                    if(sum==mult) ch++;
                }
            }
            cout<<ch<<" "<<a;
        }
        else {
            if(n==8) cout<<224<<" "<<11111128;
            if(n==9) cout<<144<<" "<<111111129;
        }
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int Sum(int a) {

int sum=0;

while(a>0) {

sum+=a%10;

a/=10;

}

return sum;

}

int Mult(int a) {

int mult=1;

while(a>0) {

mult*=a%10;

a/=10;

}

return mult;

}

int main() {

int n,ch=0,sum=0,mult=0,a;

bool b=true;

cin>>n;

if(n==1) cout<<10<<" "<<0;

else {

if(n>1 and n<8) {

for(int i=pow(10,n-1); i<pow(10,n); i++) {

sum=Sum(i);

mult=Mult(i);

if((sum==mult) and b==true) {a=i;ch++;b=false;}

else {

if(sum==mult) ch++;

}

cout<<ch<<" "<<a;

}

else {

if(n==8) cout<<224<<" "<<11111128;

if(n==9) cout<<144<<" "<<111111129;

}

return 0;

}

Решение задачи (Цикл)

Для решения задачи напишем функции [latex]Sum[/latex] и [latex]Mult[/latex]. Первая считает сумму цифр [latex]N[/latex]-значного числа, а вторая — произведение цифр. С помощью цикла создаем последовательность [latex]N[/latex]-значных чисел и вводим каждое из них в функции [latex]Sum[/latex] и [latex]Mult[/latex]. Если возращаемые значения равны между собой, то мы выводим данное число и присваиваем переменной [latex]b[/latex] значение [latex]false[/latex]. Также продолжаем считать количество [latex]N[/latex]-значных чисел у которых сумма цифр равна их произведению. Также создаем случаи, когда [latex]N=1[/latex], [latex]N=8[/latex] и [latex]N=9[/latex], ибо в цикле эти значения долго считаются. Задача решена.

Код программы (Массив)

#include <iostream>
using namespace std;

int main() {
    int x[18]= {10,0,1,22,6,123,12,1124,40,11125,30,111126,84,1111127,224,11111128,144,111111129};
    int n;
    cin>>n;
    cout<<x[2*n-2]<<" "<<x[2*n-1];
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x[18]= {10,0,1,22,6,123,12,1124,40,11125,30,111126,84,1111127,224,11111128,144,111111129};

int n;

cin>>n;

cout<<x[2*n-2]<<" "<<x[2*n-1];

return 0;

}

Решение задачи (Массив)

Для решения задачи заранее просчитали все ответы и записали их в массив [latex]x[/latex]. Так как ответы идут подряд составили формулу для вывода искомых значений: для количества чисел у которых сумма цифр совпадает с их произведением — [latex]2n-2[/latex], для минимального числа — [latex]2n-1[/latex]. Задача решена (также задачу можно решить с помощью циклов).

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com (цикл)
Код решения на ideone.com (массив)

Related Images:

e-olymp 2214. Функция 9

23/12/2017 by Андрей Лисовой

Задача

Дана функция, аргументы которой — произвольные натуральные числа

[latex]f(M,N)=\begin{cases} f(M-N,N), & \text{ npu } M>N \\ N, & \text{ npu } M=N \\ f(N-M,M) & \text{ npu } N>M \end{cases}[/latex]

Составить алгоритм (написать программу), вычисляющий значение функции.

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

Два натуральных числа [latex]n[/latex] и [latex]m[/latex] [latex](1 \le n, m \le 10^{18})[/latex].

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

Искомое значение функции.

Тесты

Входные данные	Выходные данные
[latex]6[/latex] [latex]3[/latex]	[latex]3[/latex]
[latex]12[/latex] [latex]12[/latex]	[latex]12[/latex]
[latex]126[/latex] [latex]98[/latex]	[latex]98[/latex]
[latex]10329[/latex] [latex]1501[/latex]	[latex]1501[/latex]
[latex]1008359[/latex] [latex]15113[/latex]	[latex]15113[/latex]

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

#include <iostream>
using namespace std;
 
unsigned long long f(unsigned long long n, unsigned long long m) {
    if (n % m == 0) return m;
    if (m % n == 0) return n;
    if (m > n) f(m % n, n);
    else  f(n % m , m);
}
 
int main() {
    unsigned long long n, m, t;
    cin >> m >> n;
    t = f(m, n);
    cout << t;
    return 0;
}

#include <iostream>

using namespace std;

unsigned long long f(unsigned long long n, unsigned long long m) {

if (n % m == 0) return m;

if (m % n == 0) return n;

if (m > n) f(m % n, n);

else f(n % m , m);

}

int main() {

unsigned long long n, m, t;

cin >> m >> n;

t = f(m, n);

cout << t;

return 0;

}

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

Для решения задачи напишем функцию [latex]f[/latex]. Именно эта функция и будет считать искомое значение. Из условия задачи видим, что для решения потребуется рекурсия. Для этого, если остаток от деления одного натурального числа на другое не равен нулю, то мы снова возращаемся в функцию (в зависимости от того,
что больше [latex]m[/latex] или [latex]n[/latex]). Это будет продолжаться до тех пор, пока остаток от деления одного натурального числа на другое не будет равен нулю (как только $n\mod m = 0$ или $m\mod n = 0$, то функция возращает в переменную [latex]t[/latex] искомое значение). Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

Related Images:

e-olymp 3609. Стартовая скорость

26/11/2017 by Андрей Лисовой

Задача

Кристина Стуй, Олеся Повх, Елизавета Брызгина, Мария Ремень

Женская олимпийская сборная Украины в эстафете 4×100 метров на олимпийских играх в Лондоне в составе (Кристина Стуй, Олеся Повх, Елизавета Брызгина, Мария Ремень)

Несмотря на то, что женская сборная Украины в эстафете [latex]4 \times 100[/latex] метров на олимпийских играх в Лондоне в составе Кристины Стуй, Олеси Повх, Елизаветы Брызгиной и Марии Ремень выступила очень достойно и завоевала бронзовые медали, подобная мысль назойливо мучила и программиста Васю.

Как показали тщательные экспериментальные проверки, модель, построенная им в задаче «Крейсерская скорость» оказалась не совсем точной. Многочасовые наблюдения, проведённые им на тренировках как украинских спортсменок, так и спринтеров из других стран, показали, что некоторые спортсмены во время старта разгоняются, а некоторые притормаживают. Но всё равно, после [latex]25[/latex] стартовых метров дистанции они движутся далее равномерно.

Феномен с «притормаживанием» Васе удалось с точки зрения физики пояснить довольно просто. Во время старта каждый из спортсменов имеет некоторую стартовую скорость, приобретённую в результате мощного отталкивания от стартовых колодок. Эта скорость может быть либо меньше «крейсерской», либо больше. В первом случае спортсмену нужно работать над наращиванием мышц ног для увеличения силы отталкивания. Во втором – мышцы уже наращены, но в результате того, что сила сопротивления воздуха зависит от площади соприкосновения тела спортсмена с ним, во время распрямления спортсмена во время старта эта сила сопротивления возрастает и становится постоянной только после указанных выше [latex]25[/latex] стартовых метров дистанции.

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

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

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

В единственной строке задано [latex]2[/latex] вещественных числа, разделённых единичным пробелом, соответственно результат спортсмена на дистанциях [latex]100[/latex] и [latex]200[/latex] метров.

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

В единственной строке выведите стартовую скорость спортсмена с точностью не менее [latex]6[/latex]-ти знаков после запятой.

Тесты

Входные данные	Выходные данные
[latex]9.63[/latex] [latex]19.32[/latex]	[latex]10.844104[/latex]
[latex]9.77[/latex] [latex]19.59[/latex]	[latex]10.606721[/latex]
[latex]9.69[/latex] [latex]19.40[/latex]	[latex]10.469771[/latex]
[latex]10.02[/latex] [latex]20.12[/latex]	[latex]10.548908[/latex]
[latex]9.88[/latex] [latex]19.85[/latex]	[latex]10.781564[/latex]

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

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

int main() {
    double a, b, t, v0, v;//создаем переменные, a и b - это входные данные, t - время разгона, v0 - стартовая скорость, v - "крейсерская" скорость
    cin >> a >> b;//вводим входные данные
    t = (175*a - 75*b) / 100;//находим время разгона спортсмена
    v = 75 / (a - t);//находим "крейсерскую" скорость
    v0 = (50 - v*t) / t;//находим стартовую скорость
    cout << fixed << setprecision(6) << v0;//выводим стартовую скорость с 6-тью знаками после запятой
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

double a, b, t, v0, v;//создаем переменные, a и b - это входные данные, t - время разгона, v0 - стартовая скорость, v - "крейсерская" скорость

cin >> a >> b;//вводим входные данные

t = (175*a - 75*b) / 100;//находим время разгона спортсмена

v = 75 / (a - t);//находим "крейсерскую" скорость

v0 = (50 - v*t) / t;//находим стартовую скорость

cout << fixed << setprecision(6) << v0;//выводим стартовую скорость с 6-тью знаками после запятой

return 0;

}

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

Со школы знаем формулу скорости, [latex]v=\frac{l}{t}[/latex]. Найдем из неё [latex]l=vt[/latex].
Пусть [latex]l_1[/latex] и [latex]l_2[/latex] — это расстояния, на которых спортсмен бежит с «крейсерской» скоростью соотвественно на дистанциях в [latex]100[/latex] и [latex]200[/latex] метров, где [latex]l_1=l-l_p[/latex], где [latex]l[/latex] — это длина дистанции, а [latex]l_p[/latex] — длина разгона (известно из условия задачи). Аналогично для [latex]l_2[/latex]. Заменим [latex]t[/latex] на [latex]t_1-t_p[/latex], где [latex]t_1[/latex] — время, за которое спортсмен пробегает всю дистанцию, а [latex]t_p[/latex] — время разгона на первых [latex]25[/latex]-ти метрах дистанции. Получаем формулы: [latex]l_1=v(t_1-t_p)[/latex] и [latex]l_2=v(t_2-t_p)[/latex]. Из отношения этих формул [latex]\frac {l_1}{l_2}=\frac {v(t_1-t_p)}{v(t_2-t_p)}[/latex], найдем [latex]t_p[/latex]. Имеем [latex]t_p=\frac{l_1t_2-l_2t_1}{l_2-l_1}[/latex]. Подставляем [latex]l_1=v(t_1-t_p)[/latex]. Находим «крейсерскую» скорость спортсмена, [latex]v=\frac{l_1}{t_1-t_p}[/latex]. Из уравнения равноускоренного движения
[latex]x=v_0t \times \frac{at^2}{2}[/latex], где [latex]x=25[/latex] метров (длина разгона). Находим [latex]v_0[/latex] — это и есть стартовая скорость спортсмена. Для этого заменим [latex]a[/latex] на [latex]\frac{v-v_0}{t_p}[/latex]. Приводим подобные и выражаем [latex]v_0[/latex]. В итоге получаем формулу стартовой скорости спортсмена, [latex]v_0=\frac{50-vt_p}{t_p}[/latex]. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com