A photographer lines up n students in one row for a class photo. Each student has a class number, and swapping two students of the same class counts as the same lineup.
So a lineup is described by one sequence of class numbers.
Arrange all possible lineups in dictionary order. Compare two lineups from the front: the one with the smaller number at the first differing position comes first.
This order wraps around like a ring. After the very last lineup (numbers never increasing) comes the very first lineup (numbers never decreasing), and before the very first lineup comes the very last.
From the current lineup, if m is positive, move to the next lineup m times; if m is negative, move back to the previous lineup −m times. If m is 0, stay.
Print the lineup you reach.
Write finding the next lineup and finding the previous lineup as two functions, each changing one sequence in place.
Input
First line T (1 ≤ T ≤ 10). Then two lines per lineup: n and m (1 ≤ n ≤ 1000, −200 ≤ m ≤ 200), then n class numbers (1 ≤ number ≤ 100)
Output
One line per lineup: the n class numbers after moving, separated by single spaces
Example 1 · stdin
4
3 1
1 3 2
3 2
3 2 1
3 -1
1 2 2
3 -2
1 3 2
stdout
2 1 3
1 3 2
2 2 1
3 2 1
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
The next lineup takes three steps. Scanning from the back, find the first i with a[i] < a[i+1], swap a[i] with the last a[j] after it that is greater than a[i], then reverse from i+1 to the end. After the swap the back part is always in decreasing order, so reversing it, without sorting, gives its smallest form. If there is no such i (everything decreases), it is the last lineup, and reversing the whole sequence gives the first. The previous lineup flips every comparison: find the first i with a[i] > a[i+1], swap it with the last number after it that is smaller than a[i], then reverse the back part. If there is no such i (everything rises), it is the first lineup, and reversing the whole gives the last. Reversing only a part differs by language. C++ std::reverse(a.begin() + i + 1, a.end()) takes a half-open range, and the standard library's std::next_permutation/std::prev_permutation do the whole job (at an end they turn the sequence into the other end and return false). The third argument of C# Array.Reverse(a, start, count) is a count, so passing the end index goes out of range and throws ArgumentException. Java's Collections.reverse(list.subList(i + 1, n)) reverses the original list, but there is none for int[], so you swap the two ends while closing in. C does the same. Craykon's list.Reverse() reverses only the whole list, so a range is reversed with a while loop that swaps the two ends. Six traps: (1) Python a[i + 1:].reverse() and JS/TS a.slice(i + 1).reverse() reverse a copy, leaving a unchanged. In Python put it back with a[i + 1:] = a[i + 1:][::-1]. (2) Stopping the rise search at a[i] > a[i+1] treats equal numbers (2 2) as a rise, so with repeated class numbers lineups get skipped or repeated. On equal you must keep moving left (>=); for the previous lineup likewise (<=). (3) Searching for the number to swap from just after i toward the end swaps with the first greater number met rather than the one just above, skipping several lineups. (4) Doing nothing at the last lineup never wraps around to the first. (5) Copying the next-lineup function for the previous one but keeping "swap with a greater number" gives a wrong lineup. (6) A plain for (k = 0; k < m; k++) never runs when m is negative.
Pythonmain.py · 38 lines
def next_lineup(a): """a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로).""" i = len(a) - 2 while i >= 0 and a[i] >= a[i + 1]: # 뒤에서부터 처음으로 오르는 곳 i -= 1 if i < 0: # 모두 내려가면 마지막 줄 세우기 → 뒤집으면 첫 줄 세우기 a.reverse() return j = len(a) - 1 while a[j] <= a[i]: # a[i]보다 큰 수 가운데 가장 뒤의 것 j -= 1 a[i], a[j] = a[j], a[i] a[i + 1:] = a[i + 1:][::-1] # 뒤쪽 구간만 제자리에서 뒤집는다def prev_lineup(a): """a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다.""" i = len(a) - 2 while i >= 0 and a[i] <= a[i + 1]: # 뒤에서부터 처음으로 내려가는 곳 i -= 1 if i < 0: # 모두 오르면 첫 줄 세우기 → 뒤집으면 마지막 줄 세우기 a.reverse() return j = len(a) - 1 while a[j] >= a[i]: # a[i]보다 작은 수 가운데 가장 뒤의 것 j -= 1 a[i], a[j] = a[j], a[i] a[i + 1:] = a[i + 1:][::-1]t = int(input())for _ in range(t): n, m = map(int, input().split()) a = list(map(int, input().split())) step = next_lineup if m > 0 else prev_lineup # m이 음수면 |m|번 앞으로 for _ in range(abs(m)): step(a) print(*a)
JavaScriptmain.js · 48 lines
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 구간 [lo, hi]를 제자리에서 뒤집는다function reverseRange(a, lo, hi) { for (; lo < hi; lo++, hi--) [a[lo], a[hi]] = [a[hi], a[lo]];}// a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)function nextLineup(a) { let i = a.length - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳 if (i < 0) { a.reverse(); // 모두 내려가면 마지막 → 뒤집으면 첫 줄 세우기 return; } let j = a.length - 1; while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것 [a[i], a[j]] = [a[j], a[i]]; reverseRange(a, i + 1, a.length - 1);}// a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다function prevLineup(a) { let i = a.length - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳 if (i < 0) { a.reverse(); // 모두 오르면 첫 줄 세우기 → 뒤집으면 마지막 return; } let j = a.length - 1; while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것 [a[i], a[j]] = [a[j], a[i]]; reverseRange(a, i + 1, a.length - 1);}let p = 0;const t = data[p++];const out = [];for (let c = 0; c < t; c++) { const n = data[p++]; const m = data[p++]; const a = data.slice(p, p + n); p += n; const step = m > 0 ? nextLineup : prevLineup; // m이 음수면 |m|번 앞으로 for (let k = 0; k < Math.abs(m); k++) step(a); out.push(a.join(" "));}console.log(out.join("\n"));
TypeScriptmain.ts · 49 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 구간 [lo, hi]를 제자리에서 뒤집는다function reverseRange(a: number[], lo: number, hi: number): void { for (; lo < hi; lo++, hi--) [a[lo], a[hi]] = [a[hi], a[lo]];}// a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)function nextLineup(a: number[]): void { let i = a.length - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳 if (i < 0) { a.reverse(); // 모두 내려가면 마지막 → 뒤집으면 첫 줄 세우기 return; } let j = a.length - 1; while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것 [a[i], a[j]] = [a[j], a[i]]; reverseRange(a, i + 1, a.length - 1);}// a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다function prevLineup(a: number[]): void { let i = a.length - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳 if (i < 0) { a.reverse(); // 모두 오르면 첫 줄 세우기 → 뒤집으면 마지막 return; } let j = a.length - 1; while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것 [a[i], a[j]] = [a[j], a[i]]; reverseRange(a, i + 1, a.length - 1);}let p = 0;const t = data[p++];const out: string[] = [];for (let c = 0; c < t; c++) { const n = data[p++]; const m = data[p++]; const a = data.slice(p, p + n); p += n; const step = m > 0 ? nextLineup : prevLineup; // m이 음수면 |m|번 앞으로 for (let k = 0; k < Math.abs(m); k++) step(a); out.push(a.join(" "));}console.log(out.join("\n"));
JavaMain.java · 64 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static void swap(int[] a, int x, int y) { int tmp = a[x]; a[x] = a[y]; a[y] = tmp; } // 구간 [lo, hi]를 제자리에서 뒤집는다 static void reverseRange(int[] a, int lo, int hi) { for (; lo < hi; lo++, hi--) swap(a, lo, hi); } // a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로) static void nextLineup(int[] a) { int i = a.length - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳 if (i < 0) { reverseRange(a, 0, a.length - 1); // 마지막 → 뒤집으면 첫 줄 세우기 return; } int j = a.length - 1; while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것 swap(a, i, j); reverseRange(a, i + 1, a.length - 1); } // a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다 static void prevLineup(int[] a) { int i = a.length - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳 if (i < 0) { reverseRange(a, 0, a.length - 1); // 첫 줄 세우기 → 뒤집으면 마지막 return; } int j = a.length - 1; while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것 swap(a, i, j); reverseRange(a, i + 1, a.length - 1); } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int c = 0; c < t; c++) { StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int[] a = new int[n]; st = new StringTokenizer(in.readLine()); for (int k = 0; k < n; k++) a[k] = Integer.parseInt(st.nextToken()); for (int k = 0; k < m; k++) nextLineup(a); for (int k = 0; k < -m; k++) prevLineup(a); // m이 음수면 |m|번 앞으로 for (int k = 0; k < n; k++) out.append(k > 0 ? " " : "").append(a[k]); out.append('\n'); } System.out.print(out); }}
C#Main.cs · 55 lines
using System;using System.Linq;using System.Text;class Program{ // a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로) static void NextLineup(int[] a) { int i = a.Length - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳 if (i < 0) { Array.Reverse(a); // 마지막 → 뒤집으면 첫 줄 세우기 return; } int j = a.Length - 1; while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것 (a[i], a[j]) = (a[j], a[i]); // Array.Reverse(배열, 시작, 개수) — 셋째 값은 끝 자리가 아니라 개수다 Array.Reverse(a, i + 1, a.Length - (i + 1)); } // a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다 static void PrevLineup(int[] a) { int i = a.Length - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳 if (i < 0) { Array.Reverse(a); // 첫 줄 세우기 → 뒤집으면 마지막 return; } int j = a.Length - 1; while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것 (a[i], a[j]) = (a[j], a[i]); Array.Reverse(a, i + 1, a.Length - (i + 1)); } static void Main() { int t = int.Parse(Console.ReadLine()!.Trim()); var output = new StringBuilder(); for (int c = 0; c < t; c++) { int[] nm = Console.ReadLine()!.Trim().Split(' ').Select(int.Parse).ToArray(); int[] a = Console.ReadLine()!.Trim().Split(' ').Select(int.Parse).ToArray(); int m = nm[1]; for (int k = 0; k < m; k++) NextLineup(a); for (int k = 0; k < -m; k++) PrevLineup(a); // m이 음수면 |m|번 앞으로 output.Append(string.Join(" ", a)).Append('\n'); } Console.Write(output); }}
C++main.cpp · 49 lines
#include <algorithm>#include <iostream>#include <vector>// a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)// (표준 라이브러리 std::next_permutation이 바로 이 일을 한다 — 여기서는 직접 쓴다)void nextLineup(std::vector<int>& a) { int i = (int)a.size() - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳 if (i < 0) { std::reverse(a.begin(), a.end()); // 마지막 → 뒤집으면 첫 줄 세우기 return; } int j = (int)a.size() - 1; while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것 std::swap(a[i], a[j]); std::reverse(a.begin() + i + 1, a.end()); // [시작, 끝) 반열린 구간}// a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다// (std::prev_permutation이 이 일을 한다)void prevLineup(std::vector<int>& a) { int i = (int)a.size() - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳 if (i < 0) { std::reverse(a.begin(), a.end()); // 첫 줄 세우기 → 뒤집으면 마지막 return; } int j = (int)a.size() - 1; while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것 std::swap(a[i], a[j]); std::reverse(a.begin() + i + 1, a.end());}int main() { std::ios::sync_with_stdio(false); int t; std::cin >> t; while (t--) { int n, m; std::cin >> n >> m; std::vector<int> a(n); for (int& x : a) std::cin >> x; for (int k = 0; k < m; k++) nextLineup(a); for (int k = 0; k < -m; k++) prevLineup(a); // m이 음수면 |m|번 앞으로 for (int k = 0; k < n; k++) std::cout << (k ? " " : "") << a[k]; std::cout << '\n'; }}
Cmain.c · 56 lines
#include <stdio.h>static void swap(int *x, int *y) { int tmp = *x; *x = *y; *y = tmp;}/* 구간 [lo, hi]를 제자리에서 뒤집는다 */static void reverse_range(int *a, int lo, int hi) { for (; lo < hi; lo++, hi--) swap(&a[lo], &a[hi]);}/* a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로) */static void next_lineup(int *a, int n) { int i = n - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; /* 뒤에서부터 처음으로 오르는 곳 */ if (i < 0) { reverse_range(a, 0, n - 1); /* 마지막 → 뒤집으면 첫 줄 세우기 */ return; } int j = n - 1; while (a[j] <= a[i]) j--; /* a[i]보다 큰 수 가운데 가장 뒤의 것 */ swap(&a[i], &a[j]); reverse_range(a, i + 1, n - 1);}/* a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다 */static void prev_lineup(int *a, int n) { int i = n - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; /* 뒤에서부터 처음으로 내려가는 곳 */ if (i < 0) { reverse_range(a, 0, n - 1); /* 첫 줄 세우기 → 뒤집으면 마지막 */ return; } int j = n - 1; while (a[j] >= a[i]) j--; /* a[i]보다 작은 수 가운데 가장 뒤의 것 */ swap(&a[i], &a[j]); reverse_range(a, i + 1, n - 1);}int main(void) { int t; scanf("%d", &t); static int a[1000]; while (t--) { int n, m; scanf("%d %d", &n, &m); for (int k = 0; k < n; k++) scanf("%d", &a[k]); for (int k = 0; k < m; k++) next_lineup(a, n); for (int k = 0; k < -m; k++) prev_lineup(a, n); /* m이 음수면 |m|번 앞으로 */ for (int k = 0; k < n; k++) printf(k ? " %d" : "%d", a[k]); printf("\n"); } return 0;}
Craykonmain.cray · 77 lines
// 구간 [lo, hi]를 제자리에서 뒤집는다(목록.뒤집기()는 목록 전체만 뒤집는다)구간뒤집기(a, lo, hi){ while (lo < hi) { tmp = a[lo]; a[lo] = a[hi]; a[hi] = tmp; lo += 1; hi -= 1; }}// a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)다음줄(a){ i = a.Count - 2; while (i >= 0 && a[i] >= a[i + 1]) { i -= 1; } if (i < 0) { a.Reverse(); // 마지막 → 뒤집으면 첫 줄 세우기 return; } j = a.Count - 1; while (a[j] <= a[i]) { j -= 1; } tmp = a[i]; a[i] = a[j]; a[j] = tmp; 구간뒤집기(a, i + 1, a.Count - 1);}// a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다앞줄(a){ i = a.Count - 2; while (i >= 0 && a[i] <= a[i + 1]) { i -= 1; } if (i < 0) { a.Reverse(); // 첫 줄 세우기 → 뒤집으면 마지막 return; } j = a.Count - 1; while (a[j] >= a[i]) { j -= 1; } tmp = a[i]; a[i] = a[j]; a[j] = tmp; 구간뒤집기(a, i + 1, a.Count - 1);}t = Console.ReadLine().Trim().ToNumber();for (c = 0; c < t; c++){ nm = Console.ReadNumbers(); a = Console.ReadNumbers(); m = nm[1]; for (k = 0; k < m; k++) { 다음줄(a); } for (k = 0; k < -m; k++) { 앞줄(a); } Console.WriteLine(a.Join(" "));}