「AOJ31～40」の編集履歴（バックアップ）一覧に戻る
AOJ31～40 - (2011/08/12 (金) 09:57:47) のソース
*0031 Weight
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0031&lang=jp
重さを2進数で求めるだけ。
アウトプット隙間の入れ方もう少し奇麗にならないかな。
#include<stdio.h>
int main(){
int n,p,c;
while(scanf("%d",&n)!=EOF){
p=c=1;
while(n!=0){
if(n&1==1){
printf("%s%d",c==1?"":" ",p);
c=2;
}
n/=2;
p*=2;
}
printf("\n");
}
}
----
*0032 Plastic Board
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0032&lang=jp
平行四辺形の型以外来ないので、形のチェックはしなくて済むというのがポイント。
後は中学校で習った公式通りあてはめるだけ。
#include <stdio.h>
int main(void){
int a,b,c,d=0,r=0;
while(scanf("%d,%d,%d",&a,&b,&c)!=EOF){
a*a+b*b==c*c?r++:a==b?d++:a;
}
printf("%d\n%d\n",r,d);
}
----
*0033 Ball
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0033
右の筒が左の筒より大きくなるように入れるという条件のもとボールを入れていくと上手くいく。
もし右が7で左が4でボールが8なら。
右にいれると8,4.
左に入れると7,8で右に入れた方がこのあとより多くのボールが入る。
よって右に入るか調べて駄目なら左に入るか調べてだめならお手上げ。
という操作を繰り返すことで答えが出る。
#include<stdio.h>
int main(){
int r,l,f,n,i,j,b;
scanf("%d",&n);
for(i=0;i<n;i++){
r=l=f=0;
for(j=0;j<10;j++){
scanf("%d",&b);
(b>r?r:b>l?l:f)=b;
}
printf("%s\n",f==0?"YES":"NO");
}
}
----
*0034 Railway Lines
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0034
すれ違うまでの時間tはt=路線の長さ/(v1+v2)で与えられ、ｔ秒目の位置は
l=ｔ*ｖ１で与えられる。
後はlがどの位置か調べるだけ。
小学生でも解ける簡単問題。
setを使えばもう少しコードが短くなるかな？
#include <stdio.h>
int main(){
double l[11],v1,v2,s;
l[0]=0;
while(scanf("%lf,",&l[1])!=EOF){
for(int i=2;i<11;i++){
scanf("%lf,",&l[i]);
l[i]+=l[i-1];
}
scanf("%lf,%lf",&v1,&v2);
s=v1*l[10]/(v1+v2);
for(int i=1;i<11;i++){
if(s<=l[i]){
printf("%d\n",i);
break;
}
}
}
}
----
0035 Is it Convex?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0035
最初、直線ＡＢで平面を区切った時ＣＤが同じ側に
ＢＣで区切った時Ａ，Ｄが同じ側にあるか、ＣＤで区切った時ＡＢが同じ側にあるという方法で解く。
今回のコードは多角形の上を一周する時凸多角形なら、点上での回転角の正負が常に正か負となるというのを利用した。
多角形の極限として閉曲線になる時、閉曲線にくぼみがないなら曲率の正負が入れ替わらないという問題と結び付くので中々興味深い問題。
#include <stdio.h>
int main(){
double xs[4],ys[4],a,t;
int p,np,ans;
while(scanf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf",&xs[0],&ys[0],&xs[1],&ys[1],&xs[2],&ys[2],&xs[3],&ys[3])!=EOF){
ans=a=t=0;
for(int i=0;i<4;i++){
p=(i+3)%4;
np=(i+1)%4;
t=(xs[i]-xs[p])*(ys[np]-ys[i])-(ys[i]-ys[p])*(xs[np]-xs[i]);
if(a*t<0){
ans=1;
break;
}else{
a=t;
}
}
if(ans==0){
printf("YES\n");
}else{
printf("NO\n");
}
}
}
----
*0036 A Figure on Surface
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0036
読まないでください。
やっつけで解いた適当コードです。
かなり質の悪い解法だと思います。
#include <stdio.h>
bool setMap();
int xs[7][4]={{0,1,0,1},{0,0,0,0},{0,1,2,3},{0,0,-1,-1},{0,1,1,2},{0,0,1,1},{0,1, 0,-1}};
int ys[7][4]={{0,0,1,1},{0,1,2,3},{0,0,0,0},{0,1, 1, 2},{0,0,1,1},{0,1,1,2},{0,0, 1, 1}};
int map[12][12];
int main(void)
{
while(setMap()){
}
}
bool setMap(){
char t;
int sx,sy;
bool hitCell=false;
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
scanf(" %c",&t);
map[i+1][j+1]=t-'0';
if(t=='1' && hitCell==false){
sx=j+1;
sy=i+1;
hitCell=true;
}
}
}
bool hit;
for(int i=0;i<7;i++){
hit=true;
for(int k=0;k<4;k++){
if(map[sy+ys[i][k]][sx+xs[i][k]]==0){
hit=false;
break;
}
}
if(hit==true){
printf("%c\n",i+'A');
break;
}
}
if(scanf("%c",&t)==EOF){
return false;
}
if(scanf("%c",&t)==EOF){
return false;
}
return true;
}
----
*0037 Path on a Grid
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0037
自力でパターン分けするのがめんどくさかったので
http://blog.livedoor.jp/kenyoi/archives/3995712.htmlをそのまま参考に
元にしたコードを縮めて作りました。
一見壁のどちら側にいるかが問題で向き*壁のどちらがわ＝8通りになるように思えます。
しかしこの問題見た目より簡単です。
図の上を北と見ると北に進んでいる時は壁の西側に、南に進んでいる時は壁の東側に
東に進んでいる時は壁の北側に、西に進んでいる時は壁の南側にいるので実は4通り
のむきだけ考えればいいのです。
#include <iostream>
using namespace std;
int map[11][7]={0},type=0,x=2,y=1;//type=0東向き、1南向き、２西向き、３北向き
char a[4],b[5];
void init(){
for(int i=1; i<=9; i++){
if(i%2){
cin>>a;
for(int n=0; n<4; n++)map[i][n+1] = char(a[n])-'0';
}
else {
cin>>b;
for(int m=0; m<5; m++)map[i][m+1] = char(b[m])-'0';
}
}
}
int cxs[]={0,0,0,-1};
int cys[]={-1,0,1,0};
int dxs[]={ 0,1,0,-1};
int dys[]={-2,0,2, 0};
char muki[]="URDL";
void Round(){
int p;
for(int i=type;i<4+type;i++){
p=i%4;
if(map[y+cys[p]][x+cxs[p]]==1){
type=(p+3)%4;
cout<<muki[p];
x+=dxs[p];
y+=dys[p];
return;
}
}
type=4;
}
void solve(){
while(!(x==1&&y==1)){
Round();
if(type==4) break;
}
}
int main(){
init();
cout<<'R';
solve();
cout<<"\n";
return 0;
}
*0038 Poker Hand
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0038
この問題役を求めるための簡単な2重ループ式があるそうですが知らなかったので自力で解きました。
結構コードが膨らみました。
まだまだ私未熟だなあと思った次第。
#include<stdio.h>
#include<map>
#include <algorithm>
#include <string>
int main(){
int k[5],t;
std::map<int,int> memo;
while(scanf("%d,%d,%d,%d,%d",&k[0],&k[1],&k[2],&k[3],&k[4])!=EOF){
memo.clear();
for(int i=0;i<5;i++){
t=k[i];
if(memo.find(t)==memo.end()){
memo[t]=1;
}else{
memo[t]++;
}
}
std::sort(k,k+5);
int m[5];
std::string ya;
std::map<int ,int>::iterator it;
if(memo.size()==5){
//ストレートまたは豚
if((k[0]+1==k[1] && k[1]+1==k[2] && k[2]+1==k[3] && k[3]+1==k[4]) || (k[0]==1 && k[1]==10 && k[2]==11 && k[3]==12 && k[4]==13)){
ya="straight";
}else{
ya="null";
}
}else if(memo.size()==2){
//フルハウスまたはフォーカード
it=memo.begin();
m[0]=(*it).second;
it++;
m[1]=(*it).second;
if((m[0]==2&&m[1]==3)||(m[0]==3&&m[1]==2)){
ya="full house";
}else{
ya="four card";
}
}else if(memo.size()==3){
//トゥーペアまたはスリーカード
it=memo.begin();
int max=0,l;
while(it!=memo.end()){
l=(*it).second;
max=max>l?max:l;
it++;
}
if(max==3){
ya="three card";
}else{
ya="two pair";
}
}else if(memo.size()==4){
//ワンペア
ya="one pair";
}
printf("%s\n",ya.c_str());
}
}
----
*0039 Roman Figure
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0039
工夫も何もありません、状態遷移マシーンに食わせて愚直に求めています。
#include <stdio.h>
#include <string.h>
#include <map>
int main(void){
int n;
int sum;
char in[102];
std::map<char,int> nos;
nos['I']=1;
nos['V']=5;
nos['X']=10;
nos['L']=50;
nos['C']=100;
nos['D']=500;
nos['M']=1000;
while(scanf("%s",in)!=EOF){
n=strlen(in);
sum=0;
if(n==1){
printf("%d\n",nos[in[0]]);
continue;
}
int i;
for(i=n-1;i>=1;){
if(nos[in[i-1]]>=nos[in[i]]){
sum+=nos[in[i]];
i--;
}else{
sum+=nos[in[i]]-nos[in[i-1]];
i-=2;
}
}
if(i==0){
sum+=nos[in[i]];
}
printf("%d\n",sum);
}
}
----
*0040 Affine Cipher
やるだけ問題でした。
cThisやcThatの方を変換して調べる方が効率はいいかもしれませんが実装が楽な方を選びました。
#include<stdio.h>
#include<string.h>
char calc(char t,int a,int b){
if(t>='a' && 'z'>=t){
return ((t-'a')*a+b)%26+'a';
}
return t;
}
int main(){
char cThat[5]="that",cThis[5]="this",text[257],ntext[257];
int num[]={0,1,3,5,7,9,11,15,17,19,21,23,25},len,n;
bool hit;
scanf("%d",&n);
for(int l=0;l<n;l++){
scanf(" %[^\n]",text);
len=strlen(text);
hit=false;
memset(ntext,'\0',257);
for(int i=0;i<13;i++){
for(int j=0;j<26;j++){
for(int k=0;k<len;k++){
ntext[k]=calc(text[k],num[i],j);
}
if(strstr(ntext,cThat)!=NULL || strstr(ntext,cThis)!=NULL){
hit=true;
break;
}
}
if(hit==true) break;
}
printf("%s\n",ntext);
}
}
