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 TCLYou 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.
Input- 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.
Output- The program should print one result per line, following the format described in below's output example.
Example
QuoteInput:
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
Output:
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: 256MBCluster: 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
Arrivederci