Proficient.
Put your skills to the test.

Problem summary

Repeated addition of a positive integer K reaches its positive multiples. Find the smallest such multiple whose decimal digits are all equal. Output its repeated digit and its length, or Impossible if none exists.

Source clarification. The short statement leaves the minimum-target tie-breaking implicit. The official editorial explicitly requires the shortest length, then the smallest digit: https://infos.infosbg.com/files/Contests/ETI/2011/B/analyses/calcgame_analysis.pdf . This implementation follows that intended rule.

Constraints

1 ≤ K ≤ 999. The calculator has no length or time restriction.

Worked example

Original statement sample.

37

1 3

Solution analysis

1. There is no need to construct an enormous multiple. For a fixed digit d, keep the remainder r of d,dd,ddd,… modulo K. Appending d changes the remainder to (10r+d)%K. A zero remainder identifies a divisible repeated-digit number.
2. For each digit 1…9, test at most K lengths. Starting at remainder 0, if no return to zero occurs in the first K transitions, one of the nonzero remainders repeats. Future transitions then cycle without reaching zero, so that digit cannot work.
3. The official editorial specifies the smallest target: choose the shortest successful length, breaking equal-length ties by the smaller digit. Decimal length is compared before the digit because every positive shorter decimal number is smaller. Zero is excluded because positive repeated addition cannot reach zero.
4. For K=37, the successive remainders of 1,11,111 are 1,11,0, yielding 1 3. For K=25, the last two digits of a repeated nonzero digit are never divisible by 25, so all searches fail and the result is Impossible.

Why it works

For each length, the recurrence gives exactly the remainder of the corresponding repeated-digit integer. The K-state deterministic remainder process either returns to zero within K steps or enters a cycle excluding zero. Testing all nine nonzero digits therefore finds a target exactly when one exists.

Watch out. Do not use a machine integer to build the whole repeated-digit target. The digit 0 is not a valid positive target. A target may already equal K, so one-digit answers are possible.

An independently written complete program with standard headers.

#include<iostream>
using namespace std;
int main(){
    int divisor;
    cin>>divisor;
    int bestDigit=0;
    int bestLength=divisor+1;
    for(int digit=1;digit<=9;digit++){
        int remainder=0;
        for(int length=1;length<=divisor;length++){
            // Append the digit using only a bounded remainder.
            remainder=(10*remainder+digit)%divisor;
            if(remainder==0){
                if(length<bestLength){
                    bestLength=length;
                    bestDigit=digit;
                }
                break;
            }
        }
    }
    if(bestDigit==0){
        cout<<"Impossible\n";
    }
    else{
        cout<<bestDigit<<' '<<bestLength<<'\n';
    }
}