A vending machine holds k kinds of drinks; drink i has s_i in stock and costs p_i won.
q orders are handled in the given order.
One order consists of the inserted money c won and t chosen drink numbers.
The same number may be chosen several times in one order.
The drinks are taken out one at a time in the order chosen.
Taking one out lowers that drink's stock by 1, lowers the remaining money by its price, and raises the machine's sales by its price.
If the stock of the drink to take out is 0, or the remaining money is less than its price, the whole order is cancelled.
When an order is cancelled, the stock and the sales go back to what they were before that order began.
For each order print one line: ok and the remaining money if everything was taken out, or fail and which pick of that order could not be taken out.
After all orders, print the stock of drinks 1 to k on one line and the sales on the next line.
The sales start at 0 won.
Bundle the stock and the sales in one struct, copy the struct for each order, try the order on the copy, and overwrite the original with the copy when everything was taken out.
Input
The first line has k and q separated by one space. The second line has s_1 to s_k and the third line has p_1 to p_k, separated by single spaces. Each of the next q lines has c, t and then the t chosen drink numbers, separated by single spaces. 1 ≤ k ≤ 8, 1 ≤ q ≤ 1000, 0 ≤ s_i ≤ 20, 1 ≤ p_i ≤ 1000, 0 ≤ c ≤ 20000, 1 ≤ t ≤ 20, drink numbers are between 1 and k
Output
q + 2 lines. For each order print "ok remaining-money" or "fail position" separated by one space. Positions are counted from 1. On the next line print the k stock values separated by single spaces, and on the last line print the sales
Example 1 · stdin
2 3
2 1
300 500
1000 2 1 2
1000 3 1 1 2
500 1 1
stdout
ok 200
fail 2
ok 200
0 0
1100
Example 2 · stdin
1 2
3
400
1000 3 1 1 1
800 2 1 1
stdout
fail 3
ok 0
1
800
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 3 languages
This problem accepts only C, C++ and C#. Those three let you define your own value-type struct whose data is copied whole on assignment; objects in Python, JavaScript, TypeScript and Java, and Craykon's Dict(), are references that point to the same thing after assignment. Bundle the machine's state (the stock array and the sales) into one struct Machine, and for every order make a copy with Machine trial = m; and take the drinks out of the copy. If everything works, overwrite with m = trial;; if the order is cancelled, just throw trial away, so there is no undo code at all. How far a struct assignment copies depends on the member types. C copies an array inside a struct, int stock[8], element by element (arrays cannot be assigned to each other with =, but inside a struct they are copied along). A C++ vector<int> stock member is also copied with its elements. A C# struct copies its field values, but the value of an int[] field is a reference to the array. So the C# solution creates a new array with (int[])Stock.Clone() in a Copy() method. Trap one: in C#, with just Machine trial = m; the Sales are separate but the Stock array is shared. In the first example the stock of drink 1 stays 0 even though the second order is cancelled, so the third order becomes fail 1 and the sales come out as 800. Trap two: in C, if the stock is an int *stock (memory from malloc), only the address is copied just as in C#, and the same wrong answer comes out. Trap three: Machine *trial = &m; in C or Machine& trial = m; in C++ is not a copy but another name for m. Both the stock and the sales stay changed after a cancellation, so the third order of the first example becomes fail 1. Trap four: if the taking function receives the struct by value, as in bool take(Machine t, int x, int money), only the copy inside the function changes. In the first example the stock never goes down, so the second order becomes fail 3 and the last lines are 2 1 and 0. To change it in place, C takes Machine *t and is called as take(&trial, …), C++ takes Machine& t, and C# makes it a method of the struct or takes ref Machine t.
C#Main.cs · 66 lines
using System;using System.Text;struct Machine{ public int[] Stock; // 배열은 참조다: 구조체를 대입해도 배열 자체는 복사되지 않는다 public int Sales; // 배열까지 새로 만든 복사본 public Machine Copy() { Machine c = this; c.Stock = (int[])Stock.Clone(); return c; } // 메서드는 자기 자신(this)을 제자리에서 바꾼다 public bool Take(int x, int money, int[] price) { if (Stock[x] == 0 || money < price[x]) return false; Stock[x]--; Sales += price[x]; return true; }}class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); int pos = 0; int k = int.Parse(data[pos++]), q = int.Parse(data[pos++]); var m = new Machine { Stock = new int[k], Sales = 0 }; var price = new int[k]; for (int i = 0; i < k; i++) m.Stock[i] = int.Parse(data[pos++]); for (int i = 0; i < k; i++) price[i] = int.Parse(data[pos++]); var sb = new StringBuilder(); for (int o = 0; o < q; o++) { int money = int.Parse(data[pos++]), t = int.Parse(data[pos++]); Machine trial = m.Copy(); int failed = 0; for (int j = 0; j < t; j++) { int x = int.Parse(data[pos + j]) - 1; if (!trial.Take(x, money, price)) { failed = j + 1; break; } money -= price[x]; } pos += t; if (failed > 0) { sb.Append("fail ").Append(failed).Append('\n'); } else { m = trial; sb.Append("ok ").Append(money).Append('\n'); } } sb.Append(string.Join(" ", m.Stock)).Append('\n').Append(m.Sales).Append('\n'); Console.Write(sb); }}
C++main.cpp · 53 lines
#include <iostream>#include <vector>using namespace std;struct Machine { vector<int> stock; // vector 멤버는 구조체를 대입할 때 원소까지 복사된다 int sales = 0;};vector<int> price;// 제자리에서 바꾸려고 참조로 받는다bool take(Machine& t, int x, int money) { if (t.stock[x] == 0 || money < price[x]) return false; t.stock[x]--; t.sales += price[x]; return true;}int main() { int k, q; cin >> k >> q; Machine m; m.stock.resize(k); price.resize(k); for (int& s : m.stock) cin >> s; for (int& p : price) cin >> p; for (int o = 0; o < q; o++) { int money, t; cin >> money >> t; vector<int> picks(t); for (int& x : picks) cin >> x; Machine trial = m; // 재고와 매출이 모두 복사된다 int failed = 0; for (int j = 0; j < t; j++) { int x = picks[j] - 1; if (!take(trial, x, money)) { failed = j + 1; break; } money -= price[x]; } if (failed) { cout << "fail " << failed << '\n'; } else { m = trial; cout << "ok " << money << '\n'; } } for (int i = 0; i < k; i++) cout << (i ? " " : "") << m.stock[i]; cout << '\n' << m.sales << '\n'; return 0;}
Cmain.c · 51 lines
#include <stdio.h>#define MAXK 8#define MAXT 20typedef struct { int stock[MAXK]; // 구조체 안의 배열은 구조체를 대입할 때 통째로 복사된다 int sales;} Machine;int price[MAXK];// 제자리에서 바꾸려고 포인터로 받는다int take(Machine *t, int x, int money) { if (t->stock[x] == 0 || money < price[x]) return 0; t->stock[x]--; t->sales += price[x]; return 1;}int main(void) { int k, q; if (scanf("%d %d", &k, &q) != 2) return 0; Machine m = {{0}, 0}; for (int i = 0; i < k; i++) scanf("%d", &m.stock[i]); for (int i = 0; i < k; i++) scanf("%d", &price[i]); for (int o = 0; o < q; o++) { int money, t, picks[MAXT]; scanf("%d %d", &money, &t); for (int j = 0; j < t; j++) scanf("%d", &picks[j]); Machine trial = m; // 재고 배열과 매출이 모두 복사된다 int failed = 0; for (int j = 0; j < t; j++) { int x = picks[j] - 1; if (!take(&trial, x, money)) { failed = j + 1; break; } money -= price[x]; } if (failed) { printf("fail %d\n", failed); } else { m = trial; printf("ok %d\n", money); } } for (int i = 0; i < k; i++) printf(i ? " %d" : "%d", m.stock[i]); printf("\n%d\n", m.sales); return 0;}