목록 돌기목록에 넣기그대로 따라 하기P0180

이길수록 지치는 토너먼트

선수 n명이 대진표 순서대로 줄지어 토너먼트를 한다. 첫 줄에 n이, 다음 n줄에 대진표 순서대로 선수마다 "이름 힘"이 주어진다. 한 판에서는 남은 선수를 앞에서부터 둘씩 짝지어(1번째와 2번째, 3번째와 4번째, …) 경기를 한다. 남은 선수가 홀수 명이면 맨 뒤 선수는 경기 없이 힘이 그대로인 채 다음 판에 오른다. 경기에서는 힘이 큰 선수가 이기고, 힘이 같으면 짝 가운데 앞에 선 선수가 이긴다. 이긴 선수는 지쳐서 힘이 (진 선수의 힘 ÷ 2의 몫)만큼 줄어든다. 진 선수는 떨어지고, 다음 판의 줄은 이긴 선수(와 경기 없이 오른 선수)가 이번 판의 순서 그대로 선다. 선수가 한 명 남을 때까지 판을 되풀이한다. 판이 끝날 때마다, 남은 선수를 순서대로 "이름:힘"으로 빈칸 하나씩 띄워 한 줄에 출력하라. 마지막 줄에는 "champion 이름"으로 남은 한 명을 출력하라. n이 1이면 판이 없으므로 "champion 이름" 한 줄만 출력한다.

입력: 1 ≤ n ≤ 1000, 1 ≤ 힘 ≤ 1,000,000,000(정수).
이름은 영어 소문자 1 ~ 10글자이고 모두 다르다
출력: 판마다 한 줄(남은 선수의 "이름:힘"), 마지막 줄에 "champion 이름"

예시 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

예시 2 · stdin

2
x 9
y 9

stdout

x:5
champion x

main.py 프로그래밍 언어 실행 판

입력(stdin)

실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).

$ 준비됐어요

코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.

다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이

판마다 지금 줄을 두 칸씩 돌며 이긴 선수를 새 목록에 넣고, 다 돌면 새 목록으로 갈아 끼우는 흉내 내기예요.
두 칸씩 도는 법: Python range(0, len(p), 2), JS·TS·Java·C#·C·C++ i += 2, 크레이콘 반복 (i = 0; i < n; i = i + 2).
새 목록에 넣기: Python append, JS·TS push, Java·C# add·Add, C++ push_back, 크레이콘 넣기.
C는 이긴 선수를 같은 배열의 앞쪽 k번 칸에 당겨 써서 새 배열 없이 해요(k ≤ i라 아직 읽을 칸을 덮지 않아요).
함정 하나: 짝만 돌려고 range(0, len(p) - 1, 2)처럼 끝을 하나 줄이면 홀수 명일 때 맨 뒤 선수가 소리 없이 사라져요.
함정 둘: "÷ 2의 몫"은 Java·C#·C·C++ int끼리의 /면 그대로지만, JS·TS /는 소수까지 나눠서 45.5처럼 돼요.
Math.floor(x / 2)를 쓰고, Python은 //, 크레이콘은 수학.몫(x, 2)예요(크레이콘 /도 소수가 나와요).
힘이 양수라 버림과 내림이 같아요.
함정 셋: 힘이 같으면 앞 선수가 이기니 >=로 앞 선수를 고르고, >로 쓰면 뒤 선수가 이겨요.
힘은 10억 이하이고 줄기만 하니 int로 넉넉해요.

Pythonmain.py · 23 줄

import sys lines = 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 줄

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 줄

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 줄

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 줄

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 줄

#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 줄

#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 줄

n = 콘솔.줄읽기().수로변환();names = [];power = [];반복 (i = 0; i < n; i++){    p = 콘솔.줄읽기().공백제거().나누기();    names.넣기(p[0]);    power.넣기(p[1].수로변환());} 동안 (names.개수 > 1){    nextNames = [];    nextPower = [];    반복 (i = 0; i < names.개수; i = i + 2)    {        만약 (i + 1 == names.개수)        {            // 짝이 없는 마지막 선수는 그대로 올라간다            nextNames.넣기(names[i]);            nextPower.넣기(power[i]);        }        아니면        {            win = i;            lose = i + 1;            만약 (power[i + 1] > power[i])            {                win = i + 1; // 같으면 앞 선수가 이긴다                lose = i;            }            nextNames.넣기(names[win]);            nextPower.넣기(power[win] - 수학.몫(power[lose], 2)); // 7 / 2는 3.5라 몫을 쓴다        }    }    names = nextNames;    power = nextPower;    row = [];    반복 (i = 0; i < names.개수; i++)    {        row.넣기(names[i] + ":" + power[i]);    }    콘솔.쓰기(row.잇기(" "));}콘솔.쓰기("champion " + names[0]);