standard containersqueueP0207

Coupling trains at the yard

At a rail yard, cars are coupled in one row to make a train.
At first there are no cars. Process n commands in order.
Cars go on and come off at both the front and the back of the row, so use the standard library's double-ended queue (deque) container. - addf x: couple car number x at the very front. - addb x: couple car number x at the very back. - cutf k: uncouple the front car, k times.
If fewer than k cars are left, uncouple all of them and stop.
Print the numbers of the uncoupled cars in the order they were uncoupled (front car first) on one line, separated by single spaces.
If no car was uncoupled, print -. - cutb k: uncouple the back car, k times.
The other rules are the same as cutf; since the order is the order of uncoupling, print the back car first. - rot k: k times, uncouple the front car and couple it at the back.
Print nothing.
If there are no cars, do nothing. After all commands, print the number of cars left, then on the next line the numbers of the cars left from the front, separated by single spaces.
If no cars are left, print - on the second line.

Input: First line n (1 ≤ n ≤ 5000).
Then one command per line for n lines.
For addf/addb 1 ≤ x ≤ 10^9, for cutf/cutb 1 ≤ k ≤ 10^9, for rot 0 ≤ k ≤ 10^9.
Car numbers may repeat.
Output: One line per cutf/cutb (the uncoupled car numbers, or -), then the number of cars left, then their numbers (or -)

Example 1 · stdin

9
addb 1
addb 2
addf 3
rot 1
cutb 2
addb 9
addf 4
rot 4
cutf 1

stdout

Example 2 · stdin

5
cutf 3
addf 7
addf 8
cutb 5
rot 2

stdout

-
7 8
0
-

main.py Programming language Runtime version

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 · 4 languages

This problem takes only Python, Java, C# and C++: the languages whose standard library has a container that adds and removes at both ends in O(1).
JavaScript/TypeScript array unshift/shift may move every element when working at the front, C has no containers, and Craykon's list Insert(0, x)/RemoveAt(0) also shift everything behind by one.
The names differ by language: Python collections.deque with appendleft/append/popleft/pop/rotate, Java ArrayDeque with addFirst/addLast/pollFirst/pollLast, C++ std::deque with push_front/push_back/front+pop_front (pop_front() returns nothing)/std::rotate.
C# has no Deque, so use LinkedList<T> with AddFirst/AddLast/RemoveFirst/RemoveLast.
Cut first min(k, cars left) times, and rotate only k modulo the number of cars (a full turn changes nothing); Python's rotate reduces it for you.
Five traps: (1) Python rotate(k) turns to the right, bringing back cars to the front.
To send front cars to the back use rotate(-k).
In C++ std::rotate(begin, begin + r, end) the middle argument is "the element that becomes first", so passing end - r turns the other way.
(2) Python deque.pop() removes from the back.
Removing from the front is popleft().
(3) Java ArrayDeque.push adds at the front (addFirst), like a stack.
Adding at the back is addLast (add/offer).
(4) Removing k times without reducing k removes from an empty container: C# stops with NullReferenceException because train.First is null, Java pop/removeFirst throw NoSuchElementException and pollFirst returns null, which throws NullPointerException the moment it goes into an int.
Python popleft raises IndexError, and C++ front() is undefined behavior.
(5) cutb takes the back car first, so in uncoupling order the numbers come out reversed compared with the train.

Pythonmain.py · 27 lines

import sysfrom collections import deque lines = sys.stdin.read().split("\n")n = int(lines[0])train = deque()  # 앞뒤 어느 쪽에서도 넣고 빼는 데 O(1)out = []for cmd in lines[1:n + 1]:    op, arg = cmd.split()    k = int(arg)    if op == "addf":        train.appendleft(k)    elif op == "addb":        train.append(k)    elif op in ("cutf", "cutb"):        # 남은 차량보다 많이 떼라고 하면 있는 만큼만 뗀다(빈 deque에서 빼면 IndexError)        take = min(k, len(train))        if op == "cutf":            cut = [train.popleft() for _ in range(take)]        else:            cut = [train.pop() for _ in range(take)]  # 뗀 차례: 맨 뒤 차량부터        out.append(" ".join(map(str, cut)) if cut else "-")    elif op == "rot":        train.rotate(-k)  # 음수는 왼쪽으로: 앞의 것이 뒤로 간다(빈 deque는 그대로)out.append(str(len(train)))out.append(" ".join(map(str, train)) if train else "-")print("\n".join(out))

JavaMain.java · 44 lines

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.StringJoiner; 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());        ArrayDeque<Integer> train = new ArrayDeque<>(); // 앞뒤 어느 쪽에서도 넣고 빼는 데 O(1)        StringBuilder out = new StringBuilder();        for (int i = 0; i < n; i++) {            String[] p = in.readLine().trim().split(" ");            long k = Long.parseLong(p[1]);            switch (p[0]) {                case "addf" -> train.addFirst((int) k);                case "addb" -> train.addLast((int) k);                case "cutf", "cutb" -> {                    // 있는 만큼만 뗀다(빈 ArrayDeque에서 removeFirst·pop은 예외를 던진다)                    long take = Math.min(k, train.size());                    StringJoiner cut = new StringJoiner(" ");                    for (long r = 0; r < take; r++) {                        int car = p[0].equals("cutf") ? train.pollFirst() : train.pollLast(); // 뒤는 맨 뒤 차량부터                        cut.add(String.valueOf(car));                    }                    out.append(take == 0 ? "-" : cut.toString()).append('\n');                }                case "rot" -> {                    if (!train.isEmpty()) {                        long r = k % train.size(); // 한 바퀴 돌면 제자리다                        for (long s = 0; s < r; s++) train.addLast(train.pollFirst());                    }                }                default -> throw new IllegalArgumentException(p[0]);            }        }        out.append(train.size()).append('\n');        StringJoiner items = new StringJoiner(" ");        for (int x : train) items.add(String.valueOf(x)); // 앞에서 뒤로 돈다        out.append(train.isEmpty() ? "-" : items.toString()).append('\n');        System.out.print(out);    }}

C#Main.cs · 51 lines

using System;using System.Collections.Generic;using System.Text; class Program{    static void Main()    {        int n = int.Parse(Console.ReadLine()!.Trim());        // .NET에는 Deque가 없다. LinkedList<T>는 앞뒤에 넣고 빼는 데 O(1)이다        var train = new LinkedList<int>();        var output = new StringBuilder();        for (int i = 0; i < n; i++)        {            string[] p = Console.ReadLine()!.Trim().Split(' ');            long k = long.Parse(p[1]);            switch (p[0])            {                case "addf": train.AddFirst((int)k); break;                case "addb": train.AddLast((int)k); break;                case "cutf":                case "cutb":                    // 있는 만큼만 뗀다(비었는데 First를 읽으면 null이다)                    long take = Math.Min(k, train.Count);                    var cut = new List<int>();                    for (long r = 0; r < take; r++)                    {                        if (p[0] == "cutf") { cut.Add(train.First!.Value); train.RemoveFirst(); }                        else { cut.Add(train.Last!.Value); train.RemoveLast(); } // 맨 뒤 차량부터                    }                    output.Append(cut.Count == 0 ? "-" : string.Join(" ", cut)).Append('\n');                    break;                case "rot":                    if (train.Count > 0)                    {                        long r = k % train.Count; // 한 바퀴 돌면 제자리다                        for (long s = 0; s < r; s++)                        {                            var node = train.First!;                            train.RemoveFirst();                            train.AddLast(node); // 마디를 그대로 옮긴다                        }                    }                    break;            }        }        output.Append(train.Count).Append('\n');        output.Append(train.Count == 0 ? "-" : string.Join(" ", train)).Append('\n');        Console.Write(output);    }}

C++main.cpp · 45 lines

#include <algorithm>#include <deque>#include <iostream>#include <string> int main() {    std::ios::sync_with_stdio(false);    int n;    std::cin >> n;    std::deque<int> train; // 앞뒤 어느 쪽에서도 넣고 빼는 데 O(1)    for (int i = 0; i < n; i++) {        std::string op;        long long k;        std::cin >> op >> k;        if (op == "addf") {            train.push_front((int)k);        } else if (op == "addb") {            train.push_back((int)k);        } else if (op == "cutf" || op == "cutb") {            // 빈 deque에서 front()·pop_front()는 정의되지 않은 동작이라, 있는 만큼만 뗀다            long long take = std::min(k, (long long)train.size());            if (take == 0) std::cout << '-';            for (long long r = 0; r < take; r++) {                if (r > 0) std::cout << ' ';                if (op == "cutf") {                    std::cout << train.front(); // pop_front()는 값을 돌려주지 않는다                    train.pop_front();                } else {                    std::cout << train.back(); // 뗀 차례: 맨 뒤 차량부터                    train.pop_back();                }            }            std::cout << '\n';        } else if (op == "rot") {            if (!train.empty()) {                long long r = k % (long long)train.size(); // 한 바퀴 돌면 제자리다                // [begin, begin + r)이 끝으로 간다: 앞의 r개가 뒤로                std::rotate(train.begin(), train.begin() + r, train.end());            }        }    }    std::cout << train.size() << '\n';    if (train.empty()) std::cout << "-\n";    for (std::size_t i = 0; i < train.size(); i++) std::cout << train[i] << (i + 1 < train.size() ? ' ' : '\n');}