Codeforces ラウンド #259 (ディビジョン 2) A B C 3 連続ラウンド_html/css_WEB-ITnose

A. リトルポニーとクリスタルマイン

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

トワイライトスパークルはかつてクリスタル鉱山からクリスタルを入手しました。サイズ n の結晶 (n は奇数; n?>?1) は、ダイヤモンドが刻まれた n?×?n 行列です。

奇数の整数 n が与えられます。サイズ n の結晶を描画する必要があります。マトリックスのひし形のセルは文字「D」で表す必要があります。マトリックスの他のすべてのセルは文字「*」で表す必要があります。例を見て、何を描画する必要があるかを理解してください。

入力

唯一の行には整数 n (3?≤?n?≤?101; n は奇数) が含まれています。

出力

出力サイズ n の結晶。

サンプルテスト

入力

出力

RREE

入力

出力

*D*DDD*D*

入力

出力

**D***DDD*DDDDD*DDD***D**

B. リトルポニーとシフトで並べ替え

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

ある日、Twilight Sparkle は、一連の整数 a1,?a2,?..., を並べ替える方法に興味がありました。 ?an は降順ではありません。若いユニコーンである彼女が実行できる唯一の操作はユニットのシフトです。つまり、シーケンスの最後の要素を先頭に移動できます:

a1,?a2,?...,?an?→?an,?a1,?a2,?...,?an?-? 1.

トワイライト スパークルの計算を手伝ってください: シーケンスを並べ替えるのに必要な操作の最小数は何ですか?

入力 最初の行には整数 n (2?≤?n?≤?105) が含まれています。 2 行目には n 個の整数 a1,?a2,?...,?an(1?≤?ai?≤?105) が含まれています。

出力

シーケンスを並べ替えることが不可能な場合は、-1 を出力します。それ以外の場合は、Twilight Sparkle がソートするために必要な操作の最小数を出力します。

サンプル テスト

入力

***D*****DDD***DDDDD*DDDDDDD*DDDDD***DDD*****D***

入力

#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>using namespace std;char mapp[110][110];int main(){    int i,j;    int cas;    while(~scanf("%d",&cas))    {        memset(mapp,0,sizeof(mapp));        int ans=cas/2;        for(i=0;i<cas/2+1;i++)        {            for(j=0;j<cas;j++)        {            if(j<ans||j>cas-ans-1)                mapp[i][j]='*';            else mapp[i][j]='D';        }        ans--;        cout<<mapp[i]<<endl;        }        for(i=cas/2-1;i>=0;i--)            cout<<mapp[i]<<endl;    }    return 0;}

出力

22 1

入力

出力

#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>int a[100010];int main(){    int i,j;    int cas;    int flag=0;    int ans=0;    while(~scanf("%d",&cas))    {        for(i=0;i<cas;i++)            scanf("%d",&a[i]);        for(i=1;i<cas;i++)        {            if(a[i]<a[i-1])            {flag++;}            if(flag==1)            ans++;            if(flag==3)                break;        }        if((flag==1&&a[cas-1]<=a[0])||flag==0)            printf("%d\n",ans);        else printf("-1\n");    }    return 0;}

C. Little Pony and Expected Maximum

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Twilight Sparkle was playing Ludo with her friends Rainbow Dash, Apple Jack and Flutter Shy. But she kept losing. Having returned to the castle, Twilight Sparkle became interested in the dice that were used in the game.

The dice has m faces: the first face of the dice contains a dot, the second one contains two dots, and so on, the m-th face contains mdots. Twilight Sparkle is sure that when the dice is tossed, each face appears with probability . Also she knows that each toss is independent from others. Help her to calculate the expected maximum number of dots she could get after tossing the dice n times.

Input

A single line contains two integers m and n (1?≤?m,?n?≤?105).

Output

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

Sample test(s)

input

6 1

output

3.500000000000

input

6 3

output

4.958333333333

input

2 2

output

1.750000000000

Note

Consider the third test example. If you've made two tosses:

1. You can get 1 in the first toss, and 2 in the second. Maximum equals to 2.
2. You can get 1 in the first toss, and 1 in the second. Maximum equals to 1.
3. You can get 2 in the first toss, and 1 in the second. Maximum equals to 2.
4. You can get 2 in the first toss, and 2 in the second. Maximum equals to 2.

The probability of each outcome is 0.25, that is expectation equals to:

You can read about expectation using the following link: http://en.wikipedia.org/wiki/Expected_value

#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<string>#include<algorithm>using namespace std;int a[100010];typedef double LL;double qpow(double a,int b){    LL ans=1;    while(b)    {        if(b&1) ans*=a;        b>>=1;        a*=a;    }    return ans;}int main(){    int n;    int m;    scanf("%d%d",&n,&m);    double ans=0;    for(int i=1;i<=n;i++)        ans+=(qpow(1.0*i/n,m)-qpow(1.0*(i-1)/n,m))*i;    printf("%.12f\n",ans);    return 0;}