Round and round it goes
Time limit1sMemory limit1024 MB
Pick 32-bit integers W and S so the loop starting at W with step S never stops, and for R2 maximize how many times a new minimum is printed.
- Level
Medium7 of 10
- Topics
- Number theory, Math, Simulation
- Solved
- No attempts yet
Problem
Last month, Dexter created the best infinite loop ever. However, his sister DeeDee used his computer to check her Facebook page, and meanwhile she managed to erase two numbers from Dexter's program.
Here is the damaged program in Java. (Check the input file for the same code in other languages.)
public class R {
static boolean magic(int x) {
int foo = 0;
while (x > 1)
for (int y=2; ; ++y) {
if (y==x) return foo≤0;
if (magic(y) && x%y==0) { x/=y; ++foo; break; }
}
return true;
}
public static void main(String[] argv) {
int where = ??????;
int step = ??????;
int best = where;
while (step != 0) {
where += step;
if (where < best) { best=where; System.out.println("*"); }
if (!magic(where)) break;
}
}
}
Replace the two "??????" placeholders with integers W and S. Both must fit in a signed 32-bit integer: .
In the easy data set R1, submit any two integers W and S such that the program runs in an infinite loop when where starts at W and step starts at S.
In the hard data set R2, submit W and S that satisfy the R1 condition and also maximize the number of stars (*) the program prints. Any pair that meets both conditions is accepted.
Input
For your convenience, the input file contains the program in multiple languages: r.java, r.py, and r.cpp. All these programs are equivalent.
Output
Output a single line with two space-separated integers W and S.