A program that sends requests to a server waits a little and sends again when a request fails.
Each job gives the first wait b, the maximum wait c, the maximum number of tries a, the wait budget T and a result string s.
The i-th character of s is the result of the i-th try.
S is success, F is a temporary failure (may be retried), and X is a permanent failure (never retried).
At the start of each job the wait is w = b and the total time waited so far is W = 0.
For each job, repeat steps 1 to 5 below.
1. Send the request once (the first request is always sent, whatever T is).
2. If the result is S, finish with "ok"; if it is X, finish with "fatal".
3. If the result is F and a requests have been sent so far, finish with "exhausted".
4. Otherwise wait w. But if W + w is greater than T, do not wait and finish with "timeout" (if W + w equals T, do wait).
5. After waiting, add w to W and double w, but if the double is greater than c, set w = c. Then go back to 1.
The first line gives the number of jobs q, and each of the next q lines gives b, c, a, T and s separated by single spaces.
For each job, in input order, print on one line the final state (one of ok, fatal, exhausted, timeout, without quotes), the number of requests sent, and W, separated by single spaces.
Input
1 ≤ q ≤ 1,000, 1 ≤ b ≤ c ≤ 2,000,000,000, 1 ≤ a ≤ length of s ≤ 100, 0 ≤ T ≤ 10^12, s has only S, F, X
Output
q lines, each a state word, the number of requests, the total wait
ok 3 300
exhausted 4 550
timeout 2 500
ok 1 0
fatal 2 10
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
The flow is 'send once first, then ask at the end whether to send again', which is exactly do-while: C, C++, Java, C#, JS and TS do { … } while (status == null);. Python and Craykon have no do-while, so they make 'at least once' with while True: … break (Craykon while (true) … break;). The trap is asking first, as in while (W + w <= T) { … }. Then when the budget is smaller than the first wait (the example's fourth line, T = 0) no request is sent at all. The cap fits in one ternary: C family, JS and TS w = w * 2 > c ? c : w * 2;, Craykon has the same shape wait * 2 > cap ? cap : wait * 2, and only Python orders it differently: c if w * 2 > c else w * 2. int looks big enough, but c goes up to 2 billion so w * 2 can be 4 billion, and the total wait grows to 99 × 2 billion. In C and C++ int overflow is undefined behaviour (it usually wraps to a negative), and Java and C# int silently wraps to a negative, so w * 2 > c becomes false and the wait turns negative. So use C/C++ long long and Java/C# long. Python integers have no size limit, and JS, TS and Craykon use doubles, which hold these values (below 2^53) exactly. Swapping the order of step 3 (tries) and step 4 (budget) checks the budget after the last try and turns "exhausted" into "timeout".
Pythonmain.py · 31 lines
import syslines = 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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
q = Console.ReadLine().ToNumber();for (j = 0; j < q; j++){ p = Console.ReadLine().Trim().Split(); 대기 = p[0].ToNumber(); // 다음에 기다릴 시간 상한 = p[1].ToNumber(); 최대시도 = p[2].ToNumber(); 예산 = p[3].ToNumber(); 결과들 = p[4]; 기다린합 = 0; 시도 = 0; 상태 = ""; // 크레이콘에는 do-while이 없다: 동안 (참)으로 들어가서 끝에서 멈출지 묻는다(첫 시도는 언제나 한다) while (true) { 결과 = 결과들[시도]; 시도++; if (결과 == "S") { 상태 = "ok"; } else if (결과 == "X") { 상태 = "fatal"; } else if (시도 == 최대시도) { 상태 = "exhausted"; } else if (기다린합 + 대기 > 예산) { 상태 = "timeout"; } else { 기다린합 += 대기; 대기 = 대기 * 2 > 상한 ? 상한 : 대기 * 2; } if (상태 != "") { break; } } Console.WriteLine(상태 + " " + 시도 + " " + 기다린합);}