Submit  All submissions  Best solutions  Back to list 
BOARD  Counting red squares 
Wersja polska  English version 
Your task is to count all red squares from defined area in the following infinite board:
Input
The input consist of unknown number of tests. Each of them contain one line with four integers x1, y1, x2, y2 (0<=all<1000001). The first two are the coordinates of the bottom left corner of the rectangle and the last two are the coordinates of the top right corner of the rectangle.
Output
For each test print one line with the number of red squares that the rectangle contains.
Example
Input: 0 0 2 2
2 1 4 3
Output:
3
2
Added by:  Piotr Kąkol 
Date:  20110714 
Time limit:  5s10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: SCM qobi 
Resource:  Copy of Michael Suchacz's task: DCZPROST 
hide comments


20140311 06:08:37 Hallvard Norheim Bø
@Piotr: this problem is broken, since the image doesn't show (the image source path is using spoj.pl). edit: looks like it is fixed now :) Last edit: 20140519 19:35:09 

20120221 10:23:10 Jander
@weltfremd  I suspect we do have different methods. You'll have to pop on to the IRC channel sometime  quite happy to discuss there :) 

20120221 05:10:46 weltfremd
This doesn't have to look too messy. There's a rather elegant formula for 0 0 x y. But according to the time your solution needs I think you took a different approach ;) 

20120219 19:42:19 Jander
@weltfremd  Yes, it looks like I need to do some elimination then. I will admit to not liking that part of my code as it looks messy. 

20120218 14:41:10 weltfremd
Thank you Jander :) Well, don't scratch to hard, maybe it's all about reading the input. But if there's a power of 1 in your solution, you should eliminate that. That's what saved me another 6 chars (though I had then again to add one char to compensate some strange behaviour of awk 3.1.6 ;)) 

20120218 10:57:35 Jander
@Weltfremd  very impressed at how short you've managed to get this one. I'm now scratching my head thinking about how I can get the calculations shorter :) 

20120215 21:17:31 weltfremd
@Piotr: Hi :) Would you tell me for which input my submission 6509554 fails? I've let it compete my AC solution with random input for quite a while now, but can't find any different behaviour. It's okay, I found out what the problem was on ideone. :) Last edit: 20120217 18:38:39 

20111020 09:00:24 Jander
It's only taken me just over three months to work this one out, but I got there in the end :) Perl seems to do quite well at this one. 

20110730 22:35:39 Piotr KÄ…kol
@HWK  Again the same trick. ;) There are not many variables left four of which are necessary. ;) 

20110730 20:27:00 HWK
@Piotr: Again one byte. But I guess it's still not the right var. Thus what about 121? ;) 