Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem S. 104. (January 2016)

S. 104. In the ternary numeral system there are just three digits: 0, 1 and 2. People using this system love beautiful numbers. There are \(\displaystyle N\le 20\) basic beautiful numbers. To measure the beauty of a given number, they count how many basic beautiful numbers it contains. Suppose for example that \(\displaystyle N = 3\) and the three basic beautiful numbers are 010, 21 and 01021. Then the beauty factor of the number 01021 is 3, since this number contains 010, 21 and 01021 as substrings. We know that any basic beautiful number has at most 15 digits. If a number contains a given basic beautiful number several times, then each occurrence increases the beauty factor of that number by one. We would like to find the largest beauty factor among all numbers with \(\displaystyle K\le 1000\) digits.

Your program should read the values of \(\displaystyle N\) and \(\displaystyle K\) from the first line of the standard input, then the basic beautiful numbers \(\displaystyle a_i\) from the next \(\displaystyle N\) lines. The first and only line of the standard output should contain the largest beauty factor.

Példa bemenet (Sample input (here / means new line):Sample output:
3 7 / 010 / 21 / 01021 4

Scoring and bounds. You can get 1 point for a brief and proper documentation clearly describing your solution. Nine further points can be obtained provided that your program solves any valid input within 1 second of running time.

The source code of your program with a short documentation—also describing which developer environment to use for compiling the source—should be submitted in a compressed file s104.zip.

(10 pont)

Deadline expired on February 10, 2016.


Statistics:

8 students sent a solution.
10 points:Gáspár Attila, Mernyei Péter.
5 points:1 student.
3 points:2 students.
2 points:2 students.
1 point:1 student.

Problems in Information Technology of KöMaL, January 2016