Burned Calendar
Time limit1sMemory limit128 MB
Given a small surviving rectangle of a printed calendar, find every year from 1900 to 2100 whose calendar could contain that rectangle as a contiguous block.
- Level
Medium6 of 10
- Topics
- Implementation, Simulation, Brute force, Math
- Solved
- No attempts yet
Problem
A full one-year calendar is printed in a monospace font according to the following rules:
- Every blank space on the printed calendar is shown as the dot character
.(ASCII 46). - Each month occupies a rectangle 17 characters wide and 8 characters tall; the month's name is written in uppercase, starting at the 2nd character of the first line.
- The days of each month are printed in 4, 5, or 6 columns. Each column is 2 characters wide and 7 rows tall, with one blank space between adjacent columns. The first day of the week is Monday.
- The twelve months are arranged in three rows of four months each, separated by horizontal and vertical lines of blanks. The calendar has a 1-space margin on every side, so the whole calendar is 73 characters wide and 28 characters tall.
January 1, 1900 was a Monday. A year is a leap year when it is divisible by 4 and not by 100, or when it is divisible by 400. For example, part of the printed calendar from October to December 2002 may look like this:
.OCTOBER...........NOVEMBER..........DECEMBER.........
....7.14.21.28........4.11.18.25........2..9.16.23.30.
.1..8.15.22.29........5.12.19.26........3.10.17.24.31.
.2..9.16.23.30........6.13.20.27........4.11.18.25....
.3.10.17.24.31........7.14.21.28........5.12.19.26....
.4.11.18.25........1..8.15.22.29........6.13.20.27....
.5.12.19.26........2..9.16.23.30........7.14.21.28....
.6.13.20.27........3.10.17.24........1..8.15.22.29....
......................................................
One such printed calendar was burned, and only a small rectangular piece survived. Determine every year from 1900 to 2100 whose calendar this piece could have come from.
Input
The first line contains two integers and () separated by a space — the width and the number of lines of the piece. Each of the next lines contains exactly characters: the surviving piece of the calendar (blanks shown as dots).
Output
Print, in increasing order, every year (one per line) whose printed calendar could contain the given piece. If no year's calendar could contain it, print a single 0.