横に長い紙テープが n マスに分かれていて、マスには左から 1, 2, …, n が書かれている。 テープを折ると、いくつかのマスが 1 つの位置に重なって積まれる。 テープの長さは位置の数であり、はじめはどの位置にもマスが 1 つずつあるので長さは n である。 折り k は、左から k 番目の位置と k + 1 番目の位置の間を折り目として、左の k 個の位置をまとめて持ち上げ、右へ裏返してかぶせることである。 すると、折り目から左へ d 番目だった位置が、折り目から右へ d 番目の位置の上に載る。 裏返して載るので、移ってきた位置に積まれていたマスは上下の順が逆になり、下で受ける位置のマスの上に重なる。 右側に受ける位置がなければ、移ってきたマスだけでその位置になる。 折ったあとは、折り目のすぐ右の位置が新しい 1 番目の位置である。 折る前の長さが L なら、折ったあとの長さは k と L - k の大きいほうである。 たとえば n = 5 のテープを k = 2 で折ると長さは 3 で、各位置には下から 3 2、4 1、5 が積まれている。 折り q 回を与えられた順に行ったあとのテープの様子を出力せよ。
入力
1 行目に n と q が空白 1 つで区切られて与えられる。 2 行目に折りの k が q 個、折る順に空白 1 つで区切られて与えられる。 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);}