Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
文字列 S が与えられます。S の各文字を並び替えて得られる文字列 S' のうち、辞書順で最小のものを出力してください。
なお、相異なる 2 つの文字列 s = s_1 s_2 \ldots s_n と t = t_1 t_2 \ldots t_m について、それらが以下の条件のいずれかを満たすとき、辞書順で s \lt t であるとします。
- ある整数 i\ (1 \leq i \leq \min(n,m)) が存在し、s_i \lt t_i かつすべての整数 j\ (1 \leq j \lt i) について s_j=t_j
- すべての整数 i\ (1 \leq i \leq \min(n,m)) について s_i = t_i かつ、n \lt m
制約
- S は英小文字のみからなる長さ 1 以上 2 \times 10^5 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S の各文字を並び替えて得られる文字列 S' のうち、辞書順で最小のものを出力せよ。
入力例 1
aba
出力例 1
aab
S= aba を並び替えて得られる文字列は以下の 3 つが考えられます。
abaaabbaa
この中で辞書順で最小のものは、aab です。
入力例 2
zzzz
出力例 2
zzzz
Score : 200 points
Problem Statement
You are given a string S. Find the lexicographically smallest string S' obtained by permuting the characters of S.
Here, for different two strings s = s_1 s_2 \ldots s_n and t = t_1 t_2 \ldots t_m, s \lt t holds lexicographically when one of the conditions below is satisfied.
- There is an integer i\ (1 \leq i \leq \min(n,m)) such that s_i \lt t_i and s_j=t_j for all integers j\ (1 \leq j \lt i).
- s_i = t_i for all integers i\ (1 \leq i \leq \min(n,m)), and n \lt m.
Constraints
- S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
S
Output
Print the lexicographically smallest string S' obtained by permuting the characters in S.
Sample Input 1
aba
Sample Output 1
aab
Three strings can be obtained by permuting aba:
abaaabbaa
The lexicographically smallest among them is aab.
Sample Input 2
zzzz
Sample Output 2
zzzz
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
整数 N が与えられます。
以下の指示に従って N の近似値を出力してください。
- N が 10^3-1 以下ならば、N をそのまま出力する。
- N が 10^3 以上 10^4-1 以下ならば、N の一の位を切り捨てて出力する。
- N が 10^4 以上 10^5-1 以下ならば、N の十の位以下を切り捨てて出力する。
- N が 10^5 以上 10^6-1 以下ならば、N の百の位以下を切り捨てて出力する。
- N が 10^6 以上 10^7-1 以下ならば、N の千の位以下を切り捨てて出力する。
- N が 10^7 以上 10^8-1 以下ならば、N の一万の位以下を切り捨てて出力する。
- N が 10^8 以上 10^9-1 以下ならば、N の十万の位以下を切り捨てて出力する。
制約
- N は 0 以上 10^9-1 以下の整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
20230603
出力例 1
20200000
20230603 は 10^7 以上 10^8-1 以下です。
したがって、一万以下の位を切り捨てて 20200000 を出力します。
入力例 2
0
出力例 2
0
入力例 3
304
出力例 3
304
入力例 4
500600
出力例 4
500000
Score : 200 points
Problem Statement
You are given an integer N.
Print an approximation of N according to the following instructions.
- If N is less than or equal to 10^3-1, print N as it is.
- If N is between 10^3 and 10^4-1, inclusive, truncate the ones digit of N and print the result.
- If N is between 10^4 and 10^5-1, inclusive, truncate the tens digit and all digits below it of N and print the result.
- If N is between 10^5 and 10^6-1, inclusive, truncate the hundreds digit and all digits below it of N and print the result.
- If N is between 10^6 and 10^7-1, inclusive, truncate the thousands digit and all digits below it of N and print the result.
- If N is between 10^7 and 10^8-1, inclusive, truncate the ten-thousands digit and all digits below it of N and print the result.
- If N is between 10^8 and 10^9-1, inclusive, truncate the hundred-thousands digit and all digits below it of N and print the result.
Constraints
- N is an integer between 0 and 10^9-1, inclusive.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
20230603
Sample Output 1
20200000
20230603 is between 10^7 and 10^8-1 (inclusive).
Therefore, truncate the ten-thousands digit and all digits below it, and print 20200000.
Sample Input 2
0
Sample Output 2
0
Sample Input 3
304
Sample Output 3
304
Sample Input 4
500600
Sample Output 4
500000
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
文字列 S,T が与えられます。S は英小文字からなり、T は S に英小文字を 1 つ挿入して作られたことがわかっています。
挿入された文字は T の先頭から何番目の文字であるか求めてください。
複数の候補が考えられる場合はいずれか 1 つを求めてください。
制約
- 1 \leq |S| \leq 5\times 10^5
- S は英小文字からなる
- T は S に英小文字を 1 つ挿入して作られた文字列である
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
答えを出力せよ。なお、答えが複数考えられる場合はどれを出力しても正解となる。
入力例 1
atcoder atcorder
出力例 1
5
T の先頭から 5 番目の文字 r が挿入された文字です。
入力例 2
million milllion
出力例 2
5
T の先頭から 3,4,5 番目の文字のいずれかが挿入された文字です。
よって、3,4,5 のいずれかを出力すると正解となります。
入力例 3
vvwvw vvvwvw
出力例 3
3
Score : 300 points
Problem Statement
You are given strings S and T. S consists of lowercase English letters, and T is obtained by inserting a lowercase English letter into S.
Find the position of the inserted character in T.
If there are multiple candidates, find any of them.
Constraints
- 1 \leq |S| \leq 5\times 10^5
- S consists of lowercase English letters.
- T is obtained by inserting a lowercase English letter into S.
Input
The input is given from Standard Input in the following format:
S T
Output
Print an integer i, representing that the inserted character is the i-th character from the beginning of T. If there are multiple possible answers, printing any of them is accepted.
Sample Input 1
atcoder atcorder
Sample Output 1
5
The 5-th character from the beginning of T, r, is inserted.
Sample Input 2
million milllion
Sample Output 2
5
One of the 3-rd, 4-th, and 5-th characters from the beginning of T is inserted. Thus, printing any one of 3, 4, and 5 is accepted.
Sample Input 3
vvwvw vvvwvw
Sample Output 3
3
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
1 から N の番号が付いた N 人がコイントスを何回かしました。人 i は A_i 回表を出し、B_i 回裏を出したこと分かっています。
人 i のコイントスの 成功率 は \displaystyle\frac{A_i}{A_i+B_i} で定義されます。人 1,\ldots,N の番号を、成功率の高い順に並び替えてください。成功率が同じ人が複数いる場合、その中では人の番号が小さい順になるように並び替えてください。
制約
- 2\leq N \leq 2\times 10^5
- 0\leq A_i, B_i\leq 10^9
- A_i+B_i \geq 1
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 \vdots A_N B_N
出力
人 1,\ldots,N の番号を成功率の高い順に空白区切りで出力せよ。成功率が同じ人の番号は昇順に並び替えて出力せよ。
入力例 1
3 1 3 3 1 2 2
出力例 1
2 3 1
人 1 の成功率は 0.25、人 2 の成功率は 0.75、人 3 の成功率は 0.5 です。
成功率の高い順に並び替えると出力例の順番になります。
入力例 2
2 1 3 2 6
出力例 2
1 2
人 1,2 は成功率が同じなので、番号の昇順に出力することに注意してください。
入力例 3
4 999999999 1000000000 333333333 999999999 1000000000 999999997 999999998 1000000000
出力例 3
3 1 4 2
Score : 300 points
Problem Statement
N people numbered 1 through N tossed a coin several times. We know that person i's tosses resulted in A_i heads and B_i tails.
Person i's success rate of the tosses is defined by \displaystyle\frac{A_i}{A_i+B_i}. Sort people 1,\ldots,N in descending order of their success rates, with ties broken in ascending order of their assigned numbers.
Constraints
- 2\leq N \leq 2\times 10^5
- 0\leq A_i, B_i\leq 10^9
- A_i+B_i \geq 1
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 B_1 \vdots A_N B_N
Output
Print the numbers of people 1,\ldots,N in descending order of their success rates, with ties broken in ascending order of their assigned numbers.
Sample Input 1
3 1 3 3 1 2 2
Sample Output 1
2 3 1
Person 1's success rate is 0.25, person 2's is 0.75, and person 3's is 0.5.
Sort them in descending order of their success rates to obtain the order in Sample Output.
Sample Input 2
2 1 3 2 6
Sample Output 2
1 2
Note that person 1 and 2 should be printed in ascending order of their numbers, as they have the same success rates.
Sample Input 3
4 999999999 1000000000 333333333 999999999 1000000000 999999997 999999998 1000000000
Sample Output 3
3 1 4 2
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
1 から N までの番号がついた N 枚のカードが一列に並んでいて、各 i\ (1\leq i < N) に対してカード i とカード i+1 が隣り合っています。 カード i の表には A_i が、裏には B_i が書かれており、最初全てのカードは表を向いています。
今から、N 枚のカードのうち好きな枚数 (0 枚でも良い) を選んで裏返すことを考えます。 裏返すカードの選び方は 2^N 通りありますが、そのうち以下の条件を満たすものの数を 998244353 で割った余りを求めてください。
- 選んだカードを裏返した後、どの隣り合う 2 枚のカードについても、向いている面に書かれた数が相異なる。
制約
- 1\leq N \leq 2\times 10^5
- 1\leq A_i,B_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
答えを整数として出力せよ。
入力例 1
3 1 2 4 2 3 4
出力例 1
4
裏返すカードの番号の集合を S とします。
例えば S=\{2,3\} を選ぶと、向いている面に書かれた数はカード 1 から順に 1,2,4 となるため条件を満たします。
一方 S=\{3\} を選ぶと、向いている面に書かれた数はカード 1 から順に 1,4,4 となり、カード 2 とカード 3 の数が一致するため条件を満たしません。
条件を満たす S は \{\},\{1\},\{2\},\{2,3\} の 4 通りです。
入力例 2
4 1 5 2 6 3 7 4 8
出力例 2
16
入力例 3
8 877914575 602436426 861648772 623690081 476190629 262703497 971407775 628894325 822804784 450968417 161735902 822804784 161735902 822804784 822804784 161735902
出力例 3
48
Score : 400 points
Problem Statement
N cards, numbered 1 through N, are arranged in a line. For each i\ (1\leq i < N), card i and card (i+1) are adjacent to each other. Card i has A_i written on its front, and B_i written on its back. Initially, all cards are face up.
Consider flipping zero or more cards chosen from the N cards. Among the 2^N ways to choose the cards to flip, find the number, modulo 998244353, of such ways that:
- when the chosen cards are flipped, for every pair of adjacent cards, the integers written on their face-up sides are different.
Constraints
- 1\leq N \leq 2\times 10^5
- 1\leq A_i,B_i \leq 10^9
- All values in the input 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 as an integer.
Sample Input 1
3 1 2 4 2 3 4
Sample Output 1
4
Let S be the set of card numbers to flip.
For example, when S=\{2,3\} is chosen, the integers written on their visible sides are 1,2, and 4, from card 1 to card 3, so it satisfies the condition.
On the other hand, when S=\{3\} is chosen, the integers written on their visible sides are 1,4, and 4, from card 1 to card 3, where the integers on card 2 and card 3 are the same, violating the condition.
Four S satisfy the conditions: \{\},\{1\},\{2\}, and \{2,3\}.
Sample Input 2
4 1 5 2 6 3 7 4 8
Sample Output 2
16
Sample Input 3
8 877914575 602436426 861648772 623690081 476190629 262703497 971407775 628894325 822804784 450968417 161735902 822804784 161735902 822804784 822804784 161735902
Sample Output 3
48