実行時間制限: 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 点
問題文
A 以上 B 以下であるような C の倍数を、1 つ出力してください。
条件を満たす数が存在しない場合は -1 を出力してください。
制約
- 1 \leq A \leq B \leq 1000
- 1 \leq C \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
A B C
出力
答えを出力せよ。
条件を満たす数が存在しない場合は -1 を出力せよ。
入力例 1
123 456 100
出力例 1
200
300 や 400 も正解です。
入力例 2
630 940 314
出力例 2
-1
Score : 100 points
Problem Statement
Print a number between A and B (inclusive) that is a multiple of C.
If there is no such number, print -1.
Constraints
- 1 \leq A \leq B \leq 1000
- 1 \leq C \leq 1000
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B C
Output
Print the answer.
If there is no number with the desired property, print -1.
Sample Input 1
123 456 100
Sample Output 1
200
300 or 400 would also be accepted.
Sample Input 2
630 940 314
Sample Output 2
-1
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
英小文字からなる長さ N の文字列 S が与えられます。 S の x 文字目 (1 \le x \le N) は S_x です。
i=1,2,\dots,N-1 それぞれについて、以下の条件を全て満たす最大の非負整数 l を求めてください。
- l+i \le N である。
- 全ての 1 \le k \le l を満たす整数 k について、 S_{k} \neq S_{k+i} を満たす。
なお、 l=0 は常に条件を満たすことに注意してください。
制約
- N は 2 \le N \le 5000 を満たす整数
- S は英小文字からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
N-1 行にわたって出力せよ。そのうち x 行目 (1 \le x < N) には i=x とした場合の答えを整数として出力せよ。
入力例 1
6 abcbac
出力例 1
5 1 2 0 1
この入力では、 S= abcbac です。
- i=1 のとき、 S_1 \neq S_2, S_2 \neq S_3, \dots ,S_5 \neq S_6 であるため、 最大値は l=5 です。
- i=2 のとき、 S_1 \neq S_3 ですが S_2 = S_4 であるため、 最大値は l=1 です。
- i=3 のとき、 S_1 \neq S_4, S_2 \neq S_5 ですが S_3 = S_6 であるため、 最大値は l=2 です。
- i=4 のとき、 S_1 = S_5 であるため、 最大値は l=0 です。
- i=5 のとき、 S_1 \neq S_6 であるため、 最大値は l=1 です。
Score : 200 points
Problem Statement
You are given a string S of length N consisting of lowercase English letters. The x-th (1 \le x \le N) character of S is S_x.
For each i=1,2,\dots,N-1, find the maximum non-negative integer l that satisfies all of the following conditions:
- l+i \le N, and
- for all integers k such that 1 \le k \le l, it holds that S_{k} \neq S_{k+i}.
Note that l=0 always satisfies the conditions.
Constraints
- N is an integer such that 2 \le N \le 5000.
- S is a string of length N consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
N S
Output
Print (N-1) lines. The x-th (1 \le x < N) line should contain the answer as an integer when i=x.
Sample Input 1
6 abcbac
Sample Output 1
5 1 2 0 1
In this input, S= abcbac.
- When i=1, we have S_1 \neq S_2, S_2 \neq S_3, \dots, and S_5 \neq S_6, so the maximum value is l=5.
- When i=2, we have S_1 \neq S_3 but S_2 = S_4, so the maximum value is l=1.
- When i=3, we have S_1 \neq S_4 and S_2 \neq S_5 but S_3 = S_6, so the maximum value is l=2.
- When i=4, we have S_1 = S_5, so the maximum value is l=0.
- When i=5, we have S_1 \neq S_6, so the maximum value is l=1.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と表します。
各マスの状態は文字 C_{i,j} で表されます。C_{i,j} が . ならば (i, j) には何も置かれておらず、 # ならば箱が 1 個置かれています。
1 \leq j \leq W を満たす整数 j に対して、整数 X_j を次のように定義します。
- j 列目に置かれている箱の個数。言い換えると、C_{i,j} が
#であるような整数 i の個数。
X_1, X_2, \dots, X_W をすべて求めてください。
制約
- 1 \leq H \leq 1000
- 1 \leq W \leq 1000
- H, W は整数
- C_{i, j} は
.または#
入力
入力は以下の形式で標準入力から与えられる。
H W
C_{1,1}C_{1,2}\dots C_{1,W}
C_{2,1}C_{2,2}\dots C_{2,W}
\vdots
C_{H,1}C_{H,2}\dots C_{H,W}
出力
X_1, X_2, \dots, X_W を以下の形式に従って出力せよ。
X_1 X_2 \dots X_W
入力例 1
3 4 #..# .#.# .#.#
出力例 1
1 2 0 3
1 列目の箱が置かれているマスは (1, 1) の 1 ヵ所です。よって X_1 = 1 です。
2 列目の箱が置かれているマスは (2, 2), (3, 2) の 2 ヵ所です。よって X_2 = 2 です。
3 列目の箱が置かれているマスは存在しません。よって X_3 = 0 です。
4 列目の箱が置かれているマスは (1, 4), (2, 4), (3, 4) の 3 ヵ所です。よって X_4 = 3 です。
よって (X_1, X_2, X_3, X_4) = (1, 2, 0, 3) が答えとなります。
入力例 2
3 7 ....... ....... .......
出力例 2
0 0 0 0 0 0 0
箱が置かれているマスが存在しない場合もあります。
入力例 3
8 3 .#. ### .#. .#. .## ..# ##. .##
出力例 3
2 7 4
入力例 4
5 47 .#..#..#####..#...#..#####..#...#...###...##### .#.#...#.......#.#...#......##..#..#...#..#.... .##....#####....#....#####..#.#.#..#......##### .#.#...#........#....#......#..##..#...#..#.... .#..#..#####....#....#####..#...#...###...#####
出力例 4
0 5 1 2 2 0 0 5 3 3 3 3 0 0 1 1 3 1 1 0 0 5 3 3 3 3 0 0 5 1 1 1 5 0 0 3 2 2 2 2 0 0 5 3 3 3 3
Score : 200 points
Problem Statement
There is a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
The squares are described by characters C_{i,j}. If C_{i,j} is ., (i, j) is empty; if it is #, (i, j) contains a box.
For integers j satisfying 1 \leq j \leq W, let the integer X_j defined as follows.
- X_j is the number of boxes in the j-th column. In other words, X_j is the number of integers i such that C_{i,j} is
#.
Find all of X_1, X_2, \dots, X_W.
Constraints
- 1 \leq H \leq 1000
- 1 \leq W \leq 1000
- H and W are integers.
- C_{i, j} is
.or#.
Input
The input is given from Standard Input in the following format:
H W
C_{1,1}C_{1,2}\dots C_{1,W}
C_{2,1}C_{2,2}\dots C_{2,W}
\vdots
C_{H,1}C_{H,2}\dots C_{H,W}
Output
Print X_1, X_2, \dots, X_W in the following format:
X_1 X_2 \dots X_W
Sample Input 1
3 4 #..# .#.# .#.#
Sample Output 1
1 2 0 3
In the 1-st column, one square, (1, 1), contains a box. Thus, X_1 = 1.
In the 2-nd column, two squares, (2, 2) and (3, 2), contain a box. Thus, X_2 = 2.
In the 3-rd column, no squares contain a box. Thus, X_3 = 0.
In the 4-th column, three squares, (1, 4), (2, 4), and (3, 4), contain a box. Thus, X_4 = 3.
Therefore, the answer is (X_1, X_2, X_3, X_4) = (1, 2, 0, 3).
Sample Input 2
3 7 ....... ....... .......
Sample Output 2
0 0 0 0 0 0 0
There may be no square that contains a box.
Sample Input 3
8 3 .#. ### .#. .#. .## ..# ##. .##
Sample Output 3
2 7 4
Sample Input 4
5 47 .#..#..#####..#...#..#####..#...#...###...##### .#.#...#.......#.#...#......##..#..#...#..#.... .##....#####....#....#####..#.#.#..#......##### .#.#...#........#....#......#..##..#...#..#.... .#..#..#####....#....#####..#...#...###...#####
Sample Output 4
0 5 1 2 2 0 0 5 3 3 3 3 0 0 1 1 3 1 1 0 0 5 3 3 3 3 0 0 5 1 1 1 5 0 0 3 2 2 2 2 0 0 5 3 3 3 3
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 250 点
問題文
一台のバスが走っています。バスの乗客の数は常に非負整数です。
このバスにはある時点で 0 人以上の乗客が乗っており、その時点から現在までに N 回停車しました。このうち i 回目の停車では乗客が差し引き A_i 人増えました。A_i は負の値であることもあり、その場合は乗客が差し引き -A_i 人減ったことを意味しています。また、停車時以外には乗客の乗り降りはありませんでした。
与えられた情報に矛盾しない現在のバスの乗客の数として考えられる最小値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq A_i \leq 10^9
- 入力される数値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
4 3 -5 7 -4
出力例 1
3
はじめに乗っている乗客の人数が 2 人であるとき、現在の乗客の人数は 2 + 3 + (-5) + 7 + (-4) = 3 人であり、さらにバスの乗客の人数は常に非負整数となります。
入力例 2
5 0 0 0 0 0
出力例 2
0
入力例 3
4 -1 1000000000 1000000000 1000000000
出力例 3
3000000000
Score: 250 points
Problem Statement
A bus is in operation. The number of passengers on the bus is always a non-negative integer.
At some point in time, the bus had zero or more passengers, and it has stopped N times since then. At the i-th stop, the number of passengers increased by A_i. Here, A_i can be negative, meaning the number of passengers decreased by -A_i. Also, no passengers got on or off the bus other than at the stops.
Find the minimum possible current number of passengers on the bus that is consistent with the given information.
Constraints
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq A_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
4 3 -5 7 -4
Sample Output 1
3
If the initial number of passengers was 2, the current number of passengers would be 2 + 3 + (-5) + 7 + (-4) = 3, and the number of passengers on the bus would have always been a non-negative integer.
Sample Input 2
5 0 0 0 0 0
Sample Output 2
0
Sample Input 3
4 -1 1000000000 1000000000 1000000000
Sample Output 3
3000000000