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

A. SwapSort

テストごとの時間制限

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

この問題での目標はn 個の整数で構成される配列を最大 n 個のスワップで並べ替えます。指定された配列について、配列を非降順でソートするスワップのシーケンスを見つけます。スワップは、次々と連続して実行されます。

この問題では、スワップの数を最小限に抑える必要がないことに注意してください。あなたのタスクは、n 以下のシーケンスを見つけることです。

入力

入力の最初の行には、整数 n (1?≤?n?≤?3000) が含まれています。配列要素の数。 2 行目には配列の要素が含まれています: a0,?a1,?...,?an?-?1 (?-?109?≤?ai?≤?109)。ここで、ai は配列の i 番目の要素です。 。要素は左から右に 0 から n?-?1 まで番号付けされます。一部の整数は配列内に複数回出現する場合があります。

出力

最初の行で print k (0?≤?k?≤?n) ?スワップの数。次の k 行には、k スワップの説明を 1 行に 1 つずつ含める必要があります。各スワップは、要素 ai と aj のスワップを表す整数 i, j (0?≤?i,?j?≤?n?-?1) のペアとして出力する必要があります。ペアのインデックスは任意の順序で出力できます。スワップは、出力に表示される順序で、最初から最後まで実行されます。 i?=?ja を出力し、同じ要素のペアを複数回交換することができます。

複数の答えがある場合は、いずれかを出力します。少なくとも 1 つの答えが存在することが保証されています。

サンプル テスト

入力

55 2 5 1 4

出力

20 34 2

入力

610 20 20 40 60 60

出力

入力

2101 100

出力

1<p>0 1</p><p></p><p></p><pre name="code" class="n">#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int a[3010];int b[120];int vis[120];typedef pair<int,int> P;P m[3010];int main(){   #ifdef xxz    freopen("in.txt","r",stdin);    #endif // [xxz    int n;    cin>>n;    for(int i = 0; i < n; i++)        cin>>a[i];    int sum = 0,ans = 0;    int i,j;    for(i = 0; i < n; i++)    {        int x = a[i];        int y = i;        for( j = i+1; j < n; j++)        {           if(x > a[j])           {                x = a[j];                y = j;           }        }        if(y != i)        {            m[sum].first = i;            m[sum++].second = y;            swap(a[i],a[y]);            ans++;        }    }    cout<<ans<<endl;    for(int i = 0; i < ans; i++)    {        cout<<m[i].first<<" "<<m[i].second<<endl;    }    return 0;}

B. BerSU Ball

テストごとの制限時間

1 秒

テストごとのメモリ制限

2 56メガバイト

入力

標準入力

出力

標準出力

ベルランド州立大学は創立 100500 周年を記念して社交ダンスを開催します。 n 人の男の子と m 人の女の子は、すでにワルツ、メヌエット、ポロネーズ、カドリーユの動きのリハーサルで忙しいです

私たちは、数組の男の子と女の子のペアが舞踏会に招待されることを知っています。ただし、各ペアのパートナーのダンス スキルの差は最大でも 1 つでなければなりません。

各少年のダンス スキルはわかっています。同様に、私たちは各女の子のダンススキルを知っています。 n 人の男の子と m 人の女の子から形成できるペアの最大数を決定できるコードを作成します。

入力

最初の行には整数 n が含まれています (1?≤?n?≤?100) ?男の子の数。 2 行目にはシーケンス a1,?a2,?...,?an (1?≤?ai?≤?100) が含まれており、ai は i 番目の少年のダンス スキルです

同様に、3 行目には整数が含まれていますm (1?≤?m?≤?100) ?女の子の数。 4 行目にはシーケンス b1,?b2,?...,?bm (1?≤?bj?≤?100) が含まれています。ここで、bj は j 番目の女の子のダンス スキルです。

出力

単一の出力番号 ？必要なペアの最大可能数。

Sample test(s)

input

41 4 6 255 1 5 7 9

output

input

41 2 3 4410 11 12 13

output

input

51 1 1 1 131 2 3

output

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int a[120];int b[120];int vis[120];int main(){   #ifdef xxz    freopen("in.txt","r",stdin);    #endif // [xxz    int n,m;    cin>>n;    for(int i = 0; i < n; i++) cin>>a[i];    sort(a,a+n);    cin>>m;    for(int i = 0; i < m; i++) cin>>b[i],vis[i] = 0;    sort(b,b+m);    int sum = 0;    int j;    for(int i =0; i < n; i++)    {        for( int j = 0; j < m; j++)        {            if(vis[j] == 0 && abs(a[i] - b[j]) <= 1 )            {                sum++;                vis[j] = 1;                break;            }        }    }    cout<<sum<<endl;    return 0;}

C. Given Length and Sum of Digits...

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You have a positive integer m and a non-negative integer s. Your task is to find the smallest and the largest of the numbers that have length m and sum of digits s. The required numbers should be non-negative integers written in the decimal base without leading zeroes.

Input

The single line of the input contains a pair of integers m, s (1?≤?m?≤?100,?0?≤?s?≤?900) ? the length and the sum of the digits of the required numbers.

Output

In the output print the pair of the required non-negative integer numbers ? first the minimum possible number, then ? the maximum possible number. If no numbers satisfying conditions required exist, print the pair of numbers "-1 -1" (without the quotes).

Sample test(s)

input

2 15

output

69 96

input

3 0

output

-1 -1

#include <iostream>#include <algorithm>#include <cstdio>using namespace std;bool can(int m, int s){    if(s >= 0 && 9*m >= s) return true;    else return false;}int main(){    int m,s;    cin>>m>>s;    if(!can(m,s))    {        cout<<"-1"<<" "<<"-1"<<endl;        return 0;    }    if(m == 1)    {        if(s >= 10)        {            cout<<"-1"<<" "<<"-1"<<endl;        }        else cout<<s<<" "<<s<<endl;    }    else {        if(s == 0) cout<<"-1"<<" "<<"-1"<<endl;        else {            string minn, maxn;            int sum = s;            for(int i = 1; i <= m; i++)                for(int j = 0; j < 10; j++)            {                if((j > 0 || (j == 0 && i > 1) ) && can(m - i, sum - j))                   {                       minn += char('0' + j);                       sum -= j;                       break;                   }            }            sum = s;               for(int i = 1; i <= m; i++)                for(int j = 9; j >= 0; j--)            {                if(can(m - i, sum - j))                   {                       maxn += char('0' + j);                       sum -= j;                       break;                   }            }            cout<<minn<<" "<<maxn<<endl;        }    }    return 0;}