「AOJ再挑戦111～115」の編集履歴（バックアップ）一覧はこちら
「AOJ再挑戦111～115」(2014/02/08 (土) 13:11:58) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問111 Doctor's Memorable Codes
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0111
文字列を符号化して複合する問題。
解法
先頭から少しだけ符号化して、復号が見つかった端から復号していけば少しだけメモリの節約になるはずです。
そう考えて実装してみました。
charをうまく使えば２０文字もあれば変換の作業領域は十分になりますが。
めんどくさいのでstringを使いました。
#include<stdio.h>
#include<map>
#include<string>
#include<iostream>
std::map<char,std::string> cToS;
std::map<std::string,char> sToC;
std::string toBits(char n){
std::string bits="00000";
for(int i=4;i>=0;i--){
bits[i]=(char)((n%2)+'0');
n/=2;
}
return bits;
}
int main(){
for(char i='A';i<='Z';i++){
cToS[i]=toBits(i-'A');
}
cToS[' '] ="11010";
cToS['.'] ="11011";
cToS[','] ="11100";
cToS['-'] ="11101";
cToS['\'']="11110";
cToS['?'] ="11111";
sToC["100101"]='A';
sToC["10011010"]='B';
sToC["0101"]='C';
sToC["0001"]='D';
sToC["110"]='E';
sToC["01001"]='F';
sToC["10011011"]='G';
sToC["010000"]='H';
sToC["0111"]='I';
sToC["10011000"]='J';
sToC["0110"]='K';
sToC["00100"]='L';
sToC["10011001"]='M';
sToC["10011110"]='N';
sToC["00101"]='O';
sToC["111"]='P';
sToC["10011111"]='Q';
sToC["1000"]='R';
sToC["00110"]='S';
sToC["00111"]='T';
sToC["10011100"]='U';
sToC["10011101"]='V';
sToC["000010"]='W';
sToC["10010010"]='X';
sToC["10010011"]='Y';
sToC["10010000"]='Z';
sToC["101"]=' ';
sToC["000000"]='\'';
sToC["000011"]=',';
sToC["10010001"]='-';
sToC["010001"]='.';
sToC["000001"]='?';
std::string str;
while(std::getline(std::cin,str)){
int p=0;
std::string temp="";
while(1){
bool hit=false;
for(int i=3;i<=temp.size();i++){
if(sToC.find(temp.substr(0,i))!=sToC.end()){
std::cout<<sToC[temp.substr(0,i)];
hit=true;
if(temp.size()>i)temp=temp.substr(i);
else temp="";
break;
}
}
if(hit==true)continue;
if(p==str.size())break;
temp+=cToS[str[p]];
p++;
}
std::cout<<"\n";
}
}
*問112 A Milk Shop
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0112
牛乳屋さんがお客を待たせる時間を最小にする問題。
解法
待ち時間の短い人から処理するだけです。
0～60までの整数しか与えられないのですからカウンティングソートを使えばいいですね。
数学の公式を使えばもう少し早くなりますが素朴に足し合わせてもそんなに遅くないのでこの問題ではこれで十分でしょう。
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<iostream>
int main(){
int n;
while(scanf("%d",&n)!=EOF){
if(n==0) break;
long long int ans=0,sum=0;
int t,count[61]={0};
for(int i=0;i<n;i++){
std::cin>>t;
count[t]++;
}
for(int i=0;i<=60;i++){
while(count[i]){
ans+=sum;
sum+=i;
count[i]--;
}
}
std::cout<<ans<<"\n";
}
}
*問113 Period
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0113
割り算の循環部分を表示する問題。
解法
小学生の筆算で解けます。
問題は割る数と余りの両方で循環をチェックする必要があるという点です。
それくらいですね。
#include<stdio.h>
#include<map>
struct S{
int amari,div;
bool operator<(const S &s)const{
if(amari!=s.amari)return amari<s.amari;
return div<s.div;
}
};
int main(){
int p,q;
while(scanf("%d %d",&p,&q)!=EOF){
std::map<S,int> memo;
int amari=-1,keta=0;
S s1;
p*=10;
while(amari!=0){
amari=p%q;
s1.amari=amari;
s1.div=p/q;
if(memo.find(s1)!=memo.end())break;
printf("%d",p/q);
p=amari*10;
memo[s1]=keta;
keta++;
}
printf("\n");
if(amari>0&&memo.find(s1)!=memo.end()){
for(int i=0;i<keta;i++){
printf("%c",i<memo[s1]?' ':'^');
}
printf("\n");
}
}
}
*問114 Electro-Fly
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0114
電子バエが元の位置に戻ってくるまでの回数を計算する問題。
解法
a1,a2,a3が戻ってくるまでの最小回数を個別に計算して、あとは最小回数の最小公倍数を求めればとりあえず間に合いますが。
少し数学的な方法があります。
フェルマーの小定理によれば互いに素なa,mがあった場合、a^φ(m) mod m=1です。
これで答えの気もしますが念のためφ(m)の約数のうちで条件を満たす一番小さなものをφ(m)の代わりに代入して答えとします。
一つのデータセットの計算量は1000回以下となります。
#include<stdio.h>
#include<iostream>
#include<math.h>
long long int gcd ( long long int a, long long int b ){
int c;
while ( a != 0 ) {
c = a; a = b%a; b = c;
}
return b;
}
long long int lcm(long long int a,long long int b){
return a*(b/gcd(a,b));
}
long long int calc(long long int a,long long int div,long long int m){
long long int re=1;
while(div>0){
if(div%2==1)re=(re*a)%m;
a=(a*a)%m;
div/=2;
}
return re;
}
long long int fai(long long int m){
long long int re=m;
for(int i=2;i*i<=m;i++){
if(m%i==0){
re=(re/i)*(i-1);
while(m%i==0){
m/=i;
}
}
}
if(m>1)re=(re/m)*(m-1);
return re;
}
long long int lamda(long long int a,long long int m){
long long int m1=fai(m);
long long int re=m1;
for(int i=1;i*i<=m1;i++){
if(m1%i==0){
if(calc(a,m1/i,m)==1&&re>m1/i)re=m1/i;
if(calc(a,i,m)==1&&re>i)re=i;
}
}
return re;
}
int main(){
long long int a1,a2,a3,m1,m2,m3;
while(1){
std::cin>>a1>>m1>>a2>>m2>>a3>>m3;
long long int c1,c2,c3;
if(m1==0)break;
c1=lamda(a1,m1);
c2=lamda(a2,m2);
c3=lamda(a3,m3);
std::cout<<lcm(c1,lcm(c2,c3))<<"\n";
}
}
*問115 Starship UAZ Advance
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0115
敵にビームが当たるか判定する問題。
厳密には線分とポリゴンの交差判定をする問題です。
解法
計算式を一文字書き間違えてただけで連続WAを食らった問題、たった一文字修正したら通った。
まずはバリアの一つ目の頂点を原点にとります。
バリアの外積を計算します。
外積と敵の宇宙船の座標から内積を計算し内積が0なら敵は平面上にいて敵と自分の交点を敵座標にします。
そうでないなら自分とバリアを含んだ平面と自分と敵を結んだ線分の交点を求めます。
この交点がバリア三角形の中にあるか調べれば計算終了です。
#include<stdio.h>
#include<math.h>
void gaiseki(double ax,double bx,double ay,double by,double az,double bz,
double& reX,double& reY,double& reZ){
reX=ay*bz-az*by;
reY=az*bx-ax*bz;
reZ=ax*by-ay*bx;
}
int main(){
double bXs[3],bYs[3],bZs[3];
double myX,myY,myZ;
double eX,eY,eZ;
scanf("%lf %lf %lf",&myX,&myY,&myZ);
scanf("%lf %lf %lf",&eX,&eY,&eZ);
for(int i=0;i<3;i++){
scanf("%lf %lf %lf",&bXs[i],&bYs[i],&bZs[i]);
}
myX-=bXs[0];
myY-=bYs[0];
myZ-=bZs[0];
eX-= bXs[0];
eY-= bYs[0];
eZ-= bZs[0];
bXs[1]-=bXs[0];
bYs[1]-=bYs[0];
bZs[1]-=bZs[0];
bXs[2]-=bXs[0];
bYs[2]-=bYs[0];
bZs[2]-=bZs[0];
bXs[0]=bYs[0]=bZs[0]=0;
double gx,gy,gz;
gaiseki(bXs[1],bXs[2],bYs[1],bYs[2],bZs[1],bZs[2],gx,gy,gz);
double naisekiE,naisekiMy;
naisekiE=gx*eX+gy*eY+gz*eZ;
double cx,cy,cz,lenG,lenMy,lenE;
lenG =sqrt(gx*gx+gy*gy+gz*gz);
if(naisekiE==0){
//敵がバリアと同じ平面にいる
cx=eX;
cy=eY;
cz=eZ;
}else{
naisekiMy=gx*myX+gy*myY+gz*myZ;
if((naisekiMy<0&&naisekiE<0)||(naisekiMy>0&&naisekiE>0)){
//敵と自分がバリア平面の同じ方にいた
printf("HIT\n");
return 0;
}
double myM=fabs(naisekiMy/lenG);
double eM =fabs(naisekiE/lenG);
cx=(eX-myX)*myM/(myM+eM)+myX;
cy=(eY-myY)*myM/(myM+eM)+myY;
cz=(eZ-myZ)*myM/(myM+eM)+myZ;
}
double rs[3];
bool isLine=false;
for(int i=0;i<3;i++){
double dx,dy,dz,dx1,dy1,dz1,grx,gry,grz;
dx=bXs[i]-cx;
dy=bYs[i]-cy;
dz=bZs[i]-cz;
dx1=bXs[(i+1)%3]-cx;
dy1=bYs[(i+1)%3]-cy;
dz1=bZs[(i+1)%3]-cz;
gaiseki(dx,dx1,dy,dy1,dz,dz1,grx,gry,grz);
if(fabs(gx)>0){
rs[i]=grx;
}else if(fabs(gy)>0){
rs[i]=gry;
}else if(fabs(gz)>0){
rs[i]=grz;
}else{
rs[i]=0;
}
}
if(rs[0]<=0&&rs[1]<=0&&rs[2]<=0){
printf("MISS\n");
}else if(rs[0]>=0&&rs[1]>=0&&rs[2]>=0){
printf("MISS\n");
}else{
printf("HIT\n");
}
}
*問111 Doctor's Memorable Codes
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0111
文字列を符号化して複合する問題。
解法
先頭から少しだけ符号化して、復号が見つかった端から復号していけば少しだけメモリの節約になるはずです。
そう考えて実装してみました。
charをうまく使えば２０文字もあれば変換の作業領域は十分になりますが。
めんどくさいのでstringを使いました。
#include<stdio.h>
#include<map>
#include<string>
#include<iostream>
std::map<char,std::string> cToS;
std::map<std::string,char> sToC;
std::string toBits(char n){
std::string bits="00000";
for(int i=4;i>=0;i--){
bits[i]=(char)((n%2)+'0');
n/=2;
}
return bits;
}
int main(){
for(char i='A';i<='Z';i++){
cToS[i]=toBits(i-'A');
}
cToS[' '] ="11010";
cToS['.'] ="11011";
cToS[','] ="11100";
cToS['-'] ="11101";
cToS['\'']="11110";
cToS['?'] ="11111";
sToC["100101"]='A';
sToC["10011010"]='B';
sToC["0101"]='C';
sToC["0001"]='D';
sToC["110"]='E';
sToC["01001"]='F';
sToC["10011011"]='G';
sToC["010000"]='H';
sToC["0111"]='I';
sToC["10011000"]='J';
sToC["0110"]='K';
sToC["00100"]='L';
sToC["10011001"]='M';
sToC["10011110"]='N';
sToC["00101"]='O';
sToC["111"]='P';
sToC["10011111"]='Q';
sToC["1000"]='R';
sToC["00110"]='S';
sToC["00111"]='T';
sToC["10011100"]='U';
sToC["10011101"]='V';
sToC["000010"]='W';
sToC["10010010"]='X';
sToC["10010011"]='Y';
sToC["10010000"]='Z';
sToC["101"]=' ';
sToC["000000"]='\'';
sToC["000011"]=',';
sToC["10010001"]='-';
sToC["010001"]='.';
sToC["000001"]='?';
std::string str;
while(std::getline(std::cin,str)){
int p=0;
std::string temp="";
while(1){
bool hit=false;
for(int i=3;i<=temp.size();i++){
if(sToC.find(temp.substr(0,i))!=sToC.end()){
std::cout<<sToC[temp.substr(0,i)];
hit=true;
if(temp.size()>i)temp=temp.substr(i);
else temp="";
break;
}
}
if(hit==true)continue;
if(p==str.size())break;
temp+=cToS[str[p]];
p++;
}
std::cout<<"\n";
}
}
*問112 A Milk Shop
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0112
牛乳屋さんがお客を待たせる時間を最小にする問題。
解法
待ち時間の短い人から処理するだけです。
0～60までの整数しか与えられないのですからカウンティングソートを使えばいいですね。
数学の公式を使えばもう少し早くなりますが素朴に足し合わせてもそんなに遅くないのでこの問題ではこれで十分でしょう。
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<iostream>
int main(){
int n;
while(scanf("%d",&n)!=EOF){
if(n==0) break;
long long int ans=0,sum=0;
int t,count[61]={0};
for(int i=0;i<n;i++){
std::cin>>t;
count[t]++;
}
for(int i=0;i<=60;i++){
while(count[i]){
ans+=sum;
sum+=i;
count[i]--;
}
}
std::cout<<ans<<"\n";
}
}
*問113 Period
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0113
割り算の循環部分を表示する問題。
解法
小学生の筆算で解けます。
問題は割る数と余りの両方で循環をチェックする必要があるという点です。
それくらいですね。
#include<stdio.h>
#include<map>
struct S{
int amari,div;
bool operator<(const S &s)const{
if(amari!=s.amari)return amari<s.amari;
return div<s.div;
}
};
int main(){
int p,q;
while(scanf("%d %d",&p,&q)!=EOF){
std::map<S,int> memo;
int amari=-1,keta=0;
S s1;
p*=10;
while(amari!=0){
amari=p%q;
s1.amari=amari;
s1.div=p/q;
if(memo.find(s1)!=memo.end())break;
printf("%d",p/q);
p=amari*10;
memo[s1]=keta;
keta++;
}
printf("\n");
if(amari>0&&memo.find(s1)!=memo.end()){
for(int i=0;i<keta;i++){
printf("%c",i<memo[s1]?' ':'^');
}
printf("\n");
}
}
}
*問114 Electro-Fly
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0114
電子バエが元の位置に戻ってくるまでの回数を計算する問題。
解法
a1,a2,a3が戻ってくるまでの最小回数を個別に計算して、あとは最小回数の最小公倍数を求めればとりあえず間に合いますが。
少し数学的な方法があります。
フェルマーの小定理によれば互いに素なa,mがあった場合、a^φ(m) mod m=1です。
これで答えの気もしますが念のためφ(m)の約数のうちで条件を満たす一番小さなものをφ(m)の代わりに代入して答えとします。
一つのデータセットの計算量は1000回以下となります。
#include<stdio.h>
#include<iostream>
#include<math.h>
long long int gcd ( long long int a, long long int b ){
int c;
while ( a != 0 ) {
c = a; a = b%a; b = c;
}
return b;
}
long long int lcm(long long int a,long long int b){
return a*(b/gcd(a,b));
}
long long int calc(long long int a,long long int div,long long int m){
long long int re=1;
while(div>0){
if(div%2==1)re=(re*a)%m;
a=(a*a)%m;
div/=2;
}
return re;
}
long long int fai(long long int m){
long long int re=m;
for(int i=2;i*i<=m;i++){
if(m%i==0){
re=(re/i)*(i-1);
while(m%i==0){
m/=i;
}
}
}
if(m>1)re=(re/m)*(m-1);
return re;
}
long long int lamda(long long int a,long long int m){
long long int m1=fai(m);
long long int re=m1;
for(int i=1;i*i<=m1;i++){
if(m1%i==0){
if(calc(a,m1/i,m)==1&&re>m1/i)re=m1/i;
if(calc(a,i,m)==1&&re>i)re=i;
}
}
return re;
}
int main(){
long long int a1,a2,a3,m1,m2,m3;
while(1){
std::cin>>a1>>m1>>a2>>m2>>a3>>m3;
long long int c1,c2,c3;
if(m1==0)break;
c1=lamda(a1,m1);
c2=lamda(a2,m2);
c3=lamda(a3,m3);
std::cout<<lcm(c1,lcm(c2,c3))<<"\n";
}
}
*問115 Starship UAZ Advance
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0115
敵にビームが当たるか判定する問題。
厳密には線分とポリゴンの交差判定をする問題です。
解法
計算式を一文字書き間違えてただけで連続WAを食らった問題、たった一文字修正したら通った。
まずはバリアの一つ目の頂点を原点にとります。
バリアの外積を計算します。
外積と敵の宇宙船の座標から内積を計算し内積が0なら敵は平面上にいて敵と自分の交点を敵座標にします。
そうでないなら自分とバリアを含んだ平面と自分と敵を結んだ線分の交点を求めます。
この交点がバリア三角形の中にあるか調べれば計算終了です。
#include<stdio.h>
#include<math.h>
void gaiseki(double ax,double bx,double ay,double by,double az,double bz,
double& reX,double& reY,double& reZ){
reX=ay*bz-az*by;
reY=az*bx-ax*bz;
reZ=ax*by-ay*bx;
}
int main(){
double bXs[3],bYs[3],bZs[3];
double myX,myY,myZ;
double eX,eY,eZ;
scanf("%lf %lf %lf",&myX,&myY,&myZ);
scanf("%lf %lf %lf",&eX,&eY,&eZ);
for(int i=0;i<3;i++){
scanf("%lf %lf %lf",&bXs[i],&bYs[i],&bZs[i]);
}
myX-=bXs[0];
myY-=bYs[0];
myZ-=bZs[0];
eX-= bXs[0];
eY-= bYs[0];
eZ-= bZs[0];
bXs[1]-=bXs[0];
bYs[1]-=bYs[0];
bZs[1]-=bZs[0];
bXs[2]-=bXs[0];
bYs[2]-=bYs[0];
bZs[2]-=bZs[0];
bXs[0]=bYs[0]=bZs[0]=0;
double gx,gy,gz;
gaiseki(bXs[1],bXs[2],bYs[1],bYs[2],bZs[1],bZs[2],gx,gy,gz);
double naisekiE,naisekiMy;
naisekiE=gx*eX+gy*eY+gz*eZ;
double cx,cy,cz,lenG,lenMy,lenE;
lenG =sqrt(gx*gx+gy*gy+gz*gz);
if(naisekiE==0){
//敵がバリアと同じ平面にいる
cx=eX;
cy=eY;
cz=eZ;
}else{
naisekiMy=gx*myX+gy*myY+gz*myZ;
if((naisekiMy<0&&naisekiE<0)||(naisekiMy>0&&naisekiE>0)){
//敵と自分がバリア平面の同じ方にいた
printf("HIT\n");
return 0;
}
double myM=fabs(naisekiMy/lenG);
double eM =fabs(naisekiE/lenG);
cx=(eX-myX)*myM/(myM+eM)+myX;
cy=(eY-myY)*myM/(myM+eM)+myY;
cz=(eZ-myZ)*myM/(myM+eM)+myZ;
}
double rs[3];
bool isLine=false;
for(int i=0;i<3;i++){
double dx,dy,dz,dx1,dy1,dz1,grx,gry,grz;
dx=bXs[i]-cx;
dy=bYs[i]-cy;
dz=bZs[i]-cz;
dx1=bXs[(i+1)%3]-cx;
dy1=bYs[(i+1)%3]-cy;
dz1=bZs[(i+1)%3]-cz;
gaiseki(dx,dx1,dy,dy1,dz,dz1,grx,gry,grz);
if(fabs(gx)>0){
rs[i]=grx;
}else if(fabs(gy)>0){
rs[i]=gry;
}else if(fabs(gz)>0){
rs[i]=grz;
}else{
rs[i]=0;
}
}
if(rs[0]<=0&&rs[1]<=0&&rs[2]<=0){
printf("MISS\n");
}else if(rs[0]>=0&&rs[1]>=0&&rs[2]>=0){
printf("MISS\n");
}else{
printf("HIT\n");
}
}
