|
|
I tried a number of tests, and neither of p,q is very big(Many of them beyond 1000). Maybe there's some mathematical property of the f function? If you know that 'n' is on period, you may find 'q' by checking n+1, n+2, n+3, ... till you hit identical to 'n' state. Then, when you know 'q', you may iterate from states '1' and '1+q' till they match, this way you'll find 'p'. This relies on a guess that iteratively you won't get TL. I used value of 1'500'000, but I don't know if it has a proof or if it means weak tests. For A1>0 there is a proof as there are only ~1M distinct Xi, Xi+1 pairs whose product does not overflow 100'000. But as for A1=0 case - I don't know... Theoretically p or q can be as large as ~100'000^2. Is is possible not to set limitation on number of different pairs in solution. I remembered last pair (x_s, x_{s+1}) where s is the biggest power of two less than current position. And I compared all pairs till the next power of two to this remembered pair. It is not clear from problem statement, but is true for all tests: B1 >= B2. Where it is required to subtract C, C is positive. Edited by author 24.04.2009 15:03 "You may assume that all intermediate values of H and all values of F fit in range [0..100000]" This should be put to problem statement, rather than to input description. Otherwise claim about periodicity is wrong. Consider the following sequence: X1=0, X2=2 A1=0, A2=0, A3=2, A4=0 B1=3, B2=2, C=5 0 2 -1 -2 -4 -8 -16 ... -(2^n) ... It's not periodic, but all coefficients (as well as initial elements) are non-negative. Ok.. here is my hint: Choose p large enough to be sure you are in period of the given sequence and try findind q. Edited by author 07.09.2008 13:47 What is the maximum value of p? I have two programs 1st - a right one wich have WA#2 and second - gets AC if you remove comment you get WA#2 WHY? I realy can't understand, anybody please help me! struct point { int ID; double x,y; }; int Chet(point a) { // if (a.x > 0 && a.y >=0) return 0; // if (a.x <=0 && a.y > 0) // return 1; // if (a.x < 0 && a.y <=0) // return 2; // if (a.x >=0 && a.y < 0) // return 3; } inline bool Tr(const point &a, const point &b) { return a.x*b.y-a.y*b.x > 0; } inline bool operator < (const point &a, const point &b) { int ca = Chet(a); int cb = Chet(b); return ca < cb || ca==cb && Tr(a,b); } Oh sorry, I mean problem 1175, admins you can correct it Can someone give me some tests? I got wa on test#6 Although it got AC, but I doubt whether it will give an correct answer on all test... :( My algo is simply find a large num,assume it is on the cycle,and to find the periods... I think it exist a maths way......or at least, have a good search method use something like hash and so on... |
|
|