FoxAndKgram
TCO12 Round 1B · 2012-03-27 · by cgy4ever
TCO12 Round 1B · 2012-03-27 · by cgy4ever · Simple Search, Iteration
Problem Statement
Problem Statement
Fox Ciel has some pencils.
Before she'll start writing her homework, she wants to place them into a mystic pattern for fun.
Different pencils she has may have different lengths.
You are given a int[] len. For each i, the length of i-th pencil is len[i]
The pattern she wants to create is called a k-gram. A k-gram is a pattern consisting of k rows, each of length k. There are only two types of valid rows:
Compute and return the largest positive integer k such that Fox Ciel can use some of her pencils to form a k-gram. If she is unable to form any k-grams, return 0 instead.
The pattern she wants to create is called a k-gram. A k-gram is a pattern consisting of k rows, each of length k. There are only two types of valid rows:
- Yang: A row containing a single pencil of length k.
- Yin: A row containing two pencils such that the sum of their lengths is (k-1). The pencils will be separated by a space of length 1.
Compute and return the largest positive integer k such that Fox Ciel can use some of her pencils to form a k-gram. If she is unable to form any k-grams, return 0 instead.
Constraints
- len will contain between 1 and 50 elements, inclusive.
- Each element in len will be between 1 and 50, inclusive.
Examples
0)
{1,1,1,1,3}
Returns: 3
All pencils can be used to form a 3-gram. One valid 3-gram follows: - - --- - -
1)
{2,2,1,3,5,5,5}
Returns: 5
One of the valid 5-grams: ----- -- -- - --- ----- -----
2)
{1}
Returns: 1
3)
{2,2,2,2,2,2,2,2,2,2}
Returns: 5
4)
{1,2,3,1,2,4,2,3,1}
Returns: 4
Note that it is not necessary to use all of the pencils.
Submissions are judged against all 249 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FoxAndKgram with a public method int maxK(vector<int> len) · 249 test cases · 2 s / 256 MB per case