A monthly household ledger has a budget limit for each category, and spending is written down one line at a time.
The first line gives c, the number of categories with a budget, and each of the next c lines gives "category limit".
Then comes the number of records n, and each of the next n lines gives a record "category amount".
A positive amount is money spent, a negative amount is money refunded, and the amount may also be 0.
A category without a budget may still appear in the records; its limit is 0.
Each category's spending starts at 0 and adds that category's amounts in order.
For each record print one line "runningTotal categoryTotal".
The running total is the sum of the amounts of all records so far, and the category total is that category's spending after adding this record.
If the category's spending was at most its limit just before this record and is greater than the limit after adding it, append one space and "over" to the end of that line.
A record that adds spending while the category is already above its limit does not get over.
If a refund brings the category back to its limit or below and it later goes above the limit again, that record gets over again.
After all records, print one line "category spent limit left" for every category that has a budget or appears in the records, in dictionary order of names.
left is the limit minus the spending, and it may be negative.
Dictionary order compares names letter by letter from the start, and the earlier letter comes first; if one name is the beginning of the other, the shorter one comes first.
Input
1 ≤ c ≤ 100, 1 ≤ n ≤ 3000, 0 ≤ limit ≤ 10^12, −10^9 ≤ amount ≤ 10^9 (integers). Category names are 1 to 10 lowercase English letters, the budget lines have distinct names, and at most 100 categories appear in total
Output
n lines "runningTotal categoryTotal" (with " over" at the end at the moment it goes over), then one line per category in dictionary order: "category spent limit left"
Example 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
Example 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
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 · 8 languages
This problem keeps two running sums at once: one overall, and one per category in a map. The overall total reaches 3,000 × 10^9 = 3 × 10^12, which overflows C int and Java/C# int. Use C long long and Java/C# long; Python, JS, TS and Craykon are fine as they are (3 × 10^12 is below 2^53). Updating the map means "start from 0 if missing": Python spent.get(name, 0), JS/TS spent.get(name) ?? 0, Java getOrDefault(name, 0L), C# GetValueOrDefault(name, 0), C++ spent[name] (creates a 0 if missing), and in Craykon run if (!spent.Contains(name)) { spent[name] = 0; } first (Korean 있나). For the limit map in C++, reading limit[name] adds the missing category to the map, so ask count(name) first. C has no map, so it searches a table of names in order. The final table walks the keys in order: Python sorted(spent), JS/TS [...spent.keys()].sort(), Java TreeMap, C# SortedDictionary (with StringComparer.Ordinal), C++ std::map (always sorted), Craykon Keys then Sort() (Korean 열쇠목록, 정렬), C qsort with strcmp. Trap one: a JS Map, a Python dict and a Craykon dict iterate in insertion order, so without sorting the rows come out in budget-line order. Trap two: reading a category without a budget as Python limit[name] raises KeyError, and Java long cap = limit.get(name) unboxes null and throws NullPointerException. Trap three: over marks "the moment it goes over", not "while it is over", so the test is before <= cap && after > cap. Trap four: an int running total wraps to a negative number once it passes about 2.1 billion.
Pythonmain.py · 29 lines
import syslines = 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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
c = Console.ReadLine().ToNumber();limit = Dict();spent = Dict();for (i = 0; i < c; i++){ p = Console.ReadLine().Trim().Split(); limit[p[0]] = p[1].ToNumber(); spent[p[0]] = 0;}n = Console.ReadLine().ToNumber();total = 0;for (i = 0; i < n; i++){ p = Console.ReadLine().Trim().Split(); name = p[0]; amount = p[1].ToNumber(); // 없는 열쇠를 읽으면 멈추니 먼저 넣어 둔다(예산을 정하지 않은 항목은 한도 0) if (!limit.Contains(name)) { limit[name] = 0; } if (!spent.Contains(name)) { spent[name] = 0; } before = spent[name]; spent[name] = before + amount; total = total + amount; row = total + " " + spent[name]; if (before <= limit[name] && spent[name] > limit[name]) { row = row + " over"; } Console.WriteLine(row);}// 열쇠목록은 넣은 차례라 사전 순으로 정렬한다names = spent.Keys;names.Sort();foreach (name in names){ Console.WriteLine(name + " " + spent[name] + " " + limit[name] + " " + (limit[name] - spent[name]));}