Codeforces Round#9(Div2 only) A-C

PracticeでA-Cまではやってみた。D,Eは解けたら解説うp予定。

A. Die Roll

問題概要

Yakko, Wakko, Dotの3人が旅行の行き先を決めるのに、普通の6面サイコロを1度ずつふって、目の最も大きい人の希望する所にすることにした。
Y,Wのサイコロの目が与えあられる時、Dotの希望する行き先になる確率を求め、既約分数の形で出力せよ。1の場合は1/1、0の場合は0/1と出力すること。


サイコロの目が同じだった場合にはDotの希望する行き先に決定することにする。

解法

サイコロの目がmax(Y,W)以上であればいい。分数の約分は分子分母をsの最大公約数で割ってやればよいが、gccの内部関数の__gcd(int,int)が便利。
ただし注意点が二つ。

  • algorithmをincludeする必要があること
  • 引数に0が入ると除算エラーをおこすこと
ソースコード
void run()
{
	int a,b; cin>>a>>b;
	a=max(a,b);
	
	int x=7-a,y=6,g=__gcd(x,y);
	cout<<x/g<<"/"<<y/g<<endl;
}

B. Running Student

問題概要

x軸上を走るバスに乗っている生徒が、あるバス停で降りてそこから大学まで歩く。
バス停の座標、大学の座標、バスの速度、生徒の歩行速度が与えられる時、大学に着く時間が最も早くなるような、生徒の降りるバス停の番号を答えよ。
ただしそのようなバス亭が複数ある場合、最も大学に近いバス停の番号を答えよ。
一度バスから降りたら二度とバスに乗れず、バスから降りるのにかかる時間は無視できるものとする。また、原点のバス停では降りることはできない。

解法

条件が複数あってややこしいが、バス停の数は100なのでかかる時間を全部調べればよい。

ソースコード
void run()
{
	int n; double vb,vs; cin>>n>>vb>>vs;
	double x[100],xu,yu;
	
	rep(i,n)cin>>x[i];
	cin>>xu>>yu;
	
	int ans=0; double opt=INF,dst;
	for(int i=1;i<n;i++)
	{
		if(opt>x[i]/vb+hypot(xu-x[i],yu)/vs||
			opt==x[i]/vb+hypot(xu-x[i],yu)/vs&&dst>hypot(xu-x[i],yu))
		{
			opt=x[i]/vb+hypot(xu-x[i],yu)/vs,ans=i;
			dst=hypot(xu-x[i],yu);
		}
	}
	cout<<ans+1<<endl;
}

C. Hexadecimal's Numbers

問題概要

与えられた自然数n(n≦10億)以下の自然数のうち、各桁が1と0だけのものの個数を求めよ。

解法

nの各桁が元々全て0か1の場合、nを二進数とみて十進数に変換した数を答えればいい。
この考えを少し進めれば、nに2以上の数が混ざっている場合は、その桁以下の数をすべて1に置き換えた数を二進数とみて十進数に変換した数を答えればいいことがわかる。

ソースコード
void run()
{
	int n; cin>>n;
	int d[10],nd=0;
	for(;n;n/=10)d[nd++]=n%10;
	
	int ans=0; bool f=0;
	rep(i,nd)
	{
		if(d[nd-1-i]>1)f=1;
		if(f)d[nd-i-1]=1;
		
		ans*=2;
		ans+=d[nd-i-1];
	}
	cout<<ans<<endl;
}