2013
11-09

# Number of Locks

In certain factory a kind of spring locks is manufactured. There are n slots (1 < n < 17, n is a natural number.) for each lock. The height of each slot may be any one of the 4 values in｛1,2,3,4｝( neglect unit ). Among the slots of a lock there are at least one pair of neighboring slots with their difference of height equal to 3 and also there are at least 3 different height values of the slots for a lock. If a batch of locks is manufactured by taking all over the 4 values for slot height and meet the two limitations above, find the number of the locks produced.

There is one given data n (number of slots) on every line. At the end of all the input data is -1, which means the end of input.

According to the input data, count the number of locks. Each output occupies one line. Its fore part is a repetition of the input data and then followed by a colon and a space. The last part of it is the number of the locks counted.

2
3
-1


2: 0
3: 8


/* @author:zeropinzuo */
import java.io.*;
import java.util.*;

public class Main{
static Scanner cin;
static long[] f,g;

public static void main(String args[]){
cin = new Scanner(System.in);
f = new long[17];
g = new long[17];

g[1]=4;
g[2]=14;
for(int i=3;i< 17;i++)
g[i]=3*g[i-1]+2*g[i-2];

for(int i=2;i< 17;i++)
f[i] = (1<< (2*i))-(1<< i)-g[i]+2;

while(run()==true)
;
}

static boolean run(){
int n = cin.nextInt();
if(n==-1)
return false;
if(n==16){
System.out.println(16+": 3553389280");
return true;
}

System.out.println(n+": "+f[n]);
return true;

}
}

1. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧

2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)