AtCoder Daily Training EASY 2025/11/27 20:30start

A - Job Interview

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

高橋君はある会社の採用面接を受けました。

面接官の人数 N と、各面接官の高橋君への評価を表す長さ N の文字列 S が与えられます。
i=1,2,\ldots,N に対し S の i 文字目が i 番目の面接官の評価に対応し、o は「良」、- は「可」、x は「不可」を表します。

高橋君は以下の 2 つの条件を両方満たすならば合格、そうでなければ不合格です。

「良」と評価した面接官が少なくとも 1 人いる
「不可」と評価した面接官がいない

高橋君が合格かどうかを判定してください。

制約

1 \leq N \leq 100
S は o, -, x のみからなる長さが N の文字列

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

高橋君が合格ならば Yes と、そうでなければ No と出力せよ。

入力例 1

4
oo--

出力例 1

Yes

1, 2 番目の面接官が「良」と評価していて、さらに「不可」と評価した面接官がいないため合格です。

入力例 2

3
---

出力例 2

No

「良」と評価した面接官が 1 人もいないため不合格です。

入力例 3

1
o

出力例 3

Yes

入力例 4

100
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooox

出力例 4

No

100 番目の面接官が「不可」と評価しているため不合格です。

Score : 100 points

Problem Statement

Takahashi had a job interview.

You are given the number of interviewers, N, and a string S of length N representing the interviewers' evaluations of him.
For each i=1,2,\ldots,N, the i-th character of S corresponds to the i-th interviewer's evaluation; o means Good, - means Fair, and x means Poor.

Takahashi will pass if both of the following conditions are satisfied, and fail otherwise.

At least one interviewer's evaluation is Good.
No interviewer's evaluation is Poor.

Determine whether Takahashi passes.

Constraints

1 \leq N \leq 100
S is a string of length N consisting of o, -, and x.

Input

The input is given from Standard Input in the following format:

N
S

Output

If Takahashi passes, print Yes; otherwise, print No.

Sample Input 1

4
oo--

Sample Output 1

Yes

The first and second interviewers' evaluations are Good, and no interviewer's evaluation is Poor, so he passes.

Sample Input 2

3
---

Sample Output 2

No

No interviewer's evaluation is Good, so he fails.

Sample Input 3

1
o

Sample Output 3

Yes

Sample Input 4

100
ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooox

Sample Output 4

No

The 100-th interviewer's evaluation is Poor, so he fails.

B - CBC

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

英大文字と英小文字からなる文字列 S が与えられます。S の英大文字のみを元の順序で連結して得られる文字列を出力してください。

制約

S は英大文字と英小文字からなる文字列である
S の長さは 1 以上 100 以下である

入力

入力は以下の形式で標準入力から与えられる。

出力

S の英大文字のみを元の順序で連結して得られる文字列を出力せよ。

入力例 1

AtCoderBeginnerContest

出力例 1

ACBC

S の英大文字のみを元の順序で連結して得られる文字列は ACBC です。よって、ACBC を出力します。

入力例 2

PaymentRequired

出力例 2

PR

入力例 3

program

出力例 3

S に英大文字が含まれないことがあることに注意してください。

Score : 100 points

Problem Statement

You are given a string S consisting of uppercase and lowercase English letters. Print the string obtained by concatenating only the uppercase letters of S in their original order.

Constraints

S is a string of uppercase and lowercase English letters.
The length of S is between 1 and 100, inclusive.

Input

The input is given from Standard Input in the following format:

Output

Print the string obtained by concatenating only the uppercase letters of S in their original order.

Sample Input 1

AtCoderBeginnerContest

Sample Output 1

ACBC

The string obtained by concatenating only the uppercase letters of S in their original order is ACBC. Hence, print ACBC.

Sample Input 2

PaymentRequired

Sample Output 2

PR

Sample Input 3

program

Sample Output 3

Note that S may contain no uppercase letters.

C - Get Min

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

中に何も入っていない袋があります。

Q 個のクエリが与えられるので、これらのクエリを順に処理したときのタイプ 2 の各クエリの答えを出力してください。

各クエリは、以下のいずれかの形式です。

タイプ 1 : 1 x の形式で入力として与えられる。整数 x が書かれたボールを 1 つ袋の中に入れる。
タイプ 2 : 2 の形式で入力として与えられる。袋に入っているボールのうち書かれている整数が最小のものを 1 つ取り出し、その整数を答えとする。ただし、袋の中にボールが入っていないときにはこのクエリは与えられない。

制約

2 \leq Q \leq 100
タイプ 1 のクエリにおいて、1 \leq x \leq 100
タイプ 2 のクエリが与えられたとき、袋は空ではない
タイプ 2 のクエリが 1 つ以上与えられる
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

Q 
\text{query}_1
\text{query}_2
\ldots
\text{query}_Q

ただし、\text{query}_i は i 番目のクエリであり、以下のいずれかの形式で与えられる。

1 x

出力

タイプ 2 のクエリの個数を q として、q 行出力せよ。

i 行目には、i 番目のタイプ 2 のクエリの答えを出力せよ。

入力例 1

出力例 1

6
1

はじめ、袋の中にボールは入っていません。

1 番目のクエリでは、袋の中に 6 が書かれたボールを入れます。

2 番目のクエリでは、袋の中に 7 が書かれたボールを入れます。

3 番目のクエリでは、袋の中には 6 が書かれたボールと 7 が書かれたボールが入っているため、6 が書かれたボールを取り出します。このクエリの答えは 6 となります。

4 番目のクエリでは、袋の中に 1 が書かれたボールを入れます。

5 番目のクエリでは、袋の中には 1 が書かれたボールと 7 が書かれたボールが入っているため、1 が書かれたボールを取り出します。このクエリの答えは 1 となります。

入力例 2

出力例 2

1
1
2

同じ整数が書かれたボールを複数個袋の中に入れることもあります。

Score : 200 points

Problem Statement

There is an empty bag.

You are given Q queries. Process these queries in order and output the answer to each type-2 query.

Each query is of one of the following types.

Type 1: Given as input in the format 1 x. Put a ball with the integer x written on it into the bag.
Type 2: Given as input in the format 2. Pick out one ball with the minimum integer written on it from the balls in the bag, and report that integer as the answer. This query is not given when the bag contains no balls.

Constraints

2 \leq Q \leq 100
In a type-1 query, 1 \leq x \leq 100.
When a type-2 query is given, the bag is not empty.
At least one type-2 query is given.
All input values are integers.

Input

The input is given from Standard Input in the following format:

Q 
\text{query}_1
\text{query}_2
\ldots
\text{query}_Q

Here, \text{query}_i is the i-th query and is given in one of the following formats:

1 x

Output

Let q be the number of type-2 queries, and output q lines.

The i-th line should contain the answer to the i-th type-2 query.

Sample Input 1

Sample Output 1

6
1

Initially, the bag contains no balls.

The 1st query puts a ball with 6 written on it into the bag.

The 2nd query puts a ball with 7 written on it into the bag.

In the 3rd query, the bag contains a ball with 6 written on it and a ball with 7 written on it, so you pick out the ball with 6 written on it. The answer to this query is 6.

The 4th query puts a ball with 1 written on it into the bag.

In the 5th query, the bag contains a ball with 1 written on it and a ball with 7 written on it, so you pick out the ball with 1 written on it. The answer to this query is 1.

Sample Input 2

Sample Output 2

1
1
2

The bag may contain multiple balls with the same integer.

D - Base K

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

整数 A,B が K 進法表記で与えられます。
A \times B を 10 進法表記で出力してください。

注記

K 進法表記については、Wikipedia「位取り記数法」を参照してください。

制約

2 \leq K \leq 10
1 \leq A,B \leq 10^5
A,B は K 進法表記で与えられる

入力

入力は以下の形式で標準入力から与えられる。

K
A B

出力

答えを出力せよ。

入力例 1

2
1011 10100

出力例 1

2 進法表記の 1011 を、10 進法表記すると 11 です。
2 進法表記の 10100 を、 10 進法表記すると 20 です。
11 \times 20 = 220 なので 220 を出力します。

入力例 2

7
123 456

出力例 2

7 進法表記の 123 を、10 進法表記すると 66 です。
7 進法表記の 456 を、 10 進法表記すると 237 です。
66 \times 237 = 15642 なので 15642 を出力します。

Score : 200 points

Problem Statement

You are given integers A and B, in base K.
Print A \times B in decimal.

Notes

For base-K representation, see Wikipedia's article on Positional notation.

Constraints

2 \leq K \leq 10
1 \leq A,B \leq 10^5
A and B are in base-K representation.

Input

Input is given from Standard Input in the following format:

K
A B

Output

Print the answer.

Sample Input 1

2
1011 10100

Sample Output 1

1011 in base 2 corresponds to 11 in base 10.
10100 in base 2 corresponds to 20 in base 10.
We have 11 \times 20 = 220, so print 220.

Sample Input 2

7
123 456

Sample Output 2

123 in base 7 corresponds to 66 in base 10.
456 in base 7 corresponds to 237 in base 10.
We have 66 \times 237 = 15642, so print 15642.

E - Alternated

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 350 点

問題文

長さ 2N の文字列 S が与えられます。 S は A, B を N 個ずつ含みます。

S に対して隣り合う文字を入れ替える操作を好きな回数( 0 回でもよい)行って、同じ文字が隣り合う箇所がない状態にするために必要な操作回数の最小値を求めてください。

制約

1\leq N \leq 5\times 10^5
N は整数
S は長さ 2N の文字列であり、N 個の A と N 個の B からなる

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

答えを出力せよ。

入力例 1

3
AABBBA

出力例 1

次のように操作することで 2 回の操作で同じ文字が隣り合う箇所がない状態にすることができます。

2 文字目と 3 文字目を入れ替える。S は ABABBA になる。
5 文字目と 6 文字目を入れ替える。S は ABABAB になる。

入力例 2

3
AAABBB

出力例 2

入れ替えることができるのは隣り合う文字に限ることに注意してください。

入力例 3

17
AAABABABBBABABBABABABABBAAABABABBA

出力例 3

Score : 350 points

Problem Statement

You are given a string S of length 2N. S contains exactly N occurrences of A and N occurrences of B.

Find the minimum number of operations (possibly zero) needed to make S have no adjacent identical characters, where an operation consists of swapping two adjacent characters in S.

Constraints

1\leq N \leq 5\times 10^5
N is an integer.
S is a string of length 2N consisting of N occurrences of A and N occurrences of B.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the answer.

Sample Input 1

3
AABBBA

Sample Output 1

By performing operations as follows, you can achieve a state with no adjacent identical characters in two operations:

Swap the 2nd and 3rd characters. S becomes ABABBA.
Swap the 5th and 6th characters. S becomes ABABAB.

Sample Input 2

3
AAABBB

Sample Output 2

Note that you can only swap adjacent characters.

Sample Input 3

17
AAABABABBBABABBABABABABBAAABABABBA