2120

Computer Science Level 3

How many ternary strings of length 10 DON’T \textbf{DON'T} contain the pattern 2120?

Details \textbf{Details}

Ternary strings of length n n : x 1 x 2 ⋯ x n ‾ \overline{x_1x_2\cdots x_n} with x i ∈ { 0 , 1 , 2 } x_i \in \{0,1,2\}

Example: \textbf{Example:}

0102212 doesn't contain the pattern 2120

21212021 contains the pattern 2120


The answer is 54000.

Ivan Molina N by Ivan Molina N , 28, Colombia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Aryan Gaikwad
Mar 21, 2015

Java solution

Sorry for this ugly solution. I will try to come up with a shorter solution using recursive methods later (I'm in a hurry now). But anyways, I think this is more efficient - 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
 
final int nmax = 59049, max = 2;
String n[] = new String[nmax];
int x = 0;
    for(int a = 0; a <= max; a++)
        for(int b = 0; b <= max; b++)
            for(int c = 0; c <= max; c++)
                for(int d = 0; d <= max; d++)
                    for(int e = 0; e <= max; e++)
                        for(int f = 0; f <= max; f++)
                            for(int g = 0; g <= max; g++)
                                for(int h = 0; h <= max; h++)
                                    for(int i = 0; i <= max; i++)
                                        for(int j = 0; j <= max; j++)
                                            n[x++] = Integer.toString(a) + Integer.toString(b) + Integer.toString(c) + Integer.toString(d) + Integer.toString(e) + Integer.toString(f) + Integer.toString(g) + Integer.toString(h) + Integer.toString(i) + Integer.toString(j);

int v = 0;
for(String t: n)
    if(!t.contains("2120"))
        v++;
System.out.println(v);

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Brock Brown
Mar 18, 2015

Python 2.7: 

1
2
3
4
5
6
7
 
from itertools import product
count = 0
for combo in product(xrange(3),repeat=10):
    test = ''.join([str(i) for i in combo])
    if '2120' not in test:
        count += 1
print "Answer:", count

1 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...