e-olymp 7254. Отрезки

13/03/2021 by Євген Константинов

Задача

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

Отрезки пронумерованы последовательными натуральными числами, начиная с единицы. Отрезок номер [latex]i[/latex] характеризуется двумя числами — длиной [latex]L_i[/latex] и ценой [latex]C_i[/latex]. Петя очень умный, поэтому знает, что желаемый треугольник он может сложить из трех отрезков. Более того, наш герой знает, что треугольник возможно сложить только из таких трех отрезков, среди которых длина любого отрезка строго меньше суммарной длины двух других. Итак, мальчик решил купить ровно три таких отрезка. Разумеется, он хочет сэкономить как можно больше денег на мороженое, поэтому стремится потратить как можно меньше денег на покупку треугольника.

Задание

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

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

В первой строке входного файла записано единственное число [latex]N[/latex] — количество отрезков. В следующих [latex]N[/latex] строках записана информация о самих отрезках. Каждая такая строка содержит соответствующие [latex]L_i[/latex] [latex](1 \leqslant L_i \leqslant 10^9)[/latex] и [latex]C_i[/latex]. Цены образуют перестановку чисел от [latex]1[/latex] до [latex]N[/latex], то есть являются попарно различными натуральными числами, не превосходящими [latex]N[/latex].

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

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

Тесты

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

Код

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

//Структура для представления одного отрезка
struct Line {
    int price;
    int length;
};

//Функция сортировщик по цене в порядке возрастания
bool comparator_price (Line i, Line j) { 
    return i.price < j.price;
}

int main() {
    int n, price, length, cheapest = INT_MAX;
    cin >> n;
    Line lines_by_price[n];
    
    for (int i = 0; i < n; i++) {
        Line l;
        cin >> length >> price;
        l.price = price;
        l.length = length;
        lines_by_price[i] = l;
    }
    
    //Сортируем все отрезки по цене, чтобы была возможность "отсечь"
    //слишком дорогие отрезки, когда цена одного(или двух) будет 
    //больше текущей минимальной
    sort(&lines_by_price[0], &lines_by_price[n], comparator_price);
    
    for (int i = 0; i < n; i++) {
        Line first_side = lines_by_price[i];
        if (first_side.price > cheapest) break;
        vector<Line> sides = {};
        //Перебираем все возможные тройки отрезков, отсекая
        //слишком дорогие, основываясь на сортировке по цене
        //и текущей минимальной цене
        for (int j = 0; j < n; j++) {
            if (lines_by_price[j].price != first_side.price && lines_by_price[j].length <= first_side.length) {
                sides.push_back(lines_by_price[j]);
                Line second_side = lines_by_price[j];
                if (first_side.price + second_side.price > cheapest) break;
                for (auto third_side: sides) {
                    if ((third_side.length != second_side.length && third_side.price != second_side.price) 
                    && first_side.length < second_side.length + third_side.length 
                    && second_side.length < first_side.length + third_side.length 
                    && third_side.length < second_side.length + first_side.length) {
                        if (first_side.price + second_side.price + third_side.price < cheapest) {
                            cheapest = first_side.price + second_side.price + third_side.price;
                        }
                        break;
                    }
                }
            }
        }
    }
    //Если ни одна тройка отрезков не подошла, значит составить
    //треугольник невозможно - выводим "-1"
    if (cheapest == INT_MAX) cheapest = -1;
    cout << cheapest;
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

#include <climits>

using namespace std;

//Структура для представления одного отрезка

struct Line {

int price;

int length;

};

//Функция сортировщик по цене в порядке возрастания

bool comparator_price (Line i, Line j) {

return i.price < j.price;

}

int main() {

int n, price, length, cheapest = INT_MAX;

cin >> n;

Line lines_by_price[n];

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

Line l;

cin >> length >> price;

l.price = price;

l.length = length;

lines_by_price[i] = l;

}

//Сортируем все отрезки по цене, чтобы была возможность "отсечь"

//слишком дорогие отрезки, когда цена одного(или двух) будет

//больше текущей минимальной

sort(&lines_by_price[0], &lines_by_price[n], comparator_price);

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

Line first_side = lines_by_price[i];

if (first_side.price > cheapest) break;

vector<Line> sides = {};

//Перебираем все возможные тройки отрезков, отсекая

//слишком дорогие, основываясь на сортировке по цене

//и текущей минимальной цене

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

if (lines_by_price[j].price != first_side.price && lines_by_price[j].length <= first_side.length) {

sides.push_back(lines_by_price[j]);

Line second_side = lines_by_price[j];

if (first_side.price + second_side.price > cheapest) break;

for (auto third_side: sides) {

if ((third_side.length != second_side.length && third_side.price != second_side.price)

&& first_side.length < second_side.length + third_side.length

&& second_side.length < first_side.length + third_side.length

&& third_side.length < second_side.length + first_side.length) {

if (first_side.price + second_side.price + third_side.price < cheapest) {

cheapest = first_side.price + second_side.price + third_side.price;

}

break;

}

//Если ни одна тройка отрезков не подошла, значит составить

//треугольник невозможно - выводим "-1"

if (cheapest == INT_MAX) cheapest = -1;

cout << cheapest;

return 0;

}

Решение

Для начала запишем все отрезки в массив в виде структур. Отсортируем их по цене в порядке возрастания, чтобы позже иметь возможность «отсекать» слишком дорогие отрезки. Далее мы начинаем перебирать все возможные тройки отрезков. На первом уровне цикла ставим условный оператор. Если на [latex]n[/latex]-ой итерации цикла будет отрезок с ценой больше текущей наименьшей цены треугольника, то мы можем выходить из массива и выводить текущую минимальную стоимость, т.к. все последующие отрезки будут дороже (пользуемся сортировкой и тем, что цены отрезков образуют перестановку от [latex]1[/latex] до [latex]N[/latex]). Далее на втором и третьем уровнях цикла мы также перебираем все отрезки от дешевых к дорогим и при обнаружении тройки отрезков, цена которых меньше текущей минимальной, записываем их в переменную [latex]cheapest[/latex]. При этом на втором уровне цикла проверяем, не больше ли сумма цен двух отрезков текущей минимальной, чтобы не проверять лишние тройки.

Ссылки

Related Images:

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 9066. Кружок стрельбы

03/03/2020 by Владислав Гринькив

Задача

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

На занятие кружка пришли $n$ учеников. Фэй пронумеровала их целыми числами от $1$ до $n$. В начале занятия ученики встали вдоль координатной прямой, заблаговременно нарисованной на полу, причем i-й ученик стоял в точке с координатой $x_i$. Получилось так, что координаты учеников строго возрастали, то есть $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

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

Если ученик произвел выстрел, и снаряд, выпущенный им, достиг следующего по порядку вдоль прямой ученика, снаряд прекращает свой полет, а ученик, которого достиг снаряд, внезапно решает, что ему тоже надо произвести выстрел, и совершает его. Ученик совершит выстрел, даже если снаряд достиг его, имея силу $0$.

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

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

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

Первая строка содержит количество учеников $n$ $(1 \leqslant n \leqslant 1000)$ на кружке Фэй.

Каждая из следуюших $n$ строк содержит три целых числа $x_i$, $r_i$ и $c_i$ ($1 \leqslant x_i \leqslant 10^9$, $1 \leqslant r_i$, $c_i \leqslant 100$) — координату очередного ученика, а также дальность и силу его лука соответственно. Гарантируется, что $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

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

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

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 1 3 3 5 1 2 8 2 3 10 1 2 11 3 2	2
2	6 1 3 5 4 2 2 7 4 3 10 1 2 11 3 2 13 4 3	1

Код

#include <iostream>
using namespace std;
struct archerProfile {
  unsigned long x;
  unsigned long r;
  unsigned int c;
}archer[1000];
int main(){ 
  int n;
  int commands = 1;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> archer[i].x >> archer[i].r >> archer[i].c;
  }
  for (int i = 0; i < n - 1; i++) {
    unsigned long long distanceBetweenArchers = archer[i + 1].x - archer[i].x;
    if (distanceBetweenArchers > archer[i].c * archer[i].r) {
      commands += 1;
    }
  }
  cout << commands;
  return 0;
}

#include <iostream>

using namespace std;

struct archerProfile {

unsigned long x;

unsigned long r;

unsigned int c;

}archer[1000];

int main(){

int n;

int commands = 1;

cin >> n;

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

cin >> archer[i].x >> archer[i].r >> archer[i].c;

}

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

unsigned long long distanceBetweenArchers = archer[i + 1].x - archer[i].x;

if (distanceBetweenArchers > archer[i].c * archer[i].r) {

commands += 1;

}

cout << commands;

return 0;

}

Решение

Для решения задачи, мы должны найти расстояние между лучниками, то есть $x_{i+1}-x_i$, после чего найти максимальное расстояние, которое пролетит стрела у $x_{i}$ лучника умножив силу его лука $c_i$ и расстояние $r_i$, после чего сделать проверку, если расстояние между лучниками больше чем максимальное расстояние которое пролетит стрела, то мы дадим команду совершить ещё один выстрел.

Ссылки

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

Related Images:

e-olymp 6261. Устройство для анализа бюллетеня

30/11/2019 by Евгений Фищук

Задача

Избирательная комиссия Флатландии готовится к президентским выборам. Чтобы свести к минимуму человеческий фактор при подсчете голосов, они решили разработать автоматическое устройство для анализа бюллетеней (УАБ).

На пост президента баллотируются $n$ кандидатов. Бюллетень содержит одно квадратное поле для каждого кандидата. Избиратель должен отметить ровно одно из полей. Если поле не помечено или имеется два или более отмеченных поля, бюллетень недействителен. Каждый избиратель ставит свой бюллетень на специальный сканер в УАБ. Сканер анализирует отметки в бюллетене и создает специальную строку голосования из $n$ символов: ‘X’ для отмеченного поля и ‘.’ для немаркированного. Теперь строки голосования должны быть проанализированы, чтобы получить отчет. Ваша задача — разработать генератор отчетов для УАБ.

С учетом строк голосования для всех бюллетеней Ваша программа должна распечатать отчет о голосовании. Кандидаты в протоколе должны быть расположены в порядке убывания количества голосов. Если два кандидата имеют одинаковое количество голосов, они должны иметь тот же порядок, что и в бюллетене для голосования. Для каждого кандидата рассчитайте его / ее результат в процентах (если кандидат получил p голосов, результат в процентах составляет $ \frac{100p}{m}$ ). В последней строке отчета должен быть указан процент недействительных бюллетеней.

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

Первая строка содержит два целых числа $n$ и $m (2 \leqslant n \leqslant 10, 1 \leqslant m \leqslant 1000$) — количество кандидатов и количество бюллетеней. Следующие $n$ строк содержат фамилии кандидатов. Каждое имя представляет собой строку не более 100 английских букв. Нет ни одного кандидата с именем «Invalid».

Затем следуют $m$ строк, каждая из которых содержит одну строку голосования.

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

Выведите $n+1$ строк. Сначала выведите результаты для кандидатов в процентах. Для каждого кандидата выведите его / ее фамилию, затем пробел, а затем его / ее результат в процентах и знак процента ‘%‘. В последней строке должен быть указан процент недействительных бюллетеней: слово «Invalid», за которым следуют пробел, процент недействительных бюллетеней и знак процента.

Округлите все числа до двух цифр после десятичной точки. Если число находится точно посередине двух представимых чисел, выведите большее (например, выведите «12.35» для 12.345).

Тесты

№	Входные данные	Выходные данные
1	4 7 Loudy Apples Dogman Miller .X.. X… …. ..X. ..XX ..X. ..X.	Dogman 42.86% Loudy 14.29% Apples 14.29% Miller 0.00% Invalid 28.57%
2	4 10 Loudy Apples Dogman Miller X……………….. X………………….. X……………… X…………………. X………….. x……………………….. X………………. X…………… X..x xxxx	Loudy 70.00% Apples 0.00% Dogman 0.00% Miller 0.00% Invalid 30.00%

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

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

struct candidates {
    string name;
    double numb;
};

bool c(candidates x, candidates y)
{
    return x.numb > y.numb;
}

int main() {
    int candidateNum, ballotNum;
    cin >> candidateNum >> ballotNum;
    candidates* candidate = new candidates[candidateNum+1];
    string s = "";
    for (int i = 0; i < candidateNum; i++)
    {
        cin >> s;
        candidate[i].name = s;
        candidate[i].numb = 0;
    }
    candidate[candidateNum].name = "Invalid";
    candidate[candidateNum].numb = 0;
    int count = 0, num;
    for (int i = 0; i < ballotNum; i++)
    {
        cin >> s;
        count = 0;
        for (int j = 0; j < candidateNum; j++)
        {
            if (s[j] == 'X')
            {
                count++;
                num = j;
            }
            if (isalpha(s[j]) && s[j] != 'X')
                count=2;
        }
        if (count == 1)
        {
            candidate[num].numb++;
        }
        else
            candidate[candidateNum].numb++;

    }
    sort(candidate, candidate + candidateNum,c);
    for (int i = 0; i <= candidateNum; i++)
    {
        cout << fixed << setprecision(2) << candidate[i].name << " " << candidate[i].numb*100/ballotNum << "%\n";
    }
    return 0;
}

#include <iostream>

#include <string>

#include <iomanip>

#include <algorithm>

using namespace std;

struct candidates {

string name;

double numb;

};

bool c(candidates x, candidates y)

{

return x.numb > y.numb;

}

int main() {

int candidateNum, ballotNum;

cin >> candidateNum >> ballotNum;

candidates* candidate = new candidates[candidateNum+1];

string s = "";

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

{

cin >> s;

candidate[i].name = s;

candidate[i].numb = 0;

}

candidate[candidateNum].name = "Invalid";

candidate[candidateNum].numb = 0;

int count = 0, num;

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

{

cin >> s;

count = 0;

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

{

if (s[j] == 'X')

{

count++;

num = j;

}

if (isalpha(s[j]) && s[j] != 'X')

count=2;

}

if (count == 1)

{

candidate[num].numb++;

}

else

candidate[candidateNum].numb++;

}

sort(candidate, candidate + candidateNum,c);

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

{

cout << fixed << setprecision(2) << candidate[i].name << " " << candidate[i].numb*100/ballotNum << "%\n";

}

return 0;

}

Решение

Чтобы решить задачу создадим структуру с именами и результатами кандидатов. Сначала создадим массив кандидатов и заполним его. По вводу бюллетеней будем проверять не испорчены ли они. Если кроме «X» есть любой другой символ, или буква, или еще символы «X», то бюллетень испорчен, в остальных случаях он не испорчен. Если он не испорчен, добавляем к результату кандидата единицу, если нет — добавляем к счетчику испорченых бюллетеней единицу. Выводим в процентном соотношении с количеством бюллетеней результат каждого кандидата и количество испорченых бюллетеней.

Ссылки

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

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

Related Images:

e-olymp 976. Флойд — существование

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

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

e-olymp 974. Флойд 1
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

Пройденный тесты.

e-olymp 976. Флойд — существование

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

Кратчайший путь может не существовать по двум причинам:

Нет ни одного пути.
Есть путь сколь угодно маленького веса

Пройденный тесты.

Первая задача решается Алгоритмом Флойда-Уоршела. Поскольку отрицательных ребер в графе нет, и просят вывести кратчайший путь к каждой из вершин, то надо было всего лишь определить, что мы возьмем за бесконечность. Я выбрал [latex]10001[/latex], поскольку максимальное количество вершин [latex]100[/latex], а вес ребер не превышает [latex]100[/latex], соответственной максимально возможное расстояние не превосходит [latex]100*100 = 10000[/latex].

Во второй задаче была та же идея, но в данной ситуация у нас были ребра отрицательного веса. И у нас появилась проблема, могли существовать циклы отрицательной длины(с каждым проходом расстояние до вершин уменьшалось). Поскольку мы пользовались [latex]while[/latex] -ом, мы зацикливались. По этому необходимо было прекращать добавлять вершины, которую имеют отрицательную индексацию и порогом выбрано [latex]-102[/latex], поскольку цикл мог содержать отрицательные ребра, но при это быть положительным, по этому [latex]<0[/latex] нам не подошло. Дальше необходимо было вывести матрицу существования, методом [latex]way[/latex] мы выходили из вершины и определяли индексацию, пуская из всех вершин, мы можем построково выводить матрицу, только необходимо восстанавливать к исходному виду сам граф. В выводе мы определяли, существует путь и мал ли он. Существование проверялось тем, что эта вершина была посещена, а путь к вершине проверялся по индексу, если он меньше половины порога остановки[latex](-50)[/latex], то путь к этой вершине бесконечен.

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

struct vertax{ // структура вершина
	int vert, index, father; bool visited;
	vertax(int a){vert = a; index = 10001; father = a;visited = false;}
	vertax(int a, int b){
		vert = a;
		father = b;
		index = 10001;visited = false;
	}
	vertax(int a, int b, int x){
		vert = a;
		father = b;
		index = x;visited = false;
	}
	vector<vertax> follow;// с кем связанна эта вершина
	~vertax(){}
};

struct graph{
	vector<vertax> v; // list of vertax
	int count;
	graph(){};
	graph(int n){
		count = n;
	}
	void get(){//инициализируем граф
		for(int i = 1; i <= count; i++){
			vertax v(i);
			for(int j = 1; j <= count; j++){
				int x;
				cin >> x;
				if(x != 0){
					vertax temp(j, i, x);
					v.follow.push_back(temp);
				}
			}
			graph::v.push_back(v);
		}
	}
	void write(){//вывод вершины, и с кем она связанна
		for(int i = 0; i < count; i++){
			cout << v[i].index << ":";
			for(int j = 0; j < v[i].follow.size(); j++){
				cout << v[i].follow[j].vert << " ";
			}
			cout << endl;
		}
	}
	void way(vertax& x){//алгоритм
		deque<vertax> list;
		x.index = 0;
		x.visited = true;
		list.push_front(x);
		while(!list.empty()){
			vertax& y = list[0];
			for(int i = 0; i < y.follow.size();i++){
				v[y.follow[i].vert -1].visited = true;
				if(v[y.follow[i].vert-1].index > y.index+y.follow[i].index){
					v[y.follow[i].vert-1].index = y.index+y.follow[i].index;
					if(v[y.follow[i].vert-1].index > -102){
						list.push_back(v[y.follow[i].vert-1]);
					}
				}
			}
			list.pop_front();
		}
	}
	void def(){//фунция к приведению значений по умолчанию
		for(int i = 0; i < v.size(); i++){
			v[i].index = 10001;
			v[i].visited = false;
		}
	}
	void task1(){ // Решение задачи e-olymp.com №976: Флойд - существование
		for(int i = 0; i < v.size(); i++){
			way(v[i]);
			for(int j = 0; j < v.size()-1; j++){
				if(!v[j].visited){
					cout << 0 << " ";
				}else if(v[j].index < -50){
					cout << 2 << " ";
				}else{
					cout << 1 << " ";
				}
			}
			if(!v[v.size()-1].visited){
					cout << 0 ;
				}else if(v[v.size()-1].index < -50){
					cout << 2 ;
				}else{
					cout << 1 ;
				}
			def();
			cout << endl;
		}
	}
	void task2(){ // Решение задачи e-olymp.com №974: Флойд-1
		for(int i = 0; i < v.size(); i++){
			way(v[i]);
			for(int j = 0; j < v.size()-1; j++){
				if(!v[j].visited){
					cout << 0 << " ";
				}else{
					cout << v[j].index << " ";
				}
			}
			if(!v[v.size()-1].visited){
					cout << 0 ;
				}else{
					cout << v[v.size()-1].index;
				}
			def();
			cout << endl;
		}
	}
};


int main() {
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	graph dog(n);
	dog.get();
	dog.task1();// Решаем задачу №976: Флойд - существование
	dog.task2();// Решаем задачу №974: Флойд-1
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include <iostream>

#include <vector>

#include <deque>

using namespace std;

struct vertax{ // структура вершина

int vert, index, father; bool visited;

vertax(int a){vert = a; index = 10001; father = a;visited = false;}

vertax(int a, int b){

vert = a;

father = b;

index = 10001;visited = false;

}

vertax(int a, int b, int x){

vert = a;

father = b;

index = x;visited = false;

}

vector<vertax> follow;// с кем связанна эта вершина

~vertax(){}

};

struct graph{

vector<vertax> v; // list of vertax

int count;

graph(){};

graph(int n){

count = n;

}

void get(){//инициализируем граф

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

vertax v(i);

for(int j = 1; j <= count; j++){

int x;

cin >> x;

if(x != 0){

vertax temp(j, i, x);

v.follow.push_back(temp);

}

graph::v.push_back(v);

}

void write(){//вывод вершины, и с кем она связанна

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

cout << v[i].index << ":";

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

cout << v[i].follow[j].vert << " ";

}

cout << endl;

}

void way(vertax& x){//алгоритм

deque<vertax> list;

x.index = 0;

x.visited = true;

list.push_front(x);

while(!list.empty()){

vertax& y = list[0];

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

v[y.follow[i].vert -1].visited = true;

if(v[y.follow[i].vert-1].index > y.index+y.follow[i].index){

v[y.follow[i].vert-1].index = y.index+y.follow[i].index;

if(v[y.follow[i].vert-1].index > -102){

list.push_back(v[y.follow[i].vert-1]);

}

list.pop_front();

}

void def(){//фунция к приведению значений по умолчанию

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

v[i].index = 10001;

v[i].visited = false;

}

void task1(){ // Решение задачи e-olymp.com №976: Флойд - существование

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

way(v[i]);

for(int j = 0; j < v.size()-1; j++){

if(!v[j].visited){

cout << 0 << " ";

}else if(v[j].index < -50){

cout << 2 << " ";

}else{

cout << 1 << " ";

}

if(!v[v.size()-1].visited){

cout << 0 ;

}else if(v[v.size()-1].index < -50){

cout << 2 ;

}else{

cout << 1 ;

}

def();

cout << endl;

}

void task2(){ // Решение задачи e-olymp.com №974: Флойд-1

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

way(v[i]);

for(int j = 0; j < v.size()-1; j++){

if(!v[j].visited){

cout << 0 << " ";

}else{

cout << v[j].index << " ";

}

if(!v[v.size()-1].visited){

cout << 0 ;

}else{

cout << v[v.size()-1].index;

}

def();

cout << endl;

}

};

int main() {

ios::sync_with_stdio(false);

int n;

cin >> n;

graph dog(n);

dog.get();

dog.task1();// Решаем задачу №976: Флойд - существование

dog.task2();// Решаем задачу №974: Флойд-1

return 0;

}

link

Related Images:

e-olimp 6124. Стек неограниченного размера

18/03/2015 by Ілларіонова Марія Валеріївна

Стек неограниченного размера

Реализуйте структуру данных «стек«. Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
push n
Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из стека последний элемент. Программа должна вывести его значение.
back
Программа должна вывести значение последнего элемента, не удаляя его из стека.
size
Программа должна вывести количество элементов в стеке.
clear
Программа должна очистить стек и вывести ok.
exit
Программа должна вывести bye и завершить работу.

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

Решение

Предлагается реализация стека через связные списки.

Положительные стороны:

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

Отрицательные стороны:

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

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

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

struct node {
   int value=0;
   node* prev=NULL;
   node(int val, node* prv): value(val), prev(prv) {} // конструктор нашего верхнего элемента в стеке
};

struct stack {
   int cnt=0;
   node* top=NULL;
   void push (int n) {
       top = new node(n, top); // когда создаём новую вершину, но присваиваем ей цену, а предыдущей записываем прошлую топовую вершину
       cnt++;
   }
   bool empty() {
       return cnt == 0;
   }
   int pop() {
       node* prev = top->prev; // записываем предыдущий узел во временную переменную
       int topVal = top->value;
       delete top; // удаляем последний элемент стека
       top = prev; // говорим, что он теперь равен прдыдущему
       cnt--;
       return topVal;
   }
   int back() {
       return top->value;
   }
   int size() {
       return cnt;
   }
   void clear() {
       while (!empty()) pop();
   }
};

int main() {
   ios::sync_with_stdio(false);
   string t;
   int val;
   stack s;
   while (1) {
       cin >> t;
       if (t=="push") {
           cin >> val;
           s.push(val);
           cout << "ok" << endl;
       }
       else if (t=="pop") {
           if (s.empty())
               cout << "error" << endl;
           else {
               val = s.pop();
               cout << val << endl;
           }
       }
       else if (t=="back") {
           if (s.empty())
               cout << "error" << endl;
           else
               cout << s.back() << endl;
       }
       else if (t=="size") cout << s.size() << endl;
       else if (t=="clear") {
           s.clear();
           cout << "ok" << endl;
       }
       else if (t=="exit") {
           cout << "bye" << endl;
           break;
       }
   }
   return 0;
}

#include <iostream>

#include <string>

using namespace std;

struct node {

int value=0;

node* prev=NULL;

node(int val, node* prv): value(val), prev(prv) {} // конструктор нашего верхнего элемента в стеке

};

struct stack {

int cnt=0;

node* top=NULL;

void push (int n) {

top = new node(n, top); // когда создаём новую вершину, но присваиваем ей цену, а предыдущей записываем прошлую топовую вершину

cnt++;

}

bool empty() {

return cnt == 0;

}

int pop() {

node* prev = top->prev; // записываем предыдущий узел во временную переменную

int topVal = top->value;

delete top; // удаляем последний элемент стека

top = prev; // говорим, что он теперь равен прдыдущему

cnt--;

return topVal;

}

int back() {

return top->value;

}

int size() {

return cnt;

}

void clear() {

while (!empty()) pop();

}

};

int main() {

ios::sync_with_stdio(false);

string t;

int val;

stack s;

while (1) {

cin >> t;

if (t=="push") {

cin >> val;

s.push(val);

cout << "ok" << endl;

}

else if (t=="pop") {

if (s.empty())

cout << "error" << endl;

else {

val = s.pop();

cout << val << endl;

}

else if (t=="back") {

if (s.empty())

cout << "error" << endl;

else

cout << s.back() << endl;

}

else if (t=="size") cout << s.size() << endl;

else if (t=="clear") {

s.clear();

cout << "ok" << endl;

}

else if (t=="exit") {

cout << "bye" << endl;

break;

}

return 0;

}

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].