I have correctly performed all tests from the forum, but still WA 3. Please tell me what the problem is or write new tests for me. 8 30 => 35 and not 36 12 26 => 35 and not 36 14 28 => 39 and not 40 15 30 => 42 and not 43 16 32 => 45 and not 46 20 22 => 39 and not 40 20 43 => 60 and not 61 28 27 => 52 (you get the idea) Thanks for the tests, pal. check the values of y[i] by x[i] - x[i-1] in the straight line equation > > > > > > > > use ceil() and floor() What is test 8? What input ? Edited by author 13.11.2009 15:02 Edited by author 13.11.2009 15:02 Now all ok? i find my mistake. //pseudo code divider = first_input-1; dividend = second_input-1; result: divider + dividend - FindCrossesOnTheWay(dividend,divider) *FindCrossesOnTheWay if(divider < dividend) swap() for(i=1;i<=divider;i++) if((dividend * i) % divider == 0) crosses++ Well, this is for those who didnt get the method. Consider N: no of rows of blocks M: no of columns of the blocks (N+1 and M+1 are the input). Crosspoint here refers to a point where a horizontal and a vertical line meet.
For each line that the plane intersects, a new block is introduced. Consider the south western most point also as one such point. No of horizontal lines intersected=N. No of vertical lines intersected=M. But the southwestern most point has been counted twice and it introduces the same first block. If gcd(M,N)==1, there is no intermediate point where the line passes over a crosspoint. Hence no. of blocks = M+N-1. If gcd(M,N)!=1, the whole grid can be split horizontally at the points where the line passes over a crosspoint and each of them can be considered separately with that cross point as the south westernmost point of the subproblem. There are gcd(M,N) such points. Say a=gcd(M,N). Then in each subproblem the line flies over M/a+N/a-1 blocks. Totally the line flies over a*(M/a+N/a-1) blocks. ie. M+N-a blocks. Edited by author 29.11.2007 02:42 Edited by author 26.09.2015 00:39 Or you can do it simply by tracing error: int filled_pixels = 0; long long error = 0; for (int x = 1; x <= dx; x++) { filled_pixels++; error += dy; if (error >= dx) { error -= dx; if (error != 0) filled_pixels++; } } The code is incomplete, but the idea should be clear. We need to maintain error. When we exceed this threshold, that means we have crossed horizontal line. M+N-a works in any case, even if gcd(M,N)=1, right? I wrote simple implementation but can't figure out test to prove my solution wrong. 4 3 -> 4 3 3 -> 2 4 5 -> 6 4 6 -> 7 3 8 -> 8 6 5 -> 8 6 8 -> 10 #include "stdio.h" #include <stdlib.h> int main(void) { int bigger, lesser, a, b; scanf("%d", &a); scanf("%d", &b); if (a >= b) { bigger = a - 1; lesser = b - 1; } else { bigger = b - 1; lesser = a - 1; }
if (bigger % lesser == 0) { printf("%d\n", bigger); return 0; }
printf("%d\n", bigger + lesser - 1);
return 0; } Found it 7 11 -> 14 13 21 -> 16 GCD is the key ;-) For each x (x=0,1,2,..,n-1) (x is horizontal axis) find y0=x*tg(a) and y1=(x+1)*tg(a), where tg(a) is (m-1)/(n-1). Add to answer floor (y1) - floor(y0) +1. If y1 is a whole number then subtract 1 from answer. If the plane fly across a edge and it will produce a point then produce a new block so the answer add one. If gcd(M, N) = 1, it means there is no situation that the plane fly across the crossroads. See from left to right it produce M point and see from north to south it produce N point, but one is calculate twice, so there are M + N - 1 points and Ans is M + N - 1. and what if gcd(m,n)!= 1 ?? Sorry, can't get you and what if gcd(m,n)!= 1 ?? Sorry, can't get you Reduce to smaller problem (m / gcd(m,n), n / gcd(m,n)) and then use it to solve the original problem. i used bresenham line drawing algorithm :)) together with gcd() i got 0.031 sec I have 0,015 I have 0.001 I'm too got AC 0.001 sec! I use Python 3.5 Is it right that it's prohibited to import function gcd from library math? But it's allowed to import this function from library fractions Edited by author 27.11.2015 02:04 for input 3 3, I guess the result should be 3. Why it is 2? Because the matrix is formed by (n-1) x (m-1) squares, and nxm corners, understand? You need to calculare how much squares has you overflown. Does anybody know what is test #3? Here is some tests for you: 14 12 Answer: 23 1001 101 Answer: 1000 But 1001 101 Answer: 1099 And 1001 1001 Answer: 1000 And 1001 2 Answer: 1000 1001 101 and 1001 1001 and 1001 2 all will be 1000 You might try 99 3 and 3 99 to check if they both give the same answer. They likely do not due to rounding error if you are using a slope-based solution. Edited by author 31.10.2014 03:21 For whom who use floating K = n / m, try to this test: 3 99 - right answer is 98 99 3 - right answer is 98 4 3 - 4 3 3 - 2 Is it not true 4 3 - 6, 3 3 - 3? Read the statement carefully: M and N are the number of streets, which encompass M-1 and N-1 blocks. I think it is something like 32000 31999 |
|