Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
N 匹のヘビがいます。
はじめ、i 匹目のヘビの太さは T_i、長さは L_i です。
ヘビの重さは太さと長さの積となります。
1 \leq k \leq D を満たす各整数 k について、すべてのヘビの長さが k 伸びたときの最も重いヘビの重さを求めてください。
制約
- 1 \leq N, D \leq 100
- 1 \leq T_i, L_i \leq 100
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D T_1 L_1 T_2 L_2 \vdots T_N L_N
出力
D 行出力せよ。k 行目には、すべてのヘビの長さが k 伸びたときの最も重いヘビの重さを出力せよ。
入力例 1
4 3 3 3 5 1 2 4 1 10
出力例 1
12 15 20
すべてのヘビの長さが 1 伸びたとき、ヘビの重さはそれぞれ 12, 10, 10, 11 となるので 1 行目には 12 を出力します。
すべてのヘビの長さが 2 伸びたとき、ヘビの重さはそれぞれ 15, 15, 12, 12 となるので 2 行目には 15 を出力します。
すべてのヘビの長さが 3 伸びたとき、ヘビの重さはそれぞれ 18, 20, 14, 13 となるので 3 行目には 20 を出力します。
入力例 2
1 4 100 100
出力例 2
10100 10200 10300 10400
Score : 200 points
Problem Statement
There are N snakes.
Initially, the thickness of the i-th snake is T_i, and its length is L_i.
The weight of a snake is defined as the product of its thickness and length.
For each integer k satisfying 1 \leq k \leq D, find the weight of the heaviest snake when every snake's length has increased by k.
Constraints
- 1 \leq N, D \leq 100
- 1 \leq T_i, L_i \leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D T_1 L_1 T_2 L_2 \vdots T_N L_N
Output
Print D lines. The k-th line should contain the weight of the heaviest snake when every snake's length has increased by k.
Sample Input 1
4 3 3 3 5 1 2 4 1 10
Sample Output 1
12 15 20
When every snake’s length has increased by 1, the snakes' weights become 12, 10, 10, 11, so print 12 on the first line.
When every snake’s length has increased by 2, the snakes' weights become 15, 15, 12, 12, so print 15 on the second line.
When every snake’s length has increased by 3, the snakes' weights become 18, 20, 14, 13, so print 20 on the third line.
Sample Input 2
1 4 100 100
Sample Output 2
10100 10200 10300 10400
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
AtCoder 国では、1 年が N か月からなる暦を使っています。 i 月 (1\leq i\leq N) は、i 月 1 日から i 月 D _ i 日までの D _ i 日からなります。
AtCoder 国において、1 年のうち日付がゾロ目になる日が何日あるか求めてください。
ただし、i 月 j 日 (1\leq i\leq N,1\leq j\leq D _ i) の日付がゾロ目になるとは、1 種類の数字だけを用いて i と j を十進法で表すことができることをいいます。
制約
- 1\leq N\leq100
- 1\leq D _ i\leq100\ (1\leq i\leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D _ 1 D _ 2 \ldots D _ N
出力
答えを出力せよ。
入力例 1
12 31 29 31 30 31 30 31 31 30 31 30 31
出力例 1
13
AtCoder 国では、 1 月 1 日、1 月 11 日、2 月 2 日、2 月 22 日、3 月 3 日、4 月 4 日、5 月 5 日、6 月 6 日、7 月 7 日、8 月 8 日、9 月 9 日、11 月 1 日、11 月 11 日の合計 13 日の日付がゾロ目になります。
入力例 2
10 10 1 2 3 4 5 6 7 8 100
出力例 2
1
AtCoder 国では、1 月 1 日のみが日付がゾロ目になります。
入力例 3
30 73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32
出力例 3
15
Score : 200 points
Problem Statement
AtCoder Kingdom uses a calendar whose year has N months. Month i (1\leq i\leq N) has D _ i days, from day 1 of month i to day D _ i of month i.
How many days in a year of AtCoder have "repdigits" dates?
Here, day j of month i (1\leq i\leq N,1\leq j\leq D _ i) is said to have a repdigit date if and only if all digits in the decimal notations of i and j are the same.
Constraints
- 1\leq N\leq100
- 1\leq D _ i\leq100\ (1\leq i\leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D _ 1 D _ 2 \ldots D _ N
Output
Print the answer.
Sample Input 1
12 31 29 31 30 31 30 31 31 30 31 30 31
Sample Output 1
13
In AtCoder Kingdom, the days that have repdigit dates are January 1, January 11, February 2, February 22, March 3, April 4, May 5, June 6, July 7, August 8, September 9, November 1, and November 11, for a total of 13 days.
Sample Input 2
10 10 1 2 3 4 5 6 7 8 100
Sample Output 2
1
In AtCoder Kingdom, only January 1 has a repdigit date.
Sample Input 3
30 73 8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32
Sample Output 3
15
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
十進法ですべての桁の数字が 1 である整数をレピュニットと呼びます。レピュニットを小さい順に並べると 1,11,111,\ldots です。
ちょうど 3 つのレピュニットの和として表せる整数のうち N 番目に小さいものを求めてください。
制約
- N は 1 以上 333 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
5
出力例 1
113
ちょうど 3 つのレピュニットの和として表せる整数を小さい順に並べると 3,13,23,33,113,\ldots です。例えば 113 は 113=1+1+111 と表せます。
3 つのレピュニットは相異ならなくてもよいことに注意してください。
入力例 2
19
出力例 2
2333
入力例 3
333
出力例 3
112222222233
Score : 300 points
Problem Statement
A repunit is an integer whose digits are all 1 in decimal representation. The repunits in ascending order are 1, 11, 111, \ldots.
Find the N-th smallest integer that can be expressed as the sum of exactly three repunits.
Constraints
- N is an integer between 1 and 333, inclusive.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
5
Sample Output 1
113
The integers that can be expressed as the sum of exactly three repunits are 3, 13, 23, 33, 113, \ldots in ascending order. For example, 113 can be expressed as 113 = 1 + 1 + 111.
Note that the three repunits do not have to be distinct.
Sample Input 2
19
Sample Output 2
2333
Sample Input 3
333
Sample Output 3
112222222233
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 個の文字列 S_1,\ldots,S_N が与えられます。
全ての要素が 1 以上 N 以下であるような長さ K の数列 (A_1,\ldots,A_K) に対し、
文字列 f(A_1,\ldots,A_K) を S_{A_1}+S_{A_2}+\dots+S_{A_K} と定めます。ここで + は文字列の連結を表します。
N^K 個の数列全てについての f(A_1,\dots,A_K) を辞書順に並べたとき、小さい方から X 番目の文字列を求めてください。
制約
- 1\leq N \leq 10
- 1\leq K \leq 5
- 1\leq X \leq N^K
- S_i は英小文字からなる長さ 10 以下の文字列
- N,K,X は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K X S_1 \vdots S_N
出力
答えを出力せよ。
入力例 1
3 2 6 abc xxx abc
出力例 1
abcxxx
- f(1,1)=
abcabc - f(1,2)=
abcxxx - f(1,3)=
abcabc - f(2,1)=
xxxabc - f(2,2)=
xxxxxx - f(2,3)=
xxxabc - f(3,1)=
abcabc - f(3,2)=
abcxxx - f(3,3)=
abcabc
であり、これらを辞書順に並べた abcabc, abcabc, abcabc, abcabc, abcxxx, abcxxx, xxxabc, xxxabc, xxxxxx の 6 番目は abcxxx です。
入力例 2
5 5 416 a aa aaa aa a
出力例 2
aaaaaaa
Score : 300 points
Problem Statement
You are given N strings S_1,\ldots,S_N.
For a sequence (A_1,\ldots,A_K) of length K where all elements are between 1 and N, inclusive,
define the string f(A_1,\ldots,A_K) as S_{A_1}+S_{A_2}+\dots+S_{A_K}. Here, + represents string concatenation.
When all f(A_1,\dots,A_K) for the N^K sequences are sorted in lexicographical order, find the X-th smallest string.
Constraints
- 1\leq N \leq 10
- 1\leq K \leq 5
- 1\leq X \leq N^K
- S_i is a string consisting of lowercase English letters with length at most 10.
- N, K, and X are all integers.
Input
The input is given from Standard Input in the following format:
N K X S_1 \vdots S_N
Output
Output the answer.
Sample Input 1
3 2 6 abc xxx abc
Sample Output 1
abcxxx
- f(1,1)=
abcabc - f(1,2)=
abcxxx - f(1,3)=
abcabc - f(2,1)=
xxxabc - f(2,2)=
xxxxxx - f(2,3)=
xxxabc - f(3,1)=
abcabc - f(3,2)=
abcxxx - f(3,3)=
abcabc
When these are sorted in lexicographical order: abcabc, abcabc, abcabc, abcabc, abcxxx, abcxxx, xxxabc, xxxabc, xxxxxx, the 6-th is abcxxx.
Sample Input 2
5 5 416 a aa aaa aa a
Sample Output 2
aaaaaaa
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
アイドルグループ Bit♡Beat のプロデューサーであるあなたは、次のライブに向けて特訓期間を設けることにしました。
特訓期間の候補日は 1 日目から N 日目までの N 日あり、そのうちの何日かの 連続する 期間を特訓期間とする予定です。
各候補日によってその日に特訓した場合の体力消費量は異なり、 i 日目 (1\le i\le N) に特訓した場合の体力消費量は A_i です。
あなたは、次の条件を満たす特訓期間のうち最も期間が長いものを調べようとしています。
- 特訓期間の平均体力消費量が K 以下である。
条件を満たす特訓期間のうち、最も期間が長いものの長さを求めてください。
ただし、条件を満たす特訓期間が必ず 1 つ以上存在することが保証されます。
制約
- 1\le N\le 2\times 10^5
- 1\le K\le 10^9
- 1\le A_i\le 10^9
- 条件を満たす特訓期間が必ず 1 つ以上存在する
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
5 5 3 8 3 6 6
出力例 1
4
1 日目から 4 日目までの 4 日間を特訓期間とすると、この間の平均体力消費量は \displaystyle \frac{3+8+3+6}4=5 となり条件を満たします。
4 日より長い特訓期間で条件を満たすものは存在しないので、 4 を出力してください。
入力例 2
6 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 2
6
入力例 3
12 11 19 11 13 16 3 16 9 8 11 16 14 11
出力例 3
8