City dawn lights, there is always a halo in the fall, imitators one after another, no one asked for the role, who do you choose to worship, who hate?

Title Description

Give an alphabetic string of lower-case English letters with a length not exceeding 200,200 (convention; the string is input in 2020 letters per line, guaranteeing that each line must be 2200 letters). It is required to divide the letter string into k k parts (1 < k Le 401 < K < 40), and the total number of words in each part is the largest (the words in each part can overlap partially). When a word is chosen, its first letter can no longer be used. For example, the string thisthis can contain thisthis and isis, and after selecting thisthis, it cannot contain thth.

Words are given in a dictionary of no more than 66 words.

The maximum number of outputs is required.

Input format

The first row of each group has 22 positive integers (p,kp,k)

pp denotes the number of rows in a string, and kk denotes the number of rows divided into kk parts.

The next pp line has 2020 characters per line.

Next, there are 11 positive integers ss, representing the number of words in the dictionary. (1le sle 61 < s < 6)

The next ss line has 11 words in each line.

Output format

11 integers, corresponding to the corresponding results of each group of test data.

Input and Output Samples

Input #1 replication

1 3
thisisabookyouareaoh
4
is
a
ok
sab

Output #1 replication

7

Note/hint

this/isabookyoua/reaoh

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n,m,k;
int l[20],d[510],s[310][310],dp[310][310];
char a[520],c[20][510];
int cs(int k)
{
    int jg=1e5;
    for(int i=1; i<=m; i++)
        if(l[i]+k-1<=n)
        {
            bool fg=1;
            for(int j=1; j<=l[i]; j++)
                if(c[i][j]!=a[k+j-1])
                    fg=false;
            if(fg)
                jg=min(jg,l[i]);
        }
    return jg;
}
int main()
{
    scanf("%d%d",&n,&k);
    n=n*20;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    scanf("%d",&m);
    for(int i=1; i<=m; i++)
    {
        scanf("%s",c[i]+1);
        l[i]=strlen(c[i]+1);
    }
    for(int i=1; i<=n; i++)
        d[i]=cs(i);
    for(int i=1; i<=n; i++)
        for(int j=i; j<=n; j++)
            for(int k=i; k<=j; k++)
                if(k+d[k]-1<=j)
                    s[i][j]++;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=k; j++)
            for(int p=j-1; p<=i-1; p++)
                dp[i][j]=max(dp[i][j],dp[p][j-1]+s[p+1][i]);
    printf("%d\n",dp[n][k]);
    return 0;
}

Title Description

One of the famous proofs of modern mathematics is Georg Cantor's proof that rational numbers are enumerable. He uses the following table to prove this proposition:

1/11/1 , 1/21/2 , 1/31/3 , 1/41/4, 1/51/5, ...

2/12/1, 2/22/2 , 2/32/3, 2/42/4, ...

3/13/1 , 3/23/2, 3/33/3, ...

4/14/1, 4/24/2, ...

5/15/1, ...

... We give each item in the table above a ZZ number. The first item is 1/11/1, followed by 1/21/2, 2/12/1, 3/13/1, 2/22/2,...

Input format

Integer NN (1 < N < 100000001 < N < 10000000)

Output format

NN Item in Table

Input and Output Samples

Input #1 replication

7

Output #1 replication

1/4

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n==1)
        cout<<"1/1";
    else
    {
        int m,x = 0,t = 1;
        while(x < n)
        {
            x += t;
            t++;
        }
        t--;
        m = abs(x - n);
        if(t%2==0)
            cout<<t-m<<"/"<<m+1;
        else
            cout<<m+1<<"/"<<t-m;
    }
    return 0;
}

python version:

n=input()
n=int(n)
i=0
j=0
while n>j:
    i+=1
    j+=i
if i%2==1:
    print(str(j-n+1)+'/'+str(i+n-j))
else:
    print(str(i+n-j)+'/'+str(j-n+1))

Title Description

The integer nn is divided into kk parts, and each part can not be empty. Any two schemes are different (without considering the order).

For example: n=7n=7, k=3k=3, the following three methods are considered the same.

1,1,51,1,5;
1,5,11,5,1;
5,1,15,1,1.

Ask how many different divisions there are.

Input format

n,kn,k (6<n \le 2006<n≤200，2 \le k \le 62≤k≤6)

Output format

Eleven integers, i.e. different fractions.

Input and Output Samples

Input #1 replication

7 3

Output #1 replication

4

Note/hint

The four methods are as follows:
1,1,51,1,5;
1,2,41,2,4;
1,3,31,3,3;
2,2,32,2,3.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n,k,dp[205][10];

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++)
        dp[i][1]=dp[i][i]=1;
    for(int i=2; i<=n; i++)
    {
        for(int j=2; j<=min(i-1,k); j++)
            dp[i][j]=dp[i-j][j]+dp[i-1][j-1];
    }
    printf("%d\n",dp[n][k]);
    return 0;
}