NEXT NATION

NEXT NATION은 건물을 건설하고 전사들을 훈련시켜 적의 본부를 파괴하는 2인 턴제 전략 게임입니다.

게임 규칙

1 | 개요

게임은 전장 위에서 진행됩니다. 전장은 $0$번부터 $N-1$번까지 번호가 붙은 $N$개의 구역으로 나뉘어 있으며, 중심을 기준으로 점대칭을 이룹니다. 가장 왼쪽($0$번)과 오른쪽($N-1$번) 구역에는 각 플레이어의 본부가 있습니다. 본부가 없는 구역 중 $K$개는 기지를 건설 가능한 거점입니다.

전장의 크기 $N$은 $51 \le N \le 109$, 거점의 수 $K$는 $\lceil 0.15N \rceil \le K \le \lfloor 0.2N \rfloor$입니다. $N$과 $K$는 반드시 홀수입니다.

각 플레이어는 본부에 위치한 전사 $3$명과 금화 $500$개로 시작합니다. 본부는 초기에 레벨 $1$, 체력 $10$이며, 전사의 초기 체력은 $4$입니다. 본부가 파괴된 플레이어는 패배합니다.

플레이어는 매일 다음 명령을 원하는 만큼 내릴 수 있습니다.

• 건설: 이미 있는 아군 건물(본부 및 기지)을 업그레이드하거나, 건물이 없는 거점 위에 새로운 기지를 건설할 수 있습니다.
  • 건설 명령을 수행할 위치에는 아군 전사가 한 명 이상 있고, 적 전사가 없어야 합니다.
• 이동: 현재 이동 상태가 아닌 전사 하나에게 특정 구역으로 이동하라고 명령합니다.
• 훈련: 본부에서 전사를 $n$명 훈련합니다. $n$은 본부의 훈련 가능 전사 수 이하인 $0$ 이상의 정수여야 합니다.
  • 훈련 명령은 하루에 한 번 초과로 할 수 없습니다.

플레이어가 명령을 전달하고 나면, 하루가 시작됩니다. 하루는 아침, 낮, 저녁으로 나뉩니다.

아침

건설 단계 → 이동 단계 → 훈련 단계 순서대로 진행됩니다.

• 건설 단계에서는, 금화를 지불하고 새로 기지를 건설하거나 기존에 지어진 건물을 업그레이드합니다.
• 이동 단계에서는, 오늘 이동 명령을 받았거나 이동 중이었던 전사들이 이동 규칙(섹션 3)에 따라 최대 한 칸 이동합니다.
  • 이동 명령을 새로 받은 병사마다 금화 $10$개를 지불합니다. 단, 목적지가 아군 건물이라면 지불하지 않습니다.
• 훈련 단계에서는, 훈련시키기로 한 전사 수만큼 본부에서 전사를 훈련하고 한 명당 금화 $120$개를 지불합니다.
  • 훈련된 전사의 체력은 본부의 레벨에 따릅니다.
  • 전사는 훈련되면 고유한 번호를 받으며, 먼저 훈련된 전사가 더 작은 번호를 가집니다.

낮

전투 단계가 진행됩니다.

• 전투 단계에서는, 전투 규칙(섹션 3)에 따라 적 전사와 건물을 공격합니다.

저녁

노동 단계 → 보급 단계 순서대로 진행됩니다.

• 노동 단계에서는 각 건물에서 $15 \times x$만큼 금화를 얻습니다. $x$는 해당 구역의 아군 전사 수와 해당 건물의 노동 가능 전사 수 중 작은 값입니다.
• 보급 단계에서는, 번호 오름차순으로 각 전사가 $2$만큼의 금화를 식비로 소모합니다. 만약 식비가 부족한 경우, 해당 전사는 체력을 1 잃습니다. 이때 전사의 체력이 $0$이 된 경우 전사는 퇴각하여 전장에서 벗어납니다.

---

2 | 건물

건물은 수입을 책임지는 원천입니다.

건물은 업그레이드 또는 수리 시 체력이 최대 체력까지 가득 찹니다.

건물에는 포탑이 있어, 매일 전투 단계 시작 시에 공격력만큼 같은 구역에 공격을 수행합니다. 상세 설명은 전투 단계를 확인해 주세요.

각 구역에 대해 건설 명령은 하루에 최대 한 번만 내릴 수 있습니다. 즉, 한 건물을 하루에 두 번 이상 업그레이드 하거나, 오늘 새로 지어진 건물을 오늘 업그레이드할 수 없습니다.

본부

각 플레이어는 처음에 레벨 $1$인 본부를 가지고 시작합니다. 본부는 각 플레이어마다 하나씩만 가질 수 있습니다.

기지

각 플레이어는 원하는 만큼 기지를 지을 수 있습니다. 기지에서는 본부와 달리, 전사를 훈련시킬 수 없습니다.

---

3 | 이동과 전투

이동 규칙

이동 명령을 수행 중인 각 전사는 현재 구역에 적 전사가 없다면, 현재 위치에서 목적지까지 인접한 두 구역 사이의 직선 거리 합이 가장 짧은 경로를 따라 한 구역 이동합니다. 엄밀하게는 다음과 같습니다.

자세히 보기

중심이 $(x_1, y_1)$와 $(x_2, y_2)$인 두 구역 간의 직선 거리를 $\left \lceil \sqrt{(x_1 - x_2) ^2 + (y_1 - y_2)^2 } \right \rceil$, 즉 두 구역의 중심 사이의 유클리드 거리의 올림이라 합시다. 이때 각 전사는 현재 위치에서 목적지까지 인접한 구역을 통해서만 이동하되, 경로 위에서 연속한 두 구역 사이의 직선 거리 합이 최소가 되는 경로를 찾아 해당 경로에서 현재 위치 바로 다음에 있는 구역으로 이동합니다. 그러한 경로가 여럿이라면, 구역 번호가 더 작은 구역으로 이동합니다.

이동 명령을 한 번 내리면 해당 전사는 목적지에 도착할 때까지 다른 이동 명령을 받을 수 없습니다. 전사에게 내려진 이동 명령은 목적지에 도착하는 즉시 끝납니다.

• 금화를 소모하는 이동 명령을 내린 후, 목적지에 기지가 건설되더라도 소모한 금화가 반환되지는 않습니다.
• 금화를 소모하지 않는 이동 명령을 내린 후, 목적지의 건물이 파괴되더라도 이동이 중단되지는 않습니다.

전투 규칙

1. 건물이 있는 구역에서, 해당 건물은 포탑 공격력 횟수만큼 공격을 수행합니다.
2. 각 구역에서, 나와 상대 전사 수가 각각 $a$, $b$라 할 때, 상대는 $a$번, 나는 $b$번 공격당합니다. 체력이 $0$인 전사는 전투가 끝날 때까지 퇴각하지 않으므로, 포탑 공격으로 체력이 $0$이 된 전사도 $a$와 $b$에 포함됩니다.
3. 전투가 종료되고, 체력 $0$인 전사들이 퇴각하여 전장에서 벗어납니다. 또한 체력 $0$인 건물이 파괴됩니다.

매 공격은 다음 규칙을 따라 수행됩니다.

• 그 구역에서 체력이 $0$이 아닌 상대편의 전사 중, 체력이 가장 작은 전사의 체력이 $1$ 감소합니다. 만약 그러한 전사가 여럿이라면, 번호가 가장 앞선 전사가 대상이 됩니다.
• 만약 그 구역에 체력이 $0$이 아닌 상대편의 전사가 없고, 체력이 $0$이 아닌 상대편의 건물이 있다면 해당 건물의 체력이 $1$ 감소합니다.

---

4 | 게임 종료

게임이 시작하고 $200$일 동안 어느 한 플레이어의 본부가 파괴되었다면 파괴되지 않은 플레이어의 승리입니다.

두 본부가 동시에 파괴된 경우 혹은 게임이 시작하고 $200$일 동안 양쪽 본부가 파괴되지 않은 경우, 본부의 체력이 더 많은 쪽이 승리합니다.

만약 본부의 체력도 같다면 무승부가 됩니다.

---

5 | 세부 규칙: 전장 생성 방식

전장의 구조는 입력으로 주어지기 때문에, 생성 규칙을 알아야만 문제를 해결할 수 있는 것은 아닙니다.

전장이 어떠한 방식으로 생성되는지 알고 싶으신 분은 아래를 읽을 것을 권장드립니다.

자세히 보기

전장

전장은 무한한 크기의 유클리드 평면 위에 있습니다.

• 전장에는 정확히 $N = 2N'+1$개의 다각형 모양 구역이 있습니다.
• 각 구역은 다각형의 테두리를 제외한 내부에 있는 점인 중심을 하나씩 가집니다.
• 두 구역이 인접하다는 것은, 두 구역이 적어도 하나의 변을 공유한다는 것입니다.
• 가장 왼쪽($0$번 구역)과 오른쪽의 구역($N-1$번 구역)에는 각 플레이어의 본부가 세워져 있습니다.

전장에는 특수한 구역인 거점이 있습니다.

• $K = 2K'+1$개의 구역은 거점입니다. 거점에는 건물을 건설할 수 있습니다.

전장은 매 게임마다 구조가 무작위로 생성됩니다. 구체적인 규칙은 아래에서 확인할 수 있습니다.

생성 과정

아래 설명에서 $L = 10^4$, $D = 100$, $A = 24$입니다. 매 시행은 독립이며, 특정한 범위에서 대상을 뽑을 때, 해당 범위 안에 있는 대상이 모두 같은 확률로 선택됩니다.

(1) $N'$과 $K'$을 정합니다.

• $N'$은 $25$ 이상 $54$ 이하의 정수 중에서 무작위로 정해집니다.
• 이후에 $K'$은 $\left\lceil \frac{0.15(2N'+1)-1}{2} \right\rceil$ 이상 $\left\lfloor \frac{0.2(2N'+1)-1}{2} \right\rfloor$ 이하의 정수에서 무작위로 정해집니다.

(2) 유클리드 좌표평면에서, 원점을 중심으로 삼고 반지름이 $L$인 원을 $S$라고 합시다.

(3) 처음에 $P = \{(0, 0)\}$입니다. 다음을 $N'$회 반복합니다.

• $S$의 경계 또는 내부에 있는 격자점을 하나 뽑아 $u=(x_u, y_u)$라 합니다.
• 만약 어떤 점 $(x_v, y_v) = v \in P$가 존재해서 다음 중 하나를 만족한다면 $u$를 다시 뽑습니다. $\mathrm{dist}(u, v)$는 점 $u$와 $v$ 사이의 유클리드 거리입니다.
  • $x_u = x_v$
  • $\mathrm{dist}(u, v) < D$
• $P$에 $u$와 $u$를 원점 $O$ 기준으로 점대칭한 점인 $u'$를 추가합니다.

반복 후 $|P| = 2N' + 1$입니다. $x$좌표가 증가하는 순서대로 $0$번부터 $N-1$번까지 번호를 붙입니다.

(4) 원점 $O$를 중심으로 하고 반지름이 $1.5L$인 원 $C$를 그린 후 $A$등분합니다. 구체적으로, $C$와 $x$축이 교차하는 두 점을 각각 $t_1$과 $t_2$라고 할 때, $t_1$과 $t_2$를 잇는 위쪽 호와 아랫쪽 호를 각각 $A/2$등분하는 점들을 찾습니다. 이 점들을 $Q$라고 합니다.

(5) $P \cup Q$에 있는 점들을 기준으로 보로노이 다이어그램과 델루네 삼각분할을 계산합니다. $P$의 각 점과 듀얼 관계인 보로노이 다이어그램의 다각형들의 각 무게중심을 모아 $P'$이라고 하고, 각 점에 부여된 번호를 그대로 다시 붙입니다. 이후 $P' \cup Q$를 기준으로 보로노이 다이어그램과 델루네 삼각분할을 다시 계산합니다.

(6) $t$번 점과 듀얼 관계가 있는 보로노이 다이어그램의 다각형이 $t$번 구역이 되고 $t$번 점은 $t$번 구역의 중심이 됩니다. 각 구역은 그 구역의 중심이 점 $u$라고 할 때 $u$와 델루네 삼각분할에서 이어져 있으면서 $v \in P$인 점 $v$가 중심인 구역과 이어져 있습니다. 쉽게 말해, 각 구역은 델루네 삼각분할로 이어진 구역 중 $Q$로부터 만들어지지 않은 구역들과 인접합니다.

(7) 처음에 $R = \{N'\}$입니다. 다음을 $K'$회 반복합니다.

• $t \in [0, N-1]$이고 $t \not \in R$인 무작위 $t$를 고릅니다.
• 만약 하나 이상의 $r \in R$에 대해 $t$번 구역 또는 $N-1-t$번 구역이 $r$번 구역과 인접해 있다면, $t$를 다시 뽑습니다.
• 만약 $t$번 구역과 $N-1-t$번 구역이 인접해 있다면, $t$를 다시 뽑습니다.
• $R$에 $t$와 $N-1-t$를 추가합니다.

반복 후 $|R| = 2K' + 1$입니다. 각 $r \in R$에 대해, $r$번 구역은 거점입니다.

---

인터랙션

참가자의 프로그램은 표준 입력(stdin)에서 입력을 받아 각 명령에 따라 동작해야 합니다.

준비

READY (LEFT | RIGHT)
N K
x_{0} ... x_{N-1}
y_{0} ... y_{N-1}
p_{0} ... p_{K-1}
a_{0} b_{0,0} ... b_{0,a_{0}-1}
...
a_{N-1} b_{N-1,0} b_{N-1,1} ... b_{N-1,a_{N-1}-1}

플레이어의 진영과 맵에 대한 정보를 알려주는 명령입니다.

• 첫 번째 줄에 어느 쪽 본부를 사용하는지가 주어집니다.
• 두 번째 줄에 $N$과 $K$가 주어집니다.
• $x_i$와 $y_i$는 각각 $i$번 구역 중심의 $x$좌표와 $y$좌표입니다.
• $p_i$는 거점의 구역 번호입니다.
• $i$번 구역은 $a_i$개의 구역과 인접해 있습니다. $i$번 구역과 인접한 구역의 목록은 $b_{i,j}$ ($0 \le j < a_i$)로 주어집니다.

플레이어는 입력 준비 완료를 의미하는 OK를 $1\,000$ms 안에 출력해야 합니다. 그렇지 않은 경우 시간 초과(TLE)로 패배합니다.

명령 시작

START TURN T

매 턴의 시작마다, START 명령어가 주어집니다. $T$는 오늘이 몇 번째 날인지를 나타냅니다.

명령 제출

COMMAND
...
MOVE a d
TRAIN n
UPGRADE d
...
END

플레이어는 COMMAND 명령어로 명령 단계를 시작할 수 있습니다. 플레이어는 원하는 개수만큼의 명령어를 순서 상관 없이 제출할 수 있습니다. 그 후 END 명령어로 목록의 끝을 표시합니다.

처음 주어지는 전사들의 번호는 왼쪽 플레이어의 경우 A1, A2, A3이고, 오른쪽 플레이어의 경우 B1, B2, B3입니다.

• MOVE: 번호가 $a$인 전사를 $d$번 구역으로 이동시키는 이동 명령을 내립니다.
• TRAIN: 본부에서 $n$명의 전사를 훈련합니다. 이 명령은 명령 단계에 반드시 $1$개 이하로 존재해야 합니다.
• UPGRADE: $d$번 구역에 있는 아군 건물을 업그레이드하거나 수리합니다. $d$번 구역에 건물이 없다면, 대신 기지를 건설합니다.

플레이어는 START 명령어를 받고 난 후부터 $100$ms 안에 목록을 제출해야 합니다(END 명령어를 출력해야 합니다). 만약 $100$ms를 초과하여 사용하였다면, 초과한 시간 $t$ms에 대해 $\displaystyle \left \lceil \frac{t}{100} \right \rceil$개의 초읽기를 소모합니다. 남은 초읽기가 없는 상태에서 시간을 초과했다면, 시간 초과(TLE)로 패배합니다. 각 플레이어는 처음에 $5$개씩의 초읽기를 가지고 시작합니다.

유효하지 않은 명령을 제출했다면, 그 즉시 규칙 위반(WA)로 패배합니다. 동시에 유효하지 않은 명령을 제출했다면, 무승부가 됩니다.

결과 보기

TURN T
TIME T_x R_x T_y R_y
UPGRADE N
t_1 d_1
...
TRAIN N
a_1 ... a_N
MOVE N
a_1 d_1
...
DAMAGE N
C_1 a_1 h_1
...
SIEGE N
t_1 d_1 h_1
...

두 플레이어가 모두 명령 제출을 정상적으로 마쳤다면, 결과가 반환됩니다. TRAIN, UPGRADE, MOVE, DAMAGE, SIEGE 섹션에서 $N = 0$인 경우, 해당 섹션에는 뒤따르는 줄이 주어지지 않습니다.

• TURN $T$: 현재 $T$일차에 대한 정보가 표기됨을 알려줍니다.
• TIME $T_x$ $R_x$ $T_y$ $R_y$:
  • $T_x$와 $T_y$는 각각 이번 턴에 자신과 상대 플레이어가 시간을 얼마나 사용했는지를 나타냅니다(ms).
  • $R_x$와 $R_y$는 자신과 상대 플레이어에게 몇 개의 초읽기가 남아있는지를 나타냅니다.
• UPGRADE $N$:
  • 이번 턴에 건설, 업그레이드 또는 수리된 건물의 수 $N$이 주어집니다.
  • 이어 $N$개의 줄에 건물의 소속 $t_i$($t_i$는 A나 B), 해당 건물이 있는 구역 번호 $d_i$가 차례대로 주어집니다.
• TRAIN $N$:
  • 이번 턴에 훈련된 전사의 수 $N$이 주어집니다.
  • 이어 다음 줄에 새롭게 훈련된 전사의 번호가 차례대로 주어집니다. 전사의 번호는 유일하게 부여되며, 각 플레이별로 1부터 차례대로 증가합니다.
  • 전사의 번호는 항상 A 또는 B에 정수를 하나 이어 붙인 형태입니다(e.g. A12, B7). A로 시작하면 왼쪽 플레이어의 전사이고, B로 시작하면 오른쪽 플레이어의 전사입니다.
• MOVE $N$:
  • 이번 턴에 이동한 전사의 수 $N$이 주어집니다.
  • 이어 $N$개의 줄에 이동한 전사의 번호 $a_i$와 이동한 구역 번호 $d_i$가 차례대로 주어집니다.
• DAMAGE $N$:
  • 이번 턴에 전사에 발생한 피해 정보의 개수 $N$이 주어집니다.
  • 이어 $N$개의 줄에 피해 원인 $C_i$, 피해를 입은 전사의 번호 $a_i$, 입힌 피해량 $h_i$가 차례대로 주어집니다.
  • $C_i$는 다음 중 하나입니다: TURRET(건물 포탑에 의한 피해), COMBAT(전사 간 전투에 의한 피해), HUNGER(보급 단계 식비 부족에 의한 피해).
• SIEGE $N$:
  • 이번 턴에 건물에 발생한 피해 정보의 개수 $N$이 주어집니다.
  • 이어 $N$개의 줄에 건물의 소속 $t_i$($t_i$는 A나 B), 피해를 입은 건물이 있는 구역 번호 $d_i$와 입힌 공성 피해량 $h_i$가 차례대로 주어집니다.

각 턴의 결과는 END 명령어로 마무리됩니다.

게임 종료

FINISH

어떤 이유로든 게임이 종료되면, FINISH 명령어가 주어집니다. 이 명령을 받으면 게임 진행 상황에 관계 없이 프로그램은 즉시 정상적으로 종료되어야 합니다. 다시 말해 턴이 종료되고 나서 결과 대신 FINISH 명령어가 주어진다면, 프로그램은 결과를 읽으려 시도하기 전에 즉시 종료해야 합니다.

게임 시뮬레이터

시뮬레이터 바로가기

위 시뮬레이터에 로그를 붙여 넣어 게임 플레이를 분석할 수 있습니다.

CLI 툴

CLI 툴 다운로드

위 CLI 툴을 활용하여 로컬에서 AI를 대결시켜볼 수 있습니다.

예제 코드

대회에서 지원하는 각 언어로 작성된 예제 코드를 아래에서 확인할 수 있습니다.

• C: sample-code.c
• C++: sample-code.cpp
• Python: sample-code.py
• Rust: sample-code.rs
• Java: Main.java
• JavaScript: sample-code.js
• TypeScript: sample-code.ts
• C#: sample-code.cs
• Kotlin: sample-code.kt
• Go: sample-code.go
• Scala: sample-code.scala
• Lua: sample-code.lua

샘플 AI