Many Left

Problem code: MANYLEFT

All submissions for this problem are available.

The classical game of OneLeft is played as follows. Some pegs are placed on an NxN grid. Initially, at least one cell is empty and at least one contains a peg (each cell contains at most one peg). A move consists of jumping one peg over an adjacent peg to an empty cell, and removing the peg that was jumped over. Formally, if there is a peg in cell (x1, y1), and cell (x2, y2) is empty, and (x1-x2, y1-y2) is one of (0, 2), (0, -2), (2, 0), or (-2, 0), and there is a peg in cell ((x1+x2)/2, (y1+y2)/2), then the peg in cell (x1, y1) may be moved to cell (x2, y2) and the peg in cell ((x1+x2)/2, (y1+y2)/2) removed. The coordinate (0, 0) indicates the top-left corner, (N-1, 0) indicates the top-right corner, (0, N-1) indicates the bottom-left corner, and (N-1, N-1) indicates the bottom-right corner.

The game continues until no more moves are possible. Normally the goal of OneLeft is to leave a single peg on the grid. However, in this problem the goal is to leave as many pegs as possible. Optimal solutions are not required, but solutions that leave more pegs will score more points.

Input

Input begins with an integer N, the size of the grid. N lines follow with N characters each, representing the grid. A '.' character indicates an empty cell, and a '*' character indicates a peg.

Output

For each test case, first output the number of moves in your solution. Then output each move in the form "x1 y1 x2 y2", which indicates a peg moving from (x1,y1) to (x2,y2). Any whitespace in your solution will be ignored.

Scoring

Your score for each test case is the fraction of cells containing pegs after performing the moves in your solution. Your overall score is the average of your scores on the individual test cases. Invalid solutions will be judged as "wrong answer". In particular, if any legal moves exist after the moves in your solution have been performed, your solution will considered invalid.

Sample Input 1

6
..*..*
*..*.*
***.**
.***..
****..
**.*.*

Sample Output 1

13
1 3 1 1
3 3 1 3
0 5 0 3
0 2 0 0
3 5 3 3
5 2 3 2
5 0 5 2
3 2 3 0
2 4 0 4
0 3 0 5
3 0 1 0
0 0 2 0
0 5 2 5

Sample Input 2

5
.*.*.
..*..
*...*
...*.
.*...

Sample Output 2

0

The first sample output scores 8/36 = 0.2222.
The second sample output scores 7/25 = 0.28.
Recall that the goal is to maximize your score.

Test Case Generation

For each official test file, N is chosen randomly and uniformly between 10 and 30, inclusive. A real number D is chosen randomly and uniformly between 0.5 and 0.95, then each cell is independently chosen to contain a peg with probability D.

Author: pieguy
Tester: laycurse
Editorial http://discuss.codechef.com/problems/MANYLEFT
Date Added: 30-09-2012
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

Sorry for the confusion.

david_adm @ 1 Nov 2012 11:05 PM
Sorry for the confusion. There is only 1 test case per file and input begins with N. The problem statement should be fixed shortly.

Thanks for the fix. I delete

cyberax @ 2 Nov 2012 07:43 AM
Thanks for the fix. I delete my previous comment, as it is no longer relevant.

atq there should be a peg in

anubhavhcm @ 2 Nov 2012 12:11 PM
atq there should be a peg in (x1+x2)/2,(y1+y2)/2; but in first case (1 3 1 1) there is no peg at (1,2) how it is valid??

@anubhavhcm: I got some wa

shafaet @ 2 Nov 2012 09:40 PM
@anubhavhcm: I got some wa for this, read the first paragraph very carefully.

I got a score 0.73 but in the

sakuag333 @ 3 Nov 2012 03:35 AM
I got a score 0.73 but in the contest ranking it is being displayed as 0.683 . why ?

@jehad I have the same doubt.

cherudim @ 3 Nov 2012 01:20 PM
@jehad I have the same doubt. Can admins expound why to us?

It seems the score on the

hiroto_adm @ 4 Nov 2012 12:01 AM
It seems the score on the current page is delayed (using old maximum score), and the score on the overall ranking (shown in the top page of the contest) is correct.

@adm: as it is said in the

mkmukund10 @ 4 Nov 2012 02:45 PM
@adm: as it is said in the question there should be a peg in (x1+x2)/2,(y1+y2)/2(which is to be removed if the move is possible); but in first case (1 3 1 1) there is no peg at (1,2) how it is valid??

@mkmukund10 Please read the

hiroto_adm @ 5 Nov 2012 10:15 AM
@mkmukund10 Please read the problem statements (especially the coordinate systems) and check the sample input more carefully. There is a peg at (1,2) in the first sample case.

@admin: When I am trying to

rajneesh2k10 @ 11 Nov 2012 10:43 PM
@admin: When I am trying to import "random" in my python, judge is showing a runtime error. I believe its because my code has thrown some exception to the judge. In one of my successful submissions I just included the import random statement, and didn't use it anywhere, still I got the same runtime error. Can you please tell me what can be the possible reason? 'm I missing something? I couldn't find any thing in wiki related to it. One difference that I can see is, 'm using python 3.3.0 and judge has python 3.1.2. Not sure if its because of that.

@admin: please update before

rajneesh2k10 @ 12 Nov 2012 10:00 AM
@admin: please update before the end of contest.

Thanks admins!

rajneesh2k10 @ 12 Nov 2012 03:00 PM
Thanks admins!

From my understanding, #pegs

wittawat @ 19 Nov 2012 04:00 PM
From my understanding, #pegs can never increase by moving. So, what does it mean when someone got score of 1 (full score) ? Does it mean in each test case, each cell has a peg ?

SUCCESSFUL SUBMISSIONS


Fetching successful submissions