2016第7回ブルーブリッジカップC/C++A組問題解
9382 ワード
第一題
ネットユーザーの年齢
ある君は新しいネットユーザーを知っている.年齢を聞くと、ネットユーザーは「私の年齢は2桁で、息子より27歳年上です.もし私の年齢の2桁の数字を交換すれば、ちょうど息子の年齢です」と話しています.
計算してください:ネットユーザーの年齢は全部で何種類の可能性がありますか?
ヒント:30歳はその一つの可能性ですよ.
可能性を示す種数を記入してください.注意:あなたが提出したのは整数で、余分な内容や説明的な文字を記入しないでください.
7
第二題
誕生日キャンドル
ある君はある年から年に一度誕生日パーティーを開き、その度に年齢と同じ本数のろうそくを消していた.
今から計算すると、彼は全部で236本のろうそくを消した.
すみません、彼は何歳から誕生日パーティーをしましたか?
彼が誕生日パーティーを始めた年齢数を記入してください.注意:あなたが提出したのは整数で、余分な内容や説明的な文字を記入しないでください.
26
第三題
グリッド数
下記の10個の格子+--+--+--+||||+--+--+--+--+||||+--+--+--+--+--+|||+--+--+--+--+--+--+--+
(表示に問題があれば【図1.jpg】参照)
0~9の数字を記入します.要求:連続する2つの数字は隣接できません.(左右、上下、対角ともに隣接)
全部で何種類の可能な記入案がありますか?
シナリオ数を示す整数を記入してください.注意:あなたが提出したのは整数で、余分な内容や説明的な文字を記入しないでください.1580
#include
#include
using namespace std;
int a[3][4];
bool geted[10]={false};
int cnt=0;
bool side(int x,int y)
{
for(int i=x-1;i<=x+1;i++)
{
for(int j=y-1;j<=y+1;j++)
{
if(i<0||i>2||j<0||j>3 || (i==x&&j==y))
continue;
else if(abs(a[x][y]-a[i][j])<=1)
return false;
}
}
return true;
}
void dfs(int x,int y)
{
if(x==2&&y==3)
{
cnt++;
return;
}
if(y>3)
{//
x+=1;
y=0;
}
for(int i=0;i<10;i++)
{
if(geted[i]==false)
{
geted[i]=true;
a[x][y]=i;
if(side(x,y)==true)
{
dfs(x,y+1);
}
geted[i]=false;
a[x][y]=-4;
}
}
return;
}
int main()
{
for(int i=0;i<3;i++)
{
for(int j=0;j<4;j++)
{
a[i][j]=-4;
}
}
dfs(0,1);
cout< 第四題
クイックソート
ソートは様々な場面でよく使われます.高速ソートは非常によく使われる効率的なアルゴリズムです.
まず「スケール」を選択し、キュー全体をふるいにかけて、左側の要素がそれより大きくなく、右側の要素がそれより小さくないことを保証します.
これにより,並べ替え問題は2つのサブ区間に分割される.サブ区間を別々に並べ替えるといいです.
次のコードは実装です.スクライブ部分に欠けているコードを分析して記入してください.
#include
void swap(int a[], int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
int partition(int a[], int p, int r) { int i = p; int j = r + 1; int x = a[p]; while(1){ while(i while(a[--j]>x); if(i>=j) break; swap(a,i,j); } swap(a,p,j); return j; }
void quicksort(int a[], int p, int r) { if(p int q = partition(a,p,r); quicksort(a,p,q-1); quicksort(a,q+1,r); } } int main() { int i; int a[] = {5,13,6,24,2,8,19,27,6,12,1,17}; int N = 12; quicksort(a, 0, N-1); for(i=0; i printf(""); return 0; }
注意:欠落した内容だけを記入し、問題面の既存のコードや説明的な文字を書かないでください.
第五題
削除
次のコードは、整数のバイナリで表される右端の連続する1をすべて0にします.最後のビットが0であれば、元の数字は変わりません.
コードのテストデータを使用する場合は、次のように出力する必要があります.
プログラムをよく読んで、線の部分に欠けているコードを記入してください.
#include
void f(int x) { int i; for(i=0; i<32; i++) printf("%d", (x>>(31-i))&1); printf(" "); x =x&(x+1); for(i=0; i<32; i++) printf("%d", (x>>(31-i))&1); printf(""); }
int main() { f(103); f(12); return 0; }
注意:欠落した内容だけを記入し、問題面の既存のコードや説明的な文字を書かないでください.
第六題
冬休みの宿題
今の小学校の数学の問題もそんなに面白くありません.この冬休みの宿題を見てください.
□ + □ = □ □ - □ = □ □ × □=□÷□=□(表示されない場合は【図1.jpg】参照)各ブロックは、1~13のいずれかの数字を表すが、繰り返すことはできない.たとえば、6+7=13 9-8=1 3*4=12 10/2=5
および:7+6=13 9-8=1 3*4=12 10/2=5
二つの解法でも.(加算、乗算交換律で異なる案を計算)全部で何種類の案を見つけましたか.
シナリオ数を示す整数を記入してください.注意:あなたが提出したのは整数で、余分な内容や説明的な文字を記入しないでください.64
#include
using namespace std;
bool geted[14]={false};
int cnt=0;
void dfs(int row)
{
if(row==5)
{
cnt++;
return;
}
for(int i=1;i<=13;i++)
{
for(int j=1;j 第七題
切手を切る
【図1.jpg】のように、12枚の干支がつながっている切手があります.今、中から5枚切ってください.連続していなければなりません.例えば、【図2.jpg】、【図3.jpg】では、ピンク色の部分が合格の切り取りです.(写真を出すのがおっくうになった)
全部で何種類のカット方法があるか計算してください.
シナリオ数を示す整数を記入してください.
116(この問題は私は暴力的で、後でdfs解法を見て、実はすべて良い感じがして、暴力なら細部に注意しなければなりません)
#include
#include
using namespace std;
int b[5];
int cnt=0;
void test()
{
int connect=0;
for(int i=0;i<5;i++)
{
int num=0;
int row1=b[i]/4;
int col1=b[i]%4;
for(int j=0;j<5;j++)
{// b[i] ，
if(i==j)
continue;
int row2=b[j]/4;
int col2=b[j]%4;
if((row1==row2 && abs(col1-col2)==1) || (col1==col2 && abs(row1-row2)==1))
{
num++;
}
}
if(num==0)
return;
connect+=num;
}
if(connect>6)// 3*2=6
cnt++;
return;
}
int main()
{
for(int i1=0;i1<=11-4;i1++)
{
b[0]=i1;
for(int i2=i1+1;i2<=11-3;i2++)
{
b[1]=i2;
for(int i3=i2+1;i3<=11-2;i3++)
{
b[2]=i3;
for(int i4=i3+1;i4<=11-1;i4++)
{
b[3]=i4;
for(int i5=i4+1;i5<=11;i5++)
{
b[4]=i5;
test();
}
}
}
}
}
cout< 第八題
四平方和
四平方和の定理は、ラグランジュの定理とも呼ばれます.各正の整数は、最大4つの正の整数の平方和として表すことができます.0を含めると、ちょうど4つの数の平方和として表すことができます.
例えば、5=0^2+0^2+1^2+2^2+2+2^7=1^2+1^2+1^2+2^2(^記号は乗の意味を表す)
与えられた正の整数に対して、複数の二乗和の表現が存在する可能性がある.4つの数をソートする必要があります:0<=a<=b<=c<=dで、すべての可能な表現に対してa,b,c,dを結合主キー昇順に並べて、最後に最初の表現を出力します.
プログラム入力が正の整数N(N<5000,000)になるには、4つの非負の整数を出力し、小さいものから大きいものに並べ替え、中間をスペースで分ける必要がある.
たとえば、入力:5の場合、プログラムは0 0 1 2を出力する必要があります.
例えば、入力:12の場合、プログラム出力:0 2 2 2
また、例えば、入力:773535では、プログラム出力:1 1 267 838
リソース約定:ピークメモリ消費量<256 M CPU消費量<3000 ms
要求通りに出力してください.ヘビを描いて印刷しないでください.「入力してください.」と入力します.
タイムアウトを防ぐには
#include
#include
#include 第九題
パスワードの脱落
X星の考古学者は古代に残された暗号を発見した.これらの暗号はA,B,C,Dの4種類の植物の種子からなる配列である.よく分析すると、これらの暗号列は当初前後対称であるべきである(すなわち、私たちが言ったミラー列である).年代が古いため、多くの種が脱落し、ミラーの特徴を失う可能性があります.
あなたの任務は:今見ている暗号列を与えて、当初の状態から、少なくとも何個の種が抜けてこそ、今の姿になる可能性があるかを計算することです.
現在表示されている暗号列(長さ1000以下)に正の整数を出力する必要があることを示す行を入力し、少なくともどれだけのシードが脱落したかを示します.
例えば、入力:ABCBAはプログラム出力:0
例えば、入力:ABDCBABC則プログラム出力:3
リソース約定:ピークメモリ消費<256 M CPU消費<1000 ms
#include
#include
using namespace std;
int dp[1010];//
int main()
{
string a,b;
cin>>a;
b=a;
reverse(b.begin(),b.end());
for(int i=0;i 第十題
最大スケール(Max Scale)
X星のあるグランプリにM級の奨励金が設けられた.各レベルのボーナスは正の整数です.また、隣接する2つのレベル間の割合は固定値である.つまり、すべてのレベルのボーナス数が等比数列を構成している.例えば、16,24,36,54の等比は、3/2である
今、私たちはランダムにいくつかの受賞者のボーナス数を調査しました.これに基づいて可能な最大の等比値を推定してください.
入力形式:第1行数N(0第2行N個の正の整数Xi(Xi<1,000,000,000,000,000,000,000,000)をスペースで区切る.各整数は、調査した誰かのボーナス額を表します.
要求出力:A/Bのような形の点数、A、Bの相互質を要求する.可能な最大比例係数を表す
テストデータは、入力フォーマットが正しく、最大割合が存在することを保証します.
たとえば、入力:3 1250 200 32
プログラム出力:25/4
例えば、入力:4 3125 32 32 200
プログラム出力:5/2
たとえば、3 549755813888 524288と入力します.
プログラム出力すべき:4/1
分析:この問題は半分やっただけで、考えが簡単すぎることに気づいた.答えが5/2であると仮定すると,入力データを大きさで並べ替えた後,隣接する2つの数3125200に対して比を求めると,125/8が5^3/2^3であり,分子分母の最大公因数を計算し,得られた結果が答えである.
しかし、ここには分子や分母の最大公因数を計算することができず、転がって除去して最大公因数を得ることができないところがあります.どうせ私がやったときは頭が回転できませんでした.その後、他の人の解法を見て、gcd 1の関数です.Emmmたぶん私は数学の思考がなかったでしょう.
#include
#include
#include