「AOJ再挑戦問15～19」の編集履歴（バックアップ）一覧はこちら
「AOJ再挑戦問15～19」(2014/01/11 (土) 08:49:59) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問15 National Budget
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0015
80桁までの整数足し算を実装する問題。
解法
多桁計算として実装するのが正しいと思いますが数字を文字列に変換して解きました。
80桁の右詰0埋め文字列に加工して右の桁から左の桁へ足し算をしていきます。
コードが膨らんだのですが賢い方法はあるものでしょうか？
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
const int lenLimit=82;
void sideRight(char *str,char *result){
int len=strlen(str);
memset(result,'0',lenLimit-1);
result[lenLimit-1]='\0';
memcpy(result+(lenLimit-len-1),str,len);
}
void add(char *A,char *B,char *result){
memset(result,'0',lenLimit-1);
result[lenLimit-1]='\0';
int add=0,t;
for(int i=lenLimit-2;i>=0;i--){
t=A[i]+B[i]+add-2*'0';
result[i]=t%10+'0';
add=t/10;
}
}
void myprint(char *ans){
if(ans[0]!='0'){
printf("overflow\n");
}else{
int p;
for(p=0;p<lenLimit-2&&ans[p]=='0';p++);
for(;p<lenLimit-1;p++){
printf("%c",ans[p]);
}
printf("\n");
}
}
int main(){
int n;
scanf("%d",&n);
while(n--){
char t1[512],t2[512];
char a[lenLimit],b[lenLimit],
sideA[lenLimit],sideB[lenLimit],
Ans[lenLimit];
scanf("%s %s",t1,t2);
if(strlen(t1)>80 || strlen(t2)>80){
printf("overflow\n");
}else{
sprintf(a,"%s",t1);
sprintf(b,"%s",t2);
sideRight(a,sideA);
sideRight(b,sideB);
//printf("%s\n%s\n",sideA,sideB);
add(sideA,sideB,Ans);
//printf("%s",Ans);
myprint(Ans);
}
}
*問16Treasure Hunt
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0016
宝探しを題材にした問題。
**解法
指定通り回転と移動の計算を繰り返すだけです。
三角関数を使えば簡単ですね。
#include<stdio.h>
#include<math.h>
int main(){
double nowX=0,nowY=0,len;
int dr,r=90;
while(1){
scanf("%lf,%d",&len,&dr);
if(len==0&&dr==0)break;
nowX+=len*cos(r/180.0*M_PI);
nowY+=len*sin(r/180.0*M_PI);
r=r-dr;
}
printf("%d\n%d\n",(int)nowX,(int)nowY);
}
*問17 Caesar Cipher
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0017
シーザー暗号を復元する問題。
解法
一行丸ごと読み込んでthisやtheのほうをずらして探します、this,,,という単語を排除するために後ろに空白やピリオドをつけました。。
これも問15と同じくコードが膨らんでる、もうちょっと短くなりそうだけど？
#include<stdio.h>
#include<string.h>
int main(){
char line[82];
while(gets(line)!=NULL){
char words[6][6]={"this ","the ","that ","this.","the.","that."};
int s;
for(s=1;s<27;s++){
for(int j=0;j<6;j++){
for(int k=0;k<strlen(words[j])-1;k++){
words[j][k]=(words[j][k]-'a'+1)%26+'a';
}
}
bool hit=false;
for(int j=0;j<6;j++){
if(strstr(line,words[j])!=NULL)hit=true;
}
if(hit==true)break;
}
s=26-s;
for(int i=0;i<strlen(line);i++){
if(line[i]==' '||line[i]=='.')printf("%c",line[i]);
else printf("%c",(line[i]-'a'+s)%26+'a');
}
printf("\n");
}
}
*問18 Sorting Five Numbers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0018
5つの数字を降順に出力するだけの問題。
解法
std::sortで一発。
#include<stdio.h>
#include<algorithm>
#include <functional>
int main(){
int ns[5];
for(int i=0;i<5;i++)scanf("%d",&ns[i]);
std::sort(ns,ns+5,std::greater<int>());
for(int i=0;i<5;i++)printf("%d%c",ns[i],i==4?'\n':' ');
}
*問15 National Budget
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0015
80桁までの整数足し算を実装する問題。
解法
多桁計算として実装するのが正しいと思いますが数字を文字列に変換して解きました。
80桁の右詰0埋め文字列に加工して右の桁から左の桁へ足し算をしていきます。
コードが膨らんだのですが賢い方法はあるものでしょうか？
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
const int lenLimit=82;
void sideRight(char *str,char *result){
int len=strlen(str);
memset(result,'0',lenLimit-1);
result[lenLimit-1]='\0';
memcpy(result+(lenLimit-len-1),str,len);
}
void add(char *A,char *B,char *result){
memset(result,'0',lenLimit-1);
result[lenLimit-1]='\0';
int add=0,t;
for(int i=lenLimit-2;i>=0;i--){
t=A[i]+B[i]+add-2*'0';
result[i]=t%10+'0';
add=t/10;
}
}
void myprint(char *ans){
if(ans[0]!='0'){
printf("overflow\n");
}else{
int p;
for(p=0;p<lenLimit-2&&ans[p]=='0';p++);
for(;p<lenLimit-1;p++){
printf("%c",ans[p]);
}
printf("\n");
}
}
int main(){
int n;
scanf("%d",&n);
while(n--){
char t1[512],t2[512];
char a[lenLimit],b[lenLimit],
sideA[lenLimit],sideB[lenLimit],
Ans[lenLimit];
scanf("%s %s",t1,t2);
if(strlen(t1)>80 || strlen(t2)>80){
printf("overflow\n");
}else{
sprintf(a,"%s",t1);
sprintf(b,"%s",t2);
sideRight(a,sideA);
sideRight(b,sideB);
//printf("%s\n%s\n",sideA,sideB);
add(sideA,sideB,Ans);
//printf("%s",Ans);
myprint(Ans);
}
}
*問16Treasure Hunt
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0016
宝探しを題材にした問題。
**解法
指定通り回転と移動の計算を繰り返すだけです。
三角関数を使えば簡単ですね。
#include<stdio.h>
#include<math.h>
int main(){
double nowX=0,nowY=0,len;
int dr,r=90;
while(1){
scanf("%lf,%d",&len,&dr);
if(len==0&&dr==0)break;
nowX+=len*cos(r/180.0*M_PI);
nowY+=len*sin(r/180.0*M_PI);
r=r-dr;
}
printf("%d\n%d\n",(int)nowX,(int)nowY);
}
*問17 Caesar Cipher
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0017
シーザー暗号を復元する問題。
解法
一行丸ごと読み込んでthisやtheのほうをずらして探します、this,,,という単語を排除するために後ろに空白やピリオドをつけました。。
これも問15と同じくコードが膨らんでる、もうちょっと短くなりそうだけど？
#include<stdio.h>
#include<string.h>
int main(){
char line[82];
while(gets(line)!=NULL){
char words[6][6]={"this ","the ","that ","this.","the.","that."};
int s;
for(s=1;s<27;s++){
for(int j=0;j<6;j++){
for(int k=0;k<strlen(words[j])-1;k++){
words[j][k]=(words[j][k]-'a'+1)%26+'a';
}
}
bool hit=false;
for(int j=0;j<6;j++){
if(strstr(line,words[j])!=NULL)hit=true;
}
if(hit==true)break;
}
s=26-s;
for(int i=0;i<strlen(line);i++){
if(line[i]==' '||line[i]=='.')printf("%c",line[i]);
else printf("%c",(line[i]-'a'+s)%26+'a');
}
printf("\n");
}
}
*問18 Sorting Five Numbers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0018
5つの数字を降順に出力するだけの問題。
解法
std::sortで一発。
#include<stdio.h>
#include<algorithm>
#include <functional>
int main(){
int ns[5];
for(int i=0;i<5;i++)scanf("%d",&ns[i]);
std::sort(ns,ns+5,std::greater<int>());
for(int i=0;i<5;i++)printf("%d%c",ns[i],i==4?'\n':' ');
}
*問19 Factorial
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0019
階上計算する問題。
解法
定義そのまま、double型を使えば2^51までの整数はきちんと問題なく計算できるのでこれで計算。
#include<stdio.h>
int main(){
int n;
scanf("%d",&n);
double fact[21];
fact[0]=fact[1]=1;
for(int i=2;i<=n;i++)fact[i]=fact[i-1]*i;
printf("%.0lf\n",fact[n]);
}
