勇者在一片原野上狩猎 d 天，原野上有 n 只史莱姆排成一列。 每只史莱姆都有大小。 勇者每天早上以体力 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()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
其他语言怎么写？查看各语言题解 · 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;}