{ }codelper
値型と参照型P0382

全部出るか一つも出ないかの自動販売機

自動販売機に飲み物が k 種類あり、i 番の飲み物は在庫が s_i 個、値段が p_i ウォンである。
注文 q 件を与えられた順に処理する。
一つの注文は、入れたお金 c ウォンと、選んだ飲み物の番号 t 個からなる。
一つの注文で同じ番号を何度も選ぶことができる。
選んだ順に一つずつ取り出す。
一つ取り出すと、その飲み物の在庫が 1 減り、残りのお金がその値段だけ減り、自動販売機の売上がその値段だけ増える。
取り出そうとする飲み物の在庫が 0 であるか、残りのお金がその値段より少なければ、その注文はまるごと取り消される。
取り消されると、在庫と売上はその注文を始める前に戻る。
注文ごとに一行ずつ、最後まで取り出せたなら ok と残りのお金を、取り消されたなら fail と、取り出せなかった飲み物がその注文で何番目に選んだものかを出力せよ。
すべての注文を処理した後、一行に 1 番から k 番までの飲み物の在庫を、その次の行に売上を出力せよ。
最初の売上は 0 ウォンである。
在庫と売上を一つの構造体にまとめ、注文ごとにその構造体をコピーしてコピーの上で取り出してみて、最後まで取り出せたらコピーで上書きして解いてみよう。

入力
一行目に k と q が空白一つで区切られて与えられる。
二行目に s_1 から s_k まで、三行目に p_1 から p_k までが空白一つで区切られて与えられる。
続く q 行には各行に c、t、そして選んだ飲み物の番号 t 個が空白一つで区切られて与えられる。
1 ≤ k ≤ 8、1 ≤ q ≤ 1000、0 ≤ s_i ≤ 20、1 ≤ p_i ≤ 1000、0 ≤ c ≤ 20000、1 ≤ t ≤ 20、飲み物の番号は 1 以上 k 以下
出力
q + 2 行。
注文ごとに "ok 残りのお金" または "fail 順番" を空白一つで区切って書く。
順番は 1 から数える。
その次の行に在庫 k 個を空白一つで区切って書き、最後の行に売上を書く
例 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
例 2 · stdin
1 2
3
400
1000 3 1 1 1
800 2 1 1
stdout
fail 3
ok 0
1
800
main.py
入力(stdin)

実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。

$ 準備完了

コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。

ほかの言語では？言語別の解答を見る · 3 言語の解答

この問題は C・C++・C# だけを受け付けます。
代入するとデータがまるごとコピーされる値型の構造体を自分で作れるのがこの三つで、Python・JavaScript・TypeScript・Java のオブジェクトと Craykon の 辞書() は、代入すると同じものを一緒に指す参照です。
自動販売機の状態（在庫の配列と売上）を構造体 Machine 一つにまとめ、注文ごとに Machine trial = m; でコピーを作って、そこから取り出してみます。
最後までできたら m = trial; で上書きし、取り消しなら trial を捨てるだけなので、元に戻すコードがありません。
構造体の代入がどこまでコピーするかは、メンバーの型で決まります。
C は構造体の中の配列 int stock[8] を要素までコピーします（配列同士は = で代入できませんが、構造体に入っていれば一緒にコピーされます）。
C++ の vector<int> stock メンバーも要素までコピーされます。
C# の struct はフィールドの値をコピーしますが、int[] フィールドの値は配列を指す参照です。
そこで C# の解答は Copy() メソッドの中で (int[])Stock.Clone() で配列を新しく作ります。
罠その一：C# で Machine trial = m; だけだと、Sales は別々ですが Stock 配列は共有されます。
一つ目の例の二番目の注文が取り消されても 1 番の飲み物の在庫が 0 のまま残り、三番目の注文が fail 1 になって売上は 800 になります。
罠その二：C で在庫を int *stock（malloc で確保した場所）にすると、C# と同じようにアドレスだけがコピーされて、同じ間違った答えになります。
罠その三：C の Machine *trial = &m; や C++ の Machine& trial = m; はコピーではなく、m を指す別の名前です。
取り消しても在庫も売上もそのまま残るので、一つ目の例の三番目の注文が fail 1 になります。
罠その四：取り出す関数が bool take(Machine t, int x, int money) のように構造体を値で受け取ると、関数の中のコピーだけが変わります。
一つ目の例では在庫が減らないので二番目の注文が fail 3 になり、最後に 2 1 と 0 が出ます。
その場で変えるには、C は Machine *t で受け取って take(&trial, …) と呼び、C++ は Machine& t で受け取り、C# は構造体のメソッドにするか ref Machine t で受け取ります。

C#Main.cs · 66 行
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 行
#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 行
#include <stdio.h> #define MAXK 8#define MAXT 20 typedef 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;}