0071 Bombs Chain
#include<stdio.h>
char map[9][9];
void saiki(int x,int y){
int nx,ny;
for(int i=-3;i<4;i++){
nx=x+i;
ny=y;
if(8>nx && nx>-1 && map[ny][nx]=='1'){
map[ny][nx]='0';
saiki(nx,ny);
}
nx=x;
ny=y+i;
if(ny>7 || ny<0) continue;
if(map[ny][nx]=='1'){
map[ny][nx]='0';
saiki(nx,ny);
}
}
}
void setMap(int no){
for(int i=0;i<8;i++){
scanf("%s",map[i]);
}
int sx,sy;
scanf("%d %d",&sx,&sy);
saiki(sx-1,sy-1);
printf("Data %d:\n",no+1);
for(int i=0;i<8;i++){
printf("%s\n",map[i]);
}
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
setMap(i);
}
}
0072 Carden Lantern
解法
典型的なプリム法の問題です。
最初に解いた時はプリム法を知らず、プリム法と同じ方法を自力で思いついて実装したのでコードが上手くいくかドキドキものだった印象的な問題です。
その時のコードは正解でした。
ここに掲載のコードは最初のコードの高速化を目指して少しコードを弄っています。
#include<stdio.h>
#include<queue>
#include<vector>
struct load{
int p1,p2,len;
bool operator<(const load l)const{
return len>l.len;
}
};
void setMap(int n,int m){
int points[101]={0};
std::priority_queue<load> loads;
std::vector<load> map[101];
std::vector<load>::iterator it,end;
load l,start;
start.len=2000000000;
for(int i=0;i<m;i++){
scanf("%d,%d,%d",&l.p1,&l.p2,&l.len);
l.len=l.len/100-1;
map[l.p1].push_back(l);
map[l.p2].push_back(l);
start=l.len<start.len?l:start;
}
int count=1,ans=0,addOK;
loads.push(start);
while(n>count && loads.empty()==false){
l=loads.top();
loads.pop();
addOK=false;
if(points[l.p1]==0){
addOK=true;
points[l.p1]=1;
it=map[l.p1].begin();
end=map[l.p1].end();
while(it!=end){
loads.push(*it);
it++;
}
}
if(points[l.p2]==0){
addOK=true;
points[l.p2]=1;
it=map[l.p2].begin();
end=map[l.p2].end();
while(it!=end){
loads.push(*it);
it++;
}
}
if(addOK==true){
count++;
ans+=l.len;
}
}
printf("%d\n",ans);
}
int main(){
int n,m;
scanf("%d",&n);
while(n!=0){
scanf("%d",&m);
setMap(n,m);
scanf("%d",&n);
}
}
0073 Surface Area of Quadrangular Pyramid
#include<stdio.h>
#include<math.h>
int main(){
double x,h;
while(1){
scanf("%lf %lf",&x,&h);
if(x==0&&h==0) break;
printf("%lf\n",x*(x+2*sqrt(h*h+x*x/4.0)));
}
}
0074 Videotape
#include<stdio.h>
int main(){
int h,m,s,max=7200,t,u;
while(1){
scanf("%d %d %d",&h,&m,&s);
if(h==-1 && m==-1 && s==-1) break;
u=h*3600+m*60+s;
t=max-u;
printf("%02d:%02d:%02d\n",t/3600,t%3600/60,t%60);
t*=3;
printf("%02d:%02d:%02d\n",t/3600,t%3600/60,t%60);
}
}
0075 BMI
#include<stdio.h>
int main(){
int no;
double kg,m;
while(scanf("%d,%lf,%lf",&no,&kg,&m)!=EOF){
kg/(m*m)>=25?printf("%d\n",no):m;
}
}
0076 Treasure Hunt II
#include<stdio.h>
#include<math.h>
int main(){
double xs[1001],ys[1001],len;
xs[0]=1;
ys[0]=0;
for(int i=1;i<1001;i++){
len=sqrt(xs[i-1]*xs[i-1]+ys[i-1]*ys[i-1]);
xs[i]=-ys[i-1]/len+xs[i-1];
ys[i]=xs[i-1]/len+ys[i-1];
}
int n;
while(1){
scanf("%d",&n);
if(n==-1)break;
printf("%lf\n%lf\n",xs[n-1],ys[n-1]);
}
}
0077 Run Length
解法
変換するパイプに通すだけでできます。
@を見つけたら2つ次の文字を一つ次の数字だけ出力しポインタを2つ進める。
普通の文字ならそのまま出力して次の文字へ。
#include<stdio.h>
#include<string.h>
int main(){
char text[101];
while(scanf("%s",text)!=EOF){
int len=strlen(text);
for(int i=0;i<len;i++){
if(text[i]=='@'){
for(int j=0;j<text[i+1]-'0';j++){
printf("%c",text[i+2]);
}
i+=2;
}else{
printf("%c",text[i]);
}
}
printf("\n");
}
}
0078 Magic Square
#include<stdio.h>
void set(int n){
int map[15][15]={0},size=n*n,x,y,i;
x=y=n/2;
y++;
map[y][x]=1;
i=1;
while(i<size){
x=(x+1)%n;
y=(y+1)%n;
i++;
if(map[y][x]==0){
map[y][x]=i;
}else{
x=(x+n-1)%n;
y=(y+1)%n;
map[y][x]=i;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)printf("%4d",map[i][j]);
printf("\n");
}
}
int main(){
int n;
scanf("%d",&n);
while(n!=0){
set(n);
scanf("%d",&n);
}
}
0079 Area of Polygon
#include<stdio.h>
int main(){
double xs[2],ys[2],ans=0,sx,sy;
int i=1;
scanf("%lf,%lf",&sx,&sy);
xs[0]=sx;
ys[0]=sy;
while(scanf("%lf,%lf",&xs[i],&ys[i])!=EOF){
i++;
i%=2;
ans+=(xs[i]-xs[(i+1)%2])*(ys[i]+ys[(i+1)%2]);
}
ans+=(xs[(i+1)%2]-sx)*(sy+ys[(i+1)%2]);
ans/=2;
printf("%lf\n",ans<0?-ans:ans);
}
0080 Third Root
#include<stdio.h>
#include<math.h>
int main(){
double x,q;
scanf("%lf",&q);
while(q!=-1){
x=q/2.0;
while(fabs(x*x*x-q)>=0.00001*q){
x=x-(x*x*x-q)/(3*x*x);
}
printf("%lf\n",x);
scanf("%lf",&q);
}
}
最終更新:2011年08月29日 13:19