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

Codeforces Round #272 (Div. 2)

A. Dreamoon と Stairs

テストごとの制限時間

1 秒

テストあたりのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

Dreamoon は n 段の階段を登りたいと考えています。彼は移動ごとに 1 段または 2 段を登ることができます。 Dreamoon は、移動数が整数 m の倍数であることを望んでいます。

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

入力

1 行には 2 つが含まれていますスペース区切りの整数 n, m (0?

出力

単一の整数を出力します。最小移動数は m の倍数です。満足のいく条件を登ることができない場合は、代わりに print ?-?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 の倍数ではありません。

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.

简单题：

/** * Created by ckboss on 14-10-16. */import java.util.*;public class CF476B {    static double Calu(int deta,int c){        double ret=1;        for(int i=c;i>=c-deta+1;i--){            ret=ret*i;        }        for(int i=1;i<=deta;i++){            ret=ret/i;        }        for(int i=1;i<=c;i++){            ret=ret*0.5;        }        return ret;    }    public static void main(String[] args){        Scanner in = new Scanner(System.in);        String cmd1=in.next();        String cmd2=in.next();        int a1=0,b1=0,a2=0,b2=0,c=0;        for(int i=0,sz=cmd1.length();i<sz;i++){            if(cmd1.charAt(i)=='+') a1++;            else b1++;        }        for(int i=0,sz=cmd2.length();i<sz;i++){            if(cmd2.charAt(i)=='+') a2++;            else if(cmd2.charAt(i)=='-') b2++;            else c++;        }        double ans=0.0;        if(a2<=a1&&b2<=b1){            ans = Calu(a1-a2,c);        }        System.out.print(ans);    }}





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 niceintegers. 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}.

化简一下式子。。。。

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long int LL;const LL MOD=1000000007LL;LL a,b;LL bl(){    LL ret=0;    LL bbb=(b*(b-1)/2)%MOD;    for(int i=1;i<=a;i++)        ret=(ret+((i*bbb)%MOD*b)%MOD+bbb)%MOD;    return ret;}int main(){    cin>>a>>b;    cout<<bl()<<endl;    return 0;}





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 .

规律，6×i+1 ， 6×i+2 ， 6×i+3 ， 6×i+5

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int n,k;int main(){    scanf("%d%d",&n,&k);    printf("%d\n",(6*(n-1)+5)*k);    for(int i=0;i<n;i++)    {        printf("%d %d %d %d\n",k*(6*i+1),k*(6*i+2),k*(6*i+3),k*(6*i+5));    }    return 0;}





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", ""}.




DP

DP[i][j]再第一个串中前i个字符里删j个能得到的最大匹配数

cal(i)从第一个串第i个字符往前删至少删几个可以和第二个串匹配




dp[i][j]=max( dp[i-1][j],dp[i-cal(i)-len2][j-cal(i)] );




#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>using namespace std;const int INF=0x3f3f3f3f;char s[2200],p[550];int dp[2200][2200],len1,len2;int cal(int x){    if(x<len2) return INF;    int ans=0,p1=len2,q=x;    while(p1&&q)    {        if(s[q]==p[p1]) p1--,q--;        else ans++,q--;    }    if(p1==0) return ans;    return INF;}int main(){    scanf("%s%s",s+1,p+1);    len1=strlen(s+1),len2=strlen(p+1);    for(int i=0;i<=len1;i++)    {        for(int j=0;j<=len1;j++)        {            if(i<j) dp[i][j]=-INF;        }    }    for(int i=1;i<=len1;i++)    {        int x=cal(i);        for(int j=0;j<=len1;j++)        {            dp[i][j]=max(dp[i-1][j],dp[i][j]);            if(j-x>=0) dp[i][j]=max(dp[i][j],dp[i-x-len2][j-x]+1);        }    }    for(int i=0;i<=len1;i++)        printf("%d ",dp[len1][i]);    putchar(10);    return 0;}