2018級「プログラム設計基礎(B)II」期末試験(問題解)
16269 ワード
A[4522]-学位証
B[4519]-クイズゲーム
C [4517] - easy math problem
D[4516]-並んでご飯を買う
E[4520]-アーチェリーゲーム
F[4518]-小Dの碁盤
G[4521]-小Dの一連の数字
A学位証
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
周知のように、山東理工大学で学位証を取得するには一定の単位成績点が必要であるが、プログラム設計がますます重要になっているため、学校はいくつかのプログラム設計成績が非常に優秀であるが、総単位成績点が足りない学生にも学位証を取得させることにした.
学位証を取得するために必要な単位成績点xとプログラム設計の優秀な点数線yとn人の学生の成績情報が知られている.
学位証を取得できる学生の名前と学号を出力するプログラムを書くことができますか?
Input
1行目の数字nは、同級生の総数(n<=1000)を表す.
2行目からn行目はi番目の学生の単位成績点、プログラム設計成績、氏名と学号をそれぞれ入力し、スペースで区切り、単位成績点とプログラム設計成績はint範囲内であり、氏名と学号は11桁を超えない文字列である.
最後に学位証を取得するために必要な成績点xとプログラム設計優秀線y(1<=x,y<=1 e 9)を入力する.
Output
学位証を取得できる学生の名前と学号を入力順に出力します.
合格の定義は、総単位成績点が合格またはプログラム設計成績が優秀である.
Sample Input
3
50 50 goudan 18272727272
61 40 zhangsan 18110505050
50 80 lisi 1817272aaaa
60 70Sample Output
zhangsan 18110505050
lisi 1817272aaaa#include
using namespace std;
int main()
{
int a,i,b,c;
int n[1010],m[1010];
char s[1010][15],x[1010][15];
cin >> a;
for(i=1;i<=a;i++)
{
cin >> n[i] >> m[i] >> s[i] >> x[i];
}
cin >> b >> c;
for(i=1;i<=a;i++)
{
if(n[i]>b||m[i]>c)
{
cout << s[i] << " " << x[i] << endl;
}
}
return 0;
}
B当てゲーム
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
AliceとBobはクイズゲームをしています.ゲームのルールは以下の通りです.
未知の整数が1つしかないので、Aliceが推測する必要があります.Bobは事前にこの数を知っていました.
ゲームの中でBobは全部でAlice nに手がかりを提供したが、Aliceは推測の機会が一度しかなかった.
各手がかりはLとRの2つの整数からなり、推測する数がL以上であり、R以下であることを示す.
Aliceは十分頭がいいですが、一度に当てる確率はいくらなのか教えてほしいと思っています.
(データ保証BobがAliceに提供した手がかりはすべて正しい)
Input
1行目は、データのグループ数を表す正の整数Tを入力する.(1 <= T <= 100)
各グループは正の整数nを入力し始める.(1 <= n <= 100)
次にn行、各行に2つの整数LとRを入力します.(-100 <= L <= R <= 100)
Output
共T行を出力し、i行目はi組目のテストデータの答えを表す.
答えは点数の形(A/B)で表し、余分なスペースを出力しないように注意します.
Sample Input
3
1
-100 100
2
3 4
4 5
2
3 6
4 7Sample Output
1/201
1/1
1/3#include
using namespace std;
int main()
{
int a,i,b,x,y,t=0,mi,ma;
int n[110],m[110],s[110];
cin >> a;
while(a--)
{
mi=110;
ma=-110;
cin >> b;
if(b==1)
{
cin >> x >> y;
s[++t]=y-x+1;
}
else
{
for(i=1; i<=b; i++)
{
cin >> n[i] >> m[i];
}
for(i=1; i<=b; i++)
{
if(mam[i])
{
mi=m[i];
}
}
s[++t]=mi-ma+1;
}
}
for(i=1; i<=t; i++)
{
if(i==t)
{
cout << 1 << "/" << s[i];
}
else
{
cout << 1 << "/" << s[i] << endl;
}
}
return 0;
}
Ceasy math problem
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
1つの数nについて、次の2つの操作があります.
1つは1を減らすことで、aが必要です.
しかし、nがkで除去されれば、bを費やしてnをkで除算することもできる.
すみません、この数を1にするには最低いくらかかりますか?
Input
1行目の整数n(n<=1 e 5)
2行目の3つの正の整数は、それぞれa,b,k(0
出力整数は最小コストを表します.
Sample Input
10
1 2 2Sample Output
6#include
using namespace std;
int main()
{
long long int a,x,y,z,sum=0;
cin >> a;
cin >> x >> y >> z;
while(a>1)
{
if(a%z==0)
{
if((a-(a/z))*x>y)
{
a=a/z;
sum=sum+y;
}
else
{
a=a-1;
sum=sum+x;
}
}
else
{
a=a-1;
sum=sum+x;
}
}
cout << sum;
return 0;
} D列に並んでご飯を買う
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
理工大学の食堂に着いた人はかなり多くなったと言っても過言ではありませんが、そもそも並んでいるときに先に来る人は先に来るはずですが、実際の状況は違うかもしれません.一つの列については以下の2つの操作で構成されていることに気づきました.
1を入力すると、列の一番左を代表する学生が食事の操作を完了し、彼は親友と一緒に買うのを手伝うので、買った後、彼の番号と同じ親友を全部呼んで一緒に行きます.1を入力すると、列が空いていれば削除しません.すなわち、シーケンスが空でない場合、一番左の要素と番号が同じすべての要素がシーケンスから削除されます.そうでない場合、削除されません.
2を入力すると、代表番号bの学生は列に割り込んでご飯を買いたいと思っています.彼と番号aの学生は親友なので、彼は列の左から右への最初の番号aの学生の右に挿入します.もしチームの中にaの学生がいなければ、彼は悲しくて離れます.すなわち、キューの左から右への最初のaの後ろにbが挿入され、キューにaがなければ挿入されない.
操作のたびにキューが空かどうかを判断し、空であれば「EMPTY」を出力する必要があることに注意してください.
最後の行は、すべての操作後のシーケンスを出力します.
Input
最初の行の1つの数nは、初期時シーケンスの要素を表す(n<=1 e 5)
2行目のn個のint範囲の数は、最大1000個まで異なる.
3行目の1つの数mは、操作の回数を表す.(m<=1e5)
後のm行の各行の最初の数は、操作の種類を表す.
操作が2の場合は、a,bの2つの数を入力します.
Output
操作毎に、操作後キューが空の場合は「EMPTY」を出力します.
すべての操作が完了すると、最終的なシーケンスが出力されます.
(一番下に補足テストサンプルが提示されています)
Sample Input
6
1 1 4 3 1 2
3
2 4 5
1
1Sample Output
5 3 2Hint
補足サンプル:
input:
6 1 1 4 3 1 2 5 2 6 5 1 1 1 1
output:
EMPTY
#include
#include
using namespace std;
int n[1000010];
int main()
{
int a,i,b,c,x,y,j,t;
cin >> a;
for(i=1; i<=a; i++)
{
cin >> n[i];
}
cin >> b;
while(b--)
{
cin >> c;
if(c==1)
{
t=n[1];
for(i=a; i>0; i--)
{
if(n[i]==t)
{
for(j=i; j> x >> y;
for(i=1; i<=a; i++)
{
if(n[i]==x)
{
for(j=a; j>i; j--)
{
n[j+1]=n[j];
}
a++;
n[i+1]=y;
break;
}
}
}
if(a==0)
{
cout << "EMPTY" << endl;;
}
}
if(a!=0)
{
for(i=1; i<=a; i++)
{
if(i==a)
{
cout << n[i];
}
else
{
cout << n[i] << " ";
}
}
}
return 0;
} #include"bits/stdc++.h"
using namespace std;
#define New (node *)malloc(sizeof(node))
struct node
{
int data;
node *next;
};
int main()
{
int n;
cin>>n;
node *head=New;
node *p=head;
for(int i=1; i<=n; i++)
{
int x;
cin>>x;
node *t=New;
t->data=x;
t->next=0;
p->next=t;
p=t;
}
int m;
cin>>m;
while(m--)
{
int kd;
cin>>kd;
if(kd==1)
{
if(head->next == 0)
{
puts("EMPTY");
continue;
}
else
{
int x=head->next->data;
p=head;
node *p2=head->next;
while(p2)
{
if(p2->data != x)
{
p->next=p2;
p=p2;
}
p2=p2->next;
}
p->next=0;
if(head->next == 0)
{
puts("EMPTY");
continue;
}
}
}
else
{
p = head->next;
int l,r;
int flag=0;
cin >> l >> r;
for(; p; p=p->next)
{
if(p->data == l)
{
node *t=New;
t->data=r;
t->next=p->next;
p->next=t;
flag=1;
break;
}
}
if(head->next==0)
{
puts("EMPTY");
}
}
}
p=head->next;
for(; p; p=p->next)
{
cout << p->data << " ";
}
return 0;
}Eアーチェリーゲーム
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
アリスはアーチェリーゲームをしています.
現在アリスにはN本の異なる矢があり、それぞれの矢には攻撃力がある.
M個のモンスターがあり、それぞれのモンスターに生命値があり、モンスターを撃つと金貨が落ちる.
1本の矢につき最大1回、モンスターにつき最大1回攻撃されます.
また「簡単」のため、モンスターが金貨を落とす数はその生命値に等しい.
アリスに最大いくら金貨がもらえるか聞いてみます.
Input
入力データは3行です.
1行目には2つの正の整数NとMがあり、それぞれ矢の数と怪物の数を表す.(1 <= N <= 1000000, 1 <= M <= 1000000)
2行目にはN個の正の整数があり、i番目の数はi番目の矢の攻撃力を表す.(1<=攻撃力<=10000000)
3行目にはM個の正の整数があり、i番目の数はi番目のモンスターの生命値と落下金貨数を表す.(1<=生命値<=10000000)
友情のヒント:答えはintの範囲を超えます.長い整形long long(%lld)を使用して計算してください.
Output
Aliceが最大いくらの金貨を得ることができるかを示す整数を出力します.
Sample Input
5 5
1 4 5 7 9
2 10 8 6 4Sample Output
20きゅうそくれつ
#include
#include
using namespace std;
long long int n[1000010],m[1000010];
int main()
{
long long int a,b,i,j,sum=0;
cin >> a >> b;
for(i=1; i<=a; i++)
{
cin >> n[i];
}
for(i=1; i<=b; i++)
{
cin >> m[i];
}
sort(n+1,n+a+1);
sort(m+1,m+b+1);
for(i=a; i>0; i--)
{
for(j=b; j>0; j--)
{
if(n[i]>=m[j])
{
sum=sum+m[j];
b=j-1;
break;
}
}
}
cout << sum;
return 0;
} #include
#include
using namespace std;
long long int n[1000010],m[1000010];
void quick(long long int a[],int left,int right)
{
int x=a[left],i=left,j=right;
if(left>=right)
{
return;
}
while(i=x)
{
j--;
}
a[i]=a[j];
while(i> a >> b;
for(i=1; i<=a; i++)
{
cin >> n[i];
}
for(i=1; i<=b; i++)
{
cin >> m[i];
}
quick(n,1,a);
quick(m,1,b);
for(i=a; i>0; i--)
{
for(j=b; j>0; j--)
{
if(n[i]>=m[j])
{
sum=sum+m[j];
b=j-1;
break;
}
}
}
cout << sum;
return 0;
} F小Dの碁盤
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
小Dには不思議な碁盤があり、碁盤にはn行、m列がある.この碁盤はどうして不思議なのですか.この碁盤には魔法がかけられているため、小Dが呪文を唱えるたびに、碁盤の駒は隣接する上下左右の4つの格子に分裂し、分裂した後も元のものは消え、ある方向に格子(例えば最初の行に上の格子がない)がなければ、彼は上に分裂しない.今、Dさんは彼がk回の呪文を読んだ後、碁盤に今何個の駒があるか知りたいと思っています.注意:各格子には無数の駒を置くことができ、分裂した駒はもう一度呪文を唱えて駒を分裂し続けることができる.
Input
n,mと入力します.(2<=n<=20,2<=m<=20)は碁盤の行列を表す.
次にn行、各行m個の数字aij(0<=aij<=1)で、各数字はこの格子の初期を表すときにいくつかの駒がある.
次の行にk(1<=k<=10)を入力します.
Output
小Dがk回呪文を唱えた後、碁盤に今何個の駒があるかを示す数字を出力します.この数字はintの範囲内であることを保証します.
Sample Input
3 3
0 0 0
0 1 0
0 0 0
2Sample Output
12Hint
例では、呪文を1回唱えた後の碁盤の場合:
0 1 0
1 0 1
0 1 0
もう一度読み返すと、次のようになります.
2 0 2
0 4 0
2 0 2
最終盤には12個の駒がある.
#include
#include
using namespace std;
int main()
{
int a,b,i,j,c,sum=0;
int n[21][21],m[21][21];
cin >> a >> b;
for(i=1; i<=a; i++)
{
for(j=1; j<=b; j++)
{
cin >> n[i][j];
m[i][j]=n[i][j];
}
}
cin >> c;
while(c--)
{
for(i=1; i<=a; i++)
{
for(j=1; j<=b; j++)
{
if(i==1&&j==1)
{
n[i][j]=n[i][j]+m[i+1][j]+m[i][j+1];
}
else if(i==1&&j==b)
{
n[i][j]=n[i][j]+m[i][j-1]+m[i+1][j];
}
else if(i==a&&j==1)
{
n[i][j]=n[i][j]+m[i-1][j]+m[i][j+1];
}
else if(i==a&&j==b)
{
n[i][j]=n[i][j]+m[i-1][j]+m[i][j-1];
}
else if(i!=1&&i!=a&&j==1)
{
n[i][j]=n[i][j]+m[i-1][j]+m[i][j+1]+m[i+1][j];
}
else if(i!=1&&i!=a&&j==b)
{
n[i][j]=n[i][j]+m[i-1][j]+m[i][j-1]+m[i+1][j];
}
else if(j!=1&&j!=b&&i==1)
{
n[i][j]=n[i][j]+m[i][j-1]+m[i][j+1]+m[i+1][j];
}
else if(j!=1&&j!=b&&i==a)
{
n[i][j]=n[i][j]+m[i][j-1]+m[i][j+1]+m[i-1][j];
}
else
{
n[i][j]=n[i][j]+m[i][j-1]+m[i][j+1]+m[i-1][j]+m[i+1][j];
}
}
}
for(i=1; i<=a; i++)
{
for(j=1; j<=b; j++)
{
n[i][j]=n[i][j]-m[i][j];
m[i][j]=n[i][j];
}
}
}
for(i=1; i<=a; i++)
{
for(j=1; j<=b; j++)
{
if(n[i][j]!=0)
{
sum=sum+n[i][j];
}
}
}
cout << sum;
return 0;
} #include
int dp[2][20][20];
int main()
{
int n,m,q;
scanf("%d%d",&n,&m);
for(int i=0; i G小Dの一連の数字
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
小さいDは紙の上で勝手に2列の数字を書いて、“23333333”,“0123456789”.1番目の列には7つの重複する隣接する数字が含まれ、2番目の列には隣接する重複する数字が含まれていません.小さいDは第1類の列が好きで、しかし彼は要求を下げて、1列の数字の中で2つの繰り返しの隣接する数字を超える限り、小さいDはこの数字が好きです.今彼は知りたいと思って、長さnのすべての数字の列、最大で何個の列が彼に好きになることができますか?しかし、Dさんは数学のバカなので、この問題を解決してください.
Input
Nを入力します(3=
Output
小さいDが一番好きなシリアル数を表す整数を出力します.
Sample Input
3Sample Output
10Hint
例では1112223334445556667778899000であり、この10個の列は小Dに好まれている.
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
int n;
ll dp[20][20][20][20];
int dfs(int x,int ll,int l,int tr)
{
if(x>n)
{
if(tr)
{
return 1;
}
return 0;
}
if(~dp[x][ll][l][tr])
{
return dp[x][ll][l][tr];
}
long long res=0;
for(int i=0; i<=9; i++)
{
if(i==l && l==ll)
{
res += dfs(x+1,l,i,1);
}
else
{
res += dfs(x+1,l,i,tr);
}
}
return dp[x][ll][l][tr] = res;
}
int main()
{
cin >> n;
memset(dp,-1,sizeof dp);
cout<#include
int dp[50][50];
int main()
{
int n,j,i;
for(i=0; i<10; i++)
{
dp[1][i]=1;
}
scanf("%d",&n);
for(i=2; i<=n; i++)
{
for(j=0; j<10; j++)
{
for(int k=0; k<10; k++)
{
if(j!=k)
{
dp[i][j]+=dp[i-1][k]+dp[i-1][k+10];
}
}
dp[i][j+10]=dp[i-1][j];
dp[i][j+20]=dp[i-1][j+10]+dp[i-1][j+20]*10;
}
}
int ans=0;
for(int i=0; i<10; i++)
{
ans+=dp[n][i+20];
}
printf("%d
",ans);
}