e-olymp 8963. Наименьшие влево

19/01/2020 by Даниил Кадочников

Условие

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

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

В первой строке записано натуральное число [latex]n[/latex]. В следующей строке записаны [latex]n[/latex] целых чисел. Все числа по модулю не превышают [latex]100[/latex].

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

Выведите элементы обновленного массива.

Тесты

№	Ввод	Вывод
1	7 6 -3 -7 4 -7 -4 5	-7 -7 6 -3 4 -4 5
2	2 100 -100	-100 100
3	6 -2 -2 7 3 99 -2	-2 -2 -2 7 3 99
4	5 1 1 1 1 1	1 1 1 1 1

Решение

Вместо обычных массивов будем использовать векторы, чтобы было удобнее добавлять элементы в конец. Минимальный элемент можно найти с помощью простого цикла: если какой-либо элемент вектора меньше min, то min присваивается значение этого элемента, и так пока не найдено наименьшее число. Подсчитаем, сколько раз оно встречается в векторе. Столько же раз его нужно добавить в новый вектор. Наконец, переносим в v2 все оставшиеся элементы, не равные min.

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

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

int main()
{
    int n;
    cin >> n;
    vector <int> v, v2;
    int x;
    while(cin>>x) v.push_back(x);
    int min = v[0];
    for(int q=1; q<n; q++) {
        if(v[q]<min) min = v[q];
    }

    int min_counter = 0;
    for(int w=0; w<n; w++) {
        if(v[w] == min) min_counter++;
    }

    for(int e=0; e<min_counter; e++) v2.push_back(min);
    for(int r=0; r<n; r++) {
        if(v[r]!=min) v2.push_back(v[r]);
    }
    for(int t=0; t<n; t++) cout << v2[t] << " ";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

int n;

cin >> n;

vector <int> v, v2;

int x;

while(cin>>x) v.push_back(x);

int min = v[0];

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

if(v[q]<min) min = v[q];

}

int min_counter = 0;

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

if(v[w] == min) min_counter++;

}

for(int e=0; e<min_counter; e++) v2.push_back(min);

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

if(v[r]!=min) v2.push_back(v[r]);

}

for(int t=0; t<n; t++) cout << v2[t] << " ";

return 0;

}

Ссылки

решение на E-olymp
код на ideone

Related Images:

e-olymp 9414. Убить всех термитов

21/12/2019 by Андрей Метасов

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

На дереве живут термиты. Ваша задача убить их всех. Дерево является неориентированным связным графом с $n$ вершинами и $n — 1$ ребрами. Чтобы убить термитов, Вам следует отравить некоторые вершины. Если термит попадает на вершину с ядом, то он немедленно умирает. Вы не знаете, где изначально находятся термиты. Но Вы знаете, что термиты каждый раз попадают в случайную соседнюю вершину. Однако если термит прошел ребро $(u, v)$, то следующее ребро должно отличаться от $(v, u)$ за исключением случая, когда термит попадает в лист (в этом случае термит поворачивается и возвращается назад). Вам следует отравить минимальное количество вершин так, чтобы термиты попали в отравленные вершины после конечного числа шагов.

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

Первая строка содержит одно целое число $n$ $(1 \leqslant n \leqslant 100000)$. Следующая строка содержит $n — 1$ целое число $p_{i} (2 \leqslant i \leqslant n)$, означающее что ребро соединяет $p_{i}$ и $i$.

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

Выведите минимальное количество отравленных вершин.

Тесты

№	Входные данные	Выходные данные
1	1	1
2	2 1	1
3	8 1 1 2 1 2 3 2	2
4	5 1 2 1 4	1
5	16 1 2 3 4 5 3 7 1 9 9 11 11 13 13 15	3
6	10 1 2 3 3 1 2 3 7 9	2
7	8 1 1 3 3 1 6 6	2

Код

#include <bits/stdc++.h>
using namespace std;

const int NMAX = 100001;
vector<int> tree [NMAX]; 
vector<int> killed (NMAX, 0);
vector<bool> used (NMAX, 0);
vector<int> dist (NMAX, 0);
int ans = 0;

void kills(int v, int p)
{
    if (v == p) kills(tree[v][0], v);
    if (tree[v].size() == 2) for (auto to : tree[v]) if (to != p) kills(to, v);
    if (tree[v].size() >= 3) killed[v]++;
    return;
}

void goup(int v, int p)
{
    if (v == p)
    {
        for (auto to : tree[v]) if (dist[to] < dist[v]) goup(to, v);
        killed[v] = 0;
        return;
    }
    if (tree[v].size() == 2) for (auto to : tree[v]) if (to != p) goup(to, v);
    if (tree[v].size() >= 3)
    {
        killed[v]++;
        return;
    }
}


int main()
{
    int n,v; cin>>n;
    if (n <= 5) {cout<<1; return 0;} // Частный случай
    tree[1].push_back(0); // Корень тоже должен быть "развилкой"
    vector<int> leaves;
    for (int i = 1; i < n; i++)
    {
        cin>>v;
        tree[v].push_back(i+1);
        tree[i+1].push_back(v); //Заполнение графа в том виде, в котором его дают
    }

    for (int i = 1; i <= n; i++)
    {
        if (tree[i].size() == 1 || (i == 1 && tree[i].size() == 2)) leaves.push_back(i); //Запоминаем все листья
    }

    queue<int> q; dist[1] = 0;
    q.push(1); used[1] = true;
    while (!q.empty())
    {
        int qv = q.front(); q.pop();
        used[qv] = 1;
        for (auto to : tree[qv])                //BFS заполняющий вектор dist
        {
            if (!used[to])
            {
                q.push(to);
                dist[to] = dist[qv]+1;
            }
        }
    }

    for (auto l : leaves)
    {
        kills(l, l);        // Первый этап - запросы от каждого листа
    }

    int maxdist = -1; for (int i = 1; i <= n; i++) maxdist = max(maxdist, dist[i]); // Определение максимального "уровня" дерева
    int wentup = 1;
    while (wentup)
    {
        wentup = 0;
        for (int l = maxdist; l > 0; l--)
        {
            for (int i = 2; i <= n; i++)
            {
                if (killed[i] == 1 && dist[i] == l)
                {
                    goup(i, i);                    //Этап 2 - поднятие "недошедших" запросов
                    wentup++;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) if (killed[i] >= 2) ans++; //Финальный подсчет "отравленных" развилок
    cout<<ans;
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100001;

vector<int> tree [NMAX];

vector<int> killed (NMAX, 0);

vector<bool> used (NMAX, 0);

vector<int> dist (NMAX, 0);

int ans = 0;

void kills(int v, int p)

{

if (v == p) kills(tree[v][0], v);

if (tree[v].size() == 2) for (auto to : tree[v]) if (to != p) kills(to, v);

if (tree[v].size() >= 3) killed[v]++;

return;

}

void goup(int v, int p)

{

if (v == p)

{

for (auto to : tree[v]) if (dist[to] < dist[v]) goup(to, v);

killed[v] = 0;

return;

}

if (tree[v].size() == 2) for (auto to : tree[v]) if (to != p) goup(to, v);

if (tree[v].size() >= 3)

{

killed[v]++;

return;

}

int main()

{

int n,v; cin>>n;

if (n <= 5) {cout<<1; return 0;} // Частный случай

tree[1].push_back(0); // Корень тоже должен быть "развилкой"

vector<int> leaves;

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

{

cin>>v;

tree[v].push_back(i+1);

tree[i+1].push_back(v); //Заполнение графа в том виде, в котором его дают

}

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

{

if (tree[i].size() == 1 || (i == 1 && tree[i].size() == 2)) leaves.push_back(i); //Запоминаем все листья

}

queue<int> q; dist[1] = 0;

q.push(1); used[1] = true;

while (!q.empty())

{

int qv = q.front(); q.pop();

used[qv] = 1;

for (auto to : tree[qv]) //BFS заполняющий вектор dist

{

if (!used[to])

{

q.push(to);

dist[to] = dist[qv]+1;

}

for (auto l : leaves)

{

kills(l, l); // Первый этап - запросы от каждого листа

}

int maxdist = -1; for (int i = 1; i <= n; i++) maxdist = max(maxdist, dist[i]); // Определение максимального "уровня" дерева

int wentup = 1;

while (wentup)

{

wentup = 0;

for (int l = maxdist; l > 0; l--)

{

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

{

if (killed[i] == 1 && dist[i] == l)

{

goup(i, i); //Этап 2 - поднятие "недошедших" запросов

wentup++;

}

for (int i = 1; i <= n; i++) if (killed[i] >= 2) ans++; //Финальный подсчет "отравленных" развилок

cout<<ans;

return 0;

}

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

Поскольку в задаче речь идет о дереве, циклов в нем нет по определению. Значит, единственным способом для термита ходить «вечно» будет путь между двумя листами, в которых он сможет разворачиваться. Фактически, задача сводится к вопросу «Какое минимальное количество вершин в дереве нужно отравить, чтобы нельзя было добраться из любого листа в другой лист не пройдя через отравленные?».

Определим для этого $3$ типа вершин: лист, развилка и обычная вершина. Листом назовем вершину, у которой нет детей (всего $1$ связь с другой вершиной). Обычные вершины — те, у которых ровно $2$ связи (для нашего термита это пути вниз или вверх). Развилкой назовем вершину, у которой $3$ или больше связей с другими. Будем считать корень тоже развилкой, даже если у него всего $2$ связи, или листом, если одна. Через развилки можно ходить из одного листа в другой, либо «вверх» — в сторону корня.

$1$ — корень; $5,6,3$ — листья; $4$ — развилка; $2$ — обычная;

Первый этап

Очевидно, выгоднее всего «закрывать» развилки. А среди них — те, которые соединяют несколько листов напрямую. Пусть каждый лист отправляет «запрос» вверх по дереву на закрытие ближайшей к нему развилки. Когда «запрос» доходит до развилки, он тут же записывается на её счёт. Таким образом, в дереве выше вершина $4$ будет иметь $2$ запроса — от листов $5$ и $6$, а корень — $1$ запрос от листа $3$.

Теперь, просто считаем количество вершин с количеством запросов $\geqslant2$ и «закрываем» их.

Второй этап

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

Дерево, в котором необходим второй этап

Вершина $2$ и корень получают по $1$ запросу и остаются открытыми, а у термита остается путь между листами $10$ и $6$.

Для предотвращения таких случаев, пробежимся по дереву «снизу вверх» — от самого нижнего уровня до верхнего и для каждой развилки, у которой ровно $1$ запрос, сместим его вверх аналогично первому этапу — до ближайшей развилки. Будем выполнять этот шаг, пока есть такие вершины (с $1$ запросом).

В итоге, все запросы «соединятся» в нужных развилках, значение в них станет $\geqslant2$ и эти развилки нужно будет тоже закрыть. Для дерева выше, будет закрыт корень.

Осталось посчитать кол-во закрытых.

Описание алгоритма

Дерево будем хранить в массиве векторов tree. Количество запросов для вершины $i$ хранится в killed[i]. Стандартный вектор used для поиска в ширину и dist- вектор расстояний от корня до вершин, которые и будут определяться с помощью BFS.

Функция kills предназначена для того, чтобы донести запрос от листа до развилки. Она рассматривает $3$ случая:

v == p — текущая вершина совпадает с той, из которой пришли. Это крайний случай, говорящий о том, что мы только начали и находимся в листе. Тогда, идем в единственно возможном направлении — tree[v][0].
tree[v].size == 2 — вершина обычного типа, просто идем «вверх», выбирая из двух путей тот, что не совпадает с предыдущей вершиной.
tree[v].size >= 3 — попали в развилку. Увеличиваем ее значение killed[v] и выходим из рекурсии.

Функция goup отличается от kills лишь тем, что при v == p выбирает из всех направлений то, которое ближе к корню, используя dist.

Подготовка

Можно заметить, что для всех деревьев из $5$ или менее вершин ответ будет $1$. Проверим это сразу при вводе n. Далее, осторожно считываем дерево в массив векторов (см. Входные данные). В следующем цикле, определяем листья и запоминаем их в вектор leaves. Нужно учесть то, что корень может быть листом, если у него всего $2$ связи — одна с деревом, а другая — искусственно созданная нами в $0$ вершину. Последний шаг — запустить поиск в ширину из корня, который заполнит вектор dist расстояниями от корня до вершин.

Первый этап

Просто запускаем kills (l, l) из каждого листа l для «отправки» запросов в ближайшие развилки.

Второй этап

Определяем максимальную «глубину» дерева — максимальное расстояние вершины от корня. Далее, для каждого уровня от самого нижнего до корня, при определении вершины со значением killed[i] == 1 запускаем goup (i, i), а в переменной wentup считаем количество таких случаев. Как только их не останется — while выйдет из цикла.

Наконец, осталось просто посчитать количество вершин, у которых значение killed[i] >= 2.
Задача на e-olymp
Код решения на ideone
Засчитанное решение на e-olymp

Related Images:

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:

ML 31. Площадь параллелепипеда

21/09/2016 by Сытников Дан

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

Найти площадь полной поверхности параллелепипеда три стороны которого образованы векторами [latex] \overrightarrow{a}=(a_x,a_y,a_z), \overrightarrow{b}=(b_x,b_y,b_z) [/latex] и [latex]\overrightarrow{c}=(c_x,c_y,c_z)[/latex].

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

Координаты векторов [latex] \overrightarrow{a}, \overrightarrow{b}[/latex] и [latex] \overrightarrow{c} [/latex].

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

Площадь полной поверхности параллелепипеда.

Тесты

№	Входные данные	Выходные данные
1	-5.6 8.3 -7.1 2 11 -8 2.1 1 3.3	389.28894739406866
2	1 2 3 4 5 6 7 8 9	58.787753826796276
3	-9 2 4 -3 5 1 -6 7 8	305.5334243147188
4	1 1 1 1 1 1 1 1 1	0.0
5	0 0 1 0 1 0 1 0 0	6.0
6	0 0 0 1 0 0 0 0 1	2.0
7	1 0 0 0 0 1 0 0 1	2.0

Код на C++

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
double s1(double a1, double a2, double a3, double b1, double b2, double b3) //Создаем функцию для нахождения стороны параллелепипеда
{
    return sqrt((a2*b3 - a3*b2)*(a2*b3 - a3*b2) + (a3*b1 - a1*b3)*(a3*b1 - a1*b3) + (a1*b2 - a2*b1)*(a1*b2 - a2*b1)); //Модуль векторного произведения
}
int main() 
{
    double ax, ay, az, bx, by, bz, cx, cy, cz, sab, sac, sbc, s;
    cin >> ax >> ay >> az >> bx >> by >> bz >> cx >> cy >> cz;
    sab = s1(ax, ay, az, bx, by, bz); //Поочередно вызываем функцию для каждой стороны
    sac = s1(ax, ay, az, cx, cy, cz);
    sbc = s1(bx, by, bz, cx, cy, cz);
    if ((ax == bx && ay == by && az == bz) || (ax == cx && ay == cy && az==cz) || (bx == cx && by == cy && bz == cz))
        s = sab + sac + sbc; //Конечная формула площади полной поверхности параллелепипеда
    else
        s = (sab + sac + sbc)*2; 
    cout << setprecision(15) << s;
    return 0;
}

#include <iostream>

#include <cmath>

#include <iomanip>

using namespace std;

double s1(double a1, double a2, double a3, double b1, double b2, double b3) //Создаем функцию для нахождения стороны параллелепипеда

{

return sqrt((a2*b3 - a3*b2)*(a2*b3 - a3*b2) + (a3*b1 - a1*b3)*(a3*b1 - a1*b3) + (a1*b2 - a2*b1)*(a1*b2 - a2*b1)); //Модуль векторного произведения

}

int main()

{

double ax, ay, az, bx, by, bz, cx, cy, cz, sab, sac, sbc, s;

cin >> ax >> ay >> az >> bx >> by >> bz >> cx >> cy >> cz;

sab = s1(ax, ay, az, bx, by, bz); //Поочередно вызываем функцию для каждой стороны

sac = s1(ax, ay, az, cx, cy, cz);

sbc = s1(bx, by, bz, cx, cy, cz);

if ((ax == bx && ay == by && az == bz) || (ax == cx && ay == cy && az==cz) || (bx == cx && by == cy && bz == cz))

s = sab + sac + sbc; //Конечная формула площади полной поверхности параллелепипеда

else

s = (sab + sac + sbc)*2;

cout << setprecision(15) << s;

return 0;

}

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
    static double s1(double a1, double a2, double a3, double b1, double b2, double b3) //Создаем функцию для нахождения стороны параллелепипеда
    { 
        return Math.sqrt((a2*b3 - a3*b2)*(a2*b3 - a3*b2) + (a3*b1 - a1*b3)*(a3*b1 - a1*b3) + (a1*b2 - a2*b1)*(a1*b2 - a2*b1)); //Модуль векторного произведения
    }
 
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        double ax, ay, az, bx, by, bz, cx, cy, cz, sab, sac, sbc, s;
        ax = in.nextDouble();
        ay = in.nextDouble();
        az = in.nextDouble();
        bx = in.nextDouble();
        by = in.nextDouble();
        bz = in.nextDouble();
        cx = in.nextDouble();
        cy = in.nextDouble();
        cz = in.nextDouble();
        sab = s1(ax, ay, az, bx, by, bz); //Поочередно вызываем функцию для каждой стороны
        sac = s1(ax, ay, az, cx, cy, cz);
        sbc = s1(bx, by, bz, cx, cy, cz);
        if ((ax == bx && ay == by && az == bz) || (ax == cx && ay == cy && az == cz) || (bx == cx && by == cy && bz == cz))
            s = sab + sac + sbc; //Конечная формула площади полной поверхности параллелепипеда
        else
            s = (sab + sac + sbc)*2; 
        System.out.println(s);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

static double s1(double a1, double a2, double a3, double b1, double b2, double b3) //Создаем функцию для нахождения стороны параллелепипеда

{

return Math.sqrt((a2*b3 - a3*b2)*(a2*b3 - a3*b2) + (a3*b1 - a1*b3)*(a3*b1 - a1*b3) + (a1*b2 - a2*b1)*(a1*b2 - a2*b1)); //Модуль векторного произведения

}

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

{

Scanner in = new Scanner(System.in);

double ax, ay, az, bx, by, bz, cx, cy, cz, sab, sac, sbc, s;

ax = in.nextDouble();

ay = in.nextDouble();

az = in.nextDouble();

bx = in.nextDouble();

by = in.nextDouble();

bz = in.nextDouble();

cx = in.nextDouble();

cy = in.nextDouble();

cz = in.nextDouble();

sab = s1(ax, ay, az, bx, by, bz); //Поочередно вызываем функцию для каждой стороны

sac = s1(ax, ay, az, cx, cy, cz);

sbc = s1(bx, by, bz, cx, cy, cz);

if ((ax == bx && ay == by && az == bz) || (ax == cx && ay == cy && az == cz) || (bx == cx && by == cy && bz == cz))

s = sab + sac + sbc; //Конечная формула площади полной поверхности параллелепипеда

else

s = (sab + sac + sbc)*2;

System.out.println(s);

}

Алгоритм

По определению Параллелепипед — призма, основанием которой служит параллелограмм, или (равносильно) многогранник, у которого шесть граней и каждая из них — параллелограмм.

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

Модуль векторного произведения [latex] [\overrightarrow{a},\overrightarrow{b}] [/latex] равняется площади S параллелограмма, построенного на приведённых к общему началу векторах [latex]\overrightarrow { a }[/latex] и [latex]\overrightarrow { b } [/latex]

Рассчитаем площадь каждого параллелограмма по формуле [latex] \left|\left[ \overrightarrow { a } , \overrightarrow { b } \right]\right| =
\left|(a_{ y }b_{ z }-a_{ z }b_{ y }, a_{ z }b_{ x }-a_{ x }b_{ z }, a_{ x }b_{ y }-a_{ y }b_{ x })\right|[/latex].

Найдя все три стороны, получим площадь полной поверхности параллелепипеда по формуле

[latex] S=2*(S_1+S_2+S_3) [/latex], где [latex] S_n [/latex] — площадь стороны параллелепипеда.

Ссылки:

Условие задачи ML31.

Работающая версия программы на языке C++.

Работающая версия программы на языке Java.

Геометрические свойства векторного произведения.

Related Images:

М6a

02/12/2014 by Григорян Артак

а) Чётные числа из стандартного потока ввода поместить в хранилище с именем [latex]Even[/latex], а нечётные —[latex]Odd[/latex]. Во входном потоке неизвестное количество целых чисел через пробел.

Поток ввода	Результат
4 8 15 16 23 42	4 8 16 4215 23
0 1 1 2 3 5 8 13 21 34 55 89 144	0 2 8 34 1441 1 3 5 13 21 55 89

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

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

int main() 
{
	int x;
	vector<int> Odd;
	vector<int> Even;
	while(cin>>x) 
	{
    	if(x%2==0) Even.push_back(x);
    	else Odd.push_back(x);
	}
	for(int i=0;i<Even.size();i++)
	{
		cout<<Even[i]<<" ";
	}
	cout<<endl;
	for(int i=0;i<Odd.size();i++)
	{
		cout<<Odd[i]<<" ";
	}
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

int x;

vector<int> Odd;

vector<int> Even;

while(cin>>x)

{

if(x%2==0) Even.push_back(x);

else Odd.push_back(x);

}

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

{

cout<<Even[i]<<" ";

}

cout<<endl;

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

{

cout<<Odd[i]<<" ";

}

return 0;

}

Создаем два вектора [latex] Odd [/latex] и [latex]Even[/latex]. С помощью цикла [latex]while[/latex] вводим неопределенное количество элементов. Внутри цикла с помощью [latex]push[/latex]_[latex]back[/latex] четные числа помещаем в [latex]Even[/latex] , а нечетные в [latex]Odd[/latex].

Код программы можно посмотреть тут