A school entrance has an umbrella stand that starts with u umbrellas.
You are given n events in the order they happen.
want name means the person with that name comes to borrow an umbrella. If the stand has an umbrella, they take one right away; if not, they join the back of the waiting line.
back means one borrowed umbrella comes back. If anyone is waiting, the person who came earliest among them takes that umbrella right away and leaves the line. If nobody is waiting, the umbrella goes into the stand.
Print one line per event. If someone took an umbrella because of that event, print that person's name; if nobody did, print -.
On the last line print the number of people still waiting and the number of umbrellas in the stand, separated by one space.
Input
The first line has n and u separated by one space. Each of the next n lines has one event. 1 ≤ n ≤ 9,000, 0 ≤ u ≤ 9,000. A name is 1 to 10 lowercase English letters, and different people may share a name. back is given only when at least one borrowed umbrella has not come back yet
Output
n + 1 lines. For each event the name of the person who took an umbrella, or -; on the last line the number of people waiting and the number of umbrellas in the stand
Example 1 · stdin
8 1
want mina
want joon
want sora
back
back
back
want hana
want dan
stdout
mina
-
-
joon
sora
-
hana
-
1 0
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
The tool for a queue (a line where the first one in is the first one out) differs by language. Python uses collections.deque: put in with append, take out with popleft(). Java has ArrayDeque with addLast/pollFirst, C# has Queue<T> with Enqueue/Dequeue, and C++ has std::queue with push/front/pop. C++'s pop() returns nothing, so read front() first. JS/TS, C and Craykon have no separate queue, so add to the end of an array or list (JS push, Craykon Add) and only move a number head that points at the front. Trap one: taking from the back (pop() in Python and JS) makes it a stack, so the latest person is served first. At the first back of the example you get sora instead of joon. Trap two: ask whether the line is empty before taking from it. What happens on an empty line differs by language. Python's popleft() stops with IndexError and C#'s Dequeue() with InvalidOperationException, Java's pollFirst() gives null, and JS's shift() quietly gives undefined. So in JS the third back of the example prints undefined, and since the umbrella never returns to the stand, hana does not get one either. C++'s front() on an empty queue is undefined behaviour, and Craykon stops with an error when you read item 0 of an empty list. Trap three: a returned umbrella goes either to a waiting person or into the stand, never both. If you raise the stand count and also hand it to the waiting person, one extra umbrella appears, and dan in the example receives an umbrella that does not exist.
Pythonmain.py · 23 lines
import sysfrom collections import dequelines = sys.stdin.read().split("\n")n, rack = map(int, lines[0].split())waiting = deque() # 기다리는 사람들: 뒤로 넣고 앞에서 꺼낸다out = []for line in lines[1:n + 1]: parts = line.split() if parts[0] == "want": if rack > 0: rack -= 1 out.append(parts[1]) else: waiting.append(parts[1]) out.append("-") elif waiting: out.append(waiting.popleft()) # 가장 먼저 온 사람이 받는다 else: rack += 1 # 기다리는 사람이 없으면 대여함에 꽂는다 out.append("-")out.append(f"{len(waiting)} {rack}")print("\n".join(out))
JavaScriptmain.js · 26 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, u] = lines[0].trim().split(" ").map(Number);let rack = u;// JS에는 큐가 따로 없다. 배열 뒤에 넣고, 맨 앞 자리(head)만 뒤로 옮긴다.const waiting = [];let head = 0;const out = [];for (let i = 1; i <= n; i++) { const [cmd, name] = lines[i].trim().split(" "); if (cmd === "want") { if (rack > 0) { rack--; out.push(name); } else { waiting.push(name); out.push("-"); } } else if (head < waiting.length) { out.push(waiting[head++]); // 가장 먼저 온 사람이 받는다 } else { rack++; // 기다리는 사람이 없으면 대여함에 꽂는다 out.push("-"); }}out.push(`${waiting.length - head} ${rack}`);console.log(out.join("\n"));
TypeScriptmain.ts · 28 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, u]: number[] = lines[0].trim().split(" ").map(Number);let rack: number = u;// TS에도 큐가 따로 없다. 배열 뒤에 넣고, 맨 앞 자리(head)만 뒤로 옮긴다.const waiting: string[] = [];let head = 0;const out: string[] = [];for (let i = 1; i <= n; i++) { const [cmd, name]: string[] = lines[i].trim().split(" "); if (cmd === "want") { if (rack > 0) { rack--; out.push(name); } else { waiting.push(name); out.push("-"); } } else if (head < waiting.length) { out.push(waiting[head++]); // 가장 먼저 온 사람이 받는다 } else { rack++; // 기다리는 사람이 없으면 대여함에 꽂는다 out.push("-"); }}out.push(`${waiting.length - head} ${rack}`);console.log(out.join("\n"));
JavaMain.java · 34 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] first = in.readLine().trim().split(" "); int n = Integer.parseInt(first[0]); int rack = Integer.parseInt(first[1]); ArrayDeque<String> waiting = new ArrayDeque<>(); StringBuilder out = new StringBuilder(); for (int i = 0; i < n; i++) { String[] parts = in.readLine().trim().split(" "); if (parts[0].equals("want")) { if (rack > 0) { rack--; out.append(parts[1]).append('\n'); } else { waiting.addLast(parts[1]); out.append("-\n"); } } else if (!waiting.isEmpty()) { out.append(waiting.pollFirst()).append('\n'); // 가장 먼저 온 사람이 받는다 } else { rack++; // 기다리는 사람이 없으면 대여함에 꽂는다 out.append("-\n"); } } out.append(waiting.size()).append(' ').append(rack); System.out.println(out); }}
C#Main.cs · 43 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] first = Console.ReadLine().Trim().Split(' '); int n = int.Parse(first[0]); int rack = int.Parse(first[1]); var waiting = new Queue<string>(); var sb = new StringBuilder(); for (int i = 0; i < n; i++) { string[] parts = Console.ReadLine().Trim().Split(' '); if (parts[0] == "want") { if (rack > 0) { rack--; sb.Append(parts[1]).Append('\n'); } else { waiting.Enqueue(parts[1]); sb.Append("-\n"); } } else if (waiting.Count > 0) { sb.Append(waiting.Dequeue()).Append('\n'); // 가장 먼저 온 사람이 받는다 } else { rack++; // 기다리는 사람이 없으면 대여함에 꽂는다 sb.Append("-\n"); } } sb.Append(waiting.Count).Append(' ').Append(rack).Append('\n'); Console.Write(sb); }}
C++main.cpp · 35 lines
#include <iostream>#include <queue>#include <string>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, rack; cin >> n >> rack; queue<string> waiting; for (int i = 0; i < n; i++) { string cmd; cin >> cmd; if (cmd == "want") { string name; cin >> name; if (rack > 0) { rack--; cout << name << '\n'; } else { waiting.push(name); cout << "-\n"; } } else if (!waiting.empty()) { cout << waiting.front() << '\n'; // 가장 먼저 온 사람이 받는다 waiting.pop(); // pop()은 값을 돌려주지 않는다 } else { rack++; // 기다리는 사람이 없으면 대여함에 꽂는다 cout << "-\n"; } } cout << waiting.size() << ' ' << rack << '\n'; return 0;}
Cmain.c · 35 lines
#include <stdio.h>#include <string.h>#define MAXN 9000/* 배열로 만든 큐: tail 자리에 넣고 head 자리에서 꺼낸다. 기다리는 사람은 모두 합쳐 n명을 넘지 않으니 MAXN칸이면 된다. */static char waiting[MAXN][11];int main(void) { int n, rack; scanf("%d %d", &n, &rack); int head = 0, tail = 0; for (int i = 0; i < n; i++) { char cmd[8], name[11]; scanf("%7s", cmd); if (strcmp(cmd, "want") == 0) { scanf("%10s", name); if (rack > 0) { rack--; printf("%s\n", name); } else { strcpy(waiting[tail++], name); printf("-\n"); } } else if (head < tail) { printf("%s\n", waiting[head++]); /* 가장 먼저 온 사람이 받는다 */ } else { rack++; /* 기다리는 사람이 없으면 대여함에 꽂는다 */ printf("-\n"); } } printf("%d %d\n", tail - head, rack); return 0;}
Craykonmain.cray · 36 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];rack = 첫줄[1];// 목록으로 만든 큐: 뒤에 넣고, 맨 앞 자리(head)만 뒤로 옮긴다waiting = [];head = 0;for (i = 0; i < n; i++){ parts = Console.ReadLine().Trim().Split(); if (parts[0] == "want") { if (rack > 0) { rack -= 1; Console.WriteLine(parts[1]); } else { waiting.Add(parts[1]); Console.WriteLine("-"); } } else if (head < waiting.Count) { // 가장 먼저 온 사람이 받는다 Console.WriteLine(waiting[head]); head += 1; } else { // 기다리는 사람이 없으면 대여함에 꽂는다 rack += 1; Console.WriteLine("-"); }}Console.WriteLine(waiting.Count - head + " " + rack);