Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
1,\ldots,N の番号のついた N 人の選手がゲームを行いました。選手 i のスコアは A_i であり、スコアが小さい方が上位になります。
ブービー賞に該当する選手、すなわち、下位から 2 番目の選手の番号を求めてください。
制約
- 2 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- A_i は相異なる
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \ldots A_N
出力
答えを出力せよ。
入力例 1
6 1 123 12345 12 1234 123456
出力例 1
3
6 人中 5 位になるのは、選手 3 です。
入力例 2
5 3 1 4 15 9
出力例 2
5
Score : 200 points
Problem Statement
N players, who are numbered 1, \ldots, N, have played a game. Player i has scored A_i, and a player with a smaller score ranks higher.
The player who ranks the second lowest will receive a booby prize. Who is this player? Answer with an integer representing the player.
Constraints
- 2 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- A_i are distinct.
- 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 123 12345 12 1234 123456
Sample Output 1
3
It is Player 3 who ranks fifth among the six players.
Sample Input 2
5 3 1 4 15 9
Sample Output 2
5
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
AtCoder 国の暦では、一年は 1,2,\dots,M 番目の月の M か月からなり、そのうち i 番目の月は 1,2,\dots,D_i 番目の日の D_i 日からなります。
さらに、 AtCoder 国の一年の日数は奇数、即ち D_1+D_2+\dots+D_M は奇数です。
一年の真ん中の日は何番目の月の何番目の日か求めてください。
言い換えると、 1 番目の月の 1 番目の日を 1 日目としたときの (D_1+D_2+\dots+D_M+1)/2 日目が何番目の月の何番目の日かを求めてください。
制約
- 入力は全て整数
- 1 \le M \le 100
- 1 \le D_i \le 100
- D_1 + D_2 + \dots + D_M は奇数
入力
入力は以下の形式で標準入力から与えられる。
M D_1 D_2 \dots D_M
出力
答えが a 番目の月の b 番目の日であるとき、以下の形式で出力せよ。
a b
入力例 1
12 31 28 31 30 31 30 31 31 30 31 30 31
出力例 1
7 2
この入力では、 1 年は 31+28+31+30+31+30+31+31+30+31+30+31=365 日からなります。
真ん中の日は (365+1)/2 = 183 日目であり、これを求めることを考えます。
- 1,2,3,4,5,6 番目の月に含まれる日数の合計は 181 日です。
- 7 番目の月の 1 番目の日は 182 日目です。
- 7 番目の月の 2 番目の日は 183 日目です。
以上から、答えが 7 番目の月の 2 番目の日であることが分かります。
入力例 2
1 1
出力例 2
1 1
入力例 3
6 3 1 4 1 5 9
出力例 3
5 3
Score : 200 points
Problem Statement
In the calendar of AtCoderLand, a year consists of M months: month 1, month 2, \dots, month M. The i-th month consists of D_i days: day 1, day 2, \dots, day D_i.
Furthermore, the number of days in a year is odd, that is, D_1+D_2+\dots+D_M is odd.
Find what day of what month is the middle day of the year.
In other words, let day 1 of month 1 be the first day, and find a and b such that the ((D_1+D_2+\dots+D_M+1)/2)-th day is day b of month a.
Constraints
- All input values are integers.
- 1 \le M \le 100
- 1 \le D_i \le 100
- D_1 + D_2 + \dots + D_M is odd.
Input
The input is given from Standard Input in the following format:
M D_1 D_2 \dots D_M
Output
Let the answer be day b of month a, and print it in the following format:
a b
Sample Input 1
12 31 28 31 30 31 30 31 31 30 31 30 31
Sample Output 1
7 2
In this input, a year consists of 31+28+31+30+31+30+31+31+30+31+30+31=365 days.
Let us find the middle day, which is the ((365+1)/2 = 183)-th day.
- Months 1,2,3,4,5,6 contain a total of 181 days.
- Day 1 of month 7 is the 182-th day.
- Day 2 of month 7 is the 183-th day.
Thus, the answer is day 2 of month 7.
Sample Input 2
1 1
Sample Output 2
1 1
Sample Input 3
6 3 1 4 1 5 9
Sample Output 3
5 3
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 個の商品があります。i = 1, 2, \ldots, N について、i 番目の商品の値段は A_i 円です。
高橋君は K 枚のクーポンを持っています。
1 枚のクーポンは 1 つの商品に対して使用することができ、1 つの商品に対してはクーポンを何枚でも( 0 枚でもよい)使用することができます。
値段が a 円の商品に対して k 枚のクーポンを使用すると、その商品を \max\lbrace a - kX, 0\rbrace 円で買うことができます。
高橋君がすべての商品を買うために支払う合計金額の最小値を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K, X \leq 10^9
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K X A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
5 4 7 8 3 10 5 13
出力例 1
12
1 番目の商品に対してクーポン 1 枚、3 番目の商品に対してクーポン 1 枚、5 番目の商品に対してクーポン 2 枚を使用すると、
- 1 番目の商品を \max\lbrace A_1-X, 0 \rbrace = 1 円で買うことができ、
- 2 番目の商品を \max\lbrace A_2, 0 \rbrace = 3 円で買うことができ、
- 3 番目の商品を \max\lbrace A_3-X, 0 \rbrace = 3 円で買うことができ、
- 4 番目の商品を \max\lbrace A_4, 0 \rbrace = 5 円で買うことができ、
- 5 番目の商品を \max\lbrace A_5-2X, 0 \rbrace = 0 円で買うことができます。
よって、すべての商品を 1 + 3 + 3 + 5 + 0 = 12 円で買うことができ、これが最小です。
入力例 2
5 100 7 8 3 10 5 13
出力例 2
0
入力例 3
20 815 60 2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202
出力例 3
112
Score : 300 points
Problem Statement
There are N items in a shop. For each i = 1, 2, \ldots, N, the price of the i-th item is A_i yen (the currency of Japan).
Takahashi has K coupons.
Each coupon can be used on one item. You can use any number of coupons, possibly zero, on the same item. Using k coupons on an item with a price of a yen allows you to buy it for \max\lbrace a - kX, 0\rbrace yen.
Print the minimum amount of money Takahashi needs to buy all the items.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K, X \leq 10^9
- 1 \leq A_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K X A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
5 4 7 8 3 10 5 13
Sample Output 1
12
By using 1 coupon on the 1-st item, 1 coupon on the 3-rd item, and 2 coupons on the 5-th item, Takahashi can:
- buy the 1-st item for \max\lbrace A_1-X, 0 \rbrace = 1 yen,
- buy the 2-nd item for \max\lbrace A_2, 0 \rbrace = 3 yen,
- buy the 3-rd item for \max\lbrace A_3-X, 0 \rbrace = 3 yen,
- buy the 4-th item for \max\lbrace A_4, 0 \rbrace = 5 yen,
- buy the 5-th item for \max\lbrace A_5-2X, 0 \rbrace = 0 yen,
for a total of 1 + 3 + 3 + 5 + 0 = 12 yen, which is the minimum possible.
Sample Input 2
5 100 7 8 3 10 5 13
Sample Output 2
0
Sample Input 3
20 815 60 2066 3193 2325 4030 3725 1669 1969 763 1653 159 5311 5341 4671 2374 4513 285 810 742 2981 202
Sample Output 3
112
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋くんは、プログラミングコンテストを主催することにしました。
コンテストは A 問題、B 問題、C 問題、D 問題、E 問題の 5 問からなり、それぞれの配点は a 点、b 点、c 点、d 点、e 点です。
コンテストには 31 人が参加し、全員が 1 問以上解きました。
より具体的には、文字列 ABCDE の空でない(連続するとは限らない)部分列すべてについて、その部分列を名前とする参加者が存在し、その参加者は名前に含まれる文字に対応する問題をすべて解き、それ以外の問題は解きませんでした。
例えば、A さんは A 問題のみを、BCE さんは B 問題、C 問題、E 問題を解きました。
参加者の名前を、取った点数が大きいほうから順に出力してください。 ただし、参加者が取った点数は、その参加者が解いた問題の配点の合計です。
ただし、同じ点数を獲得した参加者については、名前が辞書順で小さいほうを先に出力してください。
辞書順で小さいとは?
辞書順とは、一言で説明すると「単語が辞書に載っている順番」を意味します。
より厳密には、英大文字からなる相異なる文字列 S,T について、S が T より辞書順で小さいとは、以下の条件のどちらかが成り立つことを意味します。
- S の長さ |S| が T の長さより短く、T の先頭 |S| 文字が S と一致する
- ある整数 1\leq i\leq\min\lbrace|S|,|T|\rbrace が存在して、次の 2 つの条件を両方を満たす
- 1\leq j\lt i を満たすすべての整数 j に対して S の j 文字目と T の j 文字目が等しい
- S の i 文字目が T の i 文字目よりアルファベット順で小さい
例えば、S= AB ,T= ABC とすると、ひとつめの条件が成り立つため S は T より小さいです。
また、S= ABD ,T= ACD とすると、ふたつめの条件が i=2 で成り立つため S は T より小さいです。
制約
- 100\leq a\leq b\leq c\leq d\leq e\leq 2718
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
a b c d e
出力
31 行出力せよ。 i 行目 (1\leq i\leq 31) には、i 番目に高い得点を獲得した参加者の名前を出力せよ。 同じ得点を獲得した参加者については、それらのうち辞書順で小さい名前をもつ参加者を先に出力せよ。
入力例 1
400 500 600 700 800
出力例 1
ABCDE BCDE ACDE ABDE ABCE ABCD CDE BDE ADE BCE ACE BCD ABE ACD ABD ABC DE CE BE CD AE BD AD BC AC AB E D C B A
それぞれの参加者の得点は以下のようになります。

例えば、ADE さんと BCE さんは同じ得点を獲得していますが、ADE さんのほうが辞書順で小さい名前をもつため、ADE さんを先に出力してください。
入力例 2
800 800 900 900 1000
出力例 2
ABCDE ACDE BCDE ABCE ABDE ABCD CDE ACE ADE BCE BDE ABE ACD BCD ABC ABD CE DE AE BE CD AC AD BC BD AB E C D A B
入力例 3
128 256 512 1024 2048
出力例 3
ABCDE BCDE ACDE CDE ABDE BDE ADE DE ABCE BCE ACE CE ABE BE AE E ABCD BCD ACD CD ABD BD AD D ABC BC AC C AB B A
Score : 300 points
Problem Statement
Takahashi decided to hold a programming contest.
The contest consists of five problems: A, B, C, D, E, with scores a, b, c, d, e, respectively.
There are 31 participants, and all of them solved at least one problem.
More specifically, for every non-empty subsequence (not necessarily contiguous) of the string ABCDE, there is a participant named after that subsequence who solved the problems corresponding to the letters in their name and did not solve the other problems.
For example, participant A solved only problem A, and participant BCE solved problems B, C, and E.
Print the names of the participants in order of their obtained scores, from the largest to the smallest. The score obtained by a participant is the sum of the scores of the problems they solved.
If two participants obtained the same score, print the one whose name is lexicographically smaller first.
What does "lexicographically smaller" mean?
In short, "lexicographically smaller" refers to the order in which words would appear in a dictionary.
More precisely, for distinct strings S,T consisting of uppercase English letters, S is lexicographically smaller than T if either of the following conditions holds:
- The length |S| of S is less than the length of T, and the first |S| characters of T match S.
- There exists an integer 1\leq i\leq\min\{ |S|,|T|\} that satisfy both of the following two conditions:
- For every integer j with 1\leq j\lt i, the j-th character of S equals the j-th character of T.
- The i-th character of S is alphabetically smaller than the i-th character of T.
For example, if S= AB and T= ABC, the first condition holds, so S is lexicographically smaller than T.
If S= ABD and T= ACD, the second condition holds for i=2, so S is lexicographically smaller than T.
Constraints
- 100\leq a\leq b\leq c\leq d\leq e\leq 2718
- All input values are integers.
Input
The input is given from Standard Input in the following format:
a b c d e
Output
Print 31 lines. The i-th line (1\leq i\leq 31) should contain the name of the participant who obtained the i-th highest score. If multiple participants have the same score, print them in lexicographical order.
Sample Input 1
400 500 600 700 800
Sample Output 1
ABCDE BCDE ACDE ABDE ABCE ABCD CDE BDE ADE BCE ACE BCD ABE ACD ABD ABC DE CE BE CD AE BD AD BC AC AB E D C B A
The score of each participant is as follows:

For example, ADE and BCE obtained the same score, and ADE is lexicographically smaller, so print ADE before BCE.
Sample Input 2
800 800 900 900 1000
Sample Output 2
ABCDE ACDE BCDE ABCE ABDE ABCD CDE ACE ADE BCE BDE ABE ACD BCD ABC ABD CE DE AE BE CD AC AD BC BD AB E C D A B
Sample Input 3
128 256 512 1024 2048
Sample Output 3
ABCDE BCDE ACDE CDE ABDE BDE ADE DE ABCE BCE ACE CE ABE BE AE E ABCD BCD ACD CD ABD BD AD D ABC BC AC C AB B A
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は N 種類の硬貨をそれぞれ何枚か持っており、 具体的には、1\leq i\leq N について A_i 円硬貨を B_i 枚持っています。
高橋君が現在持っている硬貨を用いて、(お釣りが出ないように)ちょうど X 円を支払うことができるか判定してください。
制約
- 1\leq N\leq 50
- 1\leq X\leq 10^4
- 1\leq A_i\leq 100
- 1\leq B_i\leq 50
- A_i はすべて異なる。
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
高橋君が現在持っている硬貨を用いてちょうど X 円を支払うことができる場合は Yes を、
できない場合は No を出力せよ。
入力例 1
2 19 2 3 5 6
出力例 1
Yes
高橋君は 2 円硬貨を 3 枚、5 円硬貨を 6 枚持っています。
このうち、2 円硬貨を 2 枚、5 円硬貨を 3 枚用いることでちょうど 2\times 2+5\times 3=19 円を支払うことができます。
よって、Yes を出力します。
入力例 2
2 18 2 3 5 6
出力例 2
No
持っている硬貨をどのように組み合わせてもちょうど 18 円を支払うことはできません。
よって、No を出力します。
入力例 3
3 1001 1 1 2 1 100 10
出力例 3
Yes
1 枚も使用しない硬貨が存在しても構いません。
Score : 400 points
Problem Statement
Takahashi has N kinds of coins; specifically, for 1\leq i\leq N, he has B_i coins worth A_i yen (the currency in Japan) each.
Determine if Takahashi can pay exactly X yen (without change) with the coins he currently has.
Constraints
- 1\leq N\leq 50
- 1\leq X\leq 10^4
- 1\leq A_i\leq 100
- 1\leq B_i\leq 50
- A_i are pairwise distinct.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N X A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print Yes if Takahashi can pay exactly X yen with the coins he currently has;
print No otherwise.
Sample Input 1
2 19 2 3 5 6
Sample Output 1
Yes
Takahashi has three 2-yen coins and six 5-yen coins.
He can use two 2-yen coins and three 5-yen coins to pay exactly 2\times 2+5\times 3=19 yen.
Thus, Yes should be printed.
Sample Input 2
2 18 2 3 5 6
Sample Output 2
No
There is no combination of the coins that he can use to pay exactly 18 yen.
Thus, No should be printed.
Sample Input 3
3 1001 1 1 2 1 100 10
Sample Output 3
Yes
He need not use all kinds of coins.