Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.50/8: Рейтинг темы: голосов - 8, средняя оценка - 4.50
1 / 1 / 0
Регистрация: 18.09.2014
Сообщений: 70

Задача про кошелек. Проходит 8 тестов из 10

07.09.2018, 21:53. Показов 1824. Ответов 20

Студворк — интернет-сервис помощи студентам
Доброе время суток, решаю задачу (под спойлером), мое решение проходит 8 из 10 тестов. Я пробовал учесть что если "цены" всех покупок 0(пропускаем нулевые покупки, и если в итоге все нули, то выводим 0 -1, если нет, то выводим полноценно, но с пропуском 0й), пробовал что бы оно каждый 0 считало как покупка (так работает код под спойлером), отрицательный вариант на балансе на картах тоже пробовал, что пропускаем их. Что я мог не учесть, подскажите пожалуйста. Реализация кода который проходит 8 из 10 прилагается.

Задание
Разработайте программу распределения платежей .

Чтобы сохранить деньги, есть только один кошелек , и может быть несколько банковских счетов.

Платежи за покупки поступают из кошелька. Если кошелек не имеет достаточной суммы, деньги изымаются с банковского счета (ов); снятая сумма в два раза больше, чем покупка, независимо от того, сколько денег в кошельке. Если баланс на счете недостаточен для этой операции, деньги также берутся из следующей учетной записи.

Гарантируется, что банковские счета имеют достаточно денег для необходимых снятий.

Входные данные:
1. Целое число , сумма денег в кошельке .
2. Массив целых чисел, где каждый номер представляет собой сумму денег на банковском счете .
3. Номер прекращения -1.
4. Массив целых чисел, где каждый номер представляет собой сумму покупки .
5. Номер окончания -1.

Вывод:
1. Количество покупок .
2. Массив целых чисел, где номер завершения -1 разделяет остатки на всех банковских счетах после каждой покупки .

Пример:

Вход :
100 500 200 1000 -1 50 200 600 -1
Вывод:
3 500 200 1000 -1 100 200 1000 -1 0 0 100 -1

Расчет:

Расходы 50 :
Баланс:
Кошелек: 50
Банковские счета: 500 200 1000
Выход: 500 200 1000 -1

Расходы 200:
Снятие 400 с первой учетной записи
Баланс:
Кошелек: 50 + 400-200
Банковские счета: 500-400 200 1000
Выход: 100 200 1000 -1

Расходы 600:
Сумма отзыва 1200 :
·100 из первой учетной записи
·200 со второго счета
·900 с третьего счета
Баланс:
Кошелек: 250 + 1200-600
Банковские счета: 100-100 200-200 1000-900
Выход: 0 0 100 -1

Код
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
#include "iostream"
#include "vector"
#include "queue"
 
void inputVector(std::vector<long> &data)
{
    long value;
    std::cin >> value;
    while (-1 != value)
    {
        data.push_back(value);
        std::cin >> value;
    }
}
 
std::queue<std::vector<long>> calculated(long &money, std::vector<long> &moneyOfBank, const std::vector<long> &purchaseMoney)
{
    std::queue<std::vector<long>> result;
 
    for (long i = 0; i < purchaseMoney.size(); i++)
    {
        if (purchaseMoney.at(i) <= money)
            money -= purchaseMoney[i];
        else
        {
            long dbl_purchase = 2 * purchaseMoney.at(i);
            money += purchaseMoney.at(i);
 
            for (long j = 0; j < moneyOfBank.size(); j++)
            {
                if (dbl_purchase <= moneyOfBank[j])
                {
                    moneyOfBank[j] -= dbl_purchase;
                    dbl_purchase = 0;
                    break;
                }
                else
                {
                    dbl_purchase -= moneyOfBank[j];
                    moneyOfBank[j] = 0;
                }
            }
        }
 
        result.push(moneyOfBank);
    }
    return result;
}
 
void showResult(std::queue<std::vector<long>> &data)
{
    std::cout << data.size() << " ";
 
    while (!data.empty())
    {
        for (auto d : data.front())
            std::cout << d << " ";
        
        if(data.size()>1)
            std::cout << -1<<" ";
        else
            std::cout << -1;
 
        data.pop();
    }
}
 
int main()
{
    long money = 0;
 
    std::cin >> money;
 
    std::vector<long> moneyOfBank;
 
    std::vector<long> purchaseMoney;
 
    inputVector(moneyOfBank);
 
    inputVector(purchaseMoney);
 
    auto result = calculated(money, moneyOfBank, purchaseMoney);
 
    showResult(result);
 
    return 0;
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
07.09.2018, 21:53
Ответы с готовыми решениями:

Динамика - задача про Кузнечика с монетками. Не проходит по времени три теста
Здравствуйте, требуется помощь. Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики...

Не проходит пара тестов
Не могу отладить решение:cry: Посмотрите пожалуйста у кого есть минутка

Задача про взлом кода из книги Эрика Фримена про основы javascript в конце 5 главы.
читаю книгу Эрика Фримена про основы javascript.В конце 5 главы есть задачка про взлом кода.Никак не могу понять как ее решить.НЕ понимаю...

20
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
07.09.2018, 23:16
RamzezUA, а какие ограничения накладываются на программу и на вводимые значения?

Добавлено через 37 секунд
Цитата Сообщение от RamzezUA Посмотреть сообщение
мое решение проходит 8 из 10 тестов
С какой ошибкой оно не проходит два последних теста? Время? Память? Неверный результат?
0
07.09.2018, 23:20

Не по теме:

nonedark2008, using OOP

0
1 / 1 / 0
Регистрация: 18.09.2014
Сообщений: 70
07.09.2018, 23:38  [ТС]
nonedark2008
Прошу прощение, забыл указал. Ограничений по времени и памяти не указано, ошибка - неверный результат. Разве-что сказано что все числа влазят в 4х байтовый целочисленный тип со знаком.
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
08.09.2018, 00:15
RamzezUA, не вижу в твоем алгоритме каких-либо ошибок.
0
1 / 1 / 0
Регистрация: 18.09.2014
Сообщений: 70
08.09.2018, 00:36  [ТС]
nonedark2008
В том то и суть что вроде ошибок нет, а именно 2 теста не проходит, и именно последние, хотя вряд-ли это о чем-то говорит в принципе.
По этому и обратился к людям, может кто подскажет какую ситуацию я упустил для обработки, что может приводить к ошибке в результате,
Указано как знаковый, т.е. вариант с отрицательным балансом на карте возможен, и мы просто пропустим его как и нулевой - такое проверялось. Цена на покупку если отрицательна, это как-то алогична. Если 0, непонятно как обрабатывать, то ли как покупку (прямо как кража или приз) или вообще не обрабатывать. Ах мой мозг....
0
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,532
Записей в блоге: 1
08.09.2018, 00:45
Цитата Сообщение от RamzezUA Посмотреть сообщение
dbl_purchase -= moneyOfBank[j];
moneyOfBank[j] = 0;
я полагаю, ошибка в этом
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
08.09.2018, 00:52
RamzezUA, просто забей, или задолбай мозг автору этой задачи. Не стоит гадать, что же там такое подразумевал автор, когда писал вот это. Также может оказаться, что тесты неверны.

Добавлено через 4 минуты
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
я полагаю, ошибка в этом
Да, если предполагать, что сумма на счете может быть изначально отрицательной. Только это глупо, т.к. значение счета не может быть, скажем, равно -1.
0
1 / 1 / 0
Регистрация: 18.09.2014
Сообщений: 70
08.09.2018, 00:54  [ТС]
Kuzia domovenok
Та вроде нет. Там какая логика. У нас есть двойное снятие дбл_мани. Если он больше чем денег на банковском счету, мы уменьшаем дбл_мани на то что есть на счету и просто обнуляем счет и так по кругу пока дбл_мани не обнулится. Оно не правильно посчитает если на счету минус будет, но когда я отбрасывал счета которые <= 0, то результат такой же был, 8/10.

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

Я там у них налюбился с другим тестом, где считало все хорошо, но им вывод не нравился, хотя подогнал под их требования, пока просто не влупил setprecision(12), прошло.

Смотря как смотреть на задачу. Если условная персона набрала кредитов на этот счет, то баланс может быть минусом, но мы с ним просто ничего не сделаем и пропускаем же. Если те же деньги которые на руках, мы можем компенсировать, то минус на балансе никак.
0
309 / 221 / 74
Регистрация: 23.05.2011
Сообщений: 981
08.09.2018, 01:02
Я упоролся и написал свою реализацию.
Если ТС не лень, проверь, пожалуйста.

Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <utility>
#include <vector>
#include <tuple>
 
typedef long long lint;
typedef std::pair<size_t, lint> change_t; // изменившийся индекс и изменение
 
std::tuple<lint, std::vector<lint>, std::vector<lint>> read_data(std::istream& in)
{
    lint purse;
    in>>purse;
    std::vector<lint> accounts;
    lint v;
    do
    {
        in>>v;
        if(v!=-1)
            accounts.push_back(v);
    }
    while(v!=-1);
    
    std::vector<lint> buys;
    do
    {
        in>>v;
        if(v!=-1)
            buys.push_back(v);
    }
    while(v!=-1);
    
    return std::make_tuple(purse, std::move(accounts), std::move(buys));
}
 
void print_changes(std::ostream& out, const lint buy_num, std::vector<lint> account_state, 
                  const std::vector<std::vector<change_t>>& changes)
{
    out<<buy_num<<" ";
    for (const std::vector<change_t>& concrete_changes:changes)
    {
        for(const change_t change:concrete_changes)
        {
            account_state[change.first]+=change.second;
        }
        for(const lint v:account_state)
        {
            out<<v<<" ";
        }
        out<<"-1 ";
    }
}
 
int main()
{
    lint purse;
    std::vector<lint> accounts, buys;
    std::tie(purse, accounts, buys) = read_data(std::cin);
    
    const lint total_buys = buys.size(); // По условию денег хватает
    
    const std::vector<lint> accounts_initial = accounts; // Резервная копия
    
    typedef std::pair<size_t, lint> change_t; // изменившийся индекс и изменение    
    std::vector<std::vector<change_t>> changes; // Запоминаем только изменения для экономии памяти
    
    size_t active_account_index = 0;
    for(lint cost : buys)
    {
        changes.emplace_back();
        std::vector<change_t>& current_changes = changes.back();
        lint value_to_take = cost>purse?(cost<<1):0; // Сколько нужно забрать со счетов
        while(value_to_take)
        {
            if(value_to_take<accounts[active_account_index])
            {
                purse += value_to_take;
                accounts[active_account_index] -= value_to_take;
                current_changes.emplace_back(active_account_index, -value_to_take);
                value_to_take = 0;
            }
            else if(accounts[active_account_index]>=0)
            {
                const lint change = accounts[active_account_index];
                purse += change;
                value_to_take -= change;
                current_changes.emplace_back(active_account_index, -change);
                accounts[active_account_index] = 0;
                ++active_account_index;
            }
            else
            {
                ++active_account_index;
            }
        }
        purse -= cost; // тратим деньги из кассы
    }
    print_changes(std::cout, total_buys, accounts_initial, changes);
}
1
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
08.09.2018, 01:11
Цитата Сообщение от RamzezUA Посмотреть сообщение
Смотря как смотреть на задачу.
Задача вообще смахивает на какой-то гугло-перевод. Банковский счет - учетная запись, номер прекращения - номер окончания - номер завершения...

Добавлено через 2 минуты
Цитата Сообщение от New man Посмотреть сообщение
Если ТС не лень, проверь, пожалуйста.
Если она вдруг зайдет, то ему потом придется ее объяснять
0
1 / 1 / 0
Регистрация: 18.09.2014
Сообщений: 70
08.09.2018, 01:18  [ТС]
New man
За упоротость спасибо, но результат тот же) 8/10, последние 2 - wrong result

nonedark2008
Не прийдется, не зашла
0
309 / 221 / 74
Регистрация: 23.05.2011
Сообщений: 981
08.09.2018, 01:33
Видимо, либо условие неправильное, либо предполагается в качестве целых чисел использовать длинную арифметику.
0
1 / 1 / 0
Регистрация: 18.09.2014
Сообщений: 70
08.09.2018, 01:37  [ТС]
New man, вот как раз в том то и вопрос, что эму то и не нравиться, но пока я на этот вопрос не имею ответа(
0
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,532
Записей в блоге: 1
08.09.2018, 02:34
ну в условии нет вообще ничего об ограничениях на данные. Обычно так не поступают.
Нужна длинная арифметика или не нужна обычно сразу понятно из условия, в котором даны максимумы данных или что-то подобное. Где гарантия, что там файл не на 10 терабайт из сороказначных чисел?
0
Фрилансер
 Аватар для Black Fregat
3709 / 2083 / 567
Регистрация: 31.05.2009
Сообщений: 6,683
08.09.2018, 05:32
RamzezUA, я пока вижу единственное слабое место: если сумма покупки будет слишком велика, то вычисление dbl_purchase может привести к переполнению
0
1 / 1 / 0
Регистрация: 18.09.2014
Сообщений: 70
08.09.2018, 12:59  [ТС]
Black Fregat, Хм, как вариант, но не понятно какой у них размер типов, ведь с условиями о 4х байтах, у меня другие задачи проходили с простым интом
0
Фрилансер
 Аватар для Black Fregat
3709 / 2083 / 567
Регистрация: 31.05.2009
Сообщений: 6,683
08.09.2018, 13:52
Я просто пока больше не вижу возможных проблем
0
1 / 1 / 0
Регистрация: 18.09.2014
Сообщений: 70
08.09.2018, 17:23  [ТС]
Black Fregat, Спасибо за помощь, попробую еще что подумать, если пройдет, выкину ответ сюда, а если нет, значит не судьба мне туда даже пытаться идти)
0
309 / 221 / 74
Регистрация: 23.05.2011
Сообщений: 981
09.09.2018, 20:24
RamzezUA, а там на питоне сдать нельзя?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
09.09.2018, 20:24
Помогаю со студенческими работами здесь

Задача не проходит тест
Добрый день. Есть такая простая задача. /* Нужно добавить в программу новую функциональность Задача: У каждой кошки есть имя и...

Задача не проходит тест
Здравствуйте! Нашел задачу и попробовал решить и вроде бы работает, и тесты все проходит, но один тест не дает покоя выводит на единицу...

Задача не проходит по времени
Доброго времени суток, есть вот такая задача: И мое решения: std::string toB(int n) { std::string ret = &quot;&quot;; while...

Задача не проходит по времени 2 теста
Решаю задачу на informatics(да, сириус...) Подсчитайте количество натуральных делителей числа x (включая 1 и само число; x&lt;2*10**9 ). ...

acm.timus не проходит задача
ССылка на задачу Текст задачи Исходные данные Входной поток содержит набор целых чисел Ai (0 ≤ Ai ≤ 1018), отделённых...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Символьное дифференцирование
igorrr37 13.02.2026
/ * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru