시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
240 초 (추가 시간 없음) | 1024 MB | 0 | 0 | 0 | 0.000% |
Siv's birthday is next week and Cel is preparing a birthday present for her. Because Siv loves puzzles, Cel is creating a word search puzzle as a gift.
In a word search puzzle, the solver is given a rectangular grid with R rows and C columns, and the solver must find all valid words hidden inside the grid. Each hidden word may appear horizontally or vertically (but NOT diagonally) in the grid, forward or in reverse. Hidden words may overlap.
Cel has a dictionary with W different words; these are the only words that can be hidden within the puzzle grid. (Of course, not every contiguous horizontal or vertical part of the grid will necessarily contain one of the hidden words.) These words are not necessarily real English words. Each word might appear in the grid one or more times, or not at all.
Cel has already created the word search puzzle. However, there is a problem: the puzzle is too big to print on a sheet of paper. As Siv's birthday is coming soon, there is not enough time to create a new word search puzzle from scratch. So Cel is wondering whether she can reduce the size of the grid, simply by selecting a non-empty, grid-aligned subgrid from the original grid.
Randomly selecting a subgrid might result in a boring puzzle without a lot of hidden words. So Cel wants to select a subgrid with the largest fun value, where the fun value of a subgrid is defined as:
fun value = (total length of words matched) / ((width of subgrid) + (height of subgrid))
Notes:
Can you please help Cel find the largest fun value that a subgrid could have, and the number of different subgrids that have this fun value? Two subgrids are considered different if and only if there is some cell in the grid—that is, some (row, column) position—that is in one subgrid, but not the other.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case is structured as follows:
For each test case, output one line containing Case #x: y/z n
, where:
x
is the test case number (starting from 1).y/z
is an irreducible fraction equal to the largest possible fun value (as described above) of a subgrid.y
is a non-negative integer.z
is a positive integer.n
is the number of subgrids with fun value equal to y/z
.y/z
is called an irreducible fraction if the greatest common divisor of y and z is 1.
2 1 2 1 AA A 1 2 1 AA B
Case #1: 8/3 1 Case #2: 0/1 3
Let (i, j) denotes the cell at i-th row and j-th column.
In Sample Case #1, the subgrid with highest fun value is the entire grid. The valid word A
appears 8 times in the grid:
In Sample Case #2, there are 3 subgrids with fun value equals 0:
2 1 3 2 ABC ABC CBA 4 4 1 AAAB AAAB AAAB BBBB AA
Case #1: 3/2 1 Case #2: 8/1 1
In Sample Case #1, the subgrid with highest fun value is the entire grid. The valid word ABC
appears horizontally from cell (1, 1), and the valid word CBA
appears horizontally in reverse from cell (1, 1). So the fun value of the entire grid equals 6/(1 + 3) = 3/2
.
In Sample Case #2, the subgrid with highest fun value has top-left corner at cell (1, 1) and bottom-right corner at cell (3, 3). The valid word AA
appears 24 times in the subgrid:
Note: We do not recommend using interpreted/slower languages for this problem.
Contest > Google > Kick Start > Google Kick Start 2018 > Round D C번