Минимизация затрат на стоянку

@Erasus · Регистрация: 17.08.2014

Студворк — интернет-сервис помощи студентам

Всем привет, решаю задачу, написал вот такой код:

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
#include <iostream>
#include <cmath>
 
using namespace std;
 
long long find_min(long long *nums, int pos, int v1, int v2, int v3);
long long fnd_min(long long *nums, int pos, int v1, int v2, int v3);
 
int main()
{
    int a, b, c, n, len;
 
    cin >> a >> b >> c >> n;
 
    if (!(n % 28))
        len = n;
    else
        len = n + (28 - (n % 28));
 
    long long *days = new long long[len + 1];
    days[0] = 0;
    long long min;
    for (int i = 1; i <= len; i++)
    {
        days[i] = fnd_min(days, i, a, b, c);
        if (i == n)
            min = days[i];
        if (i > n && min > days[i])
            min = days[i];
    }
    cout << min << endl;
 
    system("pause");
    return 0;
}
 
long long find_min(long long *nums, int pos, int v1, int v2, int v3)
{
    long long min = pow(10.0, 15.0);
 
    for (int i = 0; i < pos; i++)
    {
        if (i + 1 == pos && min > nums[i] + v1)
            min = nums[i] + v1;
        else if (i + 7 == pos && min >(nums[i] + v2))
            min = nums[i] + v2;
        else if (i + 28 == pos && min > nums[i] + v3)
            min = nums[i] + v3;
    }
 
    return min;
}
 
long long fnd_min(long long *nums, int pos, int v1, int v2, int v3)
{
    long long min = min = nums[pos - 1] + v1;;
 
    /*
    if (min > nums[pos - 1] + v1 && pos - 1 >= 0)
        min = nums[pos - 1] + v1;*/
    if (min > nums[pos - 7] + v2 && pos - 7 >= 0)
        min = nums[pos - 7] + v2;
    if (min > nums[pos - 28] + v3 && pos - 28 >= 0)
        min = nums[pos - 28] + v3;
 
    return min;
}

Если при решении использовать функцию find_min, то всё нормально работает, но очень долго при больших значениях n (больше 100.000), а система принимает не более 2 сек.
Я немного переделал для ускорения и сделал функцию fnd_min, которая проверяет только 3 числа, но при n больше примерно 60.000 у меня вылетает ошибка в VS и прога зависает. По условию n меньше 10^15. Помогите пожалуйста исправить

@Aymurat · 02.01.2017, 23:21

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

@Erasus · 02.01.2017, 23:26 **[ТС]**

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

@Erasus · 03.01.2017, 14:21 **[ТС]**

нашел на 56 строчке ошибку:

C++
1
long long min = min = nums[pos - 1] + v1;;

->

C++
1
int min = nums[pos - 1] + v1;

Но не помогло

@Mr.X · 03.01.2017, 15:01

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
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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
///////////////////////////////////////////////////////////////////////////////
//2.
///////////////////////////////////////////////////////////////////////////////
//Оплата парковки
 
//Имя входного файла: стандартный ввод
//Имя выходного файла: стандартный вывод
//Ограничение по времени: 2 секунды
//Ограничение по памяти: 256 мегабайт
 
//На каникулах Роман решил отдохнуть во Флатландии и арендовал себе апартаменты
//и роскошный автомобиль. Разумеется, такой автомобиль нельзя оставлять во дворе,
 //поэтому Роман хочет также арендовать место на ближайшей охраняемой парковке.
//Поскольку он уже поиздержался с жильём и машиной, он хочет потратить на парковку
//как можно меньше бурлей.
//На парковке доступны три тарифа аренды:
 
//1. Заплатив a бурлей, можно использовать парковку в течение 1 дня.
 
//2. Заплатив b бурлей, можно использовать парковку в течение одной недели, то есть
//7 дней.
 
//3. Заплатив c бурлей, можно использовать парковку в течение четырёх недель, то есть
//28 дней.
 
//Роман планирует отдыхать во Флатландии n дней. Любой тариф можно использовать
//произвольное количество раз, также можно арендовать парковку на суммарно больший
//срок, чем нужно.
//Какое минимальное количество бурлей придётся заплатить Роману, чтобы иметь возможность
//использовать стоянку все n дней?
 
//Формат входных данных
//Первая строка входных данных содержит три целых числа a, b, c (1 <= a <= b <= c <= 1000)
//— цена в бурлях за однократную покупку первого, второго и третьего тарифа аренды
//соответственно.
 
//Вторая строка содержит целое число n (1 <= n <= 10^15) — количество дней, в течение которых
//Роман планирует отдыхать во Флатландии и оставлять машину на охраняемой парковке.
 
//Формат выходных данных
 
//Выведите единственное целое число — минимальное количество бурлей, которое Роману
//придётся потратить на аренду парковочного места.
 
//Примеры
 
//стандартный ввод   стандартный вывод
//4 7 20            14
//10
 
//2 9 38            47
//36
 
//Замечание
 
//В первом примере Роману выгодно взять 2 абонемента на неделю, это будет стоить
//2 * 7 = 14 бурлей и позволит оплатить парковку на 14 дней.
 
//Во втором примере выгодно купить 5 абонементов на неделю и 1 на день.
//Количество оплаченных дней будет ровно 36, а цена составит
//1 * 2 + 5 * 9 + 0 * 38 = 47 бурлей.
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
///////////////////////////////////////////////////////////////////////////////
typedef long long               T_int;
///////////////////////////////////////////////////////////////////////////////
const   T_int                   TARIFFS_TOTAL   {3};
///////////////////////////////////////////////////////////////////////////////
typedef std::array  < T_int,    TARIFFS_TOTAL   >   T_int_val_of_tariff;
typedef std::array  < double,   TARIFFS_TOTAL   >   T_double_val_of_tariff;
///////////////////////////////////////////////////////////////////////////////
const   T_int_val_of_tariff     DAYS_OF_TARIFF  { 1, 7, 28 };
///////////////////////////////////////////////////////////////////////////////
T_int     periods_of_tariff
    (
        T_int     n,
        T_int     tariff_ind
    )
{
    return  std::ceil   (
                                double(n)
                            /   DAYS_OF_TARIFF[ tariff_ind ]
                        );
}
///////////////////////////////////////////////////////////////////////////////
T_int     price_total_min
    (
        T_double_val_of_tariff  const   &   day_price_of_tariff,
        T_int                               n
    )
{
    if(!n)
    {
        return  0;
    }
 
    T_double_val_of_tariff  period_price_min_of_tariff{{}};
 
    for( T_int  i{}; i < TARIFFS_TOTAL; ++i )
    {
        period_price_min_of_tariff[i]
 
            =       DAYS_OF_TARIFF[i]
 
                *   *std::min_element
                        (
                            std::begin      ( day_price_of_tariff ),
 
                                std::begin  ( day_price_of_tariff )
                            +   i
                            +   1
                        );
    }//for
 
    T_double_val_of_tariff  results{{}};
 
    results[2]  =       period_price_min_of_tariff  [2]
                    *   periods_of_tariff           ( n, 2 );
 
    for( T_int  i = 1; i >= 0; --i )
    {
        results[i]  =       results                     [i + 1]
                        -   period_price_min_of_tariff  [i + 1]
 
                        +       period_price_min_of_tariff  [i]
 
                            *   periods_of_tariff
                                    (
                                        n   %   DAYS_OF_TARIFF[i + 1],
                                        i
                                    );
    }//for
 
    auto    res     =   *std::min_element
                            (
                                std::begin  ( results ),
                                std::end    ( results )
                            );
 
    return  std::round( res );
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    T_double_val_of_tariff  price_of_tariff{{}};
 
    for( auto   &   price   :   price_of_tariff )
    {
        std::cin    >>  price;
    }
 
    T_double_val_of_tariff  day_price_of_tariff{{}};
 
    for( T_int  i{}; i < TARIFFS_TOTAL; ++i )
    {
        day_price_of_tariff[i]  =       price_of_tariff     [i]
                                    /   DAYS_OF_TARIFF      [i];
    }
 
    T_int     n{};
    std::cin   >>  n;
 
    std::cout   <<  price_total_min
                        (
                            day_price_of_tariff,
                            n
                        )
 
                <<  std::endl;
}

@Erasus · 03.01.2017, 15:13 **[ТС]**

Спасибо большое за решение, но оно не проходит тест)
Я уже разобрался в своем решении, как я понял, нельзя очень большие массивы создавать (элементов так на 200.000), поэтому мысль уже появилась. Вопрос решен)

@Mr.X · 03.01.2017, 19:33

Сообщение от Erasus

Спасибо большое за решение, но оно не проходит тест

Да, пардон, в предыдущее решение вкрались ошибки, вот так правильно:

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
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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
///////////////////////////////////////////////////////////////////////////////
//3.
///////////////////////////////////////////////////////////////////////////////
//Оплата парковки
 
//Имя входного файла: стандартный ввод
//Имя выходного файла: стандартный вывод
//Ограничение по времени: 2 секунды
//Ограничение по памяти: 256 мегабайт
 
//На каникулах Роман решил отдохнуть во Флатландии и арендовал себе апартаменты
//и роскошный автомобиль. Разумеется, такой автомобиль нельзя оставлять во дворе,
 //поэтому Роман хочет также арендовать место на ближайшей охраняемой парковке.
//Поскольку он уже поиздержался с жильём и машиной, он хочет потратить на парковку
//как можно меньше бурлей.
//На парковке доступны три тарифа аренды:
 
//1. Заплатив a бурлей, можно использовать парковку в течение 1 дня.
 
//2. Заплатив b бурлей, можно использовать парковку в течение одной недели, то есть
//7 дней.
 
//3. Заплатив c бурлей, можно использовать парковку в течение четырёх недель, то есть
//28 дней.
 
//Роман планирует отдыхать во Флатландии n дней. Любой тариф можно использовать
//произвольное количество раз, также можно арендовать парковку на суммарно больший
//срок, чем нужно.
//Какое минимальное количество бурлей придётся заплатить Роману, чтобы иметь возможность
//использовать стоянку все n дней?
 
//Формат входных данных
//Первая строка входных данных содержит три целых числа a, b, c (1 <= a <= b <= c <= 1000)
//— цена в бурлях за однократную покупку первого, второго и третьего тарифа аренды
//соответственно.
 
//Вторая строка содержит целое число n (1 <= n <= 10^15) — количество дней, в течение которых
//Роман планирует отдыхать во Флатландии и оставлять машину на охраняемой парковке.
 
//Формат выходных данных
 
//Выведите единственное целое число — минимальное количество бурлей, которое Роману
//придётся потратить на аренду парковочного места.
 
//Примеры
 
//стандартный ввод   стандартный вывод
//4 7 20            14
//10
 
//2 9 38            47
//36
 
//Замечание
 
//В первом примере Роману выгодно взять 2 абонемента на неделю, это будет стоить
//2 * 7 = 14 бурлей и позволит оплатить парковку на 14 дней.
 
//Во втором примере выгодно купить 5 абонементов на неделю и 1 на день.
//Количество оплаченных дней будет ровно 36, а цена составит
//1 * 2 + 5 * 9 + 0 * 38 = 47 бурлей.
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <limits>
///////////////////////////////////////////////////////////////////////////////
typedef long long               T_int;
///////////////////////////////////////////////////////////////////////////////
const   T_int                   TARIFFS_TOTAL   {3};
///////////////////////////////////////////////////////////////////////////////
typedef std::array  < T_int,    TARIFFS_TOTAL   >   T_int_val_of_tariff;
///////////////////////////////////////////////////////////////////////////////
const   T_int_val_of_tariff     DAYS_OF_TARIFF  { 1, 7, 28 };
///////////////////////////////////////////////////////////////////////////////
T_int     periods_of_tariff
    (
        T_int     n,
        T_int     tariff_ind
    )
{
    return          n
                /   DAYS_OF_TARIFF          [ tariff_ind ]
 
            +   (
                            n
                        %   DAYS_OF_TARIFF  [ tariff_ind ]
 
                    !=  0
                );
}
///////////////////////////////////////////////////////////////////////////////
T_int     price_total_min
    (
        T_int_val_of_tariff     const   &   price_of_tariff,
        T_int                               n
    )
{
    T_int_val_of_tariff     price_min_of_tariff{{}};
 
    for( T_int  i{}; i < TARIFFS_TOTAL; ++i )
    {
        auto    &   elem_cur    =   price_min_of_tariff[i];
        elem_cur                =   std::numeric_limits<T_int>::max();
 
        for( T_int  j{}; j <= i; ++j )
        {
            elem_cur    =   std::min    (
                                            elem_cur,
 
                                                price_of_tariff     [j]
                                            *   DAYS_OF_TARIFF      [i]
                                            /   DAYS_OF_TARIFF      [j]
                                        );
        }//for
    }//for
 
    T_int_val_of_tariff     results{{}};
 
    results[2]  =       price_min_of_tariff     [2]
                    *   periods_of_tariff       ( n, 2 );
 
    for( T_int  i = 1; i >= 0; --i )
    {
        results[i]      =   results[i + 1];
 
        auto    n_i     =       n
                            %   DAYS_OF_TARIFF[i + 1];
 
        if( n_i )
        {
            results[i]  =       results                     [i]
                            -   price_min_of_tariff         [i + 1]
 
                            +       price_min_of_tariff     [i]
 
                                *   periods_of_tariff
                                        (
                                            n_i,
                                            i
                                        );
        }//if
    }//for
 
    return  *std::min_element
                (
                    std::begin  ( results ),
                    std::end    ( results )
                );
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    T_int_val_of_tariff     price_of_tariff{{}};
 
    for( auto   &   price   :   price_of_tariff )
    {
        std::cin    >>  price;
    }
 
    T_int     n{};
    std::cin   >>  n;
 
    std::cout   <<  price_total_min
                        (
                            price_of_tariff,
                            n
                        )
 
                <<  std::endl;
}

Новые блоги и статьи Все статьи Все блоги /
сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .

@Aymurat 125 / 117 / 67 Регистрация: 07.11.2014 Сообщений: 788
	02.01.2017, 23:21
	Erasus, условие задачи увидеть бы... А вообще, для нахождения минимума оптимально будет отсортировать массив/вектор по возрастанию, нулевой элемент то, что Вы искали. 0

@Erasus 2 / 2 / 1 Регистрация: 17.08.2014 Сообщений: 28
	02.01.2017, 23:26 [ТС]
	Условие задачи Миниатюры 0

@Erasus 2 / 2 / 1 Регистрация: 17.08.2014 Сообщений: 28
	03.01.2017, 15:13 [ТС]
	Спасибо большое за решение, но оно не проходит тест) Я уже разобрался в своем решении, как я понял, нельзя очень большие массивы создавать (элементов так на 200.000), поэтому мысль уже появилась. Вопрос решен) 0

Минимизация затрат на стоянку

Решение