Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
A の奇数番目の要素の総和を求めてください。すなわち、N 以下の最大の奇数を m としたとき A_1+A_3+A_5+\ldots+A_m を求めてください。
制約
- 1\leq N\leq 100
- 1\leq A_i\leq 100
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
7 3 1 4 1 5 9 2
出力例 1
14
A の奇数番目の要素の総和は A_1+A_3+A_5+A_7=3+4+5+2=14 です。
入力例 2
1 100
出力例 2
100
入力例 3
14 100 10 1 10 100 10 1 10 100 10 1 10 100 10
出力例 3
403
Score : 100 points
Problem Statement
You are given a sequence of positive integers of length N: A=(A_1,A_2,\dots,A_N).
Find the sum of the odd-indexed elements of A. That is, find A_1 + A_3 + A_5 + \dots + A_m, where m is the largest odd number not exceeding N.
Constraints
- 1 \le N \le 100
- 1 \le A_i \le 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
7 3 1 4 1 5 9 2
Sample Output 1
14
The sum of the odd-indexed elements of A is A_1+A_3+A_5+A_7=3+4+5+2=14.
Sample Input 2
1 100
Sample Output 2
100
Sample Input 3
14 100 10 1 10 100 10 1 10 100 10 1 10 100 10
Sample Output 3
403
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
数字のみからなる、長さがちょうど 9 の文字列 S が与えられます。
S には 0 から 9 までのうち、ちょうど 1 つの数字を除いた 9 種類の数字が一度ずつ登場します。
S に登場しない唯一の数字を出力してください。
制約
- S は数字のみからなる長さ 9 の文字列である。
- S の文字はすべて相異なる。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S に登場しない唯一の数字を出力せよ。
入力例 1
023456789
出力例 1
1
文字列 023456789 には 1 のみが登場していません。
よって、1 を出力します。
入力例 2
459230781
出力例 2
6
文字列 459230781 には 6 のみが登場していません。
よって、6 を出力します。
文字列に数字が現れる順番は昇順とは限らないので注意してください。
Score : 100 points
Problem Statement
You are given a string S of length exactly 9 consisting of digits.
One but all digits from 0 to 9 appear exactly once in S.
Print the only digit missing in S.
Constraints
- S is a string of length 9 consisting of digits.
- All characters in S are distinct.
Input
Input is given from Standard Input in the following format:
S
Output
Print the only digit missing in S.
Sample Input 1
023456789
Sample Output 1
1
The string 023456789 only lacks 1.
Thus, 1 should be printed.
Sample Input 2
459230781
Sample Output 2
6
The string 459230781 only lacks 6.
Thus, 6 should be printed.
Note that the digits in the string may not appear in increasing order.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
H 行 W 列のグリッドがあります。グリッドの上から i 番目、左から j 番目のマスをマス (i, j) と表記します。
マス (i, j) は C_{i, j} が . のとき空きマスであり、# のとき空きマスではありません。
高橋君は現在マス (S_i, S_j) におり、i = 1, 2, \ldots, |X| の順に以下のルールに従って行動します。
- X の i 文字目が
Lのとき、高橋君が現在いるマスの 1 つ左のマスが存在し、そのマスが空きマスならば 1 つ左のマスに移動する。そうでないならば、現在いるマスに留まる。 - X の i 文字目が
Rのとき、高橋君が現在いるマスの 1 つ右のマスが存在し、そのマスが空きマスならば 1 つ右のマスに移動する。そうでないならば、現在いるマスに留まる。 - X の i 文字目が
Uのとき、高橋君が現在いるマスの 1 つ上のマスが存在し、そのマスが空きマスならば 1 つ上のマスに移動する。そうでないならば、現在いるマスに留まる。 - X の i 文字目が
Dのとき、高橋君が現在いるマスの 1 つ下のマスが存在し、そのマスが空きマスならば 1 つ下のマスに移動する。そうでないならば、現在いるマスに留まる。
一連の行動を終えた後高橋君がどのマスにいるか出力してください。
制約
- 1 \leq H, W \leq 50
- 1 \leq S_i \leq H
- 1 \leq S_j \leq W
- H, W, S_i, S_j は整数
- C_{i, j} は
.または# - C_{S_i, S_j} =
. - X は
L,R,U,Dからなる長さ 1 以上 50 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
H W
S_i S_j
C_{1, 1}C_{1, 2}\ldotsC_{1, W}
C_{2, 1}C_{2, 2}\ldotsC_{2, W}
\vdots
C_{H, 1}C_{H, 2}\ldotsC_{H, W}
X
出力
高橋君が一連の行動を終えた後にいるマスをマス (x, y) として、x と y をこの順に空白区切りで出力せよ。
入力例 1
2 3 2 1 .#. ... ULDRU
出力例 1
2 2
高橋君ははじめマス (2, 1) にいます。高橋君の一連の行動は以下のようになります。
- X の 1 文字目は
Uであり、マス (2, 1) の 1 つ上のマスは存在し、そのマスは空きマスであるため 1 つ上のマスであるマス (1, 1) に移動する。 - X の 2 文字目は
Lであり、マス (1, 1) の 1 つ左のマスは存在しないためマス (1, 1) に留まる。 - X の 3 文字目は
Dであり、マス (1, 1) の 1 つ下のマスは存在し、そのマスは空きマスであるため 1 つ下のマスであるマス (2, 1) に移動する。 - X の 4 文字目は
Rであり、マス (2, 1) の 1 つ右のマスは存在し、そのマスは空きマスであるため 1 つ右のマスであるマス (2, 2) に移動する。 - X の 5 文字目は
Uであり、マス (2, 2) の 1 つ上のマスは存在するが、そのマスは空きマスではないためマス (2, 2) に留まる。
したがって一連の行動を終えた後に高橋君がいるマスはマス (2, 2) です。
入力例 2
4 4 4 2 .... .#.. ...# .... DUUUURULRD
出力例 2
2 4
入力例 3
6 6 1 1 .##### ###### ###### ###### ###### ###### RURLDLULLRULRDL
出力例 3
1 1
Score : 200 points
Problem Statement
There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.
Cell (i, j) is empty if C_{i, j} is ., and not empty if C_{i, j} is #.
Takahashi is currently at cell (S_i, S_j), and he will act according to the following rules for i = 1, 2, \ldots, |X| in order.
- If the i-th character of X is
L, and the cell to the left of his current cell exists and is empty, he moves to the cell to the left. Otherwise, he stays in the current cell. - If the i-th character of X is
R, and the cell to the right of his current cell exists and is empty, he moves to the cell to the right. Otherwise, he stays in the current cell. - If the i-th character of X is
U, and the cell above his current cell exists and is empty, he moves to the cell above. Otherwise, he stays in the current cell. - If the i-th character of X is
D, and the cell below his current cell exists and is empty, he moves to the cell below. Otherwise, he stays in the current cell.
Print the cell where he is after completing the series of actions.
Constraints
- 1 \leq H, W \leq 50
- 1 \leq S_i \leq H
- 1 \leq S_j \leq W
- H, W, S_i, S_j are integers.
- C_{i, j} is
.or#. - C_{S_i, S_j} =
. - X is a string of length between 1 and 50, inclusive, consisting of
L,R,U,D.
Input
The input is given from Standard Input in the following format:
H W
S_i S_j
C_{1, 1}C_{1, 2}\ldotsC_{1, W}
C_{2, 1}C_{2, 2}\ldotsC_{2, W}
\vdots
C_{H, 1}C_{H, 2}\ldotsC_{H, W}
X
Output
Let (x, y) be the cell where Takahashi is after completing the series of actions. Print x and y, separated by a space.
Sample Input 1
2 3 2 1 .#. ... ULDRU
Sample Output 1
2 2
Takahashi starts at cell (2, 1). His series of actions are as follows:
- The 1st character of X is
U, and the cell above (2, 1) exists and is an empty cell, so he moves to the cell above, which is (1, 1). - The 2nd character of X is
L, and the cell to the left of (1, 1) does not exist, so he stays at (1, 1). - The 3rd character of X is
D, and the cell below (1, 1) exists and is an empty cell, so he moves to the cell below, which is (2, 1). - The 4th character of X is
R, and the cell to the right of (2, 1) exists and is an empty cell, so he moves to the cell to the right, which is (2, 2). - The 5th character of X is
U, and the cell above (2, 2) exists but is not an empty cell, so he stays at (2, 2).
Therefore, after completing the series of actions, he is at cell (2, 2).
Sample Input 2
4 4 4 2 .... .#.. ...# .... DUUUURULRD
Sample Output 2
2 4
Sample Input 3
6 6 1 1 .##### ###### ###### ###### ###### ###### RURLDLULLRULRDL
Sample Output 3
1 1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
以下のような N 個の整数列 A_0,\ldots,A_{N-1} を求めてください。
- 各 i (0\leq i \leq N-1) について、A_i の長さは i+1 である。
-
各 i,j (0\leq i \leq N-1, 0 \leq j \leq i) について、A_i の j+1 番目の値 a_{i,j} は次のように定められる。
- j=0 または j=i の時、a_{i,j}=1
- それ以外の時、a_{i,j} = a_{i-1,j-1} + a_{i-1,j}
制約
- 1 \leq N \leq 30
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N 行出力せよ。 i 行目には A_{i-1} の値を順に空白区切りで出力せよ。
入力例 1
3
出力例 1
1 1 1 1 2 1
入力例 2
10
出力例 2
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1
Score : 200 points
Problem Statement
Find the N integer sequences A_0,\ldots,A_{N-1} defined as follows.
- For each i (0\leq i \leq N-1), the length of A_i is i+1.
- For each i and j (0\leq i \leq N-1, 0 \leq j \leq i), the (j+1)-th term of A_i, denoted by a_{i,j}, is defined as follows.
- a_{i,j}=1, if j=0 or j=i.
- a_{i,j} = a_{i-1,j-1} + a_{i-1,j}, otherwise.
Constraints
- 1 \leq N \leq 30
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print N lines. The i-th line should contain the terms of A_{i-1} separated by spaces.
Sample Input 1
3
Sample Output 1
1 1 1 1 2 1
Sample Input 2
10
Sample Output 2
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 350 点
問題文
整数列 A = (A_1, A_2, \ldots, A_{|A|}) に対し、A が チルダ型 とは以下の 4 つの条件をすべて満たすことであると定義します。
- A の長さ |A| は 4 以上である
- A_1 < A_2 である
- A_{i - 1} < A_i > A_{i + 1} を満たす 2 \leq i < |A| なる整数 i はちょうど 1 個である
- A_{i - 1} > A_i < A_{i + 1} を満たす 2 \leq i < |A| なる整数 i はちょうど 1 個である
数列 (1, 2, \ldots, N) を並べ替えて得られる数列 P = (P_1, P_2, \ldots, P_N) が与えられます。P の連続部分列であってチルダ型である数列の個数を求めてください。
制約
- 4 \leq N \leq 3 \times 10^5
- P = (P_1, P_2, \ldots, P_N) は (1, 2, \ldots, N) を並べ替えて得られる数列
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \ldots P_N
出力
答えを出力せよ。
入力例 1
6 1 3 6 4 2 5
出力例 1
2
数列 (1, 3, 6, 4, 2, 5) の連続部分列のうちチルダ型であるものは (3, 6, 4, 2, 5), (1, 3, 6, 4, 2, 5) の 2 つのみです。
入力例 2
6 1 2 3 4 5 6
出力例 2
0
入力例 3
12 11 3 8 9 5 2 10 4 1 6 12 7
出力例 3
4
Score : 350 points
Problem Statement
For an integer sequence A = (A_1, A_2, \ldots, A_{|A|}), we say that A is tilde-shaped if it satisfies all of the following four conditions:
- The length |A| is at least 4.
- A_1 < A_2.
- There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} < A_i > A_{i+1}.
- There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} > A_i < A_{i+1}.
You are given a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N). Find the number of (contiguous) subarrays of P that are tilde-shaped.
Constraints
- 4 \leq N \leq 3 \times 10^5
- P = (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N).
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \ldots P_N
Output
Output the answer.
Sample Input 1
6 1 3 6 4 2 5
Sample Output 1
2
Among the subarrays of (1, 3, 6, 4, 2, 5), exactly two are tilde-shaped: (3, 6, 4, 2, 5) and (1, 3, 6, 4, 2, 5).
Sample Input 2
6 1 2 3 4 5 6
Sample Output 2
0
Sample Input 3
12 11 3 8 9 5 2 10 4 1 6 12 7
Sample Output 3
4