PKU演習問メモ(8/21)

なんかPKU落ちてて解説記事が書きにくい。後ほど気が向いたら更新。
↑更新。

No.	問題名	問題の種類および解法	難易度
1102	LC-Display	実装	★★☆☆☆
2413	How many Fibs?	多倍長整数	★★☆☆☆
2305	Basic remains	多倍長整数	★★☆☆☆
2109	Power of Cryptography	多倍長整数・二分法	★★☆☆☆
1454	Factorial Frequencies	多倍長整数	★★☆☆☆
1220	NUMBER BASE CONVERSION	多倍長整数・基数変換	★★☆☆☆
1299	Polar Explorer	実装	★☆☆☆☆
1703	Find them, Catch them	Union-Find（の応用）	★★★★☆
2272	Bullseye	点の距離	★☆☆☆☆
2812	Extrusion	多角形の面積	★★☆☆☆

1102 LC-Display

問題概要

与えられた数字をLCディスプレイのように出力せよ。
sはサイズ（数字の一辺の長さ）を表す。

s≦10,n≦999,999,999を満たす。

解法

詳細はサンプルを参照せよ、らしい。酷いｗ
サイズに応じてansに表示を作って、最後に表示。

ソースコード

bool tate[10][3]={
	{1,0,1},{0,0,0},{1,1,1},{1,1,1},{0,1,0},
	{1,1,1},{1,1,1},{1,0,0},{1,1,1},{1,1,1}
};
bool yoko1[10][2]={
	{1,1},{0,1},{0,1},{0,1},{1,1},
	{1,0},{1,0},{0,1},{1,1},{1,1}
};
bool yoko2[10][2]={
	{1,1},{0,1},{1,0},{0,1},{0,1},
	{0,1},{1,1},{0,1},{1,1},{0,1}
};

int s;
string str;
char ans[1000][1000];

void write(int pos,int d)
{
	rep(i,3)if(tate[d][i])rep(j,s)ans[i*(s+1)][j+pos+1]='-';
	rep(i,2)
	{
		if(yoko1[d][i])rep(j,s)ans[j+1][pos+i*(s+1)]='|';
		if(yoko2[d][i])rep(j,s)ans[s+2+j][pos+i*(s+1)]='|';
	}
}
int main()
{
	while(cin>>s>>str,s)
	{
		int n=str.size();
		int w=(s+2)*n+n-1,h=2*s+3;
		
		//cerr<<w<<" "<<h<<endl;
		
		rep(i,h)
		{
			fill_n(ans[i],w,' ');
			ans[i][w]=0;
		}
		rep(i,n)write(i*(s+3),str[i]-'0');
		
		rep(i,h)cout<<ans[i]<<endl; cout<<endl;
	}
	return 0;
}

2413 How many Fibs?

問題概要

二つの整数a,bが与えられる。
a以上b以下のフィボナッチ数はいくつあるか求めよ。

a≦b≦10^100を満たす。

解法

10^100までのフィボナッチ数を全列挙しても500個に満たないので、全列挙してよい。
探索も線形探索で十分間に合う。

ソースコード

	class pku2413{
		BigInteger a,b;
		BigInteger[] fib;
		void run(){
			Scanner sc=new Scanner(System.in);
			fib=new BigInteger[500];
			fib[0]=BigInteger.ONE; fib[1]=BigInteger.valueOf(2);
			
			int i=2;
			for(;;i++){
				fib[i]=fib[i-1].add(fib[i-2]);
				if(fib[i].compareTo(BigInteger.TEN.pow(100))>=0)break;
			}
			
			while(true){
				a=sc.nextBigInteger(); b=sc.nextBigInteger();
				if(a.compareTo(b)==0&&a.compareTo(BigInteger.ZERO)==0)break;
				
				int l=0,r=0;
				for(;fib[l].compareTo(a)<0;l++);
				for(r=l;fib[r].compareTo(b)<=0;r++);
				System.out.println(r-l);
			}
		}
	}

2305 Basic remains

問題概要

整数b,p,mが与えられる。p,mはb進数である。
p=a*m+kとなるような負でない最小の整数kを求め、b進数で出力せよ。

bは2から10の整数、pの桁数は1000以下、
0≦m＜bを満たす。

解法

BigIntegerを使ってmodを取ればいいが、m=0の場合は場合分けして処理しなければならないことに注意。

ソースコード

	class pku2305{
		int b;
		BigInteger p,m;
		void run(){
			Scanner sc=new Scanner(System.in);
			while(true){
				b=sc.nextInt();
				
				if(b==0)break;
				
				p=sc.nextBigInteger(b);
				m=sc.nextBigInteger(b); if(m.compareTo(BigInteger.ZERO)==0)m=BigInteger.ONE;
				
				p=p.mod(m);
				System.out.println(p.toString(b));
			}
		}
	}

2109 Power of Cryptography

問題概要

与えられた整数n,pに対してk^n=pとなるような整数kを求めよ。

入力に対し、1≦k≦10^9以下で条件を満たす整数kが存在することは保証されている。
n≦200,1≦p≦10^101を満たす。

解法

nは正、kも1以上の整数なのでk^nはkに関する単調増加関数。
したがってkの値で二分法すればよい。

ただしpが大きいのでBigInteger等を使用する。

ソースコード

	class pku2199{
		int n; BigInteger p;
		void run(){
			Scanner sc=new Scanner(System.in);
			while(sc.hasNextInt())
			{
				n=sc.nextInt(); p=sc.nextBigInteger();
				int lo=1,hi=1000000005,mid=0;
				while(lo+1<hi){
					mid=(lo+hi)/2;
					if(BigInteger.valueOf(mid).pow(n).compareTo(p)>0)hi=mid;
					else lo=mid;
				}
				System.out.println(lo);
			}
		}
	}

1454 Factorial Frequencies

問題概要

与えられた数nに対し、n!を10進数で表したとき、0-9の数字が出現する回数を求めよ。

n≦366を満たす。

解法

多倍長だと難易度が高くなるのはBigIntegerが書くだけで面倒だから。
Pascalを使えばいいということか。

ソースコード

	class pku1454{
		int n;
		void run(){
			Scanner sc=new Scanner(System.in);
			while(true){
				n=sc.nextInt();
				if(n==0)break;
				
				BigInteger fc=BigInteger.ONE;
				for(int i=1;i<=n;i++)fc=fc.multiply(BigInteger.valueOf(i));

				int[] cnt=new int[10];
				for(;fc.compareTo(BigInteger.ZERO)>0;fc=fc.divide(BigInteger.TEN)){
					int a=fc.mod(BigInteger.TEN).intValue();
					cnt[a]++;
				}
				
				System.out.println(n+"! --");
				for(int i=0;i<10;i++){
					if(i%5==0)System.out.print("   ");
					System.out.printf("(%d)% 5d", i,cnt[i]);
					if(i%5==4)System.out.println();
					else System.out.print("    ");
				}
			}
		}
	}

1220 NUMBER BASE CONVERSION

問題概要

a進法で表された数字bが与えられる。これをc進法で表せ。

2≦a≦62,bの各桁はa未満、2≦cを満たす。
数字は9の次はA,B,C...Z,a,b,c...を用いよ。

解法

久しぶりのJava.

基数変換の処理はBigIntegerを使わない普通の場合と変わらない。
結果が0の場合は特別に処理する。

BigIntegerクラスには基数変換のメソッドがついているが、26進法にまでしか対応していないので自力でやる必要がある。

ソースコード

	class pku1220{
		void run(){
			Scanner sc=new Scanner(System.in);
			int n=sc.nextInt();
			
			for(int i=0;i<n;i++){
				int a=sc.nextInt(),b=sc.nextInt();
				String c=sc.next();
				
				BigInteger d=BigInteger.ZERO;
				for(int j=0;j<c.length();j++){
					d=d.multiply(BigInteger.valueOf(a)).add(BigInteger.valueOf(val(c.charAt(j))));
				}
				
				StringBuilder ans=new StringBuilder();
				for(;d.compareTo(BigInteger.ZERO)>0;d=d.divide(BigInteger.valueOf(b)))
				{
					BigInteger mod=d.mod(BigInteger.valueOf(b));
					ans.append(ch(mod.intValue()));
				}
				if(ans.length()==0)ans.append('0');
				ans.reverse();
				System.out.println(a+" "+c);
				System.out.println(b+" "+ans); System.out.println();
			}
		}
		int val(char c){
			if('0'<=c&&c<='9')return c-'0';
			if('A'<=c&&c<='Z')return c-'A'+10;
			return c-'a'+36;
		}
		char ch(int a){
			if(a<10)return (char) ('0'+a);
			if(a<36)return (char) ('A'+a-10);
			return (char) ('a'+a-36);
		}
	}

1299 Polar Explorer

問題概要

2次元平面上の円で表される星がある。
今自分は角度0の位置にいて、角度Zの位置に宇宙船が着陸した。
宇宙船まで燃費5マイル/ガロンの車で行き、戻ってきたい。

星の半径がX,車のガソリンの燃料がYガロンのとき、宇宙船まで行って戻ってこられるなら余るガソリンの量を、それが不可能ならガソリンで運転できる最大の距離を出力せよ。

解法

解法なんぞ書きようがないぞ……
わからない場合小学3年生だか4年生の頃の教科書を参照。
必要なのは、割る量、割られる量、商の意味の関係。
それから、扇形の弧長の計算方法。

もしくはプログラミング言語がわかっていない可能性があるので、各種入門書or入門サイトを参照。

ちなみに、新たに言語を勉強しはじめるならCよりC++,C++よりJavaがおすすめ。

ソースコード

int main()
{
	char dmy[99];
	while(scanf("%s",dmy),strlen(dmy)==5)
	{
		int x,y,z; scanf("%d%d%d",&x,&y,&z);
		z=min(z,360-z);
		double d=z*3.14159/360*2*x;
		
		if(2*d>y*5)printf("NO %d\n",y*5);
		else printf("YES %d\n",int(y-2*d/5));
		
		scanf("%s",dmy);
	}
	return 0;
}

1703 Find them, Catch them

問題概要

街にはGang DragonおよびGang Snakeの二つのギャング組織がある。
n人のギャングがおり、そのうちのいくつかの関係が
"A Bの属するギャングは異なる"という形式で与えられる。

その時点で
"A Bは同じギャングに属するか"というクエリを処理せよ。

出力は、

• A Bが同じギャングに属する
• 違うギャングに属する
• その時点では判別できない

の3種類とする。

解法

Union-Findの応用。WA出しまくってたので、komiya先生の解法を参考にさせてもらった。
根と自分が違う符号の場合、違う組織にいることを表す。

ソースコード

int n,p[100001];

int root(int x)
{
	if(abs(p[x])==x)return x;
	return p[x]=root(abs(p[x]))*(p[x]>0?1:-1);
}
int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		int m; scanf("%d%d",&n,&m);
		rep(i,n+1)p[i]=i;
		
		rep(i,m)
		{
			char c; int a,b; scanf(" %c%d%d",&c,&a,&b);
			
			if(c=='A')
			{
				int pa=root(a),pb=root(b);
				if(pa!=pb&&pa!=-pb)puts("Not sure yet.");
				else if(pa!=pb)puts("In different gangs.");
				else puts("In the same gang.");
				continue;
			}
			int pa=root(a),pb=root(b);
			if(pa==pb||pa==-pb)continue;
			p[abs(pa)]=pa>0?-pb:pb;
		}
	}
	return 0;
}

2272 Bullseye

問題概要

図（略）のようなダーツの的が与えられる。
的の中心は(0,0)であり、各リングの幅は3である。

投げられたダーツの刺さった座標が与えられるとき、プレイヤーの得点を計算せよ。

解法

原点からの距離を求め、どのリングに刺さったか判定する。
境界の場合は内側に刺さったことになるので、EPSを使ってその辺は調整。

ソースコード

int po(double x,double y)
{
	int r=(int)(hypot(x,y)/3-EPS);
	return max(100-20*r,0);
}

int main()
{
	double x,y;
	while(scanf("%lf%lf",&x,&y),x!=-100)
	{
		int a=po(x,y); rep(i,2)scanf("%lf%lf",&x,&y),a+=po(x,y);
		int b=0; rep(i,3)scanf("%lf%lf",&x,&y),b+=po(x,y);
		
		if(a==b)printf("SCORE: %d to %d, TIE. \n",a,b);
		else printf("SCORE: %d to %d, PLAYER %d WINS.\n",a,b,a>b?1:2);
	}
	
	return 0;
}

2812 Extrusion

問題概要

角柱の、底面の形および体積が与えられる。
このとき、角柱の高さを求めよ。

底面は各頂点の座標を時計回りの順で与えられる。

解法

高さ×底面積＝体積
多角形の面積はベクトルのクロス積を使う定石が存在。

ソースコード

spaghetti sourceの多角形の面積（http://www.prefield.com/algorithm/geometry/area2.html）を使用。

int main()
{
	int n;
	while(scanf("%d",&n),n>=3)
	{
		G g;
		rep(i,n)
		{
			double x,y; scanf("%lf%lf",&x,&y);
			g.pb(P(x,y));
		}
		double v; scanf("%lf",&v);
		printf("BAR LENGTH: %.2f\n",-v/area2(g)*2);
	}
	return 0;
}