FloorIndicator

SRM 421 · 2008-10-07 · by Alexus

SRM 421 · 2008-10-07 · by Alexus · Simple Math, Simple Search, Iteration, String Parsing

Show categories

Class Name: FloorIndicator

Return Type: double

Method Name: averageFloor

Arg Types: (int, vector<string>)

Problem Statement

Imagine a skyscraper with 10^N floors, numbered 0 to 10^N-1. The floor indicator in the elevator shows the floor number using exactly N digits, padding it with leading zeroes if necessary. Each digit is shown as a 5x3 field of small lamps, some of which are lit and some of which are unlit. Here is a representation of all the digits from 0 to 9 ('#' represents lit lamps and '.' represents unlit lamps) :

###...#.###.###.#.#.###.###.###.###.### #.#...#...#...#.#.#.#...#.....#.#.#.#.# #.#...#.###.###.###.###.###...#.###.### #.#...#.#.....#...#...#.#.#...#.#.#...# ###...#.###.###...#.###.###...#.###.###

Here, as in the actual floor indicator, consecutive digits are separated by a single column of unlit lamps. Some of the lamps in the floor indicator are malfunctioning and always remain unlit. Imagine that you are stuck in this elevator and you want to know the current floor number. You decide to calculate it as the average value of all floor numbers that could possibly be represented by the current state of the indicator, assuming that any number of the unlit lamps might be malfunctioning. You are given the state of the indicator as a String[] where each element represents a row of lamps, and rows are given from top to bottom. Return the average that you calculate, or -1 if no valid floor number could possibly be represented by the indicator.

Notes

The returned value must be accurate to within a relative or absolute value of 1E-9.

Constraints

N will be between 1 and 9, inclusive.
indicator will contain exactly 5 elements.
Each element of indicator will contain exactly 4*N - 1 characters.
Each element of indicator will be either '#' or '.' (dot).
All characters corresponding to lamps in separating columns will be '.' (dots).

Examples

1
{"###", "#.#", "#.#", "#.#", "###"}
Returns: 4.0

2
{"###.###", "#.#.#.#", "#.#.#.#", "#.#.#.#", "###.###"}
Returns: 44.0

1
{
"...", "...", "...", "...", "..."
}
Returns: 4.5

1
{
"###", "..#", "..#", "..#", "..#"
}
Returns: 5.4

1
{"###", "#.#", "#.#", "..#", "###"}
Returns: 5.666666666666667

1
{"###",
 "#.#",
 "###",
 "#.#",
 "###"}
Returns: 8.0

This digit is clearly "8", so it is the only possible floor.

2
{"###.###",
 "#.#.#.#",
 "#.#.###",
 "#.#...#",
 "###.###"}
Returns: 48.5

Although the indicator shows "09", both digits can also be partially lit "8", so the possible floor numbers are: 08,09,88,89. This results in average floor number (8+9+88+89)/4 = 48.5.

2
{".......",
 ".......",
 ".......",
 ".......",
 "......."}
Returns: 49.5

This indicator is completely broken, so any floor number between 0 and 99 is possible.

1
{"...",
 ".#.",
 "...",
 "...",
 "..."}
Returns: -1.0

No digit fits here.

Submissions are judged against all 65 archived test cases, of which 9 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FloorIndicator with a public method double averageFloor(int N, vector<string> indicator) · 65 test cases · 2 s / 256 MB per case