10309 - Turn the Lights Off

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

Well, a little bit of linear algebra :)

I liked this explanation, you might find it interesting, too:
http://www.geocities.com/jaapsch/puzzles/lomath.htm

This is another (easier?) version of the problem:
http://acmicpc-live-archive.uva.es/nuev ... php?p=2561
Top
serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur »

Well, one shouldn't be ashamed of one's own naivete :wink:
Thank you, Darko :D
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
Top
lucastan
New poster
Posts: 10
Joined: Sat Jul 02, 2011 6:46 am

Re: 10309 - Turn the Lights Off

Post by lucastan »

* Theory:
* The minimal solution consists of a sequence of moves.
* Think of these moves as a series of XOR operations .. (m1 XOR m2 XOR m3 ...) = BOARD_CLEAR
* The usual associativity and XOR-the-same-thing-cancels-out properties
* still apply.
* So no two move should be on the same cell otherwise their effects
* cancel each other out.
* Due to associativity, we can apply moves from the sequence
* in any order and still be able to get the board cleared.
*
* We exploit associativity here by finding the correct moves
* starting from the top most to bottom most row.
* We brute force on the first row by considering all 2^10=1024 ways of switching.
* And one of these ways must be part of the minimal solution.
* The second row of the minimal solution must then clear any remaining
* lighted cells in the first row.
And so on ... (the rest figure out yourself)

One trick to solving such problems is to think of how the final solution might be and how you could reach there...
Top
dhruba07
New poster
Posts: 20
Joined: Tue May 21, 2013 9:02 pm
Location: BUET

Re: 10309 - Turn the Lights Off

Post by dhruba07 »

Code: Select all

            testcase0         
#OO#OO#O#O
O#OOOO#OO#
O#OO#O##O#
#O###O##OO
#O##O####O
#O##OO#OO#
####O###O#
O#O##O#OOO
O#O#O#O##O
OO#O###OO#
            testcase1         
OOOOO#O#OO
#O#OO##OOO
O#O##OOOOO
#O##O###O#
######OO##
O#O#O##O##
#OOO#O#O##
##O#OOOOOO
####OOO#O#
O##O###O#O
            testcase2         
###OO#OOOO
O##O##O#OO
##OO###OO#
##OO#OO#OO
O####O##O#
##O##O##O#
O#OOOOOO#O
O####OOO#O
###OOOO##O
O#O##O##OO
            testcase3         
OOO###O###
#OOOO##OOO
##O#O#####
####OOOOO#
O#OOOO###O
#O#####OOO
###O##O#OO
#OO#OO#O#O
OOO#O#O##O
#O#OOO##O#
            testcase4         
####OO##OO
OO#O##O#O#
##OO#O#O##
O#O#OO#O##
O###OOOO#O
#O###OOO##
##O#O##O#O
##O##O##O#
O####OO#O#
O#O#OOO#O#
            testcase5         
OOOO##OO#O
####OO#O#O
#O###OO##O
O#OO##O#O#
##O#OO#O##
OO##OO#O##
O#O##OO##O
O#OOOO##OO
OOO#OO##OO
O###O##OOO
            testcase6         
#######O#O
O#O##O#OOO
#O#O###O#O
#O#O#OO###
##O#O#OOOO
O#O##OO#O#
##OOO#OOO#
##########
##O#O##OOO
O##O###O#O
            testcase7         
#O#OOOO###
OO#OO###OO
#O##O#O##O
#OO##O####
O#########
#O#O###OOO
OO#O#O#O#O
##O###OOO#
##OOO#####
O###OO###O
            testcase8         
#O###O#OO#
#######OOO
OOO##OOO##
OO#OO#O###
OOO#OOO#O#
#O##O##O#O
#O#OO##OOO
#O#OO#OOOO
######OO##
#O#OO##OO#
            testcase9         
O#####O#OO
O#O#O#OO##
OO##O#####
OOOO#O#O##
O##OO##OO#
#O#O#OOO##
#O#OO#O###
###OO###O#
O##OO#OO##
######O###
            testcase10         
OOO#OO##O#
#OOOOO#OO#
OOO#####OO
OOOOOO####
OO#O#O#OO#
#O##OOO##O
####O###OO
OO##OO##OO
#OOO#O#O#O
OOO##OOO#O
            testcase11         
##OOO#OOOO
O#OOOO##OO
#O##OO#O#O
#O##OOOOO#
OOO#OO####
O###O##OOO
O#OOOOO#OO
O#OOOO##OO
OO###O#OO#
#OO#OOOO#O
            testcase12         
O##OO###O#
#O##OO##O#
O##O#OO#OO
######OOO#
#O#O##OOO#
#OOOO#O#O#
#OOO##O#OO
O#OOO##O#O
#OOO####OO
O#OO##O#OO
            testcase13         
O##O##OOO#
O#O###O#OO
#####OO#OO
#O##OOOO#O
O#OOO##OO#
O#O#OOOO#O
##OOOO#O#O
#####OOOO#
##OOO#OO##
OOOO#O#O#O
            testcase14         
OO###O##OO
O#####O#O#
#OO###OO##
O###OO#O##
OOO##OO##O
OO#OOO#OOO
#O#O#OOOO#
#O###O####
OO##O##O##
OO#OOOOOOO
            testcase15         
O#O#O#OOO#
#O#O#OOOO#
#OOOOOOO#O
O##OOO#OOO
O#O##O##O#
#OO#OO###O
####OO##O#
#OOOO#O##O
#OO####OOO
##OOOOO###
            testcase16         
O##O##O###
#O#O#O#OO#
##O#O##OOO
#####OO###
O####O#O#O
#O####OOO#
O#OOO#O##O
O##O#OOOO#
O##OOO##O#
O##O####OO
            testcase17         
##OO##O##O
#O#OOO####
##OO###O#O
#O###OO###
OO#####O#O
#O#OOO###O
#O#O#OO##O
O#OO###O#O
##OO#O#OOO
##OOO#OOO#
            testcase18         
OO##OOOOOO
O###OO##O#
######O##O
#OOO##O##O
##OOOOOO##
#OOO#O####
#O##OOOO##
#######O#O
##O#####O#
O###OO##OO
            testcase19         
O###O####O
#O####O#OO
OO###O#O#O
O##O#O#O#O
O#OOO###O#
#O##OO##OO
#O##OO##OO
#####O#O##
#OOO#OOO#O
O#OOO#O#O#
            testcase20         
#OO####O#O
OOOOOOOOO#
O#OO#O###O
O#OOO###OO
#OO#OO#OOO
#O#O#OOO#O
OO#OO#OOOO
O#O#OO#OOO
O#O####OOO
OOO###O##O
            testcase21         
####O##O##
O#OOOOO#OO
OOOO####OO
##OOOO##O#
OOO#####O#
#O###O#O##
#O##O####O
O#O#O#O#OO
O####O#OOO
##OOOOOOO#
            testcase22         
OOOO##O#OO
O#O#O##O##
OO########
O#OOO##O#O
O##OO####O
OO###O#O#O
O#OO#O##OO
#O#O###OO#
###OOOO#O#
OOOOO#OOOO
            testcase23         
O#OO####OO
O#########
O#OO#O##OO
#######OO#
OOO####OOO
#O##OOO##O
#O###OOO#O
##O###OO#O
OOO#OO#OOO
O#OOO#OOO#
            testcase24         
O##O#O##OO
OO#O###O##
O#OO###O##
#O#OOOOO#O
O#O#O#O###
O##O#O##O#
OO##O#####
#OOO#O#O##
##OOOO####
O####O#O#O
            testcase25         
#OOOOOOOOO
####O####O
O#OO##OO##
O####O##O#
##O#OOOO##
OO#OOO#OO#
#OOO##OOOO
#O#O#OO#OO
#OOO#OOOOO
##O##OOOO#
            testcase26         
OO#OOOOO#O
OOOOO#OOOO
O#########
O#######O#
#O#O#O##O#
O###OOO###
OO#O#O##O#
O#O#####OO
OO##O##OO#
OO##OO#O##
            testcase27         
#####OOO##
OO####O#OO
OO#####O##
O#O#O###O#
OO##OO#O##
###OOO#OO#
#OO##O####
O######OO#
##OO##OO#O
#O###OOO##
            testcase28         
####OOOOOO
#####OO###
#O#OO##O#O
##OOOOOOOO
###O#O###O
##OO#O#OO#
#OO#OO##OO
####OO##O#
##O###O#OO
O#OOO#O#OO
            testcase29         
##O#OO#O##
#OO##OO##O
O##O######
#O#######O
OOO##O#O#O
O##OOO###O
#O#OOO####
OO#O##OO#O
O########O
#OOOOO##OO
            testcase30         
OOOOO####O
###OO#O#O#
###OO#O#OO
##OO###OO#
O#O###O#OO
OOO#OOOO##
#OO#O#OO#O
####O#O#O#
####O####O
OO#OO##O#O
            testcase31         
#O#OO##OOO
#O#O####O#
#O#OO#O#O#
##OO#OO#OO
#OOOOO#O#O
#OOO##O#OO
OO#OOOOO##
#O##O##O#O
OO#O#O###O
##OOOOOO#O
            testcase32         
#OOO##O###
##OO##O#O#
#########O
##OO#O###O
#O###OO##O
#O#O#O###O
###O##OOO#
O###OO#OO#
O######OO#
O#OO######
            testcase33         
O##OO#O#OO
OO#OOO##O#
O#OO#O#O#O
#O#OO#OO#O
##OO#O#OO#
#OOO##OO##
###O##O#O#
##OO#OOOOO
OO#OOOOOO#
##O#OOOO#O
            testcase34         
#########O
O#O#OO#OO#
###OO#O###
#OO###O###
####O#####
OOO#O#OOO#
O##OO#OOO#
O#O#OOO###
O##O#O##O#
#O#O####O#
            testcase35         
OOOO#OO###
O#O#O####O
#OOOO##OO#
#O#OOOOO#O
###O###O#O
OOO#O#O###
#O#OOO##OO
#OOOO#O###
OO#O####OO
O##OO#O#OO
            testcase36         
##O#OOOOOO
#OOOO##OO#
O#######O#
###O##O##O
#OO#O#O###
O#O###OOOO
##OO###OOO
OOO##OOO##
#OO###OO#O
O##O#####O
            testcase37         
##OOO#OO#O
#OOO######
#OO#O#OOO#
OOOOO##O##
O##O##OOO#
#O###O##O#
OO#OO###O#
OOOO######
O##OOOO##O
##OOOOO##O
            testcase38         
OOOOO###O#
O#OO#OO#OO
#########O
##OOOO###O
OO#OOO#O##
OOOO###O#O
OOO#OO#O##
OO##O####O
OOOOO#O###
O##OOOOOO#
            testcase39         
#O#O#O#O#O
OOOOOO#OOO
#O##OO#OO#
#####O#OOO
OOO#O#####
###OO#O##O
O###OO##O#
###OO###OO
###O##OOO#
OOOO#OOO##
            testcase40         
##OO#O#O##
OOOO#O##OO
OOO#OO##O#
OOOOO#OO##
##OO##O#OO
#OO#####OO
OOOOOO#OOO
#O##O#OOOO
O##OOO#O##
O##O##OO##
            testcase41         
O##OO#####
##OO#O##OO
OOOOO###O#
OOO#OOO###
O#OO###OO#
##O##OOO#O
####O#OO##
##O#OO##O#
O#OOO###OO
##OO#OO###
            testcase42         
OOO#OO####
OO##O#O#OO
OOOOO#OOO#
#OOO#OOO#O
O#O#OOO#O#
#O##O#OOOO
O##O#OOO##
O#OOO#OOOO
##OO#OO##O
O########O
            testcase43         
O##O####O#
O##OOO#O#O
O###OOOO##
O#OO######
O######O##
O#O#O####O
O#####O#O#
OOO#OOO#O#
O#O#O#OOO#
OOOO#O#O##
            testcase44         
###O##O##O
####OOOOOO
#O#OOOO#O#
OOOOO##O#O
OOOO#OOO#O
OOO#O#OOOO
##OO#O#OOO
##O##O##OO
#O##O#OOO#
O#O######O
            testcase45         
#O#O#OO##O
#OOO#OOOOO
####O#O#O#
##OO##O#O#
#O#OO#OO##
OOOO#O####
O#OO#OOO#O
##O###O###
OO#OOOO##O
O##OOOOOOO
            testcase46         
OO###OO###
OO##O###OO
#O#O##O###
#O#O#OO##O
O#OOOO###O
#OOOO#O###
OO###O###O
#O##O#O#O#
##OO#O###O
###OOO###O
            testcase47         
##OOOO#OO#
O#OO#OO##O
#O#O#OOO#O
O#######O#
OO##OO#O#O
O##O#OOOO#
OOO##OO##O
O#O#OOO###
O#O##O##O#
#O######OO
            testcase48         
OOOOOO#OOO
#O#O##OOOO
##OO###OO#
#OO##O#OO#
O####OO#O#
##O#O#O#O#
####OO##O#
#OOOOO#O##
###OO###O#
O#O#OOO#OO
            testcase49         
O######O#O
O####OOO#O
O#OOOO#OO#
#OOO###OOO
#O#O#OO###
##O###OO#O
#OO#OO##O#
O###OOOO##
OOOOO##OO#
O##O#OOO##
            testcase50         
##OO#OO###
O##O######
O###OO#OO#
##OO##O#O#
OOO#OO#O#O
##OOOOOOOO
#O##OO#O##
O#OO#OOOO#
OOOOO#O###
#O#####O##
            testcase51         
O#OOO#OO##
OO#OO###OO
OOO##OOOO#
#O#OO#####
O###O#O#O#
OO#O#OO#O#
#O#OOO###O
O#O#OO#O##
##OOO#OO##
#O##O###OO
            testcase52         
####O#####
##O##OOO##
#O#O###OO#
OOO###O#OO
O##OOO##OO
O#OO#O#OOO
O#OOO###OO
#O#O#OOO##
O#OO#OO#O#
#OO##OOO##
            testcase53         
OO#OOOO#O#
OOOO#OO###
OO#O#O###O
O##O##O#O#
OO###O##OO
OOOO##OOO#
O####O##O#
OOOO##OOOO
O##O#O##OO
#O#OOOO##O
            testcase54         
OO#OOO#O#O
###OOOO##O
#OOOOOO##O
#OOOOO#OOO
O########O
#O#O##O#OO
#OO#OO##OO
#O####OOO#
#OOOO##OOO
OOOO#O##O#
            testcase55         
##OOO###OO
O#OO#O#OOO
O#OO###OO#
O#OOO###O#
#OO####OOO
OO#O#OOO#O
##O##OOO#O
O##OOOOOOO
O#O######O
OO#OOOOO##
            testcase56         
##OO##O##O
###OO###O#
OO##O#OOO#
O#OO#####O
#O##O#OO#O
###OO#OOOO
#O##OO#O#O
OOOO#####O
OO##OOOOOO
OOO####O#O
            testcase57         
O####OO#O#
#O######O#
OO#OO####O
OOO#####O#
OO###OOOOO
#O##O#OOO#
OO#O#OO##O
O#OOO#O##O
##OOO##O#O
##O#OO#O##
            testcase58         
O#O###OOOO
O###O#O###
#OOO#OO#O#
O#OOOO#OO#
OO####O#O#
OOO#O##OOO
#O#####O##
OOO###OO#O
##O#OO#OO#
O#O###OO##
            testcase59         
O##OO##O#O
#OO#OOO#OO
OOOO######
##OO#####O
#O##O#OOOO
OO#O#O#OO#
##OO#O###O
#O#OO##O##
O#O#O#O##O
O####O#O#O
            testcase60         
O#O##OO#O#
O##OO##OO#
O#O#O#O###
##O##OO##O
###OOO##O#
O#OOOO#O#O
OOOOO#OOO#
O##O##OOOO
O##O#O##OO
#O####O###
            testcase61         
##OO#O##O#
OOO##O#O#O
OOO#O#OO##
#O#OOOO#OO
OO###O##OO
#OO#OO#O#O
OOO#OO#O##
###OO#O#OO
##OOOOO###
##O#OO###O
            testcase62         
#OOOOO#OO#
O#OO###OOO
#O####O#O#
####O#O##O
######OO##
OO##OOOO##
##OOOO#OOO
O##OOO###O
O#O##O##O#
O#O##O#O##
            testcase63         
O#O###OOO#
OOO####O#O
####O#OO##
#OOO#O##O#
O###OOO#O#
#O####O###
O######OO#
##OOOOOOOO
O#O#OOOO#O
OO###OOOO#
            testcase64         
##OO#OO#OO
#OOO#OOO##
O###OO##O#
OOOOO#OOOO
#####O##OO
#O#O#O#O##
######O#OO
##OOO#####
OOO#O###OO
###O#OO##O
            testcase65         
O##O###OOO
OOOOO###O#
O###OOOO##
O#O##OO#OO
#O#OO##OO#
#O#OO#OO#O
###OO#OOOO
O#####OO##
O#####OO##
O#O##OO#OO
            testcase66         
#OOOO#OOO#
#OO##OO#OO
OO#O#OOO#O
OOOO#OO##O
OOO####OO#
OO##OO#OOO
O#OO####OO
##O#OOO#OO
OOO##O#OOO
OO#O#OOOOO
            testcase67         
O##O##O#OO
OOOO######
##OOO#OO#O
O#OO###OOO
OOO##OOO#O
#O##O#OO##
#OO#OOO#OO
#O#O#OOOO#
O########O
#OO##O##O#
            testcase68         
O#O#######
O#O###OO#O
OOO##O####
O##OOOO#O#
OO##OOOOO#
OO######OO
OOO##OO#OO
OOO##O#O##
##O#O#O#OO
O#OOO#OOOO
            testcase69         
O###OO#OOO
#OO##O##O#
#OO#O##O##
#OOO##OO##
#O##OO####
OO####OOO#
O##O#O###O
OO#####OOO
OOO##O##O#
#OOO###OOO
            testcase70         
##OOO##O##
O######OO#
##O#O#O##O
#O##OOO#O#
OO#O#O#OO#
O##OO##OOO
O##OO#OO#O
##OO#OOOOO
OO##O#O##O
OO##O#OO##
            testcase71         
OO#O#OO###
O###OO#O#O
O#O#OOO#O#
OO###OO#O#
OOOO#OOOO#
#O####O#OO
O###OOOO#O
#OO#O##OO#
###OOOOO#O
###O#OO#O#
            testcase72         
#O####O##O
O##O#OO#OO
O####O###O
#OOO##OOO#
O#OO#OO##O
##O####O##
OO#OO#OO#O
O##O#OO#OO
O##OOO#O#O
##OOO##O#O
            testcase73         
O#OOO#OO#O
O#OO#OOOO#
####O#O##O
O##O###OOO
OO#OOO####
OO####OOO#
OO##OO#OO#
O##O#OOO##
O#####O##O
###OO#O###
            testcase74         
OOOOO#OOO#
OOO###O###
#OOOO#OOO#
########O#
OO#O#OOO##
#O#O######
O#OOO###O#
OO#######O
OO##OOO###
##O#####O#
            testcase75         
O#OOO##OOO
OOO#####OO
O#O###OOOO
#####OOOOO
OOOOO###OO
O##OOO#OOO
OO#O#OOOOO
OOO#OOOOO#
OOO#OOO#OO
#OOOOOOOOO
            testcase76         
OOO####O##
####O##O##
#O###O##O#
O#OOO####O
#O#O#OOOO#
#####O#OO#
OOOOOO#OO#
O##O##O##O
O#OOO#O##O
O#O#######
            testcase77         
O#O##OO##O
OO#OO##OOO
#OO###O#O#
OO##OO#OOO
OOO#OOO##O
#O###O#O##
#OOO#O#OO#
O###O###OO
##OO#O#OOO
##O#O####O
            testcase78         
OO####OOOO
#O##OO##O#
OO#O##O#O#
#O#O#O###O
#OOO#O##O#
OO##O#OOOO
O#O###OOO#
O##OOO####
OO#O###OO#
OOO###O###
            testcase79         
OOO#OOO###
OO##O#####
O##OOO##OO
OOOOO##OOO
##O#OOO###
O#O###OOOO
#OO#OOO#O#
OOOO#O##OO
OOOOO##OO#
O##OOO####
            testcase80         
O##OOOO##O
####O#####
##OO#OOO#O
O#####OOO#
OO####OOO#
##O#OOOOO#
OO#OOO#OOO
##OOO###OO
O#######O#
OOO#OOOOOO
            testcase81         
O##OOO####
####OOO##O
##########
##O##O##OO
O###OO###O
#OOO##OOO#
###OOOO##O
#OO##O###O
#####OO##O
#OOOOOO#OO
            testcase82         
##O#O#O#O#
OOO##O#O#O
OO#OO###O#
#OO###O#O#
#O###O##O#
###O#OOO#O
#OOO#O####
OOO#O#O#OO
OO#OO#OO##
#####O#O##
            testcase83         
#O########
O####OO#OO
O####O#OO#
#####OOOO#
#O###O#OO#
OO##OO##O#
OOO###O##O
##OOO#O##O
O###O###OO
O#O#O#OOOO
            testcase84         
O##O##OOO#
OO##O#O###
##O#OOO###
##OOOO#OO#
#O#OO#OO##
#OO#O#OOO#
##OO#OOOOO
#OOOOOOO##
#O#OO##OO#
##O###O##O
            testcase85         
#OOOO#OO##
##O##OOOOO
##O#O#OO##
#O##O#O#OO
O##OOOO#OO
####OO#OOO
##OO####O#
#O#O##O#OO
OO#####O#O
OO##OOOOOO
            testcase86         
##OOO#OO#O
##OOOOOOO#
O#O#OOOOOO
OO#OO#OOO#
##O##O##OO
#O##O##O#O
O#O##O####
OOOO######
#OOO#O#OOO
OO#O#O#OOO
            testcase87         
#OO####OOO
##O####O##
OO##O#O##O
##O#O#####
####OOOO#O
##O##OO#O#
##O####OOO
#O#O#O#OOO
O##OOOOO#O
OOOOO####O
            testcase88         
#OO####O##
O#O###OO##
O#OOOO###O
#O###O#OOO
#OOO#####O
#OO#OO#O#O
O#O#OO##O#
OO#OO###O#
####O#####
#OOO#OO#OO
            testcase89         
OOOOOO####
O###O##O#O
#OO#OO#O##
######OO##
O#O###OO##
OOO##O#O#O
OO#######O
####OOO#O#
O##OOO###O
##OOO#####
            testcase90         
#OO####OOO
#O#####OOO
O##O#O###O
O#OOOO##O#
##OOO##O##
O#OO#OOO##
##O##O##O#
O##OO####O
#O##OO#O#O
#O#O##O#OO
            testcase91         
OOO##O#O#O
#OOOOO##OO
OOO#O#OOOO
####OO##OO
O##OO###O#
#O##O#OOO#
##OOOOO#OO
#OOOOO###O
#OOO#OO##O
OO#OO##OO#
            testcase92         
O##OO#O###
#O#OOOOOO#
OO####OO#O
#OOOOO###O
O#OO##O##O
#O#O#OOOO#
O##O#OOO#O
#####OOO#O
OOO#######
OOOOO#O#O#
            testcase93         
##OOOOO#O#
#OO#O#O#OO
#OO#OO#O##
#OOOOOOO#O
OOOO#O#OO#
O##OOOO#OO
OOOOO##O#O
O##O#O#OO#
#OO#OO##O#
#O####OO#O
            testcase94         
O###O#O##O
O##OO#O#OO
O##O#O##O#
#OO#OOOO##
O#O##O#O##
OO##OO####
O#O#OO#OO#
#OOOOOO#OO
OOO#OO####
#OO##O#OO#
            testcase95         
###O##OOOO
O#OOOOOOO#
####OO####
OOO#OO#OO#
OOO#O##O##
#OO##O#O#O
#######OO#
#O#O#####O
O#O#O#####
OOO###O##O
            testcase96         
O##O#O#O##
OOOO#O#O#O
##OOO###O#
##OO###O#O
##O####OO#
O#OO####OO
O##OOO##OO
#O#O#O##O#
OO#OOO####
###O##OOO#
            testcase97         
O####O####
O###O#O###
#O#O#O####
O#O##OOO##
O#######OO
O#O###OO##
##OO##O#O#
OOO###OOO#
O#O#OOOOO#
#O#OOO#O##
            testcase98         
##########
OOO#######
###O##OO##
OOO#O#O##O
O#O#O#O#O#
##OO##O#O#
OOO##OOO##
O##OO##O##
OO#OOOOOOO
OOOO##OO##
            testcase99         
##OO##OO##
O###O##OO#
OOOOO##O##
##O##OO#OO
OO########
O##O##O###
OOOO#OOO##
OO#####OOO
#OOO####OO
OOO##O##OO
            testcase100         
OOOO#O#OO#
#O##OOOO##
OO###O#OO#
OO##OO####
OO#O#OO#OO
OOOO##OO#O
###OO####O
##OO##OOOO
O##O#O###O
OO###OOO##
end
AC output:

Code: Select all

testcase0 56
testcase1 47
testcase2 49
testcase3 55
testcase4 52
testcase5 43
testcase6 50
testcase7 48
testcase8 49
testcase9 50
testcase10 45
testcase11 53
testcase12 56
testcase13 50
testcase14 49
testcase15 51
testcase16 44
testcase17 48
testcase18 48
testcase19 50
testcase20 55
testcase21 52
testcase22 49
testcase23 43
testcase24 46
testcase25 49
testcase26 53
testcase27 54
testcase28 57
testcase29 57
testcase30 49
testcase31 43
testcase32 45
testcase33 59
testcase34 44
testcase35 47
testcase36 49
testcase37 50
testcase38 50
testcase39 43
testcase40 54
testcase41 48
testcase42 53
testcase43 45
testcase44 46
testcase45 48
testcase46 53
testcase47 57
testcase48 44
testcase49 45
testcase50 50
testcase51 54
testcase52 55
testcase53 46
testcase54 50
testcase55 49
testcase56 45
testcase57 51
testcase58 51
testcase59 57
testcase60 44
testcase61 49
testcase62 53
testcase63 46
testcase64 49
testcase65 49
testcase66 47
testcase67 45
testcase68 53
testcase69 45
testcase70 40
testcase71 41
testcase72 48
testcase73 46
testcase74 50
testcase75 57
testcase76 61
testcase77 50
testcase78 51
testcase79 44
testcase80 45
testcase81 61
testcase82 47
testcase83 46
testcase84 55
testcase85 43
testcase86 50
testcase87 56
testcase88 59
testcase89 53
testcase90 50
testcase91 47
testcase92 52
testcase93 46
testcase94 50
testcase95 50
testcase96 58
testcase97 40
testcase98 45
testcase99 54
testcase100 46
Thanks to Ibv :) for giving input specifications which helped me to get AC :)
Last edited by dhruba07 on Fri Jun 13, 2014 5:21 am, edited 2 times in total.
Accept who you are :)
Top
lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10309 - Turn the Lights Off

Post by lbv »

dhruba07 wrote:Getting wrong answer in 10309.
I think this problem illustrates an issue that is controversial and yet very common in UVa's archives. The input is not necessarily as neat as you see in the samples, so be very careful not to make any unnecessary assumptions.

For example, the only thing that input specification says about the names is: Each test case is preceded by a single word that gives a name for the test case. It doesn't say that the name will be equal to the line immediately preceding the grid of lights. What if there are blank lines between cases? What if there are spaces at the beginning or the end of the line that contains the name?

After a small tweak to your code to avoid that type of assumptions, I submitted the program and got AC.
Top
Post Reply

Return to “Volume 103 (10300-10399)”