一条横放的长纸带分成 n 格，格子上从左到右写着 1, 2, …, n。 把纸带折起来，会有几格叠在同一个位置上。 纸带的长度是位置的个数；一开始每个位置只有一格，所以长度是 n。 折法 k 是：以从左数第 k 个位置和第 k + 1 个位置之间为折线，把左边 k 个位置整个拿起来，向右翻过去盖上。 这样，原来在折线左边第 d 个的位置，会落在折线右边第 d 个位置的上面。 因为是翻过去的，翻过来的那个位置上叠着的格子上下顺序会颠倒，并叠在下面那个位置的格子之上。 如果右边没有位置托住它，翻过来的格子就单独成为那个位置。 折完以后，折线右边紧挨着的位置是新的第 1 个位置。 折之前长度是 L 的话，折之后的长度是 k 和 L - k 中较大的那个。 例如把 n = 5 的纸带按 k = 2 折，长度是 3，各个位置从下往上叠着 3 2、4 1、5。 按给出的顺序折 q 次，输出纸带最后的样子。
输入
第一行给出 n 和 q，用一个空格隔开。 第二行按折的顺序给出 q 个 k，用一个空格隔开。 2 ≤ n ≤ 1,000，1 ≤ q ≤ n - 1。 每个 k 不小于 1，并且小于当时纸带的长度
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 行
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 行
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 行
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 行
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 行
#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 行
#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 行
첫줄 = 控制台.读数字();n = 첫줄[0];folds = 控制台.读数字();// 자리마다 쌓인 칸들(아래 → 위)strip = [];循环 (i = 1; i <= n; i++){ strip.添加([i]);}遍历 (k 在 folds){ length = strip.数量; // 부분목록은 새 목록을 주고, 뒤집기는 그 목록을 제자리에서 뒤집는다 left = strip.子列表(0, k); left.反转(); folded = []; 循环 (d = 0; d < 数学.较大值(k, length - k); d++) { stack = []; 如果 (d < length - k) { stack = strip[k + d]; } 如果 (d < k) { // 위아래 차례도 거꾸로 top = left[d]; top.反转(); 遍历 (v 在 top) { stack.添加(v); } } folded.添加(stack); } strip = folded;}控制台.输出(strip.数量);遍历 (stack 在 strip){ 控制台.输出(stack);}