0161 Sport Meet
解法
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
#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
解法
料金マトリックスを作って条件を満たすか調べるだけです。
競技プログラムなので1300円以上なら40km以上走っているということを利用してコードを短縮します。
実務では距離情報のマトリックスも作っておくべきでしょう。
#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円より大きいなら40km以上走ってることになる
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
解法
簡単な問題なので書いてある通りに実装するだけです。
最後に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
宝くじの総賞金支払い額を求める問題。
宝くじ一枚は一サブプライムで当選番号はpとmの二つの整数の組であらわされ、当選額はp-m~p+mの間にある素数の数nで決まり、当選者にはnサブプライムが支払われます。
当選金のうち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
解法
一つの三角形は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
解法
数列のサイズが小さいのでそのままシミュレートして解きます。
バブルソートも挿入ソートも計算量が同じということを利用してコードを短縮して解きます。
賢い人ならこの問題はより高度な方法で解くようです。
調べてみるのもよいでしょう。
#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
解法
メモ化計算という言葉さえ知っていれば鼻歌交じりで解ける簡単問題です。
こういう簡単な問題は気楽に解ける分解いてて楽しいものです。
#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
解法
計算量が小さいので、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
解法
出来るだけ重いものかたら試すために,食べ物のデータを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();
}
}
最終更新:2012年07月11日 16:41