n people stand in line at a ticket booth, numbered 1 to n from the front. Person i wants to buy tᵢ tickets. Each turn the booth sells at most m tickets to the one person at the front of the line (fewer if that person needs fewer than m). After buying, a person who still needs more goes to the back of the line; a person who has all their tickets leaves. Repeating this until the line is empty, print the numbers of the people in the order they leave, on one line separated by spaces.
Input
The first line has n and m, the second line t₁ … tₙ. 1 ≤ n ≤ 1,000, 1 ≤ m ≤ 1,000, 1 ≤ tᵢ ≤ 1,000
Output
n numbers in leaving order (one line, separated by spaces)
Example 1 · stdin
3 3
4 3 1
stdout
2 3 1
Example 2 · stdin
5 2
5 1 4 2 3
stdout
2 4 3 5 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
The line is a queue: take from the front, add to the back. There are at most a million turns, so simply simulating works. How you get a queue differs by language: Python collections.deque with popleft() (a list's pop(0) shifts everything behind it, which is slow), Java ArrayDeque with pollFirst()/addLast(), C# Queue<int> with Dequeue()/Enqueue(), C++ std::queue with front()/pop()/push(). JavaScript and TypeScript have no built-in queue, and the tempting shift() also shifts everything — instead only push onto the array and move a front index (head). C uses an array of size n as a circular queue (head = (head + 1) % n); the line never holds more than n people, so n slots suffice. The Craykon solution builds a circular queue with NewList(n, 0). RemoveAt(0) also shifts everything behind it, but with at most 1,000 people in line a million turns are still fast enough. Two traps: taking from the back instead of the front (a stack) reverses the order. And decide whether to rejoin after selling, by whether the remaining count is above 0 — asking 'needs m or more, so rejoin' before selling makes a person who needs exactly m go around one extra time.
Pythonmain.py · 16 lines
from collections import dequen, m = map(int, input().split())need = list(map(int, input().split()))line = deque(range(n)) # 줄에 선 사람의 번호(0부터)left = need[:] # 아직 사야 할 표order = []while line: person = line.popleft() left[person] -= min(m, left[person]) if left[person] > 0: line.append(person) # 더 필요하면 맨 뒤로 else: order.append(person + 1)print(*order)
JavaScriptmain.js · 15 lines
const [n, m, ...need] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 배열 + 앞 자리(head)로 큐를 만든다. shift()는 뒤의 것을 모두 당겨서 느릴 수 있다.const line = [];for (let i = 0; i < n; i++) line.push(i);let head = 0;const left = need.slice();const order = [];while (head < line.length) { const person = line[head++]; left[person] -= Math.min(m, left[person]); if (left[person] > 0) line.push(person); // 더 필요하면 맨 뒤로 else order.push(person + 1);}console.log(order.join(" "));
TypeScriptmain.ts · 17 lines
import { readFileSync } from "node:fs";const [n, m, ...need]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 배열 + 앞 자리(head)로 큐를 만든다. shift()는 뒤의 것을 모두 당겨서 느릴 수 있다.const line: number[] = [];for (let i = 0; i < n; i++) line.push(i);let head = 0;const left: number[] = need.slice();const order: number[] = [];while (head < line.length) { const person = line[head++]; left[person] -= Math.min(m, left[person]); if (left[person] > 0) line.push(person); // 더 필요하면 맨 뒤로 else order.push(person + 1);}console.log(order.join(" "));
JavaMain.java · 30 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.StringJoiner;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int[] left = new int[n]; ArrayDeque<Integer> line = new ArrayDeque<>(); st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) { left[i] = Integer.parseInt(st.nextToken()); line.addLast(i); } StringJoiner order = new StringJoiner(" "); while (!line.isEmpty()) { int person = line.pollFirst(); left[person] -= Math.min(m, left[person]); if (left[person] > 0) line.addLast(person); // 더 필요하면 맨 뒤로 else order.add(String.valueOf(person + 1)); } System.out.println(order); }}
C#Main.cs · 22 lines
using System;using System.Collections.Generic;using System.Linq;class Program{ static void Main() { int m = int.Parse(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)[1]); int[] left = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); var line = new Queue<int>(Enumerable.Range(0, left.Length)); var order = new List<int>(); while (line.Count > 0) { int person = line.Dequeue(); left[person] -= Math.Min(m, left[person]); if (left[person] > 0) line.Enqueue(person); // 더 필요하면 맨 뒤로 else order.Add(person + 1); } Console.WriteLine(string.Join(" ", order)); }}
C++main.cpp · 28 lines
#include <algorithm>#include <iostream>#include <queue>#include <vector>int main() { int n, m; std::cin >> n >> m; std::vector<int> left(n); std::queue<int> line; for (int i = 0; i < n; i++) { std::cin >> left[i]; line.push(i); } bool first = true; while (!line.empty()) { int person = line.front(); line.pop(); left[person] -= std::min(m, left[person]); if (left[person] > 0) { line.push(person); // 더 필요하면 맨 뒤로 } else { std::cout << (first ? "" : " ") << person + 1; first = false; } } std::cout << "\n";}
Cmain.c · 31 lines
#include <stdio.h>#define MAXN 1000/* 크기 MAXN인 원형 큐: 줄에는 많아야 n명만 있다 */static int queue[MAXN];static int left[MAXN];int main(void) { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) { scanf("%d", &left[i]); queue[i] = i; } int head = 0, size = n, printed = 0; while (size > 0) { int person = queue[head]; head = (head + 1) % MAXN; size--; left[person] -= left[person] < m ? left[person] : m; if (left[person] > 0) { queue[(head + size) % MAXN] = person; /* 더 필요하면 맨 뒤로 */ size++; } else { printf(printed++ ? " %d" : "%d", person + 1); } } putchar('\n'); return 0;}
Craykonmain.cray · 32 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];m = 첫줄[1];left = Console.ReadNumbers();// 원형 큐: 줄에는 많아야 n명이라 n칸이면 된다. head는 맨 앞 자리, size는 줄 길이.line = NewList(n, 0);for (i = 0; i < n; i++){ line[i] = i;}head = 0;size = n;order = [];while (size > 0){ person = line[head]; head = (head + 1) % n; size -= 1; left[person] -= Mathf.Min(m, left[person]); if (left[person] > 0) { // 더 필요하면 맨 뒤로 line[(head + size) % n] = person; size += 1; } else { order.Add(person + 1); }}Console.WriteLine(order);