A classroom has n seats in one row, numbered 1, 2, …, n from the left.
The first line gives n, and the second line gives the names of the n students in their starting seats, in seat order, separated by single spaces.
The third line gives the number of swaps m, and each of the next m lines gives one swap "i j". The homeroom teacher performs the swaps in the given order.
A swap "i j" makes the student in seat i and the student in seat j trade places.
If i and j are equal, nothing happens.
After all swaps, print on the first line the student names in seat order, separated by single spaces.
On the second line print k, the number of students whose final seat differs from their starting seat.
Then print k lines, one per such student, as "name startSeat finalSeat" separated by single spaces.
These k lines are ordered by starting seat number, smallest first.
A student who moved several times but ended in the starting seat is not counted.
If k is 0, the output ends with the 0 on the second line.
Input
1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000, 1 ≤ i, j ≤ n. Names are 1 to 10 lowercase English letters and all different
Output
First line: names in final seat order. Second line: k. Then k lines "name startSeat finalSeat"
Example 1 · stdin
5
mina joon sora dan kai
3
1 3
2 5
3 1
stdout
mina kai sora dan joon
2
joon 2 5
kai 5 2
Example 2 · stdin
3
ari bo cy
3
1 2
2 3
3 1
stdout
ari cy bo
2
bo 2 3
cy 3 2
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
To keep the starting seats you must copy the list before swapping. Trap one: start = seats is not a copy: it puts a second name on the same list, so every swap shows through both names and the number of moved students always comes out 0. Lists and arrays in Python, JS, TS, Java and C#, and Craykon lists, all share like this. How to copy: Python seats[:] or list(seats), JS/TS [...seats] or slice(), Java seats.clone(), C# (string[])seats.Clone(), Craykon seats.GetRange(0, seats.Count) (Korean 부분목록, 개수). Only C++ std::vector copies every element on =; C arrays cannot be assigned with = at all, so you copy them with memcpy or strcpy. Swapping two cells: Python a[i], a[j] = a[j], a[i], JS/TS [a[i], a[j]] = [a[j], a[i]], a C# tuple (a[i], a[j]) = (a[j], a[i]), C++ std::swap(a[i], a[j]); Java, C and Craykon use a temporary tmp (three strcpy calls for C strings). Trap two: writing a[i] = a[j]; a[j] = a[i]; without a temporary overwrites a[i] on the first line, so both cells end up with the same name. To find each student's final seat, build a name → seat map once instead of searching again for every student.
Pythonmain.py · 19 lines
import sysdata = sys.stdin.read().split()n = int(data[0])seats = data[1:1 + n]start = seats[:] # 처음 자리를 따로 복사해 둔다(start = seats 는 같은 목록에 이름만 둘)m = int(data[1 + n])pos = 2 + nfor _ in range(m): i, j = int(data[pos]) - 1, int(data[pos + 1]) - 1 pos += 2 seats[i], seats[j] = seats[j], seats[i]now = {name: k for k, name in enumerate(seats)}moved = [(name, k + 1, now[name] + 1) for k, name in enumerate(start) if now[name] != k]print(" ".join(seats))print(len(moved))for name, a, b in moved: print(name, a, b)
JavaScriptmain.js · 20 lines
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const n = Number(data[0]);const seats = data.slice(1, 1 + n);const start = [...seats]; // 복사본. const start = seats 는 같은 배열을 가리킨다const m = Number(data[1 + n]);let pos = 2 + n;for (let k = 0; k < m; k++, pos += 2) { const i = Number(data[pos]) - 1; const j = Number(data[pos + 1]) - 1; [seats[i], seats[j]] = [seats[j], seats[i]];}const now = new Map(seats.map((name, k) => [name, k]));const out = [seats.join(" ")];const moved = [];start.forEach((name, k) => { if (now.get(name) !== k) moved.push(`${name} ${k + 1} ${now.get(name) + 1}`);});out.push(String(moved.length), ...moved);console.log(out.join("\n"));
TypeScriptmain.ts · 22 lines
import { readFileSync } from "node:fs";const data: string[] = readFileSync(0, "utf8").trim().split(/\s+/);const n = Number(data[0]);const seats: string[] = data.slice(1, 1 + n);const start: string[] = [...seats]; // 복사본. const start = seats 는 같은 배열을 가리킨다const m = Number(data[1 + n]);let pos = 2 + n;for (let k = 0; k < m; k++, pos += 2) { const i = Number(data[pos]) - 1; const j = Number(data[pos + 1]) - 1; [seats[i], seats[j]] = [seats[j], seats[i]];}const now = new Map<string, number>(seats.map((name, k): [string, number] => [name, k]));const out: string[] = [seats.join(" ")];const moved: string[] = [];start.forEach((name, k) => { const at = now.get(name)!; if (at !== k) moved.push(`${name} ${k + 1} ${at + 1}`);});out.push(String(moved.length), ...moved);console.log(out.join("\n"));
JavaMain.java · 33 lines
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); String[] seats = br.readLine().trim().split(" "); String[] start = seats.clone(); // String[] start = seats; 는 같은 배열을 가리킨다 int m = Integer.parseInt(br.readLine().trim()); for (int k = 0; k < m; k++) { StringTokenizer st = new StringTokenizer(br.readLine()); int i = Integer.parseInt(st.nextToken()) - 1; int j = Integer.parseInt(st.nextToken()) - 1; String tmp = seats[i]; seats[i] = seats[j]; seats[j] = tmp; } Map<String, Integer> now = new HashMap<>(); for (int k = 0; k < n; k++) now.put(seats[k], k); StringBuilder moved = new StringBuilder(); int count = 0; for (int k = 0; k < n; k++) { int at = now.get(start[k]); if (at != k) { count++; moved.append(start[k]).append(' ').append(k + 1).append(' ').append(at + 1).append('\n'); } } System.out.print(String.join(" ", seats) + "\n" + count + "\n" + moved); }}
C#Main.cs · 33 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { int n = int.Parse(Console.ReadLine().Trim()); string[] seats = Console.ReadLine().Trim().Split(' '); string[] start = (string[])seats.Clone(); // string[] start = seats; 는 같은 배열을 가리킨다 int m = int.Parse(Console.ReadLine().Trim()); for (int k = 0; k < m; k++) { string[] p = Console.ReadLine().Trim().Split(' '); int i = int.Parse(p[0]) - 1, j = int.Parse(p[1]) - 1; (seats[i], seats[j]) = (seats[j], seats[i]); } var now = new Dictionary<string, int>(); for (int k = 0; k < n; k++) now[seats[k]] = k; var moved = new List<string>(); for (int k = 0; k < n; k++) { int at = now[start[k]]; if (at != k) moved.Add($"{start[k]} {k + 1} {at + 1}"); } var sb = new StringBuilder(); sb.Append(string.Join(" ", seats)).Append('\n').Append(moved.Count).Append('\n'); foreach (string line in moved) sb.Append(line).Append('\n'); Console.Write(sb); }}
C++main.cpp · 33 lines
#include <iostream>#include <string>#include <unordered_map>#include <utility>#include <vector>int main() { int n, m; std::cin >> n; std::vector<std::string> seats(n); for (auto& s : seats) std::cin >> s; std::vector<std::string> start = seats; // vector는 = 가 통째로 복사한다(참조가 아니다) std::cin >> m; for (int k = 0; k < m; k++) { int i, j; std::cin >> i >> j; std::swap(seats[i - 1], seats[j - 1]); } std::unordered_map<std::string, int> now; for (int k = 0; k < n; k++) now[seats[k]] = k; std::string out, moved; int count = 0; for (int k = 0; k < n; k++) out += (k ? " " : "") + seats[k]; for (int k = 0; k < n; k++) { int at = now[start[k]]; if (at != k) { count++; moved += start[k] + " " + std::to_string(k + 1) + " " + std::to_string(at + 1) + "\n"; } } std::cout << out << "\n" << count << "\n" << moved;}
Cmain.c · 37 lines
#include <stdio.h>#include <string.h>static char seats[1000][11];static char start[1000][11];int main(void) { int n, m; scanf("%d", &n); for (int k = 0; k < n; k++) scanf("%10s", seats[k]); memcpy(start, seats, sizeof seats); /* 배열은 = 로 복사할 수 없다: 칸을 통째로 복사 */ scanf("%d", &m); for (int k = 0; k < m; k++) { int i, j; char tmp[11]; scanf("%d %d", &i, &j); i--, j--; if (i == j) continue; /* 같은 칸끼리 strcpy 하면 겹친 복사라 안 된다 */ strcpy(tmp, seats[i]); strcpy(seats[i], seats[j]); strcpy(seats[j], tmp); } /* 처음 자리마다 지금 자리를 찾는다(n이 1000 이하라 차례로 찾아도 된다) */ static int at[1000]; int count = 0; for (int k = 0; k < n; k++) { for (int t = 0; t < n; t++) if (strcmp(seats[t], start[k]) == 0) { at[k] = t; break; } if (at[k] != k) count++; } for (int k = 0; k < n; k++) printf(k ? " %s" : "%s", seats[k]); printf("\n%d\n", count); for (int k = 0; k < n; k++) if (at[k] != k) printf("%s %d %d\n", start[k], k + 1, at[k] + 1); return 0;}
Craykonmain.cray · 35 lines
n = Console.ReadLine().ToNumber();seats = Console.ReadLine().Trim().Split();// start = seats; 라면 같은 목록에 이름만 둘이다. 부분목록은 새 목록을 만든다start = seats.GetRange(0, seats.Count);m = Console.ReadLine().ToNumber();for (k = 0; k < m; k++){ p = Console.ReadNumbers(); i = p[0] - 1; j = p[1] - 1; tmp = seats[i]; seats[i] = seats[j]; seats[j] = tmp;}now = Dict();for (k = 0; k < n; k++){ now[seats[k]] = k;}moved = [];for (k = 0; k < n; k++){ at = now[start[k]]; if (at != k) { moved.Add(start[k] + " " + (k + 1) + " " + (at + 1)); }}Console.WriteLine(seats.Join(" "));Console.WriteLine(moved.Count);foreach (line in moved){ Console.WriteLine(line);}