Proficient.
Put your skills to the test.

Problem summary

Construct an exactly uniform generator for 0…M−1 from repeated independent uniform digits 0…N−1. The only state between days is a number below 500. Minimize the expected number of days.

Constraints

2 ≤ N,M ≤ 30; 0 ≤ X,Y < 500; 0 ≤ R < N; 0 ≤ T < M. Mean days C must not exceed 100. Score uses Q=min((C*+0.005)/C,1) and S=(1+Q^10−(1−Q)^0.15)/2, with C* the optimal mean.

Worked example

The displayed communication is the official deliberately incorrect example: probabilities are 4/7,2/7,1/7 and the judge must reject it. It is not the output of this implementation. Our mock separately checks the valid uniform transition system.

setup(2,3)
proc(0,0)
proc(0,1)
proc(1,0)
proc(1,1)
proc(2,0)
proc(2,1)

{false,1}
{true,0}
{false,2}
{true,1}
{false,0}
{true,2}

Solution analysis

1. Represent a uniform integer value in [0,count), with count<M. After seeing a fresh base-N digit R, replace them by count×N and value×N+R. The value remains uniform across the expanded interval.
2. Let accepted=floor(count/M)×M. If value<accepted, return value mod M. Otherwise subtract accepted from both count and value: the rejected suffix remains uniform and can be recycled. Encode the pair as count(count−1)/2+value. With count≤29 this is at most 434, and (1,0) is state 0.
3. For N=2,M=3, state 0 first expands to two possibilities and continues. The next expansion has four equally likely outcomes: values 0,1,2 terminate with those respective outputs; value 3 returns to state 0. The expected length is 2/(3/4)=8/3 days. This differs from the deliberately invalid official example.
4. Every day uses as many complete groups of M outcomes as possible and retains only the incomplete suffix. The residual path count after d digits is N^d mod M; hence the survival probability is (N^d mod M)/N^d. This gives an independently checkable exact mean as a rapidly convergent sum; finite simulation can fluctuate, so reported judge scores are not guaranteed.

Why it works

Conditional on continuing, the interval value is uniform, and appending an independent digit preserves uniformity. The accepted prefix contains equally many representatives of every residue modulo M, so every termination layer contributes identical probability to each output. Residual probability tends to zero because at depth d fewer than M equally likely prefixes survive, so termination is almost sure and the output probabilities sum to one. After blocks of five days, conditional survival is at most 29/32, since N^5≥32 and count≥1. Thus mean≤5/(1−29/32)=160/3<100. The triangular encoding is injective on all valid pairs and stays below 500.

Watch out. Uniform output requires equally sized residue classes; value%M without rejection is biased. Recycle the suffix instead of assigning all rejected outcomes the same value. Global setup parameters may be stored, but the evolving random state must be carried by X.

Grader functions only. setup stores fixed parameters; proc derives its entire changing state from X. The source includes fortuna.h; no standard-input replacement is supplied.

#include"fortuna.h"
#include<utility>
namespace{
int base;
int target;
} // namespace
void setup(int N,int M){
    base=N;
    target=M;
}
std::pair<bool,int>proc(int X,int R){
    int count=1;
    while(count*(count+1)/2<=X){
        ++count;
    }
    int value=X-count*(count-1)/2;
    count*=base;
    value=value*base+R;
    int accepted=count/target*target;
    if(value<accepted){
        return {true,value%target};
    }
    // Retain the uniformly distributed rejected interval rather than restart.
    count-=accepted;
    value-=accepted;
    return {false,count*(count-1)/2+value};
}