Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋くんの通う学校では、創立された年に入学した生徒を 1 期生、その次の年に入学した生徒を 2 期生、といったように呼びます。 つまり、(入学した年 - 創立された年) + 1 = n の時に n 期生と呼ばれることとなります。 また、高橋くんの学校内では生徒がみな ID を持っており、それぞれの ID には必ず自分の期の数字が含まれることがわかっています。 ある生徒の ID が文字列 S として与えられるとき、その生徒が何期生であるかを回答してください。 また、数字が 2 つ連続して並んでいる場合は 2 桁の数字を意味するものとします。
制約
- S は大文字か小文字のアルファベット、または数字によって構成される
- S は 1 個または 2 個の数字を含む
- S が 2 個の数字を含む場合、数字は連続している
- S に最初に現れる数字は 0 ではない
- 3 ≤ |S| ≤ 10
入力
入力は以下の形式で標準入力から与えられる。
S
出力
出力は 1 行からなる。 生徒が n 期生の時に、出力の 1 行目に n を出力せよ。
入力例 1
chokudai55
出力例 1
55
入力例 2
cho9dai
出力例 2
9
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
3次元空間( xyz 空間)上に N 個の円錐が互いに重なり合わないように浮いています。
どの円錐も底面が yz 平面と平行で、x 軸の正の方向にとがっています。
i 番目の円錐の底面の中心の x 座標の値は X_i で半径は R_i 、高さは H_i です。
以下のクエリに Q 個答えてください。
- 2 つの整数 A と B が与えられるので A ≦ x ≦ B となる空間の内いずれかの円錐の内側にある部分の体積をもとめよ。
制約
- 与えられる数字はすべて整数
- 1 ≦ N ≦ 100
- 1 ≦ Q ≦ 10^5
- 0 ≦ X_i ≦ 10^4
- 1 ≦ H_i ≦ 10^4
- 1 ≦ R_i ≦ 10^3
- 0 ≦ A_i ≦ B_i ≦ 2×10^4
入力
入力は以下の形式で標準入力から与えられる。
N Q X_1 R_1 H_1 X_2 R_2 H_2 : X_N R_N H_N A_1 B_1 A_2 B_2 : A_Q B_Q
- 1 行目には円錐の個数を表す整数 N とクエリの個数を表す整数 Q が空白区切りで与えられる。
- 2 行目からの N 行のうち i 行目には i 番目の円錐の底面の中心の x 座標の値を表す整数 X_i と半径の長さを表す整数 R_i、高さを表す整数 H_i が空白区切りで与えられる。
- N+2 行目からの Q 行のうち i 行目には i 番目のクエリの内容を表す整数 A_i, B_i が空白区切りで与えられる。
出力
出力は Q 行からなる。 i 行目には i 番目のクエリの答えを 1 行で出力せよ。 出力は絶対誤差または相対誤差が 10^{-3} 以下であれば許容される。 なお、出力の末尾に改行を入れること。
入力例1
10 10 3 3 3 2 1 1 5 2 3 1 5 6 2 9 3 4 6 12 11 18 5 4 15 25 0 2 3 1 1 7 0 1 0 2 0 10 3 10 0 100 3 8 1 5 2 9 3 4 6 9
出力例1
8.843002 80.992182 4173.878112 3865.997282 8512.668894 2882.971997 1227.377293 3629.490541 114.081013 1747.545749
入力例2
5 5 5 10 10 4 100 100 3 1000 1000 2 1000 1000 1 1000 1000 0 3 2 1000 4 314 3 217 5 432
出力例2
9409079.422279 3139502408.531295 2100737789.465234 1613523459.243475 2532621914.444282
Time Limit: 4 sec / Memory Limit: 256 MB
問題文
町 0 から町 N-1 までの N 個の町があります。 これらは M 個の双方向に行き来可能な道で結ばれています。 道にはタイプ A とタイプ B の二種類の道があります。 タイプ A の道を通ると、コストが 1 かかります。 タイプ B の道を通るとき、コストが (今まで通ったタイプ B の道の本数) + 1 かかります。 ただし、i (1 ≤ i ≤ M) 本目の道は、町 A_i と町 B_i を結び、C_i が 0 のときはタイプ A、C_i が 1 のときはタイプ B とします。 全ての町において、町 0 からその町までの移動にかかる最小コストをそれぞれ求めてください。 ただし、町 0 から到達できない町は存在しないものとします。
制約
- 与えられる数字はすべて整数
- 1 ≤ N ≤ 10^4
- 1 ≤ M ≤ 10^5
- 0 ≤ A_i, B_i ≤ N - 1
- 0 ≤ C_i ≤ 1
入力
入力は以下の形式で標準入力から与えられる。
N M C_1 A_1 B_1 C_2 A_2 B_2 : C_M A_M B_M
出力
出力は N 行からなる。 i 行目 (1 ≤ i ≤ N)には、町 0 から町 i-1 への移動でかかるコストを出力せよ。
入力例 1
3 3 0 0 1 1 1 2 1 2 0
出力例 1
0 1 1
入力例 2
7 8 1 0 1 1 1 2 1 2 5 1 5 6 0 1 3 0 3 4 0 4 5 0 2 6
出力例 2
0 1 3 2 3 4 4
入力例 3
8 9 0 0 1 0 1 2 0 2 3 0 5 6 0 6 7 1 1 3 1 3 4 1 4 5 1 5 7
出力例 3
0 1 2 2 4 6 7 8
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
整数の 9 には面白い性質があります。 どのような非負整数 N を選んでも N を 9 で割った余りと、 N を 10 進法で表記した時の各桁の数字の和を 9 で割った余りが一致するのです。
高橋君はこのような性質を持つ整数が他にないか気になりました。しかし、残念なことにこのような性質をもつ整数は 9 と 3 と 1 くらいしか見つかりませんでした。 そこで、「どのような非負整数 N を選んでも・・・」ではなくて「できるだけ多くの非負整数 N に対して・・・」というふうに性質の条件を落として探してみることにしてみました。
高橋君は非負整数 K がどれくらい多くの非負整数 N に対して上のような条件をみたすのかが知りたいです。
高橋君を手伝うために以下の問いに答えてください。
- 1 ≦ N ≦ M となる整数 N のうち K で割った余りと、N を 10 進法表記した時の各桁の数字の和を K で割った余りが一致するような N の個数を求めてください。
制約
- 与えられる数字はすべて整数
- 1 ≦ K ≦ M ≦ 10^{10}
入力
入力は以下の形式で標準入力から与えられる。
K M
部分点
この問題には部分点が設定されている。
- 1 ≦ M ≦ 10^5 を満たすデータセットに正解した場合は 10 点が与えられる。
- 1 ≦ M ≦ 10^{10}を満たすデータセットに正解した場合はさらに 90 点が与えられる。合計で100点となる。
出力
問題文で挙げた条件に一致する非負整数の個数を 1 行で出力せよ。
入力例1
5 100
出力例1
19
1桁の整数はかならず条件を満たします。 そのほかに 50 ≦ N ≦ 59 を満たす整数は全て条件を満たします。 これら以外に条件を満たす整数は 100 以下の範囲にはありません。 よって 19 を出力します。
入力例2
112 32279
出力例2
309
入力例3
108 3141592653
出力例3
261799999
入力例4
9 10000000000
出力例4
10000000000