Show all threads Hide all threads Show all messages Hide all messages |
WA 3 | Vasiliy | 1139. City Blocks | 8 Nov 2022 02:50 | 3 |
WA 3 Vasiliy 19 Jul 2020 23:20 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. Re: WA 3 LetsSolveSomePuzzles 4 Oct 2022 19:33 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. |
Формула Пика ван лав!!! | Egor Sibriaev | 1139. City Blocks | 2 Dec 2021 03:31 | 1 |
|
hint | [MAI] do_v_5_strok | 1139. City Blocks | 17 Jan 2021 21:06 | 1 |
hint [MAI] do_v_5_strok 17 Jan 2021 21:06 check the values of y[i] by x[i] - x[i-1] in the straight line equation > > > > > > > > use ceil() and floor() |
explanation for solution | lostbrain | 1139. City Blocks | 16 Sep 2020 22:50 | 1 |
|
WA 9 help please | Ivan | 1139. City Blocks | 8 May 2020 18:17 | 1 |
|
WA Test 8 | EvGeniy[ONPU] | 1139. City Blocks | 9 Dec 2019 18:37 | 3 |
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. |
Simpliest algorythm | Ilya Lubashov | 1139. City Blocks | 30 Sep 2019 07:23 | 1 |
//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++ |
Summary of the Algorithm(the formula derivation) | jagatsastry | 1139. City Blocks | 3 May 2018 14:07 | 4 |
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? |
Can't find tests to prove algorithm wrong (WA 3) | Kirill | 1139. City Blocks | 31 Oct 2017 01:00 | 3 |
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 ;-) |
My solution works as follows : | Mahilewets | 1139. City Blocks | 13 Jun 2017 21:25 | 1 |
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 you want to know why when gcd(M, N) = 1 Ans is M + N - 1, come in! | Huang WenHao | 1139. City Blocks | 30 Oct 2016 22:52 | 3 |
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. |
can you tell me how to solve this question | xinxin | 1139. City Blocks | 30 Oct 2016 22:41 | 2 |
|
i got accepted 0.078 sec | panic | 1139. City Blocks | 13 Dec 2015 22:38 | 5 |
i used bresenham line drawing algorithm :)) together with gcd() I'm too got AC 0.001 sec! |
TO ADMINS | mberdyshev | 1139. City Blocks | 27 Nov 2015 01:57 | 1 |
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 |
not clear | Najmaddin Akhundov | 1139. City Blocks | 24 Aug 2015 02:23 | 2 |
not clear Najmaddin Akhundov 9 Nov 2014 03:16 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. |
test 3 | ghostfreak | 1139. City Blocks | 31 Oct 2014 03:20 | 5 |
test 3 ghostfreak 5 Jul 2009 13:47 Does anybody know what is test #3? Re: test 3 Sobolev_Team (Zhenya Sobolev, Dima Sobolev) 6 Jul 2009 03:18 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 |
a mathematical explanantion | akash akash | 1139. City Blocks | 30 Aug 2014 07:52 | 2 |
|
wa3 hint - floating poing error | svg2003 | 1139. City Blocks | 3 Dec 2013 13:09 | 1 |
For whom who use floating K = n / m, try to this test: 3 99 - right answer is 98 99 3 - right answer is 98 |
Why are these tests? | Sasha | 1139. City Blocks | 12 Jul 2013 17:01 | 2 |
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. |
What is the 10 test? | NeMo | 1139. City Blocks | 11 Jun 2011 03:48 | 2 |
I think it is something like 32000 31999 |