0031 Weight
この問題は錘の重さが1、２，４，８、16、、、と2^nであることを利用して解きます。
重さを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
解法
平行四辺形の型以外来ないので、形のチェックはしなくて済むというのがポイントです。
なので3平方の定理で直角三角形か調べ、でないなら菱形か調べ、でないなら何もしないというコードを書きます。
#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
解法
右の筒が左の筒より大きくなるように入れるという条件のもとボールを入れていくと上手くいきます。
右が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
解法
すれ違うまでの時間tはt=路線の長さ/(v1+v2)で与えられ、ｔ秒目の位置は
l=ｔ*ｖ１で与えられます。
後はlがどの位置か調べるだけです。
#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?
解法
多角形の線上を点が動いて一周する時凸多角形なら、頂点上での回転角の正負が常に正か負となるというのを利用して解けば簡単です。
少し変更すれば一般のＮ多角形の場合のヘコミも検出できるコードです。
多角形の極限として閉曲線になる時、閉曲線にくぼみがないなら曲率の正負が入れ替わらないという問題と結び付くので中々興味深い問題です。
#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
#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://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
解法
今回私は力づくでパタン分けして求めました。
特に特筆する内容もありません。
この問題役を求めるための簡単な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
#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
アフィン暗号で暗号化された文字を複合化する問題です。
暗号前野文章にはthatかthisが含まれているのでそれを手がかりに複合します。
解法
愚直に全探索しても間に合うので全複合を試すだけです。
この時無意味な複合は排除してnum[]にある値だけを試します。
#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);
}
}
最終更新：2011年09月06日 10:46
