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

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

チップテスト

分解素因数

行列乗算

行列乗方

おつり

審美課

参考ブログ

チップテスト

問題の説明はn(2≦n≦20)ブロックチップがあり、良いチップと悪いチップがあり、良いチップが悪いチップより多いことが知られている.各チップは他のチップをテストするために使用できます.他のチップをチップでテストすると、テストされたチップが良いか悪いかを正確に与えることができます.一方、悪いチップで他のチップをテストすると、良いか悪いかのテスト結果がランダムに与えられます(すなわち、この結果は被テストチップの実際の良し悪しとは関係ありません).すべてのチップのテスト結果を示し、どのチップが良いチップなのかを尋ねます.入力フォーマット入力データの第1の動作は、チップ個数を表す整数nである.2行目からn+1行目n*nのテーブルで、1行n個のデータが表示されます.表中の各データは0または1であり、このn行のi行目j列目(1≦i,j≦n)のデータは、iブロック目チップでjブロック目チップをテストしたときに得られたテスト結果を示し、1は良い、0は悪い、i=jの場合は一律に1(このチップが自分に対するテスト結果を示さない.コアシートは自分に対してテストできない)である.

#include
using namespace std;
const int MAXN = 22;
int g[MAXN][MAXN];
int a[MAXN];


int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j)scanf("%d",&g[i][j]);
    }
    int t = 1<<n;// 2 
    int cnt = 0;// 1 
    bool flag = false;// 
    for(int i=1;i<t;++i){
        for(int j=0;j<n;++j)a[j]=(i>>j)&1;
        cnt=0;
        for(int j=0;j<n;++j)if(a[j])cnt++;
        if(cnt<=n-cnt)continue;// 
        flag = true;// 
        for(int j=0;j<n;++j){
            if(!a[j])continue;// 
            for(int t=0;t<n;++t)if(g[j][t]!=a[t]){flag=false;break;}
            if(!flag)break;
        }
        if(flag){
            int cntt=1;
            for(int j=0;j<n;++j){
                if(a[j]){
                    if(cntt<cnt)printf("%d ",j+1);
                    else printf("%d",j+1);
                    cntt++;
                }
            }
            break;
        }
    }
    return 0;
}

ぶんかいしつりょう

問題記述は区間[a,b]におけるすべての整数の質量係数分解を求める.入力フォーマットは、2つの整数a,bを入力します.サンプル入力3 10サンプル出力3=3 4=2*2 5=5 6=2*3 7=7=2*2*2 9=3*3 10=2*5

#include
using namespace std;
const int MAXN = 105;
bool vis[MAXN];
int  prime[MAXN],_index=0;
void EuerPrime(){
    for (int i=2; i<MAXN; i++)
    {
        if (!vis[i]) prime[_index++]=i;
        for(int j=0; j<_index&&prime[j]*i<MAXN; j++)
        {
            vis[prime[j]*i]=1;
            if(i%prime[j]==0)break;
        }
    }
}// 

int main(){
    EuerPrime();
    int a,b,d,j,cnt;
    scanf("%d%d",&a,&b);
    for(int i=a;i<=b;++i){
        d = i;
        cnt = 0;
        printf("%d=",d);
        for(j=0;j<_index;++j){
            if(d<=prime[j])break;
            if(d%prime[j])continue;
            while(d%prime[j]==0){
                if(cnt)printf("*");
                printf("%d",prime[j]);
                cnt++;
                d/=prime[j];
            }
        }
        if(cnt&&d!=1)printf("*");
        if(d!=1)printf("%d",d);
        printf("
");
    }
}

マトリックス乗算

質問は1つのN次行列Aを記述し、出力AのM次べき乗(Mは非負の整数)は、例えば、A=1 2 3 4 Aの2次べき乗7 10 10 15 22入力フォーマットの第1行は正の整数N、M(1<=N<=30、0<=M<=5)であり、行列Aの次数と要求されるべき乗数が続くN行を表し、各行Nの絶対値が10を超えない非負の整数であり、行列Aの値を記述する

#include 
using  namespace std;
typedef long long ll;
const int MAXN = 32;
int tmp[MAXN][MAXN]={0};// 
void matrixcopy(int a[][MAXN],int b[][MAXN],int n){
		for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)a[i][j]=b[i][j];
}// B A

//  A(n*n)* B(n*n), A 
void mul(int a[][MAXN],int b[][MAXN],int n){
    int tmp[MAXN][MAXN]={0};// 
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			for(int k=0;k<n;k++)
				tmp[i][j]+=a[i][k]*b[k][j];
	matrixcopy(a,tmp,n);
}

void matrixquickpow(int a[][MAXN],int b,int n){
    int ans[MAXN][MAXN]={0};
	for(int i=0;i<n;i++)ans[i][i]=1;// 
	while (b)
	{
		if(b&1)mul(ans,a,n);
		mul(a,a,n);
		b>>=1;
	}
	matrixcopy(a,ans,n);
}// 
int t[MAXN][MAXN];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j)scanf("%d",&t[i][j]);
    }
    matrixquickpow(t,m,n);
    for(int i=0;i<n;++i){
        for(int j=0;j<n-1;++j)printf("%d ",t[i][j]);
        printf("%d
",t[i][n-1]);
    }
}

マトリックス乗

問題は、与えられたマトリクスA、非負の整数b、および正の整数mを記述し、Aのb次方除mの残数を求める.一方のnxnのマトリクスがmの余剰を除いて得られるのは依然としてnxnのマトリクスであり、このマトリクスの各要素は元のマトリクスに対応する位置の数がmの余剰を除いたものである.この問題を計算するには,Aをb回連乗し,毎回mに余剰を求めることができるが,この方法は特に遅く,bが大きいと使用できない.以下に、比較的速いアルゴリズム(A^bでAのb次数を表す):b=0であれば、A^b%m=I%mである.ここで、Iは単位行列を表す.bが偶数であれば、Ab%m=(A(b/2)%m)^2%m、すなわち、Aをb/2乗してmを余剰とし、その後、平方してmを余剰とする.bが奇数であれば、Ab%m=(A(b-1)%m)*a%m、すなわち、Aにb-1を乗じてmに残差を求め、その後、Aを乗じてmに残差を求める.この方法は速度が速いので,A^b%mを計算し,Aは2 x 2の行列であり,mは10000以下である.入力フォーマット入力第1行は、マトリクスAの2つの整数b,m、第2行および第3行の各行の2つの整数を含む.

#include 
using  namespace std;
typedef long long ll;
const int MAXN = 32;
int tmp[MAXN][MAXN]={0};// 
void matrixcopy(int a[][MAXN],int b[][MAXN],int n){
		for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)a[i][j]=b[i][j];
}// B A

//  A(n*n)* B(n*n), A 
void mul(int a[][MAXN],int b[][MAXN],int n,int m){
    int tmp[MAXN][MAXN]={0};// 
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			for(int k=0;k<n;k++)
				tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%m;
	matrixcopy(a,tmp,n);
}

void matrixquickpow(int a[][MAXN],int b,int n,int m){
    int ans[MAXN][MAXN]={0};
	for(int i=0;i<n;i++)ans[i][i]=1;// 
	while (b)
	{
		if(b&1)mul(ans,a,n,m);
		mul(a,a,n,m);
		b>>=1;
	}
	matrixcopy(a,ans,n);
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j)a[i][j]%=m;// b=0
    }
}// 
int t[MAXN][MAXN];
int main(){
    int n=2,b,m;
    scanf("%d%d",&b,&m);
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j)scanf("%d",&t[i][j]);
    }
    matrixquickpow(t,b,n,m);
    for(int i=0;i<n;++i){
        for(int j=0;j<n-1;++j)printf("%d ",t[i][j]);
        printf("%d
",t[i][n-1]);
    }
}

小銭をさがす

問題はn人が食堂に並んで海北鶏ご飯を買っているということです.海北鶏ご飯は1人前25元かかります.不思議なことに、一人一人の手には紙幣が1枚しかありません(1枚の紙幣の額面は25、50、100元です)、食堂のおばさんは最初小銭がありませんでした.すみません、食堂のおばさんはすべての人におつりを探してもらえますか(食堂のおばさんが十分に頭がいいと仮定します)フォーマットの1行目の整数nを入力して、列に並んでいる人数を表します.次にn個の整数a[1],a[2],...,a[n].a[i]i番目の学生が手に持っている紙幣の価値(iが小さいほど、チーム内で上位になる)を示す出力フォーマット出力YESまたはNO

#include 
using  namespace std;

int main(){
    int n,a=0,b=0,d;// ，25，50
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%d",&d);
        if(d==25)a++;
        else if(d==50){
            a--;
            if(a<0){
                printf("NO");
                return 0;
            }
            b++;
        }else{
            if(b==0){
                a-=2;
            }else {
                a--;
                b--;
            }
            if(a<0){
                printf("NO");
                return 0;
            }
        }
    }
    printf("YES");
    return 0;
}

審美の授業

問題は「審美の過程」の授業でn人の学生がいて、かっこいい先生はm絵を展示して、その中にゴッホの作品があって、ほかのものはすべて5歳の子供の手から出ました.先生は学生たちにどの絵の作者がゴッホなのかを見分けるように頼んだが、先生自身は答えがなかった.これらの絵は子供が描いたように見えるからだ.先生は、学生に与えた答えがどれだけ逆なのか知りたいだけだ.そうすれば、彼はこのデータで皇帝の新しい服を着た抽象芸術を暴くことができる(かっこいい先生を支持する).答えが正反対とは、絵ごとに判断が逆であることを意味します.フォーマットの1行目の2つの数nとmを入力し、学生数と図画数を表す.次はn*mの01行列Aです.aij=0なら、学生iがj番目の絵が子供が描いたと思っていることを示します.aij=1なら、学生iがj番目の絵がゴッホが描いたと思っていることを示します.

#include 
using namespace std;
int x[1<<20];
int main()// 2 
{
    int n,m,d,ans=0;
    scanf("%d%d",&n,&m); 
    const int N =(1<<m)-1;
    for(int i=0;i<n;++i){
        int sum1=0,sum2=0;
        for(int j=0;j<m;++j){
            scanf("%d",&d);
            sum1=(sum1<<1)+d;// 
        }
        x[sum1]++;
        ans+=x[sum1^N];
    }
   printf("%d
",ans);
}

ブログ参照

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

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