累積while ループ64ビット整数P0296

上がるほど遠ざかる次のレベル

ゲームのキャラクターがレベル 1、経験値 0 から始める。
次のレベルに上がるのに必要な経験値をしきい値と呼ぶ。
最初のしきい値は a、最初の増加幅は d である。
q 個の出来事が順に起こり、出来事ごとに 0 でない整数 x が一つ与えられる。
x が正なら経験値を得る。
今回の出来事が、途切れずに続いている正の出来事の k 回目なら、経験値に x + (k − 1) × b を足す。
最初の出来事であるか直前の出来事が罰点だったなら k = 1 で、直前の出来事が正だったなら k はその出来事の k より 1 大きい。
x が負なら罰点である。
経験値から −x を引き、その結果が 0 より小さければ経験値を 0 にする。
罰点は連続を切るので、次の正の出来事はまた 1 回目になる。
出来事ごとに経験値を直したあと、レベルが M より小さく経験値がしきい値以上である間、次を繰り返す：経験値からしきい値を引き、レベルを 1 上げ、しきい値に増加幅を足し、そのあと増加幅に g を足す。
だから一つの出来事で複数のレベルが上がることがあり、残った経験値は次に持ち越される。
レベルは下がらない。
レベルが M になるとそれ以上上がらず、経験値は引かれないまま積み上がる。
一行目に a、d、g、M、b が空白一つずつで区切って与えられ、二行目に q、続く q 行に x が一つずつ与えられる。
出来事ごとに、その出来事を処理したあとのレベルと経験値を空白一つで区切って一行に出力せよ。
最後の行には、一つの出来事で上がったレベル数のうち最大の値を出力せよ（一度も上がらなければ 0）。

入力: 1 ≤ a ≤ 1,000,000,000、0 ≤ d ≤ 1,000,000、0 ≤ g ≤ 1,000、1 ≤ M ≤ 10,000、0 ≤ b ≤ 1,000,000、1 ≤ q ≤ 1,000、1 ≤ |x| ≤ 1,000,000,000。
すべて整数で、カンマなしの数字だけで与えられる
出力: q + 1 行。
出来事ごとにレベルと経験値、最後の行に一つの出来事で上がった最大のレベル数。
数はカンマなしの数字だけで書く

例 1 · stdin

stdout

main.py プログラミング言語実行バージョン

入力(stdin)

実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。

$ 準備完了

コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。

ほかの言語では？言語別の解答を見る · 8 言語の解答

ループが回るたびに前の回の値に積み上げていく変数が五つあります（経験値、しきい値、増加幅、連続回数、最大上昇数）。
xp += x のような += は八つの言語すべてにあり、level++ がないのは Python だけです（level += 1）。
落とし穴 ① 一つの出来事で複数のレベルが上がるので、if ではなく while（Craykon 間）で「しきい値以上である間」繰り返します。
if だと例の二番目の出来事でレベル 3 で止まります。
② しきい値に増加幅を足したあと、増加幅にも g を足します。
積み上げる値が別の積み上げる値に積まれる形なので、一行を忘れやすいです。
③ >= を > にすると、経験値がしきい値とちょうど同じときに上がれません。
④ 最高レベルでは level < M で止めます。
この条件がないと M を超えても上がります。
⑤ 罰点は 0 より下に行かないように切ります：Python max(0, v)、JS・TS・Java Math.max(0, v)、C# Math.Max(0, v)、C++ std::max(0LL, v)（二つの引数の型が同じでなければならないので 0 ではなく 0LL）、Craykon 数学.大きい方(0, v)。
C の標準ライブラリには整数用の max 関数がないので if (xp < 0) xp = 0; と書きます。
⑥ 罰点が来たら連続回数を 0 に戻し、連続 k 回目のボーナスは k × b ではなく (k − 1) × b です。
⑦ 経験値は約 1.5 兆まで大きくなり、しきい値も 21 億を超えることがあるので、int（約 21 億）に入りません。
C・C++ は long long（printf は %lld）、Java・C# は long を使います。
Python の整数は大きさに限りがなく、JS・TS・Craykon の数は 2^53（約 9 × 10^15）まで整数が正確なのでそのままで大丈夫です。

Pythonmain.py · 31 行

import sys lines = sys.stdin.read().split("\n")a, d, g, M, b = map(int, lines[0].split())q = int(lines[1]) level, xp = 1, 0need, step = a, d  # 문턱과 증가폭: 오를 때마다 둘 다 쌓인다streak = 0  # 연달아 얻은 횟수best = 0  # 한 사건에서 가장 많이 오른 레벨 수out = []for i in range(q):    x = int(lines[2 + i])    if x > 0:        streak += 1        xp += x + (streak - 1) * b    else:        streak = 0        xp = max(0, xp + x)    ups = 0    # 한 번에 여러 레벨을 오를 수 있으니 if가 아니라 while    while level < M and xp >= need:        xp -= need        level += 1        need += step        step += g        ups += 1    best = max(best, ups)    out.append(f"{level} {xp}")out.append(str(best))print("\n".join(out))

JavaScriptmain.js · 32 行

const lines = require("fs").readFileSync(0, "utf8").split("\n");const [a, d, g, M, b] = lines[0].trim().split(/\s+/).map(Number);const q = Number(lines[1]); let level = 1, xp = 0;let need = a, step = d; // 문턱과 증가폭: 오를 때마다 둘 다 쌓인다let streak = 0; // 연달아 얻은 횟수let best = 0; // 한 사건에서 가장 많이 오른 레벨 수const out = [];for (let i = 0; i < q; i++) {  const x = Number(lines[2 + i]);  if (x > 0) {    streak += 1;    xp += x + (streak - 1) * b;  } else {    streak = 0;    xp = Math.max(0, xp + x);  }  let ups = 0;  // 한 번에 여러 레벨을 오를 수 있으니 if가 아니라 while  while (level < M && xp >= need) {    xp -= need;    level += 1;    need += step;    step += g;    ups += 1;  }  best = Math.max(best, ups);  out.push(`${level} ${xp}`);}out.push(String(best));console.log(out.join("\n"));

TypeScriptmain.ts · 34 行

import { readFileSync } from "node:fs"; const lines: string[] = readFileSync(0, "utf8").split("\n");const [a, d, g, M, b]: number[] = lines[0].trim().split(/\s+/).map(Number);const q = Number(lines[1]); let level = 1, xp = 0;let need = a, step = d; // 문턱과 증가폭: 오를 때마다 둘 다 쌓인다let streak = 0; // 연달아 얻은 횟수let best = 0; // 한 사건에서 가장 많이 오른 레벨 수const out: string[] = [];for (let i = 0; i < q; i++) {  const x = Number(lines[2 + i]);  if (x > 0) {    streak += 1;    xp += x + (streak - 1) * b;  } else {    streak = 0;    xp = Math.max(0, xp + x);  }  let ups = 0;  // 한 번에 여러 레벨을 오를 수 있으니 if가 아니라 while  while (level < M && xp >= need) {    xp -= need;    level += 1;    need += step;    step += g;    ups += 1;  }  best = Math.max(best, ups);  out.push(`${level} ${xp}`);}out.push(String(best));console.log(out.join("\n"));

JavaMain.java · 41 行

import java.util.Scanner; public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        long a = sc.nextLong(), d = sc.nextLong(), g = sc.nextLong();        int M = sc.nextInt();        long b = sc.nextLong();        int q = sc.nextInt();         int level = 1;        long xp = 0; // 1조 넘게 쌓여서 int로는 모자란다        long need = a, step = d; // 문턱과 증가폭: 오를 때마다 둘 다 쌓인다        long streak = 0; // 연달아 얻은 횟수        int best = 0; // 한 사건에서 가장 많이 오른 레벨 수        StringBuilder out = new StringBuilder();        for (int i = 0; i < q; i++) {            long x = sc.nextLong();            if (x > 0) {                streak += 1;                xp += x + (streak - 1) * b;            } else {                streak = 0;                xp = Math.max(0, xp + x);            }            int ups = 0;            // 한 번에 여러 레벨을 오를 수 있으니 if가 아니라 while            while (level < M && xp >= need) {                xp -= need;                level += 1;                need += step;                step += g;                ups += 1;            }            best = Math.max(best, ups);            out.append(level).append(' ').append(xp).append('\n');        }        out.append(best).append('\n');        System.out.print(out);    }}

C#Main.cs · 49 行

using System;using System.Text; class Program{    static void Main()    {        string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);        long a = long.Parse(p[0]), d = long.Parse(p[1]), g = long.Parse(p[2]);        int M = int.Parse(p[3]);        long b = long.Parse(p[4]);        int q = int.Parse(Console.ReadLine().Trim());         int level = 1;        long xp = 0; // 1조 넘게 쌓여서 int로는 모자란다        long need = a, step = d; // 문턱과 증가폭: 오를 때마다 둘 다 쌓인다        long streak = 0; // 연달아 얻은 횟수        int best = 0; // 한 사건에서 가장 많이 오른 레벨 수        var output = new StringBuilder();        for (int i = 0; i < q; i++)        {            long x = long.Parse(Console.ReadLine().Trim());            if (x > 0)            {                streak += 1;                xp += x + (streak - 1) * b;            }            else            {                streak = 0;                xp = Math.Max(0, xp + x);            }            int ups = 0;            // 한 번에 여러 레벨을 오를 수 있으니 if가 아니라 while            while (level < M && xp >= need)            {                xp -= need;                level += 1;                need += step;                step += g;                ups += 1;            }            best = Math.Max(best, ups);            output.Append(level).Append(' ').Append(xp).Append('\n');        }        output.Append(best).Append('\n');        Console.Write(output);    }}

C++main.cpp · 38 行

#include <algorithm>#include <iostream> int main() {    std::ios::sync_with_stdio(false);    long long a, d, g, b;    int M, q;    std::cin >> a >> d >> g >> M >> b >> q;     int level = 1;    long long xp = 0;             // 1조 넘게 쌓여서 int로는 모자란다    long long need = a, step = d; // 문턱과 증가폭: 오를 때마다 둘 다 쌓인다    long long streak = 0;         // 연달아 얻은 횟수    int best = 0;                 // 한 사건에서 가장 많이 오른 레벨 수    for (int i = 0; i < q; i++) {        long long x;        std::cin >> x;        if (x > 0) {            streak += 1;            xp += x + (streak - 1) * b;        } else {            streak = 0;            xp = std::max(0LL, xp + x); // 두 인수의 타입이 같아야 해서 0LL        }        int ups = 0;        // 한 번에 여러 레벨을 오를 수 있으니 if가 아니라 while        while (level < M && xp >= need) {            xp -= need;            level += 1;            need += step;            step += g;            ups += 1;        }        best = std::max(best, ups);        std::cout << level << ' ' << xp << '\n';    }    std::cout << best << '\n';}

Cmain.c · 38 行

#include <stdio.h> int main(void) {    long long a, d, g, b;    int M, q;    scanf("%lld %lld %lld %d %lld %d", &a, &d, &g, &M, &b, &q);     int level = 1;    long long xp = 0;             /* 1조 넘게 쌓여서 int로는 모자란다 */    long long need = a, step = d; /* 문턱과 증가폭: 오를 때마다 둘 다 쌓인다 */    long long streak = 0;         /* 연달아 얻은 횟수 */    int best = 0;                 /* 한 사건에서 가장 많이 오른 레벨 수 */    for (int i = 0; i < q; i++) {        long long x;        scanf("%lld", &x);        if (x > 0) {            streak += 1;            xp += x + (streak - 1) * b;        } else {            streak = 0;            xp += x;            if (xp < 0) xp = 0;        }        int ups = 0;        /* 한 번에 여러 레벨을 오를 수 있으니 if가 아니라 while */        while (level < M && xp >= need) {            xp -= need;            level += 1;            need += step;            step += g;            ups += 1;        }        if (ups > best) best = ups;        printf("%d %lld\n", level, xp);    }    printf("%d\n", best);    return 0;}

Craykonmain.cray · 41 行

p = コンソール.数読み();a = p[0];d = p[1];g = p[2];M = p[3];b = p[4];q = コンソール.行読み().数に(); level = 1;xp = 0;need = a; // 문턱step = d; // 증가폭: 오를 때마다 문턱과 함께 쌓인다streak = 0; // 연달아 얻은 횟수best = 0; // 한 사건에서 가장 많이 오른 레벨 수繰り返す (i = 0; i < q; i++){    x = コンソール.行読み().数に();    もし (x > 0)    {        streak += 1;        xp += x + (streak - 1) * b;    }    でなければ    {        streak = 0;        xp = 数学.大きい方(0, xp + x);    }    ups = 0;    // 한 번에 여러 레벨을 오를 수 있으니 만약이 아니라 동안    間 (level < M && xp >= need)    {        xp -= need;        level += 1;        need += step;        step += g;        ups += 1;    }    best = 数学.大きい方(best, ups);    コンソール.書く(level + " " + xp);}コンソール.書く(best);