実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
英小文字からなる長さ N の文字列 S が与えられます。S の末尾の文字を出力してください。
制約
- N は整数
- 1 ≤ N ≤ 1000
- S は英小文字からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
S の末尾の文字を出力せよ。
入力例 1
5 abcde
出力例 1
e
S = {}abcde です。S の末尾の文字は e なので、e を出力します。
入力例 2
1 a
出力例 2
a
Score : 100 points
Problem Statement
Given a string S of length N consisting of lowercase English alphabets, print the last character of S.
Constraints
- N is an integer.
- 1 ≤ N ≤ 1000
- S is a string of length N consisting of lowercase English alphabets.
Input
Input is given from Standard Input in the following format:
N S
Output
Print the last character of S.
Sample Input 1
5 abcde
Sample Output 1
e
The last character of S = {}abcde is e, so e should be printed.
Sample Input 2
1 a
Sample Output 2
a
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
英小文字からなる文字列 S が与えられます。
S に a が現れるならば最後に現れるのが何文字目かを出力し、現れないならば -1 を出力してください。
制約
- S は英小文字からなる長さ 1 以上 100 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
abcdaxayz
出力例 1
7
S に a は 3 回現れますが、最後に現れるのは 7 文字目なので、7 を出力します。
入力例 2
bcbbbz
出力例 2
-1
S に a は現れないので、-1 を出力します。
入力例 3
aaaaa
出力例 3
5
Score : 100 points
Problem Statement
You are given a string S consisting of lowercase English letters.
If a appears in S, print the last index at which it appears; otherwise, print -1. (The index starts at 1.)
Constraints
- S is a string of length between 1 and 100 (inclusive) consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
abcdaxayz
Sample Output 1
7
a appears three times in S. The last occurrence is at index 7, so you should print 7.
Sample Input 2
bcbbbz
Sample Output 2
-1
a does not appear in S, so you should print -1.
Sample Input 3
aaaaa
Sample Output 3
5
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
1 から N までの番号がついた N 個の数列が与えられます。
数列 i は、長さが L_i で j (1 \leq j \leq L_i) 番目の要素が a_{i,j} であるような数列です。
数列 i と 数列 j は、 L_i = L_j かつすべての k (1 \leq k \leq L_i) に対して a_{i,k} = a_{j,k} が成り立つ時に同じであるとみなします。
同じ数列は 1 種類として数えるとき、数列 1 から 数列 N の中に全部で何種類の数列がありますか？
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq L_i \leq 2 \times 10^5 (1 \leq i \leq N)
- 0 \leq a_{i,j} \leq 10^{9} (1 \leq i \leq N, 1 \leq j \leq L_i)
- すべての数列の要素の個数の和、すなわち \sum_{i=1}^N L_i は 2 \times 10^5 を超えない。
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
L_1 a_{1,1} a_{1,2} \dots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \dots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \dots a_{N,L_N}
出力
数列の種類数を出力せよ。
入力例 1
4 2 1 2 2 1 1 2 2 1 2 1 2
出力例 1
3
入力例 1 で与えられている数列は以下の 4 個です。
- 数列 1 : (1, 2)
- 数列 2 : (1, 1)
- 数列 3 : (2, 1)
- 数列 4 : (1, 2)
このうち数列 1 と数列 4 は同じ数列で、それ以外は互いに異なる数列なので全部で 3 種類の数列があります。
入力例 2
5 1 1 1 1 1 2 2 1 1 3 1 1 1
出力例 2
4
入力例 2 で与えられている数列は以下の 5 個です。
- 数列 1 : (1)
- 数列 2 : (1)
- 数列 3 : (2)
- 数列 4 : (1, 1)
- 数列 5 : (1, 1, 1)
入力例 3
1 1 1
出力例 3
1
Score : 200 points
Problem Statement
You are given N sequences numbered 1 to N.
Sequence i has a length of L_i and its j-th element (1 \leq j \leq L_i) is a_{i,j}.
Sequence i and Sequence j are considered the same when L_i = L_j and a_{i,k} = a_{j,k} for every k (1 \leq k \leq L_i).
How many different sequences are there among Sequence 1 through Sequence N?
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq L_i \leq 2 \times 10^5 (1 \leq i \leq N)
- 0 \leq a_{i,j} \leq 10^{9} (1 \leq i \leq N, 1 \leq j \leq L_i)
- The total number of elements in the sequences, \sum_{i=1}^N L_i, does not exceed 2 \times 10^5.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
L_1 a_{1,1} a_{1,2} \dots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \dots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \dots a_{N,L_N}
Output
Print the number of different sequences.
Sample Input 1
4 2 1 2 2 1 1 2 2 1 2 1 2
Sample Output 1
3
Sample Input 1 contains four sequences:
- Sequence 1 : (1, 2)
- Sequence 2 : (1, 1)
- Sequence 3 : (2, 1)
- Sequence 4 : (1, 2)
Except that Sequence 1 and Sequence 4 are the same, these sequences are pairwise different, so we have three different sequences.
Sample Input 2
5 1 1 1 1 1 2 2 1 1 3 1 1 1
Sample Output 2
4
Sample Input 2 contains five sequences:
- Sequence 1 : (1)
- Sequence 2 : (1)
- Sequence 3 : (2)
- Sequence 4 : (1, 1)
- Sequence 5 : (1, 1, 1)
Sample Input 3
1 1 1
Sample Output 3
1
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
長さ N の正整数列 a = (a_1, a_2, \dots, a_N) には何種類の整数が現れますか？
制約
- 1 \leq N \leq 1000
- 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N a_1 \ldots a_N
出力
答えを出力せよ。
入力例 1
6 1 4 1 2 2 1
出力例 1
3
1, 2, 4 の 3 種類の整数が現れます。
入力例 2
1 1
出力例 2
1
入力例 3
11 3 1 4 1 5 9 2 6 5 3 5
出力例 3
7
Score : 200 points
Problem Statement
In a sequence of N positive integers a = (a_1, a_2, \dots, a_N), how many different integers are there?
Constraints
- 1 \leq N \leq 1000
- 1 \leq a_i \leq 10^9 \, (1 \leq i \leq N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N a_1 \ldots a_N
Output
Print the answer.
Sample Input 1
6 1 4 1 2 2 1
Sample Output 1
3
There are three different integers: 1, 2, 4.
Sample Input 2
1 1
Sample Output 2
1
Sample Input 3
11 3 1 4 1 5 9 2 6 5 3 5
Sample Output 3
7
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 個の袋があります。
袋 i には L_i 個のボールが入っていて、袋 i の j(1\leq j\leq L_i) 番目のボールには正の整数 a_{i,j} が書かれています。
それぞれの袋から 1 つずつボールを取り出します。
取り出したボールに書かれた数の総積が X になるような取り出し方は何通りありますか？
ただし、書かれた数が同じであっても全てのボールは区別します。
制約
- N \geq 2
- L_i \geq 2
- 袋に入っているボールの個数の総積は 10^5 を超えない。すなわち、\displaystyle\prod_{i=1}^{N}L_i \leq 10^5
- 1 \leq a_{i,j} \leq 10^9
- 1 \leq X \leq 10^{18}
- 入力に含まれる値は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N X
L_1 a_{1,1} a_{1,2} \ldots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \ldots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \ldots a_{N,L_N}
出力
答えを出力せよ。
入力例 1
2 40 3 1 8 4 2 10 5
出力例 1
2
袋 1 の 3 番目のボールと袋 2 の 1 番目のボールを選ぶと、a_{1,3} \times a_{2,1} = 4 \times 10 = 40 となります。
袋 1 の 2 番目のボールと袋 2 の 2 番目のボールを選ぶと、a_{1,2} \times a_{2,2} = 8 \times 5 = 40 となります。
これ以外に総積が 40 になる取り出し方は存在しないので、答えは 2 です。
入力例 2
3 200 3 10 10 10 3 10 10 10 5 2 2 2 2 2
出力例 2
45
書かれた数が同じであっても全てのボールは区別することに注意してください。
入力例 3
3 1000000000000000000 2 1000000000 1000000000 2 1000000000 1000000000 2 1000000000 1000000000
出力例 3
0
総積が X になる取り出し方が 1 つも存在しないこともあります。
Score : 300 points
Problem Statement
We have N bags.
Bag i contains L_i balls. The j-th ball (1\leq j\leq L_i) in Bag i has a positive integer a_{i,j} written on it.
We will pick out one ball from each bag.
How many ways are there to pick the balls so that the product of the numbers written on the picked balls is X?
Here, we distinguish all balls, even with the same numbers written on them.
Constraints
- N \geq 2
- L_i \geq 2
- The product of the numbers of balls in the bags is at most 10^5: \displaystyle\prod_{i=1}^{N}L_i \leq 10^5.
- 1 \leq a_{i,j} \leq 10^9
- 1 \leq X \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X
L_1 a_{1,1} a_{1,2} \ldots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \ldots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \ldots a_{N,L_N}
Output
Print the answer.
Sample Input 1
2 40 3 1 8 4 2 10 5
Sample Output 1
2
When choosing the 3-rd ball in Bag 1 and 1-st ball in Bag 2, we have a_{1,3} \times a_{2,1} = 4 \times 10 = 40.
When choosing the 2-nd ball in Bag 1 and 2-nd ball in Bag 2, we have a_{1,2} \times a_{2,2} = 8 \times 5 = 40.
There are no other ways to make the product 40, so the answer is 2.
Sample Input 2
3 200 3 10 10 10 3 10 10 10 5 2 2 2 2 2
Sample Output 2
45
Note that we distinguish all balls, even with the same numbers written on them.
Sample Input 3
3 1000000000000000000 2 1000000000 1000000000 2 1000000000 1000000000 2 1000000000 1000000000
Sample Output 3
0
There may be no way to make the product X.