e-olymp 9080. Три богатыря

04/12/2019 by Паша Мацалышенко

Задача

Три богатыря шли из Бразилии в Киевскую Русь. Шли они со скоростью [latex]n[/latex] метров в минуту и должны пройти расстояние [latex]r[/latex] километров. Сколько дней им понадобится для преодоления пути?

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

Два натуральных числа [latex]n[/latex] и [latex]r[/latex] [latex]\left(n, r \leqslant10^{4}\right)[/latex]

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

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

Тесты

№	Входные данные	Выходные данные
1	1 10	7
2	2 8	3
3	4 70	13
4	5 68	10
5	3 12	3

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

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

int main() {
    int n, r;
    cin >> n >> r;
    cout << ceil(r / n * 1.44);
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n, r;

cin >> n >> r;

cout << ceil(r / n * 1.44);

return 0;

}

Решение

Ответом к задаче будет количество дней, за которое богатыри проделают путь. То есть нам просто надо поделить путь на скорость. Но загвоздка задачи состоит в том, что скорость дана в метрах в минуту, а нам надо перевести в километры в сутки. В одних сутках [latex]1440[/latex] минут, в километре [latex]1000[/latex] метров. Выполнив математические преобразования, получаем, что надо заданное значение скорости умножить на [latex]1.44[/latex]. Выводим результат деления пути на скорость, умноженную на [latex]1.44[/latex]. Так как получится нецелый результат, округляем значение в сторону большего с помощью функции ceil() , предварительно подключив библиотеку cmath .

Ссылки

Related Images:

e-olymp 47. Паркет из треугольников

24/06/2018 by Артем Чернобровкин

Задача

Прямоугольную комнату размерами [latex]m[/latex] на [latex]n[/latex] (сначала по горизонтали, а потом по вертикали) замостили треугольными плитками и их пронумеровали, как показано на рисунке.

За один шаг можно переместиться с одной паркетины на другую только через общую сторону. Найти наименьшее количество шагов, нужных для перемещения с паркетины [latex]a[/latex] на паркетину [latex]b[/latex].

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

Во входном файле в первой строке через пробел заданы значения [latex]n[/latex], [latex]m[/latex] [latex](1 ≤ n, m ≤ 100)[/latex], а во второй — [latex]a[/latex], [latex]b[/latex].

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

Искомое количество шагов.

Тесты

#	Входные данные	Выходные данные
1	5 4 25 38	5
2	5 4 6 22	4
3	5 4 15 22	3
4	3 2 1 12	7
5	3 2 6 12	2

Код 1

#include <iostream>
using namespace std;

int main()
{
    int vertSize;
    int horSize;
    int firstNumber;
    int lastNumber;
    cin >> horSize >> vertSize >> firstNumber >> lastNumber;
    //создание динамического массива
    int*** arr;
    arr = new int**[vertSize];
    int count = 1;
    int z = 2;
    int apos[3];
    int bpos[3];
    for (int i = 0; i < vertSize; i++)
    {
        arr[i] = new int*[horSize];
        for (int j = 0; j < horSize; j++)
        {
            arr[i][j] = new int[z];
            for (int k = 0; k < 2; k++)
            {
                arr[i][j][k] = count;
                count++;
                // определяем позицию наших элементов в массиве
                if (arr[i][j][k] == firstNumber)
                {
                    apos[0] = i;
                    apos[1] = j;
                    apos[2] = k;
                }
                if (arr[i][j][k] == lastNumber)
                {
                    bpos[0] = i;
                    bpos[1] = j;
                    bpos[2] = k;
                }
            }
        }
    }
    int hor;
    int vert;
    // направление движения по вертикали
    vert = apos[0] < bpos[0] ? 1 : (apos[0] == bpos[0] ? 0 : -1);
    // направление движения по горизонтали
    hor = apos[1] < bpos[1] ? 1 : (apos[1] == bpos[1] ? 0 : -1);
    int stepCount = 0;
    int curCell[3];
    for (int i = 0; i < 3; i++)
        curCell[i] = apos[i];

    bool dir;
    if (apos[1] < bpos[1] && firstNumber % 2 == 0 || apos[1] > bpos[1] && firstNumber % 2 != 0)
        dir = false;
    else
        dir = true;
    while (1)
    {
        if (dir && vert != 0)
        {
            if (vert == -1)
            {
                if (curCell[2] == 0)
                    curCell[0]--;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
            else
            {
                if (curCell[2] == 1)
                    curCell[0]++;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
        }
        else if (!dir && hor != 0)
        {
            if (hor == -1)
            {
                if (curCell[2] == 0)
                    curCell[1]--;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
            else
            {
                if (curCell[2] == 1)
                    curCell[1]++;
                curCell[2] = !((bool)curCell[2]);
                stepCount++;
            }
        }
        dir = !dir;

        if (curCell[0] == bpos[0])
            vert = 0;
        if (curCell[1] == bpos[1])
            hor = 0;

        if (curCell[0] == bpos[0] && curCell[1] == bpos[1] && curCell[2] != bpos[2])
        {
            curCell[2] = !((bool)curCell[2]);
            stepCount++;
        }

        bool end;
        for (int i = 0; i < 3; i++)
        {
            if (curCell[i] != bpos[i])
            {
                end = false;
                break;
            }
            end = true;
        }
        if (end)
            break;
    }
    cout << stepCount << endl;
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

#include <iostream>

using namespace std;

int main()

{

int vertSize;

int horSize;

int firstNumber;

int lastNumber;

cin >> horSize >> vertSize >> firstNumber >> lastNumber;

//создание динамического массива

int*** arr;

arr = new int**[vertSize];

int count = 1;

int z = 2;

int apos[3];

int bpos[3];

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

{

arr[i] = new int*[horSize];

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

{

arr[i][j] = new int[z];

for (int k = 0; k < 2; k++)

{

arr[i][j][k] = count;

count++;

// определяем позицию наших элементов в массиве

if (arr[i][j][k] == firstNumber)

{

apos[0] = i;

apos[1] = j;

apos[2] = k;

}

if (arr[i][j][k] == lastNumber)

{

bpos[0] = i;

bpos[1] = j;

bpos[2] = k;

}

int hor;

int vert;

// направление движения по вертикали

vert = apos[0] < bpos[0] ? 1 : (apos[0] == bpos[0] ? 0 : -1);

// направление движения по горизонтали

hor = apos[1] < bpos[1] ? 1 : (apos[1] == bpos[1] ? 0 : -1);

int stepCount = 0;

int curCell[3];

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

curCell[i] = apos[i];

bool dir;

if (apos[1] < bpos[1] && firstNumber % 2 == 0 || apos[1] > bpos[1] && firstNumber % 2 != 0)

dir = false;

else

dir = true;

while (1)

{

if (dir && vert != 0)

{

if (vert == -1)

{

if (curCell[2] == 0)

curCell[0]--;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else

{

if (curCell[2] == 1)

curCell[0]++;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else if (!dir && hor != 0)

{

if (hor == -1)

{

if (curCell[2] == 0)

curCell[1]--;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

else

{

if (curCell[2] == 1)

curCell[1]++;

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

dir = !dir;

if (curCell[0] == bpos[0])

vert = 0;

if (curCell[1] == bpos[1])

hor = 0;

if (curCell[0] == bpos[0] && curCell[1] == bpos[1] && curCell[2] != bpos[2])

{

curCell[2] = !((bool)curCell[2]);

stepCount++;

}

bool end;

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

{

if (curCell[i] != bpos[i])

{

end = false;

break;

}

end = true;

}

if (end)

break;

}

cout << stepCount << endl;

return 0;

}

Код 2

#include <iostream>
using namespace std;
int main() {
    int vertSize;
    int horSize;
    int firstNumber;
    int lastNumber;
    cin >> horSize >> vertSize >> firstNumber >> lastNumber;
    if (firstNumber > lastNumber){
        swap(firstNumber, lastNumber);  
    } 
    //вычисление координат
    int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;
    int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;
    int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;
    int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;
    //создание и задание размера для статического массива
    int Search[2 * horSize];
    Search[firstNumberx - 1] = 0;
    int step = 1;
    for (int i = firstNumberx - 2; i >= 0; i--){
        Search[i] = step++;
        
    }
    step = 1;
    for (int i = firstNumberx; i < 2 * horSize; i++){
        Search[i] = step++;
    }
    //сравнение по у
    for (int j = firstNumbery; j < lastNumbery; j++) {
        for (int i = 1; i < 2 * horSize; i += 2) {
            Search[i - 1] = Search[i] + 1;
            Search[i] += 2;
            //определние значения на предпоследнем элементе
            if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){
                Search[i - 2] = Search[i];
            }
        }
    }
    cout << Search[lastNumberx - 1] << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int vertSize;

int horSize;

int firstNumber;

int lastNumber;

cin >> horSize >> vertSize >> firstNumber >> lastNumber;

if (firstNumber > lastNumber){

swap(firstNumber, lastNumber);

}

//вычисление координат

int firstNumberx = (firstNumber - 1) % (2 * horSize) + 1;

int firstNumbery = (firstNumber - 1) / (2 * horSize) + 1;

int lastNumberx = (lastNumber - 1) % (2 * horSize) + 1;

int lastNumbery = (lastNumber - 1) / (2 * horSize) + 1;

//создание и задание размера для статического массива

int Search[2 * horSize];

Search[firstNumberx - 1] = 0;

int step = 1;

for (int i = firstNumberx - 2; i >= 0; i--){

Search[i] = step++;

}

step = 1;

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

Search[i] = step++;

}

//сравнение по у

for (int j = firstNumbery; j < lastNumbery; j++) {

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

Search[i - 1] = Search[i] + 1;

Search[i] += 2;

//определние значения на предпоследнем элементе

if (((i - 2) >= 0) && (Search[i]<Search[i - 2])){

Search[i - 2] = Search[i];

}

cout << Search[lastNumberx - 1] << endl;

return 0;

}

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

Способ 1

Каждый элемент имеет три параметра:

Положение в строке
Положение в столбце
Четность

Для хранения этих значений создадим трёхмерный массив. Существует несколько вариантов расположения элементов в нем:

Оба элемента расположены в одной строке строке
Оба элемента расположены в одном столбце
Оба элемента расположены на одной диагонали
Произвольное расположение

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

firstNumber = 7;
lastNumber = 14;

1 2	firstNumber = 7; lastNumber = 14;

Позиция [latex]7[/latex] [latex]\left[ 0 , 3 , 0 \right] [/latex].
Позиция [latex]14[/latex] [latex]\left[ 1 , 2 , 1 \right] [/latex].
Для случая [latex] 5*4 [/latex] эти элементы расположены на одной диагонали. Далее идет создание вспомогательного 3-х мерного массива, в который мы положим координаты [latex]7[/latex]. Идея состоит в том, чтобы временный массив и массив с координатам [latex]14[/latex] совпали. Т.к [latex]7[/latex] нечетное, а [latex]14[/latex] четное, то первый «шаг» будет сделан по горизонтали, тем самым мы уровняем координату, отвечающую за четность. Далее идет сравнение по «строчной» координате, т.к. они не совпадают, то делается «шаг» вниз. Далее остается сделать «шаг» влево, чтобы совпали координаты по столбцам.
Аналогичные проверки делаются для остальных случаев.
Важно отметить, что лучше всего для проверки подходят переменные типа bool. Поэтому в некоторых местах были использованы преобразование из типа int в тип bool. Делалось это при помощи следующей строки кода

(bool)curCell[2]

1	(bool)curCell[2]

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

Способ 2

Для того, чтобы наш код был универсален для случая [latex]firstNumber > lastNumber[/latex] и [latex]firstNumber < lastNumber[/latex] мы меняем местами [latex]firstNumber[/latex] и [latex]lastNumber[/latex].
Следующим шагом будет определение позиции [latex]firstNumber[/latex] и [latex]lastNumber[/latex]. Положим, что [latex] x [/latex] — это позиция в строке, а [latex] y [/latex] — столбце. Удобнее всего хранить значения в массиве, поэтому мы создаем

int V[2 * horSize];

1	int V[2 * horSize];

массив, переменные в котором будет иметь тип [latex] int [/latex], а размер будет фиксированный. Для определения количества шагов заведем переменную с типом [latex] int [/latex].
Важно отметить, что идея решения данного способа состоит в том, чтобы на позиции

Search[firstNumberx - 1];

1	Search[firstNumberx - 1];

стояло количество шагов, совершенных в ходе решения.

Ссылки

Задача на e-olymp

Код задачи на ideone ( способ 1 )

Код задачи на ideone ( способ 2 )

Related Images:

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

13/05/2015 by Осецимський Анатолій Вадимович

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

Условие задачи на e-olimp.
Cсылка на пройденный тесты.

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

link.

#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;

}

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

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

Tag Archives: путь

e-olymp 9080. Три богатыря

Задача

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

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

Тесты

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

Решение

Ссылки

Related Images:

e-olymp 47. Паркет из треугольников

Задача

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

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

Тесты

Код 1

Код 2

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

Способ 1

Способ 2

Ссылки

Related Images:

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

Related Images: