e-olymp 7213. Шашка на кубе

12/12/2020 by Максим Ливитчук

Условие

Поверхность куба отрезками, параллельными рёбрам куба, разделена на квадратные клетки, длина сторон которых в $l$ (нечетное натуральное число) раз меньше длины ребра куба. Шашку передвигают за один ход из клетки на произвольную смежную с ней клетку (что имеет с данной общую сторону).

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

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

Содержит натуральные числа $l$ и $m$ ($l < 52$, $m < 200$).

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

Вывести искомое количество способов.

Тесты

l	m	вывод
3	3	1
3	4	0
3	5	25
51	199	4009263689513240276071196173369495212494629453793821392879244551766927964742684514532573281589075237363501397360
3	199	11954860546705755218324706261555627152268568460810054501274297031890136116190373877274924800908756150285132065690107399

Код

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

#define cr(a, b, x, y) case a: return CellCoord{b, x, y}
#define SIDENUM 3 //количество сторон куба которые хранятся
#define MAX_L 51 //максимальное значение L

#define BASE 1000000000 //10^9, основание системы счисления для длинной арифметики 
#define DNUM 9 //количество цифр 10-ичной системы счисления в 1 "цифре" длинной арифметики

struct LongNum {
    //реализация длинной арифметики на векторах со сложением и выводом
    vector<int> v;
    LongNum() {} //стандартный конструктор
    LongNum(int s) { //конструктор из int
        v.push_back(s);
    }
    void print() { //вывод числа
        cout <<(v.empty() ? 0 : v.back());
        for (int i = (int)v.size() - 2; i>=0; i--)
            cout <<setfill('0') <<setw(DNUM) <<v[i];
    }
    void add(LongNum term) { //прибавление длинного числа
        auto b = term.v;
        int carry = 0;
        for (size_t i = 0; i < max(v.size(), b.size()) || carry; i++) {
            if (i == v.size())
                v.push_back(0);
            v[i] += carry + (i < b.size() ? b[i] : 0);
            carry = v[i] >= BASE;
            if (carry)  v[i] -= BASE;
        }
    }
};

struct CellCoord {
    //хранит данные о положении клетки
    short side;
    short x, y;
};

struct CellNeighbors {
    //хранит данные о положении всех(4) соседей определённой клетки
    CellCoord n[4];
};

CellCoord FixNeighbor(short l, short side, short x, short y) {
    //исправляет данные о положении клетки, если она выходит за края грани
    if(x == -1) { //если сосед находится левее грани
        switch(side) {
        //если координаты выходят за левую границу 0-ой грани - меняет грань на 1-ую,
        //обнуляя y, а в x записывает старый y 
        cr(0, 1, y,     0); //и так далее
        cr(1, 1, l-1,   y);
        cr(2, 1, l-y-1, l-1);
        }
    } else if(x == l) {//правее
        switch(side) {
        cr(0, 1, l-y-1, 0);
        cr(1, 1, 0,     y);
        cr(2, 1, y,     l-1);
        }
    } else if(y == -1) {//выше
        switch(side) {
        cr(0, 1, l-x-1, 0);
        cr(1, 0, x,     l-1);
        cr(2, 1, x,     l-1);
        }
    } else if(y == l) {//ниже
        switch(side) {
        cr(0, 1, x,     0);
        cr(1, 2, x,     0);
        cr(2, 1, l-x-1, l-1);
        }
    } else {
        // если координаты не вышли за границы грани просто возвращаем неизменёные координаты
        return CellCoord{side, x, y};
    }
}

CellNeighbors GetNeighbors(short l, short side, short x, short y) {
    //возвращает исправленные координаты всех(4) соседних клеток
    return CellNeighbors{{
        FixNeighbor(l, side, x-1, y),
        FixNeighbor(l, side, x+1, y),
        FixNeighbor(l, side, x, y-1),
        FixNeighbor(l, side, x, y+1)
    }};
}

int main() {
    short l, m;
    bool flag = false;
    cin >>l >>m;
    LongNum cubes[2][SIDENUM][MAX_L][MAX_L];

    cubes[0][0][l/2][l/2] = LongNum(1);
    //за 0 ходов можно дойти 1 путём в изначальную точку

    CellNeighbors nbs[SIDENUM][MAX_L][MAX_L];
    //массив координат соседей

    for(short side=0; side<SIDENUM; side++) {
        for(short xi=0; xi<l; xi++) {
            for(short yi=0; yi<l; yi++) { //перебор координат всех клеток
                nbs[side][xi][yi] = GetNeighbors(l, side, xi, yi);
                //кэш координат соседних клеток
            }
        }
    }

    for(short i=0; i<m; i++) {
        for(short side=0; side<SIDENUM; side++) {
            for(short xi=0; xi<l; xi++) {
                for(short yi=0; yi<l; yi++) { //перебор всех клеток
                    LongNum neighbor_sum;
                    for(auto e: nbs[side][xi][yi].n) { //перебор всех соседей
                        neighbor_sum.add(cubes[flag][e.side][e.x][e.y]);
                        //сложение количества путей ко всем соседям на предыдущем шаге
                    }
                    cubes[!flag][side][xi][yi] = neighbor_sum;
                    //запись получившейся суммы в клетку
                }
            }
        }
        flag = !flag; //замена местами массива для предыдущего шага и нынешнего
    }
    cubes[flag][1][l/2][l/2].print();
    //вывод количества путей к центру соседней грани на m-ом шаге
}

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 <iomanip>

#include <vector>

using namespace std;

#define cr(a, b, x, y) case a: return CellCoord{b, x, y}

#define SIDENUM 3 //количество сторон куба которые хранятся

#define MAX_L 51 //максимальное значение L

#define BASE 1000000000 //10^9, основание системы счисления для длинной арифметики

#define DNUM 9 //количество цифр 10-ичной системы счисления в 1 "цифре" длинной арифметики

struct LongNum {

//реализация длинной арифметики на векторах со сложением и выводом

vector<int> v;

LongNum() {} //стандартный конструктор

LongNum(int s) { //конструктор из int

v.push_back(s);

}

void print() { //вывод числа

cout <<(v.empty() ? 0 : v.back());

for (int i = (int)v.size() - 2; i>=0; i--)

cout <<setfill('0') <<setw(DNUM) <<v[i];

}

void add(LongNum term) { //прибавление длинного числа

auto b = term.v;

int carry = 0;

for (size_t i = 0; i < max(v.size(), b.size()) || carry; i++) {

if (i == v.size())

v.push_back(0);

v[i] += carry + (i < b.size() ? b[i] : 0);

carry = v[i] >= BASE;

if (carry) v[i] -= BASE;

}

};

struct CellCoord {

//хранит данные о положении клетки

short side;

short x, y;

};

struct CellNeighbors {

//хранит данные о положении всех(4) соседей определённой клетки

CellCoord n[4];

};

CellCoord FixNeighbor(short l, short side, short x, short y) {

//исправляет данные о положении клетки, если она выходит за края грани

if(x == -1) { //если сосед находится левее грани

switch(side) {

//если координаты выходят за левую границу 0-ой грани - меняет грань на 1-ую,

//обнуляя y, а в x записывает старый y

cr(0, 1, y, 0); //и так далее

cr(1, 1, l-1, y);

cr(2, 1, l-y-1, l-1);

}

} else if(x == l) {//правее

switch(side) {

cr(0, 1, l-y-1, 0);

cr(1, 1, 0, y);

cr(2, 1, y, l-1);

}

} else if(y == -1) {//выше

switch(side) {

cr(0, 1, l-x-1, 0);

cr(1, 0, x, l-1);

cr(2, 1, x, l-1);

}

} else if(y == l) {//ниже

switch(side) {

cr(0, 1, x, 0);

cr(1, 2, x, 0);

cr(2, 1, l-x-1, l-1);

}

} else {

// если координаты не вышли за границы грани просто возвращаем неизменёные координаты

return CellCoord{side, x, y};

}

CellNeighbors GetNeighbors(short l, short side, short x, short y) {

//возвращает исправленные координаты всех(4) соседних клеток

return CellNeighbors{{

FixNeighbor(l, side, x-1, y),

FixNeighbor(l, side, x+1, y),

FixNeighbor(l, side, x, y-1),

FixNeighbor(l, side, x, y+1)

}};

}

int main() {

short l, m;

bool flag = false;

cin >>l >>m;

LongNum cubes[2][SIDENUM][MAX_L][MAX_L];

cubes[0][0][l/2][l/2] = LongNum(1);

//за 0 ходов можно дойти 1 путём в изначальную точку

CellNeighbors nbs[SIDENUM][MAX_L][MAX_L];

//массив координат соседей

for(short side=0; side<SIDENUM; side++) {

for(short xi=0; xi<l; xi++) {

for(short yi=0; yi<l; yi++) { //перебор координат всех клеток

nbs[side][xi][yi] = GetNeighbors(l, side, xi, yi);

//кэш координат соседних клеток

}

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

for(short side=0; side<SIDENUM; side++) {

for(short xi=0; xi<l; xi++) {

for(short yi=0; yi<l; yi++) { //перебор всех клеток

LongNum neighbor_sum;

for(auto e: nbs[side][xi][yi].n) { //перебор всех соседей

neighbor_sum.add(cubes[flag][e.side][e.x][e.y]);

//сложение количества путей ко всем соседям на предыдущем шаге

}

cubes[!flag][side][xi][yi] = neighbor_sum;

//запись получившейся суммы в клетку

}

flag = !flag; //замена местами массива для предыдущего шага и нынешнего

}

cubes[flag][1][l/2][l/2].print();

//вывод количества путей к центру соседней грани на m-ом шаге

}

Решение

Из условия можно понять, что задача про специфического вида граф, по которому движется шашка. Его вершинами являются клетки на гранях куба, а дуги лежат между клетками с общими границами. Очевидно количество путей за $m$ шагов до любой точки в графе будет равняться сумме количества путей за $m-1$ шагов ко всем соседним вершинам, то есть мы можем получать решение задачи для $m$ шагов из решения меньшей задачи для $m-1$ шагов, из чего можно понять что это задача на динамическое программирование.
Для решения создадим массив со всеми вершинами и будем хранить в нём количество путей к каждой из них на i-ом шаге. Удобнее всего задать такой массив как 6 числовых матриц размером $ l \times l$, по одной на каждую грань куба.

Раскладка шести граней куба с переходами между границами

Соседство будем определять, прибавляя или отнимая единицу от одной из координат клетки в матрице, например $(x-1, y)$ всегда будет соседом $(x, y)$, не считая крайних случаев, когда $x-1$ будет меньше нуля. Такие ситуации в коде обрабатывает функция FixNeighbor(...), в которой прописаны все подобные крайние случаи.

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

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

Оптимизированный вариант хранения куба

Так как для получения значения клетки через $i$ шагов нужны значения всех её соседей через $i-1$ шагов, а для получения значения соседей через $i$ шагов нужно значение клетки через $i-1$ шагов, нам не хватит только одного массива для перезаписи, надо использовать минимум два для хранения предыдущего и нынешнего состояния. В программе это реализовано с помощью булевой переменной flag — сначала мы вычисляем следующее состояние на основании 0-ого массива ( flag), записывая результат 1-ый ( !flag), а потом инвертируем значение переменной на противоположное и массивы в алгоритме меняются местами.

Ссылки

Related Images:

e-olymp 2270. Поиск цикла

02/12/2019 by Наташа Писаревская

Задача

Дан ориентированный невзвешенный граф. Необходимо определить есть ли в нём циклы, и если есть, то вывести любой из них.

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

В первой строке находятся два натуральных числа $n$ и $m$ $($$1$ $\leqslant$ $n$ $\leqslant$ $10$^$5$$, $$1$ $\leqslant$ $m$ $\leqslant$ $10$^$5$$)$ — количество вершин и ребер в графе соответственно. Далее в $m$ строках перечислены рёбра графа. Каждое задаётся парой чисел — номерами начальной и конечной вершин соответственно.

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

Если в графе нет цикла, то вывести «NO», иначе вывести «YES» и затем перечислить вершины в порядке обхода цикла.

Тесты

№	Входные данные	Выходные данные
1	2 2 1 2 1 2	NO
2	2 2 1 2 2 1	YES 1 2
3	6 7 1 2 1 5 2 3 2 4 4 6 6 5 5 2	YES 2 4 6 5
4	6 6 1 3 2 4 3 4 1 2 3 5 3 6	NO
5	4 4 1 3 4 2 2 3 3 4	YES 3 4 2

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> graph; 
vector<int> used, path;
int flag, n, m;
// поиск в глубину для каждой вершины
void dfs (int v) {
    if (flag == 1) return; // если уже нашли цикл, то останавливаемся
    else {
        used[v] = 1; // посещаем вершину 
        path.push_back(v); // добавляем ее в порядок обхода графа
        for (int i = 0; i < graph[v].size(); i++) {
            int to = graph[v][i];// следующая вершина графа
            if (used[to] == 1) { // если мы ее посетили, но не вышли из нее, значит мы нашли цикл
                path.push_back(to); // добавляем следующую вершину в порядок обхода графа
                flag = 1; // ставим индикатор, что мы нашли цикл и останавливаемся
                return;
            } 
            else {
                dfs(to); // если не посетили, то посещаем 
            }
            if (flag == 1) return; // если нашли цикл, то останавливаемся 
        }
        used[v] = 2; // если не нашли цикл, то выходим из вершины 
        path.pop_back();
    }
} 
// проверяем вершины на наличие цикла 
void checkNodes() { 
    for (int i = 1; i <= n; i++) {
        if (used[i] == 0) { // если не посещали вершину, то посещаем ее 
            dfs(i);
            if (flag == 1) return; // если нашли цикл, то останавливаемся
        }   
    }
} 
int main(){
    int v1, v2; 
    cin >> n >> m; // считываем количество вершин и ребер 
    graph.resize(n + 1); 
    used.resize(n + 1, 0);
    for (int i = 0; i < m; i++) {
        cin >> v1 >> v2; // считываем ребра и заполняем граф
        graph[v1].push_back(v2);
    }
    checkNodes();  // проверяем вершины на наличие цикла
    if (flag == 1) { // если цикл найден
        int i = path.size() - 2; // последняя вершина цикла   
        int to = path.back(); // вершина в которой зациклились 
        while (path[i] != to) { // получаем индекс вершины в которой зациклились
            i--;
        }
        cout << "YES" << endl;
        while (i < path.size() - 1) { // выводим сам цикл
            cout << path[i] << " ";
            i++; 
        }
        cout << endl;
    }
    else cout << "NO" << endl;
}

#include <iostream>

#include <vector>

using namespace std;

vector<vector<int>> graph;

vector<int> used, path;

int flag, n, m;

// поиск в глубину для каждой вершины

void dfs (int v) {

if (flag == 1) return; // если уже нашли цикл, то останавливаемся

else {

used[v] = 1; // посещаем вершину

path.push_back(v); // добавляем ее в порядок обхода графа

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

int to = graph[v][i];// следующая вершина графа

if (used[to] == 1) { // если мы ее посетили, но не вышли из нее, значит мы нашли цикл

path.push_back(to); // добавляем следующую вершину в порядок обхода графа

flag = 1; // ставим индикатор, что мы нашли цикл и останавливаемся

return;

}

else {

dfs(to); // если не посетили, то посещаем

}

if (flag == 1) return; // если нашли цикл, то останавливаемся

}

used[v] = 2; // если не нашли цикл, то выходим из вершины

path.pop_back();

}

// проверяем вершины на наличие цикла

void checkNodes() {

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

if (used[i] == 0) { // если не посещали вершину, то посещаем ее

dfs(i);

if (flag == 1) return; // если нашли цикл, то останавливаемся

}

int main(){

int v1, v2;

cin >> n >> m; // считываем количество вершин и ребер

graph.resize(n + 1);

used.resize(n + 1, 0);

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

cin >> v1 >> v2; // считываем ребра и заполняем граф

graph[v1].push_back(v2);

}

checkNodes(); // проверяем вершины на наличие цикла

if (flag == 1) { // если цикл найден

int i = path.size() - 2; // последняя вершина цикла

int to = path.back(); // вершина в которой зациклились

while (path[i] != to) { // получаем индекс вершины в которой зациклились

i--;

}

cout << "YES" << endl;

while (i < path.size() - 1) { // выводим сам цикл

cout << path[i] << " ";

i++;

}

cout << endl;

}

else cout << "NO" << endl;

}

Решение

Для решения данной задачи воспользуемся поиском в глубину. Также будем отмечать вершины в различными цветами ($0$ (белый) — мы еще не посещали вершину, $1$ (серый) — посетили вершину и не вышли из нее (зациклились), $2$ (черный) — посетили вершину и вышли из неё).

В векторе $graph$ будем хранить сам граф, для проверки на цикличность воспользуемся вектором $visited$, так же будем хранить порядок обхода графа в векторе $path$. Так как по условию, в случае нескольких циклов, необходимо вывести любой, то мы будем находить первый и на этом останавливаться, для этого заведем переменную $flag$, которая равна 1, если цикл уже найден, и равна 0, если цикл еще не найден. В векторе $visited$ будем окрашивать вершину в один из цветов. Если мы захотим посетить $1$ (серую) вершину, то это будет означать, что мы отыскали цикл в этой вершине, тогда устанавливаем $flag = 1$.

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

Ссылки

Условие задачи на e-olymp

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

Related Images:

e-olymp 8361. Робот

25/12/2018 by Богдан Подгорный

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

Условие

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

[latex]S[/latex] — сделать шаг вперед
[latex]L[/latex] — повернуться на [latex]90°[/latex] влево
[latex]R[/latex] — повернуться на [latex]90°[/latex]вправо

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

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

Одна строка из заглавных латинских букв [latex]S[/latex], [latex]L[/latex], [latex]R[/latex], описывающая программу для робота. Общее число команд в программе не превышает [latex]200[/latex], при этом команд [latex]S[/latex] — не более [latex]50[/latex].

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

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

Тесты

№	Inputs	Outputs
1	SSLSLSLSSRSRS	5
2	LSSSS	-1
3	LLSRSRSRSLLLLSSSSLRSRSSSRSRSRS	15
4	LLLLLLLL	-1
5	SRLSRLSLRSLRLSLSLSLSSSLRLSSLRSLRSRSRSRSLRLSRLLLLLSRLSRL	7

Код

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

struct point{
    int x, y;
    point(){
        x = 0;
        y = 0;
    }
    point(int x1,int y1){
        x=x1;
        y=y1;
    }
    bool isequal(point&a, point&b);
}my_point;
 
bool point::isequal(point&a, point&b){
    return a.x == b.x and a.y == b.y;
} 
 
int main() {
    int counter = 0, x = 0, y = 0, res = 0;
    point a;
    char c;
    bool stop = false;
    vector coor(1);
    while(cin >> c and stop == false){
        if(c == 'L'){
            counter = (counter + 1)%4;
        }
        else if(c == 'R'){
            counter = ((counter - 1) + 4)%4;
        }
        else{
            if(counter == 0){
                y++;
            }
            else if(counter == 1){
                x--;
            }
            else if(counter == 2){
                y--;
            }
            else{
                x++;
            }
            res++;
            point a(x,y);
            for(int j = 1; j < coor.size();j++){
                if(my_point.isequal(coor[j],a)){
                    stop = true;
                }
            }
            coor.push_back(a);
        }
    }
    cout << ((stop == true) ? res : -1);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

struct point{

int x, y;

point(){

x = 0;

y = 0;

}

point(int x1,int y1){

x=x1;

y=y1;

}

bool isequal(point&a, point&b);

}my_point;

bool point::isequal(point&a, point&b){

return a.x == b.x and a.y == b.y;

}

int main() {

int counter = 0, x = 0, y = 0, res = 0;

point a;

char c;

bool stop = false;

vector coor(1);

while(cin >> c and stop == false){

if(c == 'L'){

counter = (counter + 1)%4;

}

else if(c == 'R'){

counter = ((counter - 1) + 4)%4;

}

else{

if(counter == 0){

y++;

}

else if(counter == 1){

x--;

}

else if(counter == 2){

y--;

}

else{

x++;

}

res++;

point a(x,y);

for(int j = 1; j < coor.size();j++){

if(my_point.isequal(coor[j],a)){

stop = true;

}

coor.push_back(a);

}

cout << ((stop == true) ? res : -1);

return 0;

}

Решение

Если представить, что точка старта движения робота имеет координаты [latex]\left(0;0 \right)[/latex], то, соответственно, при движении координата будет изменяться на 1 единицу за шаг. Всего координата может изменяться четырьмя способами: координата [latex]x[/latex] уменьшается на единицу, координата [latex]x[/latex] увеличивается на единицу, координата [latex]y[/latex] уменьшается на единицу, координата [latex]y[/latex] увеличивается на единицу. Тогда можно сделать вывод, что эти 4 состояния можно привязать к счетчику, который будет меняться при каждом повороте налево и направо. Для хранения координат как единого объекта можно создать структуру point. Также необходимо запоминать в массив координаты точки после передвижения вперед для того, чтобы в будущем проверять каждую точку на совпадение с предыдущими, чтобы знать когда прервать проверку строки. В главном цикле при встрече символа «[latex]S[/latex]» делаем проверку на состояние счетчика, чтобы увеличивать соответствующую координату. После изменения координаты необходимо проверить ее на совпадение с предыдущими, если она совпала, то назначаем переменной stop значение true для того, чтобы прервать цикл и вывести результат. Если координата не совпала, то добавляем ее в массив(если использовать vector, это делается с помощью команды push_back(), если обычный массив, то придется создать дополнительную переменную и увеличивать ее каждую встречу команды «[latex]S[/latex]»). Если в итоге робот не вернется в то место, где побывал, то переменная stop останется со значением false и выведется «[latex]-1[/latex]».

Ссылки

Related Images:

e-olymp 333. Детская железная дорога-2

18/06/2017 by Антон Куперман

Задача

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

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

Сколько всего разных слов может быть в таком необычном «английском» словаре Витэка?

Тесты

Входные данные	Выходные данные
ALPHABET	35
AAAA	4
UNIVERSITY	54
ABABABABC	24

Код на C++

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

int main() {
    string a;
    vector <string> c;
    vector<string> :: iterator it;// задаем итератор
    cin>>a;
    for(int i=0;i<a.size();i++)
    {
        for(int j=1;j<a.size();j++)
        {
            c.push_back(a.substr(i,j));
        }
    }
    sort(c.begin(), c.end()); // сортируем вектор для функции unique
    it = unique(c.begin(), c.end()); // задаем итератору значение функции unigue
    c.resize(it - c.begin());// производим resize вектора при помощи итератора
    cout<<c.size()+1;
    return 0;
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

string a;

vector <string> c;

vector<string> :: iterator it;// задаем итератор

cin>>a;

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

{

for(int j=1;j<a.size();j++)

{

c.push_back(a.substr(i,j));

}

sort(c.begin(), c.end()); // сортируем вектор для функции unique

it = unique(c.begin(), c.end()); // задаем итератору значение функции unigue

c.resize(it - c.begin());// производим resize вектора при помощи итератора

cout<<c.size()+1;

return 0;

}

Код на Java

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

public class Main
{
    public static void main (String[] args) 
    {
        Scanner in = new Scanner(System.in);
        Vector<String> c = new Vector<String>();
        String a = in.nextLine();
        for(int i=0;i<a.length();i++)
        {
            for(int j=i+1;j<=a.length();j++)
            {
                c.add(a.substring(i,j));
            }
        }
        HashSet<String> unique = new HashSet<String>(c);
        Vector<String> d = new Vector<String>(unique);
        System.out.print(d.size());
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

Vector<String> c = new Vector<String>();

String a = in.nextLine();

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

{

for(int j=i+1;j<=a.length();j++)

{

c.add(a.substring(i,j));

}

HashSet<String> unique = new HashSet<String>(c);

Vector<String> d = new Vector<String>(unique);

System.out.print(d.size());

}

Решение

Казалось бы, задачу можно решить простым циклом. Ведь в 6-буквенном слове: 6 однобуквенных слов, 5 двубуквенных и т.д. Однако очевидной становится проблема повторения,причем не только повторений букв, но и повторений подстрок, что изрядно усложняет наше решение. Создадим вектор, состоящий из строк, куда мы будем добавлять все подстроки строки из входного потока. Отсортируем полученный вектор. Это нужно для того чтобы одинаковые элементы шли рядом с друг другом. Тогда мы можем использовать функцию unique(), которая удалит из вектора все повторяющиеся элементы, кроме одного. Для того, чтобы провести resize() вектора нам понадобится итератор, который мы приравняем к функции unique(). После resize() останется только вывести размер вектора и прибавить к нему единицу, так как само слово не является подстрокой.

Ссылки

1.Код на С++

2.Код на Java

3.Условие на e-olymp

Related Images:

A272. Количество осадков

07/05/2017 by Тимур Фирсов

Задача

Даны действительные числа [latex]a_{1}, a_{2}, …, a_{n}[/latex] – количество осадков (в миллиметрах), выпавших в Москве в течение [latex]n[/latex] лет. Вычислить среднее количество осадков [latex]average[/latex] и отклонение от среднего для каждого года [latex]d_{1}, d_{2}, …, d_{n}[/latex].

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

Последовательность действительных чисел.

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

Среднее количество осадков [latex]average[/latex].
Последовательность действительных чисел [latex]d_{1}, d_{2}, …, d_{n}[/latex] — отклонение от среднего.

Тесты

№	Входные данные	Выходные данные
1	0 0 0 0 0 0 1 0 0 0	0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.9 0.1 0.1 0.1
2	1.23 2.34 3.45 4.56 5.67	3.45 2.22 1.11 0 1.11 2.22
3	234.109 4655.15 43.629 14.109	1236.75 1002.64 3418.4 1193.12 1222.64
4	5 5 5 5 5 5	5 0 0 0 0 0 0

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

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

int main() {
    vector <long double> v;
    long double a, average=0;
    while(cin>>a){
        average+=a;
        v.push_back(a);
    }
    average/=v.size();
    cout<<average<<'\n';
    for(int i=0; i<v.size(); i++)cout<<abs(v[i]-average)<<' ';
    return 0;
}

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

int main() {

vector <long double> v;

long double a, average=0;

while(cin>>a){

average+=a;

v.push_back(a);

}

average/=v.size();

cout<<average<<'\n';

for(int i=0; i<v.size(); i++)cout<<abs(v[i]-average)<<' ';

return 0;

}

Решение

В цикле считываем числа из входного потока и прибавляем их к переменной [latex]average[/latex] (изначально [latex]average=0[/latex]), а также помещаем их в вектор [latex]v[/latex]. Далее делим [latex]average[/latex] на количество элементов в векторе, таким образом получим среднее количество осадков. Затем при помощи цикла поочередно будем выводить отклонение от среднего количества осадков для каждого года. Отклонением от среднего будет абсолютная величина разности соответствующего элемента вектора [latex]v[/latex] и среднего значения [latex]average[/latex].

Ссылки

Код программы
Условие задачи (страница 117).

Related Images:

e-olymp 1075. Умножение многочленов

06/05/2017 by Эммануил Прокопов

Задача с сайта e-olymp.com.
Засчитанное решение. (C++)
Засчитанное решение. (Java)

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

Вводится в символьной форме два многочлена от [latex]x[/latex] с целыми коэффициентами. Вывести их произведение в порядке убывания степеней — также в символьной форме. Степень исходных многочленов не более [latex]10[/latex], коэффициенты исходных многочленов по модулю не более [latex]{ 10 }^{ 4 }[/latex].

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

В двух строках находятся многочлены.

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

В единственной строке выводится многочлен.

Тесты

№	Входные данные	Выходные данные
1	0 0	0
2	x+1 x-1	x^2-1
3	-5 x^2+x+x-2x^3	10x^3-5x^2-10x
3	x^10+2x^9+3x^8 -1	-x^10-2x^9-3x^8
4	x^10+2x^9+3x^8 0	0
5	x^10+5x^2 x^3-4x	x^13-4x^11+5x^5-20x^3

Решение с использованием класса string

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

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

int str_to_int(string &s, int begin, int end){ //Принимает строку и индексы первого и последнего символов, между которыми в ней (предположительно) записано число (последний не включительно).
    int val = 0;                //Возвращает объект типа int, значение которого равно этому числу.
    bool negative = 0;          //Является ли число отрицательным?
    if(s[begin] == '+') begin++;//Плюс игнорируется.
    else{
        if(s[begin] == '-'){    //Проверка на отрицательность.
            negative = 1;
            begin++;
        }
    }
    for(auto i = begin; i < end; ++i){   //Обработка самих цифр числа.
        val *= 10;
        val += s[i] - 48;
    }
    if(val == 0 && s[begin] != '0') val++; //Если значение получилось равным нулю, но в исходной строке не только ноль, значит, обрабатывается строка вида "+x", в которой при записи опускается единица
    if(negative == 1) val *= -1;
    return val;
}

string int_to_str(int val){ //Возвращает строку с записанным в ней числом val.
    string s, tmp;
    if(val > 0) s.push_back('+'); //Проверка на отрицательность.
    else{
        val *= -1;
        s.push_back('-');
    }
    while(val > 0){
        tmp.push_back(val%10 + 48);  //В tmp хранится запись числа в обратном порядке.
        val /= 10;
    }
    for(int i = tmp.size()-1; i >= 0; --i){ //Переписывание элементво из tmp в s в верном порядке.
        s.push_back(tmp[i]);
    }
    return s;
}

void erase_the_plus(string &s){  //Удаляет плюс, стоящий в начале строки.
    if(s[0] == '+') s.erase(s.begin());
}

void erase_the_one(string &s){   //Удаляет единицу из строк вида "+1", "-1".
    if((s[1] == '1') && (s.size() == 2)) s.erase(s.begin()+1);
}

void analyze(string &s, vector <int> &v){  //Анализирует строку и увеличивает соответствующие элементы вектора на коэфициенты при степенях х.
    if(s.find("x") == string::npos) v[0] += str_to_int(s, 0, s.size()); //Если в строке содержится запись константаы.
    else{
        if(s.find("^") == string::npos) v[1] += str_to_int(s, 0, s.find("x"));  //Строка вида "ax".
        else{
            int power = str_to_int(s, s.find("^") + 1, s.size()); //Строка вида "ax^y".
            v[power] += str_to_int(s, 0, s.find("x"));
        }
    }
}

vector <int> decompose(string &s){ //Разбивает многочлен на слагаемые и возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.
    vector <int> v(11);
    string cur_s;
    int i = 0;
    while(i < s.size()){
        cur_s.clear();
        cur_s.push_back(s[i]);
        i++;
        while((s[i] != '+') && (s[i] != '-') && (i < s.size())){ //cur_s - анализируемое в данный момент слагаемое.
            cur_s.push_back(s[i]);
            i++;
        }
        analyze(cur_s, v);
    }
    return v;
}

vector <int> multiplicate (vector <int> &a, vector <int> &b){ //Умножение многочленов.
    vector <int> c(21);       //Возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.
    for(int i = 0; i < c.size(); ++i) c[i] = 0;
    for(int i = 0; i < a.size(); ++i){
        for(int j = 0; j < b.size(); ++j){
            c[i + j] += a[i] * b[j];
        }
    }
    return c;
}

string compose(vector <int> &v){ //Из элементов вектора составляет строку, в которой записан многочлен.
    string s;
    for(int i = v.size() - 1; i >= 2; --i){
        if(v[i] != 0){
            string coef = int_to_str(v[i]); //Коэффициент.
            erase_the_one(coef);
            s = s + coef;
            s.push_back('x');
            s.push_back('^');
            string power = int_to_str(i);  //Степень х.
            erase_the_plus(power);
            s = s + power;
        }
    }
    if(v[1] != 0){   //Записи слагаемых с первой и нулевой степенями х отличаются.
        string coef = int_to_str(v[1]);
        erase_the_one(coef);
        s = s + coef;
        s.push_back('x');
    }
    if(v[0] != 0){
        s = s + int_to_str(v[0]);
    }
    return s;
}

int main() {
    string a,b;
    vector <int> a_decomposed(11, 0);
    vector <int> b_decomposed(11, 0);
    getline(cin, a);    //Ввод многочленов.
    getline(cin, b);
    a_decomposed = decompose(a);
    b_decomposed = decompose(b);
    vector <int> c_decomposed = multiplicate(a_decomposed, b_decomposed);
    string c = compose(c_decomposed);
    erase_the_plus(c);  //Удаляется первый плюс, если он есть.
    if(c.size() > 0) cout << c;
    else cout << 0;       //Если в ответе получаем константу 0.
    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

#include <iostream>

#include <string>

#include <vector>

using namespace std;

int str_to_int(string &s, int begin, int end){ //Принимает строку и индексы первого и последнего символов, между которыми в ней (предположительно) записано число (последний не включительно).

int val = 0; //Возвращает объект типа int, значение которого равно этому числу.

bool negative = 0; //Является ли число отрицательным?

if(s[begin] == '+') begin++;//Плюс игнорируется.

else{

if(s[begin] == '-'){ //Проверка на отрицательность.

negative = 1;

begin++;

}

for(auto i = begin; i < end; ++i){ //Обработка самих цифр числа.

val *= 10;

val += s[i] - 48;

}

if(val == 0 && s[begin] != '0') val++; //Если значение получилось равным нулю, но в исходной строке не только ноль, значит, обрабатывается строка вида "+x", в которой при записи опускается единица

if(negative == 1) val *= -1;

return val;

}

string int_to_str(int val){ //Возвращает строку с записанным в ней числом val.

string s, tmp;

if(val > 0) s.push_back('+'); //Проверка на отрицательность.

else{

val *= -1;

s.push_back('-');

}

while(val > 0){

tmp.push_back(val%10 + 48); //В tmp хранится запись числа в обратном порядке.

val /= 10;

}

for(int i = tmp.size()-1; i >= 0; --i){ //Переписывание элементво из tmp в s в верном порядке.

s.push_back(tmp[i]);

}

return s;

}

void erase_the_plus(string &s){ //Удаляет плюс, стоящий в начале строки.

if(s[0] == '+') s.erase(s.begin());

}

void erase_the_one(string &s){ //Удаляет единицу из строк вида "+1", "-1".

if((s[1] == '1') && (s.size() == 2)) s.erase(s.begin()+1);

}

void analyze(string &s, vector <int> &v){ //Анализирует строку и увеличивает соответствующие элементы вектора на коэфициенты при степенях х.

if(s.find("x") == string::npos) v[0] += str_to_int(s, 0, s.size()); //Если в строке содержится запись константаы.

else{

if(s.find("^") == string::npos) v[1] += str_to_int(s, 0, s.find("x")); //Строка вида "ax".

else{

int power = str_to_int(s, s.find("^") + 1, s.size()); //Строка вида "ax^y".

v[power] += str_to_int(s, 0, s.find("x"));

}

vector <int> decompose(string &s){ //Разбивает многочлен на слагаемые и возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.

vector <int> v(11);

string cur_s;

int i = 0;

while(i < s.size()){

cur_s.clear();

cur_s.push_back(s[i]);

i++;

while((s[i] != '+') && (s[i] != '-') && (i < s.size())){ //cur_s - анализируемое в данный момент слагаемое.

cur_s.push_back(s[i]);

i++;

}

analyze(cur_s, v);

}

return v;

}

vector <int> multiplicate (vector <int> &a, vector <int> &b){ //Умножение многочленов.

vector <int> c(21); //Возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.

for(int i = 0; i < c.size(); ++i) c[i] = 0;

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

for(int j = 0; j < b.size(); ++j){

c[i + j] += a[i] * b[j];

}

return c;

}

string compose(vector <int> &v){ //Из элементов вектора составляет строку, в которой записан многочлен.

string s;

for(int i = v.size() - 1; i >= 2; --i){

if(v[i] != 0){

string coef = int_to_str(v[i]); //Коэффициент.

erase_the_one(coef);

s = s + coef;

s.push_back('x');

s.push_back('^');

string power = int_to_str(i); //Степень х.

erase_the_plus(power);

s = s + power;

}

if(v[1] != 0){ //Записи слагаемых с первой и нулевой степенями х отличаются.

string coef = int_to_str(v[1]);

erase_the_one(coef);

s = s + coef;

s.push_back('x');

}

if(v[0] != 0){

s = s + int_to_str(v[0]);

}

return s;

}

int main() {

string a,b;

vector <int> a_decomposed(11, 0);

vector <int> b_decomposed(11, 0);

getline(cin, a); //Ввод многочленов.

getline(cin, b);

a_decomposed = decompose(a);

b_decomposed = decompose(b);

vector <int> c_decomposed = multiplicate(a_decomposed, b_decomposed);

string c = compose(c_decomposed);

erase_the_plus(c); //Удаляется первый плюс, если он есть.

if(c.size() > 0) cout << c;

else cout << 0; //Если в ответе получаем константу 0.

return 0;

}

Нажмите, чтобы выполнить его на ideone.com.

Описание

Сначала в функции main объявляются две строки a и b. В них водятся исходные два многочлена. Но в форме строк, особенно учитывая, что подобные слагаемые не всегда приведены, умножать многочлены не удобно. Потому объявляются три вектора: a_decomposed, b_decomposed и c_decomposed. Первые два имеют размер [latex]11[/latex], поскольку в условии сказано, что многочлены могут быть от нулевой до десятой степени включительно. В них элемент с индексом [latex]i[/latex] равняется коэффициенту при слагаемом многочлена, в котором [latex]x[/latex] имеет степень [latex]i[/latex]. Они заполняются при помощи функции decompose. В ней при помощи функции analyze отдельно анализируется каждое слагаемое многочлена, и результат заносится в вектор. c_decomposed хранит коэффициенты многочлена, полученного умножением двух исходных. Значения его элементов вычисляются при помощи функции multiplicate. После в ходе работы функции compose многочлен в требуемой форме записывается в строку c. Далее, если её первым символом является [latex]+[/latex], он удаляется из строки. Наконец, если c — непустая строка, она выводится. Иначе выводится [latex]0[/latex].

Решение с использованием c-string

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

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

int str_to_int(char *s, int begin, int end){//Принимает адрес первого элемента строки и индексы первого и последнего символов, между которыми в ней (предположительно) записано число (последний не включительно).
    int val = 0;        //Возвращает объект типа int, значение которого равно этому числу.
    bool negative = 0;  //Является ли число отрицательным?
    if(s[begin] == '+') begin++;//Плюс игнорируется.
    else{
        if(s[begin] == '-'){    //Проверка на отрицательность.
            negative = 1;
            begin++;
        }
    }
    for(auto i = begin; i < end; ++i){   //Обработка самих цифр числа.
        val *= 10;
        val += s[i] - 48;
    }
    if(val == 0 && s[begin] != '0') val++; //Если значение получилось равным нулю, но в исходной строке не только ноль, значит, обрабатывается строка вида "+x", в которой при записи опускается единица
    if(negative == 1) val *= -1;
    return val;
}

void int_to_str(int val, char *s){ //Записывает в строку s число val.
    char tmp[5];
    if(val > 0) s[0] = '+';  //Проверка на отрицательность.
    else{
        val *= -1;
        s[0] = '-';
    }
    int i = 0;
    while(val > 0){
        tmp[i] = (val%10 + 48); //В tmp хранится запись числа в обратном порядке.
        val /= 10;
        i++;
    }
    tmp[i] = 0;
    int j = 1;
    for(i = strlen(tmp)-1; i >= 0; --i){ //Переписывание элементво из tmp в s в верном порядке.
        s[j] = tmp[i];
        j++;
    }
    s[j] = 0; //Если строка получилась короче пяти символов, нужно поставить после последнего нулевой символ.
}

void erase_the_plus(char *s){   //Удаляет плюс, стоящий в начале строки.
    if(s[0] == '+'){
        for(int i = 0; s[i] != 0; ++i){
            s[i] = s[i+1];
        }
    }
}

void erase_the_one(char *s){        //Удаляет единицу из строк вида "+1", "-1".
    if((s[1] == '1') && (strlen(s) == 2)){
        s[1] = 0;
    }
}

void analyze(char *s, vector <int> &v){       //Анализирует строку и увеличивает соответствующие элементы вектора на коэфициенты при степенях х.
    if(strchr(s, 'x') == NULL) v[0] += str_to_int(s, 0, strlen(s));     //Если в строке содержится запись константаы.
    else{
        if(strchr(s, '^') == NULL) v[1] += str_to_int(s, 0, strchr(s, 'x') - s);//Строка вида "ax".
        else{
            int power = str_to_int(s, strchr(s, '^') - s + 1, strlen(s));
            v[power] += str_to_int(s, 0, strchr(s, 'x') - s);
        }
    }
}
 
vector <int> decompose(char *s){//Разбивает многочлен на слагаемые и возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.
    vector <int> v(11);
    char cur_s[10];
    int i = 0, j;
    while(s[i] != 0){
        //cur_s[0] = 0;
        cur_s[0] = s[i];
        i++;
        j = 1;
        while((s[i] != '+') && (s[i] != '-') && (s[i] != 0)){   //cur_s - анализируемое в данный момент слагаемое.
            cur_s[j] = s[i];
            i++;
            j++;
        }
        cur_s[j] = 0;
        analyze(cur_s, v);
    }
    return v;
}
 
vector <int> multiplicate (vector <int> &a, vector <int> &b){ //Умножение многочленов.
    vector <int> c(21);   //Возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.
    for(int i = 0; i < c.size(); ++i) c[i] = 0;
    for(int i = 0; i < a.size(); ++i){
        for(int j = 0; j < b.size(); ++j){
            c[i + j] += a[i] * b[j];
        }
    }
    return c;
}
 
void compose(char *s, vector <int> &v){   //Из элементов вектора составляет строку, в которой записан многочлен.
    for(int i = v.size() - 1; i >= 2; --i){
        if(v[i] != 0){
            char coef[6];   //Коэффициент.
            int_to_str(v[i], coef);
            erase_the_one(coef);
            strcat(s, coef);
            strcat(s, "x");
            strcat(s, "^");
            char power[2];  //Степень х.
            int_to_str(i, power);
            erase_the_plus(power);
            strcat(s, power);
        }
    }
    if(v[1] != 0){  //Записи слагаемых с первой и нулевой степенями х отличаются.
        char coef[6];
        int_to_str(v[1], coef);
        erase_the_one(coef);
        strcat(s, coef);
        strcat(s, "x");
    }
    if(v[0] != 0){
        char coef[6];
        int_to_str(v[0], coef);
        strcat(s, coef);
    }
}
 
int main() {
    char *a, *b;
    int max_number_of_symbols = 100;
    a = new char[max_number_of_symbols];
    b = new char[max_number_of_symbols];
    vector <int> a_decomposed(11, 0);
    vector <int> b_decomposed(11, 0);
    
    cin.getline(a, max_number_of_symbols);  //Ввод многочленов.
    cin.getline(b, max_number_of_symbols);
    a_decomposed = decompose(a);
    b_decomposed = decompose(b);
    
    vector <int> c_decomposed = multiplicate(a_decomposed, b_decomposed);
    char *c;
    c = new char[max_number_of_symbols];
    compose(c, c_decomposed);
    erase_the_plus(c);  //Удаляется первый плюс, если он есть.
    if(strlen(c) > 0) cout << c;
    else cout << 0;       //Если в ответе получаем константу 0.
    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

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

#include <iostream>

#include <cstring>

#include <vector>

using namespace std;

int str_to_int(char *s, int begin, int end){//Принимает адрес первого элемента строки и индексы первого и последнего символов, между которыми в ней (предположительно) записано число (последний не включительно).

int val = 0; //Возвращает объект типа int, значение которого равно этому числу.

bool negative = 0; //Является ли число отрицательным?

if(s[begin] == '+') begin++;//Плюс игнорируется.

else{

if(s[begin] == '-'){ //Проверка на отрицательность.

negative = 1;

begin++;

}

for(auto i = begin; i < end; ++i){ //Обработка самих цифр числа.

val *= 10;

val += s[i] - 48;

}

if(negative == 1) val *= -1;

return val;

}

void int_to_str(int val, char *s){ //Записывает в строку s число val.

char tmp[5];

if(val > 0) s[0] = '+'; //Проверка на отрицательность.

else{

val *= -1;

s[0] = '-';

}

int i = 0;

while(val > 0){

tmp[i] = (val%10 + 48); //В tmp хранится запись числа в обратном порядке.

val /= 10;

i++;

}

tmp[i] = 0;

int j = 1;

for(i = strlen(tmp)-1; i >= 0; --i){ //Переписывание элементво из tmp в s в верном порядке.

s[j] = tmp[i];

j++;

}

s[j] = 0; //Если строка получилась короче пяти символов, нужно поставить после последнего нулевой символ.

}

void erase_the_plus(char *s){ //Удаляет плюс, стоящий в начале строки.

if(s[0] == '+'){

for(int i = 0; s[i] != 0; ++i){

s[i] = s[i+1];

}

void erase_the_one(char *s){ //Удаляет единицу из строк вида "+1", "-1".

if((s[1] == '1') && (strlen(s) == 2)){

s[1] = 0;

}

void analyze(char *s, vector <int> &v){ //Анализирует строку и увеличивает соответствующие элементы вектора на коэфициенты при степенях х.

if(strchr(s, 'x') == NULL) v[0] += str_to_int(s, 0, strlen(s)); //Если в строке содержится запись константаы.

else{

if(strchr(s, '^') == NULL) v[1] += str_to_int(s, 0, strchr(s, 'x') - s);//Строка вида "ax".

else{

int power = str_to_int(s, strchr(s, '^') - s + 1, strlen(s));

v[power] += str_to_int(s, 0, strchr(s, 'x') - s);

}

vector <int> decompose(char *s){//Разбивает многочлен на слагаемые и возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.

vector <int> v(11);

char cur_s[10];

int i = 0, j;

while(s[i] != 0){

//cur_s[0] = 0;

cur_s[0] = s[i];

i++;

j = 1;

while((s[i] != '+') && (s[i] != '-') && (s[i] != 0)){ //cur_s - анализируемое в данный момент слагаемое.

cur_s[j] = s[i];

i++;

j++;

}

cur_s[j] = 0;

analyze(cur_s, v);

}

return v;

}

vector <int> multiplicate (vector <int> &a, vector <int> &b){ //Умножение многочленов.

for(int i = 0; i < c.size(); ++i) c[i] = 0;

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

for(int j = 0; j < b.size(); ++j){

c[i + j] += a[i] * b[j];

}

return c;

}

void compose(char *s, vector <int> &v){ //Из элементов вектора составляет строку, в которой записан многочлен.

for(int i = v.size() - 1; i >= 2; --i){

if(v[i] != 0){

char coef[6]; //Коэффициент.

int_to_str(v[i], coef);

erase_the_one(coef);

strcat(s, coef);

strcat(s, "x");

strcat(s, "^");

char power[2]; //Степень х.

int_to_str(i, power);

erase_the_plus(power);

strcat(s, power);

}

if(v[1] != 0){ //Записи слагаемых с первой и нулевой степенями х отличаются.

char coef[6];

int_to_str(v[1], coef);

erase_the_one(coef);

strcat(s, coef);

strcat(s, "x");

}

if(v[0] != 0){

char coef[6];

int_to_str(v[0], coef);

strcat(s, coef);

}

int main() {

char *a, *b;

int max_number_of_symbols = 100;

a = new char[max_number_of_symbols];

b = new char[max_number_of_symbols];

vector <int> a_decomposed(11, 0);

vector <int> b_decomposed(11, 0);

cin.getline(a, max_number_of_symbols); //Ввод многочленов.

cin.getline(b, max_number_of_symbols);

a_decomposed = decompose(a);

b_decomposed = decompose(b);

vector <int> c_decomposed = multiplicate(a_decomposed, b_decomposed);

char *c;

c = new char[max_number_of_symbols];

compose(c, c_decomposed);

erase_the_plus(c); //Удаляется первый плюс, если он есть.

if(strlen(c) > 0) cout << c;

else cout << 0; //Если в ответе получаем константу 0.

return 0;

}

Нажмите, чтобы выполнить его на ideone.com.

Описание

Алгоритм решения тот же. Следует отметить: поскольку объекты типа char* «не знают» свою длину, и в силу других причин, в некоторых местах программы используются «магические числа». Однако они не взяты случайно, а продиктованы условием задачи (к примеру, тем, что максимальная степень исходных многочленов — [latex]10[/latex] и т.п.). Только подходящее значение переменной max_number_of_symbols было найдено эмпирически.

Решение на Java

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

import java.util.*;

class Main
{
    static int strToInt(String s, int begin, int end){ //Принимает строку и индексы первого и последнего символов, между которыми в ней (предположительно) записано число (последний не включительно).
        int val = 0;           //Возвращает объект типа int, значение которого равно этому числу.
        boolean negative = false;      //Является ли число отрицательным?
        if(s.charAt(begin) == '+') begin++;//Плюс игнорируется.
        else{
            if(s.charAt(begin) == '-'){   //Проверка на отрицательность.
                negative = true;
                begin++;
            }
        }
        for(int i = begin; i < end; ++i){  //Обработка самих цифр числа.
            val *= 10;
            val += s.charAt(i) - 48;
        }
        if(val == 0 && s.charAt(begin) != '0') val++; //Если значение получилось равным нулю, но в исходной строке не только ноль, значит, обрабатывается строка вида "+x", в которой при записи опускается единица
        if(negative == true) val *= -1;
        return val;
    }
    
    static String intToStr(int val){ //Возвращает строку с записанным в ней числом val.
        String s = "", tmp = "";
        if(val > 0) s = s + "+"; //Проверка на отрицательность.
        else{
            val *= -1;
            s = s + "-";
        }
        while(val > 0){
            tmp = tmp + Integer.toString(val%10); //В tmp хранится запись числа в обратном порядке.
            val /= 10;
        }
        for(int i = tmp.length()-1; i >= 0; --i){ //Переписывание элементво из tmp в s в верном порядке.
            s = s + tmp.charAt(i);
        }
        return s;
    }

    static String eraseThePlus(String s){  //Удаляет плюс, стоящий в начале строки.
        if(s.charAt(0) == '+') s = s.substring(1, s.length());
        return s;
    }
 
    static String eraseTheOne(String s){   //Удаляет единицу из строк вида "+1x", "-1x^y".
        if((s.charAt(1) == '1') && (s.length() == 2)) s = s.charAt(0) + s.substring(2, s.length());
        return s;
    }

    static void analyze(String s, Vector v){  //Анализирует строку и увеличивает соответствующие элементы вектора на коэфициенты при степенях х.
        for(int i = 0; i < 11; ++i) v.addElement(0);
        if(s.indexOf('x') == -1) v.set(0, (int)(v.elementAt(0)) + strToInt(s, 0, s.length())); 
        else{
            if(s.indexOf('^') == -1) v.set(1, (int)(v.elementAt(1)) + strToInt(s, 0, s.indexOf("x")));  //Строка вида "ax".
            else{
                int power = strToInt(s, s.indexOf("^") + 1, s.length()); //Строка вида "ax^y".
                v.set(power, (int)(v.elementAt(power)) + strToInt(s, 0, s.indexOf("x")));
            }
        }
    }
    
    static Vector decompose(String s){ //Разбивает многочлен на слогаемые и возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.
        Vector v = new Vector();
        String cur_s = "";
        int i = 0;
        while(i < s.length()){
            cur_s  = "";
            cur_s = cur_s + s.charAt(i);
            i++;
            while((i < s.length()) && (s.charAt(i) != '+') && (s.charAt(i) != '-')){ //cur_s - анализируемое в данный момент слогаемое.
                cur_s = cur_s + s.charAt(i);
                i++;
            }
            analyze(cur_s, v);
        }
        return v;
    }

    static Vector multiplicate (Vector a, Vector b){ //Умножение многочленов.
        Vector c = new Vector();             //Возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.
        for(int i = 0; i < 21; ++i) c.addElement(0);
        for(int i = 0; i < 11; ++i){
            for(int j = 0; j < 11; ++j){
                c.set(i+j, ((int)(c.elementAt(i+j)))+((int)(a.elementAt(i)))*((int)(b.elementAt(j))));
            }
        }
        return c;
    }

    static String compose(Vector v){ //Из элементов вектора составляет строку, в которой записан многочлен.
        String s = "";
        for(int i = v.size() - 1; i >= 2; --i){
            if((int)v.elementAt(i) != 0){
                String coef = intToStr((int)v.elementAt(i)); //Коэффициент.
                coef = eraseTheOne(coef);
                s = s + coef;
                s = s + "x";
                s = s + "^";
                String power = intToStr(i);  //Степень х.
                power = eraseThePlus(power);
                s = s + power;
            }
        }
        if((int)v.elementAt(1) != 0){   //Записи слогаемых с первой и нулевой степенями х отличаются.
            String coef = intToStr((int)v.elementAt(1));
            coef = eraseTheOne(coef);
            s = s + coef;
            s = s + "x";
        }
        if((int)v.elementAt(0) != 0){
            s = s + intToStr((int)v.elementAt(0));
        }
        return s;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        String a = in.nextLine();
        String b = in.nextLine();
        String c = new String();
        Vector a_decomposed = new Vector(11);
        Vector b_decomposed = new Vector(11);
        a_decomposed = decompose(a);
        b_decomposed = decompose(b);
        Vector c_decomposed = multiplicate(a_decomposed, b_decomposed);
        c = compose(c_decomposed);
        if(c.length() > 0){
            c = eraseThePlus(c); //Удаляется первый плюс, если он есть.
            System.out.print(c);
        }
        else System.out.print(0); //Если в ответе получаем константу 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

133

134

135

import java.util.*;

class Main

{

static int strToInt(String s, int begin, int end){ //Принимает строку и индексы первого и последнего символов, между которыми в ней (предположительно) записано число (последний не включительно).

int val = 0; //Возвращает объект типа int, значение которого равно этому числу.

boolean negative = false; //Является ли число отрицательным?

if(s.charAt(begin) == '+') begin++;//Плюс игнорируется.

else{

if(s.charAt(begin) == '-'){ //Проверка на отрицательность.

negative = true;

begin++;

}

for(int i = begin; i < end; ++i){ //Обработка самих цифр числа.

val *= 10;

val += s.charAt(i) - 48;

}

if(val == 0 && s.charAt(begin) != '0') val++; //Если значение получилось равным нулю, но в исходной строке не только ноль, значит, обрабатывается строка вида "+x", в которой при записи опускается единица

if(negative == true) val *= -1;

return val;

}

static String intToStr(int val){ //Возвращает строку с записанным в ней числом val.

String s = "", tmp = "";

if(val > 0) s = s + "+"; //Проверка на отрицательность.

else{

val *= -1;

s = s + "-";

}

while(val > 0){

tmp = tmp + Integer.toString(val%10); //В tmp хранится запись числа в обратном порядке.

val /= 10;

}

for(int i = tmp.length()-1; i >= 0; --i){ //Переписывание элементво из tmp в s в верном порядке.

s = s + tmp.charAt(i);

}

return s;

}

static String eraseThePlus(String s){ //Удаляет плюс, стоящий в начале строки.

if(s.charAt(0) == '+') s = s.substring(1, s.length());

return s;

}

static String eraseTheOne(String s){ //Удаляет единицу из строк вида "+1x", "-1x^y".

if((s.charAt(1) == '1') && (s.length() == 2)) s = s.charAt(0) + s.substring(2, s.length());

return s;

}

static void analyze(String s, Vector v){ //Анализирует строку и увеличивает соответствующие элементы вектора на коэфициенты при степенях х.

for(int i = 0; i < 11; ++i) v.addElement(0);

if(s.indexOf('x') == -1) v.set(0, (int)(v.elementAt(0)) + strToInt(s, 0, s.length()));

else{

if(s.indexOf('^') == -1) v.set(1, (int)(v.elementAt(1)) + strToInt(s, 0, s.indexOf("x"))); //Строка вида "ax".

else{

int power = strToInt(s, s.indexOf("^") + 1, s.length()); //Строка вида "ax^y".

v.set(power, (int)(v.elementAt(power)) + strToInt(s, 0, s.indexOf("x")));

}

static Vector decompose(String s){ //Разбивает многочлен на слогаемые и возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.

Vector v = new Vector();

String cur_s = "";

int i = 0;

while(i < s.length()){

cur_s = "";

cur_s = cur_s + s.charAt(i);

i++;

while((i < s.length()) && (s.charAt(i) != '+') && (s.charAt(i) != '-')){ //cur_s - анализируемое в данный момент слогаемое.

cur_s = cur_s + s.charAt(i);

i++;

}

analyze(cur_s, v);

}

return v;

}

static Vector multiplicate (Vector a, Vector b){ //Умножение многочленов.

Vector c = new Vector(); //Возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.

for(int i = 0; i < 21; ++i) c.addElement(0);

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

for(int j = 0; j < 11; ++j){

c.set(i+j, ((int)(c.elementAt(i+j)))+((int)(a.elementAt(i)))*((int)(b.elementAt(j))));

}

return c;

}

static String compose(Vector v){ //Из элементов вектора составляет строку, в которой записан многочлен.

String s = "";

for(int i = v.size() - 1; i >= 2; --i){

if((int)v.elementAt(i) != 0){

String coef = intToStr((int)v.elementAt(i)); //Коэффициент.

coef = eraseTheOne(coef);

s = s + coef;

s = s + "x";

s = s + "^";

String power = intToStr(i); //Степень х.

power = eraseThePlus(power);

s = s + power;

}

if((int)v.elementAt(1) != 0){ //Записи слогаемых с первой и нулевой степенями х отличаются.

String coef = intToStr((int)v.elementAt(1));

coef = eraseTheOne(coef);

s = s + coef;

s = s + "x";

}

if((int)v.elementAt(0) != 0){

s = s + intToStr((int)v.elementAt(0));

}

return s;

}

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

{

Scanner in = new Scanner(System.in);

String a = in.nextLine();

String b = in.nextLine();

String c = new String();

Vector a_decomposed = new Vector(11);

Vector b_decomposed = new Vector(11);

a_decomposed = decompose(a);

b_decomposed = decompose(b);

Vector c_decomposed = multiplicate(a_decomposed, b_decomposed);

c = compose(c_decomposed);

if(c.length() > 0){

c = eraseThePlus(c); //Удаляется первый плюс, если он есть.

System.out.print(c);

}

else System.out.print(0); //Если в ответе получаем константу 0.

}

Нажмите, чтобы выполнить его на ideone.com.

Related Images:

А273. Центр тяжести системы

05/05/2017 by Иванна Ялымова

Задача. Задача из сборника задач по программированию С.А.Абрамова за 2000 год.
Система из 25 материальных точек в пространстве задана с помощью последовательности действительных чисел [latex]x_{1}, y_{1}, z_{1}, p_{1}, x_{2}, y_{2}, z_{2}, p_{2},\ldots,x_{25}, y_{25}, z_{25}, p_{25}[/latex], где [latex]x_{i}, y_{i}, z_{i}[/latex] — координаты [latex]i[/latex]-ой точки, а [latex]p_{i}[/latex] — ее вес ([latex]i=1,2,\ldots,25[/latex]). Получить координаты центра тяжести системы, а также расстояние от центра тяжести до всех точек системы.

Входные данные:
[latex]x, y, z, p[/latex] — координаты и вес точки.

Выходные данные:
[latex]sum(x,y,z)[/latex] — координаты центра тяжести системы, [latex]l[/latex] — расстояние от центра тяжести до одной из точек.

Тесты:

Входные данные	Выходные данные
[latex]x[/latex] [latex]y[/latex] [latex]z[/latex] [latex]p[/latex]	[latex]sum[/latex] [latex](x[/latex] [latex]y[/latex] [latex]z)[/latex]	[latex]l[/latex]
2 2 1 2 3 1 2 1	2.33333 1.66667 1.33333	0.57735 1.1547
7 10 5 20 1 0 3 1 43 50 6 3 0 9 0 200 4 8 15 66	1.84138 9.23448 3.83103	5.34452 9.3099 57.9704 4.25705 11.4424

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

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

struct dot {
    double x;
    double y;
    double z;
    dot() {
        x=0;
        y=0;
        z=0;
    }
    dot (double a, double b, double c) {
        x=a;
        y=b;
        z=c;
    }
};
int main() {
    vector <dot> a;
    double x, y, z, p;
    double sump=0;
    dot sum=dot();
    while (cin>>x && 
           cin>>y && 
           cin>>z && 
           cin>>p) 
    {                                           
        a.push_back(dot(x,y,z));
        sum.x+=x*p;
        sum.y+=y*p;
        sum.z+=z*p;
        sump+=p;
    }
    sum.x/=sump;
    sum.y/=sump;
    sum.z/=sump;
    
    cout << sum.x << " " << sum.y << " " << sum.z << endl;
    
    for (int i=0; i<a.size(); i++)
    {
        double l=sqrt((a[i].x-sum.x)*(a[i].x-sum.x) + (a[i].y-sum.y)*(a[i].y-sum.y) + (a[i].z-sum.z)*(a[i].z-sum.z));
        cout << l << endl; 
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

struct dot {

double x;

double y;

double z;

dot() {

x=0;

y=0;

z=0;

}

dot (double a, double b, double c) {

x=a;

y=b;

z=c;

}

};

int main() {

vector <dot> a;

double x, y, z, p;

double sump=0;

dot sum=dot();

while (cin>>x &&

cin>>y &&

cin>>z &&

cin>>p)

{

a.push_back(dot(x,y,z));

sum.x+=x*p;

sum.y+=y*p;

sum.z+=z*p;

sump+=p;

}

sum.x/=sump;

sum.y/=sump;

sum.z/=sump;

cout << sum.x << " " << sum.y << " " << sum.z << endl;

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

{

double l=sqrt((a[i].x-sum.x)*(a[i].x-sum.x) + (a[i].y-sum.y)*(a[i].y-sum.y) + (a[i].z-sum.z)*(a[i].z-sum.z));

cout << l << endl;

}

return 0;

}

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

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

class Dot {
    double x;
    double y;
    double z;
    public Dot() {
        x = 0;
        y = 0;
        z = 0;
    }
    Dot (double a, double b, double c) {
        x=a;
        y=b;
        z=c;
    }
}
class Ideone{
    public static void main (String[] args) throws java.lang.Exception{
        Scanner in = new Scanner(System.in);
        Vector a = new Vector();
        double x, y, z, p;
        double sump=0;
        Dot sum = new Dot();
        while (in.hasNextDouble()){
            x = in.nextDouble();
            y = in.nextDouble();
            z = in.nextDouble();
            p = in.nextDouble();
            a.add(new Dot(x,y,z));
            
            sum.x += x*p;
            sum.y += y*p;
            sum.z += z*p;
            sump+=p;
        }
        sum.x/=sump;
        sum.y/=sump;
        sum.z/=sump;
        
        System.out.println(sum.x + " " + sum.y + " " + sum.z);
        Dot dot;
        for (int i=0; i<a.size(); i++)
        {
            dot = (Dot)a.elementAt(i);
            double l = Math.sqrt((dot.x-sum.x)*(dot.x-sum.x) + (dot.y-sum.y)*(dot.y-sum.y) + (dot.z-sum.z)*(dot.z-sum.z));
            System.out.println(l);
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Dot {

double x;

double y;

double z;

public Dot() {

x = 0;

y = 0;

z = 0;

}

Dot (double a, double b, double c) {

x=a;

y=b;

z=c;

}

class Ideone{

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

Scanner in = new Scanner(System.in);

Vector a = new Vector();

double x, y, z, p;

double sump=0;

Dot sum = new Dot();

while (in.hasNextDouble()){

x = in.nextDouble();

y = in.nextDouble();

z = in.nextDouble();

p = in.nextDouble();

a.add(new Dot(x,y,z));

sum.x += x*p;

sum.y += y*p;

sum.z += z*p;

sump+=p;

}

sum.x/=sump;

sum.y/=sump;

sum.z/=sump;

System.out.println(sum.x + " " + sum.y + " " + sum.z);

Dot dot;

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

{

dot = (Dot)a.elementAt(i);

double l = Math.sqrt((dot.x-sum.x)*(dot.x-sum.x) + (dot.y-sum.y)*(dot.y-sum.y) + (dot.z-sum.z)*(dot.z-sum.z));

System.out.println(l);

}

Решение
В цикле «[latex]while[/latex]» читаем числа из входного потока и запоминаем координаты точек в векторе [latex]а[/latex], к переменной [latex]sum[/latex] прибавляем эти координаты, умноженные на [latex]p[/latex].
Потом подсчитываем координаты центра тяжести системы и выводим эти координаты.
В цикле «[latex]for[/latex]» берем из вектора координаты одной из точек системы, считаем расстояние от центра тяжести до одной из точек системы и выводим это расстояние.

Ссылки
Код в ideone.com (C++)
Код в ideone.com (Java)
Условие задачи (с.117)

Related Images:

А282(а)

03/05/2017 by Антон Куперман

Задача

Даны действительные числа [latex]a_1,a_2, …,a_{2n}[/latex]. Получить:

[latex]a_1,a_{n+1},a_2,a_{n+2}, …,a_n,a_{2n}[/latex]

Тесты

Ввод	Вывод
1 2 3 4 5 6 7 8 9 10	1 6 2 7 3 8 4 9 5 10
8 25 3 7	8 3 25 7
5.5 6.025 2.387 1.0986 7.762 3.5958	5.5 1.0986 6.025 7.762 2.387 3.5958

Хороший код

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

int main() {
    vector <double> s;
    vector <double> l;
    double a,n;
    while(cin>>a)
    {
        s.push_back(a);
    }
    n=s.size()/2;
    for(int i=0;i<n;i++)
    {
        l.push_back(s.at(i));
        l.push_back(s.at(i+n));
    }
    for(int i=0;i<l.size();i++)
    {
        cout<<l.at(i)<<" ";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> s;

vector <double> l;

double a,n;

while(cin>>a)

{

s.push_back(a);

}

n=s.size()/2;

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

{

l.push_back(s.at(i));

l.push_back(s.at(i+n));

}

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

{

cout<<l.at(i)<<" ";

}

return 0;

}

Решение

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

Лучший код на C++

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
        vector <double> s;
        double a,n;
        int b=0;
        while(cin>>a)
        {
                s.push_back(a);
        }
        n=s.size()/2;
        for(int i=0;i<n;i++)
        {
                s.insert(s.begin()+2*i+1,s.at(n+b+i));
                b++;
        }
        s.resize(2*n);
        for(int i=0;i<s.size();i++)
        {
                cout<<s.at(i)<<" ";
        }
        return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> s;

double a,n;

int b=0;

while(cin>>a)

{

s.push_back(a);

}

n=s.size()/2;

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

{

s.insert(s.begin()+2*i+1,s.at(n+b+i));

b++;

}

s.resize(2*n);

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

{

cout<<s.at(i)<<" ";

}

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);
        Vector a = new Vector();
        while(in.hasNextDouble()){ 
            a.add(in.nextDouble()); 
        }
        int n=a.size()/2;
        int b=0;
        for(int i=0;i<n;i++){
            a.add(2*i+1,a.get(n+b+i));
            b++;
        }
        a.setSize(2*n);
        Double[] s = new Double[a.size()];
        a.toArray(s);
        for(int i=0;i<s.length;i++){
            System.out.print(s[i]+" "); 
        }
    }
}

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

Vector a = new Vector();

while(in.hasNextDouble()){

a.add(in.nextDouble());

}

int n=a.size()/2;

int b=0;

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

a.add(2*i+1,a.get(n+b+i));

b++;

}

a.setSize(2*n);

Double[] s = new Double[a.size()];

a.toArray(s);

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

System.out.print(s[i]+" ");

}

Решение

В первом способе мы задавали два вектора, чем естественно увеличивали занимаемую память. C помощью функции insert() мы можем вставлять элементы в вектор, не используя дополнительных средств. Однако мы сталкиваемся с тем, что функция по определению вставляет в вектор константу из-за чего наш цикл не будет правильно работать. Чтобы изменять параметр вводимого элемента, заводим отдельный счетчик. Теперь каждый [latex]2*i+1[/latex]-ый шаг мы вставляем [latex]n+b+i[/latex]-ый элемент вектора. Проведем resize() вектора чтобы убрать лишние элементы и получим готовый результат.

Ссылки

Related Images:

А282в

27/06/2016 by Станислав Коциевский

Задача

Даны действительные числа [latex]a_{1}, a_{2}, \cdots, a_{2n}.[/latex] Получить [latex]a_{1}+a_{2n}, a_{2}+ a_{2n-1}, \cdots, a_{n}+a_{n+1}.[/latex]

Тесты

Входные данные	Выходные данные
2 4 6 2 2 9 7 5	7 11 15 4
1 2 2 1	1 4
139 64 15 20 10 5 6 1	140 70 20 30
111111 22222 33333 11 25 4	111115 22247 33344
15 7 6 9	24 13
2 2	4
138 56 78 3	141 134

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

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

int main()
{
    vector <int> a;
    int b;
    while (cin>>b)
    {
        a.push_back(b);
    }
    for (int i = 0; i<a.size()/2; i++)
    {
        cout<<a[i] + a[a.size()-i-1]<<" ";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

vector <int> a;

int b;

while (cin>>b)

{

a.push_back(b);

}

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

{

cout<<a[i] + a[a.size()-i-1]<<" ";

}

return 0;

}

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

Считаем все числа [latex]a_{1}, \cdots, a_{2n}[/latex] в ранее объявленный вектор, пока есть, что считывать. Поскольку мы используем класс vector и цикл while (cin >> b) и метод push_back(), в числе [latex]n[/latex] нет необходимости, а во входых данных присутствуют только сами числа [latex]a_{1}, \cdots, a_{2n}[/latex]. Далее, чтобы узнать количество элементов в векторе, будем использовать метод size(). Остается только выводить в цикле сумму двух текущих чисел, начиная с краев вектора и сдвигаясь в каждом витке на элемент ближе к центру вектора, пока не дойдем до центра.

Ссылки

Задача взята из задачника С. Абрамова;
Ссылка на код на ideone.com.

Related Images:

A285

01/06/2016 by Максим Носов

Задача

Даны действительные числа [latex]{ a }_{ 1 }[/latex]…[latex]{ a }_{ n }[/latex] . Если в результате замены отрицательных членов последовательности [latex]{ a }_{ 1 }[/latex]…[latex]{ a }_{ n }[/latex] их квадратами члены будут образовывать неубывающую последовательность, то получить сумму членов исходной последовательности ; в противном случае получить их произведение.

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

Последовательность

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

Сумма членов, если последовательность неубывающая и их произведение в противном случае.

Тесты

№	Последовательность	Результат
1	1 2 3 4	10
2	1 2 -3 4	-24
3	1 -2 5 6 7 8	25
4	-1 -1 -2 -3 -4 -5	-16

Код

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector <double> x; //задаем элемент типа vector
    double a,m=0,k=0,n=0;
    while(cin>>a){     //вводим последовательность
        x.push_back(a);  //для дальнейшего преобразования последовательности
    }
    for(int i=0;i<x.size();i++)n+=x[i]; //находим сумму
    for(int i=0;i<x.size();i++){
        if(i==0)k=x[0];
        else k*=x[i];
    } //и произведение исходной последовательности
    for(int i=0;i<x.size();i++){   //задаем цикл, в котором заменяем все отрицательные элементы их квадратами
        if(x[i]<0)x[i]=x[i]*x[i];
        if(x[i]<m){  //проверяем возрастаемая последовательность или нет
            m=0;
            break;
        }
        m=x[i];
    }
    if(m!=0){    //если возрастающая - то выводим сумму
        cout<<n;
    }
    else {
        cout<<k; //если нет - то произведение
    }
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> x; //задаем элемент типа vector

double a,m=0,k=0,n=0;

while(cin>>a){ //вводим последовательность

x.push_back(a); //для дальнейшего преобразования последовательности

}

for(int i=0;i<x.size();i++)n+=x[i]; //находим сумму

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

if(i==0)k=x[0];

else k*=x[i];

} //и произведение исходной последовательности

for(int i=0;i<x.size();i++){ //задаем цикл, в котором заменяем все отрицательные элементы их квадратами

if(x[i]<0)x[i]=x[i]*x[i];

if(x[i]<m){ //проверяем возрастаемая последовательность или нет

m=0;

break;

}

m=x[i];

}

if(m!=0){ //если возрастающая - то выводим сумму

cout<<n;

}

else {

cout<<k; //если нет - то произведение

}

Решение

Предлагаю следующее решение. Записываем каждый член последовательности в элемент типа vector. Сразу находим их сумму и произведение. Затем заменяем каждый отрицательный элемент его квадратом и проверяем возрастающая ли последовательность. Если да — то выводим сумму, если нет — то произведение.

Код на ideone.

Related Images:

A288

19/04/2016 by Павел Загинайло

Задача A288

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

Даны целые числа [latex]a_{1}[/latex], …, [latex]a_{n}[/latex], каждое из которых отлично от нуля. Если в последовательности отрицательные и положительные члены чередуются (+, –, +, –, или –, +, –, +, … ), то ответом должна служить сама исходная последовательность. Иначе получить все отрицательные члены последовательности, сохранив порядок их следования.

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

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


int main() {
	vector <int> a, b;
	bool alternate = true; //переменная, которая изменяет свое значение, в зависимости от того, чередуются знаки (true) или нет (false)
	int a1; //первый элемент
	
	cin >> a1;
	int tester = a1; //в переменной хранится значение, с которым будут сравниваться последующие
	if (a1 > 0){
		b.push_back(a1);
	}
	else if (a1 < 0){
		a.push_back(a1);
		b.push_back(a1);
	}
	
	int n;
	while (cin >> n){
		if (n > 0){
			b.push_back(n);
		}
		if (n < 0){
			a.push_back(n);
			b.push_back(n);
		}
		if (tester*n > 0) alternate = false;  //если встретили два значения подряд одного знака
		tester = n;
	}
	if (alternate == true){
		for (int i = 0; i < b.size(); i++){
			cout << b[i] << " ";
		}
	}
	if (alternate == false){
		for (int i = 0; i < a.size(); i++){
			cout << a[i] << " ";
		}
	}
	return 0;
}

#include <vector>

#include <iostream>

using namespace std;

int main() {

vector <int> a, b;

bool alternate = true; //переменная, которая изменяет свое значение, в зависимости от того, чередуются знаки (true) или нет (false)

int a1; //первый элемент

cin >> a1;

int tester = a1; //в переменной хранится значение, с которым будут сравниваться последующие

if (a1 > 0){

b.push_back(a1);

}

else if (a1 < 0){

a.push_back(a1);

b.push_back(a1);

}

int n;

while (cin >> n){

if (n > 0){

b.push_back(n);

}

if (n < 0){

a.push_back(n);

b.push_back(n);

}

if (tester*n > 0) alternate = false; //если встретили два значения подряд одного знака

tester = n;

}

if (alternate == true){

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

cout << b[i] << " ";

}

if (alternate == false){

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

cout << a[i] << " ";

}

return 0;

}

Тесты

Входные данные	Выходные данные
5 5 3 1 2 7 8 100000
-9 -5 -1 -3 -7 -4198 -852	-9 -5 -1 -3 -7 -4198 -852
5 -3 1 81 3 -7 1 -5 6	-3 -7 -5
-1 2 -8 995 -3 777 -42	-1 2 -8 995 -3 777 -42

Решение

Для решение данной задачи я воспользовался следующим алгоритмом. Заводим два целочисленных вектора, булеву переменную, которую мы будем проверять при печати и целочисленную переменную, которая будет являться первым элементом последовательности, а также начальным значением переменной [latex]tester[/latex], с которой будет сравниваться следующий элемент, а после этого его значение мы снова положим в [latex]tester[/latex]. В ходе цикла мы положительные числа кладем в один вектор, а отрицательные в оба. И в зависимости от того чередовались ли знаки или нет (значение переменной [latex]alternate[/latex]), мы печатаем нужный вектор.

Related Images:

А282б

16/03/2016 by Антон Локтев

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

Даны действительные числа [latex]a_{1}[/latex], [latex]a_{2}[/latex], [latex]\ldots[/latex], [latex]a_{2n}[/latex]. Получить [latex]a_{1}[/latex], [latex]a_{2n}[/latex], [latex]a_{2}[/latex], [latex]a_{2n-1}[/latex], [latex]a_{3}[/latex], [latex]\ldots[/latex], [latex]a_{n}[/latex], [latex]a_{n+1}[/latex].

Данную задачу можно найти здесь.

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

Последовательность действительных чисел [latex]a_{1}[/latex], [latex]a_{2}[/latex], [latex]\ldots[/latex], [latex]a_{2n}[/latex].

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

Последовательность действительных чисел [latex]a_{1}[/latex], [latex]a_{2n}[/latex], [latex]a_{2}[/latex], [latex]a_{2n-1}[/latex], [latex]a_{3}[/latex], [latex]\ldots[/latex], [latex]a_{n}[/latex], [latex]a_{n+1}[/latex] .

Тесты

№	Входные данные	Выходные данные
1	1 2 3 4 5 6	1 6 2 5 3 4
2	0 0 0 0 0 1	0 1 0 0 0 0
3	3 12 42 -6 15 0 0 0 501 20 20 20	3 20 12 20 42 20 -6 501 15 0 0 0
4	42 0 17 -2.6 -54 41888 0.25 13 1.3333 -284.73	42 -284.73 0 1.3333 17 13 -2.6 0.25 -54 41888
5	0 1 -1 0 1 -1 97 113 -7.777 0 48 -69	0 -69 1 48 -1 0 0 -7.777 1 113 -1 97

Код

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector <double> sequence, result_sequence;
    double term_of_sequence;
    while (cin >> term_of_sequence){
        sequence.push_back(term_of_sequence);
    }
    for (int i = 0; i < sequence.size() / 2; i++){
        result_sequence.push_back(sequence[i]);
        result_sequence.push_back(sequence[sequence.size() - 1 - i]);
    }
    for (int i = 0; i < result_sequence.size(); i++){
        cout << result_sequence[i] << " ";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> sequence, result_sequence;

double term_of_sequence;

while (cin >> term_of_sequence){

sequence.push_back(term_of_sequence);

}

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

result_sequence.push_back(sequence[i]);

result_sequence.push_back(sequence[sequence.size() - 1 - i]);

}

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

cout << result_sequence[i] << " ";

}

return 0;

}

Код на ideone можно найти здесь.

Ход решения

Считываем все числа из входного потока и записываем их в вектор исходной последовательности sequence. Результатом работы нашей программы должна быть новая последовательность действительных чисел result_sequence, которая задаётся по следующему правилу: первый член новой последовательности совпадает с первым членом исходной, второй член новой последовательности является последним членом исходной, третий – второй член исходной и так далее до исчерпания чисел. Иными словами, новая последовательность из [latex]2n[/latex] чисел на нечётных номерах имеет члены исходной последовательности (от первого и до [latex]n[/latex]-го включительно), чётным же номерам новой последовательности соответствуют члены исходной с номерами от [latex]n+1[/latex] до [latex]2n[/latex] включительно, записанные в обратном порядке.

Related Images:

e-olymp 1073. Статическая сложность

05/03/2016 by Сплошнов Кирилл

Условие

Задача взята с сайта e-olymp, полное условие можно прочитать здесь.

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

В первой строке находится целое число [latex]k[/latex] — число программ во входном файле. Затем идут [latex]k[/latex] программ, удовлетворяющих приведенной грамматике. Пробелы и переводы строк могут встречаться везде в программе, но не в ключевых словах [latex]BEGIN[/latex], [latex]END[/latex], [latex]LOOP[/latex] и [latex]OP[/latex], нет их и в целых числах.

Вложенность операторов [latex]LOOP[/latex] не превышает [latex]10[/latex], размер входного файла не более [latex]2[/latex] Кбайт, коэффициенты многочлена в ответе не превышают [latex]50000[/latex].

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

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

Для каждой программы сначала идет строка с номером программы. В следующей строке записывается время работы программы в терминах [latex]n[/latex] — многочлен степени не более [latex]10[/latex]. Многочлен должен быть записан обычным способом, то есть подобные слагаемые должны быть приведены, слагаемое большей степени должно предшествовать слагаемому меньшей степени, слагаемые с коэффициентом [latex]0[/latex] не записываются, множители [latex]1[/latex] не записываются. Общий вид второй строки [latex]Runtime = a*n^{10}+b*n^9+\ldots+i*n^2+j*n+k[/latex]. Если время выполнения нулевое, нужно вывести [latex]Runtime = 0[/latex]. За строкой с многочленом должна следовать пустая строка, кроме последнего тестового случая.

Решение

Создадим массив коэффициентов [latex]coefficients[/latex] на 11 элементов (нулевой элемент — свободный член, 10-й — десятая (максимальная) степень). В цикле для каждой программы будем:

Обнулять массив [latex]coefficients[/latex].
Заполнять его новыми данными с помощью функции void getCoefficients(int* coefficients);
Строить на основании полученных коэффициентов требуемую строку-многочлен, за это отвечает функция string toString(int* coefficients);
Выводить требуемую информацию.

Рассмотрим процесс заполнения массива. Создадим вектор для строк [latex]params[/latex], где будем хранить кол-ва повторений для всех открытых циклах, от внешнего к внутреннему, и переменную-счетчик [latex]keywords[/latex]. Функция будет завершать свою работу при значении [latex]keywords[/latex] равном [latex]0[/latex]. Изначально присвоим [latex]keywords = 1[/latex] (оператор [latex]BEGIN[/latex]). Далее, в цикле будем, в зависимости от прочитанного оператора:

[latex]END[/latex]: уменьшаем значение [latex]keywords[/latex] на [latex]1[/latex], удаляем последний элемент из [latex]params[/latex] (чтобы не было проблем с последним оператором [latex]END[/latex] (пустой вектор), положим в него перед циклом строку «[latex]1[/latex]»). Если [latex]keywords[/latex] равно нулю — завершаем работу.
[latex]LOOP[/latex]: увеличиваем значение [latex]keywords[/latex] на [latex]1[/latex], считываем следующую строку и добавляем ее в конец [latex]params[/latex].
[latex]OP[/latex]: Считываем следующую строку, преобразовываем ее к числу (кол-ву операций) стандартной функцией stoi(). Далее, проходя по строкам из [latex]params[/latex], если строка равна [latex]n[/latex], увеличиваем степень (номер ячейки массива, куда прибавим результат) на [latex]1[/latex], иначе — преобразовываем к числу и домножаем на кол-во операций. Прибавляем полученный результат к числу в соответствующей ячейке массива.

Функция toString() реализована достаточно просто (см. код). Пробегаем по элементам массива с конца, и если элемент [latex]n[/latex] не равен нулю, прибавляем к строке-многочлену соответствующий набор символов (отдельно учитывая случаи при [latex]n = 1[/latex], [latex]n=-1[/latex], первой и нулевой степени и т.д.). Если в итоге строка пустая, возвращаем «[latex]0[/latex]».

Тесты

№

Ввод

Вывод

2
BEGIN
LOOP n
OP 4
LOOP 3
LOOP n
OP 1
END
OP 2
END
OP 1
END
OP 17
END

BEGIN
OP 1997 LOOP n LOOP n OP 1 END END
END

Program #1
Runtime = 3*n^2+11*n+17

Program #2
Runtime = n^2+1997

3
BEGIN
END

BEGIN
LOOP n LOOP n LOOP n OP 1
LOOP n LOOP n LOOP n OP 1
LOOP n LOOP n LOOP n OP 1
END END END OP 3
END END END OP 3
END END END OP 3
END

BEGIN OP 42
LOOP n LOOP 5 LOOP n
OP 7 END OP 2 END OP 1 END
OP 1 END

Program #1
Runtime = 0

Program #2
Runtime = n^9+4*n^6+4*n^3+3

Program #3
Runtime = 35*n^2+11*n+43

Код

#include <iostream>
#include <string>
#include <vector>
#define MAX_POWER 10
using namespace std;

void getCoefficients(int* coefficients)
{
	int keywords = 1;
	vector<string> params;
	string begin;
	cin >> begin;
	params.push_back(((string) "1")); //чтобы вектор не был пустой на последнем END (который соответствует BEGIN)
	while (true)
	{
		string keyword;
		cin >> keyword;
		if (keyword == (string)"END")
        {
            keywords--;
            params.pop_back();
            if (keywords == 0) 
            {
            	break;
            }
        }
        else if (keyword == (string)"LOOP")
        {
            keywords++;
            string param;
            cin >> param;
            params.push_back(param);
        }
        else if (keyword == (string)"OP")
        {
        	string num;
        	cin >> num;
            int coefficient = stoi(num);
            int multiplier = 1, pow = 0;
            for (string param : params)
            {
                if (param == (string)"n") 
                {
                	pow++;
                }
                else 
                {
                	multiplier *= stoi(param);
                }
            }
            coefficients[pow] += coefficient * multiplier;
        }
	}
}

string toString(int* coefficients)
{
	string result;
    for (int i = MAX_POWER; i > 0; i--)
    {
        if (coefficients[i] != 0)
            {
                if (coefficients[i] == 1) 
                {
                	result += "n";
                }
                else if (coefficients[i] == -1) 
                {
                	result += "-n";
                }
                else
                {
                	result += to_string(coefficients[i]); //стандартная функция, преобразовывает число в строку
                	result += "*n";
                }
                if (i != 1) //если степень не первая, добавляем "^[степень]"
                {
                	result += "^";
                	result += to_string(i);
                }
            }
            if (coefficients[i-1] > 0 && result.length() != 0) //проверка, чтобы + не стоял в начале строки и между членами не было "+-"
            {
            	result += "+";
            }
        }
        if (result.length() == 0 || coefficients[0] != 0) //прибавляем последний коэффициент, если он не равен нулю или строка пустая
        {
        	result += to_string(coefficients[0]);
        }
        return result;
}

int main() 
{
	int n;
	cin >> n;
	int coefficients[MAX_POWER + 1];
	for (int i = 1; i <= n; i++)
	{
		cout << "Program #" << i << endl;
		fill(coefficients, coefficients + MAX_POWER + 1, 0); //обнуляем массив коэффициентов
		getCoefficients(coefficients);
		cout << "Runtime = " << toString(coefficients) << endl;
		if (i != n)
		{
			cout << endl; 
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

#include <iostream>

#include <string>

#include <vector>

#define MAX_POWER 10

using namespace std;

void getCoefficients(int* coefficients)

{

int keywords = 1;

vector<string> params;

string begin;

cin >> begin;

params.push_back(((string) "1")); //чтобы вектор не был пустой на последнем END (который соответствует BEGIN)

while (true)

{

string keyword;

cin >> keyword;

if (keyword == (string)"END")

{

keywords--;

params.pop_back();

if (keywords == 0)

{

break;

}

else if (keyword == (string)"LOOP")

{

keywords++;

string param;

cin >> param;

params.push_back(param);

}

else if (keyword == (string)"OP")

{

string num;

cin >> num;

int coefficient = stoi(num);

int multiplier = 1, pow = 0;

for (string param : params)

{

if (param == (string)"n")

{

pow++;

}

else

{

multiplier *= stoi(param);

}

coefficients[pow] += coefficient * multiplier;

}

string toString(int* coefficients)

{

string result;

for (int i = MAX_POWER; i > 0; i--)

{

if (coefficients[i] != 0)

{

if (coefficients[i] == 1)

{

result += "n";

}

else if (coefficients[i] == -1)

{

result += "-n";

}

else

{

result += to_string(coefficients[i]); //стандартная функция, преобразовывает число в строку

result += "*n";

}

if (i != 1) //если степень не первая, добавляем "^[степень]"

{

result += "^";

result += to_string(i);

}

if (coefficients[i-1] > 0 && result.length() != 0) //проверка, чтобы + не стоял в начале строки и между членами не было "+-"

{

result += "+";

}

if (result.length() == 0 || coefficients[0] != 0) //прибавляем последний коэффициент, если он не равен нулю или строка пустая

{

result += to_string(coefficients[0]);

}

return result;

}

int main()

{

int n;

cin >> n;

int coefficients[MAX_POWER + 1];

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

{

cout << "Program #" << i << endl;

fill(coefficients, coefficients + MAX_POWER + 1, 0); //обнуляем массив коэффициентов

getCoefficients(coefficients);

cout << "Runtime = " << toString(coefficients) << endl;

if (i != n)

{

cout << endl;

}

return 0;

}

Ссылки

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

Рабочий код на ideaone.

Related Images:

Ю12.20

20/12/2014 by Карагяур Мілан Сергійович

Задача: В имеющемся словаре найти пары слов ( анаграммы), при прочтении каждого из которых в обратном направлении образуется другое слово пары.

Ввод	Вывод
qwerty ytrewq av ab va tg	qwerty — ytrewq av — va
12345 45 67 54 123567 543 54321	12345 — 54321 45 — 54

#include <iostream>
#include <vector>
using namespace std;
int main() {
	vector<string> x;
	vector<string> r;
	string t;
	int k = 0;
	while(getline(cin, t))
	{	
		x.push_back(t);
	}
	for(int i=0; i <(int) x.size(); i++)
	{
		string g, f="";
		g=x[i];
		for (int j=g.length()-1 ; j>=0 ; j--)
	    	        f+= x[i][j];
		for(int j=i+1; j < (int)x.size(); j++)
		{
			if (f==x[j])
			{
				r.push_back(x[i]+" - "+f);
			}
		}
	}
	for(int i=0; i <(int) r.size(); i++)
	{
		cout<<r[i]<<endl;
	}
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector<string> x;

vector<string> r;

string t;

int k = 0;

while(getline(cin, t))

{

x.push_back(t);

}

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

{

string g, f="";

g=x[i];

for (int j=g.length()-1 ; j>=0 ; j--)

f+= x[i][j];

for(int j=i+1; j < (int)x.size(); j++)

{

if (f==x[j])

{

r.push_back(x[i]+" - "+f);

}

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

{

cout<<r[i]<<endl;

}

return 0;

}

Записываем каждое слово словаря в вектор. А цикле переворачиваем каждое слово вектора и потом в цикле сравниваем его с каждым словом в словаре, если найдено обратное слово, то закидываем пару слов в новый вектор. Выводим вектор из пар слов на экран.

Ideone.

Related Images:

М16. Freshly Pressed Juice

29/11/2014 by Іванов Вячеслав Володимирович

Формулировка задачи

Известно, что каждый посетитель фруктового бара просит сделать наиболее дешевый коктейль из свежевыжатого сока. Объем стакана для сока V. Рассчитайте стоимость и сформируйте рецепт коктейля, который достанется n-тому посетителю. V и n читаются из входного потока. Во входном потоке имеется неизвестное количество строк – справочник в котором для каждого вида фруктов указано его название, текущая стоимость за килограмм, процент выхода сока и количество фруктов на складе.
а) Прочитать справочник в список (vector) соответствующих структур.
б) Сформировать рецепт и рассчитать стоимость наиболее дешёвого коктейля.

Тесты

[latex]V[/latex]	[latex]n[/latex]	[latex]Menu[/latex]	[latex]Recipe[/latex]	Комментарий
150	2	Apple 10 60 200 Cherry 20 70 50	Sorry, we are closed for today	Объем фруктов на складе меньше 300.
80	8	Dragonfruit 123 50 10 Aplle 10 60 200 Cherry 40 80 100 Coconut 20 5 30 Pineapple 80 90 50 Raspberry 70 95 30 Blackberry 130 95 30 Strawberry 60 95 40 Grape 20 95 120 Orange 10 80 200 Melon 10 98 300 Banana 20 30 120	Apple 80 800	В самом деле, более выгодным будет использование только арбузов и апельсинов, израсходованных ранее.
80	14	(см. тест № 2)	Banana 40.000000 Raspberry 30.000000 Pineapple 10.000000 3700	Корректно
110	1	(см. тест №2)	Melon 110 1100	Корректно

Анализ задачи

Параметры «количество», «удельная стоимость», «процент выхода сока» описывают сущность типа «фрукт». Следовательно, необходимо создать одноименную структуру, связав конкретное наименование в меню (списке) с его количественными характеристиками.
Условие задачи можно переформулировать как поиск наиболее выгодного фрукта по соотношению (у.е./куб.ед.) — фрукта, из единицы массы которого можно дешевле всего получить кубическую единицу объема, [latex]\frac {price}{volume}[/latex]. Данные, необходимые для сортировки фруктов в порядке возрастания стоимости единицы объема сока, присуствуют в исходных данных. Подробнее: [latex]\frac {price}{volume} = \frac {amount*specificCost}{amount*percentage*\rho} = \frac {specificCost}{percentage*\rho}[/latex]. В условии не указано обратное, потому плотность сока принята равной [latex]\rho = 1[/latex](г/мл). Окончательно, [latex]worth = \frac {specificCost}{percentage}[/latex].

Алгоритм решения

- Объявить структуру [latex]fruit[/latex] с переменными:
  - name
  - specific_cost
  - percentage
  - amount
- Необходимо
  1. считывать информацию о фрукте;
  2. сортировать фрукты по некоторому параметру
  Следовательно, уместно определить методы [latex]get()[/latex] и [latex]worth()[/latex] соответственно.
Дальнейшее решение распадается на несколько подзадач:
1. Сортировка элементов вектора в порядке убывания стоимости единицы объема.
2. Поиск фруктов, доступных в момент, когда [latex]n[/latex]-ый посетитель делает заказ.
3. Составление коктейля наименьшей стоимости при заданном объёме порции.
Был намечен следующий алгоритм действий:
1. После сортировки определить, какая масса фруктов должна быть израсходована к моменту заказа, и последовательно проходить по вектору, уменьшая количество каждого фрукта, пока не дойдем до требуемого значения.
2. Если оставшихся фруктов достаточно для приготовления коктейля, последовательно перерабатывать фрукты, пока на складе не закончится текущее наименование, а тогда перейти к следующему, и так пока не прийдем к заданному объему.
3. На каждом шаге добавлять в рецепт количество использованных фруктов вместе с их названиями. В конце рецепта указать стоимость коктейля.

Программный код

Программа доступна для тестирования по ссылке: http://ideone.com/qj8ovB.

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

struct fruit{
    string name;            //название фрукта
    double specific_cost;   //удельная стоимость
    double percentage;      //процентный выход сока
    double amount;          //текущее количество на складе
    double worth(){         //параметр в критерии отбора 
        return (specific_cost * 100)/percentage;
    }
    bool get(){             //логический тип позволяет 
        return (cin >> name //производить считывание
        >> specific_cost  //до конца файла
        >> percentage
        >> amount);
    }
};

int main()
{
    double V; int n;        //объем сока и номер посетителя по счёту
    cin >> V >> n;          
    /*Заполнение меню - показателя текущего состояния на складе*/
    vector<fruit> menu;
    fruit tmp; double total_amount = 0;
    while(tmp.get()){
        menu.push_back(tmp);
        total_amount += tmp.amount;
    }
    /*Критерий отбора: отсортировать в порядке уменьшения цены за литр*/
    sort(menu.begin(), menu.end(), [](fruit a, fruit b){return a.worth() < b.worth();});
    /*Составление рецепта коктейля*/
    /*1. Поиск фруктов, доступных на n-м шаге*/
    double used = (n - 1) * V; int starting_position = 0;
    if(total_amount >= n*V &&
        any_of(menu.begin(), menu.end(), [&](fruit &a) mutable {
            double new_amount = (used -= a.amount);
            if(new_wolume >= 0){starting_position++; a.amount = 0;}
            else a.amount = (-1)*new_amount;
            return new_amount < 0;
        })){
        //Заполнение коктейля соком до заданного объёма
        double volume_left = V, price = 0; string recipe;
        /*Добавлять ингредиенты из отсортированного меню, пока возможно*/
        any_of(menu.begin() + starting_position, menu.end(), [&](fruit &a) mutable {
        /*Если ингридиент израсходован*/
            double new_amount = (volume_left -= a.amount);
            if(new_amount >= 0){
                price += a.specific_cost * a.amount;
                recipe += a.name + ' ' + to_string(a.amount) + '\n';
                a.amount = 0;
            }
        /*Если коктейль готов*/
            else{
                a.amount = new_amount + a.amount;
                price += a.specific_cost * a.amount;
                recipe += a.name + ' ' + to_string(a.amount) + '\n';
            }
            return (new_amount <= 0);
        });
        cout << recipe << price << endl;
    }
    else cout << "Sorry, we are closed for today." << endl;
    return 0;
}

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

struct fruit{

string name; //название фрукта

double specific_cost; //удельная стоимость

double percentage; //процентный выход сока

double amount; //текущее количество на складе

double worth(){ //параметр в критерии отбора

return (specific_cost * 100)/percentage;

}

bool get(){ //логический тип позволяет

return (cin >> name //производить считывание

>> specific_cost //до конца файла

>> percentage

>> amount);

}

};

int main()

{

double V; int n; //объем сока и номер посетителя по счёту

cin >> V >> n;

/*Заполнение меню - показателя текущего состояния на складе*/

vector<fruit> menu;

fruit tmp; double total_amount = 0;

while(tmp.get()){

menu.push_back(tmp);

total_amount += tmp.amount;

}

/*Критерий отбора: отсортировать в порядке уменьшения цены за литр*/

sort(menu.begin(), menu.end(), [](fruit a, fruit b){return a.worth() < b.worth();});

/*Составление рецепта коктейля*/

/*1. Поиск фруктов, доступных на n-м шаге*/

double used = (n - 1) * V; int starting_position = 0;

if(total_amount >= n*V &&

any_of(menu.begin(), menu.end(), [&](fruit &a) mutable {

double new_amount = (used -= a.amount);

if(new_wolume >= 0){starting_position++; a.amount = 0;}

else a.amount = (-1)*new_amount;

return new_amount < 0;

})){

//Заполнение коктейля соком до заданного объёма

double volume_left = V, price = 0; string recipe;

/*Добавлять ингредиенты из отсортированного меню, пока возможно*/

any_of(menu.begin() + starting_position, menu.end(), [&](fruit &a) mutable {

/*Если ингридиент израсходован*/

double new_amount = (volume_left -= a.amount);

if(new_amount >= 0){

price += a.specific_cost * a.amount;

recipe += a.name + ' ' + to_string(a.amount) + '\n';

a.amount = 0;

}

/*Если коктейль готов*/

else{

a.amount = new_amount + a.amount;

price += a.specific_cost * a.amount;

recipe += a.name + ' ' + to_string(a.amount) + '\n';

}

return (new_amount <= 0);

});

cout << recipe << price << endl;

}

else cout << "Sorry, we are closed for today." << endl;

return 0;

}

Подробности реализации

Из интереса и эксперимента ради решение было запрограммировано в двух вариантах: в процедурном, в духе классического языка C, и средствами стандарта C++11. Вторая версия получилась более лаконичной, но, при необходимости, может быть предъявлена и первая.

После считывания списка переменная [latex]total amount[/latex] хранит в себе общее количество всех фруктов на складе.
Метод [latex]get()[/latex] возвращает значение булевого типа, так как таким образом можно производить чтение до конца файла средствами [latex]cin[/latex], с автоматической проверкой.
Для работы только с фруктами, доступными в момент совершения заказы [latex]n[/latex]-м посетителем, была создана переменная [latex]used[/latex], хранящая объем всех коктейлей, сделанных для предыдущих посетителей. В цикле [latex]any of()[/latex] на каждом шаге происходит уменьшение переменной [latex]used[/latex] на доступную массу фруктов данного типа. Для наглядности восприятия введена переменная [latex]new amount[/latex]. Если оставшееся на складе количество фруктов позволяет сделать ещё один коктейль, происходит вход во внутренний цикл. В противном случае, пользователя уведомляют о том, что выполнение заказа невозможно.
Во внутреннем цикле, который выполняется, пока не наберется достаточный объем сока, на каждом шаге берут максимально возможное количество фрукта данного типа. Рецепт сохраняется в строку [latex]recipe[/latex].
В лямбда-выражения параметры из тела программы передаются по ссылке. Возможность их изменения гарантируется ключевым словом [latex]mutable[/latex].