e-olymp 161. Роботы

01/03/2018 by Костя Григорян

Задача

На некотором заводе решили модернизировать производство и закупили для этого роботов. Так как для обработки детали требовалось выполнение двух операций, роботы также были двух типов: первую операцию выполняли роботы типа $A$, а вторую – роботы типа $B$. Чтобы сэкономить на покупке роботов, было решено купить не новых роботов последней модели, а уже бывших в употреблении. В результате, время, которое разные роботы тратили на выполнение одной и той же операции, существенно различалось, что привело к трудностям в планировании работ.

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

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

В первой строке натуральное число $N$, $1 ≤ N ≤ 100000$ – количество деталей, которое необходимо обработать.

Во второй строке натуральное число $N_a$, $1 ≤ N_a ≤ 1000$ – количество роботов, выполняющих первую операцию.

В третьей строке через пробел $N_a$ натуральных чисел $A_{i}$, $1 ≤ A_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $A$ на выполнение операции.

В четвертой строке натуральное число $N_b$, $1 ≤ N_b ≤ 1000$ – количество роботов, выполняющих вторую операцию.

В пятой строке через пробел $N_b$ натуральных чисел $B_{i}$, $1 ≤ B_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $B$ на выполнение операции.

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

В первой строке одно целое число – минимальное время, за которое все $N$ деталей будут обработаны сначала роботом типа $A$, а потом роботом типа $B$. Временем передачи детали от робота типа $A$ роботу типа $B$ пренебречь.

Тесты

Входные данные	Выходные данные
[latex]6[/latex]	[latex]9[/latex]
[latex]3[/latex]
[latex]1\, 3\, 2[/latex]
[latex]2[/latex]
[latex]2\, 3[/latex]
[latex]2[/latex]	[latex]5[/latex]
[latex]2[/latex]
[latex]3\, 2[/latex]
[latex]2[/latex]
[latex]2\, 3[/latex]
[latex]5[/latex]	[latex]41[/latex]
[latex]4[/latex]
[latex]84\, 50\, 50\ 8[/latex]
[latex]2[/latex]
[latex]1\, 21[/latex]
[latex]100[/latex]	[latex]100[/latex]
[latex]2[/latex]
[latex]1\, 50[/latex]
[latex]4[/latex]
[latex]1\, 2\, 3\, 4[/latex]

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

#include <iostream>
#include <set>
#include <climits>
using namespace std;

int inf = INT_MAX;

int main() {
    cin.sync_with_stdio(false);
    int n;
    cin >> n;
    int na;
    cin >> na;
    multiset<pair<int, int> > s;
    int a[na];
    int resa[n];
    for(int i=0; i<na; i++)
    {
        cin >> a[i];
        s.insert({a[i], a[i]});
    }
    for(int i=0; i<n; i++)
    {
        auto it=s.begin();
        int val=it->first;
        int t=it->second;
        s.erase(it);
        s.insert({val+t, t});
        resa[i]=val;
    }
    int nb;
    cin >> nb;
    int b[nb];
    for(int i=0; i<nb; i++)
    {
        cin >> b[i];
    }
    multiset<pair<int, int> > q;
    long long l=resa[n-1], r=10000100;
    while(l<r)
    {
        int w=0;
        int m=(l+r)/2;
        for(int i=0; i<nb; i++)
        {
            q.insert({b[i], b[i]});
        }
        q.insert({inf, inf});
        for(int i=n-1; i>=0; i--)
        {
            int y=m-resa[i];
            auto x=q.begin();
            if(y<(x->first))
            {
                w++;
                break;
            }
            else{
                auto it=q.lower_bound({y, -1});
                int z=it->first;
                if(z>y)
                    it--;
                int val=it->first;
                int t=it->second;
                q.erase(it);
                q.insert({val+t, t});
            }
        }
        if(w==0)
            r=m;
        else
            l=m+1;
        q.clear();  
    }
    cout << l;
    return 0;
}

#include <iostream>

#include <set>

#include <climits>

using namespace std;

int inf = INT_MAX;

int main() {

cin.sync_with_stdio(false);

int n;

cin >> n;

int na;

cin >> na;

multiset<pair<int, int> > s;

int a[na];

int resa[n];

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

{

cin >> a[i];

s.insert({a[i], a[i]});

}

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

{

auto it=s.begin();

int val=it->first;

int t=it->second;

s.erase(it);

s.insert({val+t, t});

resa[i]=val;

}

int nb;

cin >> nb;

int b[nb];

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

{

cin >> b[i];

}

multiset<pair<int, int> > q;

long long l=resa[n-1], r=10000100;

while(l<r)

{

int w=0;

int m=(l+r)/2;

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

{

q.insert({b[i], b[i]});

}

q.insert({inf, inf});

for(int i=n-1; i>=0; i--)

{

int y=m-resa[i];

auto x=q.begin();

if(y<(x->first))

{

w++;

break;

}

else{

auto it=q.lower_bound({y, -1});

int z=it->first;

if(z>y)

it--;

int val=it->first;

int t=it->second;

q.erase(it);

q.insert({val+t, t});

}

if(w==0)

r=m;

else

l=m+1;

q.clear();

}

cout << l;

return 0;

}

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

Решение состоит из двух этапов.
Найдем минимальное время, которое понадобится роботам первого типа, чтобы завершить обработку всех деталей. Для каждой детали, мы берем робота с минимальным временем завершения обработки этой детали и обновляем его время на время обработки им одной детали.
Найдем теперь общее минимальное время работы роботов, требуемое для завершения обработки всех деталей. Пусть нам уже известно, за какое время обрабатывают роботы первого типа каждую из данных деталей. Очевидно, что если возможно выполнить работу за $t$, то возможно выполнить работу и за $t+1$, а также, если невозможно выполнить работу за $t$, то невозможно выполнить работу за $t-1$. Следовательно, для решения данной задачи можно применить бинарный поиск по ответу. Применим бинарный поиск по ответу, рассматривая детали по мере их поступления с конца: роботы могут выполнить работу за $T$, если для каждой детали существует такой робот второго типа, который выполнит работу за $T_{2}$, такое, что $ T_{1}+T_{2}$ $\leqslant T$, где $T_{1}$ – время, за которое эту деталь выполнит робот первого типа.
Теперь оценим сложность работы алгоритма. Бинарный поиск работает за $O(\log n)$. Для каждого этапа бинарного поиска мы обрабатываем $n$ деталей. Далее для каждой из $n$ деталей работает логарифмическая вставка в мультисет. Получаем, что асимптотическая вычислительная сложность алгоритма $O(n\, \log^2n)$.

Ссылки

Условие задачи на e-olymp
Код решения
Видеозапись разбора задачи Евгением Задорожным на зимней школе по алгоритмам и программированию в Одесском национальном университете иемни И.И.Мечникова:

Related Images:

e-olymp 138. Банкомат

20/09/2015 by Женя Максимова

Задача. В банкомате имеются в достаточном количестве купюры номиналом [latex]10, 20, 50, 100, 200[/latex] и [latex]500[/latex] гривен. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в [latex]n[/latex] гривен[latex](0 \leq n \leq 1000001)[/latex], или вывести [latex]-1[/latex], если указанную сумму выдать нельзя.

Тесты

Сумма	130	999	7360	3	80	123450	567	440
Число купюр	3	-1	18	-1	3	249	-1	4

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

#include <stdio.h>
int Q[] = { 500, 200, 100, 50, 20, 10 }; //создание одномерного массива, в который входят все имеющиеся купюры
int main()
{
 int n, q, x; //q - вспомогательная переменная в цикле
 scanf("%d",&n); 
 x=0; //количество купюр,  ему по умолчанию присваивается 0
 for(int i = 0; i < 6; ++i) //цикл перебирает все элементы массива, от большего к меньшему
 {
    q = Q[i]; 
    x += n / q; //считаем, сколько раз входит купюра в сумму
    n %= q;  //сумме присваивается остаток от деления на данную купюру
 }
 if(n > 0) x = -1; //проверяем наличие остатка, который банкомат не сможет выдать
 printf("%d",x); 
 return 0;
}

#include <stdio.h>

int Q[] = { 500, 200, 100, 50, 20, 10 }; //создание одномерного массива, в который входят все имеющиеся купюры

int main()

{

int n, q, x; //q - вспомогательная переменная в цикле

scanf("%d",&n);

x=0; //количество купюр, ему по умолчанию присваивается 0

for(int i = 0; i < 6; ++i) //цикл перебирает все элементы массива, от большего к меньшему

{

q = Q[i];

x += n / q; //считаем, сколько раз входит купюра в сумму

n %= q; //сумме присваивается остаток от деления на данную купюру

}

if(n > 0) x = -1; //проверяем наличие остатка, который банкомат не сможет выдать

printf("%d",x);

return 0;

}

Алгоритм

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

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

Следует учесть, что сумма может быть и такой, что банкомат не сможет ее выдать. Это будет происходить тогда, когда сумма содержит некоторую часть, меньшую самой меньшей купюры. Чтобы выяснить, так ли это, мы смотрим, что осталось от суммы после применения жадного»алгоритма. Если остаток равен [latex]0[/latex], то исходную сумму можно получить с помощью имеющихся купюр, и на экран выводится результат, полученный в цикле. Если же остаток больше [latex]0[/latex], такую операцию осуществить невозможно и программа выводит [latex]-1[/latex].

Решение

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

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

Related Images:

e-olymp 3. Спичечная модель

25/09/2014 by Куленюк Денис Віталійович

Спичечная модель с http://www.e-olimp.com.ua/problems/3

Условие задачи:
http://www.e-olimp.com.ua/problems/3
Прохождение тестов данной программой:
http://www.e-olimp.com.ua/
solutions/1591163
Я разделил задачу на три подэтапа: построение боковой, верхней и задней стен.

Ввод Вывод Комментарий Вердикт

0 0 Проверка на нуль: Пройдено

3 28 Тот же пример что и в условии к задаче: Сходится Проверка пройдена

9 62 1 этап Пройдено

13 83 2 этап Пройдено

19 112 3 этап Пройдено

2Е9 6.00953Е9 Проверка на переполнение максимальным возможным числом: Пройдено

Вначале увидев эту задачу я понял что самое главное в этой задаче это понять какую фигуру лучше строить и как строить. С фигурой все было очевидно: в данном случае самая экономичная фигура это куб, а это значит что нам нужно найти как лучше всего его строить, а если быть более точным как из кубов с величиной стены [latex]I[/latex] построить куб с величиной стены [latex]I+1[/latex]. Я решил что нужно последовательно наращивать стены: вначале боковую, потом верхнюю и напоследок заднюю. Здесь было замечено что количество кубов входящих в нашу фигуру можно найти просто возведя сторону в кубическую степень, с этого и пошли эти строчки:

C++

for(; k<n ; ++i){ k=pow(i+1,3); }

13
14
15

for(; k<n ; ++i){
       k=pow(i+1,3);
   }

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

Первый этап(строительство боковой стены):

C++

if ( (i-1)*(i-1)*(i-1) < n && n<= (i-1)*(i-1)*i )

18

if ( (i-1)*(i-1)*(i-1) < n && n<= (i-1)*(i-1)*i )

Второй этап(строительство верхней стены):

C++

else if ( (i-1)*(i-1)*i < n && n<= (i-1)*i*i )

23

else if ( (i-1)*(i-1)*i < n && n<= (i-1)*i*i )

Или третий(строительство задней стены):

C++

else if ( (i-1)*i*i < n && n<= i*i*i )

28

else if ( (i-1)*i*i < n && n<= i*i*i )

И мы сразу приступаем к делу: я вывел формулу зависимости количества спичек от фигуры, вот она:
[latex]3xyz+2xy+2xz+2yz+x+y+z[/latex] и из неё я уже вывел эти формулы:
1) Если все стороны равны: [latex]3n(n+1)^2[/latex];

C++

r=3*(i-1)*pow(i,2);

20

r=3*(i-1)*pow(i,2);

2) Если две стороны равны, а третья на единицу больше: [latex]3n^3 + 9n^2 + 7n + 1[/latex];

C++

r= 3*pow(i-1,3) + 9*pow(i-1,2) + 7*(i-1) + 1;

25

r= 3*pow(i-1,3) + 9*pow(i-1,2) + 7*(i-1) + 1;

3) Если две стороны равны, а третья на единицу меньше: [latex]3n^3 + 3n^2 -n-1[/latex].

C++

r= 3*(pow(i,3) + pow(i,2))-i-1;

30

r= 3*(pow(i,3) + pow(i,2))-i-1;

Зачем? Первая формула пригодится нам для первого этапа, когда к уже готовому кубу добавляются еще кубы. Вторая: когда после первого этапа одна сторона стала больше чем остальные. И конечно же третья: которая соответственно строится когда две стороны больше третьей.
Теперь нам осталось только достроить недостающие кубы, для этого вначале нужно узнать сколько кубов нужно достроить:
1)Для первого этапа:

C++

n-=pow(i-1,3);

21

n-=pow(i-1,3);

2)Для второго:

C++

n-=pow(i-1,2)*i;

26

n-=pow(i-1,2)*i;

3)И конечно же для третьего:

C++

n-=pow(i,2)*(i-1);

31

n-=pow(i,2)*(i-1);

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

C++

for( int i1=1 ; n ; i1+=2 )for( int i2=0 ; i2<i1 && n ; i2++,n-- )

37

for( int i1=1 ; n ; i1+=2  )for( int i2=0 ; i2<i1 && n ; i2++,n-- )

Зачем нам это нужно? Просто, я заметил что достройка идет по такому принципу(начиная с левого нижнего угла):

3 3 3 5

3 3 5 3

3 5 3 3

8 5 5 5

и в таком порядке:

16 15 14 13

9 8 7 12

4 3 6 11

1 2 5 10

Как вы видите +8 мы видим только на первом кубе, а +5 на первом кубе треугольного и в середине треугольного . Осталось только описать это и мы получаем:

C++

#include <cstdlib> #include <iostream> #include <cmath> using namespace std; int main() { double n, k=1, i=0,r,r1; cin>>n; for(; k<n ; ++i){ k=pow(i+1,3); } if(!i)i++; if ( (i-1)*(i-1)*(i-1) < n && n<= (i-1)*(i-1)*i ) { r=3*(i-1)*pow(i,2); // 3n(n+1)^2 n-=pow(i-1,3); } else if ( (i-1)*(i-1)*i < n && n<= (i-1)*i*i ) { r= 3*pow(i-1,3) + 9*pow(i-1,2) + 7*(i-1) + 1; // 3n^3 + 9n^2 + 7n + 1 n-=pow(i-1,2)*i; } else if ( (i-1)*i*i < n && n<= i*i*i ) { r= 3*(pow(i,3) + pow(i,2))-i-1; // 3n^3 + 3n^2 -n-1 n-=pow(i,2)*(i-1); } else{ cout << i << "???"; return 0; } for( int i1=1 ; n ; i1+=2 ) { for( int i2=0 ; i2<i1 && n ; i2++,n-- ) { if( i1 == 1 ){ r+=8; } else if( i2 == 0 || i2 == i1/2 ){ r+=5; } else{ r+=3; } } } cout << r << endl; return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <cstdlib>
#include <iostream>
#include <cmath>

using namespace std;

int main()
{


   double n, k=1, i=0,r,r1;
   cin>>n;
   for(; k<n ; ++i){
       k=pow(i+1,3);
   }
   if(!i)i++;

   if ( (i-1)*(i-1)*(i-1) < n && n<= (i-1)*(i-1)*i )
   {
        r=3*(i-1)*pow(i,2);                                    // 3n(n+1)^2
        n-=pow(i-1,3);
   }
   else if ( (i-1)*(i-1)*i < n && n<= (i-1)*i*i )
   {
               r= 3*pow(i-1,3) + 9*pow(i-1,2) + 7*(i-1) + 1; // 3n^3 + 9n^2 + 7n + 1
               n-=pow(i-1,2)*i;
   }
   else if ( (i-1)*i*i < n && n<= i*i*i )
   {
        r= 3*(pow(i,3) + pow(i,2))-i-1;             // 3n^3 + 3n^2 -n-1
        n-=pow(i,2)*(i-1);
   }
   else{
       cout << i << "???";
       return 0;
   }
    for( int i1=1 ; n ; i1+=2  )
               {
                   for( int i2=0 ; i2<i1 && n ; i2++,n-- )
                   {
                       if( i1 == 1 ){
                                       r+=8;
                                    }
                       else if( i2 == 0 || i2 == i1/2 ){
                                                           r+=5;
                                                        }
                       else{
                               r+=3;
                           }
                   }

               }
        cout << r << endl;

return 0;
}

Related Images:

Posted in Творческие задачи. Tagged Жадные алгоритмы, Олимпиадные задачи.

Post navigation

Search

1. Линейные вычисления

2. Программы с ветвлением

3. Циклы

4. Потоковая обработка

5. Массивы

6. Многомерные массивы

7. Строки c-string

8. Строки string

9. Последовательные контейнеры

A. Сортировки и жадность

B. Стеки-деки-очереди

C. Ассоциативные контейнеры

D. Графы

E. Дерево отрезков

F. Динамическое программирование

Игры программистов

Спортивное программирование

Творческие задачи

Численный анализ

⌂ Организационные

Студенты 2020

Введите адрес для отправки новостей

E-mail

Іванов Вячеслав Володимирович (22)
Ілларіонова Марія Валеріївна (20)
Зелінський Вячеслав Олександрович (19)
Вустянюк Ігор Дмитрович (19)
Сплошнов Кирилл (18)
Таран Таня (17)
Гордийчук Вадим (15)
Корнилова Таня (14)
Денисова Ольга (14)
Калачьов Андрій Сергійович (14)
Студенты 2019

Студенты 2018

Студенты 2017

Студенты 2016

Студенты 2015

Студенты 2014

Proudly powered by WordPress | Theme: Sunspot by WordPress.com.

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

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

Tag Archives: Жадные алгоритмы

e-olymp 161. Роботы

Задача

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

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

Тесты

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

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

Ссылки

Related Images:

e-olymp 138. Банкомат

Related Images:

М16. Freshly Pressed Juice

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

Тесты

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

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

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

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

Related Images:

e-olymp 3. Спичечная модель

Related Images:

Ввод	Вывод	Комментарий	Вердикт
0	0	Проверка на нуль:	Пройдено
3	28	Тот же пример что и в условии к задаче: Сходится	Проверка пройдена
9	62	1 этап	Пройдено
13	83	2 этап	Пройдено
19	112	3 этап	Пройдено
2Е9	6.00953Е9	Проверка на переполнение максимальным возможным числом:	Пройдено