勇者が、スライム n 匹が一列に並んだ野原で d 日間狩りをする。 スライムにはそれぞれ大きさがある。 勇者は毎朝、気力 e で始める。 前の日に残った気力は次の日に持ち越さない。 勇者は、その日の朝に列にいたスライムに、列の前から順に一回ずつ出会う。 出会ったスライムの大きさが勇者の残りの気力以下なら、そのスライムを捕まえる。 捕まえると残りの気力がそのスライムの大きさだけ減り、そのスライムは列から抜ける。 捕まえたスライムの大きさが 2 以上なら、大きさがその半分(小数点以下は切り捨てる)の子スライムが列のいちばん後ろに新しく並ぶ。 出会ったスライムの大きさが残りの気力より大きければ、捕まえずに通り過ぎて次のスライムへ進む。 その日に生まれた子スライムにはその日は出会わず、次の日から出会う。 捕まらなかったスライムはお互いの順番をそのまま保ち、その日に生まれた子スライムは生まれた順にその後ろに並ぶ。 日ごとにその日捕まえたスライムの数とその日の狩りを終えたときの残りの気力を求め、d 日が過ぎたあと列に残ったスライムの大きさを求める。
入力
1 行目にスライムの数 n、朝の気力 e、日数 d が空白一つで区切って与えられる(1 ≤ n ≤ 1,000、1 ≤ e ≤ 1,000,000,000、1 ≤ d ≤ 200)。 2 行目に、最初に列に並んでいるスライムの大きさ 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()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 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 にはこのようなループがないので、朝の匹数を変数に入れておいて番号で回ります。 Craykon の それぞれ は、回り始めたときのリストのまま回ります。 回っている途中で追加した値は今回は出てこず、取り除いた値もそのまま出てきます。 だからどの言語でも、回っているリストには手を付けず、捕まらなかったスライムと子スライムを新しいリストに入れて、一日の終わりに列を入れ替えると安全です。 罠その一: 回りながら追加することです。 例 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;}