A hero hunts for d days in a field where n slimes stand in a row.
Each slime has a size.
Every morning the hero starts with energy e. Energy left from the day before does not carry over to the next day.
The hero meets each slime that was in the row that morning once, in order from the front of the row.
If the size of the slime met is less than or equal to the hero's remaining energy, the hero catches it. Catching it reduces the remaining energy by the size of the slime, and the slime leaves the row.
If the size of the caught slime is 2 or more, a baby slime of half that size (fractions are dropped) newly joins the very back of the row.
If the size of the slime met is greater than the remaining energy, the hero does not catch it and passes on to the next slime.
Baby slimes born that day are not met that day; they are met from the next day on.
The slimes that were not caught keep their order among themselves, and the baby slimes born that day stand behind them in the order they were born.
For each day find the number of slimes caught that day and the energy remaining when that day's hunt ends, and find the sizes of the slimes left in the row after d days.
Input
The first line contains the number of slimes n, the morning energy e, and the number of days d, separated by single spaces (1 ≤ n ≤ 1,000, 1 ≤ e ≤ 1,000,000,000, 1 ≤ d ≤ 200).
The second line contains the n sizes of the slimes standing in the row at the start, in order from the front of the row, separated by single spaces.
Each size is an integer from 1 to 1,000,000,000.
Output
On the first d lines, for each day in order, print the number of slimes caught that day and the energy remaining when that day's hunt ends, separated by a single space.
For a day when the row has no slimes, print 0 and e.
On the last line, print the sizes of the slimes left in the row after d days, in order from the front of the row, separated by single spaces.
If no slimes are left, print a single - on the last line.
Print numbers without commas.
Example 1 · stdin
4 10 3
4 7 1 3
stdout
3 2
3 0
2 6
1
Example 2 · stdin
1 5 3
1
stdout
1 4
0 5
0 5
-
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Languages differ in what happens when, inside a loop that takes the values of a list one by one, you add to or remove from that very list.
Python's for s in row and JavaScript and TypeScript's for (const s of row) take values by index as they go. A value added at the back during the loop comes out too, and deleting an earlier value pulls the later ones forward so that one is skipped. No error is raised.
Java's for (int s : row) and C#'s foreach (int s in row) notice that the list changed during the loop and stop with an exception. One exception to this: in Java, removing an element while on the second-to-last value ends the loop without an exception, skipping the last value.
In C++'s for (int s : row), calling push_back or erase on the vector during the loop is undefined behavior.
C has no such loop, so you keep the morning count in a variable and loop by index.
Craykon's foreach walks the list as it was when the loop started. A value added during the loop does not come out this time, and a removed value still comes out.
So in any language it is safe to leave the list being walked alone, collect the slimes that were not caught and the babies in new lists, and swap the row at the end of the day.
Trap one: adding while looping. On the first day of example 1 the hero catches 4, 1 and 3, so the answer is 3 2. In Python, adding the babies (sizes 2 and 1) straight to the back of the list being walked makes the hero meet them that day and catch the baby of size 2, giving 4 0. Doing the same in Java stops with a ConcurrentModificationException.
Trap two: removing while looping. In JavaScript, deleting a caught slime from the array being walked with splice skips the slime after it. After catching 1 on the first day the hero never meets 3, giving 2 5. Doing the same in C# stops with an InvalidOperationException.
Trap three: passing by. On the first day the second slime (size 7) cannot be caught with 6 energy left, but the 1 and the 3 after it can. Ending the loop there (break) gives 1 6. You must move on to the next value (continue).
Trap four: a baby from size 1. A slime of size 1 leaves no baby. Making a baby of size 0 lets the hero catch that baby too on the second day, giving 4 0 instead of 3 0.
Trap five: the morning energy. Without resetting the energy to e every morning, the second day starts with 2 energy and gives 1 0 instead of 3 0.
Pythonmain.py · 23 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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;}