Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Страница 2 |
No subject | Yaroslaff | 1430. Преступление и наказание | 16 мар 2018 13:04 | 1 |
|
This may help if WA 7 | MishaRash | 1430. Преступление и наказание | 9 фев 2020 14:56 | 3 |
I have WA 7 and I found the problem on test '20 30 13456'. It's a nice case to fix program but still it doesn't fix WA7. Edited by author 09.02.2020 15:46 |
Little Hint with mathematics | Mickkie | 1430. Преступление и наказание | 16 окт 2016 12:51 | 2 |
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! :) |
WA 16, or how I lost 13 tries | [RISE] Levon Oganesyan [RAU] | 1430. Преступление и наказание | 20 июл 2014 20:50 | 3 |
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. Ouch... Thanks, I understood my problem. I am write int q, w; instead of int q = 0, w = 0; |
Страница 1 |
Hint | TakeOver | 1430. Преступление и наказание | 10 янв 2013 01:07 | 1 |
Hint TakeOver 10 янв 2013 01:07 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 =) |
WA#3 | Anton | 1430. Преступление и наказание | 19 окт 2011 13:15 | 1 |
WA#3 Anton 19 окт 2011 13:15 I have no idea ... If somebody've got AC, send some tests, pls |
limitation for the full search | luckysundog | 1430. Преступление и наказание | 18 ноя 2011 23:34 | 2 |
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? Edited by author 18.11.2011 23:48 |
AC | Rauf Agayev | 1430. Преступление и наказание | 27 ноя 2011 00:06 | 4 |
AC Rauf Agayev 23 мар 2011 23:01 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 Re: AC sklyack 27 авг 2011 01:34 I did how you said, and when I tried to pass this solution without trick, I got TL#10, with trick got AC in 0.031 sec. I really don't understand, how this trick can give so impressive speed-up? Explain me pls!! Re: AC -XraY- 18 ноя 2011 23:56 Let's suppose A >= B, (A, B) = 1; Then there is such (0 <= i < b) that (a * i) % b = (N % b). On the other hand, i <= N / a. So, i <= min(N / a, b - 1) <= min(N / a, a - 1) <= sqrt(n); Re: AC sklyack 27 ноя 2011 00:06 |
please give me idea to solve this problem, thanks!!! | hoan | 1430. Преступление и наказание | 3 янв 2011 19:57 | 5 |
Just full search. ~O(sqrt(N)) in the worst case. To avoid TL before search do: C = GCD(A,B); A /= C; B /= C; N -= (N%C); Think why you always can do this. GOOD LUCK! Oh! I forgot, that after that N must be divided by C too :) got AC now. thanx again & HAPPY NEW YEAR!!! |
If you have WA26, then use long long. | Sobolev_Team (Zhenya Sobolev, Dima Sobolev) | 1430. Преступление и наказание | 6 июл 2009 23:31 | 1 |
|
WA on test7 | Erjin Zhou | 1430. Преступление и наказание | 31 мар 2009 13:57 | 1 |
I need help... what is the test 7? |
WA#24....Please help me... | rohit | 1430. Преступление и наказание | 31 авг 2008 06:02 | 3 |
Please tell me what is test..I m stuck at this problem for long time. Guys...please tell me..I am sure my algo is correct. Maybe overflow? I use int64 everywhere. |
WA24 | rohit | 1430. Преступление и наказание | 14 фев 2008 03:23 | 1 |
WA24 rohit 14 фев 2008 03:23 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 |
Problem 1430 "Crime and punishment" has been rejudged (+) | Sandro (USU) | 1430. Преступление и наказание | 13 сен 2007 12:53 | 1 |
New tricky tests were added. Some authors got TL. Thanks to Boris Parfenenkov for idea of tests. |
Give me some test pls. I got WA26 | Valery | 1430. Преступление и наказание | 30 июн 2007 16:39 | 1 |
Give me some test:), or may be some think wrong with test???? |
HINT for those who got TLE on #24 | Chantat Eksombatchai[PONG] | 1430. Преступление и наказание | 10 мар 2010 19:54 | 7 |
B can be greater than A Good Luck ^^ N'Pong Thx for your hint. from P'Moo Edited by author 07.01.2007 11:30 Thx a lot! but why goods at moderate price cost higher than "high price" good? I don't care for value of b :) |
Why WA on #24 | The Punisher | 1430. Преступление и наказание | 15 янв 2007 23:31 | 4 |
First I got TL on #24 Then I got WA on #24 Are there large answer? Thanks. No. No large answer. How could it be large? Everything is quite simple. You can solve this problem occasionally, even if not think much. I try to took "j" goods for A$ and goods for B$ on rest money. Then I try to took "j" goods for B$ and goods for A$ on rest money. 0<="j"<=min(n/a,b) What's wrong? My single idea :my code can generate negative numbers as answer. I don't understand anything... |
I'm confused | friend | 1430. Преступление и наказание | 15 фев 2006 23:48 | 1 |
I really can't understand why i recieved WA on 1th test. I'm sure in my solution and i pass all my tests. Please give me some additional tests. Now i'm getting WA 43:( Edited by author 16.02.2006 00:12 Edited by author 16.02.2006 16:41 |
could u pls otpimize it? for test #9 and #10 | Stels | 1430. Преступление и наказание | 11 фев 2006 16:50 | 3 |
[code deleted] Edited by moderator 11.02.2006 17:32 thats true! there's no problem. it just cant pass test #9 |
test #9 | lyc84_6 | 1430. Преступление и наказание | 22 фев 2006 23:44 | 5 |
what is test #9? all my tests go good. Give a hint, please. misha ne pravil'no reshaesh', poprobyi mozgami poshevelit'! esli kone4no oni est':) I've got TL #9 then WA #24 |