Does anybody know the algorithms used in the contest mentioned above?
I mean problems 12461 through 12470. I only need the names of the algorithms.
Thanks in advance!
![:D](./images/smilies/icon_biggrin.gif)
Moderator: Board moderators
Hi and thanks for your help!nupt-xxp wrote:yes, as brianfry713 says,i just plus that the 12467 can be solved by KMP.
and i don't know how to solve 12470,Could somebody tell me how to solve it?
maybe it's matrics , but i don't know its details,Could someone explain it to me ?
Please..
sorry for my bad english
Thanks , i solved it! And the picture you shows is wonderful !AhmadKhatar wrote:Hi and thanks for your help!nupt-xxp wrote:yes, as brianfry713 says,i just plus that the 12467 can be solved by KMP.
and i don't know how to solve 12470,Could somebody tell me how to solve it?
maybe it's matrics , but i don't know its details,Could someone explain it to me ?
Please..
sorry for my bad english
I solved it using the recurrence attached at the bottom.
Then you can use fast exponentiation to find the answer. For example to find matrix F to the power of n (i.e. F(n)):
if ( n is 0 ){
return unit-matrix(i.e. I);
}
else if ( n is even ){
return F(n/2)*F(n/2);
}
else{
return F(n-1)*F(1);
}
Remember that at each step of the recursion you should use modulus. Otherwise the result will be an overflow.
Now i'm thinking 12464,but i've no idea to solve it even you give the hints above.brianfry713 wrote:12461 - Airplane - Probability theory.
12462 - Rectangle - I haven't solved it yet.
12463 - Little Nephew - Simple math.
12464 - Professor Lazy, Ph.D. - Simulation, GCD, rational numbers.
12465 - The Turanga Leela Problem - I haven't solved it yet.
12466 - Ancestors - I haven't solved it yet but you could call it graph theory.
12467 - Secret Word - String processing.
12468 - Zapping - Simple math, absolute value.
12469 - Stones - DP.
12470 - Tribonacci - I haven't solved it yet but you could try the matrix-power method.
think you !i solved it!brianfry713 wrote:On 12464 Try to solve the sample input with small n first. Code the rationals with two variables, one for the numerator and one for the denominator.