Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 100 点
問題文
A 駅と B 駅を結ぶ鉄道があり、運賃は X 円です。
また、B 駅と C 駅を結ぶバスがあり、運賃は Y 円です。
joisinoお姉ちゃんは、A 駅から B 駅まで鉄道で移動し、B 駅から C 駅までバスで移動すると、バスの運賃が半額になる特別券を手に入れました。
この特別券を用いたとき、A 駅から C 駅まで移動するのにいくらかかるか求めてください。
制約
- 1 \leq X,Y \leq 100
- Y は偶数
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
X Y
出力
A 駅から C 駅まで移動するのに x 円かかるとき、x を出力せよ。
入力例 1
81 58
出力例 1
110
- 鉄道の運賃は 81 円です。
- バスの運賃は半額となるため、58 ⁄ 2=29 円です。
よって、A 駅から C 駅まで移動するのに 110 円かかります。
入力例 2
4 54
出力例 2
31
Score: 100 points
Problem Statement
There is a train going from Station A to Station B that costs X yen (the currency of Japan).
Also, there is a bus going from Station B to Station C that costs Y yen.
Joisino got a special ticket. With this ticket, she can take the bus for half the fare if she travels from Station A to Station B by train and then travels from Station B to Station C by bus.
How much does it cost to travel from Station A to Station C if she uses this ticket?
Constraints
- 1 \leq X,Y \leq 100
- Y is an even number.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
X Y
Output
If it costs x yen to travel from Station A to Station C, print x.
Sample Input 1
81 58
Sample Output 1
110
- The train fare is 81 yen.
- The train fare is 58 ⁄ 2=29 yen with the 50% discount.
Thus, it costs 110 yen to travel from Station A to Station C.
Sample Input 2
4 54
Sample Output 2
31
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 200 点
問題文
ある国で、宮殿を作ることになりました。
この国では、標高が x メートルの地点での平均気温は T-x \times 0.006 度です。
宮殿を建設する地点の候補は N 個あり、地点 i の標高は H_i メートルです。
joisinoお姫様は、これらの中から平均気温が A 度に最も近い地点を選んで宮殿を建設するようにあなたに命じました。
宮殿を建設すべき地点の番号を出力してください。
ただし、解は一意に定まることが保証されます。
制約
- 1 \leq N \leq 1000
- 0 \leq T \leq 50
- -60 \leq A \leq T
- 0 \leq H_i \leq 10^5
- 入力は全て整数
- 解は一意に定まる
入力
入力は以下の形式で標準入力から与えられる。
N T A H_1 H_2 ... H_N
出力
宮殿を建設すべき地点の番号を出力せよ。
入力例 1
2 12 5 1000 2000
出力例 1
1
- 地点 1 の平均気温は 12-1000 \times 0.006=6 度です。
- 地点 2 の平均気温は 12-2000 \times 0.006=0 度です。
よって、宮殿を建設すべき地点は地点 1 となります。
入力例 2
3 21 -11 81234 94124 52141
出力例 2
3
Score: 200 points
Problem Statement
A country decides to build a palace.
In this country, the average temperature of a point at an elevation of x meters is T-x \times 0.006 degrees Celsius.
There are N places proposed for the place. The elevation of Place i is H_i meters.
Among them, Princess Joisino orders you to select the place whose average temperature is the closest to A degrees Celsius, and build the palace there.
Print the index of the place where the palace should be built.
It is guaranteed that the solution is unique.
Constraints
- 1 \leq N \leq 1000
- 0 \leq T \leq 50
- -60 \leq A \leq T
- 0 \leq H_i \leq 10^5
- All values in input are integers.
- The solution is unique.
Input
Input is given from Standard Input in the following format:
N T A H_1 H_2 ... H_N
Output
Print the index of the place where the palace should be built.
Sample Input 1
2 12 5 1000 2000
Sample Output 1
1
- The average temperature of Place 1 is 12-1000 \times 0.006=6 degrees Celsius.
- The average temperature of Place 2 is 12-2000 \times 0.006=0 degrees Celsius.
Thus, the palace should be built at Place 1.
Sample Input 2
3 21 -11 81234 94124 52141
Sample Output 2
3
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 300 点
問題文
Atcoder国には N 個の県があり、これらの県には合計で M 個の市が属しています。
市 i が誕生したのは Y_i 年であり、県 P_i に属しています。
ただし、同じ年に誕生した市が複数存在することはないとします。
それぞれの市に 12 桁の認識番号を割り振ることとなりました。
市 i が 県 P_i に属する市の中で x 番目に誕生した市のとき、市 i の認識番号の上 6 桁は P_i、下 6 桁は x となります。
ただし、P_i や x が 6 桁に満たない場合は 6 桁になるまで 0 を左に追加するものとします。
全ての市の認識番号を求めてください。
ただし、市が 1 つも属さない県がある場合に注意してください。
制約
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq P_i \leq N
- 1 \leq Y_i \leq 10^9
- Y_i は全て異なる
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M P_1 Y_1 : P_M Y_M
出力
全ての市の認識番号を市の番号の昇順に出力せよ。
入力例 1
2 3 1 32 2 63 1 12
出力例 1
000001000002 000002000001 000001000001
- 市 1 は県 1 に属する市の中で 2 番目に誕生したので、認識番号は 000001000002 となります。
- 市 2 は県 2 に属する市の中で 1 番目に誕生したので、認識番号は 000002000001 となります。
- 市 3 は県 1 に属する市の中で 1 番目に誕生したので、認識番号は 000001000001 となります。
入力例 2
2 3 2 55 2 77 2 99
出力例 2
000002000001 000002000002 000002000003
Score: 300 points
Problem Statement
In Republic of Atcoder, there are N prefectures, and a total of M cities that belong to those prefectures.
City i is established in year Y_i and belongs to Prefecture P_i.
You can assume that there are no multiple cities that are established in the same year.
It is decided to allocate a 12-digit ID number to each city.
If City i is the x-th established city among the cities that belong to Prefecture i, the first six digits of the ID number of City i is P_i, and the last six digits of the ID number is x.
Here, if P_i or x (or both) has less than six digits, zeros are added to the left until it has six digits.
Find the ID numbers for all the cities.
Note that there can be a prefecture with no cities.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq P_i \leq N
- 1 \leq Y_i \leq 10^9
- Y_i are all different.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M P_1 Y_1 : P_M Y_M
Output
Print the ID numbers for all the cities, in ascending order of indices (City 1, City 2, ...).
Sample Input 1
2 3 1 32 2 63 1 12
Sample Output 1
000001000002 000002000001 000001000001
- As City 1 is the second established city among the cities that belong to Prefecture 1, its ID number is 000001000002.
- As City 2 is the first established city among the cities that belong to Prefecture 2, its ID number is 000002000001.
- As City 3 is the first established city among the cities that belong to Prefecture 1, its ID number is 000001000001.
Sample Input 2
2 3 2 55 2 77 2 99
Sample Output 2
000002000001 000002000002 000002000003
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 400 点
問題文
あみだくじは, 日本に古くから伝わる伝統的なくじ引きである.
あみだくじを作るには, まず W 本の平行な縦線を引き, 次にそれらを繋ぐ横線を引いていく. それぞれの縦棒の長さは H+1 [cm] であり、横線の端点となれるのは上から 1,2,3,...,H [cm] の位置のみである.
ここで,「正しいあみだくじ」とは, 以下のような条件を満たすあみだくじのことである.
- どの 2 つの横棒も端点を共有しない.
- それぞれの横棒の 2 つの端点は同じ高さになければならない.
- 横棒は隣り合う縦線を繋がなければならない.
縦棒 1 の上端から, 横線があれば必ずそれを通るというルールで下へたどったときに, 最終的にたどり着く縦棒の番号が K となるような「正しいあみだくじ」の本数を 1\ 000\ 000\ 007 で割った余りを求めなさい.
例として, 以下のあみだくじにおいて, 最終的にたどり着く縦棒の番号は 4 である.
制約
- H は 1 以上 100 以下の整数
- W は 1 以上 8 以下の整数
- K は 1 以上 W 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
H W K
出力
条件を満たすあみだくじの本数を 1\ 000\ 000\ 007 で割った余りを出力しなさい.
入力例 1
1 3 2
出力例 1
1
以下の 1 個のあみだくじのみが条件を満たす.
入力例 2
1 3 1
出力例 2
2
以下の 2 個のあみだくじのみが条件を満たす.
入力例 3
2 3 3
出力例 3
1
以下の 1 個のあみだくじのみが条件を満たす.
入力例 4
2 3 1
出力例 4
5
以下の 5 個のあみだくじのみが条件を満たす.
入力例 5
7 1 1
出力例 5
1
縦線が 1 本しかないので, 横線をそもそも引くことができない. よって条件を満たすあみだくじは「一本も横線を引かない」の 1 通りしかない.
入力例 6
15 8 5
出力例 6
437760187
答えを 1\ 000\ 000\ 007 で割った余りを出力すること.
Score: 400 points
Problem Statement
Amidakuji is a traditional method of lottery in Japan.
To make an amidakuji, we first draw W parallel vertical lines, and then draw horizontal lines that connect them. The length of each vertical line is H+1 [cm], and the endpoints of the horizontal lines must be at 1, 2, 3, ..., or H [cm] from the top of a vertical line.
A valid amidakuji is an amidakuji that satisfies the following conditions:
- No two horizontal lines share an endpoint.
- The two endpoints of each horizontal lines must be at the same height.
- A horizontal line must connect adjacent vertical lines.
Find the number of the valid amidakuji that satisfy the following condition, modulo 1\ 000\ 000\ 007: if we trace the path from the top of the leftmost vertical line to the bottom, always following horizontal lines when we encounter them, we reach the bottom of the K-th vertical line from the left.
For example, in the following amidakuji, we will reach the bottom of the fourth vertical line from the left.
Constraints
- H is an integer between 1 and 100 (inclusive).
- W is an integer between 1 and 8 (inclusive).
- K is an integer between 1 and W (inclusive).
Input
Input is given from Standard Input in the following format:
H W K
Output
Print the number of the amidakuji that satisfy the condition, modulo 1\ 000\ 000\ 007.
Sample Input 1
1 3 2
Sample Output 1
1
Only the following one amidakuji satisfies the condition:
Sample Input 2
1 3 1
Sample Output 2
2
Only the following two amidakuji satisfy the condition:
Sample Input 3
2 3 3
Sample Output 3
1
Only the following one amidakuji satisfies the condition:
Sample Input 4
2 3 1
Sample Output 4
5
Only the following five amidakuji satisfy the condition:
Sample Input 5
7 1 1
Sample Output 5
1
As there is only one vertical line, we cannot draw any horizontal lines. Thus, there is only one amidakuji that satisfies the condition: the amidakuji with no horizontal lines.
Sample Input 6
15 8 5
Sample Output 6
437760187
Be sure to print the answer modulo 1\ 000\ 000\ 007.