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

链接 : http://codeforces.com/contest/476

D题yy、ABC水

A.と階段

テストごとの制限時間

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 の倍数ではありません。

<span style="font-size:14px;">#include <cstdio>int main(){    int n, m;    scanf("%d %d", &n, &m);    int temp = n / 2;    if(n % 2)         temp++;    if(temp % m == 0)         printf("%d\n", temp);    else    {        temp = temp + m - temp % m;        if(temp > n)             printf("-1\n");        else             printf("%d\n", temp);    }}</span>

B. Dreamoon と WiFi

テストごとの制限時間

1 秒

メモリテストごとの制限

256 メガバイト

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

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

1. '+' で示される正の方向に 1 ユニット移動します
2. Go負の方向に 1 単位、「-」で示されます

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

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

入力

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

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

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

出力

確率に対応する 1 つの実数を出力します。相対誤差または絶対誤差が 10?-?9 を超えない場合、答えは正しいとみなされます。

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.

<span style="font-size:14px;">#include <cmath>#include <cstdio>#include <cstring>char s1[15],s2[15];int main(){    scanf("%s %s",s1,s2);    int p1=0, m1=0;    int p2=0, m2=0;    int size=(int)strlen(s1);    int wh=0;    for(int i=0;i<size; i++)    {        if(s1[i]=='+') ++p1;        else ++m1;    }    for(int i=0;i<size; i++)    {        if(s2[i]=='+') ++p2;        else if(s2[i]=='-') ++m2;        else ++wh;    }    if(wh == 0)    {        if(p1 - m1 == p2 - m2)            printf("1\n");        else            printf("0\n");        return 0;    }    int all = 1;    for(int i = 0;i < wh; i++)        all *= 2;    int pneed,mneed;    int temp = p1 - m1 - p2 + m2;    if(fabs(temp) > wh)    {        printf("0\n");        return 0;    }    pneed = (temp + wh) / 2;    mneed = wh - pneed;    int ans = 1;    for(int i = 0; i < pneed; i++)    {        ans *= wh;        --wh;    }    for(int i=1; i<= pneed; i++)        ans /= i;    printf("%.12f\n",double(ans)/double(all));}</span>

C. Dreamoon and Sums

time limit per test

1.5 seconds

memory limit per test

256 megabytes

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

<span style="font-size:14px;">#include <cstdio>#define ll long longconst int mod=1e9 + 7;int main(){    ll a,b;    scanf("%I64d %I64d", &a, &b);    if(b == 1)         printf("0\n");    else    {        ll res = (b * (b - 1) / 2) % mod;        ll sum = (a * (a + 1) / 2) % mod;        ll ans = (a % mod * res % mod) % mod;        ll temp = (sum % mod * res % mod) % mod;        printf("%I64d\n", (ans % mod + (temp % mod * b % mod)) % mod);    }}</span>

D. Dreamoon and Sets

time limit per test

1 second

memory limit per test

256 megabytes

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 .

<span style="font-size:14px;">#include <cstdio>int main(){    int n, k;    scanf("%d %d", &n, &k);    int a = 1, b = 2, c = 3, d = 5;    printf("%d\n", (d * k + 6 * k * (n- 1)));    a *= k; b *= k; c *= k; d *= k;    for(int i = 0; i < n; i++)    {        printf("%d %d %d %d\n",a, b, c, d);        a += 6 * k;        b += 6 * k;        c += 6 * k;        d += 6 * k;    }}</span>