Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
A を N 個、B を N 個、…、Z を N 個この順に繋げて得られる文字列の先頭から X 番目の文字を求めてください。
制約
- 1 \leq N \leq 100
- 1 \leq X \leq N\times 26
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X
出力
答えを出力せよ。
入力例 1
1 3
出力例 1
C
得られる文字列は ABCDEFGHIJKLMNOPQRSTUVWXYZ です。先頭から 3 番目の文字は C です。
入力例 2
2 12
出力例 2
F
得られる文字列は AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ です。先頭から 12 番目の文字は F です。
Score : 100 points
Problem Statement
Find the X-th character from the beginning of the string that is obtained by concatenating these characters: N copies of A's, N copies of B's, …, and N copies of Z's, in this order.
Constraints
- 1 \leq N \leq 100
- 1 \leq X \leq N\times 26
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X
Output
Print the answer.
Sample Input 1
1 3
Sample Output 1
C
We obtain the string ABCDEFGHIJKLMNOPQRSTUVWXYZ, whose 3-rd character from the beginning is C.
Sample Input 2
2 12
Sample Output 2
F
We obtain the string AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ, whose 12-th character from the beginning is F.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
高橋君は N 週間の間、自分が歩いた歩数を記録しました。i 日目に歩いた歩数は A_i でした。
各週に高橋君が歩いた歩数の合計を求めてください。
より正確には、1 週目( 1 日目から 7 日目まで)の 7 日間の歩数の合計、2 週目( 8 日目から 14 日目まで)の 7 日間の歩数の合計、……をそれぞれ求めてください。
制約
- 1 \leq N \leq 10
- 0 \leq A_i \leq 10^5
- 入力は整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \ldots A_{7N}
出力
i 週目に歩いた歩数を B_i とする。B_1,B_2,\ldots,B_N をこの順に空白区切りで出力せよ。
入力例 1
2 1000 2000 3000 4000 5000 6000 7000 2000 3000 4000 5000 6000 7000 8000
出力例 1
28000 35000
高橋君は 1 週目に 1000+2000+3000+4000+5000+6000+7000=28000 歩あるき、2 週目に 2000+3000+4000+5000+6000+7000+8000=35000 歩あるきました。
入力例 2
3 14159 26535 89793 23846 26433 83279 50288 41971 69399 37510 58209 74944 59230 78164 6286 20899 86280 34825 34211 70679 82148
出力例 2
314333 419427 335328
Score : 100 points
Problem Statement
Takahashi has recorded the number of steps he walked for N weeks. He walked A_i steps on the i-th day.
Find the total number of steps Takahashi walked each week.
More precisely, find the sum of the steps for the first week (the 1-st through 7-th day), the sum of the steps for the second week (the 8-th through 14-th day), and so on.
Constraints
- 1 \leq N \leq 10
- 0 \leq A_i \leq 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_1 A_2 \ldots A_{7N}
Output
Let B_i be the number of steps walked for the i-th week. Print B_1,B_2,\ldots,B_N in this order, separated by spaces.
Sample Input 1
2 1000 2000 3000 4000 5000 6000 7000 2000 3000 4000 5000 6000 7000 8000
Sample Output 1
28000 35000
For the first week, he walked 1000+2000+3000+4000+5000+6000+7000=28000 steps, and for the second week, he walked 2000+3000+4000+5000+6000+7000+8000=35000 steps.
Sample Input 2
3 14159 26535 89793 23846 26433 83279 50288 41971 69399 37510 58209 74944 59230 78164 6286 20899 86280 34825 34211 70679 82148
Sample Output 2
314333 419427 335328
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
配点 : 200 点
問題文
N 頂点 N-1 辺の木が与えられます。
頂点には 1,2,\ldots,N の番号がついており、i 本目の辺は頂点 a_i と頂点 b_i を結んでいます。
この木がスターであるか判定してください。
ただしスターとは、1 つの頂点から、他の全ての頂点に 1 本ずつ辺が出ている木のことです。
注記
「木」については、Wikipedia「木(数学)」 を参照してください。
制約
- 3 \leq N \leq 10^5
- 1 \leq a_i \lt b_i \leq N
- 与えられるグラフは木である
入力
入力は以下の形式で標準入力から与えられる。
N
a_1 b_1
\vdots
a_{N-1} b_{N-1}
出力
与えられたグラフがスターであるなら Yes と、スターでないなら No と出力せよ。
入力例 1
5 1 4 2 4 3 4 4 5
出力例 1
Yes
与えられたグラフはスターです。
入力例 2
4 2 4 1 4 2 3
出力例 2
No
与えられたグラフはスターではありません。
入力例 3
10 9 10 3 10 4 10 8 10 1 10 2 10 7 10 6 10 5 10
出力例 3
Yes
Score : 200 points
Problem Statement
You are given a tree with N vertices and N-1 edges.
The vertices are numbered 1,2,\ldots,N. The i-th edge connects Vertex a_i and Vertex b_i.
Determine whether this tree is a star.
Here, a star is a tree where there is a vertex directly connected to all other vertices.
Notes
For the definition of a tree, see Tree (graph theory) - Wikipedia.
Constraints
- 3 \leq N \leq 10^5
- 1 \leq a_i \lt b_i \leq N
- The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N
a_1 b_1
\vdots
a_{N-1} b_{N-1}
Output
If the given graph is a star, print Yes; otherwise, print No.
Sample Input 1
5 1 4 2 4 3 4 4 5
Sample Output 1
Yes
The given graph is a star.
Sample Input 2
4 2 4 1 4 2 3
Sample Output 2
No
The given graph is not a star.
Sample Input 3
10 9 10 3 10 4 10 8 10 1 10 2 10 7 10 6 10 5 10
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
非負整数 N が与えられるので、以下の条件を満たす非負整数 x を昇順に全て出力してください。
- x を 2 進数として表記した時に 1 となる位の集合が、 N を 2 進数として表記した時に 1 となる位の集合の部分集合となる。
- すなわち、全ての非負整数 k について、「 x の 2^k の位が 1 ならば、 N の 2^k の位は 1 」が成り立つ。
制約
- N は整数
- 0 \le N < 2^{60}
- N を 2 進数として表記した時、 1 となる位は 15 個以下である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを 1 行に 1 つずつ、10 進法の整数として昇順に出力せよ。
入力例 1
11
出力例 1
0 1 2 3 8 9 10 11
N = 11_{(10)} を 2 進数で表記すると、 1011_{(2)} となります。
条件を満たす非負整数 x は以下の通りです。
- 0000_{(2)}=0_{(10)}
- 0001_{(2)}=1_{(10)}
- 0010_{(2)}=2_{(10)}
- 0011_{(2)}=3_{(10)}
- 1000_{(2)}=8_{(10)}
- 1001_{(2)}=9_{(10)}
- 1010_{(2)}=10_{(10)}
- 1011_{(2)}=11_{(10)}
入力例 2
0
出力例 2
0
入力例 3
576461302059761664
出力例 3
0 524288 549755813888 549756338176 576460752303423488 576460752303947776 576461302059237376 576461302059761664
入力は 32bit 符号付き整数に収まらない可能性があります。
Score : 300 points
Problem Statement
You are given a non-negative integer N. Print all non-negative integers x that satisfy the following condition in ascending order.
- The set of the digit positions containing 1 in the binary representation of x is a subset of the set of the digit positions containing 1 in the binary representation of N.
- That is, the following holds for every non-negative integer k: if the digit in the "2^ks" place of x is 1, the digit in the 2^ks place of N is 1.
Constraints
- N is an integer.
- 0 \le N < 2^{60}
- In the binary representation of N, at most 15 digit positions contain 1.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer as decimal integers in ascending order, each in its own line.
Sample Input 1
11
Sample Output 1
0 1 2 3 8 9 10 11
The binary representation of N = 11_{(10)} is 1011_{(2)}.
The non-negative integers x that satisfy the condition are:
- 0000_{(2)}=0_{(10)}
- 0001_{(2)}=1_{(10)}
- 0010_{(2)}=2_{(10)}
- 0011_{(2)}=3_{(10)}
- 1000_{(2)}=8_{(10)}
- 1001_{(2)}=9_{(10)}
- 1010_{(2)}=10_{(10)}
- 1011_{(2)}=11_{(10)}
Sample Input 2
0
Sample Output 2
0
Sample Input 3
576461302059761664
Sample Output 3
0 524288 549755813888 549756338176 576460752303423488 576460752303947776 576461302059237376 576461302059761664
The input may not fit into a 32-bit signed integer.