CCC '09 S2 - Lights Going On and Off - DMOJ: Modern Online Judge

CCC '09 S2 - Lights Going On and Off

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem type

Canadian Computing Competition: 2009 Stage 1, Senior #2

For your birthday, you have been given a grid of $R$ $R$ $(1 < R < 30)$ $(1 < R < 30)$ rows of lights, with each row containing $L$ $L$ $(1 \le L < 8)$ $(1 \leq L < 8)$ lights. Lights can be in one of two states: on or off. For this question, the topmost row is row $R$ $R$ , and the bottom-most row is row $1$ $1$ . Also, beside all rows except the topmost row (row $R$ $R$ ), there is a button which can be pushed.

Pushing the button beside row $k$ $k$ $(1 \le k < R)$ $(1 \leq k < R)$ will perform an "exclusive-or" operation on each light of row $k$ $k$ , which is described below. Consider column $i$ $i$ in row $k$ $k$ , where $1 \le i \le L$ $1 \leq i \leq L$ . If the lights in column $i$ $i$ of row $k$ $k$ and column $i$ $i$ of row $k + 1$ $k + 1$ are both the same (i.e., both on, or both off), then pushing the button beside row $k$ $k$ will cause the light in column $i$ $i$ of row $k$ $k$ to be off. If the lights in column $i$ $i$ of row $k$ $k$ and column $i$ $i$ of row $k + 1$ $k + 1$ are different (i.e., one is on, and the other is off), then pushing the button beside row $k$ $k$ will cause the light in column $i$ $i$ of row $k$ $k$ to be on. An example is shown below, for $L = 4$ $L = 4$ :

Column Numbers	1	2	3	4
Row $k+1$ $k + 1$	on	on	off	off
Row $k$ $k$ before button pushed	on	off	on	off
Row $k$ $k$ after button pushed	off	on	on	off

You are told which lights are initially on and which are initially off. You must calculate how many different light patterns are possible for the bottom row by any sequence of button pushes. Each button may only be pressed once, but in any order.

Input Specification

The first line of input will contain the integer $R$ $R$ , the number of rows. The second line of input will contain the integer $L$ $L$ , the number of lights per row. The next $R$ $R$ lines of input will contain $L$ $L$ integers, where the integer will either be $0$ $0$ (to indicate "off") or $1$ $1$ (to indicate "on"). Pairs of consecutive integers will be separated by one space character. These $R$ $R$ lines will be given in topdown order: that is, the third line of input will be the description of row $R$ $R$ , the fourth line will be $R - 1$ $R - 1$ , and so on, until the last line describes the bottom row.

Output Specification

Output the number of possible light patterns of the bottom row.

Sample Input

Copy

Sample Output

Copy

Comments

0

JinchengLuo2007 commented on Feb. 19, 2024, 2:46 p.m.

what if you press the first button?

8

BT commented on Nov. 23, 2022, 9:26 p.m. ← edited →

And you have to calculate/write code for your birthday???

9

bariumlanthanum commented on Feb. 1, 2022, 9:14 p.m. ← edit 3 →

keyboards have 6 rows and 21 columns, so this gift could have totally been a sideways RGB gaming keyboard, which is a pretty good present. Why are people saying its bad?

11

tin_martin commented on Jan. 11, 2022, 5:59 p.m.

idk what people are saying, this present rocks

22

satvick16 commented on Feb. 16, 2021, 3:01 p.m.

i guess these are the kinds of bday presents ppl get in dmojistan

71

puppy commented on Nov. 24, 2019, 3:48 p.m.

worst birthday present ever

93

ThatGuyOnTheStreet commented on Dec. 16, 2018, 10:17 p.m.

what kind of parent would buy their kids this

44

discoverMe commented on March 23, 2018, 4:08 p.m. ← edited →

do you have to press every button?

update:no you don't