At a science fair, a hands-on booth lets students in as one group every time k students who chose that booth have gathered.
You are given n students in the order they arrive, each with a name and the number b of the booth chosen.
When a student arrives, the student joins the end of that booth's waiting line.
As soon as a booth's waiting line has k students, print on one line the booth number, a colon (:), and the names of those k students in the order they lined up, and then empty that booth's waiting line.
Put one space after the colon and between names (for example 30: mina seo).
After all students have arrived, print on one line the word left and the number of students still waiting, separated by one space.
Then, for each booth that has waiting students, print one line in the same form with the booth number and the waiting names in the order they lined up.
The booths go in the order in which each booth number first appeared in the input.
That order does not change even if a group from the booth has already gone in.
Do not print booths that have no waiting students.
Input
The first line has n and k (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 10), and each of the next n lines has a name and a booth number b (1 ≤ b ≤ 1,000,000,000) separated by one space. All numbers are integers given as plain digits, without commas or leading zeros. A name is 1 to 8 lowercase letters, and several students may share a name
Output
One line each time a group goes in, then the left line, then one line for each booth with waiting students (booth numbers as plain digits without commas)
Example 1 · stdin
7 2
mina 30
jun 7
seo 30
dan 7
eli 7
ari 12
bo 30
stdout
30: mina seo
7: jun dan
left 3
30: bo
7: eli
12: ari
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
With the booth number as the key and the list of waiting names as the value, students of the same booth come together. Because the end goes in 'first appeared' order, the order in which a dictionary hands out its keys is where the languages part. Python's dict, the Map of JS and TS, Java's LinkedHashMap and Craykon's Dict() (Keys) go through the keys in the order they were first put in. C#'s Dictionary does not promise an order in its documentation, and neither does C++'s unordered_map, so the solutions keep the booth numbers in a separate list as they first appear and walk that list. C has no dictionary, so search an array of booth numbers from the front and add at the end if it is missing. The order of the array is then the first-appearance order. Trap one: a plain object {} in JS goes through integer-like keys such as 30, 7 and 12 from the smallest, not in insertion order. The last three lines of the example come out as 7: eli, 12: ari, 30: bo. Trap two: Java's HashMap does not remember insertion order. On the example it also gives 7, 12, 30. Trap three: C++'s std::map always goes from the smallest key, which gives the same wrong answer. Trap four: if you delete the key when a group goes in (Python del waiting[b]), the booth is put in again at the very end when it comes back. Booth 30 in the example appeared first, yet 30: bo slides to the last line. Keep the key and only replace the value with an empty list (Python waiting[b] = [], JS names.length = 0, Java names.clear(), C# names.Clear(), C++ names.clear(), Craykon waiting[b] = []).
Pythonmain.py · 15 lines
n, k = map(int, input().split())waiting = {} # 부스 번호 → 기다리는 이름들. dict는 열쇠를 처음 넣은 차례를 기억한다for _ in range(n): name, b = input().split() b = int(b) if b not in waiting: waiting[b] = [] waiting[b].append(name) if len(waiting[b]) == k: print(f"{b}: {' '.join(waiting[b])}") waiting[b] = [] # 열쇠는 지우지 않고 값만 비운다: 처음 나온 차례가 남는다print("left", sum(len(names) for names in waiting.values()))for b, names in waiting.items(): if names: print(f"{b}: {' '.join(names)}")
JavaScriptmain.js · 23 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, k] = lines[0].split(" ").map(Number);// Map은 열쇠를 처음 넣은 차례대로 돈다(보통 객체 {}는 정수 열쇠를 작은 것부터 돈다)const waiting = new Map();const out = [];for (let i = 1; i <= n; i++) { const [name, t] = lines[i].split(" "); const b = Number(t); if (!waiting.has(b)) waiting.set(b, []); const names = waiting.get(b); names.push(name); if (names.length === k) { out.push(`${b}: ${names.join(" ")}`); names.length = 0; // 열쇠는 지우지 않고 값만 비운다 }}let left = 0;for (const names of waiting.values()) left += names.length;out.push(`left ${left}`);for (const [b, names] of waiting) { if (names.length > 0) out.push(`${b}: ${names.join(" ")}`);}console.log(out.join("\n"));
TypeScriptmain.ts · 28 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, k] = lines[0].split(" ").map(Number);// Map은 열쇠를 처음 넣은 차례대로 돈다(보통 객체 {}는 정수 열쇠를 작은 것부터 돈다)const waiting = new Map<number, string[]>();const out: string[] = [];for (let i = 1; i <= n; i++) { const [name, t] = lines[i].split(" "); const b: number = Number(t); let names: string[] | undefined = waiting.get(b); if (names === undefined) { names = []; waiting.set(b, names); } names.push(name); if (names.length === k) { out.push(`${b}: ${names.join(" ")}`); names.length = 0; // 열쇠는 지우지 않고 값만 비운다 }}let left = 0;for (const names of waiting.values()) left += names.length;out.push(`left ${left}`);for (const [b, names] of waiting) { if (names.length > 0) out.push(`${b}: ${names.join(" ")}`);}console.log(out.join("\n"));
JavaMain.java · 37 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.LinkedHashMap;import java.util.List;import java.util.Map;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] first = br.readLine().split(" "); int n = Integer.parseInt(first[0]), k = Integer.parseInt(first[1]); // LinkedHashMap은 열쇠를 처음 넣은 차례대로 돈다(HashMap은 차례를 지키지 않는다) Map<Integer, List<String>> waiting = new LinkedHashMap<>(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { String[] parts = br.readLine().split(" "); int b = Integer.parseInt(parts[1]); List<String> names = waiting.computeIfAbsent(b, key -> new ArrayList<>()); names.add(parts[0]); if (names.size() == k) { sb.append(b).append(": ").append(String.join(" ", names)).append('\n'); names.clear(); // 열쇠는 지우지 않고 값만 비운다 } } int left = 0; for (List<String> names : waiting.values()) left += names.size(); sb.append("left ").append(left).append('\n'); for (Map.Entry<Integer, List<String>> e : waiting.entrySet()) { if (!e.getValue().isEmpty()) { sb.append(e.getKey()).append(": ").append(String.join(" ", e.getValue())).append('\n'); } } System.out.print(sb); }}
C#Main.cs · 43 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] first = Console.ReadLine()!.Split(' '); int n = int.Parse(first[0]), k = int.Parse(first[1]); var waiting = new Dictionary<int, List<string>>(); var order = new List<int>(); // Dictionary는 도는 차례를 약속하지 않으므로 처음 나온 차례를 따로 적는다 var sb = new StringBuilder(); for (int i = 0; i < n; i++) { string[] parts = Console.ReadLine()!.Split(' '); int b = int.Parse(parts[1]); if (!waiting.TryGetValue(b, out List<string>? names)) { names = new List<string>(); waiting[b] = names; order.Add(b); } names.Add(parts[0]); if (names.Count == k) { sb.Append(b).Append(": ").Append(string.Join(" ", names)).Append('\n'); names.Clear(); // 열쇠는 지우지 않고 값만 비운다 } } int left = 0; foreach (int b in order) left += waiting[b].Count; sb.Append("left ").Append(left).Append('\n'); foreach (int b in order) { if (waiting[b].Count > 0) { sb.Append(b).Append(": ").Append(string.Join(" ", waiting[b])).Append('\n'); } } Console.Write(sb); }}
C++main.cpp · 39 lines
#include <iostream>#include <string>#include <unordered_map>#include <vector>using namespace std;static void printGroup(int b, const vector<string>& names) { cout << b << ':'; for (const string& s : names) cout << ' ' << s; cout << '\n';}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; unordered_map<int, vector<string>> waiting; vector<int> order; // map은 열쇠 크기순, unordered_map은 제멋대로 돌므로 처음 나온 차례를 따로 적는다 for (int i = 0; i < n; i++) { string name; int b; cin >> name >> b; if (waiting.find(b) == waiting.end()) order.push_back(b); vector<string>& names = waiting[b]; names.push_back(name); if ((int)names.size() == k) { printGroup(b, names); names.clear(); // 열쇠는 지우지 않고 값만 비운다 } } size_t left = 0; for (int b : order) left += waiting[b].size(); cout << "left " << left << '\n'; for (int b : order) { if (!waiting[b].empty()) printGroup(b, waiting[b]); } return 0;}
Cmain.c · 43 lines
#include <stdio.h>#include <string.h>/* C에는 사전이 없다: 부스 번호를 처음 나온 차례대로 배열에 적고 앞에서부터 찾는다 */int booth[1000]; /* booth[g]: g번째로 처음 나온 부스 번호 */int count[1000]; /* 그 부스에서 기다리는 사람 수 */char names[1000][10][9]; /* 그 부스에서 기다리는 이름들(k ≤ 10, 이름 ≤ 8글자) */static void print_group(int g) { printf("%d:", booth[g]); for (int j = 0; j < count[g]; j++) printf(" %s", names[g][j]); printf("\n");}int main(void) { int n, k, groups = 0; if (scanf("%d %d", &n, &k) != 2) return 0; for (int i = 0; i < n; i++) { char name[9]; int b; if (scanf("%8s %d", name, &b) != 2) return 0; int g = 0; while (g < groups && booth[g] != b) g++; if (g == groups) { booth[groups] = b; count[groups] = 0; groups++; } strcpy(names[g][count[g]], name); count[g]++; if (count[g] == k) { print_group(g); count[g] = 0; /* 자리는 그대로 두고 수만 0으로 */ } } int left = 0; for (int g = 0; g < groups; g++) left += count[g]; printf("left %d\n", left); for (int g = 0; g < groups; g++) { if (count[g] > 0) print_group(g); } return 0;}
Craykonmain.cray · 32 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];k = 첫줄[1];waiting = Dict(); // 부스 번호 → 기다리는 이름들. 사전은 열쇠를 처음 넣은 차례를 기억한다for (i = 0; i < n; i++){ parts = Console.ReadLine().Split(); b = parts[1].ToNumber(); if (!waiting.Contains(b)) { waiting[b] = []; } waiting[b].Add(parts[0]); if (waiting[b].Count == k) { Console.WriteLine(b + ": " + waiting[b].Join(" ")); waiting[b] = []; // 열쇠는 빼지 않고 값만 비운다 }}left = 0;foreach (b in waiting.Keys){ left += waiting[b].Count;}Console.WriteLine("left " + left);foreach (b in waiting.Keys){ if (waiting[b].Count > 0) { Console.WriteLine(b + ": " + waiting[b].Join(" ")); }}