{ }codelper
累計辞書の更新キー順P0178

項目別の予算帳

一か月の家計簿に項目ごとの予算上限があり、使ったお金が一行ずつ書かれる。
一行目に予算を決めた項目の数 c が、続く c 行に「項目 上限」が与えられる。
続いて記録の数 n が、続く n 行に記録「項目 金額」が与えられる。
金額が正なら使ったお金、負なら払い戻されたお金（返金）で、0 のこともある。
予算を決めていない項目も記録に出てくることがあり、そのような項目の上限は 0 である。
項目ごとの使ったお金は 0 から始まり、その項目の金額を順に足した値である。
記録ごとに一行に「全体累計 項目累計」を出力せよ。
全体累計はここまでのすべての記録の金額の和で、項目累計はこの記録を足したあとのその項目の使ったお金である。
この記録の直前にはその項目の使ったお金が上限以下だったのに、この記録を足したあと上限より大きくなったなら、その行の最後に空白一つと「over」を付ける。
すでに上限より大きい状態でさらに使った記録には over を付けない。
返金で上限以下に戻ったあと再び上限を超えたら、その記録にまた over を付ける。
すべての記録のあとで、予算を決めた項目と記録に出た項目をすべて、名前の辞書順に一行ずつ「項目 使ったお金 上限 残り」として出力せよ。
残りは上限から使ったお金を引いた値で、負になることもある。
辞書順は先頭の文字から比べてアルファベットが前のほうが先で、一方がもう一方の先頭部分なら短いほうが先である。

入力
1 ≤ c ≤ 100、1 ≤ n ≤ 3000、0 ≤ 上限 ≤ 10^12、−10^9 ≤ 金額 ≤ 10^9（整数）。
項目名は英小文字 1 ～ 10 文字で、予算行の名前はすべて異なり、出てくる項目は合わせて 100 個以下
出力
n 行の「全体累計 項目累計」（超えた瞬間には最後に「 over」）、続いて項目ごとに辞書順で「項目 使ったお金 上限 残り」
例 1 · stdin
3
food 50000
rent 300000
book 20000
6
food 30000
rent 300000
food 25000
game 5000
food -10000
food 6000
stdout
30000 30000
330000 300000
355000 55000 over
360000 5000 over
350000 45000
356000 51000 over
book 0 20000 20000
food 51000 50000 -1000
game 5000 0 -5000
rent 300000 300000 0
例 2 · stdin
1
bus 0
4
bus 0
bus -500
bus 500
bus 1
stdout
0 0
-500 -500
0 0
1 1 over
bus 1 0 -1
main.py
入力(stdin)

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

$ 準備完了

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

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

累計を二つ（全体に一つ、項目ごとに辞書で一つ）同時に回す問題です。
全体累計は 3,000 × 10億 = 3兆 まで行くので、C の int、Java・C# の int ではあふれます。
C は long long、Java・C# は long を使い、Python・JS・TS・Craykon はそのままで大丈夫です（3兆は 2^53 未満です）。
辞書の更新は「なければ 0 から」です：Python spent.get(name, 0)、JS・TS spent.get(name) ?? 0、Java getOrDefault(name, 0L)、C# GetValueOrDefault(name, 0)、C++ spent[name]（なければ 0 を作ります）、Craykon は先に もし (!spent.含む(name)) { spent[name] = 0; }（韓国語 있나）を実行します。
上限の辞書は C++ で limit[name] と読むとない項目が辞書に新しくできるので、count(name) で先に確かめます。
C には辞書がないので名前の表を順に探します。
最後の表はキーの順に回ります：Python sorted(spent)、JS・TS [...spent.keys()].sort()、Java TreeMap、C# SortedDictionary（StringComparer.Ordinal）、C++ std::map（いつも整列済み）、Craykon は キー一覧 を 並べ替え()（韓国語 열쇠목록・정렬）、C は qsort と strcmp。
落とし穴その一：JS の Map・Python の dict・Craykon の辞書は入れた順に回るので、並べ替えを抜くと予算行の順に出てしまいます。
落とし穴その二：予算を決めていない項目を Python limit[name] で読むと KeyError、Java long cap = limit.get(name) は null をほどこうとして NullPointerException です。
落とし穴その三：over は「超えている間」ではなく「超えた瞬間」なので before <= cap && after > cap です。
落とし穴その四：全体累計を int にすると約 21 億を超えた瞬間に負の数に回ります。

Pythonmain.py · 29 行
import sys lines = sys.stdin.read().split("\n")c = int(lines[0])limit = {}spent = {}for line in lines[1:1 + c]:    name, cap = line.split()    limit[name] = int(cap)    spent[name] = 0n = int(lines[1 + c])total = 0out = []for line in lines[2 + c:2 + c + n]:    name, amount = line.split()    amount = int(amount)    cap = limit.get(name, 0)            # 예산을 정하지 않은 항목은 한도 0    before = spent.get(name, 0)    spent[name] = before + amount    total += amount                     # 전체 누적    row = f"{total} {spent[name]}"    if before <= cap < spent[name]:     # 한도 안에서 밖으로 넘어간 순간만        row += " over"    out.append(row) for name in sorted(spent):              # 열쇠를 사전 순으로    cap = limit.get(name, 0)    out.append(f"{name} {spent[name]} {cap} {cap - spent[name]}")print("\n".join(out))
JavaScriptmain.js · 30 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const c = Number(lines[0]);const limit = new Map();const spent = new Map();for (const line of lines.slice(1, 1 + c)) {  const [name, cap] = line.trim().split(" ");  limit.set(name, Number(cap));  spent.set(name, 0);}const n = Number(lines[1 + c]);let total = 0;const out = [];for (const line of lines.slice(2 + c, 2 + c + n)) {  const [name, a] = line.trim().split(" ");  const amount = Number(a);  const cap = limit.get(name) ?? 0; // 예산을 정하지 않은 항목은 한도 0  const before = spent.get(name) ?? 0;  const after = before + amount;  spent.set(name, after);  total += amount;  out.push(`${total} ${after}` + (before <= cap && after > cap ? " over" : ""));} // Map은 넣은 차례를 지키므로 열쇠를 따로 정렬해야 사전 순이 된다for (const name of [...spent.keys()].sort()) {  const cap = limit.get(name) ?? 0;  const s = spent.get(name) ?? 0;  out.push(`${name} ${s} ${cap} ${cap - s}`);}console.log(out.join("\n"));
TypeScriptmain.ts · 31 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const c = Number(lines[0]);const limit = new Map<string, number>();const spent = new Map<string, number>();for (const line of lines.slice(1, 1 + c)) {  const [name, cap] = line.trim().split(" ");  limit.set(name, Number(cap));  spent.set(name, 0);}const n = Number(lines[1 + c]);let total = 0;const out: string[] = [];for (const line of lines.slice(2 + c, 2 + c + n)) {  const [name, a] = line.trim().split(" ");  const amount = Number(a);  const cap = limit.get(name) ?? 0; // 예산을 정하지 않은 항목은 한도 0  const before = spent.get(name) ?? 0;  const after = before + amount;  spent.set(name, after);  total += amount;  out.push(`${total} ${after}` + (before <= cap && after > cap ? " over" : ""));} // Map은 넣은 차례를 지키므로 열쇠를 따로 정렬해야 사전 순이 된다for (const name of [...spent.keys()].sort()) {  const cap = limit.get(name) ?? 0;  const s = spent.get(name) ?? 0;  out.push(`${name} ${s} ${cap} ${cap - s}`);}console.log(out.join("\n"));
JavaMain.java · 37 行
import java.io.*;import java.util.*; public class Main {    public static void main(String[] args) throws IOException {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        int c = Integer.parseInt(br.readLine().trim());        Map<String, Long> limit = new HashMap<>();        Map<String, Long> spent = new TreeMap<>(); // TreeMap은 열쇠를 사전 순으로 지킨다        for (int i = 0; i < c; i++) {            String[] p = br.readLine().trim().split(" ");            limit.put(p[0], Long.parseLong(p[1]));            spent.put(p[0], 0L);        }        int n = Integer.parseInt(br.readLine().trim());        long total = 0; // 3,000 × 10억 = 3조라 int로는 넘친다        StringBuilder out = new StringBuilder();        for (int i = 0; i < n; i++) {            String[] p = br.readLine().trim().split(" ");            long amount = Long.parseLong(p[1]);            long cap = limit.getOrDefault(p[0], 0L); // 예산을 정하지 않은 항목은 한도 0            long before = spent.getOrDefault(p[0], 0L);            long after = before + amount;            spent.put(p[0], after);            total += amount;            out.append(total).append(' ').append(after);            if (before <= cap && after > cap) out.append(" over");            out.append('\n');        }        for (Map.Entry<String, Long> e : spent.entrySet()) {            long cap = limit.getOrDefault(e.getKey(), 0L);            out.append(e.getKey()).append(' ').append(e.getValue()).append(' ')               .append(cap).append(' ').append(cap - e.getValue()).append('\n');        }        System.out.print(out);    }}
C#Main.cs · 41 行
using System;using System.Collections.Generic;using System.Text; class Program{    static void Main()    {        int c = int.Parse(Console.ReadLine().Trim());        var limit = new Dictionary<string, long>();        var spent = new SortedDictionary<string, long>(StringComparer.Ordinal); // 열쇠를 글자 코드 순으로        for (int i = 0; i < c; i++)        {            string[] p = Console.ReadLine().Trim().Split(' ');            limit[p[0]] = long.Parse(p[1]);            spent[p[0]] = 0;        }        int n = int.Parse(Console.ReadLine().Trim());        long total = 0; // 3,000 × 10억 = 3조라 int로는 넘친다        var sb = new StringBuilder();        for (int i = 0; i < n; i++)        {            string[] p = Console.ReadLine().Trim().Split(' ');            long amount = long.Parse(p[1]);            long cap = limit.GetValueOrDefault(p[0], 0); // 예산을 정하지 않은 항목은 한도 0            long before = spent.GetValueOrDefault(p[0], 0);            long after = before + amount;            spent[p[0]] = after;            total += amount;            sb.Append(total).Append(' ').Append(after);            if (before <= cap && after > cap) sb.Append(" over");            sb.Append('\n');        }        foreach (var (name, s) in spent)        {            long cap = limit.GetValueOrDefault(name, 0);            sb.Append($"{name} {s} {cap} {cap - s}\n");        }        Console.Write(sb);    }}
C++main.cpp · 38 行
#include <iostream>#include <map>#include <string> int main() {    std::ios::sync_with_stdio(false);    int c, n;    std::cin >> c;    std::map<std::string, long long> limit;    std::map<std::string, long long> spent; // std::map은 열쇠를 정렬해 둔다    for (int i = 0; i < c; i++) {        std::string name;        long long cap;        std::cin >> name >> cap;        limit[name] = cap;        spent[name] = 0;    }    std::cin >> n;    long long total = 0; // 3,000 × 10억 = 3조라 int로는 넘친다    std::string out;    for (int i = 0; i < n; i++) {        std::string name;        long long amount;        std::cin >> name >> amount;        // count로 먼저 묻는다: limit[name]이라고 읽으면 없는 열쇠가 0으로 새로 생긴다        long long cap = limit.count(name) ? limit[name] : 0;        long long before = spent[name]; // 없으면 []가 0으로 만들어 준다        long long after = before + amount;        spent[name] = after;        total += amount;        out += std::to_string(total) + " " + std::to_string(after) + (before <= cap && after > cap ? " over" : "") + "\n";    }    for (const auto& [name, s] : spent) {        long long cap = limit.count(name) ? limit[name] : 0;        out += name + " " + std::to_string(s) + " " + std::to_string(cap) + " " + std::to_string(cap - s) + "\n";    }    std::cout << out;}
Cmain.c · 50 行
#include <stdio.h>#include <stdlib.h>#include <string.h> /* C에는 사전이 없다: 항목은 많아야 100개라 이름 표를 차례로 찾는다 */typedef struct {    char name[11];    long long limit, spent; /* 3,000 × 10억 = 3조라 int로는 넘친다 */} Item; static Item items[100];static int count = 0; static int find_or_add(const char* name) {    for (int i = 0; i < count; i++)        if (strcmp(items[i].name, name) == 0) return i;    strcpy(items[count].name, name);    items[count].limit = 0; /* 예산을 정하지 않은 항목은 한도 0 */    items[count].spent = 0;    return count++;} static int by_name(const void* a, const void* b) {    return strcmp(((const Item*)a)->name, ((const Item*)b)->name);} int main(void) {    int c, n;    char name[11];    long long x;    scanf("%d", &c);    for (int i = 0; i < c; i++) {        scanf("%10s %lld", name, &x);        items[find_or_add(name)].limit = x;    }    scanf("%d", &n);    long long total = 0;    for (int i = 0; i < n; i++) {        scanf("%10s %lld", name, &x);        Item* it = &items[find_or_add(name)];        long long before = it->spent;        it->spent += x;        total += x;        printf("%lld %lld%s\n", total, it->spent, before <= it->limit && it->spent > it->limit ? " over" : "");    }    qsort(items, count, sizeof items[0], by_name);    for (int i = 0; i < count; i++)        printf("%s %lld %lld %lld\n", items[i].name, items[i].spent, items[i].limit, items[i].limit - items[i].spent);    return 0;}
Craykonmain.cray · 43 行
c = コンソール.行読み().数に();limit = 辞書();spent = 辞書();繰り返す (i = 0; i < c; i++){    p = コンソール.行読み().空白除去().分ける();    limit[p[0]] = p[1].数に();    spent[p[0]] = 0;}n = コンソール.行読み().数に();total = 0;繰り返す (i = 0; i < n; i++){    p = コンソール.行読み().空白除去().分ける();    name = p[0];    amount = p[1].数に();    // 없는 열쇠를 읽으면 멈추니 먼저 넣어 둔다(예산을 정하지 않은 항목은 한도 0)    もし (!limit.含む(name))    {        limit[name] = 0;    }    もし (!spent.含む(name))    {        spent[name] = 0;    }    before = spent[name];    spent[name] = before + amount;    total = total + amount;    row = total + " " + spent[name];    もし (before <= limit[name] && spent[name] > limit[name])    {        row = row + " over";    }    コンソール.書く(row);} // 열쇠목록은 넣은 차례라 사전 순으로 정렬한다names = spent.キー一覧;names.並べ替え();それぞれ (name の中 names){    コンソール.書く(name + " " + spent[name] + " " + limit[name] + " " + (limit[name] - spent[name]));}