A long horizontal paper strip is divided into n cells, and the cells carry the numbers 1, 2, …, n from the left.
When the strip is folded, several cells pile up at one position. The length of the strip is its number of positions; at first every position holds one cell, so the length is n.
A fold k takes the line between the k-th and the (k + 1)-th position from the left as the crease, lifts the left k positions as a whole and flips them over to the right.
The position that was d-th to the left of the crease then lands on top of the position that is d-th to the right of the crease. Because it is flipped over, the cells piled at the position that came over are in reversed bottom-to-top order, and they lie above the cells of the position underneath.
If there is no position on the right to carry it, the cells that came over form that position by themselves.
After the fold, the position just right of the crease is the new 1st position. If the length before the fold is L, the length after it is the larger of k and L - k.
For example, folding a strip with n = 5 by k = 2 gives length 3, and the positions hold, from the bottom, 3 2, 4 1 and 5.
Do the q folds in the given order and print what the strip looks like.
Input
The first line has n and q separated by one space. The second line has the q values of k in folding order, separated by one space. 2 ≤ n ≤ 1,000, 1 ≤ q ≤ n - 1. Each k is at least 1 and smaller than the length of the strip at that moment
Output
On the first line print the final length of the strip. Then, from the leftmost position, print one position per line: the numbers of the cells piled there from the bottom cell to the top cell, separated by one space
Example 1 · stdin
5 2
2 2
stdout
2
5 1 4
2 3
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
One fold reverses things at two levels: the order of the positions that go over, and the bottom-to-top order of the cells in each of them. Whether the reversing tool gives a new list or changes the original in place differs by language. Python's s[::-1] gives a new list, while s.reverse() reverses in place and returns None. reversed(s) gives an iterator, not a list, so joining it to a list with + is a TypeError. JS/TS reverse() reverses in place and returns the same array, so the solution reverses a copy made with slice() or [...a] (toReversed() gives a new array). Java's Collections.reverse, C#'s List.Reverse(), C++'s std::reverse and Craykon's Reverse() all reverse in place and return nothing. So the part that goes over is copied first: Java uses new ArrayList<>(strip.subList(0, k)) (a bare subList is a view of the original, so the original would be reversed), C# uses GetRange and Craykon uses GetRange. C++ can also read from the back without copying through rbegin()/rend(). C has no list, so all cells sit one after another in one array, and a position that came over is read from the back while it is written into a new array. Trap one: in JS, getting the part that goes over with strip.reverse().slice(L - k) reverses strip itself. The right part taken afterwards with strip.slice(k) is then the wrong positions, and the first line of the example becomes 3 2 1 2 instead of 5 1 4. Trap two: reversing only the order of the positions and not the order inside each position turns the example into 5 4 1 and 3 2. It does not show in the first fold, where every position has one cell, and goes wrong in the second. Trap three: in Python stack + left[d].reverse() tries to join None and stops with a TypeError.
Pythonmain.py · 22 lines
import syslines = sys.stdin.read().split("\n")n, q = map(int, lines[0].split())folds = list(map(int, lines[1].split()))strip = [[i] for i in range(1, n + 1)] # 자리마다 쌓인 칸들(아래 → 위)for k in folds: length = len(strip) left = strip[:k][::-1] # 넘어가는 쪽: 접는 선에 가까운 자리부터 (새 목록) right = strip[k:] folded = [] for d in range(max(k, length - k)): stack = right[d] if d < length - k else [] if d < k: stack = stack + left[d][::-1] # 뒤집혀 얹히므로 위아래 차례도 거꾸로 folded.append(stack) strip = foldedout = [str(len(strip))]out += [" ".join(map(str, stack)) for stack in strip]print("\n".join(out))
JavaScriptmain.js · 23 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n] = lines[0].trim().split(" ").map(Number);const folds = lines[1].trim().split(" ").map(Number);let strip = []; // 자리마다 쌓인 칸들(아래 → 위)for (let i = 1; i <= n; i++) strip.push([i]);for (const k of folds) { const length = strip.length; // reverse()는 제자리에서 뒤집으므로, slice()로 떼어 낸 복사본을 뒤집는다 const left = strip.slice(0, k).reverse(); const right = strip.slice(k); const folded = []; for (let d = 0; d < Math.max(k, length - k); d++) { let stack = d < length - k ? right[d] : []; if (d < k) stack = stack.concat([...left[d]].reverse()); // 위아래 차례도 거꾸로 folded.push(stack); } strip = folded;}const out = [String(strip.length)];for (const stack of strip) out.push(stack.join(" "));console.log(out.join("\n"));
TypeScriptmain.ts · 25 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n]: number[] = lines[0].trim().split(" ").map(Number);const folds: number[] = lines[1].trim().split(" ").map(Number);let strip: number[][] = []; // 자리마다 쌓인 칸들(아래 → 위)for (let i = 1; i <= n; i++) strip.push([i]);for (const k of folds) { const length: number = strip.length; // reverse()는 제자리에서 뒤집으므로, slice()로 떼어 낸 복사본을 뒤집는다 const left: number[][] = strip.slice(0, k).reverse(); const right: number[][] = strip.slice(k); const folded: number[][] = []; for (let d = 0; d < Math.max(k, length - k); d++) { let stack: number[] = d < length - k ? right[d] : []; if (d < k) stack = stack.concat([...left[d]].reverse()); // 위아래 차례도 거꾸로 folded.push(stack); } strip = folded;}const out: string[] = [String(strip.length)];for (const stack of strip) out.push(stack.join(" "));console.log(out.join("\n"));
JavaMain.java · 53 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Collections;import java.util.List;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 q = Integer.parseInt(st.nextToken()); st = new StringTokenizer(in.readLine()); List<List<Integer>> strip = new ArrayList<>(); // 자리마다 쌓인 칸들(아래 → 위) for (int i = 1; i <= n; i++) { List<Integer> one = new ArrayList<>(); one.add(i); strip.add(one); } for (int f = 0; f < q; f++) { int k = Integer.parseInt(st.nextToken()); int length = strip.size(); // subList는 원본을 들여다보는 창이라, 새 목록으로 복사한 뒤에 뒤집는다 List<List<Integer>> left = new ArrayList<>(strip.subList(0, k)); Collections.reverse(left); List<List<Integer>> folded = new ArrayList<>(); for (int d = 0; d < Math.max(k, length - k); d++) { List<Integer> stack = d < length - k ? strip.get(k + d) : new ArrayList<>(); if (d < k) { List<Integer> top = left.get(d); Collections.reverse(top); // 위아래 차례도 거꾸로 stack.addAll(top); } folded.add(stack); } strip = folded; } StringBuilder out = new StringBuilder(); out.append(strip.size()).append('\n'); for (List<Integer> stack : strip) { for (int i = 0; i < stack.size(); i++) { if (i > 0) out.append(' '); out.append(stack.get(i)); } out.append('\n'); } System.out.print(out); }}
C#Main.cs · 42 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]); string[] folds = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); var strip = new List<List<int>>(); // 자리마다 쌓인 칸들(아래 → 위) for (int i = 1; i <= n; i++) strip.Add(new List<int> { i }); foreach (string token in folds) { int k = int.Parse(token); int length = strip.Count; // GetRange는 새 목록을 주고, Reverse()는 그 목록을 제자리에서 뒤집는다 List<List<int>> left = strip.GetRange(0, k); left.Reverse(); var folded = new List<List<int>>(); for (int d = 0; d < Math.Max(k, length - k); d++) { List<int> stack = d < length - k ? strip[k + d] : new List<int>(); if (d < k) { List<int> top = left[d]; top.Reverse(); // 위아래 차례도 거꾸로 stack.AddRange(top); } folded.Add(stack); } strip = folded; } var sb = new StringBuilder(); sb.Append(strip.Count).Append('\n'); foreach (List<int> stack in strip) sb.Append(string.Join(" ", stack)).Append('\n'); Console.Write(sb); }}
C++main.cpp · 36 lines
#include <algorithm>#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<vector<int>> strip(n); // 자리마다 쌓인 칸들(아래 → 위) for (int i = 0; i < n; i++) strip[i].push_back(i + 1); for (int f = 0; f < q; f++) { int k; cin >> k; int length = (int)strip.size(); // 넘어가는 쪽을 복사한 뒤 std::reverse로 제자리에서 뒤집는다 vector<vector<int>> left(strip.begin(), strip.begin() + k); reverse(left.begin(), left.end()); vector<vector<int>> folded; for (int d = 0; d < max(k, length - k); d++) { vector<int> stack; if (d < length - k) stack = strip[k + d]; // rbegin/rend: 복사하지 않고 뒤에서부터 읽는다 (위아래 차례도 거꾸로) if (d < k) stack.insert(stack.end(), left[d].rbegin(), left[d].rend()); folded.push_back(stack); } strip = folded; } cout << strip.size() << '\n'; for (const auto &stack : strip) { for (size_t i = 0; i < stack.size(); i++) cout << (i ? " " : "") << stack[i]; cout << '\n'; } return 0;}
Cmain.c · 46 lines
#include <stdio.h>#define MAXN 1000/* 모든 칸을 한 배열에 자리 차례로 이어 적고, start[p]에 p번 자리의 칸이 시작하는 곳을 둔다. 접을 때마다 다른 배열에 새로 적고 두 배열을 번갈아 쓴다. */static int cells[2][MAXN];static int start[2][MAXN + 1];int main(void) { int n, q; scanf("%d %d", &n, &q); int cur = 0, length = n; for (int i = 0; i < n; i++) { cells[0][i] = i + 1; start[0][i] = i; } start[0][n] = n; for (int f = 0; f < q; f++) { int k; scanf("%d", &k); int nxt = 1 - cur; int newLength = k > length - k ? k : length - k; int w = 0; for (int d = 0; d < newLength; d++) { start[nxt][d] = w; if (d < length - k) { /* 그대로 있는 쪽: 차례대로 옮겨 적는다 */ for (int i = start[cur][k + d]; i < start[cur][k + d + 1]; i++) cells[nxt][w++] = cells[cur][i]; } if (d < k) { /* 넘어온 쪽: 뒤에서부터 읽어 거꾸로 얹는다 */ for (int i = start[cur][k - d] - 1; i >= start[cur][k - 1 - d]; i--) cells[nxt][w++] = cells[cur][i]; } } start[nxt][newLength] = w; cur = nxt; length = newLength; } printf("%d\n", length); for (int p = 0; p < length; p++) { for (int i = start[cur][p]; i < start[cur][p + 1]; i++) { printf(i > start[cur][p] ? " %d" : "%d", cells[cur][i]); } printf("\n"); } return 0;}
Craykonmain.cray · 43 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];folds = Console.ReadNumbers();// 자리마다 쌓인 칸들(아래 → 위)strip = [];for (i = 1; i <= n; i++){ strip.Add([i]);}foreach (k in folds){ length = strip.Count; // 부분목록은 새 목록을 주고, 뒤집기는 그 목록을 제자리에서 뒤집는다 left = strip.GetRange(0, k); left.Reverse(); folded = []; for (d = 0; d < Mathf.Max(k, length - k); d++) { stack = []; if (d < length - k) { stack = strip[k + d]; } if (d < k) { // 위아래 차례도 거꾸로 top = left[d]; top.Reverse(); foreach (v in top) { stack.Add(v); } } folded.Add(stack); } strip = folded;}Console.WriteLine(strip.Count);foreach (stack in strip){ Console.WriteLine(stack);}