[C/C++/C#] SPOJ Problem -> Free Positions

Started by Apidcloud, December 03, 2012, 06:26:16 pm

Previous topic - Next topic


December 03, 2012, 06:26:16 pm Last Edit: December 09, 2012, 05:59:14 am by Apidcloud
Hey guys,
today I heard about something called SPOJ - Sphere Online Judge - which basically judges your solutions to specific programming problems. I believe this system supports 48 different programming languages, which is pretty amazing. Note that every problem has a time limit, which you can find at the end of this post or by clicking on problem's title(note that the problem in the link is written in Portuguese)

Has I might join a programming group - which will join few national competitions - I tried one problem, and I'm "challenging" you to do it as well.
You can either post your solution here, so I can submit it on SPOJ or try to help you having a correct answer. Please be aware that in the problem I'll propose, these languages aren't accepted: AWK CLOJ ERL F# GO JS NODEJS PERL 6 PYTH 3.2.3 n SCALA SED TCL
You can also submit it by yourself, you just need to register an account giving an email, username, etc

I can mainly help you with C/C++/C#, hence the topic's tag

So, here's the problem:
Free Positions
(I found this problem in Brazilian SPOJ(couldn't find it in English), so I'll translate it - except output, which was "already" translated)

- Write a program that, giving a table and a list of sub rectangular parts from the table, returns the number of positions that don't belong to none of its sub-parts.

- The input consists in many test sets divided by blank lines. A test set begins with a line containing 3 numbers W, H and N, which respectively mean width, height and the number of table's sub parts. These values are under the following restrictions: 1 <= W, H <= 500 and 0 <= N <= 99. The following N lines, contain 4 integers, X1, Y1, X2 and Y2, so that (X1, Y1) and (X2,Y2) are the sub-part's position of two opposite corners. These values are under the following restrictions: 1 <= X1, X2 <= W and 1 <= Y1, Y2 <= H. The end of the input happens when W=H=N=0. This last input line shall not be considered as a test set.

- The program should print one result per line, following the format described in below's output example.


1 1 1
1 1 1 1

2 2 2
1 1 1 2
1 1 2 1

493 182 3
349 148 363 146
241 123 443 147
303 124 293 17

0 0 0

There is no empty spots.
There is no empty spot.
There are 83470 empty spots.

Problem added by Wanderley GuimarĂ£es
Date: 2007-10-11
Time limit: 1s(RunTime execution made by the server)
Memory limit: 256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)

Few Notes:
- Input is always made by the user - no external files are needed - (e.g. using cin >> x_variable in C++);
- Output should be exactly as the one in the example;
- main should always return 0( int main() { /*...*/ return 0; } )

From time to time, I'll try to write down more problems(that if you don't read and do it using SPOJ) and its possible solution - If I already have it.

I made a Free Positions solution in about 10~15minutes in paper. It worked in my first try(both when compiling it on vs and when submitting to SPOJ)
I can post my solution here, but I won't post it for now, since I would like to check your solutions without cheating  :haha:

Instead of wanting to be somebody else, rather become somebody else

"I will treasure the knowledge like a squirrel treasures acorns."

Gibbo Glast 2D Engine - The sky is no longer a limit