I am sure that my program is right, but i get WA on test 16. Do somebody know this test or can say something interesting? I think, you haven't really proved your algorithm. I guess it's much more interesting than just gcd. Sergei Try using long long and read your data like this scanf( "%I64d%I64d%I64d%I64d%I64d%I64d", &p, &q, &sx, &sy, &ex, &ey ); Thanks for all, if not you I die near my PC. scanf("%lld%lld%lld%lld%lld%lld", &P, &Q, &SL, &SC, &X, &Y); => WA 16 cin >> P >> Q >> SL >> SC >> X >> Y; => AC Is there anyone who can explain this? Have somebody any things about test N 26? Thank you! I have founf a mistake. AC now. I had WA 26 too. Stuped mistake. =) Was: ( v + f + i*p + k*q )%2==0 && ( -v + f + i*p - k*q )%2==0 && ( u + s - i*q - k*p )%2==0 && ( -u + s - i*q + k*p )%2==0 This get AC: ( v + f + i*(p/g) + k*(q/g) )%2==0 && ( -v + f + i*(p/g) - k*(q/g) )%2==0 && ( u + s - i*(q/g) - k*(p/g) )%2==0 && ( -u + s - i*(q/g) + k*(p/g) )%2==0 i guess || instead of && ? [code deleted] Should I use long arithmetic?Thank!!! Edited by author 06.02.2008 02:47 Somebody,who solved this problem,please,answer:what 25-th test is?Thank! Edited by author 06.02.2008 02:48 I know, that on test 25 x1==x2 and right answer is NO. Anybody,who know #25,please,help me!!! Edited by author 24.08.2007 04:43 Oh,need a help! Edited by author 24.08.2007 04:41 Please,give me some interesting tests. Edited by author 24.08.2007 04:43 AC finally! And I am still not sure my math solution is unbeatable. Does anybody know something about test 26? So what troubles did you had with this test? because i am having wa26 too :) A standart way of solution has appeared too slow(TLE14)! Standard way is to make Hermit form above __int64 of the matrix A= [p q -p -q] [q p q p] or form [0 0 * *] [0 0 0 *] by Gauss operations on columns in int ring. For initial A and Hermit form answer is equel. I were very suprized what for so small matrix we have big Time. This is due to many operations need to make zeros. Excuse me! I got quick AC(0.015) by replacing __int64 by int in the same program. I think that it because weak tests It was very interesting to solve this problem. There are some tests: test 1: 1 1 -2000000000 -2000000000 2000000000 2000000000 Yes test 2: 2 3 0 0 0 1 Yes Please help! I got WA on 9 test! A maths problem...... First, let m = x2 - x1, n = y2 - y1, d:= gcd(p, q) {assume p, q > 0, this is no harm but convenient} Second, discuss four trivial case: 1. (m = 0) and (n = 0) {Y} 2. (p = 0) and (q = 0) {N} 3. (p = 0) or (q = 0) {Y / N} 4. (m mod d <> 0) or (n mod d <> 0) {N} Third, make p = p / d, q = q / d, m = m / d, n = n / d Fourth, find x and y so that p * x + q * y = 1. Let A1 = x * m , B1 = y * m A2 = y * n , B2 = x * n You job is to judge whether there exist k1 and k2 so that (A1 + A2 + k1 * p + k2 * q ) and (B1 + B2 + k1 * q + k2 * p) are both even numbers, if so, output 'YES', otherwise 'NO'. By the way, just check (k1 = 1, 2) and (k2 = 1, 2) are enough... I have proved my algo is right. Anyway, if you doubt whether it is right, you could try to prove or disprove it by yourself, too. If you have another algo,I will be pleased if you could write it down. Sorry for my bad English, hope it can help :) Edited by author 16.05.2005 21:01 I did almost the same, but... 1) I didn't care about p=0 or q=0 2) I didn't cate about p<0 or q<0 So, I assumed that (p>0) and (q>0) - it seemed so evident from the problems's situation (-: And after having divided everything by gcd, I do the following: if p mod 2 + q mod 2 = 1 then (* p is even and q is odd or vice versa *) ___Result := true else (* both p and q are odd *) ___Result := ( deltaX + deltaY ) mod 2 = 0 ______(* we can reach a point iff its coords are both even or odd at the same time *) And I got AC. http://acm.timus.ru/status.aspx?space=1&pos=903260I use: if( Abs( Abs( DI - SI ) - Abs( DJ - SJ ) ) % NOD( Abs( P - Q ), 2 * nod_pq ) != 0 ) ____Result = false; Sorry, but what does it mean: 1) DI 2) SI 3) DJ 4) SJ 5) NOD( Abs( P - Q ), 2 * nod_pq )!=Factorial(GCD(abs(p-q),2*qcd(p,q))) use int64 to make difference and you'll get AC! Like me ::) |
|