C - Minimize Ordering

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 つが考えられます。

  • aba
  • aab
  • baa

この中で辞書順で最小のものは、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:

  • aba
  • aab
  • baa

The lexicographically smallest among them is aab.


Sample Input 2

zzzz

Sample Output 2

zzzz
D - Subscribers

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
E - Extra Character

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
F - Standings

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
G - Flip Cards

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