Numbered lockers stand in one row along a corridor, in order of their numbers. At first no locker is in use.
n students arrive one after another, and each picks one locker number x.
If locker x is already in use, print "taken" and change nothing.
Otherwise print the numbers L and R of its neighbors among the lockers in use so far, separated by one space on one line, and then make x a locker in use.
L is the largest number among the lockers in use that is smaller than x.
R is the smallest number among the lockers in use that is larger than x.
If there is no such locker, write - (a single minus sign) in its place instead of a number.
On the last line print the number of lockers in use.
If your language has a standard library container that always keeps its numbers sorted, try using it.
Input
The first line gives n (1 ≤ n ≤ 2,000), and each of the next n lines gives one x (1 ≤ x ≤ 1,000,000,000). Numbers are written with digits only, without commas.
Output
n + 1 lines. The first n lines are "taken" or "L R" for each student; the last line is the number of lockers in use
Example 1 · stdin
8
50
20
80
50
9
100
35
20
stdout
- -
- 50
50 -
taken
- 20
80 -
20 50
taken
6
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 splits the languages that have an always-sorted set in the standard library from those that do not. Java TreeSet answers directly with lower(x) (the largest element smaller than x) and higher(x), giving null when there is none. C++ std::set::lower_bound(x) gives the first position not less than x, which is the right neighbor, and std::prev(it) is the left neighbor. C# SortedSet<int> has no method for the element before or after, so cut a range with GetViewBetween(low, high) and look at Max / Min. Python has no sorted set; use a sorted list with the bisect module (bisect_left to find the position, insert or insort to put it in). A JavaScript/TypeScript Set and a Craykon list only keep insertion order and do not sort, so scan every element and find "the largest one smaller than x" yourself. C has no containers at all, so keep the numbers in an array in arrival order and scan it the same way. n is small enough here to scan, but a sorted set needs only about log n steps per question. Six traps: (1) Java floor(x) / ceiling(x) mean "equal or" smaller / larger, so if you add first and then ask, you get x itself. (2) In C++, when it is begin() there is no left neighbor. Checking only whether the set is empty fails when the smallest number arrives, and std::prev on begin() is undefined behavior. (3) In Python, when the position i is 0, used[i - 1] is not an error but the last element used[-1]. (4) In C#, Max / Min of an empty SortedSet<int> return 0 without any error. Check Count first. (5) A JS array's sort() without a compare function turns numbers into strings and sorts them in dictionary order, so 10 comes before 9. Write sort((a, b) => a - b). (6) Unlike a set, a list accepts the same value again. If you do not ask whether it is already there, "taken" is missing and the count grows (Java add returns false when the element is already present).
Pythonmain.py · 15 lines
from bisect import bisect_leftn = int(input())used = [] # 쓰는 사물함 번호를 늘 작은 것부터 둔다for _ in range(n): x = int(input()) i = bisect_left(used, x) # x가 들어갈 자리: 그 왼쪽은 모두 x보다 작다 if i < len(used) and used[i] == x: print("taken") continue left = used[i - 1] if i > 0 else "-" # i가 0일 때 used[-1]은 맨 끝 값이라 따로 본다 right = used[i] if i < len(used) else "-" print(left, right) used.insert(i, x)print(len(used))
JavaScriptmain.js · 22 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);// JavaScript에는 정렬된 집합이 없어서, 쓰는 번호를 Set에 두고 양옆 이웃은 하나씩 훑어 찾는다const used = new Set();const out = [];for (let i = 1; i <= n; i++) { const x = Number(lines[i]); if (used.has(x)) { out.push("taken"); continue; } let left = null; // x보다 작은 번호 가운데 가장 큰 것 let right = null; // x보다 큰 번호 가운데 가장 작은 것 for (const y of used) { if (y < x && (left === null || y > left)) left = y; if (y > x && (right === null || y < right)) right = y; } out.push(`${left ?? "-"} ${right ?? "-"}`); used.add(x);}out.push(used.size);console.log(out.join("\n"));
TypeScriptmain.ts · 23 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);// TypeScript에도 정렬된 집합이 없어서, 쓰는 번호를 Set에 두고 양옆 이웃은 하나씩 훑어 찾는다const used = new Set<number>();const out: string[] = [];for (let i = 1; i <= n; i++) { const x = Number(lines[i]); if (used.has(x)) { out.push("taken"); continue; } let left: number | null = null; // x보다 작은 번호 가운데 가장 큰 것 let right: number | null = null; // x보다 큰 번호 가운데 가장 작은 것 for (const y of used) { if (y < x && (left === null || y > left)) left = y; if (y > x && (right === null || y < right)) right = y; } out.push(`${left ?? "-"} ${right ?? "-"}`); used.add(x);}out.push(String(used.size));console.log(out.join("\n"));
JavaMain.java · 27 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.TreeSet;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); TreeSet<Integer> used = new TreeSet<>(); // 늘 정렬되어 있는 집합 StringBuilder out = new StringBuilder(); for (int i = 0; i < n; i++) { int x = Integer.parseInt(in.readLine().trim()); if (used.contains(x)) { out.append("taken\n"); continue; } Integer left = used.lower(x); // x보다 작은 것 가운데 가장 큰 것, 없으면 null Integer right = used.higher(x); // x보다 큰 것 가운데 가장 작은 것, 없으면 null out.append(left == null ? "-" : left.toString()).append(' '); out.append(right == null ? "-" : right.toString()).append('\n'); used.add(x); } out.append(used.size()).append('\n'); System.out.print(out); }}
C#Main.cs · 31 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { int n = int.Parse(Console.ReadLine()); var used = new SortedSet<int>(); // 늘 정렬되어 있는 집합 var sb = new StringBuilder(); for (int i = 0; i < n; i++) { int x = int.Parse(Console.ReadLine()); if (used.Contains(x)) { sb.Append("taken\n"); continue; } // SortedSet에는 '바로 앞·뒤 값' 메서드가 없어서, x의 왼쪽·오른쪽 구간을 잘라 보고 끝 값을 본다. // 빈 구간의 Max·Min은 0을 돌려주므로 Count를 먼저 확인한다 var below = used.GetViewBetween(int.MinValue, x); var above = used.GetViewBetween(x, int.MaxValue); sb.Append(below.Count > 0 ? below.Max.ToString() : "-").Append(' '); sb.Append(above.Count > 0 ? above.Min.ToString() : "-").Append('\n'); used.Add(x); } sb.Append(used.Count).Append('\n'); Console.Write(sb); }}
C++main.cpp · 24 lines
#include <iostream>#include <set>int main() { int n; std::cin >> n; std::set<int> used; // 늘 정렬되어 있는 집합 for (int i = 0; i < n; i++) { int x; std::cin >> x; auto it = used.lower_bound(x); // x 이상인 값이 처음 나오는 자리 if (it != used.end() && *it == x) { std::cout << "taken\n"; continue; } // it이 오른쪽 이웃이고, 그 바로 앞이 왼쪽 이웃이다. begin()보다 앞으로는 갈 수 없다 if (it != used.begin()) std::cout << *std::prev(it) << ' '; else std::cout << "- "; if (it != used.end()) std::cout << *it << '\n'; else std::cout << "-\n"; used.insert(it, x); // 찾은 자리를 알려 주면 바로 그 앞에 넣는다 } std::cout << used.size() << '\n';}
Cmain.c · 34 lines
#include <stdio.h>int main(void) { int n; scanf("%d", &n); /* C에는 정렬된 집합이 없어서, 쓰는 번호를 배열에 두고 양옆 이웃은 하나씩 훑어 찾는다 */ static int used[2000]; int count = 0; for (int k = 0; k < n; k++) { int x; scanf("%d", &x); int taken = 0; int left = 0; /* x보다 작은 번호 가운데 가장 큰 것. 번호는 1부터라서 0이면 아직 없다는 뜻 */ int right = 0; /* x보다 큰 번호 가운데 가장 작은 것. 0이면 아직 없다는 뜻 */ for (int i = 0; i < count; i++) { int y = used[i]; if (y == x) taken = 1; if (y < x && y > left) left = y; if (y > x && (right == 0 || y < right)) right = y; } if (taken) { puts("taken"); continue; } if (left != 0) printf("%d ", left); else printf("- "); if (right != 0) printf("%d\n", right); else printf("-\n"); used[count] = x; /* 배열은 같은 값도 받아 주므로, 위에서 이미 있는지 먼저 확인했다 */ count++; } printf("%d\n", count); return 0;}
Craykonmain.cray · 29 lines
n = Console.ReadLine().ToNumber();// 크레이콘에는 정렬된 집합이 없어서, 쓰는 번호를 목록에 두고 양옆 이웃은 하나씩 훑어 찾는다쓰는번호 = [];for (k = 0; k < n; k++){ x = Console.ReadLine().ToNumber(); if (쓰는번호.Contains(x)) { Console.WriteLine("taken"); continue; } 왼쪽 = null; // x보다 작은 번호 가운데 가장 큰 것 오른쪽 = null; // x보다 큰 번호 가운데 가장 작은 것 foreach (y in 쓰는번호) { if (y < x && (왼쪽 == null || y > 왼쪽)) { 왼쪽 = y; } if (y > x && (오른쪽 == null || y < 오른쪽)) { 오른쪽 = y; } } 줄 = (왼쪽 == null ? "-" : "" + 왼쪽) + " " + (오른쪽 == null ? "-" : "" + 오른쪽); Console.WriteLine(줄); 쓰는번호.Add(x);}Console.WriteLine(쓰는번호.Count);