「AOJ151～160」の編集履歴（バックアップ）一覧はこちら
「AOJ151～160」(2011/08/27 (土) 12:56:49) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*0151 Grid
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0151
升目に01が与えられるので、その中で縦横斜めで最も1が長く連続している場所の長さを答えよという問題。
解法
memoに縦横斜めに分解して計算したら後は動的計画法で解けます。
memoに全部まとめたのでコードがコンパクトになった分少しわかりにくくなったかもしれません。
#include<stdio.h>
#include<string.h>
char row[258];
int memo[4][2][258];//0横,1上 2左斜め ３右斜め
int dxs[]={-1,0,-1,1};
void search(int n){
int y,up,t,ans=0;
memset(memo,0,4*2*258*4);
for(int i=0;i<n;i++){
scanf("%s",&row[1]);
y=i%2;
for(int j=0;j<4;j++){
//j=0横,1上 2左斜め ３右斜め
up=j==0?y:(y+1)%2;
for(int x=1;x<=n;x++){
if(row[x]=='0'){
memo[j][y][x]=0;
}else{
t=memo[j][up][x+dxs[j]]+1;
ans=t>ans?t:ans;
memo[j][y][x]=t;
}
}
}
}
printf("%d\n",ans);
}
int main(){
int n;
scanf("%d",&n);
while(n!=0){
search(n);
scanf("%d",&n);
}
}
----
*0152 Bowling
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0152
ボーリングのピンを倒したデータからその得点を計算し、得点の良い順番に表示するという問題。
解法
計算が少し頻雑です。
ターンごとに結果を追いかけて分岐します。
10ターン目以降とそれ以外で処理を分岐させます。
typeに何投目がストライク、スペア、１０本倒せなかったかの結果を記録し,scoreに倒したピン数を記録します。
最後に集計して終わりです。
#include<stdio.h>
#include <algorithm>
struct menber{
int no,score;
bool operator<(const menber m)const{
if(score!=m.score) return score>m.score;
return no<m.no;
}
};
int calc(){
int p=0,turn=1,s,no;
bool first=true;
int score[22];
int type[22];
score[0]=type[0]=0;
char re;
while(re!='\n'){
scanf("%d%c",&s,&re);
score[p]=s;
if(turn>9){
type[p]=0;
}else{
if(s==10 && first==true){
type[p]=2;
turn++;
}else if(first==false && score[p]+score[p-1]==10){
type[p]=1;
turn++;
first=true;
}else{
score[p]=s;
type[p]=0;
if(first==true){
first=false;
}else{
first=true;
turn++;
}
}
}
p++;
}
int ans=0;
for(int i=0;i<p;i++){
ans+=score[i];
for(int j=1;j<=type[i];j++){
ans+=score[i+j];
}
}
return ans;
}
int main(){
int m,no;
menber menbers[41];
while(1){
scanf("%d",&m);
if(m==0)break;
for(int i=0;i<m;i++){
scanf("%d",&menbers[i].no);
menbers[i].score=calc();
}
std::sort(menbers,menbers+m);
for(int i=0;i<m;i++){
printf("%d %d\n",menbers[i].no,menbers[i].score);
}
}
}
----
*0153 Triangle and Circle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0153
三角形と円の座標とサイズが与えられるので三角形と円の位置関係を出力せよという問題。
三角形の中に円がある、円の中に三角形がある、２つに共有部分がある、全くないの４パタンを判断します。
解法
あまり良い解法を用意できませんでした。
コードは最初に三角形が円の中にあるかを最初に確かめ円の中にあればそう出力します。
当てはまらなければ次に三角形の中に円があるかを確かめます。
ここではinDelta関数でベクトルの概念を使い円の中心が三角形の中にあるかを確かめます。
同時に円の中心と三角形の線分までの距離を求め、円と三角形の辺が交点を持たず三角形の中に円があれば三角形の中に円があると出力します。
当てはまらなければ三角形の線分と円が交点を持つかを調べます。
もてば共有部分を持つと出力します。
全ての条件に当てはまらなければ共有点なしと出力します。
#include<stdio.h>
#include<math.h>
double min=0.000001;
bool inDelta(double xs[3],double ys[3],double x,double y){
double x1,x2,x3,y1,y2,y3,k,s,t,u;
x1=xs[1]-xs[0];
y1=ys[1]-ys[0];
x2=xs[2]-xs[0];
y2=ys[2]-ys[0];
x3=x-xs[0];
y3=y-ys[0];
k=(x1*y2-x2*y1);
if(k==0){
return false;
}
s=(y2*x3-x2*y3)/k;
t=(x1*y3-y1*x3)/k;
u=s+t;
if(s<0.0 || 1.0<s || t<0.0 || 1.0<t || u<0.0 || 1.0<u){
return false;
}else{
return true;
}
}
bool unionOK(double vx,double vy,double vx2,double vy2,double r,int mode){
double len,ansH,cosA,len3,ansW,ans;
len =hypot(vx,vy);
ansH=fabs(vx*vy2-vx2*vy)/len;
ansW=(vx*vx2+vy*vy2)/len;
if(mode==0){
if(ansH>=r){
return false;
}else{
return true;
}
}else if(mode==1){
if(ansH>r){
return false;
}
}
ansH=ansH>r?r:ansH;
len3=sqrt(r*r-ansH*ansH);
ans=ansW+len3;
if(0<=ans && ans<=len){
return true;
}
ans=ansW-len3;
if(0<=ans && ans<=len){
return true;
}
return false;
}
void check(double xs[3],double ys[3],double x,double y,double r){
bool isInCircle=true;
for(int i=0;i<3;i++){
//三角形が円に含まれる場合
if(hypot(xs[i]-x,ys[i]-y)>r){
isInCircle=false;
}
}
if(isInCircle==true){
printf("b\n");
return ;
}
bool isInDelta=inDelta(xs,ys,x,y);
bool isAllUnion=false;
for(int i=0;i<3;i++){
isAllUnion=isAllUnion||unionOK(xs[(i+1)%3]-xs[i],ys[(i+1)%3]-ys[i],x-xs[i],y-ys[i],r,0);
}
if(isInDelta==true && isAllUnion==false){
printf("a\n");
return ;
}
isAllUnion=false;
for(int i=0;i<3;i++){
isAllUnion=isAllUnion||unionOK(xs[(i+1)%3]-xs[i],ys[(i+1)%3]-ys[i],x-xs[i],y-ys[i],r,1);
}
if(isAllUnion==true){
printf("c\n");
return;
}
printf("d\n");
}
int main(){
double xs[3],ys[3],x,y,r;
while(1){
scanf("%lf %lf",&xs[0],&ys[0]);
if(xs[0]==0 && ys[0]==0) break;
scanf("%lf %lf %lf %lf %lf %lf %lf",&xs[1],&ys[1],&xs[2],&ys[2],&x,&y,&r);
check(xs,ys,x,y,r);
}
}
----
*0154 Sum of Cards
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0154
aiという数の書かれたカードがbi枚ずつあります(1<=i<=m aは整数)。
カードを組み合わせて数ｎを作る時何通りの作り方があるか答える問題。
解法
ナップザック法で計算します。
組み合わせ数が小さいことと配列のループは非常に速いということを利用して、全パタンをナップザックで回します。
大きい方から足し合わせることで重複して同じ数を足すことを避けます。
#include<stdio.h>
#include<string.h>
void setData(int m){
int a,b,perm[1001],p;
memset(perm,0,1001*4);
perm[0]=1;
for(int i=0;i<m;i++){
scanf("%d %d",&a,&b);
for(int j=1000;j>=a;j--){
for(int k=1;k<=b;k++){
if(j-k*a<0) break;
perm[j]+=perm[j-k*a];
}
}
}
perm[0]=0;
int g,num;
scanf("%d",&g);
for(int i=0;i<g;i++){
scanf("%d",&num);
printf("%d\n",perm[num]);
}
}
int main(){
int m;
while(1){
scanf("%d",&m);
if(m==0) break;
setData(m);
}
}
----
*0155 Spider Jin
http://judge.u-aizu.ac.jp/onlinejudge/status.jsp
ビルからビルへ縄を使って飛び移るスパイダー人がスタートするビルから目的のビルまで到達できるか、出来るならその経路を出力せよという問題。
ビルの座標がデータとして与えられるので、ビル間の距離が５０以下ならビルからビルへ飛び移れます。
解法
グラフの問題なので、データからグラフを生成してダイクストラ法で経路を探索します。
この時グラフのノードを必要なものだけグラフを表すｇに記録しておきます。
ビル番号が連番でない可能性を考慮してbillMemoに記録しておき、ビル番号とは別にビルに0から番号を振っておきます。
#include<stdio.h>
#include<map>
#include<vector>
#include<math.h>
int xs[1001],ys[1001];
int billNos[1001],billMemo[1001];
std::map<int,double> g[1001];
double flen=100000000;
void Dijkstras(int n,int start,int goal){
if(start==goal){
printf("%d\n",billNos[start]);
return ;
}
bool okPoints[1001];
double lens[1001];
double tlen;
int root[1001];
std::map<int,double>::iterator it;
for(int i=0;i<n;i++){
lens[i]=flen;
okPoints[i]=true;
}
lens[start]=0;
int nowPoint;
double minLen;
while(1){
minLen=flen;
nowPoint=-1;
for(int i=0;i<n;i++){
if(okPoints[i]==true && lens[i]<minLen){
minLen=lens[i];
nowPoint=i;
}
}
if(nowPoint==goal){
break;
}
if(nowPoint==-1){
printf("NA\n");
return;
}
okPoints[nowPoint]=false;
it=g[nowPoint].begin();
while(it!=g[nowPoint].end()){
tlen=(*it).second+lens[nowPoint];
if(tlen<lens[(*it).first]){
lens[(*it).first]=tlen;
root[(*it).first]=nowPoint;
}
it++;
}
}
std::vector<int> ansRoot;
nowPoint=goal;
while(nowPoint!=start){
ansRoot.push_back(root[nowPoint]);
nowPoint=root[nowPoint];
}
printf("%d",billNos[start]);
for(int i=ansRoot.size()-2;i>=0;i--){
printf(" %d",billNos[ansRoot[i]]);
}
printf(" %d\n",billNos[goal]);
}
void setData(int n){
int len;
for(int i=0;i<n;i++){
g[i].clear();
}
for(int i=0;i<n;i++){
scanf("%d %d %d",&billNos[i],&xs[i],&ys[i]);
billMemo[billNos[i]]=i;
for(int j=i-1;j>=0;j--){
len=(xs[i]-xs[j])*(xs[i]-xs[j])+(ys[i]-ys[j])*(ys[i]-ys[j]);
if(len<=2500){
g[i][j]=g[j][i]=sqrt((double)len);
}
}
}
int m,start,goal;
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d %d",&start,&goal);
Dijkstras(n,billMemo[start],billMemo[goal]);
}
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0) break;
setData(n);
}
}
----
*0156 Moats around the Castle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0156
忍者が外堀から城まで到達するルートを答える問題です。
外堀から城に行くまでに渡る堀の数の最小回数を答えます。
解法
逆に考えます。
城から最短の堀の数で外へでるのも外堀から城へ向かうのも塀を超える最小回数は同じになるはずです。
城からスタートして堀を一度も渡らないルートを全て確かめます。
外に出られたらそのまま出力します。
でられないなら一度堀に登っていけるルートを全て試します。
それでも駄目なら更にもうひとつ堀を渡ったルートを試します。
これを外に出られるまで繰り返します。
この発想を実現するため下記コードでは、移動した先をpoint構造体で保存し塀に登った回数をupCountとして保存します。
upＣｏｕｎｔをソート基準に優先順位付きキューに入れていけば簡単に実現します。
#include<stdio.h>
#include<string.h>
#include<queue>
struct point{
int x,y,upCount;
bool operator<(const point p)const{
return upCount>p.upCount;
}
};
char map[101][101];
bool moveOKs[101][101];
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
void search(int h,int w){
int x,y;
for(int i=0;i<h;i++){
scanf("%s",&map[i]);
for(int j=0;j<w;j++){
if(map[i][j]=='&'){
x=j;
y=i;
moveOKs[y][x]=false;
map[y][x]='.';
}
}
}
memset(moveOKs,true,101*101);
std::priority_queue<point> memo;
point p,nextP;
p.x=x;
p.y=y;
p.upCount=0;
memo.push(p);
int nx,ny;
while(memo.empty()==false){
p=memo.top();
nextP=memo.top();
memo.pop();
x=p.x;
y=p.y;
if(x==0 || x==w-1 || y==0 || y==h-1){
printf("%d\n",p.upCount);
break;
}
for(int i=0;i<4;i++){
nx=x+dxs[i];
ny=y+dys[i];
if(moveOKs[ny][nx]==false) continue;
moveOKs[ny][nx]=false;
if(map[ny][nx]=='#' && map[y][x]=='.'){
nextP.upCount=p.upCount+1;
}else{
nextP.upCount=p.upCount;
}
nextP.x=nx;
nextP.y=ny;
memo.push(nextP);
}
}
}
int main(){
int h,w;
while(1){
scanf("%d %d",&w,&h);
if(h==0 && w==0) break;
search(h,w);
}
}
----
*0157 Russian Dolls
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0157
マトリョーシカ(ロシアの入れ子人形)の中にできるだけたくさんより小さいマトリョーシカを入れたい。
マトリョーシカのサイズデータが与えられるので最も多く入る組み合わせを求めよという問題。
解法
人形の数も少ないので適当なメモ化探索でも十分計算量が安定します。
実装が楽な深さ優先探索のメモ化で実装してみましたが、より計算量を安定させるならナップザック法的な解き方もあると思います。
#include<stdio.h>
#include<map>
#include<vector>
struct kumi{
int h,r;
bool operator<(const kumi k)const{
if(h!=k.h) return h<k.h;
return r<k.r;
}
};
std::map<kumi,int> memo;
std::vector<int> hs;
std::vector<int> rs;
std::vector<bool> oks;
int k;
int saiki(kumi size,int deep){
if(memo.find(size)!=memo.end()){
return memo[size]+deep;
}
kumi next;
int sum=deep+1,temp;
for(int i=0;i<k;i++){
if(oks[i]==true && hs[i]<size.h && rs[i]<size.r){
oks[i]=false;
next.h=hs[i];
next.r=rs[i];
temp=saiki(next,deep+1);
sum=sum>temp?sum:temp;
oks[i]=true;
}
}
memo[size]=sum-deep;
return sum;
}
void setData(int n){
memo.clear();
hs.clear();
rs.clear();
oks.clear();
int h,r;
for(int i=0;i<n;i++){
scanf("%d %d",&h,&r);
hs.push_back(h);
rs.push_back(r);
oks.push_back(true);
}
int m;
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d %d",&h,&r);
hs.push_back(h);
rs.push_back(r);
oks.push_back(true);
}
kumi start;
int ans=0,temp;
k=m+n;
for(int i=0;i<k;i++){
start.h=hs[i];
start.r=rs[i];
temp=saiki(start,0);
ans=ans>temp?ans:temp;
}
printf("%d\n",ans);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0) break;
setData(n);
}
}
----
*0158 Collatz's Problem
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0158
コラッツの予想を計算して確かめましょうという問題。
解法
問題の方でアルゴリズムを指定しているのでそのまま実装します。
#include<stdio.h>
int main(){
int n,c;
while(1){
scanf("%d",&n);
if(n==0) break;
c=0;
while(n!=1){
n=n%2==1?n*3+1:n/2;
c++;
}
printf("%d\n",c);
}
}
----
*0159 The Best Body
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0159
ｎ人の伸長と体重のデータが与えられるので、ＢＭＩ値が22に最も近い人を探すという問題。
解法
計算するだけです。
3分で解くことを期待されてるような問題ですので気楽に解きましょう。
現実ではありえませんがＢＭＩ値は最悪200/0.0001=200万という値をとることにだけ注意しましょう。
#include<stdio.h>
#include<math.h>
int main(){
int n,no,ansNo;
double h,w,ans,t;
while(1){
scanf("%d",&n);
ans=9999999;
if(n==0)break;
while(n--){
scanf("%d %lf %lf",&no,&h,&w);
t=fabs(w/(h*h/10000.0)-22.0);
if(ans>t){
ans=t;
ansNo=no;
}
}
printf("%d\n",ansNo);
}
}
----
*0160 Delivery Fee
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0160
郵便物の郵便料金を求める問題。
荷物はサイズと重さで郵便料金が変わるのでそれを考慮して郵便料金の総計を出力せよという問題。
解法
指定通りに実装するだけです。
#include <stdio.h>
#include <algorithm>
int main(){
int x,y,h,w,n,t,sum,s1;
int size[6]={60,80,100,120,140,160};
int ws[6] ={2,5,10,15,20,25};
int ps[7] ={600,800,1000,1200,1400,1600,0};
scanf("%d",&n);
while(n!=0){
sum=0;
for(int i=0;i<n;i++){
t=6;
scanf("%d %d %d %d",&x,&y,&h,&w);
s1=x+y+h;
for(int i=0;i<6;i++){
if(size[i]>=s1 && ws[i]>=w){
t=i;
break;
}
}
sum+=ps[t];
}
printf("%d\n",sum);
scanf("%d",&n);
}
}
*0151 Grid
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0151
升目に01が与えられるので、その中で縦横斜めで最も1が長く連続している場所の長さを答えよという問題。
解法
memoに縦横斜めに分解して計算したら後は動的計画法で解けます。
memoに全部まとめたのでコードがコンパクトになった分少しわかりにくくなったかもしれません。
#include<stdio.h>
#include<string.h>
char row[258];
int memo[4][2][258];//0横,1上 2左斜め ３右斜め
int dxs[]={-1,0,-1,1};
void search(int n){
int y,up,t,ans=0;
memset(memo,0,4*2*258*4);
for(int i=0;i<n;i++){
scanf("%s",&row[1]);
y=i%2;
for(int j=0;j<4;j++){
//j=0横,1上 2左斜め ３右斜め
up=j==0?y:(y+1)%2;
for(int x=1;x<=n;x++){
if(row[x]=='0'){
memo[j][y][x]=0;
}else{
t=memo[j][up][x+dxs[j]]+1;
ans=t>ans?t:ans;
memo[j][y][x]=t;
}
}
}
}
printf("%d\n",ans);
}
int main(){
int n;
scanf("%d",&n);
while(n!=0){
search(n);
scanf("%d",&n);
}
}
----
*0152 Bowling
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0152
ボーリングのピンを倒したデータからその得点を計算し、得点の良い順番に表示するという問題。
解法
計算が少し頻雑です。
ターンごとに結果を追いかけて分岐します。
10ターン目以降とそれ以外で処理を分岐させます。
typeに何投目がストライク、スペア、１０本倒せなかったかの結果を記録し,scoreに倒したピン数を記録します。
最後に集計して終わりです。
#include<stdio.h>
#include <algorithm>
struct menber{
int no,score;
bool operator<(const menber m)const{
if(score!=m.score) return score>m.score;
return no<m.no;
}
};
int calc(){
int p=0,turn=1,s,no;
bool first=true;
int score[22];
int type[22];
score[0]=type[0]=0;
char re;
while(re!='\n'){
scanf("%d%c",&s,&re);
score[p]=s;
if(turn>9){
type[p]=0;
}else{
if(s==10 && first==true){
type[p]=2;
turn++;
}else if(first==false && score[p]+score[p-1]==10){
type[p]=1;
turn++;
first=true;
}else{
score[p]=s;
type[p]=0;
if(first==true){
first=false;
}else{
first=true;
turn++;
}
}
}
p++;
}
int ans=0;
for(int i=0;i<p;i++){
ans+=score[i];
for(int j=1;j<=type[i];j++){
ans+=score[i+j];
}
}
return ans;
}
int main(){
int m,no;
menber menbers[41];
while(1){
scanf("%d",&m);
if(m==0)break;
for(int i=0;i<m;i++){
scanf("%d",&menbers[i].no);
menbers[i].score=calc();
}
std::sort(menbers,menbers+m);
for(int i=0;i<m;i++){
printf("%d %d\n",menbers[i].no,menbers[i].score);
}
}
}
----
*0153 Triangle and Circle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0153
三角形と円の座標とサイズが与えられるので三角形と円の位置関係を出力せよという問題。
三角形の中に円がある、円の中に三角形がある、２つに共有部分がある、全くないの４パタンを判断します。
解法
あまり良い解法を用意できませんでした。
コードは最初に三角形が円の中にあるかを確かめ円の中にあればそう出力します。
当てはまらなければ次に三角形の中に円があるかを確かめます。
ここではinDelta関数でベクトルの概念を使い円の中心が三角形の中にあるかを確かめます。
同時に円の中心と三角形の線分までの距離を求め、円と三角形の辺が交点を持たず三角形の中に円があれば三角形の中に円があると出力します。
当てはまらなければ三角形の線分と円が交点を持つかを調べます。
もてば共有部分を持つと出力します。
全ての条件に当てはまらなければ共有点なしと出力します。
#include<stdio.h>
#include<math.h>
double min=0.000001;
bool inDelta(double xs[3],double ys[3],double x,double y){
double x1,x2,x3,y1,y2,y3,k,s,t,u;
x1=xs[1]-xs[0];
y1=ys[1]-ys[0];
x2=xs[2]-xs[0];
y2=ys[2]-ys[0];
x3=x-xs[0];
y3=y-ys[0];
k=(x1*y2-x2*y1);
if(k==0){
return false;
}
s=(y2*x3-x2*y3)/k;
t=(x1*y3-y1*x3)/k;
u=s+t;
if(s<0.0 || 1.0<s || t<0.0 || 1.0<t || u<0.0 || 1.0<u){
return false;
}else{
return true;
}
}
bool unionOK(double vx,double vy,double vx2,double vy2,double r,int mode){
double len,ansH,cosA,len3,ansW,ans;
len =hypot(vx,vy);
ansH=fabs(vx*vy2-vx2*vy)/len;
ansW=(vx*vx2+vy*vy2)/len;
if(mode==0){
if(ansH>=r){
return false;
}else{
return true;
}
}else if(mode==1){
if(ansH>r){
return false;
}
}
ansH=ansH>r?r:ansH;
len3=sqrt(r*r-ansH*ansH);
ans=ansW+len3;
if(0<=ans && ans<=len){
return true;
}
ans=ansW-len3;
if(0<=ans && ans<=len){
return true;
}
return false;
}
void check(double xs[3],double ys[3],double x,double y,double r){
bool isInCircle=true;
for(int i=0;i<3;i++){
//三角形が円に含まれる場合
if(hypot(xs[i]-x,ys[i]-y)>r){
isInCircle=false;
}
}
if(isInCircle==true){
printf("b\n");
return ;
}
bool isInDelta=inDelta(xs,ys,x,y);
bool isAllUnion=false;
for(int i=0;i<3;i++){
isAllUnion=isAllUnion||unionOK(xs[(i+1)%3]-xs[i],ys[(i+1)%3]-ys[i],x-xs[i],y-ys[i],r,0);
}
if(isInDelta==true && isAllUnion==false){
printf("a\n");
return ;
}
isAllUnion=false;
for(int i=0;i<3;i++){
isAllUnion=isAllUnion||unionOK(xs[(i+1)%3]-xs[i],ys[(i+1)%3]-ys[i],x-xs[i],y-ys[i],r,1);
}
if(isAllUnion==true){
printf("c\n");
return;
}
printf("d\n");
}
int main(){
double xs[3],ys[3],x,y,r;
while(1){
scanf("%lf %lf",&xs[0],&ys[0]);
if(xs[0]==0 && ys[0]==0) break;
scanf("%lf %lf %lf %lf %lf %lf %lf",&xs[1],&ys[1],&xs[2],&ys[2],&x,&y,&r);
check(xs,ys,x,y,r);
}
}
----
*0154 Sum of Cards
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0154
aiという数の書かれたカードがbi枚ずつあります(1<=i<=m aは整数)。
カードを組み合わせて数ｎを作る時何通りの作り方があるか答える問題。
解法
ナップザック法で計算します。
組み合わせ数が小さいことと配列のループは非常に速いということを利用して、全パタンをナップザックで回します。
大きい方から足し合わせることで重複して同じ数を足すことを避けます。
#include<stdio.h>
#include<string.h>
void setData(int m){
int a,b,perm[1001],p;
memset(perm,0,1001*4);
perm[0]=1;
for(int i=0;i<m;i++){
scanf("%d %d",&a,&b);
for(int j=1000;j>=a;j--){
for(int k=1;k<=b;k++){
if(j-k*a<0) break;
perm[j]+=perm[j-k*a];
}
}
}
perm[0]=0;
int g,num;
scanf("%d",&g);
for(int i=0;i<g;i++){
scanf("%d",&num);
printf("%d\n",perm[num]);
}
}
int main(){
int m;
while(1){
scanf("%d",&m);
if(m==0) break;
setData(m);
}
}
----
*0155 Spider Jin
http://judge.u-aizu.ac.jp/onlinejudge/status.jsp
ビルからビルへ縄を使って飛び移るスパイダー人がスタートするビルから目的のビルまで到達できるか、出来るならその経路を出力せよという問題。
ビルの座標がデータとして与えられるので、ビル間の距離が５０以下ならビルからビルへ飛び移れます。
解法
グラフの問題なので、データからグラフを生成してダイクストラ法で経路を探索します。
この時グラフのノードを必要なものだけグラフを表すｇに記録しておきます。
ビル番号が連番でない可能性を考慮してbillMemoに記録しておき、ビル番号とは別にビルに0から番号を振っておきます。
#include<stdio.h>
#include<map>
#include<vector>
#include<math.h>
int xs[1001],ys[1001];
int billNos[1001],billMemo[1001];
std::map<int,double> g[1001];
double flen=100000000;
void Dijkstras(int n,int start,int goal){
if(start==goal){
printf("%d\n",billNos[start]);
return ;
}
bool okPoints[1001];
double lens[1001];
double tlen;
int root[1001];
std::map<int,double>::iterator it;
for(int i=0;i<n;i++){
lens[i]=flen;
okPoints[i]=true;
}
lens[start]=0;
int nowPoint;
double minLen;
while(1){
minLen=flen;
nowPoint=-1;
for(int i=0;i<n;i++){
if(okPoints[i]==true && lens[i]<minLen){
minLen=lens[i];
nowPoint=i;
}
}
if(nowPoint==goal){
break;
}
if(nowPoint==-1){
printf("NA\n");
return;
}
okPoints[nowPoint]=false;
it=g[nowPoint].begin();
while(it!=g[nowPoint].end()){
tlen=(*it).second+lens[nowPoint];
if(tlen<lens[(*it).first]){
lens[(*it).first]=tlen;
root[(*it).first]=nowPoint;
}
it++;
}
}
std::vector<int> ansRoot;
nowPoint=goal;
while(nowPoint!=start){
ansRoot.push_back(root[nowPoint]);
nowPoint=root[nowPoint];
}
printf("%d",billNos[start]);
for(int i=ansRoot.size()-2;i>=0;i--){
printf(" %d",billNos[ansRoot[i]]);
}
printf(" %d\n",billNos[goal]);
}
void setData(int n){
int len;
for(int i=0;i<n;i++){
g[i].clear();
}
for(int i=0;i<n;i++){
scanf("%d %d %d",&billNos[i],&xs[i],&ys[i]);
billMemo[billNos[i]]=i;
for(int j=i-1;j>=0;j--){
len=(xs[i]-xs[j])*(xs[i]-xs[j])+(ys[i]-ys[j])*(ys[i]-ys[j]);
if(len<=2500){
g[i][j]=g[j][i]=sqrt((double)len);
}
}
}
int m,start,goal;
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d %d",&start,&goal);
Dijkstras(n,billMemo[start],billMemo[goal]);
}
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0) break;
setData(n);
}
}
----
*0156 Moats around the Castle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0156
忍者が外堀から城まで到達するルートを答える問題です。
外堀から城に行くまでに渡る堀の数の最小回数を答えます。
解法
逆に考えます。
城から最短の堀の数で外へでるのも外堀から城へ向かうのも塀を超える最小回数は同じになるはずです。
城からスタートして堀を一度も渡らないルートを全て確かめます。
外に出られたらそのまま出力します。
でられないなら一度堀に登っていけるルートを全て試します。
それでも駄目なら更にもうひとつ堀を渡ったルートを試します。
これを外に出られるまで繰り返します。
この発想を実現するため下記コードでは、移動した先をpoint構造体で保存し塀に登った回数をupCountとして保存します。
upＣｏｕｎｔをソート基準に優先順位付きキューに入れていけば簡単に実現します。
#include<stdio.h>
#include<string.h>
#include<queue>
struct point{
int x,y,upCount;
bool operator<(const point p)const{
return upCount>p.upCount;
}
};
char map[101][101];
bool moveOKs[101][101];
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
void search(int h,int w){
int x,y;
for(int i=0;i<h;i++){
scanf("%s",&map[i]);
for(int j=0;j<w;j++){
if(map[i][j]=='&'){
x=j;
y=i;
moveOKs[y][x]=false;
map[y][x]='.';
}
}
}
memset(moveOKs,true,101*101);
std::priority_queue<point> memo;
point p,nextP;
p.x=x;
p.y=y;
p.upCount=0;
memo.push(p);
int nx,ny;
while(memo.empty()==false){
p=memo.top();
nextP=memo.top();
memo.pop();
x=p.x;
y=p.y;
if(x==0 || x==w-1 || y==0 || y==h-1){
printf("%d\n",p.upCount);
break;
}
for(int i=0;i<4;i++){
nx=x+dxs[i];
ny=y+dys[i];
if(moveOKs[ny][nx]==false) continue;
moveOKs[ny][nx]=false;
if(map[ny][nx]=='#' && map[y][x]=='.'){
nextP.upCount=p.upCount+1;
}else{
nextP.upCount=p.upCount;
}
nextP.x=nx;
nextP.y=ny;
memo.push(nextP);
}
}
}
int main(){
int h,w;
while(1){
scanf("%d %d",&w,&h);
if(h==0 && w==0) break;
search(h,w);
}
}
----
*0157 Russian Dolls
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0157
マトリョーシカ(ロシアの入れ子人形)の中にできるだけたくさんより小さいマトリョーシカを入れたい。
マトリョーシカのサイズデータが与えられるので最も多く入る組み合わせを求めよという問題。
解法
人形の数も少ないので適当なメモ化探索でも十分計算量が安定します。
実装が楽な深さ優先探索のメモ化で実装してみましたが、より計算量を安定させるならナップザック法的な解き方もあると思います。
#include<stdio.h>
#include<map>
#include<vector>
struct kumi{
int h,r;
bool operator<(const kumi k)const{
if(h!=k.h) return h<k.h;
return r<k.r;
}
};
std::map<kumi,int> memo;
std::vector<int> hs;
std::vector<int> rs;
std::vector<bool> oks;
int k;
int saiki(kumi size,int deep){
if(memo.find(size)!=memo.end()){
return memo[size]+deep;
}
kumi next;
int sum=deep+1,temp;
for(int i=0;i<k;i++){
if(oks[i]==true && hs[i]<size.h && rs[i]<size.r){
oks[i]=false;
next.h=hs[i];
next.r=rs[i];
temp=saiki(next,deep+1);
sum=sum>temp?sum:temp;
oks[i]=true;
}
}
memo[size]=sum-deep;
return sum;
}
void setData(int n){
memo.clear();
hs.clear();
rs.clear();
oks.clear();
int h,r;
for(int i=0;i<n;i++){
scanf("%d %d",&h,&r);
hs.push_back(h);
rs.push_back(r);
oks.push_back(true);
}
int m;
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d %d",&h,&r);
hs.push_back(h);
rs.push_back(r);
oks.push_back(true);
}
kumi start;
int ans=0,temp;
k=m+n;
for(int i=0;i<k;i++){
start.h=hs[i];
start.r=rs[i];
temp=saiki(start,0);
ans=ans>temp?ans:temp;
}
printf("%d\n",ans);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0) break;
setData(n);
}
}
----
*0158 Collatz's Problem
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0158
コラッツの予想を計算して確かめましょうという問題。
解法
問題の方でアルゴリズムを指定しているのでそのまま実装します。
#include<stdio.h>
int main(){
int n,c;
while(1){
scanf("%d",&n);
if(n==0) break;
c=0;
while(n!=1){
n=n%2==1?n*3+1:n/2;
c++;
}
printf("%d\n",c);
}
}
----
*0159 The Best Body
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0159
ｎ人の伸長と体重のデータが与えられるので、ＢＭＩ値が22に最も近い人を探すという問題。
解法
計算するだけです。
3分で解くことを期待されてるような問題ですので気楽に解きましょう。
現実ではありえませんがＢＭＩ値は最悪200/0.0001=200万という値をとることにだけ注意しましょう。
#include<stdio.h>
#include<math.h>
int main(){
int n,no,ansNo;
double h,w,ans,t;
while(1){
scanf("%d",&n);
ans=9999999;
if(n==0)break;
while(n--){
scanf("%d %lf %lf",&no,&h,&w);
t=fabs(w/(h*h/10000.0)-22.0);
if(ans>t){
ans=t;
ansNo=no;
}
}
printf("%d\n",ansNo);
}
}
----
*0160 Delivery Fee
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0160
郵便物の郵便料金を求める問題。
荷物はサイズと重さで郵便料金が変わるのでそれを考慮して郵便料金の総計を出力せよという問題。
解法
指定通りに実装するだけです。
#include <stdio.h>
#include <algorithm>
int main(){
int x,y,h,w,n,t,sum,s1;
int size[6]={60,80,100,120,140,160};
int ws[6] ={2,5,10,15,20,25};
int ps[7] ={600,800,1000,1200,1400,1600,0};
scanf("%d",&n);
while(n!=0){
sum=0;
for(int i=0;i<n;i++){
t=6;
scanf("%d %d %d %d",&x,&y,&h,&w);
s1=x+y+h;
for(int i=0;i<6;i++){
if(size[i]>=s1 && ws[i]>=w){
t=i;
break;
}
}
sum+=ps[t];
}
printf("%d\n",sum);
scanf("%d",&n);
}
}
