Link to the problem on Timus Online Judge

The problem statement is completely straight forward with no hidden tricks :). Yeah yeah I know that you know problem statement is straight forward :), so let's talk about solution.

What do I do in a problem like this? I pay attention to range of input. Let's rewrite what problem wants for output :

The problem statement is completely straight forward with no hidden tricks :). Yeah yeah I know that you know problem statement is straight forward :), so let's talk about solution.

What do I do in a problem like this? I pay attention to range of input. Let's rewrite what problem wants for output :

*N*=*A*+ (*A*+ 1) + … + (*A*+*P*− 1)- N = P*A + 0 + 1 + 2 + ... + (P-1)
- N = P*A + (P-1)*P/2

Can we iterate over all possible values for P? or What could be maximum value for P according to range of input? Yes, what is the maximum value of P if N=10^9. If you look at the equations, P would be less than square root of 10^9, about 33,000, that's good, cause if you can iterate over all possible values for P, then A would be known in the equation.

What is value of A if we know N and P? A = ( 2*N - (P-1)*P ) / (2*P) such that : numerator must be positive and numerator must be divisible by denominator, then you can pick maximum value over 33,000 possible values for P.

What is value of A if we know N and P? A = ( 2*N - (P-1)*P ) / (2*P) such that : numerator must be positive and numerator must be divisible by denominator, then you can pick maximum value over 33,000 possible values for P.

## No comments:

## Post a Comment