実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
あるプログラミングコンテストでは、以下のルールに従って参加者に T シャツをプレゼントします。
- 上位 A 位までの参加者は、必ず T シャツが貰える。
- 加えて、上位 A+1 位から B 位までの参加者のうち C 人が一様ランダムに選ばれ、選ばれた参加者は T シャツを貰える。
コンテストには 1000 人が参加し、全ての参加者が相異なる順位を取りました。
このコンテストの参加者であるいろはちゃんは、X 位を取りました。
このとき、いろはちゃんが T シャツを貰える確率を求めてください。
制約
- 入力はすべて整数
- 1 \le A < B \le 1000
- 1 \le C \le B-A
- 1 \le X \le 1000
入力
入力は以下の形式で標準入力から与えられる。
A B C X
出力
答えを出力せよ。 なお、想定解との絶対誤差または相対誤差が 10^{−6} 以下であれば、正解として扱われる。
入力例 1
30 500 20 103
出力例 1
0.042553191489
いろはちゃんは 103 位を取りました。
31 位から 500 位までの 470 人の参加者の中から 20 人が一様ランダムに選ばれ、ここで選ばれるといろはちゃんは T シャツを貰えます。この確率は \frac{20}{470}=0.04255319\dots です。
入力例 2
50 500 100 1
出力例 2
1.000000000000
いろはちゃんは 1 位を取りました。この入力において、いろはちゃんは確実に T シャツを貰えます。
入力例 3
1 2 1 1000
出力例 3
0.000000000000
いろはちゃんは 1000 位を取りました。この入力において、いろはちゃんが T シャツを貰えることはありません。
Score : 100 points
Problem Statement
In a certain programming contest, T-shirts are awarded to participants according to the following rules.
- All participants who ranked A-th or higher get a T-shirt.
- Additionally, from the participants who ranked between (A+1)-th and B-th (inclusive), C participants chosen uniformly at random get a T-shirt.
There were 1000 participants in this contest, and all of them got different ranks.
Iroha-chan, who participated in this contest, ranked X-th.
Find the probability that she gets a T-shirt.
Constraints
- All values in input are integers.
- 1 \le A < B \le 1000
- 1 \le C \le B-A
- 1 \le X \le 1000
Input
Input is given from Standard Input in the following format:
A B C X
Output
Print the answer. Your output will be considered correct if the absolute or relative error from the judge's answer is at most 10^{−6}.
Sample Input 1
30 500 20 103
Sample Output 1
0.042553191489
Iroha-chan ranked 103-rd.
She will get a T-shirt if she is among the 20 participants chosen uniformly at random from the 470 participants who ranked between 31-st and 500-th, which happens with probability \frac{20}{470}=0.04255319\dots.
Sample Input 2
50 500 100 1
Sample Output 2
1.000000000000
Iroha-chan ranked 1-st. This time, she is guaranteed to get a T-shirt.
Sample Input 3
1 2 1 1000
Sample Output 3
0.000000000000
Iroha-chan ranked 1000-th. This time, she will never get a T-shirt.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
数字からなる文字列 S が与えられます。
S から 2 以外の文字を削除し、残った文字を順序を保って結合した文字列を求めてください。
制約
- S は数字からなる長さ 1 以上 100 以下の文字列
- S は
2を 1 つ以上含む
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
20250222
出力例 1
22222
20250222 から 0, 5, 0 を削除し、残った文字を順序を保って結合することで文字列 22222 が得られます。
入力例 2
2
出力例 2
2
入力例 3
22222000111222222
出力例 3
22222222222
Score : 100 points
Problem Statement
You are given a string S consisting of digits.
Remove all characters from S except for 2, and then concatenate the remaining characters in their original order to form a new string.
Constraints
- S is a string consisting of digits with length between 1 and 100, inclusive.
- S contains at least one
2.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
20250222
Sample Output 1
22222
By removing 0, 5, and 0 from 20250222 and then concatenating the remaining characters in their original order, the string 22222 is obtained.
Sample Input 2
2
Sample Output 2
2
Sample Input 3
22222000111222222
Sample Output 3
22222222222
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 250 点
問題文
東西に無限に伸びる道路があり、この道路上のある基準となる地点から東に x\mathrm{\,m} のところにある地点の座標は x と定められています。 特に、基準となる地点から西に x\mathrm{\,m} のところにある地点の座標は -x です。
すぬけ君は今から、座標が A である地点を基点にして M\mathrm{\,m} おきにクリスマスツリーを立てます。 すなわち、座標がある整数 k を用いて A+kM と表されるような地点それぞれにクリスマスツリーを立てます。
高橋君と青木君はそれぞれ座標が L,R\ (L\leq R) である地点に立っています。 高橋君と青木君の間（高橋君と青木君が立っている地点を含む）に立てられるクリスマスツリーの本数を求めてください。
制約
- -10^{18}\leq A \leq 10^{18}
- 1\leq M \leq 10^9
- -10^{18}\leq L\leq R \leq 10^{18}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
A M L R
出力
高橋君と青木君の間（高橋君と青木君が立っている地点を含む）に立てられるクリスマスツリーの本数を出力せよ。
入力例 1
5 3 -1 6
出力例 1
3
すぬけ君は、座標が \dots,-4,-1,2,5,8,11,14\dots である地点にクリスマスツリーを立てます。 これらのうち高橋君と青木君の間にあるのは、座標が -1,2,5 である地点に立てられる 3 本です。
入力例 2
-2 2 1 1
出力例 2
0
高橋君と青木君が同じ地点に立っていることもあります。
入力例 3
-177018739841739480 2436426 -80154573737296504 585335723211047198
出力例 3
273142010859
Score : 250 points
Problem Statement
There is a road that stretches infinitely to the east and west, and the coordinate of a point located x meters to the east from a certain reference point on this road is defined as x. In particular, the coordinate of a point located x meters to the west from the reference point is -x.
Snuke will set up Christmas trees at points on the road at intervals of M meters, starting from a point with coordinate A. In other words, he will set up a Christmas tree at each point that can be expressed as A+kM using some integer k.
Takahashi and Aoki are standing at points with coordinates L and R (L\leq R), respectively. Find the number of Christmas trees that will be set up between Takahashi and Aoki (including the points where they are standing).
Constraints
- -10^{18}\leq A \leq 10^{18}
- 1\leq M \leq 10^9
- -10^{18}\leq L\leq R \leq 10^{18}
- All input values are integers.
Input
Input is given from Standard Input in the following format:
A M L R
Output
Print the number of Christmas trees that will be set up between Takahashi and Aoki (including the points where they are standing).
Sample Input 1
5 3 -1 6
Sample Output 1
3
Snuke will set up Christmas trees at points with coordinates \dots,-4,-1,2,5,8,11,14\dots. Three of them at coordinates -1, 2, and 5 are between Takahashi and Aoki.
Sample Input 2
-2 2 1 1
Sample Output 2
0
Sometimes, Takahashi and Aoki are standing at the same point.
Sample Input 3
-177018739841739480 2436426 -80154573737296504 585335723211047198
Sample Output 3
273142010859
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
N 人の人が、M 問からなるプログラミングコンテストに参加しました。
参加者は人 1, 人 2, \ldots, 人 N と番号づけられており、問題は問題 1, 問題 2, \ldots, 問題 M と番号づけられています。
このコンテストでは K 個のイベントが順番に起き、i 番目 (1\leq i\leq K) のイベントでは次のことが起きました。
- 人 A_i が問題 B_i に正解した。
同じイベントが 2 回以上起きることはありません。 また、この K 個のイベント以外に誰かがどれかの問題に正解することはありません。
すべての問題に正解した人の番号を全員出力してください。
そのような人が複数いる場合は、すべての問題に正解したタイミングが早い順に出力してください。
制約
- 1 \leq N \leq 10
- 1 \leq M \leq 10
- K \geq 1
- 1 \leq A_i\leq N
- 1 \leq B_i\leq M
- i\neq j ならば (A_i,B_i)\neq (A_j,B_j)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M K A_1 B_1 A_2 B_2 \vdots A_K B_K
出力
すべての問題に正解した人の番号を、すべての問題に正解したタイミングが早い順に空白区切りで一行に出力せよ。
すべての問題に正解した人がいないならば、何も出力しないようにせよ。
入力例 1
3 2 5 1 1 3 2 2 1 3 1 1 2
出力例 1
3 1
コンテストでは次のことが順に起きました。
- 人 1 が問題 1 に正解した。人 1 はこれまでに、問題 1 のみに正解した。
- 人 3 が問題 2 に正解した。人 3 はこれまでに、問題 2 のみに正解した。
- 人 2 が問題 1 に正解した。人 2 はこれまでに、問題 1 のみに正解した。
- 人 3 が問題 1 に正解した。人 3 はこれまでに、問題 1,2 に正解した。よって、この時点で人 3 はすべての問題に正解した。
- 人 1 が問題 2 に正解した。人 1 はこれまでに、問題 1,2 に正解した。よって、この時点で人 1 はすべての問題に正解した。
よって、すべての問題に正解したのは人 1,3 であり、すべての問題に正解したタイミングは人 3 の方が早いです。
よって、3,1 をこの順に空白区切りで出力します。
入力例 2
2 2 2 1 1 2 2
出力例 2
すべての問題に正解した人がいない場合は、何も出力しないでください。
Score : 200 points
Problem Statement
N people participated in a programming contest consisting of M problems.
The participants are numbered person 1, person 2, \ldots, person N, and the problems are numbered problem 1, problem 2, \ldots, problem M.
In this contest, K events occurred in order; in the i-th event (1\leq i\leq K), the following happened:
- Person A_i solved problem B_i.
The same event does not occur two or more times. Also, apart from these K events, nobody solves any problem.
Output the numbers of all people who solved all problems.
If there are multiple such people, output them in ascending order of the time at which they solved all problems.
Constraints
- 1 \leq N \leq 10
- 1 \leq M \leq 10
- K \geq 1
- 1 \leq A_i \leq N
- 1 \leq B_i \leq M
- If i\neq j then (A_i,B_i)\neq (A_j,B_j).
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M K A_1 B_1 A_2 B_2 \vdots A_K B_K
Output
Output, on one line and separated by spaces, the numbers of all people who solved all problems, in ascending order of the time at which they solved all problems. If there is no person who solved all problems, output nothing.
Sample Input 1
3 2 5 1 1 3 2 2 1 3 1 1 2
Sample Output 1
3 1
In the contest, the following happened in order.
- Person 1 solved problem 1. So far, person 1 has solved only problem 1.
- Person 3 solved problem 2. So far, person 3 has solved only problem 2.
- Person 2 solved problem 1. So far, person 2 has solved only problem 1.
- Person 3 solved problem 1. So far, person 3 has solved problems 1,2. Thus, at this point person 3 has solved all problems.
- Person 1 solved problem 2. So far, person 1 has solved problems 1,2. Thus, at this point person 1 has solved all problems.
Thus, the people who solved all problems are persons 1,3, and the one who solved all problems earlier is person 3. Thus, output 3,1 in this order, separated by spaces.
Sample Input 2
2 2 2 1 1 2 2
Sample Output 2
If there is no person who solved all problems, output nothing.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
長さ N の文字列 S が与えられます。S_i\ (1\leq i \leq N) を S の左から i 番目の文字とします。
あなたは以下の 2 種類の操作を好きな順番で 0 回以上好きな回数行うことができます。
-
A 円払う。 S の左端の文字を右端に移動する。すなわち、S_1S_2\ldots S_N を S_2\ldots S_NS_1 に変える。
-
B 円払う。 1 以上 N 以下の整数 i を選び、 S_i を好きな英小文字で置き換える。
S を回文にするためには最低で何円必要ですか？
回文とは
ある文字列 T について、 T の長さを |T| として、全ての整数 i (1 \le i \le |T|) について、 T の前から i 文字目と後ろから i 文字目が同じであるとき、またそのときに限って、 T は回文です。制約
- 1\leq N \leq 5000
- 1\leq A,B\leq 10^9
- S は英小文字からなる長さ N の文字列
- S 以外の入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A B S
出力
答えを整数として出力せよ。
入力例 1
5 1 2 rrefa
出力例 1
3
最初に 2 番目の操作を 1 回行います。2 円払い、i=5 として S_5 を e で置き換えます。 S は rrefe となります。
次に 1 番目の操作を 1 回行います。1 円払い、S は refer となります。これは回文です。
よって 3 円払うことで S を回文にすることができました。 2 円以下払うことで S を回文にすることは不可能なので、これが答えです。
入力例 2
8 1000000000 1000000000 bcdfcgaa
出力例 2
4000000000
答えは 32 bit 整数に収まらない場合があることに注意してください。
Score : 300 points
Problem Statement
You are given a string S of length N. Let S_i\ (1\leq i \leq N) be the i-th character of S from the left.
You may perform the following two kinds of operations zero or more times in any order:
-
Pay A yen (the currency in Japan). Move the leftmost character of S to the right end. In other words, change S_1S_2\ldots S_N to S_2\ldots S_NS_1.
-
Pay B yen. Choose an integer i between 1 and N, and replace S_i with any lowercase English letter.
How many yen do you need to pay to make S a palindrome?
What is a palindrome?
A string T is a palindrome if and only if the i-th character from the left and the i-th character from the right are the same for all integers i (1 \le i \le |T|), where |T| is the length of T.Constraints
- 1\leq N \leq 5000
- 1\leq A,B\leq 10^9
- S is a string of length N consisting of lowercase English letters.
- All values in the input except for S are integers.
Input
The input is given from Standard Input in the following format:
N A B S
Output
Print the answer as an integer.
Sample Input 1
5 1 2 rrefa
Sample Output 1
3
First, pay 2 yen to perform the operation of the second kind once: let i=5 to replace S_5 with e. S is now rrefe.
Then, pay 1 yen to perform the operation of the first kind once. S is now refer, which is a palindrome.
Thus, you can make S a palindrome for 3 yen. Since you cannot make S a palindrome for 2 yen or less, 3 is the answer.
Sample Input 2
8 1000000000 1000000000 bcdfcgaa
Sample Output 2
4000000000
Note that the answer may not fit into a 32-bit integer type.