Play several games of a dice game.
A game has n people who take turns in order from 1 to n (after n comes 1 again). Everyone starts with 0 points.
The die is a device that makes numbers by a fixed rule, and everyone in a game shares the same one.
The die holds a current value x. Each roll replaces x with the remainder of (a × x + c) divided by m, and the face rolled is the new x modulo 6, plus 1.
On a person's turn, do the following.
1. Roll the die once and add the face to this turn's sum.
2. If the face is 6 and this turn has had fewer than 3 rolls, go back to 1.
3. If this turn rolled 6 three times (all three rolls were 6), this turn's sum becomes 0.
4. Add this turn's sum to that person's score. If the score becomes G or more, that person wins and the game ends.
A win is checked only after the turn is over, so every turn rolls at least once.
If nobody has won when the T-th turn ends, the game ends with no winner.
The first line gives the number of games t, and each of the next t lines gives n, G, T, the starting x, a, c and m for one game, separated by single spaces.
Print two lines per game.
The first line has the winner's number (0 if nobody won), the number of turns played, and the number of rolls, separated by single spaces.
The second line has the scores of people 1 to n, separated by single spaces.
Input
1 ≤ t ≤ 50, 1 ≤ n ≤ 8, 1 ≤ G ≤ 10,000, 1 ≤ T ≤ 10,000, the sum of T over all games ≤ 100,000. 1 ≤ m ≤ 1,000,000, 0 ≤ starting x, a, c < m (integers)
Output
Two lines per game
Example 1 · stdin
2
2 15 20 1 9 10 19
1 5 3 5 1 0 7
stdout
1 11 15
15 10
0 3 9
0
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
A turn has the shape 'roll first, then ask whether to roll again', which is exactly do-while. Java, C#, C, C++, JavaScript and TypeScript write do { roll } while (face == 6 && count < 3);. Python has no do-while, so it rolls inside while True: and ends with if not (...): break; Craykon writes while (true) { … if (!(…)) { break; } } (동안 (참) { … 만약 (!(…)) { 그만; } }). Four traps: ① turning the do-while into a plain while (face == 6 && count < 3) asks before entering, so with a face not rolled yet (0) it never rolls at all. ② a × x grows up to 10^12. Multiplying in int in C, C++, Java or C# overflows (undefined behaviour in C/C++; in Java/C# it silently wraps and can even turn negative), and the faces go wrong. Multiply in long long/long. Python int is unbounded, and numbers in JS/TS/Craykon are exact up to 2^53 (about 9×10^15), so 10^12 is fine. ③ three 6s stop the turn and score 0. With count <= 3 you roll a fourth time, and forgetting the zeroing adds 18 points. After the loop, a last face of 6 means all three were 6, so one line if (face == 6) tells you. ④ check for a win only after the turn ends. Comparing score plus the running sum with G after every roll counts a win even on a turn that 6·6·6 is about to wipe out.
Pythonmain.py · 34 lines
import syslines = sys.stdin.read().split("\n")t = int(lines[0])out = []for line in lines[1 : t + 1]: n, goal, max_turns, x, a, c, m = map(int, line.split()) scores = [0] * n winner = 0 turns = 0 rolls = 0 player = 0 while turns < max_turns and winner == 0: turns += 1 turn_sum = 0 count = 0 # Python에는 do-while이 없다: while True로 들어가 끝에서 멈출지 묻는다(첫 굴림은 언제나 한다) while True: x = (a * x + c) % m face = x % 6 + 1 rolls += 1 count += 1 turn_sum += face if not (face == 6 and count < 3): break if face == 6: # 세 번 모두 6이면 이번 차례는 0점 turn_sum = 0 scores[player] += turn_sum if scores[player] >= goal: winner = player + 1 player = (player + 1) % n out.append(f"{winner} {turns} {rolls}") out.append(" ".join(map(str, scores)))print("\n".join(out))
JavaScriptmain.js · 27 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const t = Number(lines[0]);const out = [];for (let g = 1; g <= t; g++) { // a * x는 10^12까지라 number(2^53까지 정확)로 충분하다 let [n, goal, maxTurns, x, a, c, m] = lines[g].trim().split(" ").map(Number); const scores = new Array(n).fill(0); let winner = 0, turns = 0, rolls = 0, player = 0; while (turns < maxTurns && winner === 0) { turns++; let turnSum = 0, count = 0, face; do { // 첫 굴림은 언제나 한다 x = (a * x + c) % m; face = (x % 6) + 1; rolls++; count++; turnSum += face; } while (face === 6 && count < 3); if (face === 6) turnSum = 0; // 세 번 모두 6 scores[player] += turnSum; if (scores[player] >= goal) winner = player + 1; player = (player + 1) % n; } out.push(`${winner} ${turns} ${rolls}`, scores.join(" "));}console.log(out.join("\n"));
TypeScriptmain.ts · 30 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const t: number = Number(lines[0]);const out: string[] = [];for (let g = 1; g <= t; g++) { // a * x는 10^12까지라 number(2^53까지 정확)로 충분하다 const [n, goal, maxTurns, x0, a, c, m] = lines[g].trim().split(" ").map(Number); let x: number = x0; const scores: number[] = new Array<number>(n).fill(0); let winner = 0, turns = 0, rolls = 0, player = 0; while (turns < maxTurns && winner === 0) { turns++; let turnSum = 0, count = 0, face: number; do { // 첫 굴림은 언제나 한다 x = (a * x + c) % m; face = (x % 6) + 1; rolls++; count++; turnSum += face; } while (face === 6 && count < 3); if (face === 6) turnSum = 0; // 세 번 모두 6 scores[player] += turnSum; if (scores[player] >= goal) winner = player + 1; player = (player + 1) % n; } out.push(`${winner} ${turns} ${rolls}`, scores.join(" "));}console.log(out.join("\n"));
JavaMain.java · 36 lines
import java.io.BufferedReader;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int g = 0; g < t; g++) { String[] p = in.readLine().trim().split(" "); int n = Integer.parseInt(p[0]), goal = Integer.parseInt(p[1]), maxTurns = Integer.parseInt(p[2]); long x = Long.parseLong(p[3]), a = Long.parseLong(p[4]), c = Long.parseLong(p[5]), m = Long.parseLong(p[6]); // a * x는 int를 넘친다 int[] scores = new int[n]; int winner = 0, turns = 0, rolls = 0, player = 0; while (turns < maxTurns && winner == 0) { turns++; int turnSum = 0, count = 0, face; do { // 첫 굴림은 언제나 한다 x = (a * x + c) % m; face = (int) (x % 6) + 1; rolls++; count++; turnSum += face; } while (face == 6 && count < 3); if (face == 6) turnSum = 0; // 세 번 모두 6 scores[player] += turnSum; if (scores[player] >= goal) winner = player + 1; player = (player + 1) % n; } out.append(winner).append(' ').append(turns).append(' ').append(rolls).append('\n'); for (int i = 0; i < n; i++) out.append(i > 0 ? " " : "").append(scores[i]); out.append('\n'); } System.out.print(out); }}
C#Main.cs · 39 lines
using System;using System.Text;class Program{ static void Main() { int t = int.Parse(Console.ReadLine()!.Trim()); var sb = new StringBuilder(); for (int g = 0; g < t; g++) { string[] p = Console.ReadLine()!.Trim().Split(' '); int n = int.Parse(p[0]), goal = int.Parse(p[1]), maxTurns = int.Parse(p[2]); long x = long.Parse(p[3]), a = long.Parse(p[4]), c = long.Parse(p[5]), m = long.Parse(p[6]); // a * x는 int를 넘친다 int[] scores = new int[n]; int winner = 0, turns = 0, rolls = 0, player = 0; while (turns < maxTurns && winner == 0) { turns++; int turnSum = 0, count = 0, face; do // 첫 굴림은 언제나 한다 { x = (a * x + c) % m; face = (int)(x % 6) + 1; rolls++; count++; turnSum += face; } while (face == 6 && count < 3); if (face == 6) turnSum = 0; // 세 번 모두 6 scores[player] += turnSum; if (scores[player] >= goal) winner = player + 1; player = (player + 1) % n; } sb.Append($"{winner} {turns} {rolls}\n"); sb.Append(string.Join(" ", scores)).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 33 lines
#include <iostream>#include <vector>int main() { std::ios::sync_with_stdio(false); int t; std::cin >> t; while (t--) { int n, goal, maxTurns; long long x, a, c, m; // a * x는 10^12까지 커져서 int로는 넘친다 std::cin >> n >> goal >> maxTurns >> x >> a >> c >> m; std::vector<int> scores(n, 0); int winner = 0, turns = 0, rolls = 0, player = 0; while (turns < maxTurns && winner == 0) { turns++; int turnSum = 0, count = 0, face; do { // 첫 굴림은 언제나 한다 x = (a * x + c) % m; face = static_cast<int>(x % 6) + 1; rolls++; count++; turnSum += face; } while (face == 6 && count < 3); if (face == 6) turnSum = 0; // 세 번 모두 6 scores[player] += turnSum; if (scores[player] >= goal) winner = player + 1; player = (player + 1) % n; } std::cout << winner << ' ' << turns << ' ' << rolls << '\n'; for (int i = 0; i < n; i++) std::cout << (i ? " " : "") << scores[i]; std::cout << '\n'; }}
Cmain.c · 32 lines
#include <stdio.h>int main(void) { int t; scanf("%d", &t); while (t--) { int n, goal, maxTurns; long long x, a, c, m; /* a * x는 10^12까지 커져서 int(약 21억)로는 넘친다 */ scanf("%d %d %d %lld %lld %lld %lld", &n, &goal, &maxTurns, &x, &a, &c, &m); int scores[8] = {0}; int winner = 0, turns = 0, rolls = 0, player = 0; while (turns < maxTurns && winner == 0) { turns++; int turnSum = 0, count = 0, face; do { /* 첫 굴림은 언제나 한다 */ x = (a * x + c) % m; face = (int)(x % 6) + 1; rolls++; count++; turnSum += face; } while (face == 6 && count < 3); if (face == 6) turnSum = 0; /* 세 번 모두 6 */ scores[player] += turnSum; if (scores[player] >= goal) winner = player + 1; player = (player + 1) % n; } printf("%d %d %d\n", winner, turns, rolls); for (int i = 0; i < n; i++) printf(i ? " %d" : "%d", scores[i]); putchar('\n'); } return 0;}
Craykonmain.cray · 49 lines
t = Console.ReadLine().ToNumber();for (g = 0; g < t; g++){ p = Console.ReadLine().Trim().Split(); n = p[0].ToNumber(); 목표 = p[1].ToNumber(); 최대차례 = p[2].ToNumber(); x = p[3].ToNumber(); a = p[4].ToNumber(); c = p[5].ToNumber(); m = p[6].ToNumber(); 점수 = NewList(n, 0); 이긴사람 = 0; 차례수 = 0; 굴린수 = 0; 사람 = 0; while (차례수 < 최대차례 && 이긴사람 == 0) { 차례수++; 합 = 0; 번 = 0; 눈 = 0; // 크레이콘에는 do-while이 없다: 동안 (참)으로 들어가 끝에서 멈출지 묻는다(첫 굴림은 언제나 한다) while (true) { x = (a * x + c) % m; // 10^12까지라 정확하다 눈 = x % 6 + 1; 굴린수++; 번++; 합 += 눈; if (!(눈 == 6 && 번 < 3)) { break; } } if (눈 == 6) { 합 = 0; } 점수[사람] += 합; if (점수[사람] >= 목표) { 이긴사람 = 사람 + 1; } 사람 = (사람 + 1) % n; } Console.WriteLine(이긴사람 + " " + 차례수 + " " + 굴린수); Console.WriteLine(점수.Join(" "));}