Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Levk
0 / 0 / 0
Регистрация: 22.02.2012
Сообщений: 4
#1

Как работает эта программа? - C++

22.02.2012, 09:10. Просмотров 412. Ответов 0
Метки нет (Все метки)

Помогите пожалуйста построчно/блочно определить, что делается в программе. Заранее благодарю!

Задача
На стороне оператора установлен SMS шлюз, который по некоторому протоколу принимает сообщения и передаёт их конечным абонентам. У шлюза есть память, которая может хранить не более M сообщений.
Шлюз работает циклично, каждый цикл состоит из следующих шагов:
1) Шлюз принимает заявки на отправку сообщений от всех провайде-ров. Каждая заявка содержит количество сообщений для отправки и стои-мость одного сообщения. Все сообщения в одной заявке имеют одинаковую стоимость.
2) Шлюз анализирует заявки и сохраненные в памяти сообщения, после чего запрашивает у провайдеров не более M сообщений для последующей отправки.
3) Все запрошенные сообщения сохраняются в память, при необходимости затирая старые.
4) Шлюз отправляет не более N сообщений из своей памяти, все от-правленные сообщения удаляются из памяти.
5) Если в памяти остались сообщения, то цена каждого сообщения уменьшается на 1 копейку, если цена становится нулевой сообщение удаля-етсяиз памяти. После чего шлюз переходит к следующему циклу.
Определить, сколько сообщений будет доставлено, сколько будет потеряно и сколько денег будет заработано, если известно, что на начало работы сообщений в памятине было, и шлюз работал по оптимальномуалгоритму позволяющему заработать как можно больше денег.

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

Первая строка входа содержит количество тестов. Первая строка каждого теста содержит три числа K, N, M. K – количество циклов работы шлюза (1<=K<=100). N – максимальное количество сообщений, которое может отправить шлюз за один цикл (1<=N<=1000000). M – количество сообщений, сохраняемое в памяти шлюза (1<=M<=1000000). Далее следует K строк с описанием заявок принятых в каждом цикле работы шлюза. В начале каждой строкизадается число P - количество заявок, полученных в данном цикле, далее следует Pпар чисел, описывающих параметры заявки:n– количество сообщений и c- стоимость одного сообщения в копейках (0<P<=100, 0<n<=1000, 0<c<=1000). Работа шлюза заканчивается после Kцикла, оставшиеся в памяти сообщения считаются потерянными.

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

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

Пример входных данных Пример выходных данных
1 75 150 325
2 100 50
1 200 3
1 25 7

Решение
C++
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <algorithm>
using namespace std;
 
struct package
{
    package()
    {}
    package(int c, int m): count(c), money(m)
    {}
    int count, money;
 
};
 
bool cmp (package &f, package &s)
{
    return f.money >s.money;
}
 
typedef vector<package>::iterator pi;
 
int main()
{
    freopen("gateway.in", "r", stdin);
    freopen("gateway.out", "w", stdout);
 
    vector<package> pack, next;
    pack.reserve(100*100);
    next.reserve(100*100);
 
    int testn;
    cin >> testn;
    for(int test = 0; test < testn; test++)
    {
        long long send = 0, lost = 0, money = 0;
        int k, n, m;
        cin >> k >> n >> m;
 
        assert(1<=k && k<=100);
        assert(1<=n && n<=1000000);
        assert(1<=m && m<=1000000);
 
        for(int iter=0; iter<k; iter++)
        {
            int p;
            cin >> p;
            assert(1<=p && p<=100);
            for(int i=0; i<p; i++)
            {
                package cur;
                cin >> cur.count >> cur.money;
 
                assert(1<=cur.count && cur.count<=1000);
                assert(1<=cur.money && cur.money<=1000);
                next.push_back(cur);                
            }
 
            sort(next.begin(), next.end(), cmp);
            
            int mem = 0;
            pi pos = next.begin();
            while(mem < m && pos!=next.end())
            {
                int add = min(m-mem, pos->count);
                mem+=add;
                package cur(add, pos->money);
                pack.push_back(cur);
                pos->count -= add;      
                pos++;
            }
 
            for(pi i = next.begin(); i!= next.end(); i++)
            {
                lost += i->count;
            }
 
            int s = 0;
            pos = pack.begin();
            while(s < n && pos != pack.end())
            {
                int add = min(n-s, pos->count);
                s += add;
                pos->count -= add;
                money += add*pos->money;
                pos++;
            }
            send+=s;
 
            next.clear();
            for(pi i=pack.begin(); i!=pack.end(); i++)
            {
                if (i->count == 0) continue;
 
                i->money--;
                if (i->money == 0)
                {
                    lost += i->count;
                }
                else
                {
                    next.push_back(*i);
                }
            }
            pack.clear();
        }
 
        for(pi i = next.begin(); i!=next.end(); i++)
        {
            lost += i->count;
        }
        next.clear();
 
        cout << send << " " << lost << " " << money << endl;
    }
 
 
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.02.2012, 09:10     Как работает эта программа?
Посмотрите здесь:

Как работает эта программа? (клиент-сервер) - C++
клиент: #include &lt;stdio.h&gt; #include &lt;string.h&gt; #include &lt;winsock2.h&gt; #include &lt;windows.h&gt; #pragma comment(lib, &quot;ws2_32.lib&quot;) ...

У кого нибудь работает эта программа? просто запустите - C++
#pragma hdstop #include &lt;stdio.h&gt; #include &lt;conio.h&gt; #include &lt;string.h&gt; #define eof 26 #define max 1000 char line; char...

Как работает эта функция? - C++
Как работает эта функция?Я знаю, что она ищет простые числа, но каким образом,я не понимаю.Например зачем тут Num/2 и т.д? bool...

Как работает эта функция? - C++
Вот код программы крестики-нолики. Пожалуйста, объясните на пальцах как работает ф-ция &quot;botMove&quot;. Мне нужно написать такую же, но у меня...

Не понимаю как работает эта функция - C++
Что означают аргументы &amp; и * в этой функции ? template &lt;typename T&gt; inline T* const&amp; max(T* const&amp; a, T* const&amp; b) { return *a...

Как работает эта часть кода? - C++
element *el, *n_el; int i; n_el = (element *)malloc(sizeof(element)); printf(&quot;Vvedite FIO: &quot;); scanf(&quot;%32s %32s %32s&quot;,...

Поясните что и как делает эта программа! - C++
Вот программа. #include &lt;iostream&gt; using namespace std; void main() { const int n=7; int a={1,0,-3,2,0,-4,5};

Объясните пожалуйста как работает эта сортировка - C++
Я не совсем понимаю что происходит с вектором #include &lt;stdio.h&gt; #include &lt;iostream&gt; #include &lt;string&gt; #include &lt;vector&gt; ...

Не могли бы объяснить, как работает эта функция для удаления цифр? - C++
char* delDig(char *S) { int i,j; i=0; for (j=0; j&lt;strlen(S); j++) if ((S &lt; '0') || (S &gt; '9')) S=S; S=0;...

Для чего предназначена эта программа - C++
Для чего предназначена эта программа, и как ее доработать? #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; #include...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru