One elevator runs between floors 1 and F. It can carry up to K people at once.
There are n passengers, numbered 1 to n in input order. Passenger i arrives at floor a_i at minute t_i and wants to go to floor b_i.
The elevator's direction is one of 'up', 'down' and 'stopped'. At minute 0 the elevator is empty at floor 1 and its direction is 'stopped'.
When the time is minute T and the elevator is at floor f, it does the following five steps in order.
Step 1: Passengers who arrive at minute T join the back of the line on their floor. Passengers arriving at the same minute line up in order of number.
Step 2: All riding passengers going to floor f get off. Their arrival time is T.
Step 3: Decide the direction. There is 'work above' if there is at least one of: a riding passenger going above floor f, a passenger waiting on a floor above f, or a passenger waiting on floor f who wants to go up. 'Work below' looks downward in the same way.
- If the direction is 'up' and there is work above, keep 'up'. If there is no work above, change to 'down' if there is work below, and to 'stopped' if not.
- The same holds for 'down': keep it if there is work below; otherwise change to 'up' if there is work above, and to 'stopped' if not.
- If the direction is 'stopped', look at the waiting passenger P with the smallest number. If P is on another floor, head toward P's floor; if P is on floor f, head the way P wants to go. If nobody is waiting, stay 'stopped'. It is the passenger with the smallest number, not the nearest one.
Step 4: If the direction is not 'stopped', passengers in floor f's line who want to go that way board in line order. When K people are riding, no one else can board. Those who could not board and those going the other way keep waiting, keeping their places in line.
Step 5: If the direction is 'up', go up one floor; if 'down', go down one floor; the time becomes T + 1. If the direction is 'stopped', stay on that floor and skip ahead to the minute the next passenger arrives.
It ends when every passenger has arrived.
The first line gives F, K and n, and the next n lines give t_i, a_i and b_i separated by single spaces.
Print each passenger's arrival time, one per line, in order of number.
Input
2 ≤ F ≤ 30, 1 ≤ K ≤ 10, 1 ≤ n ≤ 500, 0 ≤ t_i ≤ 1,000,000, 1 ≤ a_i, b_i ≤ F, a_i ≠ b_i (all integers). t_i never decreases as the number grows.
Output
n lines, each passenger's arrival time
Example 1 · stdin
6 2 5
0 1 4
0 3 1
1 2 5
2 5 3
2 6 5
stdout
3
10
4
8
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 is a simulation that turns the rules into code one step at a time. Keep a waiting line for each floor (a list of lists) and a list of riders, and run the five steps every minute. Counting one minute at a time while there is nothing to do would spin through a million idle minutes, so when the direction is 'stopped', jump straight to the next arrival time. Removing riders who get off differs by language: Python builds a new list with a comprehension, JS/TS use filter, Java uses Iterator.remove() (calling list.remove inside a for-each usually throws ConcurrentModificationException), C# uses RemoveAll(p => …) (removing inside foreach throws InvalidOperationException), C packs the remaining riders to the front of the array and lowers the count, C++20 has std::erase_if, and Craykon builds a new list of those who stay. Removing boarders from a line likewise builds a new line that keeps the others' order. Six traps: (1) Boarding everyone without checking direction drags passengers going the other way along. (2) Boarding before getting off tries to board while still full, so people cannot get on even though seats would free up at that floor. (3) Heading toward the nearest passenger when stopped is wrong; head toward the one with the smallest number. (4) Going all the way to the end floor before turning (SCAN) is wrong; this elevator turns right where there is no more work (LOOK). (5) Comparing seats with <= K lets one extra person on. (6) When stopped and P is on another floor, starting toward P's destination never goes to pick P up.
Pythonmain.py · 59 lines
import sysdef main(): data = sys.stdin.read().split() floors, cap, n = int(data[0]), int(data[1]), int(data[2]) t = [int(data[3 + 3 * i]) for i in range(n)] a = [int(data[4 + 3 * i]) for i in range(n)] b = [int(data[5 + 3 * i]) for i in range(n)] waiting = [[] for _ in range(floors + 1)] # 층마다 기다리는 사람 번호(온 차례) inside = [] # 타고 있는 사람 번호 arrive = [0] * n now, floor, direction = 0, 1, 0 # 방향: 1 위, -1 아래, 0 멈춤 nxt = done = 0 while done < n: # 1) 이 시각에 온 사람이 줄을 선다 while nxt < n and t[nxt] == now: waiting[a[nxt]].append(nxt) nxt += 1 # 2) 내릴 사람이 내린다 for p in [p for p in inside if b[p] == floor]: arrive[p] = now done += 1 inside = [p for p in inside if b[p] != floor] # 3) 방향을 정한다 up = any(b[p] > floor for p in inside) or any(waiting[g] for g in range(floor + 1, floors + 1)) \ or any(b[p] > floor for p in waiting[floor]) down = any(b[p] < floor for p in inside) or any(waiting[g] for g in range(1, floor)) \ or any(b[p] < floor for p in waiting[floor]) if direction == 1 and not up: direction = -1 if down else 0 elif direction == -1 and not down: direction = 1 if up else 0 elif direction == 0: first = min((p for g in range(1, floors + 1) for p in waiting[g]), default=None) if first is not None: target = a[first] if a[first] != floor else b[first] direction = 1 if target > floor else -1 # 4) 같은 방향으로 갈 사람이 온 차례대로, 자리가 있는 만큼 탄다 if direction != 0: stay = [] for p in waiting[floor]: if (b[p] - floor) * direction > 0 and len(inside) < cap: inside.append(p) else: stay.append(p) waiting[floor] = stay if done == n: break # 5) 한 층 옮긴다. 할 일이 없으면 다음 사람이 올 때까지 건너뛴다 if direction == 0: now = t[nxt] else: floor += direction now += 1 print("\n".join(map(str, arrive)))main()
JavaScriptmain.js · 55 lines
const d = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [floors, cap, n] = d;const t = [], a = [], b = [];for (let i = 0; i < n; i++) { t.push(d[3 + 3 * i]); a.push(d[4 + 3 * i]); b.push(d[5 + 3 * i]);}let waiting = Array.from({ length: floors + 1 }, () => []); // 층마다 기다리는 사람 번호(온 차례)let inside = []; // 타고 있는 사람 번호const arrive = new Array(n).fill(0);let now = 0, floor = 1, dir = 0; // 방향: 1 위, -1 아래, 0 멈춤let next = 0, done = 0;while (done < n) { // 1) 이 시각에 온 사람이 줄을 선다 while (next < n && t[next] === now) waiting[a[next]].push(next++); // 2) 내릴 사람이 내린다 for (const p of inside) if (b[p] === floor) { arrive[p] = now; done++; } inside = inside.filter((p) => b[p] !== floor); // 3) 방향을 정한다 let up = inside.some((p) => b[p] > floor) || waiting[floor].some((p) => b[p] > floor); let down = inside.some((p) => b[p] < floor) || waiting[floor].some((p) => b[p] < floor); for (let g = 1; g <= floors; g++) { if (waiting[g].length === 0) continue; if (g > floor) up = true; if (g < floor) down = true; } if (dir === 1 && !up) dir = down ? -1 : 0; else if (dir === -1 && !down) dir = up ? 1 : 0; else if (dir === 0) { let first = -1; // 기다리는 사람 가운데 가장 먼저 온 사람 for (let g = 1; g <= floors; g++) if (waiting[g].length > 0 && (first < 0 || waiting[g][0] < first)) first = waiting[g][0]; if (first >= 0) { const target = a[first] !== floor ? a[first] : b[first]; dir = target > floor ? 1 : -1; } } // 4) 같은 방향으로 갈 사람이 온 차례대로, 자리가 있는 만큼 탄다 if (dir !== 0) { const stay = []; for (const p of waiting[floor]) { if ((b[p] - floor) * dir > 0 && inside.length < cap) inside.push(p); else stay.push(p); } waiting[floor] = stay; } if (done === n) break; // 5) 한 층 옮긴다. 할 일이 없으면 다음 사람이 올 때까지 건너뛴다 if (dir === 0) now = t[next]; else { floor += dir; now++; }}console.log(arrive.join("\n"));
TypeScriptmain.ts · 55 lines
const d: number[] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [floors, cap, n] = d;const t: number[] = [], a: number[] = [], b: number[] = [];for (let i = 0; i < n; i++) { t.push(d[3 + 3 * i]); a.push(d[4 + 3 * i]); b.push(d[5 + 3 * i]);}let waiting: number[][] = Array.from({ length: floors + 1 }, () => []); // 층마다 기다리는 사람 번호(온 차례)let inside: number[] = []; // 타고 있는 사람 번호const arrive: number[] = new Array(n).fill(0);let now = 0, floor = 1, dir = 0; // 방향: 1 위, -1 아래, 0 멈춤let next = 0, done = 0;while (done < n) { // 1) 이 시각에 온 사람이 줄을 선다 while (next < n && t[next] === now) waiting[a[next]].push(next++); // 2) 내릴 사람이 내린다 for (const p of inside) if (b[p] === floor) { arrive[p] = now; done++; } inside = inside.filter((p) => b[p] !== floor); // 3) 방향을 정한다 let up = inside.some((p) => b[p] > floor) || waiting[floor].some((p) => b[p] > floor); let down = inside.some((p) => b[p] < floor) || waiting[floor].some((p) => b[p] < floor); for (let g = 1; g <= floors; g++) { if (waiting[g].length === 0) continue; if (g > floor) up = true; if (g < floor) down = true; } if (dir === 1 && !up) dir = down ? -1 : 0; else if (dir === -1 && !down) dir = up ? 1 : 0; else if (dir === 0) { let first = -1; // 기다리는 사람 가운데 가장 먼저 온 사람 for (let g = 1; g <= floors; g++) if (waiting[g].length > 0 && (first < 0 || waiting[g][0] < first)) first = waiting[g][0]; if (first >= 0) { const target = a[first] !== floor ? a[first] : b[first]; dir = target > floor ? 1 : -1; } } // 4) 같은 방향으로 갈 사람이 온 차례대로, 자리가 있는 만큼 탄다 if (dir !== 0) { const stay: number[] = []; for (const p of waiting[floor]) { if ((b[p] - floor) * dir > 0 && inside.length < cap) inside.push(p); else stay.push(p); } waiting[floor] = stay; } if (done === n) break; // 5) 한 층 옮긴다. 할 일이 없으면 다음 사람이 올 때까지 건너뛴다 if (dir === 0) now = t[next]; else { floor += dir; now++; }}console.log(arrive.join("\n"));
JavaMain.java · 83 lines
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in)); in.nextToken(); int floors = (int) in.nval; in.nextToken(); int cap = (int) in.nval; in.nextToken(); int n = (int) in.nval; int[] t = new int[n], a = new int[n], b = new int[n]; for (int i = 0; i < n; i++) { in.nextToken(); t[i] = (int) in.nval; in.nextToken(); a[i] = (int) in.nval; in.nextToken(); b[i] = (int) in.nval; } List<List<Integer>> waiting = new ArrayList<>(); // 층마다 기다리는 사람 번호(온 차례) for (int g = 0; g <= floors; g++) waiting.add(new ArrayList<>()); List<Integer> inside = new ArrayList<>(); int[] arrive = new int[n]; int now = 0, floor = 1, dir = 0; // 방향: 1 위, -1 아래, 0 멈춤 int next = 0, done = 0; while (done < n) { // 1) 이 시각에 온 사람이 줄을 선다 while (next < n && t[next] == now) waiting.get(a[next]).add(next++); // 2) 내릴 사람이 내린다 for (Iterator<Integer> it = inside.iterator(); it.hasNext(); ) { int p = it.next(); if (b[p] == floor) { arrive[p] = now; done++; it.remove(); } } // 3) 방향을 정한다 boolean up = false, down = false; for (int p : inside) { if (b[p] > floor) up = true; if (b[p] < floor) down = true; } for (int p : waiting.get(floor)) { if (b[p] > floor) up = true; if (b[p] < floor) down = true; } for (int g = 1; g <= floors; g++) { if (waiting.get(g).isEmpty()) continue; if (g > floor) up = true; if (g < floor) down = true; } if (dir == 1 && !up) dir = down ? -1 : 0; else if (dir == -1 && !down) dir = up ? 1 : 0; else if (dir == 0) { int first = -1; for (int g = 1; g <= floors; g++) { List<Integer> w = waiting.get(g); if (!w.isEmpty() && (first < 0 || w.get(0) < first)) first = w.get(0); } if (first >= 0) { int target = a[first] != floor ? a[first] : b[first]; dir = target > floor ? 1 : -1; } } // 4) 같은 방향으로 갈 사람이 온 차례대로, 자리가 있는 만큼 탄다 if (dir != 0) { List<Integer> stay = new ArrayList<>(); for (int p : waiting.get(floor)) { if ((b[p] - floor) * dir > 0 && inside.size() < cap) inside.add(p); else stay.add(p); } waiting.set(floor, stay); } if (done == n) break; // 5) 한 층 옮긴다. 할 일이 없으면 다음 사람이 올 때까지 건너뛴다 if (dir == 0) now = t[next]; else { floor += dir; now++; } } StringBuilder sb = new StringBuilder(); for (int x : arrive) sb.append(x).append('\n'); System.out.print(sb); }}
C#Main.cs · 75 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { var d = Array.ConvertAll(Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries), int.Parse); int floors = d[0], cap = d[1], n = d[2]; int[] t = new int[n], a = new int[n], b = new int[n]; for (int i = 0; i < n; i++) { t[i] = d[3 + 3 * i]; a[i] = d[4 + 3 * i]; b[i] = d[5 + 3 * i]; } var waiting = new List<int>[floors + 1]; // 층마다 기다리는 사람 번호(온 차례) for (int g = 0; g <= floors; g++) waiting[g] = new List<int>(); var inside = new List<int>(); var arrive = new int[n]; int now = 0, floor = 1, dir = 0; // 방향: 1 위, -1 아래, 0 멈춤 int next = 0, done = 0; while (done < n) { // 1) 이 시각에 온 사람이 줄을 선다 while (next < n && t[next] == now) { waiting[a[next]].Add(next); next++; } // 2) 내릴 사람이 내린다 foreach (int p in inside) if (b[p] == floor) { arrive[p] = now; done++; } inside.RemoveAll(p => b[p] == floor); // 3) 방향을 정한다 bool up = false, down = false; foreach (int p in inside) { if (b[p] > floor) up = true; if (b[p] < floor) down = true; } foreach (int p in waiting[floor]) { if (b[p] > floor) up = true; if (b[p] < floor) down = true; } for (int g = 1; g <= floors; g++) { if (waiting[g].Count == 0) continue; if (g > floor) up = true; if (g < floor) down = true; } if (dir == 1 && !up) dir = down ? -1 : 0; else if (dir == -1 && !down) dir = up ? 1 : 0; else if (dir == 0) { int first = -1; for (int g = 1; g <= floors; g++) if (waiting[g].Count > 0 && (first < 0 || waiting[g][0] < first)) first = waiting[g][0]; if (first >= 0) { int target = a[first] != floor ? a[first] : b[first]; dir = target > floor ? 1 : -1; } } // 4) 같은 방향으로 갈 사람이 온 차례대로, 자리가 있는 만큼 탄다 if (dir != 0) { var stay = new List<int>(); foreach (int p in waiting[floor]) { if ((b[p] - floor) * dir > 0 && inside.Count < cap) inside.Add(p); else stay.Add(p); } waiting[floor] = stay; } if (done == n) break; // 5) 한 층 옮긴다. 할 일이 없으면 다음 사람이 올 때까지 건너뛴다 if (dir == 0) now = t[next]; else { floor += dir; now++; } } var sb = new StringBuilder(); foreach (int x in arrive) sb.Append(x).Append('\n'); Console.Write(sb); }}
C++main.cpp · 59 lines
#include <algorithm>#include <iostream>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int floors, cap, n; std::cin >> floors >> cap >> n; std::vector<int> t(n), a(n), b(n), arrive(n); for (int i = 0; i < n; i++) std::cin >> t[i] >> a[i] >> b[i]; std::vector<std::vector<int>> waiting(floors + 1); // 층마다 기다리는 사람 번호(온 차례) std::vector<int> inside; int now = 0, floor = 1, dir = 0; // 방향: 1 위, -1 아래, 0 멈춤 int next = 0, done = 0; while (done < n) { // 1) 이 시각에 온 사람이 줄을 선다 while (next < n && t[next] == now) waiting[a[next]].push_back(next), next++; // 2) 내릴 사람이 내린다 for (int p : inside) if (b[p] == floor) arrive[p] = now, done++; std::erase_if(inside, [&](int p) { return b[p] == floor; }); // 3) 방향을 정한다 bool up = false, down = false; for (int p : inside) up |= b[p] > floor, down |= b[p] < floor; for (int p : waiting[floor]) up |= b[p] > floor, down |= b[p] < floor; for (int g = 1; g <= floors; g++) { if (waiting[g].empty()) continue; if (g > floor) up = true; if (g < floor) down = true; } if (dir == 1 && !up) dir = down ? -1 : 0; else if (dir == -1 && !down) dir = up ? 1 : 0; else if (dir == 0) { int first = -1; for (int g = 1; g <= floors; g++) if (!waiting[g].empty() && (first < 0 || waiting[g][0] < first)) first = waiting[g][0]; if (first >= 0) { int target = a[first] != floor ? a[first] : b[first]; dir = target > floor ? 1 : -1; } } // 4) 같은 방향으로 갈 사람이 온 차례대로, 자리가 있는 만큼 탄다 if (dir != 0) { std::vector<int> stay; for (int p : waiting[floor]) { if ((b[p] - floor) * dir > 0 && (int)inside.size() < cap) inside.push_back(p); else stay.push_back(p); } waiting[floor] = stay; } if (done == n) break; // 5) 한 층 옮긴다. 할 일이 없으면 다음 사람이 올 때까지 건너뛴다 if (dir == 0) now = t[next]; else floor += dir, now++; } for (int x : arrive) std::cout << x << '\n'; return 0;}
Cmain.c · 83 lines
#include <stdio.h>#define MAXN 500#define MAXF 30static int t[MAXN], a[MAXN], b[MAXN], arrive[MAXN];static int waiting[MAXF + 1][MAXN]; /* 층마다 기다리는 사람 번호(온 차례) */static int wcount[MAXF + 1];static int inside[10], icount = 0; /* 타고 있는 사람 번호 */int main(void) { int floors, cap, n; scanf("%d %d %d", &floors, &cap, &n); for (int i = 0; i < n; i++) scanf("%d %d %d", &t[i], &a[i], &b[i]); int now = 0, floor = 1, dir = 0; /* 방향: 1 위, -1 아래, 0 멈춤 */ int next = 0, done = 0; while (done < n) { /* 1) 이 시각에 온 사람이 줄을 선다 */ while (next < n && t[next] == now) { waiting[a[next]][wcount[a[next]]++] = next; next++; } /* 2) 내릴 사람이 내린다(남는 사람은 앞으로 당겨 담는다) */ int k = 0; for (int j = 0; j < icount; j++) { int p = inside[j]; if (b[p] == floor) { arrive[p] = now; done++; } else { inside[k++] = p; } } icount = k; /* 3) 방향을 정한다 */ int up = 0, down = 0; for (int j = 0; j < icount; j++) { if (b[inside[j]] > floor) up = 1; if (b[inside[j]] < floor) down = 1; } for (int j = 0; j < wcount[floor]; j++) { if (b[waiting[floor][j]] > floor) up = 1; if (b[waiting[floor][j]] < floor) down = 1; } for (int g = 1; g <= floors; g++) { if (wcount[g] == 0) continue; if (g > floor) up = 1; if (g < floor) down = 1; } if (dir == 1 && !up) dir = down ? -1 : 0; else if (dir == -1 && !down) dir = up ? 1 : 0; else if (dir == 0) { int first = -1; for (int g = 1; g <= floors; g++) if (wcount[g] > 0 && (first < 0 || waiting[g][0] < first)) first = waiting[g][0]; if (first >= 0) { int target = a[first] != floor ? a[first] : b[first]; dir = target > floor ? 1 : -1; } } /* 4) 같은 방향으로 갈 사람이 온 차례대로, 자리가 있는 만큼 탄다 */ if (dir != 0) { int *w = waiting[floor]; k = 0; for (int j = 0; j < wcount[floor]; j++) { int p = w[j]; if ((b[p] - floor) * dir > 0 && icount < cap) inside[icount++] = p; else w[k++] = p; } wcount[floor] = k; } if (done == n) break; /* 5) 한 층 옮긴다. 할 일이 없으면 다음 사람이 올 때까지 건너뛴다 */ if (dir == 0) { now = t[next]; } else { floor += dir; now++; } } for (int i = 0; i < n; i++) printf("%d\n", arrive[i]); return 0;}
Craykonmain.cray · 146 lines
첫줄 = Console.ReadNumbers();floors = 첫줄[0];cap = 첫줄[1];n = 첫줄[2];t = [];a = [];b = [];for (i = 0; i < n; i++){ p = Console.ReadNumbers(); t.Add(p[0]); a.Add(p[1]); b.Add(p[2]);}waiting = []; // 층마다 기다리는 사람 번호(온 차례)for (g = 0; g <= floors; g++){ waiting.Add([]);}inside = []; // 타고 있는 사람 번호arrive = NewList(n, 0);now = 0;floor = 1;dir = 0; // 방향: 1 위, -1 아래, 0 멈춤next = 0;done = 0;while (done < n){ // 1) 이 시각에 온 사람이 줄을 선다 while (next < n && t[next] == now) { waiting[a[next]].Add(next); next++; } // 2) 내릴 사람이 내린다 남은 = []; foreach (p in inside) { if (b[p] == floor) { arrive[p] = now; done++; } else { 남은.Add(p); } } inside = 남은; // 3) 방향을 정한다 up = false; down = false; foreach (p in inside) { if (b[p] > floor) { up = true; } if (b[p] < floor) { down = true; } } foreach (p in waiting[floor]) { if (b[p] > floor) { up = true; } if (b[p] < floor) { down = true; } } for (g = 1; g <= floors; g++) { if (waiting[g].Count > 0 && g > floor) { up = true; } if (waiting[g].Count > 0 && g < floor) { down = true; } } if (dir == 1 && !up) { dir = down ? -1 : 0; } else if (dir == -1 && !down) { dir = up ? 1 : 0; } else if (dir == 0) { first = -1; // 기다리는 사람 가운데 가장 먼저 온 사람 for (g = 1; g <= floors; g++) { if (waiting[g].Count > 0 && (first < 0 || waiting[g][0] < first)) { first = waiting[g][0]; } } if (first >= 0) { target = a[first]; if (target == floor) { target = b[first]; } dir = target > floor ? 1 : -1; } } // 4) 같은 방향으로 갈 사람이 온 차례대로, 자리가 있는 만큼 탄다 if (dir != 0) { stay = []; foreach (p in waiting[floor]) { if ((b[p] - floor) * dir > 0 && inside.Count < cap) { inside.Add(p); } else { stay.Add(p); } } waiting[floor] = stay; } if (done == n) { break; } // 5) 한 층 옮긴다. 할 일이 없으면 다음 사람이 올 때까지 건너뛴다 if (dir == 0) { now = t[next]; } else { floor = floor + dir; now++; }}Console.WriteLine(arrive.Join("\n"));