Codeforces ラウンド #272 (ディビジョン 2)AKreport_html/css_WEB-ITnose

A. Dreamoon と Stairs

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

Dreamoon n段の階段を登りたいと思っています。彼は移動するたびに 1 段か 2 段登ることができます。 Dreamoon は、手数を整数 m の倍数にしたいと考えています。

彼の条件を満たす階段の一番上まで登る最小の歩数は何ですか?

入力

1 行には、スペースで区切られた 2 つの整数 n、m (0?

出力

単一の整数を出力します ?最小移動数は m の倍数です。満足のいく条件で登ることができない場合は、代わりに ?-?1 を出力します。

サンプル テスト

入力

10 2

出力

入力

3 5

出力

-1

注

最初のサンプルでは、​​Dreamoon は次のステップのシーケンスで 6 つの手で登ることができました: {2, 2, 2, 2, 1, 1}。

2 番目のサンプルでは、​​ステップは 3 つだけです。ステップ {2, 1}、{1, 2}、{1, 1, 1} の有効なシーケンス (それぞれ 2、2、および 3 ステップ)。これらすべての数字は 5 の倍数ではありません。

要求の次数が m の倍数の場合、最小次数はいくらか、
若くは応答案出力 - 1 です。リー

B. Dreamoon と WiFi


テストごとの制限時間
1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

Dreamoon は数直線上の 0 の位置に立っています。 Drazil は Wi-Fi 経由で Dreamoon のスマートフォンにコマンドのリストを送信し、Dreamoon はそれに従います。

各コマンドは次の 2 種類のいずれかです:

'+' で示される正の方向に 1 ユニット移動します

Go負の方向に 1 単位、「-」で示されます

しかし、Wi-Fi の状態が非常に悪いため、Dreamoon のスマートフォンは一部のコマンドが認識できないと報告し、Dreamoon はコマンドの一部が正常ではあるものの間違っている可能性があることを認識しています認識された。 Dreamoon は、認識されたすべてのコマンドに従い、認識されていないコマンドを決定するために公正なコインを投げることを決定します (つまり、同じ確率 0.5 でマイナスまたはプラスの方向に 1 ユニット移動します)。

Drazil によって送信されたコマンドのオリジナルのリストと Dreamoon によって受信されたリストが与えられます。 Drazil のコマンドによって、Dreamoon が本来最終であるはずの位置で終了する確率はどれくらいですか?

入力 最初の行には文字列 s1 が含まれています ? Drazil が Dreamoon に送信するコマンド。この文字列は、セット {'+', '-'} 内の文字のみで構成されます。

2 行目には文字列 s2 ? が含まれています。 Dreamoon のスマートフォンが認識するコマンドの場合、この文字列は {'+'、'-'、'?'} のセット内の文字のみで構成されます。 「？」認識できないコマンドを示します。

2 つの文字列の長さは等しく、10 を超えません。

Output

Output a single real number corresponding to the probability. The answer will be considered correct if its relative or absolute error doesn't exceed 10?-?9.

Sample test(s)

Input

++-+-+-+-+

Output

1.000000000000

Input

+-+-+-??

Output

0.500000000000

Input

+++??-

Output

0.000000000000

Note

For the first sample, both s1 and s2 will lead Dreamoon to finish at the same position ?+?1.

For the second sample, s1 will lead Dreamoon to finish at position 0, while there are four possibilites for s2: {"+-++", "+-+-", "+--+", "+---"} with ending position {+2, 0, 0, -2} respectively. So there are 2 correct cases out of 4, so the probability of finishing at the correct position is 0.5.

For the third sample, s2 could only lead us to finish at positions {+1, -1, -3}, so the probability to finish at the correct position ?+?3 is 0.

题意：给两个长度不超过10的相同长度的串，

第一个串由+和-组成，

第二个串由+和-和？组成，

初始状态为0，+代表+1，-代表-1，

现在要求上下结果状态相同时，概率是多少。

做法：先判断是否有解，若无解输出0，

若有解，求出第二个串还需要多少个+，

统计？的数量，求出组合数除以所有的可能数量。

或者，直接爆搜，因为最多只有10个字符，

所以，不会超时。

代码：

#include<iostream>#include<map>#include<string>#include<cstring>#include<cstdio>#include<cstdlib>#include<cmath>#include<queue>#include<vector>#include<algorithm>using namespace std;int s1,s2,s3;void dfs(int step,int val){    if(step==s2)    {        if(val==s1)            s3++;        return;    }    dfs(step+1,val+1);    dfs(step+1,val-1);}int main(){    string a,b;    int n,i;    cin>>a>>b;    n=a.length();    s1=0;    for(i=0;i<n;i++)        if(a[i]=='+')            s1++;        else            s1--;    s2=0;    for(i=0;i<n;i++)        if(b[i]=='+')            s1--;        else if(b[i]=='-')            s1++;        else            s2++;    s3=0;    dfs(0,0);    printf("%.10f",(double)s3/(1<<s2));}

C. Dreamoon and Sums

time limit per test

1.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Dreamoon loves summing up something for no reason. One day he obtains two integers a and b occasionally. He wants to calculate the sum of all nice integers. Positive integer x is called nice if and , where k is some integer number in range [1,?a].

By we denote the quotient of integer division of x and y. By we denote the remainder of integer division of x and y. You can read more about these operations here: http://goo.gl/AcsXhT.

The answer may be large, so please print its remainder modulo 1?000?000?007 (109?+?7). Can you compute it faster than Dreamoon?

Input

The single line of the input contains two integers a, b (1?≤?a,?b?≤?107).

Output

Print a single integer representing the answer modulo 1?000?000?007 (109?+?7).

Sample test(s)

Input

1 1

Output

Input

2 2

Output

Note

For the first sample, there are no nice integers because is always zero.

For the second sample, the set of nice integers is {3,?5}.

题意：给出两个数a,b,当

div(x,b)/mod(x,b)=k，1<=k<=a时，求出

所有可能的x的和对1?000?000?007取余的结果。

做法：

设y=div(x,b),z=mod(x,b)，

可以得到

y=z*k,y*b+z=x,联立得

(kb+1)z=x,

下面用到求和公式，

然后假设k为常量，得到x=b(b-1)*(kb+1)/2，

最后k还原为变量，得到x=b(b-1)/2*[(1+a)a*b/2+a]

代码：

#include<iostream>#include<map>#include<string>#include<cstring>#include<cstdio>#include<cstdlib>#include<cmath>#include<queue>#include<vector>#include<algorithm>using namespace std;const long long mod=1000000007;int main(){	long long a,b,t1,t2,t3;	cin>>a>>b;	t1=(1+a)*a/2%mod;	t1=(t1*b)%mod;	t1=(t1+a)%mod;	t2=b*(b-1)/2%mod;	t3=(t1*t2)%mod;	cout<<t3;}

D. Dreamoon and Sets

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Dreamoon likes to play with sets, integers and . is defined as the largest positive integer that divides both a and b.

Let S be a set of exactly four distinct integers greater than 0. Define S to be of rank k if and only if for all pairs of distinct elements si, sj from S, .

Given k and n, Dreamoon wants to make up n sets of rank k using integers from 1 to m such that no integer is used in two different sets (of course you can leave some integers without use). Calculate the minimum m that makes it possible and print one possible solution.

Input

The single line of the input contains two space separated integers n, k (1?≤?n?≤?10?000,?1?≤?k?≤?100).

Output

On the first line print a single integer ? the minimal possible m.

On each of the next n lines print four space separated integers representing the i-th set.

Neither the order of the sets nor the order of integers within a set is important. If there are multiple possible solutions with minimal m, print any one of them.

Sample test(s)

Input

1 1

Output

51 2 3 5

Input

2 2

Output

222 4 6 2214 18 10 16

Note

For the first example it's easy to see that set {1,?2,?3,?4} isn't a valid set of rank 1 since .

题意：

求出n个集合均为4个元素，且每个集合内任意两两

元素的最大公约数为k，集合不允许有交集，

当n*4个元素最大值最小时，输出所有n个集合，

如果有多组结果输出任意一组。

做法：

很明显，当任意集合内的所有元素除以k后，

两两元素之间是互质的，然后为了满足元素最大值最小，

在除掉k后，任意集合内肯定是由3个奇数，1个偶数组成，

因为若少一个奇数，就会有至少一对数不互质，

若多一个奇数，元素最大值就会变大。

所以，从1开始构建所有元素集合即可。

代码：

#include<iostream>#include<map>#include<string>#include<cstring>#include<cstdio>#include<cstdlib>#include<cmath>#include<queue>#include<vector>#include<algorithm>using namespace std;int main(){    int n,k;    cin>>n>>k;    cout<<(6*n-1)*k<<endl;    while(n--)    {        cout<<(6*n+1)*k<<" "<<(6*n+2)*k<<" "<<(6*n+3)*k<<" "<<(6*n+5)*k<<endl;    }}

E. Dreamoon and Strings

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Dreamoon has a string s and a pattern string p. He first removes exactly x characters from s obtaining string s' as a result. Then he calculates that is defined as the maximal number of non-overlapping substrings equal to p that can be found in s'. He wants to make this number as big as possible.

More formally, let's define as maximum value of over all s' that can be obtained by removing exactly x characters from s. Dreamoon wants to know for all x from 0 to |s| where |s| denotes the length of string s.

Input

The first line of the input contains the string s (1?≤?|s|?≤?2?000).

The second line of the input contains the string p (1?≤?|p|?≤?500).

Both strings will only consist of lower case English letters.

Output

Print |s|?+?1 space-separated integers in a single line representing the for all x from 0 to |s|.

Sample test(s)

Input

aaaaaaa

Output

2 2 1 1 0 0

Input

axbaxxbab

Output

0 1 1 2 1 1 0 0

Note

For the first sample, the corresponding optimal values of s' after removal 0 through |s|?=?5 characters from s are {"aaaaa", "aaaa", "aaa", "aa", "a", ""}.

For the second sample, possible corresponding optimal values of s' are {"axbaxxb", "abaxxb", "axbab", "abab", "aba", "ab", "a", ""}.

题意：

给出两个串，当对第一个串长度为n时，

分别除去1到n个字符可以获得n个新串，

要求每个新串的子串为第二个串的数量最大，

输出n个新串的所谓最大数量。

做法：

dp[i][j]:第一个串0到i的位置除去j个字符可以得到的最大数量
（j<=i,且除去的位置不包括i）
a[i]：从i开始，包含第二个串的最近位置，若没有赋值为-1，
ns:第一个串的长度
np:第二个串的长度
有
dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
//若不删除第i个字符dp[i+1][j]=dp[i][j]
dp[i+1][j+1]=max(dp[i][j],dp[i+1][j+1]);
//若删除第i个字符dp[i+1][j+1]=dp[i][j]
if(a[i]>0)
dp[i+a[i]][j+a[i]-np]=max(dp[i][j]+1,dp[i+a[i]][j+a[i]-np]);
//若删除从i开始后到i+a[i]不包含与第二个串相同的字符，
dp[i+a[i]][j+a[i]-np]=dp[i][j]+1

因为dp[ns-1][j]木有考虑ns-1个字符是否删除的情况，

所以最终答案存在dp[ns][j]中。

代码：

#include<iostream>#include<map>#include<string>#include<cstring>#include<cstdio>#include<cstdlib>#include<cmath>#include<queue>#include<vector>#include<algorithm>using namespace std;int a[2010],dp[2010][2010];int main(){    string s,p;    int i,j,k,ns,np;    cin>>s>>p;    ns=s.length();    np=p.length();    for(i=0;i<ns;i++)    {        j=0;k=i;        while(j<np&&k<ns)        {            if(p[j]==s[k])                j++;            k++;        }        a[i]= j==np?k-i:-1;    }    for(i=0;i<ns;i++)        for(j=0;j<=i;j++)        {            dp[i+1][j]=max(dp[i][j],dp[i+1][j]);            dp[i+1][j+1]=max(dp[i][j],dp[i+1][j+1]);            if(a[i]>0)                dp[i+a[i]][j+a[i]-np]=max(dp[i][j]+1,dp[i+a[i]][j+a[i]-np]);        }    i=ns;    cout<<dp[i][0];    for(j=1;j<=ns;j++)        cout<<" "<<dp[i][j];}