2014年4月14日月曜日

会津大学オンラインジャッジ　問129　

Hide-and-Seek Supporting System
かくれんぼを題材にした問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0129

特にショートコードを狙ったわけではないがコード短さ１５/168位。
まあまあの結果だと思う、この問題では昔この問題を解いたときに書いたコードを抜けた気がする。
この問題でもpldwさんがコードの短さで突出している。
彼（彼女？）はいったいどんな人物なのだろう。

#include<stdio.h>
#include<math.h>

int main(){
int n,m;

while(scanf("%d",&n)!=EOF){
if(n==0)break;
double wallXs[101],wallYs[101],wallRs[101],px,py,ex,ey,lenP,lenE,r;
double pDx,pDy,eDx,eDy,peDx,peDy,n1,n2,len3,peLen;
for(int i=0;i<n;i++){
scanf("%lf %lf %lf",&wallXs[i],&wallYs[i],&wallRs[i]);
}
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%lf %lf %lf %lf",&px,&py,&ex,&ey);
bool danger=true;
for(int j=0;j<n;j++){
pDx=wallXs[j]-px;
pDy=wallYs[j]-py;
eDx=wallXs[j]-ex;
eDy=wallYs[j]-ey;
lenP=hypot(pDx,pDy);
lenE=hypot(eDx,eDy);
r=wallRs[j];
//自分と相手が円の内と外の関係
if((lenP<r&&lenE>r)||(lenP>r&&lenE<r)){
danger=false;
break;
}
//同じ円内にいる
if(lenP<r&&lenE<r){
continue;
}
//円から線分へおろした垂線と重なる直線。これからなる半開平面の両側に自分と相手がいるかチェック
peDx=ex-px;
peDy=ey-py;
peLen=hypot(peDx,peDy);
n1=peDx*pDx+peDy*pDy;
n2=peDx*eDx+peDy*eDy;
if((n1<0&&n2>0)||(n1>0&&n2<0)){
len3=fabs((pDx*peDy-pDy*peDx)/peLen);
//両側にいたので線分と円の距離が条件を満たすか調べる
if(len3<=r){
danger=false;
break;
}
}
}
printf("%s\n",danger?"Danger":"Safe");
}
}
}

会津大学オンラインジャッジ　問128　Abacus

Abacus
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0128
そろばんを題材にした問題。

この問題そろばんを９０度回して、全部*で埋めている状態から*を削ってそろばんの一つの列（９０度まわしてるから行だけど）を生成すると考えると綺麗に解けます。
というか昔の自分はそうやって解いたようです。

うーんＡＯＪの問題を復習中なのですが昔の自分のコードに勝てる気がしない。
Ｐｒｏｌｏｇ言語のやりすぎでなんでも列挙する方向だけから考えるという悪い癖がついたな。
昔の自分のほうがアプローチが柔軟だ。

昔のコード。
#include<stdio.h>
#include<string.h>
void change(int num,char* re){
//*をけずって一列を作る処理
strcpy(re,"**=*****");
re[-(num/5-1)]=' ';
re[num%5+3]=' ';
}
int main(){
char ans[5][9];
int n,c=0;
while(scanf("%d",&n)!=EOF){
printf("%s",c==0?"":"\n");
c++;
for(int i=4;i>=0;i--){
change(n%10,ans[i]);
n/=10;
}
//縦と横を元に戻して表示
for(int i=0;i<8;i++){
for(int j=0;j<5;j++)printf("%c",ans[j][i]);
printf("\n");
}
}
}

会津大学オンラインジャッジ　問127　Pocket Pager Input

ポケベルを題材にした問題。
今の若者にポケベルは通用するのだろうか？
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0127

ＡＯＪの問題を復習中でこの問題もその一つなのですが。
昔自分が書いたコードのほうが賢かったので賢いほうを掲載。
なるほど文字数が合わなければ途中で処理に失敗してるわけか。
昔の自分賢いな、感心。
今の自分頭悪いな。

#include<stdio.h>
#include<string.h>

char memo[6][6]={"abcde","fghij","klmno","pqrst","uvwxy","z.?! "};

int main(){
char mes[201],ans[101];
int p,len,t1,t2;
while(scanf("%s",mes)!=EOF){
len=strlen(mes);
p=0;
if(len%2==0){
while(p<len){
t1=mes[p];
t2=mes[p+1];
if(t1<'1' || '6'<t1 || t2<'1' || '5'<t2){
break;
}else{
ans[p/2]=memo[t1-'1'][t2-'1'];
p+=2;
}
}
}
ans[len/2]='\0';
printf("%s\n",p>=len?ans:"NA");
}
}

2014年4月12日土曜日

会津大学オンラインジャッジ　問126

Puzzle

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0126
数独で間違った回答の間違ってる部分にチェックをつける問題。

行、列　３*３で数えて２つ以上重なってるものに*をつけるだけです。
結構エレガントに書けた気はするがショートコーダーから見たらきっとこのコードは長い。
７００バイト１２位、特にショートコードを狙ったわけでもないのでまあまあの順位に思えるが。
１位は２６４バイトなので２位以下か１位かという区別しか意味がない。

#include<stdio.h>
#include<string.h>

void check(){
int rows[9][10],cols[9][10],cell33[3][3][10];
int board[9][9],num;
memset(cell33,0,sizeof(cell33));
memset(rows,0,sizeof(rows));
memset(cols,0,sizeof(cols));

for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
scanf("%d",&num);
rows[i][num]++;
cols[j][num]++;
cell33[i/3][j/3][num]++;
board[i][j]=num;
}
}
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
int num=board[i][j];
if(rows[i][num]>1||cols[j][num]>1||cell33[i/3][j/3][num]>1){
printf("*%d",num);
}else{
printf(" %d",num);
}
}
printf("\n");
}
}

int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
check();
if(i+1<n)printf("\n");
}
}

会津大学オンラインジャッジ　問125

Day Count
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0125
２つの日付の間の日数をこたえる問題。

ネット上に転がっていた日数計算公式をそのまま採用。
http://ufcpp.net/study/algorithm/o_days.html

#include<stdio.h>
int calcDays(int y,int m,int d){
if(m<=2){
--y;
m+=12;
}
int dy=365*(y-1);
int c=y/100;
int dl=(y>>2)-c+(c>>2);
int dm=(m*979-1033)>>5;
return dy+dl+dm+d-1;
}

int main(){
int y,m,d,y1,m1,d1;
while(scanf("%d %d %d %d %d %d",&y,&m,&d,&y1,&m1,&d1)!=EOF){
if(y1==-1)break;
printf("%d\n",calcDays(y1,m1,d1)-calcDays(y,m,d));
}
}

会津大学オンラインジャッジ　問124

League Match Score Sheet

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0124
サッカー試合のスコアを計算する問題。

#include<stdio.h>
#include<string>
#include<iostream>
#include<queue>

struct S{
std::string name;
int score,no;
bool operator<(const S& s)const{
if(score!=s.score)return score<s.score;
return no>s.no;
}
};

void rank(int n){
S s;
int v,loss,b;
std::priority_queue<S> pq;
for(int i=0;i<n;i++){
std::cin>>s.name>>v>>loss>>b;
s.no=i;
s.score=v*3+b;
pq.push(s);
}
while(pq.empty()==false){
s=pq.top();
pq.pop();
std::cout<<s.name<<","<<s.score<<"\n";
}

}

int main(){
int n,c=0;
while(scanf("%d",&n)!=EOF){
if(n==0)break;
if(c>0)printf("\n");
rank(n);
c++;
}
}

会津大学オンラインジャッジ　問123

Speed Skating Badge Test

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0123
スピードスケートのランク付けを行う問題。
500ｍでＡＡランクなら1000ｍでＡＡＡをとっても意味がない。
これを利用して1000m判定のｒ２の検証を減らします。
こういう簡単な判定では意味がありませんが重たい判定ではこういう小手先のテクニックもすこしは役に立つかもしれません。
まあその前にバイナリサーチを導入するとは思いますが。

#include<stdio.h>

int main(){
char kekka[8][4]={
"AAA",
"AA",
"A",
"B",
"C",
"D",
"E",
"NA"};
double M500[8] ={35.5,37.5,40,43,50,55,70};
double M1000[8]={71,77,83,89,105,116,148};
double t500,t1000;
while(scanf("%lf %lf",&t500,&t1000)!=EOF){
int r1=7,r2=7;
for(int i=0;i<7;i++){
if(t500<M500[i]){
r1=i;
break;
}
}
for(int i=r1;i<7;i++){
if(t1000<M1000[i]){
r2=i;
break;
}
}
printf("%s\n",kekka[r2]);
}
}