Description

Suppose that you have an infinite number of containers with different sizes, already filled with water. Given another empty container with size N liters, you need to find the best way to fill this N-liter empty container using the provided smaller containers. By ‘best’, we mean that the total number of used containers should be as small as possible. For example, assume that we have containers in 1, 5, and 10 liters. To get the 17 liters of water, we need 2 containers of 1 liter, 1 container of 5 liters, and 1 container of 10 liters. Another example: assume that we have containers in 1, 5, 10 and 50 liters. To get the 57 liters of water, we need 1 container of 50 liters, 1 container of 5 liters, and 2 containers of 1 liter. Note that, to avoid water wastage, if you choose to use a container, all the water in this container should be poured.

The following is an excerpt of incomplete code:

#include <stdio.h>
#define MAXNV 5
int DONE = 0;
int liters[MAXNV];
int numbers[MAXNV];
void show(int nv);
void filling(int amount, int cur, int nv);
int j=0;
int water;
int min=100;
int min_numbers[MAXNV]={0};
int main(void)
{
    int nv, i;

    scanf("%d", &nv);
    for (i=0; i<nv; i++) {
        scanf("%d", &liters[i]);
    }
    scanf("%d", &water);
    filling(water, 0, nv);

    for(i=0;i<nv;i++)
        numbers[i]=min_numbers[i];
    show(nv);
    return 0;
}

void show(int nv)
{
    int i;
    printf("(%d", numbers[0]);
    for (i=1; i<nv; i++) {
        printf(",%d", numbers[i]);
    }
    printf(")\n");
}

void filling(int amount, int cur, int nv)
{
    /* your code */
}

Input

The input contains three lines.

The first line contains an integer N, indicating that how many containers you have.

The second line gives you each container's size.

The last line is the total amount of water you have to pour.

 

Output

The result can be displayed by calling the function show().
Only the best way to fill the empty container should be displayed.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given any 2 strings consisted by '0'to '9' , 'a' to 'z' and 'A' to 'Z', we can find a common longest substring (CLS), which belongs to the both strings, continuty, left to right, and as long as possible. The length of CLS might be 1.

For instance, the CLS of "aabbccdd" and "bbaaccdd" is "ccdd".

You now are asked to implement a code, trying to find CLS for any pair of string.

Input

There are multiple lines in each testcase. Every two lines contain a pair of strings.

The input file is ended by 'EOF'.

There's no guarantee that the length of strings in the same pair are just the same.

It is guaranteed that (s is an arbitrary string n the corresponding testcase):

• At most 10 pairs of lines in each testcase.
• testcase #1 ~ #4 : 1 ≤ | s | ≤ 50
• testcase #5 ~ #6 : 50 ≤ | s | ≤ 1000

The last two testcases are the bonus. You will get extra credit as long as you pass them.

Output

For each string pair si, please output a line contains one integer representing the length of CLS in si.

If CLS does not exist, please output 0.

Please print '\n' after each answer.

Sample Input  Download

Sample Output  Download

Tags

Discuss