「AOJ1100～1109」の編集履歴（バックアップ）一覧に戻る
AOJ1100～1109 - (2013/01/16 (水) 10:17:20) のソース
*1105 Unable Count
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1105
n a bの３数が与えられるのでnまでの自然数をax+by(x,yは0以上の自然数)(a,bは多分1以上の自然数)の形であらわしたとき、この式で表せない数の個数を求めよという問題。
妙に言葉遊びで遊んでいる問題文は出題者の趣味？
解法
とりあえずナップザック問題の応用で解いてみましたがメモリを馬鹿みたいに使ってます。
#include<stdio.h>
#include<iostream>
#include<string.h>
int memo[1000*1000+1];
int main(){
int n,a,b;
while(1){
int ans=0;
std::cin>>n>>a>>b;
if(n==0&&a==0&&b==0)break;
memset(memo,0,sizeof(memo));
memo[0]=1;
if(a==1||b==1){
printf("0\n");
}else{
for(int i=0;i+a<=n;i++){
memo[i+a]|=memo[i];
}
for(int i=0;i+b<=n;i++){
memo[i+b]|=memo[i];
}
for(int i=1;i<=n;i++){
if(memo[i]==0)ans++;
}
printf("%d\n",ans);
}
}
}
*1107 Spiral Footrace
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1107
平面上の地点が与えられるので、外側から初めて螺旋を描きながらすべての地点を通って最後に真中の地点に到達するとき、そのコースの距離を小数点一ケタの精度で答えよという問題。
出発点は(0,0)座標、北向きとする。
解法
螺旋を描きながら中心まで向かうので、コース候補となる線分を延長して直線とし、その直線の半開平面の片側にまだ通ってない地点が全て集まるならそのコースは結んでも良いコースとなります。
半開平面のどちらにあるかは外積で答えがでます。
#include<stdio.h>
#include<math.h>
int main(){
while(1){
double tempLen,ans=0,oldX=0,oldY=0;
int n,spents[401]={0},no;
double xs[401],ys[401];
scanf("%d",&n);
if(n==0)break;
for(int i=0;i<n;i++){
scanf("%lf %lf",&xs[i],&ys[i]);
}
for(int i=0;i<n;i++){
tempLen=500.0*500.0*3;
int no;
for(int j=0;j<n;j++){
if(spents[j]==1)continue;
double dx1=xs[j]-oldX;
double dy1=ys[j]-oldY;
double nowLen=dx1*dx1+dy1*dy1;
bool ok=true;
for(int k=0;k<n;k++){
if(spents[k]==1||j==k)continue;
double dx2=xs[k]-oldX;
double dy2=ys[k]-oldY;
double g=dx1*dy2-dy1*dx2;
if(g>0){
ok=false;
break;
}
}
if(ok==true&&tempLen>nowLen){
no=j;
tempLen=nowLen;
}
}
oldX=xs[no];
oldY=ys[no];
spents[no]=1;
ans+=sqrt(tempLen);
}
printf("%.1lf\n",ans);
}
}
*1108 A Long Ride on a Railway
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1108
路線図と駅間の距離？がグラフの形で与えられるので同じルートを一度しか通らないという条件で最も距離の稼げる経路とその距離を求めよトいう問題。
解法
点の数が少ないので深さ優先探索で探して十分間に合います。
同じ地点を何度通っても良いのがポイントです。
#include<stdio.h>
#include<vector>
#include<string.h>
int ans,ns,nl;
int G[11][11];
std::vector<int> ansRoute;
void saiki(int nowP,std::vector<int>& route,int cost){
if(cost>ans){
ans=cost;
ansRoute.clear();
ansRoute.insert(ansRoute.begin(),route.begin(),route.end());
}
for(int i=1;i<=ns;i++){
if(nowP==0||G[nowP][i]!=0){
int t=G[nowP][i];
G[nowP][i]=G[i][nowP]=0;
route.push_back(i);
saiki(i,route,cost+t);
route.pop_back();
G[nowP][i]=G[i][nowP]=t;
}
}
}
void calc(){
int a,b,c;
ans=0;
memset(G,0,sizeof(G));
for(int i=0;i<nl;i++){
scanf("%d %d %d",&a,&b,&c);
G[a][b]=G[b][a]=c;
}
std::vector<int> route;
ansRoute.clear();
saiki(0,route,0);
printf("%d\n",ans);
for(unsigned int i=0;i<ansRoute.size();i++){
if(i>0)printf(" ");
printf("%d",ansRoute[i]);
}
printf("\n");
}
int main(){
while(1){
scanf("%d %d",&ns,&nl);
if(ns==0&&nl==0)break;
calc();
}
}
