Roller Coaster
Source: aizu

Roller Coaster
Problem Statement

In Japan Amusement Group (JAG), members discuss how to have better amusement to attract many people. These days, they are interested in reducing waiting time stress.

As a member of JAG, you found out the hypothesis that knowing waiting time can reduce such kind of stress. Therefore, you decided to write a program which presumes the waiting time of a roller coaster.

$N$ groups stand in line for the roller coaster, and the groups are numbered from $1$ to $N$. The group $i$ has $a_i$ people. People in line ride the roller coaster in ascending order of group number.

The first roller coaster departs at time $0$ and departs every minute thereafter. The roller coaster can hold up to $M$ people.

For each group, the whole group member must ride the roller coaster at the same time. Additionally, there is no need to get exactly $M$ people on the roller coaster at one time. Each group wants to ride the roller coaster as soon as possible, so they ride it if they can.

You should output $N$ lines. In the $i$-th line, you should output the time the group $i$ can ride the roller coaster.

Input
$N$ $M$
$a_1$ $a_2$  ... $a_N$


The first line consists of an integer $N$ between $1$ and $100,000$, and an integer $M$ between $1$ and $10^9$, inclusive. $N$ represents the number of groups, and $M$ represents the capacity of the roller coaster.

The second line consists of $N$ integers between $1$ and $M$, inclusive. For each $i$ ($1 \leq i \leq N$), $a_i$ represents the number of people in the group $i$.

Output

Output $N$ lines. In the $i$-th line, you should output the answer for the group $i$.

Sample Input 1
3 5
2 4 1

Sample Output 1
0
1
1

Sample Input 2
2 1000000000
1000000000 1000000000

Sample Output 2
0
1


C++ solution:
// AOJ #3612
// Roller Coaster 2025.1.25

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll N, M;
    cin >> N >> M;
    vector<ll> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];

    vector<ll> result(N);

    ll departure_time = 0;
    ll remaining_capacity = M;

    for (int i = 0; i < N; i++) {
        ll people = a[i];
        // このグループが今のコースターに乗れるか？
        if (people <= remaining_capacity) {
            result[i] = departure_time;
            remaining_capacity -= people;
        } else {
            departure_time++;
            remaining_capacity = M;
            result[i] = departure_time;
            remaining_capacity -= people;
        }
    }
    for (int i = 0; i < N; i++) {
        cout << result[i] << endl;
    }
    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	// Read N and M
	if !scanner.Scan() {
		return
	}
	N, _ := strconv.Atoi(scanner.Text())
	if !scanner.Scan() {
		return
	}
	M, _ := strconv.ParseInt(scanner.Text(), 10, 64)

	// Read a_1 to a_N
	a := make([]int64, N)
	for i := 0; i < N; i++ {
		if !scanner.Scan() {
			return
		}
		num, err := strconv.ParseInt(scanner.Text(), 10, 64)
		if err != nil {
			return
		}
		a[i] = num
	}

	result := make([]int64, N)
	var departureTime int64 = 0
	var remainingCapacity int64 = M

	for i := 0; i < N; i++ {
		people := a[i]
		if people <= remainingCapacity {
			result[i] = departureTime
			remainingCapacity -= people
		} else {
			departureTime++
			remainingCapacity = M - people
			result[i] = departureTime
		}
	}

	// Print results
	for _, time := range result {
		fmt.Println(time)
	}
}

Java solution:
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        int N = Integer.parseInt(firstLine[0]);
        long M = Long.parseLong(firstLine[1]);
        
        long[] a = new long[N];
        String[] secondLine = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            a[i] = Long.parseLong(secondLine[i]);
        }
        
        long[] result = new long[N];
        long departureTime = 0;
        long remainingCapacity = M;
        
        for (int i = 0; i < N; i++) {
            long people = a[i];
            if (people <= remainingCapacity) {
                result[i] = departureTime;
                remainingCapacity -= people;
            } else {
                departureTime++;
                remainingCapacity = M - people;
                result[i] = departureTime;
            }
        }
        
        for (int i = 0; i < N; i++) {
            System.out.println(result[i]);
        }
    }
}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

function main() {
    let N, M;
    let groups = [];
    let lineCount = 0;

    rl.on('line', (line) => {
        if (lineCount === 0) {
            [N, M] = line.trim().split(' ').map(Number);
            lineCount++;
        } else if (lineCount === 1) {
            groups = line.trim().split(' ').map(Number);
            processGroups(N, M, groups);
            rl.close();
        }
    });
}

function processGroups(N, M, groups) {
    const result = [];
    let currentTime = 0;
    let remainingCapacity = M;

    for (let i = 0; i < N; i++) {
        const groupSize = groups[i];
        
        if (groupSize > M) {
            console.error(`Error: Group ${i+1} size (${groupSize}) exceeds roller coaster capacity (${M})`);
            process.exit(1);
        }

        if (groupSize <= remainingCapacity) {
            result.push(currentTime);
            remainingCapacity -= groupSize;
        } else {
            currentTime++;
            remainingCapacity = M - groupSize;
            result.push(currentTime);
        }
    }

    // Output results
    result.forEach(time => console.log(time));
}

main();

Python solution:
import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    a = list(map(int, input[ptr:ptr+N]))
    
    result = [0] * N
    departure_time = 0
    remaining_capacity = M
    
    for i in range(N):
        people = a[i]
        if people <= remaining_capacity:
            result[i] = departure_time
            remaining_capacity -= people
        else:
            departure_time += 1
            remaining_capacity = M - people
            result[i] = departure_time
    
    print('\n'.join(map(str, result)))

if __name__ == '__main__':
    main()

Ruby solution:
n, m = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)

departure_time = 0
remaining_capacity = m
results = []

a.each do |group_size|
  if group_size <= remaining_capacity
    results << departure_time
    remaining_capacity -= group_size
  else
    departure_time += 1
    remaining_capacity = m - group_size
    results << departure_time
  end
end

results.each { |time| puts time }