「AOJ161～170」の編集履歴（バックアップ）一覧に戻る
AOJ161～170 - (2012/07/11 (水) 16:41:59) のソース
----
*0161 Sport Meet
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0161
スポーツ大会の合計タイムから1位のチーム2位のチーム、びりより一つ上のチームを表示せよという問題。
簡単な問題です。
解法
100万チームのデータを毎回確保するのは処理速度的にどうかと思うので最初に確保しておくくらいです。
後はデータを読み込んでソートするだけで答えが出ます。
#include<stdio.h>
#include<set>
#include <algorithm>
struct team{
int no,time;
bool operator<(const team t)const {
return time<t.time;
}
};
team teams[1000002];
void setData(int n){
int m1,s1,m2,s2,m3,s3,m4,s4;
team t;
for(int i=0;i<n;i++){
scanf("%d %d %d %d %d %d %d %d %d",&t.no,&m1,&s1,&m2,&s2,&m3,&s3,&m4,&s4);
t.time=60*(m1+m2+m3+m4)+(s1+s2+s3+s4);
teams[i]=t;
}
std::sort(teams,teams+n);
printf("%d\n%d\n%d\n",teams[0].no,teams[1].no,teams[n-2].no);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0) break;
setData(n);
}
}
----
*0162 Hamming Numbers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0162
ｍ以上ｎ以下の整数の間にあるハミング数(1、2、3、5の掛け算組み合わせで表現できる数)の個数を求めよという問題。
解法
与えられた数をハミング数かどうか判断していると時間がかかります。
最初にハミング数を生成して下から数えていくことで計算量を落とします。
この時生成ルールに素数の一意分解を適用して重複計算をなくします。
#include<stdio.h>
#include<string.h>
const int max=1000001;
int sums[max];
int ts[3]={2,3,5};
void saiki(int num,int p){
if(num>=max) return;
sums[num]=1;
for(int i=p;i<3;i++){
saiki(num*ts[i],i);
}
}
void setData(){
memset(sums,0,max);
saiki(1,0);
for(int i=1;i<max;i++){
sums[i]+=sums[i-1];
}
}
int main(){
setData();
int m,n,t;
while(1){
scanf("%d",&m);
if(m==0) break;
scanf("%d",&n);
printf("%d\n",sums[n]-sums[m-1]);
}
}
----
*0163 Highway Toll
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0163
ハイウェイを通った車の通行料金を算出する問題です。
半額時間に40ｋｍ以下の道を通った車は半額50円切り上げで出力します。
解法
料金マトリックスを作って条件を満たすか調べるだけです。
競技プログラムなので1300円以上なら40ｋｍ以上走っているということを利用してコードを短縮します。
実務では距離情報のマトリックスも作っておくべきでしょう。
#include <stdio.h>
int main()
{
int s,g,sTime,eTime;
int map[7][7]={ {0,300,500,600,700,1350,1650},
{300,0,350,450,600,1150,1500},
{500,350,0,250,400,1000,1350},
{600,450,250,0,250,850,1300},
{700,600,400,250,0,600,1150},
{1350,1150,1000,850,600,0,500},
{1650,1500,1350,1300,1150,500,0}};
//1300円より大きいなら40ｋｍ以上走ってることになる
while(1){
int t1,t2;
scanf("%d",&s);
if(s==0) break;
scanf("%d %d",&t1,&t2);
sTime=t1*100+t2;
scanf("%d",&g);
scanf("%d %d",&t1,&t2);
eTime=t1*100+t2;
s--;g--;
if(map[s][g]>1300){
printf("%d\n",map[s][g]);
}else{
if((1930>=sTime && sTime>=1730) || (1930>=eTime && eTime>=1730)){
t1=map[s][g]/2;
if(t1%50!=0){
t1=t1/50*50+50;
}else{
t1=t1/50*50;
}
printf("%d\n",t1);
}else{
printf("%d\n",map[s][g]);
}
}
}
}
----
*0164 Ohajiki Game
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0164
二人でおはじきゲームをします。
32個のおはじきを交互に取りのぞき最後に残った一個を取った方が負けになります。
おはじきを取るときのパタンが提示されるので、その方法で取った時の試合の経過を提示してくださいという問題。
*解法
簡単な問題なので書いてある通りに実装するだけです。
最後に0を出力するのを忘れると不正解となるので注意してください。
#include<stdio.h>
int main(){
int c[26],n,m,p;
while(1){
scanf("%d",&n);
if(n==0) break;
for(int i=0;i<n;i++){
scanf("%d",&c[i]);
}
m=32;
p=0;
while(1){
m=m-(m-1)%5;
printf("%d\n",m);
if(m==1) break;
m=m-c[p];
printf("%d\n",m);
p=(p+1)%n;
}
printf("0\n");
}
}
----
*0165 Lottery
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0165
宝くじの総賞金支払い額を求める問題。
宝くじ一枚は一サブプライムで当選番号はｐとｍの二つの整数の組であらわされ、当選額はp-m～p+mの間にある素数の数ｎで決まり、当選者にはｎサブプライムが支払われます。
当選金のうち1サブプライムは宝くじの購入金額から戻ってきます。
残りを宝くじがわが支払うのですが、宝くじ側がいくら支払うことになるかを計算する問題です。
当たりに素数が含まれてない場合は宝くじ側に一サブプライムがプールされます。
解法
素数をエラトステネスの篩で求めて、下から素数の数が何個あるか数えてsoに入れていきます。
後は当選番号から素数の数を求めて差分を計算するだけです。
#include<stdio.h>
#include<string.h>
const int max=1000001;
int so[max];
void setSo(){
memset(so,0,max*4);
so[2]=1;
for(int i=3;i<1001;i+=2){
if(so[i]==1) continue;
for(int j=i*3;j<max;j+=i*2){
so[j]=1;
}
}
for(int i=3;i<max;i++){
so[i]=(i&1)==0?so[i-1]:!so[i]+so[i-1];
}
}
int main(){
setSo();
int n,p,m,down,up,chargeMoney,temp;
while(1){
scanf("%d",&n);
if(n==0) break;
chargeMoney=0;
for(int i=0;i<n;i++){
scanf("%d %d",&p,&m);
down=p-m-1;
up=p+m;
if(down<0) down=0;
if(up>=max) up=max-1;
chargeMoney+=so[up]-so[down]-1;
}
printf("%d\n",chargeMoney);
}
}
----
*0166 Area of Polygon
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0166
同一サイズの円周に内接する多角形の情報が2つ与えられるので、どちらの多角形が大きいか判断せよという問題。
解法
一つの三角形はa*b*sin(θ)/2という式でもとまることを利用して計算します。
円のサイズが指定されてないので単位円と仮定し、計算誤差が生まれる可能性を考慮して差分0.000001以下なら同じ値と判断します。
#include<stdio.h>
#include<math.h>
double calcS(int m){
double r,S=0,sum=360;
for(int i=0;i<m-1;i++){
scanf("%lf",&r);
sum-=r;
S+=sin(r/180.0*M_PI)/2.0;
}
S+=sin(sum/180.0*M_PI)/2.0;
return S;
}
int main(){
int m,n;
double s1,s2;
while(1){
scanf("%d",&m);
s1=calcS(m);
if(m==0) break;
scanf("%d",&n);
s2=calcS(n);
if(fabs(s1-s2)<0.000001){
printf("0\n");
}else if(s1<s2){
printf("2\n");
}else{
printf("1\n");
}
}
}
----
*0167 Bubble Sort
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0167
数列が与えられるのでバブルソートでソートした時何回数列が入れ替えられるのか回数を答える問題。
解法
数列のサイズが小さいのでそのままシミュレートして解きます。
バブルソートも挿入ソートも計算量が同じということを利用してコードを短縮して解きます。
賢い人ならこの問題はより高度な方法で解くようです。
調べてみるのもよいでしょう。
#include<stdio.h>
#include <algorithm>
void sort(int n){
int d[101],count=0;
for(int i=0;i<n;i++){
scanf("%d",&d[i]);
for(int j=i;j>0;j--){
if(d[j]<d[j-1]){
std::swap(d[j],d[j-1]);
count++;
}
}
}
printf("%d\n",count);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0) break;
sort(n);
}
}
----
*0168 Kannondou
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0168
ｎ段の階段を1段ずつ、一段飛ばし、2段飛ばしを組み合わせて登った時何通りの登り方があるか、全ての登り方を制覇するのに一日10通りずつ登ったら何年かかるを答えよという問題。
*解法
メモ化計算という言葉さえ知っていれば鼻歌交じりで解ける簡単問題です。
こういう簡単な問題は気楽に解ける分解いてて楽しいものです。
#include<stdio.h>
int main(){
int d[32];
d[1]=1;
d[2]=2;
d[3]=4;
for(int i=4;i<31;i++){
d[i]=d[i-1]+d[i-2]+d[i-3];
}
int n;
while(1){
scanf("%d",&n);
if(n==0) break;
printf("%d\n",d[n]/3650+(d[n]%3650==0?0:1));
}
}
----
*0169 Blackjack
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0169
ブラックジャックのカードが渡されるので得点を計算して出力せよという問題です。
注意点は1を1点とみるか11点と見るかだけです。
解法
計算量が小さいので、1を1とみるか11と見るかで分岐して全探索します。
11と見た場合残りの1は1と見るしかないということを利用してもう少しコードを縮める方法があるかもしれません。
#include<stdio.h>
#include<vector>
int ans;
std::vector<int> cards;
void saiki(int deep,int sum){
if(sum>21){
return ;
}
if(deep==cards.size()){
ans=ans>sum?ans:sum;
return ;
}
int card=cards[deep];
if(card==1){
saiki(deep+1,sum+11);
}
saiki(deep+1,sum+cards[deep]);
}
int main(){
int card;
char re;
while(1){
scanf("%d%c",&card,&re);
if(card==0) break;
cards.clear();
ans=0;
card=card>9?10:card;
cards.push_back(card);
while(re!='\n'){
scanf("%d%c",&card,&re);
card=card>9?10:card;
cards.push_back(card);
}
saiki(0,0);
printf("%d\n",ans);
}
}
----
*0170 Lunch
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0170
食べ物を縦長の袋に入れていきます。
食べ物は上にある食べ物の重さが限界地を超えると潰れてしまうので潰れないように食べ物を入れます。
この時できるだけ重心が低くなるように入れるという問題です。
解法
出来るだけ重いものかたら試すために,食べ物のデータをitem構造体で表現し重い順番にソートしておきます。
後は、重心が出来るだけ下になる順番で一つずつ試して深さ優先探索で全探索します。
この時食べ物が潰れる組み合わせは除外します。
#include<stdio.h>
#include <algorithm>
struct item{
char f[21];
int w,s;
bool operator<(const item i)const{
if(w!=i.w)return w>i.w;
return s>i.s;
}
};
item items[10],ans[10];
bool addOKs[10],allOK;
int n;
void saiki(int deep,int sum){
if(deep==n){
allOK=true;
return ;
}
int upSum;
for(int i=0;i<n;i++){
if(addOKs[i]==true){
upSum=sum-items[i].w;
if(upSum<=items[i].s){
ans[deep]=items[i];
addOKs[i]=false;
saiki(deep+1,upSum);
addOKs[i]=true;
if(allOK==true) return;
}
}
}
}
void setData(){
int sum=0;
for(int i=0;i<n;i++){
scanf("%s %d %d",items[i].f,&items[i].w,&items[i].s);
addOKs[i]=true;
sum+=items[i].w;
}
allOK=false;
std::sort(items,items+n);
saiki(0,sum);
for(int i=0;i<n;i++){
printf("%s\n",ans[i].f);
}
}
int main(){
while(1){
scanf("%d",&n);
if(n==0) break;
setData();
}
}
