GIVE ME SOME TEST!!!!!! I STILL HAVE WA#2!!!!!!!!!

I have WA 7 and I found the problem on test '20 30 13456'.

kek

My approach divides into 2 cases

I) A>= sqrt(N) or B>=sqrt(N)
  this can be solved by brute force in O(sqrt(N))

II) A<sqrt(N) and B<sqrt(N)
  now this is more interesting
  in case of gcd(A,B)=1
  you can proof that there exist x,y>=0 that A*x+B*y = N
    since A*x congruent to N (mod B) -> x = N*inv(A,B) % B
    hence 0<=x<=B-1 but B<sqrt(N) and A<sqrt(N)
    then A*x < N so y >= 0
  in case of gcd(A,B)>1
    that's your work!

:)

Hi all.

I tried to solve this problem with standart method. I devide all numbers on GCD, and calculate all x in A*x + B*y and I tried find the maximum T, T <= N.

In cicle I write something like this:
if ( max < T )
{
   max = T;
   //something too
}
and have WA16.
After WA16 I tried fix my program, but don't find anything global. Fix something right on wrong, I 13 times get WA 1 - 16.

Then I changed ( max < T ) on ( max <= T ), and don't send, because did not think, what that will be changed WA16 on AC. I was wrong.

I don't know why that fix is right, can someone explain me?

Thanks. Sorry for bad English.

Who solved it. GIVE ME SOME TEST PLEASE!!!!!!!

when you search x and y (A*x+B*y = N)
use something like
this for x:= 0 to min(n div a, trunc(sqrt(n))) do
=)

Given A B N
D=GCD(A,B); then N/=D and N*=D and N/=D;because we must find closed number to N;
A/=D;
B/=D;

then full search

if(A>B) for(i=0;i<=N/A;i++){type here equation Ai+By=N, try to find x and y}                 else for(i=0;i<=N/B;i++){type here equation Ax+Bi=N , try to find x and y}

*trick:in loop, if Ax+By=N then break,that means we have already found number..


Edited by author 24.03.2011 01:44

Suppose:
1) A>B
2) gcd(A,B)=1
Need to find maximal A*x + B*y
I try all 0 <= x <= (N-B) / A + 1
This upper limit gives AC, but is it optimal?

I have no idea ... If somebody've got AC, send some tests, pls

B can be greater than A
Good Luck ^^

I need help...
what is the test 7?

Please tell me what is test..I m stuck at this problem for long time.

Please tell me what test..I am stuck at this problem for long time.

Edited by author 19.04.2008 02:47

Edited by author 19.04.2008 02:48

New tricky tests were added. Some authors got TL. Thanks to Boris Parfenenkov for idea of tests.

Give me some test:), or may be some think wrong with test????

First I got TL on #24
Then I got WA on #24
Are there large answer?
 Thanks.

Give me some test please!!!!! I've got WA!!!

Edited by author 11.02.2006 14:28