35 15 2 0 6 0 8 15 0 18 4 0 18 0 7 0 13 0 24 1 0 24 0 22 21 0 4 15 0 15 11 0 26 0 31 21 0 32 2 0 2 0 13 1 0 29 4 0 5 8 0 28 18 0 8 16 0 8 27 0 29 18 0 13 26 0 1 0 14 0 25 35 0 10 25 0 3 0 23 9 0 1 8 0 19 26 0 10 20 0 33 0 26 0 27 16 ans:12 28 5 0 15 0 8 22 0 23 20 0 6 19 0 1 22 0 9 28 0 14 15 0 5 0 7 18 0 18 0 16 0 27 0 8 0 27 0 19 3 0 24 8 0 2 25 0 22 0 15 12 0 8 5 0 12 0 6 0 2 9 0 25 0 9 9 0 9 0 2 0 19 15 ans:4 38 19 36 0 15 0 23 0 17 0 9 0 34 0 13 10 0 15 0 15 4 0 26 0 5 33 0 34 0 9 0 29 0 4 0 4 20 0 24 0 3 38 0 27 0 22 7 0 35 27 0 8 0 34 36 0 5 33 0 22 7 0 18 26 0 26 17 0 22 0 12 0 27 0 8 8 0 35 0 24 0 31 0 23 0 6 0 18 0 16 27 0 9 35 ans:7 37 34 0 16 3 0 24 0 14 24 0 33 18 0 17 0 33 32 0 18 16 0 19 1 0 8 0 29 34 0 1 25 0 7 3 0 28 0 34 0 1 21 0 36 0 18 0 36 21 0 27 0 14 0 15 5 0 33 0 9 32 0 35 14 0 22 1 0 18 35 0 6 0 30 0 1 2 0 30 0 20 0 18 0 30 0 30 0 11 0 15 37 0 1 6 ans:4 I hope they can help you~ Edited by author 26.08.2009 18:29 thanks! I got great help! your tests are simply. i got WA6 and got right answers on your tests. now AC So how to deal with WA#6? Второй абзац: > Профессор A - завсегдатай симпозиума решил следует заменить на > Профессор A, завсегдатай симпозиума, решил Четвёртый абзац: > в отличии > ведь в отличии от космологов, хронологи считают Правильно: > в отличие > ведь в отличие от космологов хронологи считают (Здесь по правилам запятую рекомендуется не ставить, однако она возможна.) Четвёртый абзац: > Сейчас он просто не мог ждать ни секунды (...), поэтому он сел в свой хрономобиль и отправился на встречу. Лучше убрать второе слово "он". Пятый абзац: > Так уже сейчас Следует добавить запятую: > Так, уже сейчас В исходных данных: > Далее следуют N строк, описывающие перекрёстки. Правильно: > Далее следуют N строк, описывающих перекрёстки. В исходных данных: > Любой список, содержит Запятая лишняя. В исходных данных: > В последней строке находится два числа. заменить на > В последней строке находятся два числа. В последнем предложении исходных данных точку с запятой лучше заменить просто на запятую. И ещё: в некоторых написаниях слов с буквой 'ё' эта буква присутствует, в некоторых - нет. Нехорошо. I think that this problem has wrong tag. However, it needs tag - "Number Theory Problems"; The compiler has been changed to VC. long long is still available but we must use %I64d instead of %lld!!! Which VC? 'cuz my VC2005 eats both %lld and %I64d, both __int64 and long long. I tried to submit a Pascal solution using 64-bit integers and received wrong answer already on test #1. (The same solution with 32-bit integers received wrong answer only on test #55.) Anyway, after much experimentation, I noticed that if I change the signature of just one function (the solver for the Diophantine equation Ax + By = C) from function Diophant(A, B, C: int64; var x, y, dx, dy: int64): boolean; to function Diophant(A, B, C: integer; var x, y, dx, dy: int64): boolean; the program was accepted. I don't see why the two should produce different results, but the fact is that, on the evaluation server, they do, already on the first test case (I tried calling both and entering an endless loop if the results differ, and the program got TLE which means that the results really did differ). Of course the results of both versions were the same when I was testing on my own computer (with FreePascal -- I'm not sure which compiler is used on the evaluation server). I guess this must be due to some kind of quirk in the compiler used on the evaluation server. So if anybody else is having problems with 64-bit integers in Pascal for this task, maybe some similar workaround will work for you as well -- don't pass 64-bit integers as parameters unless really necessary. It's a bug of FreePascal This program outputs 4294967295 on server. var x: integer; begin x := 1; writeln(int64(-x)); end. Try to avoid structures like int64(-x). I hope the bug will be fixed soon. This bug is fixed in FreePascal now. Your submits with WA#1 were rejudged. My solution is like this: We find the paths of A && B. Definitely A && B will enter some circular path eventually. We assign to every junction(for A && B separately): 1. "pos" if this junction is traversed only once(before A || B enters his circular path) 2. "(pos,period)" if it appears in the circular path, where pos is the first occurrence of the junction,and period is the length of the circular path 3. "-1" if it is never visited Then for every junction we check whether its position(s) for A will meet B's. We may need to solve the equation: pos_A + period_A * x == pos_B + period_B * y where x,y >= 0 && the value on each side is minimum This can be done with euclid's method. However I am stuck on test#55. I have disposed all of my energy to find the tricky case but ended up with no result. Please help! Edited by author 23.04.2005 22:04 Have you used int64 for the intermediate result? I suspect I've got some kind of overflow Thx Of course, there are may be very big numbers! if period_A = 99999, period_B = 99998 and pos_B - pos_A = 99997, we have almost 100000^2. Good luck! I still can't pass #55 Now I suspect I made something wrong when solving pos_A + period_A * x == pos_B + period_B * y using euclid's method My method goes like this (short hands: pos_A: n1, pos_B: n2, period_A: a, period_B: b) So we want to solve n1 + ax == n2 + by, such that x, y >= 0 && n1 + ax is minimized if n1 >= n2, we just solve by - ax == n1 - n2, such that x, y >= 0 && x is minimum else ax - by == n2 - n1, such that x, y >= 0 && y is minimum Here's my code for solving ax - by == n, such that x, y >= 0 && y is minimum ( which equals to solve: by == a - n mod a (mod a) ) !! I am sorry for the readablility of the code since I don't know how to make the code look like indented. You can use my account 36057RJ to edit this msg and get indented code ################################ typedef typedef __int64 LL; LL Gcd(LL a, LL b, LL *x, LL *y) { if ( b == 0 ) { *x = 1; *y = 0; return a; } else { LL xx, yy; LL gcd = Gcd(b, a % b, &xx, &yy); *x = yy; *y = xx - (a / b) * yy; return gcd; } } LL SolveLinear(LL a, LL b, LL n) { LL result; LL x, y; LL q; LL d = Gcd(b, a, &x, &y); n = (a - n % a) % a; if ( n % d != 0 ) return -1; x *= n / d; q = a / d; result = x % q; if ( result < 0 ) result += q; return result; } #################################### Is this the right thing to do ? Thanks in advance for taking your time to check this Edited by author 26.04.2005 19:31 |
|