2000 Misterious Gems
#include<stdio.h>
#include<string.h>
void setData(int n){
bool map[22][22];
int x,y,ans=0,m,d,r;
char s[2];
memset(map,false,sizeof(map));
for(int i=0;i<n;i++){
scanf("%d %d",&x ,&y);
map[y][x]=true;
}
scanf("%d",&m);
char v[4]={'E','N','W','S'};
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
x=y=10;
while(m--){
scanf("%s %d",s,&d);
for(r=0;r<4;r++)if(s[0]==v[r])break;
//ここもちょっと綺麗にならないかな。
ans+=map[y][x];
map[y][x]=false;
while(d--){
ans+=map[y+=dys[r]][x+=dxs[r]];
map[y][x]=false;
}
}
printf("%s\n",ans==n?"Yes":"No");
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
setData(n);
}
}
2001 Amida, the City of Miracle
あみだくじをシミュレートする問題。
あみだを題材にした問題の中では一番簡単な部類。
何も考えず書いて上の下にランクイン。
#include<stdio.h>
#include<algorithm>
struct bar{
int h,p,q;
bool operator<(const bar& b)const{
return h>b.h;
}
};
void setData(int m,int a){
bar b,bars[1002];
for(int i=0;i<m;i++){
scanf("%d %d %d",&b.h, &b.p, &b.q);
bars[i]=b;
}
std::sort(bars,bars+m);
for(int i=0;i<m;i++){
b=bars[i];
a=a==b.p?b.q:a==b.q?b.p:a;
}
printf("%d\n",a);
}
int main(){
int n,m,a;
while(1){
scanf("%d %d %d",&n,&m,&a);
if(a==0)break;
setData(m,a);
}
}
2002 X-Ray Screening System
#include<stdio.h>
#include<string.h>
#include <algorithm>
struct Goods{
int lx,ty,rx,dy;//左上、右下
bool spents;//調査済み
char type;//材質
};
char map[52][52];//マップ
int layered[52][52];//そのセルに材質がいくつ重なっているか
int maxType;//見つかった材質の種類
Goods goods[10];//グッズの左上から右下までの座標保持
bool checkBad;
void saiki(int deep){
if(deep==maxType){
checkBad=false;
}else{
for(int i=0;i<maxType;i++){
Goods g=goods[i];
if(g.spents==false){
//未使用だったので長方形の範囲を調べる
bool ok=true;
for(int y=g.ty;y<=g.dy;y++){
for(int x=g.lx;x<=g.rx;x++){
if(layered[y][x]==0&&g.type!=map[y][x]){
ok=false;//長方形に足りない部分が見つかった
}
layered[y][x]++;
}
}
goods[i].spents=true;
if(ok==true)saiki(deep+1);//長方形だったので次へ行く
if(checkBad==false)return;
goods[i].spents=false;
for(int y=g.ty;y<=g.dy;y++){
for(int x=g.lx;x<=g.rx;x++){
layered[y][x]--;
}
}
}
}
}
}
void setData(){
int h,w;
int hit[30];//A~Zの文字がヒットしたか
checkBad=true;
scanf("%d %d",&h,&w);
maxType=0;//ヒットした材質の数
memset(layered,0,sizeof(layered));//重なりの初期化
memset(hit,-1,sizeof(hit));
Goods g,*tg;
g.lx=g.ty=100;
g.rx=g.dy=-1;
g.spents=false;
for(int i=0;i<10;i++){
goods[i]=g;//ダミーデータを入れておく
}
for(int r=0;r<h;r++){
scanf("%s",map[r]);
for(int x=0;x<w;x++){
char c=map[r][x];
if(c<'A'||'Z'<c)continue;
c-='A';
if(hit[c]==-1){
hit[c]=maxType;
goods[hit[c]].type=c+'A';
maxType++;
}
tg=&(goods[hit[c]]);
(*tg).lx=std::min((*tg).lx,x);
(*tg).rx=std::max((*tg).rx,x);
(*tg).ty=std::min((*tg).ty,r);
(*tg).dy=std::max((*tg).dy,r);
}
}
for(int i=0;i<maxType;i++){
g=goods[i];
//printf("%c lx=%d ty=%d rx=%d dy=%d \n",g.type,g.lx,g.ty,g.rx,g.dy);
}
saiki(0);
printf("%s\n",checkBad==false?"SAFE":"SUSPICIOUS");
}
int main(){
int n;
scanf("%d",&n);
while(n--)setData();
}
2003 Railroad Conflict
解法
幾何の問題なので公式通り線分の交差判定で交差をチェックし交差するなら媒介変数表示の値で交点を並べます。
後は状態遷移マシンに食わせておしまいです。
問題自体は簡単ですが幾何の判定は基本的にめんどくさいのでコードが長くなっています。
#include<stdio.h>
#include<queue>
#include<iostream>
struct cross{
long double t;
int type,cType;
bool operator<(const cross& c)const{
return t>c.t;
}
};
double calcS(double xa,double ya,double xb,double yb,double x1,double y1){
return (x1-xa)*(yb-ya)-(xb-xa)*(y1-ya);
}
int calc(){
long double xa,ya,xb,yb,xs1,xs2,ys1,ys2,s1,s2,s3,s4,Ax,Ay,Bx,By,Cx,Cy,Dx,Dy;
std::priority_queue<cross> qu;
std::cin>>xa>>ya>>xb>>yb;
cross c,c1;
int size;
scanf("%d",&size);
for(int i=0;i<size;i++){
std::cin>>xs1>>ys1>>xs2>>ys2>>c.cType>>c.type;
s1=calcS(xa,ya,xb,yb,xs1,ys1);
s2=calcS(xa,ya,xb,yb,xs2,ys2);
s3=calcS(xs1,ys1,xs2,ys2,xa,ya);
s4=calcS(xs1,ys1,xs2,ys2,xb,yb);
if(s1*s2<0&&s3*s4<0){
Ax=xa;
Ay=ya;
Bx=xb;
By=yb;
Cx=xs1;
Cy=ys1;
Dx=xs2;
Dy=ys2;
c.t=((Dy-Cy)*(Cx-Ax)-(Dx-Cx)*(Cy-Ay))/((Bx - Ax)*(Dy-Cy)-(By-Ay)*(Dx-Cx));
qu.push(c);
}
}
if(qu.empty()==true)return 0;
c=qu.top();
qu.pop();
int gType=c.type;
if(c.cType==0)gType=!gType;
int ans=0;
while(qu.empty()==false){
c1=qu.top();
qu.pop();
if(c1.cType==0){
if(c1.type==gType){
ans++;
gType=!gType;
}
}else{
if(c1.type!=gType){
ans++;
gType=!gType;
}
}
}
return ans;
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
printf("%d\n",calc());
}
}
2005 Water Pipe Construction
水が一方通行であることに注意しながらワーシャルフロイド法で全2地点間を結ぶ最短コストを求めます。
後は基地、水道管の分岐点、目的基地までを結ぶ3つの最短経路の計が最小化される道を探すだけです。
#include<stdio.h>
#include<string.h>
#include<algorithm>
void wf(int con[101][101],int n){
//ワーシャルフロイド法で全基地の最小距離を求める
int t;
for(int y=1;y<=n;y++){
for(int x=1;x<=n;x++){
if(con[x][y]==-1)continue;
for(int i=1;i<=n;i++){
if(con[y][i]==-1)continue;
t=con[x][y]+con[y][i];
if(con[x][i]==-1||con[x][i]>t){
con[x][i]=t;
}
}
}
}
}
bool setData(){
int n,m,s,g1,g2,con[101][101],b1,b2,c;
scanf("%d %d %d %d %d",&n,&m,&s,&g1,&g2);
if(n==0&&m==0&&s==0&&g1==0&&g2==0)return false;
memset(con,-1,sizeof(con));
for(int i=0;i<m;i++){
scanf("%d %d %d",&b1,&b2,&c);
con[b1][b2]=c;
}
for(int i=1;i<=n;i++)con[i][i]=0;
wf(con,n);
int ans=2000000000,t;
for(int i=1;i<=n;i++){
if(con[i][g1]!=-1&&con[i][g2]!=-1&&con[s][i]!=-1){
t=con[i][g1]+con[i][g2]+con[s][i];
ans=std::min(ans,t);
}
}
printf("%d\n",ans);
return true;
}
int main(){
while(setData());
}
2006 Keitai Message
解法
マトリックスを用意して状態遷移マシーンを回すだけです。
#include<stdio.h>
void change(){
char text[1030];
scanf("%s",text);
char no='0',c;
int count=0;
char word[10][7]={"",".,!? ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
for(int i=0;text[i]!='\0';i++){
c=text[i];
if(no!='0'&&c=='0'){
printf("%c",word[no-'0'][count]);
no=c;
count=0;
}
if(no=='0'&&c=='0'){
count=0;
}
if(no!='0'&&c!='0'){
count++;
if(word[no-'0'][count]=='\0')count=0;
}
if(no=='0'&&c!='0'){
no=c;
count=0;
}
}
printf("\n");
}
int main(){
int n;
scanf("%d",&n);
while(n--){
change();
}
}
最終更新:2013年01月12日 16:30