実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
あるプログラミングコンテストの予選に N 人が参加し、参加者全員が異なる順位を得ました。
長さ N の文字列 S が与えられ、この文字列は決勝への参加希望の有無を表現します。具体的には下記の通りです。
- S の i 文字目が
oなら、予選 i 位の参加者が決勝への参加を希望した。 - S の i 文字目が
xなら、予選 i 位の参加者が決勝への参加を希望しなかった。
決勝への参加を希望した参加者のうち順位の小さい方から K 人が予選を通過します。
以下の条件を満たす長さ N の文字列 T を出力してください。
- 予選 i 位の参加者が予選を通過する場合、 T の i 文字目は
o - 予選 i 位の参加者が予選を通過しない場合、 T の i 文字目は
x
制約
- N,K は整数
- 1 \le K \le N \le 100
- S は
oとxからなる長さ N の文字列 - S には少なくとも K 個の
oが含まれる
入力
入力は以下の形式で標準入力から与えられる。
N K S
出力
答えを出力せよ。
入力例 1
10 3 oxxoxooxox
出力例 1
oxxoxoxxxx
この入力の場合、予選の参加者は N=10 人であり、予選を通過する人数は K=3 人です。
- 予選 1 位の参加者は決勝への参加を希望しているため、予選を通過します。この時点で、通過者は 1 人です。
- 予選 2,3 位の参加者は決勝への参加を希望していないため、予選を通過しません。
- 予選 4 位の参加者は決勝への参加を希望しているため、予選を通過します。この時点で、通過者は 2 人です。
- 予選 5 位の参加者は決勝への参加を希望していないため、予選を通過しません。
- 予選 6 位の参加者は決勝への参加を希望しているため、予選を通過します。この時点で、通過者は 3 人です。
- ここで、予選を通過した人数が 3 人となりました。なので、予選 7 位以下の参加者は予選を通過しません。
Score : 200 points
Problem Statement
There were N contestants in the qualification round of a programming contest. All contestants got distinct ranks.
You are given a length-N string S, which represents whether the contestants want to participate in the final round or not. Specifically,
- if the i-th character of S is
o, the contestant ranked i-th in the qualification wants to participate in the final; - if the i-th character of S is
x, the contestant ranked i-th in the qualification does not want to participate in the final.
Among those who want to participate in the final, K contestants with the smallest ranks advance to the final.
Print a string T of length N that satisfies the following conditions:
- if the contestant ranked i-th in the qualification advances to the final, the i-th character of T is
o; - if the contestant ranked i-th in the qualification does not advance to the final, the i-th character of T is
x.
Constraints
- N and K are integers.
- 1 \le K \le N \le 100
- S is a string of length N consisting of
oandx. - S has at least K
o's.
Input
The input is given from Standard Input in the following format:
N K S
Output
Print the answer.
Sample Input 1
10 3 oxxoxooxox
Sample Output 1
oxxoxoxxxx
In this input, N=10 people took part in the qualification round, and K=3 of them advance to the final.
- The participant who ranked 1-st in the qualification wants to participate in the final, so the participant advances to the final. 1 participant has advanced so far.
- The participants who ranked 2-nd and 3-rd in the qualification do not want to participate in the final, so the participants do not advance to the final.
- The participant who ranked 4-th in the qualification wants to participate in the final, so the participant advances to the final. 2 participants have advanced so far.
- The participants who ranked 5-th in the qualification does not want to participate in the final, so the participant does not advance to the final.
- The participant who ranked 6-th in the qualification wants to participate in the final, so the participant advances to the final. 3 participants have advanced so far.
- Now that 3 people have advanced to the final, no participants ranked 7-th or lower advance to the final.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 人の競技プログラマーがいます。順に 人 1, 人 2, \dots, 人 N と呼びます。
競技プログラマーの間には 強さ と呼ばれる関係性があり、相異なる 2 人組 (人 X, 人 Y) 全てに対して 「人 X は人 Y より強い」または「人 Y は人 X より強い」のどちらか一方が成り立ちます。
強さ は 推移律 が成り立ちます。言い換えると、相異なる 3 人組 (人 X, 人 Y, 人 Z) 全てに対して次の条件が成り立ちます。
- 人 X が人 Y よりも強く、かつ人 Y が人 Z よりも強いとき、人 X は人 Z よりも強い。
人 X が自分以外のどの人 Y に対しても「人 X は人 Y より強い」という関係が成り立つ時、人 X を 最強のプログラマー と呼びます。(上記の制約下においてそのような人がちょうど 1 人存在することが証明できます)
あなたは M 個の強さに関する情報を知っています。i 個目の情報は「人 A_i は人 B_i より強い」という情報です。
あなたは情報を元に N 人の中から最強のプログラマーを特定することができますか?
最強のプログラマーを特定できる場合はその人の番号を出力してください。特定できない場合、つまり最強のプログラマーとしてあり得る人が複数人いる場合は -1 を出力してください。
制約
- 2 \leq N \leq 50
- 0 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq A_i, B_i \leq N
- A_i \neq B_i
- i \neq j ならば (A_i, B_i) \neq (A_j, B_j)
- 全ての情報が正しくなるように、全ての相異なる 2 人組にどちらが強いかを割り当てる方法が少なくとも 1 通り存在する
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
最強のプログラマーを特定できる場合はその人の番号を出力せよ。特定できない場合は -1 を出力せよ。
入力例 1
3 2 1 2 2 3
出力例 1
1
あなたは「人 1 は人 2 より強い」「人 2 は人 3 より強い」という情報が分かっています。
推移律から「人 1 は人 3 より強い」という情報もわかるので、人 1 は最強のプログラマーです。
入力例 2
3 2 1 3 2 3
出力例 2
-1
最強のプログラマーである可能性がある人は人 1 と人 2 です。最強のプログラマーを一意に特定できないので -1 を出力してください。
入力例 3
6 6 1 6 6 5 6 2 2 3 4 3 4 2
出力例 3
-1
Score : 300 points
Problem Statement
There are N competitive programmers numbered person 1, person 2, \ldots, and person N.
There is a relation called superiority between the programmers. For all pairs of distinct programmers (person X, person Y), exactly one of the following two relations holds: "person X is stronger than person Y" or "person Y is stronger than person X."
The superiority is transitive. In other words, for all triplets of distinct programmers (person X, person Y, person Z), it holds that:
- if person X is stronger than person Y and person Y is stronger than person Z, then person X is stronger than person Z.
A person X is said to be the strongest programmer if person X is stronger than person Y for all people Y other than person X. (Under the constraints above, we can prove that there is always exactly one such person.)
You have M pieces of information on their superiority. The i-th of them is that "person A_i is stronger than person B_i."
Can you determine the strongest programmer among the N based on the information?
If you can, print the person's number. Otherwise, that is, if there are multiple possible strongest programmers, print -1.
Constraints
- 2 \leq N \leq 50
- 0 \leq M \leq \frac{N(N-1)}{2}
- 1 \leq A_i, B_i \leq N
- A_i \neq B_i
- If i \neq j, then (A_i, B_i) \neq (A_j, B_j).
- There is at least one way to determine superiorities for all pairs of distinct programmers, that is consistent with the given information.
Input
The input is given from Standard Input in the following format:
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
Output
If you can uniquely determine the strongest programmer, print the person's number; otherwise, print -1.
Sample Input 1
3 2 1 2 2 3
Sample Output 1
1
You have two pieces of information: "person 1 is stronger than person 2" and "person 2 is stronger than person 3."
By the transitivity, you can also infer that "person 1 is stronger than person 3," so person 1 is the strongest programmer.
Sample Input 2
3 2 1 3 2 3
Sample Output 2
-1
Both person 1 and person 2 may be the strongest programmer. Since you cannot uniquely determine which is the strongest, you should print -1.
Sample Input 3
6 6 1 6 6 5 6 2 2 3 4 3 4 2
Sample Output 3
-1
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 人の巨人がいます。巨人にはそれぞれ 1, 2, \ldots, N の名前がついており、巨人 i が地面に立ったとき、肩の高さは A_i、頭の高さは B_i となります。
あなたは (1, 2, \ldots, N) を並べ替えて得られる数列 (P_1, P_2, \ldots, P_N) を選び、以下の規則に従って N 人の巨人を積み上げることができます。
-
まず地面に巨人 P_1 を立たせる。巨人 P_1 の肩は地面を基準として A_{P_1}、頭は地面を基準として B_{P_1} の高さとなる。
-
i = 1, 2, \ldots, N - 1 の順に巨人 P_i の肩の上に巨人 P_{i + 1} を立たせる。巨人 P_i の肩が地面を基準として高さ t のとき、巨人 P_{i + 1} の肩は地面を基準として t + A_{P_{i + 1}}、頭は地面を基準として t + B_{P_{i + 1}} の高さとなる。
一番上に立っている巨人、すなわち巨人 P_N の地面を基準とした頭の高さとして実現できる最大値を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq B_i \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
答えを出力せよ。
入力例 1
3 4 10 5 8 2 9
出力例 1
18
(P_1, P_2, P_3) = (2, 1, 3) とすると、地面を基準として巨人 2 は肩の高さが 5、頭の高さが 8、巨人 1 は肩の高さが 9、頭の高さが 15、巨人 3 は肩の高さが 11、頭の高さが 18 となります。
一番上に立っている巨人の頭の高さが地面を基準として 18 より大きくなることはないため 18 を出力します。
入力例 2
5 1 1 1 1 1 1 1 1 1 1
出力例 2
5
入力例 3
10 690830957 868532399 741145463 930111470 612846445 948344128 540375785 925723427 723092548 925021315 928915367 973970164 563314352 832796216 562681294 868338948 923012648 954764623 691107436 891127278
出力例 3
7362669937
Score: 300 points
Problem Statement
There are N giants, named 1 to N. When giant i stands on the ground, their shoulder height is A_i, and their head height is B_i.
You can choose a permutation (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) and stack the N giants according to the following rules:
-
First, place giant P_1 on the ground. The giant P_1's shoulder will be at a height of A_{P_1} from the ground, and their head will be at a height of B_{P_1} from the ground.
-
For i = 1, 2, \ldots, N - 1 in order, place giant P_{i + 1} on the shoulders of giant P_i. If giant P_i's shoulders are at a height of t from the ground, then giant P_{i + 1}'s shoulders will be at a height of t + A_{P_{i + 1}} from the ground, and their head will be at a height of t + B_{P_{i + 1}} from the ground.
Find the maximum possible height of the head of the topmost giant P_N from the ground.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq B_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print the answer.
Sample Input 1
3 4 10 5 8 2 9
Sample Output 1
18
If (P_1, P_2, P_3) = (2, 1, 3), then measuring from the ground, giant 2 has a shoulder height of 5 and a head height of 8, giant 1 has a shoulder height of 9 and a head height of 15, and giant 3 has a shoulder height of 11 and a head height of 18.
The head height of the topmost giant from the ground cannot be greater than 18, so print 18.
Sample Input 2
5 1 1 1 1 1 1 1 1 1 1
Sample Output 2
5
Sample Input 3
10 690830957 868532399 741145463 930111470 612846445 948344128 540375785 925723427 723092548 925021315 928915367 973970164 563314352 832796216 562681294 868338948 923012648 954764623 691107436 891127278
Sample Output 3
7362669937
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
ポエムオンラインジャッジ (Poem Online Judge, 以下 POJ と表記) は提出された文字列に得点をつけるオンラインジャッジです。
POJ に N 回の提出がありました。早い方から i 番目の提出では文字列 S_i が提出されて、得点は T_i でした。(同じ文字列が複数回提出される場合もあります)
ただし、POJ では 同じ文字列を提出しても得点が等しいとは限らない のに注意してください。
N 回の提出のうち、その提出よりも早い提出であって文字列が一致するものが存在しないような提出を オリジナル であると呼びます。
また、オリジナルな提出の中で最も得点が高いものを 最優秀賞 と呼びます。ただし、そのような提出が複数ある場合は、最も提出が早いものを最優秀賞とします。
最優秀賞は早い方から何番目の提出ですか?
制約
- 1 \leq N \leq 10^5
- S_i は英小文字からなる文字列
- S_i の長さは 1 以上 10 以下
- 0 \leq T_i \leq 10^9
- N, T_i は整数
入力
入力は以下の形式で標準入力から与えられる。
N S_1 T_1 S_2 T_2 \vdots S_N T_N
出力
答えを出力せよ。
入力例 1
3 aaa 10 bbb 20 aaa 30
出力例 1
2
以下では早い方から i 番目の提出を提出 i と呼びます。
オリジナルな提出は提出 1 と 提出 2 です。提出 3 は提出 1 と文字列が一致しているためオリジナルではありません。
オリジナルな提出のうち最も得点が高い提出は提出 2 です。よってこれが最優秀賞になります。
入力例 2
5 aaa 9 bbb 10 ccc 10 ddd 10 bbb 11
出力例 2
2
オリジナルな提出は提出 1・提出 2・提出 3・提出 4 です。
その中で最も得点が高い提出は提出 2・提出 3・提出 4 です。この場合はこの中でもっとも提出の早い提出 2 を最優秀賞とします。
このように、オリジナルな提出の中で最も得点が高い提出が複数ある場合は、さらにその中で最も提出が早いものを最優秀賞とするのに注意してください。
入力例 3
10 bb 3 ba 1 aa 4 bb 1 ba 5 aa 9 aa 2 ab 6 bb 5 ab 3
出力例 3
8
Score : 300 points
Problem Statement
Poem Online Judge (POJ) is an online judge that gives scores to submitted strings.
There were N submissions to POJ. In the i-th earliest submission, string S_i was submitted, and a score of T_i was given. (The same string may have been submitted multiple times.)
Note that POJ may not necessarily give the same score to submissions with the same string.
A submission is said to be an original submission if the string in the submission is never submitted in any earlier submission.
A submission is said to be the best submission if it is an original submission with the highest score. If there are multiple such submissions, only the earliest one is considered the best submission.
Find the index of the best submission.
Constraints
- 1 \leq N \leq 10^5
- S_i is a string consisting of lowercase English characters.
- S_i has a length between 1 and 10, inclusive.
- 0 \leq T_i \leq 10^9
- N and T_i are integers.
Input
Input is given from Standard Input in the following format:
N S_1 T_1 S_2 T_2 \vdots S_N T_N
Output
Print the answer.
Sample Input 1
3 aaa 10 bbb 20 aaa 30
Sample Output 1
2
We will refer to the i-th earliest submission as Submission i.
Original submissions are Submissions 1 and 2. Submission 3 is not original because it has the same string as that in Submission 1.
Among the original submissions, Submission 2 has the highest score. Therefore, this is the best submission.
Sample Input 2
5 aaa 9 bbb 10 ccc 10 ddd 10 bbb 11
Sample Output 2
2
Original submissions are Submissions 1, 2, 3, and 4.
Among them, Submissions 2, 3, and 4 have the highest scores. In this case, the earliest submission among them, Submission 2, is the best.
As in this sample, beware that if multiple original submissions have the highest scores, only the one with the earliest among them is considered the best submission.
Sample Input 3
10 bb 3 ba 1 aa 4 bb 1 ba 5 aa 9 aa 2 ab 6 bb 5 ab 3
Sample Output 3
8
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
非負整数 x に対し定義される関数 f(x) は以下の条件を満たします。
- f(0) = 1
- 任意の正整数 k に対し f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor)
ここで、\lfloor A \rfloor は A の小数点以下を切り捨てた値を指します。
このとき、 f(N) を求めてください。
制約
- N は 0 \le N \le 10^{18} を満たす整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
2
出力例 1
3
f(2) = f(\lfloor \frac{2}{2}\rfloor) + f(\lfloor \frac{2}{3}\rfloor) = f(1) + f(0) =(f(\lfloor \frac{1}{2}\rfloor) + f(\lfloor \frac{1}{3}\rfloor)) + f(0) =(f(0)+f(0)) + f(0)= 3 です。
入力例 2
0
出力例 2
1
入力例 3
100
出力例 3
55
Score : 400 points
Problem Statement
A function f(x) defined for non-negative integers x satisfies the following conditions.
- f(0) = 1.
- f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor) for any positive integer k.
Here, \lfloor A \rfloor denotes the value of A rounded down to an integer.
Find f(N).
Constraints
- N is an integer satisfying 0 \le N \le 10^{18}.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
2
Sample Output 1
3
We have f(2) = f(\lfloor \frac{2}{2}\rfloor) + f(\lfloor \frac{2}{3}\rfloor) = f(1) + f(0) =(f(\lfloor \frac{1}{2}\rfloor) + f(\lfloor \frac{1}{3}\rfloor)) + f(0) =(f(0)+f(0)) + f(0)= 3.
Sample Input 2
0
Sample Output 2
1
Sample Input 3
100
Sample Output 3
55