Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2521
LED Display

Time Limit: 2 Seconds      Memory Limit: 65536 KB

One day in the laboratory, Fred found some LED displays. This seven-segment LED can display digit 0 to 9 properly. But Fred soon find the LED have a serious problem, at the beginning, the seven bars were all on. But when one bar once was trun off, it can't be turn on again! So ecah LED only can display digit in certain oder. For example, one LED can display 9,3,7 successively, but can't display 2,4.

Now, Fred have a task to display a sequence of digit that is between 0 to 9. Because of the shortcoming of these LEDs, he need a number of them. But he also want to minimize the number, can you help him?

NOTE:If two digits in a sequece are the same,Fred want for the clearness, so he thought the latter digit can't be displayed on the same LED.


The input consists of several test cases. The first line of each test case contains a positive integer N (<=1000), then followed by a list of N digits. Each digit follows with a blank space.


For each test case, you must print a minimum number of LED that Fred need in one line.

Sample Input:

9 0 7 3

8 8 8 9 6 5 4 1
Sample Output:
2		(Hint:one mothod is display {9,3} on the first LED; {0,7} on the second)
3		(Hint:one possible solution is {8},{8,9,4,1},{8,6,5})

Author: JIANG, Dongming
Source: ZOJ Monthly, September 2005
Submit    Status