n players line up in bracket order and play a tournament.
The first line gives n, and each of the next n lines gives one player's "name strength" in bracket order.
In each round the remaining players are paired from the front, two at a time (1st with 2nd, 3rd with 4th, …), and each pair plays a match.
If an odd number of players remain, the last player advances to the next round without a match, with strength unchanged.
In a match the stronger player wins; with equal strength, the player standing earlier in the pair wins.
The winner gets tired and loses strength equal to the quotient of (loser's strength ÷ 2).
The loser is eliminated, and the next round's line is the winners (and the player who advanced without a match) in the same order as this round.
Rounds repeat until one player remains.
After each round, print the remaining players in order as "name:strength" on one line, separated by single spaces.
On the last line print the remaining player as "champion name".
If n is 1 there are no rounds, so print only the one line "champion name".
Input
1 ≤ n ≤ 1000, 1 ≤ strength ≤ 1,000,000,000 (integers). Names are 1 to 10 lowercase English letters and all different
Output
One line per round (the remaining players as "name:strength"), and "champion name" on the last line
Example 1 · stdin
5
ari 50
bo 70
cy 40
dan 40
eve 90
stdout
bo:45 cy:20 eve:90
bo:35 eve:90
eve:73
champion eve
Example 2 · stdin
2
x 9
y 9
stdout
x:5
champion x
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
This simulation walks the current line two cells at a time, appends each winner to a new list, and swaps in the new list at the end of the round. Stepping by two: Python range(0, len(p), 2), JS/TS/Java/C#/C/C++ i += 2, Craykon for (i = 0; i < n; i = i + 2) (Korean 반복). Appending: Python append, JS/TS push, Java/C# add/Add, C++ push_back, Craykon Add (Korean 넣기). C writes each winner to cell k at the front of the same array, needing no second array (k ≤ i, so it never overwrites a cell not yet read). Trap one: shortening the end to only visit full pairs, as in range(0, len(p) - 1, 2), silently drops the last player when the count is odd. Trap two: "the quotient of ÷ 2" is exactly / between ints in Java, C#, C and C++, but JS/TS / keeps the fraction and gives values like 45.5. Use Math.floor(x / 2); Python uses // and Craykon Mathf.Quot(x, 2) (Korean 수학.몫; Craykon / also gives a fraction). Strength is positive, so truncating and flooring agree. Trap three: on equal strength the earlier player wins, so pick the earlier player with >=; writing > lets the later player win. Strength is at most 10^9 and only goes down, so int is plenty.
Pythonmain.py · 23 lines
import syslines = sys.stdin.read().split("\n")n = int(lines[0])players = []for line in lines[1:1 + n]: name, power = line.split() players.append((name, int(power)))out = []while len(players) > 1: nxt = [] for i in range(0, len(players), 2): if i + 1 == len(players): # 짝이 없는 마지막 선수는 그대로 올라간다 nxt.append(players[i]) continue a, b = players[i], players[i + 1] win, lose = (a, b) if a[1] >= b[1] else (b, a) # 같으면 앞 선수 nxt.append((win[0], win[1] - lose[1] // 2)) players = nxt out.append(" ".join(f"{name}:{power}" for name, power in players))out.append(f"champion {players[0][0]}")print("\n".join(out))
JavaScriptmain.js · 24 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);let players = lines.slice(1, 1 + n).map((line) => { const [name, power] = line.trim().split(" "); return { name, power: Number(power) };});const out = [];while (players.length > 1) { const next = []; for (let i = 0; i < players.length; i += 2) { if (i + 1 === players.length) { next.push(players[i]); // 짝이 없는 마지막 선수는 그대로 올라간다 continue; } const [a, b] = [players[i], players[i + 1]]; const [win, lose] = a.power >= b.power ? [a, b] : [b, a]; // 같으면 앞 선수 next.push({ name: win.name, power: win.power - Math.floor(lose.power / 2) }); // /는 소수가 나온다 } players = next; out.push(players.map((p) => `${p.name}:${p.power}`).join(" "));}out.push(`champion ${players[0].name}`);console.log(out.join("\n"));
TypeScriptmain.ts · 32 lines
import { readFileSync } from "node:fs";interface Player { name: string; power: number;}const lines: string[] = readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);let players: Player[] = lines.slice(1, 1 + n).map((line) => { const [name, power] = line.trim().split(" "); return { name, power: Number(power) };});const out: string[] = [];while (players.length > 1) { const next: Player[] = []; for (let i = 0; i < players.length; i += 2) { if (i + 1 === players.length) { next.push(players[i]); // 짝이 없는 마지막 선수는 그대로 올라간다 continue; } const a = players[i]; const b = players[i + 1]; const [win, lose] = a.power >= b.power ? [a, b] : [b, a]; // 같으면 앞 선수 next.push({ name: win.name, power: win.power - Math.floor(lose.power / 2) }); // /는 소수가 나온다 } players = next; out.push(players.map((p) => `${p.name}:${p.power}`).join(" "));}out.push(`champion ${players[0].name}`);console.log(out.join("\n"));
JavaMain.java · 41 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()); List<String> names = new ArrayList<>(); List<Integer> power = new ArrayList<>(); for (int i = 0; i < n; i++) { String[] p = br.readLine().trim().split(" "); names.add(p[0]); power.add(Integer.parseInt(p[1])); } StringBuilder out = new StringBuilder(); while (names.size() > 1) { List<String> nextNames = new ArrayList<>(); List<Integer> nextPower = new ArrayList<>(); for (int i = 0; i < names.size(); i += 2) { if (i + 1 == names.size()) { // 짝이 없는 마지막 선수는 그대로 올라간다 nextNames.add(names.get(i)); nextPower.add(power.get(i)); continue; } int a = power.get(i), b = power.get(i + 1); int win = a >= b ? i : i + 1; // 같으면 앞 선수 int lose = Math.min(a, b); nextNames.add(names.get(win)); nextPower.add(Math.max(a, b) - lose / 2); // int끼리 /는 몫 } names = nextNames; power = nextPower; StringJoiner sj = new StringJoiner(" "); for (int i = 0; i < names.size(); i++) sj.add(names.get(i) + ":" + power.get(i)); out.append(sj).append('\n'); } out.append("champion ").append(names.get(0)).append('\n'); System.out.print(out); }}
C#Main.cs · 40 lines
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ static void Main() { int n = int.Parse(Console.ReadLine().Trim()); var players = new List<(string Name, int Power)>(); for (int i = 0; i < n; i++) { string[] p = Console.ReadLine().Trim().Split(' '); players.Add((p[0], int.Parse(p[1]))); } var sb = new StringBuilder(); while (players.Count > 1) { var next = new List<(string Name, int Power)>(); for (int i = 0; i < players.Count; i += 2) { if (i + 1 == players.Count) // 짝이 없는 마지막 선수는 그대로 올라간다 { next.Add(players[i]); continue; } var (win, lose) = players[i].Power >= players[i + 1].Power // 같으면 앞 선수 ? (players[i], players[i + 1]) : (players[i + 1], players[i]); next.Add((win.Name, win.Power - lose.Power / 2)); // int끼리 /는 몫 } players = next; sb.Append(string.Join(" ", players.Select(p => $"{p.Name}:{p.Power}"))).Append('\n'); } sb.Append($"champion {players[0].Name}\n"); Console.Write(sb); }}
C++main.cpp · 36 lines
#include <iostream>#include <string>#include <vector>struct Player { std::string name; int power;};int main() { int n; std::cin >> n; std::vector<Player> players(n); for (auto& p : players) std::cin >> p.name >> p.power; std::string out; while (players.size() > 1) { std::vector<Player> next; for (size_t i = 0; i < players.size(); i += 2) { if (i + 1 == players.size()) { // 짝이 없는 마지막 선수는 그대로 올라간다 next.push_back(players[i]); continue; } const Player& a = players[i]; const Player& b = players[i + 1]; const Player& win = a.power >= b.power ? a : b; // 같으면 앞 선수 const Player& lose = a.power >= b.power ? b : a; next.push_back({win.name, win.power - lose.power / 2}); // int끼리 /는 몫 } players = next; for (size_t i = 0; i < players.size(); i++) out += (i ? " " : "") + players[i].name + ":" + std::to_string(players[i].power); out += "\n"; } std::cout << out << "champion " << players[0].name << "\n";}
Cmain.c · 33 lines
#include <stdio.h>#include <string.h>static char name[1000][11];static int power[1000];int main(void) { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%10s %d", name[i], &power[i]); /* 이긴 선수를 같은 배열의 앞쪽에 차례로 당겨 쓴다(k번째 승자는 k번 칸) */ while (n > 1) { int k = 0; for (int i = 0; i < n; i += 2, k++) { int win = i, lose = i + 1; if (i + 1 == n) { /* 짝이 없는 마지막 선수는 그대로 */ strcpy(name[k], name[i]); power[k] = power[i]; continue; } if (power[i + 1] > power[i]) win = i + 1, lose = i; /* 같으면 앞 선수 */ int p = power[win] - power[lose] / 2; if (k != win) strcpy(name[k], name[win]); /* 같은 칸끼리 strcpy 하면 겹친 복사라 안 된다 */ power[k] = p; } n = k; for (int i = 0; i < n; i++) printf(i ? " %s:%d" : "%s:%d", name[i], power[i]); printf("\n"); } printf("champion %s\n", name[0]); return 0;}
Craykonmain.cray · 45 lines
n = Console.ReadLine().ToNumber();names = [];power = [];for (i = 0; i < n; i++){ p = Console.ReadLine().Trim().Split(); names.Add(p[0]); power.Add(p[1].ToNumber());}while (names.Count > 1){ nextNames = []; nextPower = []; for (i = 0; i < names.Count; i = i + 2) { if (i + 1 == names.Count) { // 짝이 없는 마지막 선수는 그대로 올라간다 nextNames.Add(names[i]); nextPower.Add(power[i]); } else { win = i; lose = i + 1; if (power[i + 1] > power[i]) { win = i + 1; // 같으면 앞 선수가 이긴다 lose = i; } nextNames.Add(names[win]); nextPower.Add(power[win] - Mathf.Quot(power[lose], 2)); // 7 / 2는 3.5라 몫을 쓴다 } } names = nextNames; power = nextPower; row = []; for (i = 0; i < names.Count; i++) { row.Add(names[i] + ":" + power[i]); } Console.WriteLine(row.Join(" "));}Console.WriteLine("champion " + names[0]);