Proficient.
Put your skills to the test.

Problem summary

Given the correct answers to a multiple choice test, find the smallest positive M<1000 maximizing the score of this rule. Start each question at the first prime p at least M for the first question, or strictly greater than the previous stopping number later. Label p with a, then successive integers with b,c,d,a,... Stop at the first multiple of 13 and select the following letter.

Constraints

1 ≤ n ≤ 50; 1 ≤ M < 1000.

Worked example

An independently prepared example for this explanation.

2
ac

1

Solution analysis

1. Try every permitted M in increasing order. For each question find the next prime by trial division; then compute the stopping multiple as 13 times the ceiling of p/13.
2. If the stopping multiple is t, its letter has index (t−p) modulo 4. The selected next letter therefore has index (t−p+1) modulo 4. Start the next prime search at t+1.
3. For M=1 the first prime is 2 and the stop is 13, producing a. The next prime is 17 and the stop is 26, producing c. Both answers match the sample.

Why it works

The computed t is exactly the first permitted multiple of 13. The modular formula counts exactly the letter increments including the final advance. Therefore every simulated score is correct; exhaustive increasing enumeration with strict score improvement returns the smallest maximizer.

Watch out. 1 is not prime. Select the letter after the stopping letter, and begin the next prime search strictly after the stopping number.

An independently written complete program with standard headers.

#include<iostream>
#include<string>
using namespace std;
bool prime(int value){
    if(value<2){
        return false;
    }
    for(int d=2;d*d<=value;d++){
        if(value%d==0){
            return false;
        }
    }
    return true;
}
int main(){
    // Compute the exact archive answer using the method explained above.
    int n;
    string correct;
    cin>>n>>correct;
    int best=-1;
    int answer=1;
    for(int start=1;start<1000;start++){
        int p=start;
        int score=0;
        for(int question=0;question<n;question++){
            while(!prime(p)){
                p++;
            }
            int stop=((p+12)/13)*13;
            char chosen=static_cast<char>('a'+(stop-p+1)%4);
            score+=chosen==correct[question];
            p=stop+1;
        }
        if(score>best){
            best=score;
            answer=start;
        }
    }
    cout<<answer<<'\n';
}