「AOJ201～210」の編集履歴（バックアップ）一覧に戻る
AOJ201～210 - (2011/09/27 (火) 14:54:38) のソース
*0201 Wrought Gold Master
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0201
錬金術でアイテムの調合ができます。
複数のアイテムを調合して最も安く目的のアイテムを作ったときの値段を求める問題。
解法
アイテムを一つずつ確かめて、錬金で安く作れるならその値段に改定します。
改定した値段で更に調べなおして、値段が改定できなくなるまでループし続ければ答えがもとまります。
この方法でも十分速度はでますが、すべてのアイテムの最低値を求めており無駄があります。
もっと賢い方法として両手法という方法があるようです。
#include<iostream>
#include<map>
#include<string>
#include<vector>
using namespace std;
void setData(int n){
map<string,int> items;
map<string,vector<string> > process;
map<string,int>::iterator itemIt;
vector<string>::iterator processIt,end;
int Count=1,value,m,k,sum;
string name,item;
for(int i=0;i<n;i++){
std::cin>>name>>value;
items[name]=value;
}
std::cin>>m;
for(int i=0;i<m;i++){
std::cin>>name>>k;
for(int i=0;i<k;i++){
cin>>item;
process[name].push_back(item);
}
}
cin>>name;
while(Count>0){
Count=0;
itemIt=items.begin();
while(itemIt!=items.end()){
sum=0;
if(process.find((*itemIt).first)!=process.end()){
processIt=process[(*itemIt).first].begin();
end=process[(*itemIt).first].end();
while(processIt!=end){
sum+=items[*processIt];
processIt++;
}
if(sum<(*itemIt).second){
items[(*itemIt).first]=sum;
Count++;
}
}
itemIt++;
}
}
cout<<items[name]<<"\n";
}
int main(){
int n;
while(scanf("%d",&n),n>0){
setData(n);
}
}
----
*0202 At Boss's Expense
飲食店で食べ物の値段と予算が与えられます。
食べ物を組み合わせて、予算額以下で素数になっている注文額を求めよという問題。
1円は特例的に素数に含むようです。
解法
下から足しこんでいくだけです。
値段1円のものがあったら計算量が増えるのでその時は全ての値段を作ることができることを逆利用して上から見ていきます。
普通の値段なら下から足しこんでいくだけです。
重複して足しこんでいる部分があるので重複を削除できればもう少し高速化できるかもしれません。
#include<stdio.h>
#include<string.h>
#include <algorithm>
int so[1000002];
void setSo(){
for(int i=2;i<1000001;i++)
so[i]=i%2;
int k;
for(int i=3;i<=1000;i+=2){
if(so[i]==true){
k=i*2;
for(int j=i*3;j<1000001;j+=(k)){
so[j]=false;
}
}
}
so[0]=false;
so[1]=true;
so[2]=true;
}
bool permMemo[1000002];
void calc(int n,int x){
int foods[31],ans=-1,t;
bool isOne=false;
for(int i=0;i<n;i++){
scanf("%d",&foods[i]);
if(foods[i]==1) isOne=true;
}
if(isOne==true){
//1があったので最大の素数を求める
for(int i=x;i>0;i--){
if(so[i]==true){
ans=i;
break;
}
}
}else{
memset(permMemo,false,x+1);
permMemo[0]=true;
std::sort(foods,foods+n);
for(int i=0;i<x;i++){
//0から値段を一つずつ足しこんでいく
if(permMemo[i]==true){
for(int j=0;j<n;j++){
t=i+foods[j];
if(x<t)break;
permMemo[t]=true;
if(so[t]==true){
ans=t>ans?t:ans;
}
}
}
}
}
if(ans==-1){
printf("NA\n");
}else{
printf("%d\n",ans);
}
}
int main(){
int n,x;
setSo();
while(scanf("%d %d",&n,&x),n+x>0){
calc(n,x);
}
}
----
*0203 A New Plan of Aizu Ski Resort
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0203
スキー場のマップが格子で与えられるので何通りの滑り方があるか答える問題。
解法
一段ずつ前の段から計算してルート数を求め最後に集計するだけです。
最後の集計は最終行をジャンプ台で飛ばしてる場合があるので一行先まで集計します。
ジャンプ台杉ジャンプ台のようなパターンがあるのでその点にだけ注意すれば簡単な問題です。
#include<stdio.h>
#include<string.h>
int map[16][18];
int roots[18][18];
void setMap(int x,int y){
memset(map,0,16*18*4);
for(int i=0;i<y;i++){
for(int j=1;j<=x;j++){
scanf("%d",&map[i][j]);
}
}
memset(roots,0,18*18*4);
for(int i=1;i<=x;i++){
if(map[0][i]==0){
roots[0][i]=1;
}
}
int t,r;
for(int i=0;i<y-1;i++){
for(int j=1;j<=x;j++){
t=map[i][j];
r=roots[i][j];
if(t==1){
//障害物なので何もしない
roots[i][j]=0;
continue;
}else if(t==2 && map[i+2][j]!=1){
//ジャンプ台かつジャンプ先が障害物でないなら
roots[i+2][j]+=r;
}else if(t==0){
//斜面なら
if(map[i+1][j-1]==0) roots[i+1][j-1]+=r;
if(map[i+1][j+0]!=1) roots[i+1][j+0]+=r;
if(map[i+1][j+1]==0) roots[i+1][j+1]+=r;
}
}
}
int sum=0;
for(int i=1;i<=x;i++) sum+=roots[y][i]+roots[y-1][i];
printf("%d\n",sum);
}
int main(){
int x,y;
while(scanf("%d %d",&x,&y),x+y>0){
setMap(x,y);
}
}
----
*0204 UFO Shooting Down Operation
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0204
ＵＦＯ撃墜ゲームの自動迎撃システムの撃墜シミュレーションをせよという問題です。
解法
この問題は当たり判定の数学的記述ができるかどうだけです。
三角関数と正射影の概念を使ってcalc関数で当たり判定を簡潔に記述します。
後は移動処理、ビームの半径内に入った機体の削除処理、ビームの当たり処理、削除処理を記述します。
、
#include<stdio.h>
#include<math.h>
#include<vector>
#include <algorithm>
struct enemy{
double x,y,len,moveX,moveY,r,v;
void setData(double sx,double sy,double size,double sv){
len=sqrt(sx*sx+sy*sy);
moveX=-sv*sx/len;
moveY=-sv*sy/len;
x=sx;
y=sy;
r=size;
v=sv;
}
void move(){
x+=moveX;
y+=moveY;
len-=v;
}
bool operator<(const enemy e)const{
return len<e.len;
}
};
bool calc(double bx,double by,double rb,double ex,double ey,double re){
double len1=sqrt(bx*bx+by*by);
double lenSin=fabs(bx*ey-ex*by)/len1;
if(re<lenSin) return false;
double lenCos=(bx*ex+by*ey)/len1;
double len2=sqrt(re*re-lenSin*lenSin);
double ans=lenCos+len2;
if(ans<=rb)return false;
return true;
}
void setData(double R,int N){
std::vector<enemy> enemys;
std::vector<enemy>::iterator it;
enemy e;
double x0,y0,r,v;
for(int i=0;i<N;i++){
scanf("%lf %lf %lf %lf",&x0,&y0,&r,&v);
e.setData(x0,y0,r,v);
enemys.push_back(e);
}
int inCount=0;
double bx,by;
while(enemys.empty()==false){
it=enemys.begin();
while(it!=enemys.end()){
//移動処理
(*it).move();
//レーザーの有効圏内を割ったので削除処理
if((*it).len<=R){
it=enemys.erase(it);
inCount++;
}else{
it++;
}
}
if(enemys.empty()) break;
//一番近いＵＦＯに並べ替える
std::sort(enemys.begin(),enemys.end());
it=enemys.begin();
bx=(*it).x;
by=(*it).y;
while(it!=enemys.end()){
//ビームの射線上に他に当たり判定がないか確かめて敵を削除する。
if(calc(bx,by,R,(*it).x,(*it).y,(*it).r)){
it=enemys.erase(it);
}else{
it++;
}
}
}
printf("%d\n",inCount);
}
int main(){
double R;
int N;
while(1){
scanf("%lf %d",&R,&N);
if(R==0 && N==0) break;
setData(R,N);
}
}
----
*0205 Rock, Paper, Scissors
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0205
5人のじゃんけんの結果を表示せよという問題。
解法
グーを1チョキを2パーを4としてビット演算に符号化して解いてみました。
この方法なら何人に増えても変数を変えるだけで対応できます。
#include<stdio.h>
int main(){
int te[5],kekka[4];
int all;
while(scanf("%d",&te[0]),te[0]!=0){
all=(1<<(te[0]-1));
for(int i=1;i<5;i++){
scanf("%d",&te[i]);
all|=(1<<(te[i]-1));
}
if(all==7 || all==4 || all==2 || all==1){
kekka[1]=kekka[2]=kekka[3]=3;
}else if(all==3){
//グーとチョキ
kekka[1]=1;
kekka[2]=2;
}else if(all==5){
//グーとパー
kekka[1]=2;
kekka[3]=1;
}else if(all==6){
//チョキとパー
kekka[2]=1;
kekka[3]=2;
}
for(int i=0;i<5;i++)printf("%d\n",kekka[te[i]]);
}
}
----
*0206 Next Trip
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0206
月々の貯蓄から旅行費用の積み立てがいつ終わるかを答える問題。
解法
単純に足し算するだけの問題です。
#include<stdio.h>
int main(){
int l,n,m,sum,ans;
while(scanf("%d",&l),l!=0){
ans=sum=0;
for(int i=0;i<12;i++){
scanf("%d %d",&m,&n);
sum+=m-n;
if(sum>=l && ans==0){
ans=i+1;
}
}
if(ans==0){
printf("NA\n");
}else{
printf("%d\n",ans);
}
}
}
----
*0207 Block
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0207
ブロックでできた迷路がスタートからゴールまでたどり着けるか調べる問題。
解法
奇麗に整え直したコードを掲載しようと思ったのですが、簡単な問題なのに奇麗に直したコードがなぜか通らず。
最初に書いたあまり良くないコードを掲載しておきます。
盤面を生成して再帰で探索しています。
#include <stdio.h>
void addBlock(int color,int d,int x,int y);
void setMap();
void search(int x,int y);
int map[102][102];
int xs,ys,xg,yg;
int w,h;
bool endFlag;
int startColor;
int main(){
scanf("%d %d",&w,&h);
while(w!=0 || h!=0){
setMap();
scanf("%d %d",&w,&h);
}
}
void setMap(){
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
map[i][j]=-1;
}
}
endFlag=false;
scanf("%d %d",&xs,&ys);
scanf("%d %d",&xg,&yg);
int n;
scanf("%d",&n);
int c,d,x,y;
for(int i=0;i<n;i++){
scanf("%d %d %d %d",&c,&d,&x,&y);
addBlock(c,d,x,y);
}
startColor=map[xs][ys];
if(startColor!=-1){
search(xs,ys);
}
if(endFlag==true)
{
printf("OK\n");
}else{
printf("NG\n");
}
}
void search(int x,int y){
if(w>=x && x>0 && h>=y && y>0){
if(map[x][y]!=-1 && map[x][y]==startColor){
if(y==yg && x==xg){
endFlag=true;
return ;
}
map[x][y]=-1;
search(x+1,y);
if(endFlag==true) return ;
search(x-1,y);
if(endFlag==true) return ;
search(x,y+1);
if(endFlag==true) return ;
search(x,y-1);
if(endFlag==true) return ;
}
}
}
void addBlock(int color,int d,int x,int y)
{
if(d==0){
//横向き
map[x][y]=map[x+1][y]=map[x+2][y]=map[x+3][y]=color;
map[x][y+1]=map[x+1][y+1]=map[x+2][y+1]=map[x+3][y+1]=color;
}else{
//縦向き
map[x][y]=map[x][y+1]=map[x][y+2]=map[x][y+3]=color;
map[x+1][y]=map[x+1][y+1]=map[x+1][y+2]=map[x+1][y+3]=color;
}
}
----
*0208 Room Numbers of a Hospital
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0208
解法
私の考えたコードを掲載しようかと考えたのですがネットにとても美しい解法があったのでそちらを掲載することにしました。
簡単な問題を解くだけですが、シンプルで無駄がないいいコードです。
#include<stdio.h>
//http://program.pinemz.net/article/168162542.htmlを参考にしました
int t[]={0,1,2,3,5,7,8,9};
void saiki(int n){
if(n>=8){
saiki(n/8);
}
printf("%d",t[n%8]);
}
int main(){
int n;
while(scanf("%d",&n),n>0){
saiki(n);
printf("\n");
}
}
----
*0209 Scene in a Picture
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0209
２つの画像データを照合して一致する左上の座標を返す問題。
解法
普通に左上から画像を照合するだけです。
#include<stdio.h>
void roundPict(int rPict[4][51][51],int r,int m){
for(int y=0;y<m;y++){
for(int x=0;x<m;x++){
rPict[r][x][m-y-1]=rPict[r-1][y][x];
}
}
}
void getPictTop(int rPict[4][51][51],int m,int xTops[4],int yTops[4]){
for(int r=0;r<4;r++){
bool hit=false;
for(int y=0;y<m;y++){
for(int x=0;x<m;x++){
if(rPict[r][y][x]!=-1){
xTops[r]=x;
yTops[r]=y;
hit=true;
break;
}
}
if(hit==true)break;
}
}
}
bool setData(){
int rPict[4][51][51],map[101][101],n,m;
int xTops[4],yTops[4];
scanf("%d %d",&n,&m);
if(n==0 && m==0) return false;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&map[i][j]);
}
}
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
scanf("%d",&rPict[0][i][j]);
}
}
roundPict(rPict,1,m);
roundPict(rPict,2,m);
roundPict(rPict,3,m);
getPictTop(rPict,m,xTops,yTops);
int side=n-m+1;
bool hit;
int ansX=101,ansY=101,tx,ty;
for(int y=0;y<side;y++){
if(ansY<y) break;
for(int x=0;x<side;x++){
for(int r=0;r<4;r++){
hit=true;
for(int dy=0;dy<m;dy++){
for(int dx=0;dx<m;dx++){
if(rPict[r][dy][dx]!=-1 && rPict[r][dy][dx]!=map[y+dy][x+dx]){
hit=false;
break;
}
}
if(hit==false) break;
}
if(hit==true){
tx=x+xTops[r];
ty=y+yTops[r];
if(ansY>ty || (ansY==ty && ansX>tx)){
ansY=ty;
ansX=tx;
}
}
}
}
}
if(ansY==101){
printf("NA\n");
}else{
printf("%d %d\n",ansX+1,ansY+1);
}
return true;
}
int main(){
while(setData()){
}
}
