ブルーブリッジカップ練習(二)

ブルーブリッジカップ練習(二)

階乗計算

高精度加算

Huffumanツリー

n皇后問題

時報アシスタント

回形取数

亀ウサギ競走予測

時間変換

文字列対比

FJの文字列

参考ブログ

階乗計算

問題の説明は正の整数nを入力して、nを出力します!で行ないます.入力フォーマット入力は正の整数n,n<=1000を含む.太字スタイル出力フォーマット出力n!を行ないます.

#include
using namespace std;
const int maxn = 1e4;
int a[maxn]={1};
int main(){
    int n,d,t=1;
    scanf("%d",&n);
    for(int i=2;i<=n;++i){
        d=0;
        for(int j=0;j<t;++j){
            a[j]=a[j]*i+d;
            d=a[j]/10;
            a[j]%=10;
        }
        while(d){
            a[t++]=d%10;
            d/=10;
        }
    }
    //printf("%d",t);
    for(int i=t-1;i>=0;--i)printf("%d",a[i]);
}

高精度加算

2つの整数aとbを入力し、この2つの整数の和を出力します.aもbも100位を超えない.

#include
using namespace std;
const int maxn = 1e2+1;
int a[maxn]={0};
int b[maxn]={0};

void transfer(string &s,int c[]){
    int t=0;
    for(int i=s.size()-1;i>=0;--i){
        c[t++]=s[i]-'0';
    }
}

int main(){
   string s;
   cin>>s;
   transfer(s,a);
   cin>>s;
   transfer(s,b);
   int d=0;
   for(int i=0;i<maxn;++i){
       a[i]+=b[i]+d;
       if(a[i]>9){
           a[i]-=10;
           d=1;
       }else d=0;
   }
   for(int i=maxn-1;i>0;--i){
       if(a[i]!=0){
           for(int t=i;t>=0;--t){
               cout<<a[t];
           }
           return 0;
       }
   }
   cout<<0;
   return 0;
}

ハフマンの木

問題記述Huffmanツリーは符号化に広く応用されている.ここでは,Huffman樹の構造過程のみに関心を持つ.列数{pi}={p 0,p 1,...,pn−1}を与え,この列数でHuffmanツリーを構築する過程は以下の通りである.{pi}の最小の2つの数を見つけ、paとpbに設定し、paとpbを{pi}から削除し、それらの和を{pi}に追加します.このプロセスの費用はpa+pbと記す.　　2. 手順1を繰り返し、{pi}に数が1つしか残っていないまで繰り返します.上の操作過程ですべての費用を加算すると,Huffmanツリーを構築する総費用が得られる.このタスク:指定された数列について、Huffmanツリーをこの数列で構築する総費用を求めます.入力フォーマット入力の最初の行には、正の整数n(n<=100)が含まれます.次はn個の正の整数で、p 0,p 1,...,pn-1を表し、各数は1000を超えない.

#include
using namespace std;

int main(){
    priority_queue<int,vector<int>,greater<int> > q;
    int n,d;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%d",&d);
        q.push(d);
    }
    int sum = 0;
    while(q.size()>1){
        d = q.top();q.pop();
        d+=q.top();q.pop();
        sum+=d;
        //printf("%d ",d);
        q.push(d);
    }
    printf("%d",sum);
}

2 n皇后問題

問題の説明はn*nの碁盤を与えて、碁盤の中にいくつかの位置が皇后を置くことができません.今、碁盤にn人の黒皇后とn人の白皇后を入れて、任意の2人の黒皇后が同じ行、同じ列または同じ対角線上になく、任意の2人の白皇后が同じ行、同じ列または同じ対角線上にないようにします.全部で何種類の置き方がありますか?nは8以下である.入力フォーマット入力の第1の動作は、碁盤のサイズを表す整数nである.次にn行、各行n個の0または1の整数、もし1つの整数が1であれば、対応する位置が皇后を置くことができることを示し、1つの整数が0であれば、対応する位置が皇后を置くことができないことを示す.

#include
using namespace std;
const int maxn = 10;
int g[maxn][maxn];// 1  ，0   2， ，3  
int n,ans;
int row1[maxn];
int row2[maxn];

bool check(int t,int col,int row[]){
    for(int i=0;i<t;++i)
        if(row[i]==col||abs(i-t)==abs(row[i]-col))
            return false;
    
    return true;
}

void dfs(int i,int j,int row[]){
    if(i==n&&3==j){
        ans++;
        return;
    }
    if(i==n&&j==2){
        dfs(0,3,row2);
    }
    for(int t=0;t<n;++t){
        if(g[i][t]==1&&check(i,t,row)){
            row[i]=t;
            g[i][t]=j;
            dfs(i+1,j,row);
            g[i][t]=1;
        }
    }
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j)scanf("%d",&g[i][j]);
    }
    dfs(0,2,row1);
    printf("%d",ans);
    return 0;
}

時報アシスタント

質問の説明現在の時間を指定して、英語の読み方で読んでください.時間は時間hと分mで表され、英語の読み方では、1時間読む方法は、mが0であれば時間を読み出し、3:00に「three o’clock」と読むように「o’clock」を加えることです.mが0でない場合は、時間を読み出し、5:30のように「five thirty」と読む.時と分の読み方は英数字の読み方で、0~20は0:zero、1:one、2:two、3:three、4:four、5:five、6:six、7:seven、8:eight、9:nine、10:ten、11:eleven、12:twelve、13:thirteen、14:fourteen、15:fifteen、16:sixteen、17:seventeen、18:eighteen、19:nineteen、20:twentyと読みます.30はthirty、40はforty、50はfiftyと読みます.20より60未満の数字については、まず10の数を読み、次に桁数を加えます.31のようにまず30に1を加えた読み方で、「thirty one」と読みます.上記のルールで21:54を「twenty one fifty four」、9:07を「nine seven」、0:15を「zero fifteen」と読みます.入力フォーマット入力は、時間の時と分を表す2つの非負の整数hとmを含む.ゼロ以外の数値の先頭に0はありません.hは24未満、mは60未満である.

#include
using namespace std;

string msg[] ={"zero","one","two","three","four","five","six","seven",
"eight","nine","ten","eleven","twelve","thirteen","fourteen","fifteen",
"sixteen","seventeen","eighteen","nineteen","twenty"};

int main(){
    int h,m;
    cin>>h>>m;
     if(h<21)cout<<msg[h];
     else  cout<<msg[20]<<" "<<msg[h-20];
    if(m==0){
        cout<<" o'clock";
    }else{
        cout<<" ";
        if(m<21)cout<<msg[m];
        else if(m<30)cout<<msg[20]<<" "<<msg[m-20];
        else if(m==30)cout<<"thirty";
        else if(m<40)cout<<"thirty"<<" "<<msg[m-30];
        else if(m==40)cout<<"forty";
        else if(m<50)cout<<"forty"<<" "<<msg[m-40];
        else if(m==50)cout<<"fifty";
        else cout<<"fifty "<<msg[m-50];
    }
}

かいふくしゅうすう

問題記述リターン数はマトリクスのエッジに沿って数を取り、現在の方向に無数に取れるか、すでに取った場合、左に90度回転します.最初はマトリクスの左上隅に位置し、方向を下にします.入力フォーマット入力第1行は、マトリクスの行と列を表す2つの200を超えない正の整数m,nである.次に、m行の各行n個の整数は、この行列を表す.

#include
using namespace std;

const int MAXN = 202;
int a[MAXN][MAXN];
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            scanf("%d",&a[i][j]);
        }
    }
    int l=0,r=m-1,t=0,d=n-1;
    vector<int> ans;
    while(l<=r&&t<=d){
        for(int i=t;i<=d;++i)ans.push_back(a[i][l]);
        l++;
        if(ans.size()==n*m)break;
        for(int i=l;i<=r;++i)ans.push_back(a[d][i]);
        d--;
        if(ans.size()==n*m)break;
        for(int i=d;i>=t;--i)ans.push_back(a[i][r]);
        r--;
        if(ans.size()==n*m)break;
        for(int i=r;i>=l;--i)ans.push_back(a[t][i]);
        t++;
        if(ans.size()==n*m)break;
    }
    for(int i=0;i<ans.size()-1;++i)printf("%d ",ans[i]);
    printf("%d",ans[ans.size()-1]);
}

亀とウサギの競走予測

この世界には様々なウサギとカメがいるが、研究によると、すべてのウサギとカメには共通の特徴がある--競走が好きだ.そこで世界の隅々で亀とウサギの試合が絶えず発生して、華さんはこれに興味を持って、そこで異なるウサギと亀の競走を研究することにしました.彼は、ウサギはカメより速く走っているが、よく知られている欠点がある--誇りに思って怠け者で、カメとの試合で、いずれかの秒が終わった後、ウサギが自分がtメートル以上リードしていることに気づくと、彼らは止まってs秒を休むことに気づいた.異なるウサギに対して、t、sの数値は異なるが、すべてのカメは一致している.ゴールまで止まらない.しかし、一部の試合はかなり長く、全行程を見るのに多くの時間がかかるが、華さんは試合が始まるたびにウサギと亀のデータを記録すれば、ウサギの速度v 1(毎秒ウサギがv 1メートル走ることができることを示す)、カメの速度v 2、ウサギに対応するt、s値、コースの長さlを記録すれば、試合の結果を予測できることを発見した.しかし、華さんは怠け者で、手作業で試合の結果を推測したくないので、清華大学のコンピュータ学部の高才生を見つけました.助けを求めて、入力した試合のデータv 1、v 2、t、s、lについて、試合の結果を予測するプログラムを書いてください.入力形式入力は1行のみで、5つの正の整数v 1,v 2,t,s,l(v 1,v 2<=100;t<=300;s<=10;l<=10000、v 1,v 2の公倍数)を含む

#include
using namespace std;

int main(){
    int v1,v2,t,s,l;
    scanf("%d%d%d%d%d",&v1,&v2,&t,&s,&l);
    int l1=0,l2=0;// ， 
    int flag=false;// 
    int d;// 
    int cnt=0;// 
    while(true){
        cnt++;
        if(flag){
            d++;
            if(d==s)flag=false;
        }else l1+=v1;
        l2+=v2;
        //printf("%d %d %d %d
",cnt,d,l1,l2);
        if(l1==l&&l1==l2){
            printf("D");
            break;
        }else if(l1==l){
            printf("R");
            break;
        }else if(l2==l){
            printf("T");
            break;
        }
        if(l1-l2>=t&&flag==false){
            flag=true;
            d=0;
        }
    }
    printf("
%d",cnt);
    return 0;
}

じかんへんかん

問題記述は、秒単位の時間tを与え、この時間を「::」の形式で表すことを要求する.時間を表し、分を表し、秒を表します.これらはすべて整数で、先頭のない「0」です.例えば、t=0であれば、出力は「0:0:0」である.t=3661の場合、「1:1:1」が出力される.入力フォーマット入力は1行のみで、整数t(0<=t<=86399)である.

#include
using namespace std;

int main(){
    int n;
    cin>>n;
    printf("%d:%d:%d",n/3600,n%3600/60,n%60);
    return 0;
}

文字列の比較

質問は、大文字または小文字のみからなる2つの文字列(長さは1～10)を指定します.これらの関係は、次の4つのいずれかです.1:2つの文字列の長さが等しくありません.例えばBeijingとHebei 2:2つの文字列は長さが等しいだけでなく、対応する位置の文字は完全に一致しています(大文字と小文字を区別します)、例えばBeijingとBeijing 3:2つの文字列の長さが等しく、対応する位置の文字は大文字と小文字を区別しない前提でのみ完全に一致します(つまり、状況2を満たしていません).たとえばbeijingとBEIjing 4:2つの文字列の長さは等しいが、大文字と小文字を区別しなくても2つの文字列を一致させることはできない.たとえばBeijingとNanjingプログラミングは,入力された2つの文字列間の関係がこの4つのクラスのどのクラスに属するかを判断し,属するクラスの番号を与える.入力フォーマットには2つの行が含まれています.各行は文字列です.

#include
using namespace std;

char toLower(char c){
    if(c<='Z')c+=32;
    return c;
}
int stringCmp(string &s1, string &s2){
    for(int i=0;i<s1.size();++i){
        if(toLower(s1[i])!=toLower(s2[i]))return 4;
    }
    return 3;
}

int main(){
    string s1,s2;
    cin>>s1>>s2;
    if(s1.size()!=s2.size())cout<<1;
    else{
        if(s1==s2)cout<<2;
        else cout<<stringCmp(s1,s2);
    }
    return 0;
}

FJの文字列

質問記述FJは砂盤にA 1=「A」A 2=「ABA」A 3=「ABACABA」A 4=「ABACABADABACABA」と書かれていますが...その法則を見つけてすべての数列ANを書くことができますか?入力フォーマットには、N≦26の数しかありません.

#include
using namespace std;

int main(){
    string s = "A";
    int n;
    cin>>n;
    for(int i=1;i<n;++i){
        s = s + char('A'+i)+s;
    }
    cout<<s;
}

ブログ参照

ブルーブリッジカップ練習(一)