do-while 循环三元运算符溢出P0138

等待后重试

向服务器发送请求的程序在请求失败时，会稍等一会儿再发送。
每个任务给出首次等待时间 b、最大等待时间 c、最大尝试次数 a、等待预算 T 和结果字符串 s。
s 的第 i 个字符是第 i 次尝试的结果。
S 表示成功，F 表示临时失败（可以重试），X 表示永久失败（不再重试）。
每个任务开始时，等待时间 w = b，到目前为止等待的总时间 W = 0。
每个任务重复下面的 1～5 步。
1.
发送一次请求（第一次请求不管 T 是多少都一定发送）。
2.
结果是 S 就以 "ok" 结束，是 X 就以 "fatal" 结束。
3.
结果是 F 且到目前为止已经发送了 a 次，就以 "exhausted" 结束。
4.
否则等待 w。
但如果 W + w 大于 T，就不等待，以 "timeout" 结束（W + w 等于 T 时要等待）。
5.
等待后把 w 加到 W 上，再把 w 翻倍，但翻倍后大于 c 时令 w = c。
然后回到 1。
第一行给出任务数 q，接下来 q 行给出每个任务的 b、c、a、T、s，之间各隔一个空格。
按输入顺序，每个任务一行输出结束状态（ok、fatal、exhausted、timeout 之一，不带引号）、发送请求的次数和 W，用一个空格隔开。

输入: 1 ≤ q ≤ 1,000，1 ≤ b ≤ c ≤ 2,000,000,000，1 ≤ a ≤ s 的长度 ≤ 100，0 ≤ T ≤ 10^12，s 只由 S、F、X 组成
输出: q 行，每行一个状态词、发送次数、等待总时间

样例 1 · stdin

5
100 1000 5 10000 FFSFF
100 250 4 10000 FFFFS
500 4000 4 1200 FFFS
1000 1000 3 0 SFF
10 100 3 1000 FXS

stdout

ok 3 300
exhausted 4 550
timeout 2 500
ok 1 0
fatal 2 10

main.py 编程语言运行版本

输入(stdin)

运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。

$ 就绪

请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。

其他语言怎么写？查看各语言题解 · 8 种语言题解

流程是“先发送一次，最后再问要不要重发”，正好是 do-while：C、C++、Java、C#、JS、TS do { … } while (status == null);。
Python 和 Craykon 没有 do-while，用 while True: … break（Craykon 当 (真) … 跳出;）来实现“至少一次”。
陷阱是像 while (W + w <= T) { … } 这样先判断条件。
这样当预算小于首次等待时间时（例子第四行 T = 0），一次请求也不会发送。
上限可以用一行三元运算符：C 系、JS、TS w = w * 2 > c ? c : w * 2;，Craykon 也是同样的形状 等待 * 2 > 上限 ? 上限 : 等待 * 2，只有 Python 顺序不同：c if w * 2 > c else w * 2。
看起来 int 就够了，但 c 最大 20 亿，w * 2 可能达到 40 亿，等待总和会增长到 99 × 20 亿。
C、C++ 的 int 溢出是未定义行为（通常回绕成负数），Java、C# 的 int 会悄悄回绕成负数，于是 w * 2 > c 变成假，等待时间变成负数。
所以 C、C++ 用 long long，Java、C# 用 long。
Python 的整数没有大小限制，JS、TS、Craykon 用 double，能精确表示这些 2^53 以内的值。
如果把第 3 步（次数）和第 4 步（预算）的判断顺序对调，就会在最后一次尝试后检查预算，"exhausted" 变成 "timeout"。

Pythonmain.py · 31 行

import sys lines = sys.stdin.read().split("\n")q = int(lines[0])out = []for line in lines[1:q + 1]:    b, c, a, t, s = line.split()    c, a, t = int(c), int(a), int(t)    wait = int(b)  # 다음에 기다릴 시간    waited = 0     # 지금까지 기다린 시간의 합    tries = 0    # Python에는 do-while이 없다: while True로 들어가 끝에서 멈출지 정한다(첫 시도는 언제나 한다)    while True:        result = s[tries]        tries += 1        if result == "S":            status = "ok"            break        if result == "X":            status = "fatal"            break        if tries == a:            status = "exhausted"            break        if waited + wait > t:            status = "timeout"            break        waited += wait        wait = c if wait * 2 > c else wait * 2    out.append(f"{status} {tries} {waited}")print("\n".join(out))

JavaScriptmain.js · 28 行

const lines = require("fs").readFileSync(0, "utf8").split("\n");const q = Number(lines[0]);const out = [];for (let j = 1; j <= q; j++) {  const [b, c, a, t, s] = lines[j].trim().split(/\s+/);  const cap = Number(c);  const maxTries = Number(a);  const budget = Number(t);  let wait = Number(b); // 다음에 기다릴 시간  let waited = 0; // 지금까지 기다린 시간의 합  let tries = 0;  let status = null;  // 첫 시도는 언제나 한다: 몸통을 먼저 돌고 끝에서 계속할지 묻는다  do {    const result = s[tries];    tries++;    if (result === "S") status = "ok";    else if (result === "X") status = "fatal";    else if (tries === maxTries) status = "exhausted";    else if (waited + wait > budget) status = "timeout";    else {      waited += wait;      wait = wait * 2 > cap ? cap : wait * 2;    }  } while (status === null);  out.push(`${status} ${tries} ${waited}`);}console.log(out.join("\n"));

TypeScriptmain.ts · 29 行

import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const q: number = Number(lines[0]);const out: string[] = [];for (let j = 1; j <= q; j++) {  const [b, c, a, t, s] = lines[j].trim().split(/\s+/);  const cap: number = Number(c);  const maxTries: number = Number(a);  const budget: number = Number(t);  let wait: number = Number(b); // 다음에 기다릴 시간  let waited = 0; // 지금까지 기다린 시간의 합  let tries = 0;  let status: string | null = null;  // 첫 시도는 언제나 한다: 몸통을 먼저 돌고 끝에서 계속할지 묻는다  do {    const result: string = s[tries];    tries++;    if (result === "S") status = "ok";    else if (result === "X") status = "fatal";    else if (tries === maxTries) status = "exhausted";    else if (waited + wait > budget) status = "timeout";    else {      waited += wait;      wait = wait * 2 > cap ? cap : wait * 2;    }  } while (status === null);  out.push(`${status} ${tries} ${waited}`);}console.log(out.join("\n"));

JavaMain.java · 37 行

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class Main {    public static void main(String[] args) throws IOException {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        int q = Integer.parseInt(br.readLine().trim());        StringBuilder out = new StringBuilder();        for (int j = 0; j < q; j++) {            String[] p = br.readLine().trim().split("\\s+");            long wait = Long.parseLong(p[0]); // 다음에 기다릴 시간(2배가 int를 넘을 수 있다)            long cap = Long.parseLong(p[1]);            int maxTries = Integer.parseInt(p[2]);            long budget = Long.parseLong(p[3]);            String s = p[4];            long waited = 0; // 지금까지 기다린 시간의 합            int tries = 0;            String status = null;            // 첫 시도는 언제나 한다: 몸통을 먼저 돌고 끝에서 계속할지 묻는다            do {                char result = s.charAt(tries);                tries++;                if (result == 'S') status = "ok";                else if (result == 'X') status = "fatal";                else if (tries == maxTries) status = "exhausted";                else if (waited + wait > budget) status = "timeout";                else {                    waited += wait;                    wait = wait * 2 > cap ? cap : wait * 2;                }            } while (status == null);            out.append(status).append(' ').append(tries).append(' ').append(waited).append('\n');        }        System.out.print(out);    }}

C#Main.cs · 40 行

using System;using System.Text; class Program{    static void Main()    {        int q = int.Parse(Console.ReadLine().Trim());        var sb = new StringBuilder();        for (int j = 0; j < q; j++)        {            string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);            long wait = long.Parse(p[0]); // 다음에 기다릴 시간(2배가 int를 넘을 수 있다)            long cap = long.Parse(p[1]);            int maxTries = int.Parse(p[2]);            long budget = long.Parse(p[3]);            string s = p[4];            long waited = 0; // 지금까지 기다린 시간의 합            int tries = 0;            string? status = null;            // 첫 시도는 언제나 한다: 몸통을 먼저 돌고 끝에서 계속할지 묻는다            do            {                char result = s[tries];                tries++;                if (result == 'S') status = "ok";                else if (result == 'X') status = "fatal";                else if (tries == maxTries) status = "exhausted";                else if (waited + wait > budget) status = "timeout";                else                {                    waited += wait;                    wait = wait * 2 > cap ? cap : wait * 2;                }            } while (status == null);            sb.Append(status).Append(' ').Append(tries).Append(' ').Append(waited).Append('\n');        }        Console.Write(sb);    }}

C++main.cpp · 30 行

#include <iostream>#include <string> int main() {    int q;    std::cin >> q;    for (int j = 0; j < q; j++) {        long long wait, cap, budget; // 2배가 int(약 21억)를 넘을 수 있다        int maxTries;        std::string s;        std::cin >> wait >> cap >> maxTries >> budget >> s;        long long waited = 0; // 지금까지 기다린 시간의 합        int tries = 0;        std::string status;        // 첫 시도는 언제나 한다: 몸통을 먼저 돌고 끝에서 계속할지 묻는다        do {            char result = s[tries];            tries++;            if (result == 'S') status = "ok";            else if (result == 'X') status = "fatal";            else if (tries == maxTries) status = "exhausted";            else if (waited + wait > budget) status = "timeout";            else {                waited += wait;                wait = wait * 2 > cap ? cap : wait * 2;            }        } while (status.empty());        std::cout << status << ' ' << tries << ' ' << waited << '\n';    }}

Cmain.c · 30 行

#include <stdio.h> int main(void) {    int q;    scanf("%d", &q);    for (int j = 0; j < q; j++) {        long long wait, cap, budget; /* 2배가 int(약 21억)를 넘을 수 있다 */        int max_tries;        char s[128];        scanf("%lld %lld %d %lld %127s", &wait, &cap, &max_tries, &budget, s);        long long waited = 0; /* 지금까지 기다린 시간의 합 */        int tries = 0;        const char *status = NULL;        /* 첫 시도는 언제나 한다: 몸통을 먼저 돌고 끝에서 계속할지 묻는다 */        do {            char result = s[tries];            tries++;            if (result == 'S') status = "ok";            else if (result == 'X') status = "fatal";            else if (tries == max_tries) status = "exhausted";            else if (waited + wait > budget) status = "timeout";            else {                waited += wait;                wait = wait * 2 > cap ? cap : wait * 2;            }        } while (status == NULL);        printf("%s %d %lld\n", status, tries, waited);    }    return 0;}

Craykonmain.cray · 45 行

q = 控制台.读行().转数字();循环 (j = 0; j < q; j++){    p = 控制台.读行().去空白().分割();    대기 = p[0].转数字(); // 다음에 기다릴 시간    상한 = p[1].转数字();    최대시도 = p[2].转数字();    예산 = p[3].转数字();    결과들 = p[4];    기다린합 = 0;    시도 = 0;    상태 = "";    // 크레이콘에는 do-while이 없다: 동안 (참)으로 들어가서 끝에서 멈출지 묻는다(첫 시도는 언제나 한다)    当 (真)    {        결과 = 결과들[시도];        시도++;        如果 (결과 == "S")        {            상태 = "ok";        }        否则 如果 (결과 == "X")        {            상태 = "fatal";        }        否则 如果 (시도 == 최대시도)        {            상태 = "exhausted";        }        否则 如果 (기다린합 + 대기 > 예산)        {            상태 = "timeout";        }        否则        {            기다린합 += 대기;            대기 = 대기 * 2 > 상한 ? 상한 : 대기 * 2;        }        如果 (상태 != "")        {            跳出;        }    }    控制台.输出(상태 + " " + 시도 + " " + 기다린합);}