용사가 슬라임 n마리가 한 줄로 늘어선 들판에서 d일 동안 사냥을 한다.
슬라임마다 크기가 있다.
용사는 날마다 아침에 기운 e로 시작한다. 전날 남은 기운은 다음 날로 이어지지 않는다.
용사는 그날 아침에 줄에 있던 슬라임을 줄의 앞에서부터 차례로 한 번씩 만난다.
만난 슬라임의 크기가 용사의 남은 기운 이하이면 그 슬라임을 잡는다. 잡으면 남은 기운이 그 슬라임의 크기만큼 줄고, 그 슬라임은 줄에서 빠진다.
잡힌 슬라임의 크기가 2 이상이면, 크기가 그 절반(소수점 아래는 버린다)인 새끼 슬라임이 줄의 맨 뒤에 새로 선다.
만난 슬라임의 크기가 남은 기운보다 크면 잡지 않고 지나쳐 다음 슬라임으로 간다.
그날 생긴 새끼 슬라임은 그날에는 만나지 않고 다음 날부터 만난다.
잡히지 않은 슬라임들은 서로의 순서를 그대로 지키고, 그날 생긴 새끼 슬라임들은 생긴 순서대로 그 뒤에 선다.
날마다 그날 잡은 슬라임 수와 그날 사냥을 마쳤을 때 남은 기운을 구하고, d일이 지난 뒤 줄에 남은 슬라임들의 크기를 구한다.
입력
첫 줄에 슬라임의 수 n, 아침 기운 e, 날 수 d가 빈칸 하나로 띄워 주어진다(1 ≤ n ≤ 1,000, 1 ≤ e ≤ 1,000,000,000, 1 ≤ d ≤ 200).
둘째 줄에 처음 줄에 선 슬라임의 크기 n개가 줄의 앞에서부터 차례로 빈칸 하나로 띄워 주어진다.
크기는 1 이상 1,000,000,000 이하의 정수이다.
출력
처음 d개 줄에 날마다 그날 잡은 슬라임 수와 그날 사냥을 마쳤을 때 남은 기운을 빈칸 하나로 띄워 날 순서대로 출력한다.
줄에 슬라임이 없는 날은 0과 e를 출력한다.
마지막 줄에 d일이 지난 뒤 줄에 남은 슬라임들의 크기를 줄의 앞에서부터 차례로 빈칸 하나로 띄워 출력한다.
남은 슬라임이 없으면 마지막 줄에 - 하나만 출력한다.
수는 쉼표 없이 출력한다.
예시 1 · stdin
4 10 3
4 7 1 3
stdout
3 2
3 0
2 6
1
예시 2 · stdin
1 5 3
1
stdout
1 4
0 5
0 5
-
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
목록의 값을 하나씩 꺼내며 도는 반복문 안에서 바로 그 목록에 넣거나 빼면 무슨 일이 생기는지가 언어마다 달라요.
Python의 for s in row와 JavaScript·TypeScript의 for (const s of row)는 목록을 번호 순서로 그때그때 꺼내요. 도는 중에 뒤에 넣은 값도 이어서 나오고, 앞의 값을 지우면 뒤의 값이 당겨져 하나를 건너뛰어요. 오류는 나지 않아요.
Java의 for (int s : row)와 C#의 foreach (int s in row)는 도는 중에 목록이 바뀐 것을 알아채고 예외로 멈춰요. 다만 Java는 끝에서 둘째 값을 돌 때 하나를 지우면 예외 없이 마지막 값을 건너뛰고 끝나요.
C++의 for (int s : row)는 도는 중에 vector에 push_back이나 erase를 하면 정해지지 않은 동작이에요.
C에는 이런 반복문이 없어서 아침의 마리 수를 변수에 담아 두고 번호로 돌아요.
크레이콘의 각각은 돌기 시작할 때의 목록 그대로 돌아요. 도는 중에 넣은 값은 이번에 나오지 않고, 뺀 값도 그대로 나와요.
그래서 어느 언어에서나 도는 목록은 건드리지 않고, 잡히지 않은 슬라임과 새끼를 새 목록에 담은 다음 하루가 끝날 때 줄을 바꿔 끼우면 안전해요.
함정 하나: 돌면서 넣기예요. 예시 1의 첫날은 4, 1, 3을 잡아 3 2가 답이에요. Python에서 새끼(크기 2, 1)를 돌고 있는 목록 뒤에 바로 넣으면 그날 새끼까지 만나 크기 2인 새끼를 잡아서 4 0이 나와요. Java에서 똑같이 하면 ConcurrentModificationException으로 멈춰요.
함정 둘: 돌면서 빼기예요. JavaScript에서 잡힌 슬라임을 돌고 있는 배열에서 splice로 바로 지우면 그 뒤의 슬라임을 건너뛰어요. 첫날 1을 잡은 뒤 3을 만나지 못해 2 5가 나와요. C#에서 똑같이 하면 InvalidOperationException으로 멈춰요.
함정 셋: 지나치기예요. 첫날 둘째 슬라임(크기 7)은 남은 기운 6으로 잡을 수 없지만 그 뒤의 1과 3은 잡을 수 있어요. 여기서 반복을 끝내면(break) 1 6이 나와요. 다음 값으로 넘어가야(continue) 해요.
함정 넷: 크기 1의 새끼예요. 크기 1인 슬라임은 새끼를 남기지 않아요. 크기 0인 새끼를 만들면 둘째 날에 그 새끼까지 잡아 3 0이 아니라 4 0이 나와요.
함정 다섯: 아침 기운이에요. 기운을 아침마다 e로 되돌리지 않으면 둘째 날을 기운 2로 시작해 3 0이 아니라 1 0이 나와요.
Pythonmain.py · 23 줄
import sysdata = sys.stdin.read().split()n, e, d = int(data[0]), int(data[1]), int(data[2])row = [int(v) for v in data[3:3 + n]]out = []for day in range(d): energy = e # 아침마다 기운이 돌아온다 caught = 0 stay = [] # 잡히지 않은 슬라임 babies = [] # 오늘 생긴 새끼(내일부터 만난다) for s in row: # 도는 목록(row)은 건드리지 않고 새 목록에 담는다 if s > energy: stay.append(s) continue energy -= s caught += 1 if s >= 2: babies.append(s // 2) row = stay + babies out.append(f"{caught} {energy}")out.append(" ".join(map(str, row)) if row else "-")print("\n".join(out))
JavaScriptmain.js · 26 줄
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter((v) => v !== "").map(Number);const n = data[0];const e = data[1];const d = data[2];let row = data.slice(3, 3 + n);const out = [];for (let day = 0; day < d; day++) { let energy = e; // 아침마다 기운이 돌아온다 let caught = 0; const stay = []; // 잡히지 않은 슬라임 const babies = []; // 오늘 생긴 새끼(내일부터 만난다) for (const s of row) { // 도는 배열(row)은 건드리지 않고 새 배열에 담는다 if (s > energy) { stay.push(s); continue; } energy -= s; caught++; if (s >= 2) babies.push(Math.floor(s / 2)); } row = stay.concat(babies); out.push(`${caught} ${energy}`);}out.push(row.length > 0 ? row.join(" ") : "-");console.log(out.join("\n"));
TypeScriptmain.ts · 28 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter((v) => v !== "").map(Number);const n: number = data[0];const e: number = data[1];const d: number = data[2];let row: number[] = data.slice(3, 3 + n);const out: string[] = [];for (let day = 0; day < d; day++) { let energy: number = e; // 아침마다 기운이 돌아온다 let caught: number = 0; const stay: number[] = []; // 잡히지 않은 슬라임 const babies: number[] = []; // 오늘 생긴 새끼(내일부터 만난다) for (const s of row) { // 도는 배열(row)은 건드리지 않고 새 배열에 담는다 if (s > energy) { stay.push(s); continue; } energy -= s; caught++; if (s >= 2) babies.push(Math.floor(s / 2)); } row = stay.concat(babies); out.push(`${caught} ${energy}`);}out.push(row.length > 0 ? row.join(" ") : "-");console.log(out.join("\n"));
JavaMain.java · 49 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int e = Integer.parseInt(st.nextToken()); int d = Integer.parseInt(st.nextToken()); List<Integer> row = new ArrayList<>(); st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) row.add(Integer.parseInt(st.nextToken())); StringBuilder sb = new StringBuilder(); for (int day = 0; day < d; day++) { int energy = e; // 아침마다 기운이 돌아온다 int caught = 0; List<Integer> stay = new ArrayList<>(); // 잡히지 않은 슬라임 List<Integer> babies = new ArrayList<>(); // 오늘 생긴 새끼(내일부터 만난다) for (int s : row) { // 도는 목록(row)을 고치면 예외가 난다: 새 목록에 담는다 if (s > energy) { stay.add(s); continue; } energy -= s; caught++; if (s >= 2) babies.add(s / 2); } stay.addAll(babies); row = stay; sb.append(caught).append(' ').append(energy).append('\n'); } if (row.isEmpty()) { sb.append('-'); } else { for (int i = 0; i < row.size(); i++) { if (i > 0) sb.append(' '); sb.append(row.get(i)); } } sb.append('\n'); System.out.print(sb); }}
C#Main.cs · 42 줄
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] head = Console.ReadLine().Trim().Split(' '); int n = int.Parse(head[0]); int e = int.Parse(head[1]); int d = int.Parse(head[2]); string[] parts = Console.ReadLine().Trim().Split(' '); var row = new List<int>(); for (int i = 0; i < n; i++) row.Add(int.Parse(parts[i])); StringBuilder sb = new StringBuilder(); for (int day = 0; day < d; day++) { int energy = e; // 아침마다 기운이 돌아온다 int caught = 0; var stay = new List<int>(); // 잡히지 않은 슬라임 var babies = new List<int>(); // 오늘 생긴 새끼(내일부터 만난다) foreach (int s in row) // 도는 목록(row)을 고치면 예외가 난다: 새 목록에 담는다 { if (s > energy) { stay.Add(s); continue; } energy -= s; caught++; if (s >= 2) babies.Add(s / 2); } stay.AddRange(babies); row = stay; sb.Append(caught).Append(' ').Append(energy).Append('\n'); } sb.Append(row.Count > 0 ? string.Join(" ", row) : "-").Append('\n'); Console.Write(sb); }}
C++main.cpp · 41 줄
#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, e, d; cin >> n >> e >> d; vector<int> row(n); for (int& s : row) cin >> s; for (int day = 0; day < d; day++) { int energy = e; // 아침마다 기운이 돌아온다 int caught = 0; vector<int> stay; // 잡히지 않은 슬라임 vector<int> babies; // 오늘 생긴 새끼(내일부터 만난다) for (int s : row) { // 도는 vector(row)에 넣거나 빼면 안 된다: 새 vector에 담는다 if (s > energy) { stay.push_back(s); continue; } energy -= s; caught++; if (s >= 2) babies.push_back(s / 2); } stay.insert(stay.end(), babies.begin(), babies.end()); row = stay; cout << caught << ' ' << energy << '\n'; } if (row.empty()) { cout << "-"; } else { for (size_t i = 0; i < row.size(); i++) { if (i > 0) cout << ' '; cout << row[i]; } } cout << '\n'; return 0;}
Cmain.c · 42 줄
#include <stdio.h>/* C에는 for-each가 없다: 그날 아침의 마리 수(size)를 기억해 두고 번호로 돈다 */static int row[1000];static int babies[1000];int main(void) { int n, e, d; if (scanf("%d %d %d", &n, &e, &d) != 3) return 1; for (int i = 0; i < n; i++) { if (scanf("%d", &row[i]) != 1) return 1; } int size = n; for (int day = 0; day < d; day++) { int energy = e; /* 아침마다 기운이 돌아온다 */ int caught = 0; int stay = 0; /* 잡히지 않은 슬라임을 앞으로 당겨 담을 자리 */ int baby_count = 0; for (int i = 0; i < size; i++) { int s = row[i]; if (s > energy) { row[stay++] = s; /* stay <= i라서 아직 안 본 칸을 덮지 않는다 */ continue; } energy -= s; caught++; if (s >= 2) babies[baby_count++] = s / 2; } for (int i = 0; i < baby_count; i++) row[stay + i] = babies[i]; size = stay + baby_count; printf("%d %d\n", caught, energy); } if (size == 0) { printf("-\n"); } else { for (int i = 0; i < size; i++) { printf(i > 0 ? " %d" : "%d", row[i]); } printf("\n"); } return 0;}
Craykonmain.cray · 41 줄
처음 = 콘솔.수들읽기();마리수 = 처음[0];아침기운 = 처음[1];날수 = 처음[2];줄 = 콘솔.수들읽기();반복 (날 = 0; 날 < 날수; 날++){ 기운 = 아침기운; // 아침마다 기운이 돌아온다 잡은수 = 0; 남은줄 = []; // 잡히지 않은 슬라임 새끼들 = []; // 오늘 생긴 새끼(내일부터 만난다) 각각 (크기 에서 줄) { 만약 (크기 > 기운) { 남은줄.넣기(크기); 건너뛰기; } 기운 -= 크기; 잡은수++; 만약 (크기 >= 2) { 새끼들.넣기(수학.몫(크기, 2)); } } 각각 (새끼 에서 새끼들) { 남은줄.넣기(새끼); } 줄 = 남은줄; 콘솔.쓰기(잡은수 + " " + 기운);}만약 (줄.개수 == 0){ 콘솔.쓰기("-");}아니면{ 콘솔.쓰기(줄.잇기(" "));}