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

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

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

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

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

Новые блоги и статьи Все статьи Все блоги /
Вопросы на собеседованиях по микросервисам ArchitectMsa 27.03.2025 Работодатели ищут не просто разработчиков, знающих базовые концепции, а специалистов, разбирающихся в тонкостях масштабирования, отказоустойчивости и производительности. Сейчас на первый план выходят. . .	Взаимодействие Python с REST API py-thonny 27.03.2025 REST API - это архитектурный стиль взаимодействия компонентов распределённого приложения в сети. Python располагает функциональным набором инструментов для работы с REST API и основная библиотека для. . .	sshd restrictions, ssh access limitations jigi33 26.03.2025 sshd restrictions \| ssh access limitations рестрикции доступа на сервер sshd статья: https:/ / www. golinuxcloud. com/ restrict-allow-ssh-certain-users-groups-rhel	Компиляция C++ с Clang API NullReferenced 24.03.2025 Компиляторы обычно воспринимаются как черные ящики, которые превращают исходный код в исполняемые файлы. Мы запускаем компилятор командой в терминале, и вуаля — получаем бинарник. Но что если нужно. . .	Многопоточное программирование в C#: Класс Thread UnmanagedCoder 24.03.2025 Когда запускается приложение на компьютере, операционная система создаёт для него процесс - виртуальное адресное пространство. В C# этот процесс изначально получает один поток выполнения — главный. . .
SwiftUI Data Flow: Передача данных между представлениями mobDevWorks 23.03.2025 При первом знакомстве со SwiftUI кажется, что фреймворк предлагает избыточное количество механизмов для передачи данных: @State, @Binding, @StateObject, @ObservedObject, @EnvironmentObject и другие. . . .	Моки в Java: Сравниваем Mockito, EasyMock, JMockit Javaican 23.03.2025 Как протестировать класс, который зависит от других сложных компонентов, таких как базы данных, веб-сервисы или другие классы, с которыми и так непросто работать в тестовом окружении? Для этого и. . .	Архитектурные паттерны микросервисов: ТОП-10 шаблонов ArchitectMsa 22.03.2025 Популярность микросервисной архитектуры объясняется множеством важных преимуществ. К примеру, она позволяет командам разработчиков работать независимо друг от друга, используя различные технологии и. . .	Оптимизация рендеринга в Unity: Сортировка миллиона спрайтов GameUnited 22.03.2025 Помните, когда наличие сотни спрайтов в игре приводило к существенному падению производительности? Время таких ограничений уходит в прошлое. Сегодня геймдев сталкивается с задачами совершенно иного. . .	Образование и практика Igor3D 21.03.2025 Добрый день А вот каково качество/ эффективность ВУЗовского образования? Аналитическая геометрия изучается в первом семестре и считается довольно легким курсом, что вполне справедливо. Ну хорошо,. . .

@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

Опции темы

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

Решение