A - センター採点
高橋君はセンター試験を受けました。
センター試験の各々の問題は 1 から 4 までの選択肢があります。高橋君はあまり勉強をしていなかったので、全ての問題で同じ選択肢を選びました。
試験終了後、センター試験の解答が与えられましたが、高橋君は何番を選んだのかを忘れてしまいました。しかし、高橋君は自分の点数が気になります。
そこで、高橋君のため、高橋君が正解する問題の数として考えられる最大と最小の数を求めなさい。
入力は以下の形式で与えられる。
高橋君が正解する問題の数として考えられる最大と最小の数を空白区切りで 1 行に出力せよ。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
センター試験の各々の問題は 1 から 4 までの選択肢があります。高橋君はあまり勉強をしていなかったので、全ての問題で同じ選択肢を選びました。
試験終了後、センター試験の解答が与えられましたが、高橋君は何番を選んだのかを忘れてしまいました。しかし、高橋君は自分の点数が気になります。
そこで、高橋君のため、高橋君が正解する問題の数として考えられる最大と最小の数を求めなさい。
入力
N c_1c_2c_3…c_N
- 1 行目は、センター試験の問題の数を表す整数 N (1 ≦ N ≦ 100) が与えられる。
- 2 行目は、センター試験の解答を表す N 文字の文字列が与えられる。この文字列の i 文字目 (1 ≦ i ≦ N) の文字 c_i (c_i は
1、2、3、4のいずれかである) は、i 番目の問題の正解が c_i であったことを表す。
出力
入力例 1
9 131142143
出力例 1
4 1
- 選択肢 1 を選ぶ時、高橋君が正解する問題の数は 4 問となり、これが最大の正解数です。
- 選択肢 2 を選ぶ時、高橋君が正解する問題の数は 1 問となり、これが最小の正解数です。
入力例 2
20 12341234123412341234
出力例 2
5 5
- 1,2,3,4 のいずれの選択肢を選んだ場合も、正答数は 5 問であり、高橋君が正解する問題の数の最小と最大の数はいずれも 5 となります。
入力例 3
4 1111
出力例 3
4 0
Source Name
ARC 001
B - リモコン
高橋君は、エアコンの設定温度を変更しようとしています。現在の設定温度は A 度ですが、これを B 度に設定したいと思っています。
エアコンのリモコンは 1 回ボタンを押すことで、
高橋君が設定温度を A 度から B 度に変更するために押すボタンの最小回数を求めなさい。
入力は以下の形式で与えられる。
高橋君がボタンを押す必要のある回数の最小値を 1 行に出力せよ。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
エアコンのリモコンは 1 回ボタンを押すことで、
- 1 度設定温度を下げる、もしくは上げる
- 5 度設定温度を下げる、もしくは上げる
- 10 度設定温度を下げる、もしくは上げる
高橋君が設定温度を A 度から B 度に変更するために押すボタンの最小回数を求めなさい。
入力
A B
- 1 行目は現在の設定温度を表す整数 A (0 ≤ A ≤ 40) と、設定したい温度を表す整数 B (0 ≤ B ≤ 40) が与えられる。
出力
入力例 1
7 34
出力例 1
5
- 10 度、10 度、5 度、1 度、1 度の順で上げていくと、5 回で設定することが出来ます。
入力例 2
19 28
出力例 2
2
- 10 度上げた後に、1 度下げることで、2 回で設定することが出来ます。
入力例 3
10 10
出力例 3
0
- 同じ温度の時は、設定温度を変える必要はありません。
Source Name
ARC 001
C - パズルのお手伝い
高橋君は、パズルが好きです。今日は、8 クイーン問題に挑戦しようとしています。
8 クイーン問題とは、8×8 のチェスボード上の縦・横・斜め 45 度の同一直線状にそれぞれクイーンが 1 つしか存在しないように、合計 8 つのクイーンを置く問題です。
図:出力例1の図。縦・横・斜め 45 度の同一直線状にそれぞれクイーンが 1 つのみ存在する。
高橋君は、3 つのクイーンを置いたところで残りのクイーンをどう置いたら良いのか判らなくなってしまいました。
残りの 5 つのクイーンを含めた 8 つのクイーンの位置を求めなさい。
入力は以下の形式で与えられる。
8 つのクイーンを置き終わった後の状態のうちの 1 つを、入力と同様のフォーマットで出力せよ。
答えが存在しない場合は、
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
8 クイーン問題とは、8×8 のチェスボード上の縦・横・斜め 45 度の同一直線状にそれぞれクイーンが 1 つしか存在しないように、合計 8 つのクイーンを置く問題です。
図:出力例1の図。縦・横・斜め 45 度の同一直線状にそれぞれクイーンが 1 つのみ存在する。
高橋君は、3 つのクイーンを置いたところで残りのクイーンをどう置いたら良いのか判らなくなってしまいました。
残りの 5 つのクイーンを含めた 8 つのクイーンの位置を求めなさい。
入力
c_{11} c_{12} … c_{18}
c_{21} c_{22} … c_{28}
:
:
c_{81} c_{82} … c_{88}
- 1 行目から 8 行目の各行は 8 文字の文字列が与えられる。
- i 行目の先頭から j 番目の文字である c_{ij} は、i 行目 j 列目にクイーンが置かれているかどうかを表す。
- c_{ij} は、
'.'もしくは'Q'で与えられ、'.'であればクイーンが置かれていないことを、'Q'であればクイーンが置かれていることを表す。
出力
答えが存在しない場合は、
"No Answer" と 1 行で出力せよ。
入力例 1
........ ........ .......Q ........ ..Q..... ........ .Q...... ........
出力例 1
Q....... ....Q... .......Q .....Q.. ..Q..... ......Q. .Q...... ...Q....
- 上記のようにクイーンを置いた時、条件を満たすことが出来ます。
入力例 2
.....Q.. .Q...... ........ ........ ........ Q....... ........ ........
出力例 2
No Answer
- 初期配置で既に 1 行目と 6 行目のクイーンが斜め 45 度の同一直線状に存在するので、この地点で条件を満たしておらず答えは存在しません。
Source Name
ARC 001
D - レースゲーム
高橋君は、レーシングゲームをプレイしようとしています。
レースは (x, y) = (start, 0) からスタートし、(x, y) = (goal, N) のゴールに向かって走っていきます。
0 ≦ k ≦ N の y=k に対してコースの存在する左端と右端が与えられ、それぞれを順に結んだ線の内側がコースとなります。
図：入力1の例。赤丸がスタート地点。青丸がゴール地点。茶色部分がコースとなる。
レースに使う車はコース上以外を走ることは出来ません。また、一瞬で方向転換できるものとし、車の幅及び長さは無視できるものとします。
高橋君は、このレーシングゲームを攻略するためにスタートからゴールまでの最短経路を求めたいです。
入力は以下の形式で与えられる。
レースの最短経路を 1 行で出力せよ。
なお、出力は絶対誤差または相対誤差 1e-9 以下までを許容する。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
レースは (x, y) = (start, 0) からスタートし、(x, y) = (goal, N) のゴールに向かって走っていきます。
0 ≦ k ≦ N の y=k に対してコースの存在する左端と右端が与えられ、それぞれを順に結んだ線の内側がコースとなります。
図：入力1の例。赤丸がスタート地点。青丸がゴール地点。茶色部分がコースとなる。
レースに使う車はコース上以外を走ることは出来ません。また、一瞬で方向転換できるものとし、車の幅及び長さは無視できるものとします。
高橋君は、このレーシングゲームを攻略するためにスタートからゴールまでの最短経路を求めたいです。
入力
N start goal l_0 r_0 l_1 r_1 : : l_N r_N
- 1 行目には、レースの全長 N が与えられる。
- 2 行目には、コースのスタート地点の start 座標及びゴール地点の goal 座標が空白を区切りとして与えられる。
- 続く 3 行目から N+2 行目の各行には、i+3 行目にy=i のコースの左端 l_i 及びコースの右端 r_i が空白を区切りとして与えられる。
- また、入力値はそれぞれ以下の条件を満たす。
- N は整数であり、1 ≦ N ≦ 200,000 を満たす。
- l_i 及び r_i は整数であり、0 ≦ l_i ＜ r_i ≦ 1,000,000 を満たす。
- start は整数であり、l_0 ≦ start ≦ r_0 を満たす。
- goal は整数であり、l_N ≦ goal ≦ r_N を満たす。
出力
なお、出力は絶対誤差または相対誤差 1e-9 以下までを許容する。
入力例 1
7 3 3 2 5 4 6 2 3 3 6 3 4 4 6 2 5 1 5
出力例 1
8.22677276241436
- 赤丸をスタート地点、青丸をゴール地点として、下図の赤線のルートが最短となります。
入力例 2
5 3 3 0 5 0 5 0 5 0 5 0 5 0 5
出力例 2
5