実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
英小文字からなる長さが奇数の文字列 S が与えられます。
S の中央の文字を出力してください。
中央の文字とは
ある長さが奇数の文字列 T について、 T の長さを |T| として、T の前から \frac{|T|+1}{2} 番目の文字を中央の文字とします。制約
- S は英小文字からなる長さが奇数の文字列
- S の長さは 1 以上 99 以下
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
atcoder
出力例 1
o
atcoder の中央の文字は o です。
入力例 2
a
出力例 2
a
Score : 100 points
Problem Statement
You are given an odd-length string S consisting of lowercase English letters.
Print the central character of S.
What is the central character?
For an odd-length string T, its central character is the \frac{|T|+1}{2}-th character from the beginning, where |T| is the length of T.Constraints
- S is an odd-length string consisting of lowercase English letters.
- The length of S is between 1 and 99 (inclusive).
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
atcoder
Sample Output 1
o
The central character of atcoder is o.
Sample Input 2
a
Sample Output 2
a
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
N が与えられます。2^N を出力してください。
制約
- 0 \leq N \leq 30
- N は整数である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
3
出力例 1
8
2^3=8 です。
入力例 2
30
出力例 2
1073741824
Score : 100 points
Problem Statement
Given N, print 2^N.
Constraints
- 0 \leq N \leq 30
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
3
Sample Output 1
8
We have 2^3=8.
Sample Input 2
30
Sample Output 2
1073741824
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君はAtCoderレストランの前の待ち行列の管理をしたいです。はじめ、待ち行列に並んでいる人はいません。 また、待ち行列に並ぶ人は必ず注文する料理のメニュー番号が書かれた食券を持って並びます。
Q 個のクエリが与えられるので順に処理してください。クエリは 2 種類あり、以下のいずれかの形式で与えられます。
1 X: 待ち行列の末尾に 1 人並ぶ。このとき並ぶ人はメニュー番号が X の食券を持って並ぶ。2: 待ち行列の先頭にいる人をレストランに案内する。このとき案内される人が持っている食券のメニュー番号を出力する。
制約
- 1 \leq Q \leq 100
- 1 \leq X \leq 100
- 2 つ目の形式のクエリについて、案内する前に待ち行列に並んでいる人がいる
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
各クエリは以下の 2 種類のいずれかの形式で与えられる。
1 X
2
出力
問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。
入力例 1
6 1 3 1 1 1 15 2 1 3 2
出力例 1
3 1
はじめ、待ち行列に並んでいる人はいません。
- 1 つ目のクエリについて、メニュー番号が 3 の食券を持った人が待ち行列の末尾に並びます。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 3 です。
- 2 つ目のクエリについて、メニュー番号が 1 の食券を持った人が待ち行列の末尾に並びます。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 3,1 です。
- 3 つ目のクエリについて、メニュー番号が 15 の食券を持った人が待ち行列の末尾に並びます。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 3,1,15 です。
- 4 つ目のクエリについて、待ち行列の先頭にいる人をレストランに案内します。案内する人はメニュー番号が 3 の食券を持っているので 3 を出力します。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 1,15 です。
- 5 つ目のクエリについて、メニュー番号が 3 の食券を持った人が待ち行列の末尾に並びます。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 1,15,3 です。
- 6 つ目のクエリについて、待ち行列の先頭にいる人をレストランに案内します。案内する人はメニュー番号が 1 の食券を持っているので 1 を出力します。この時、待ち行列に並んでいる人が持っている食券のメニュー番号は先頭の人から順に 15,3 です。
入力例 2
7 1 3 1 1 1 4 1 1 1 5 1 9 1 2
出力例 2
2 つ目の形式のクエリがないことがあることに注意してください。
Score : 200 points
Problem Statement
Takahashi wants to manage the waiting line in front of the AtCoder Restaurant. Initially, the waiting line is empty. Each person who joins the line holds a meal ticket with the menu number of the dish they will order.
Process Q queries in order. There are two types of queries, given in the following formats:
1 X: One person joins the end of the waiting line holding a ticket with menu number X.2: Takahashi guides the person at the front of the waiting line into the restaurant. Print the menu number on that person’s ticket.
Constraints
- 1 \leq Q \leq 100
- 1 \leq X \leq 100
- For each query of the second type, there is at least one person in the line before guiding.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query has one of the following two formats:
1 X
2
Output
For each query, print the answer as specified in the problem statement, each on its own line.
Sample Input 1
6 1 3 1 1 1 15 2 1 3 2
Sample Output 1
3 1
Initially, the waiting line is empty.
- For the first query, a person holding a ticket with menu number 3 joins the end of the line. The sequence of menu numbers held by people in line from front to back is 3.
- For the second query, a person holding a ticket with menu number 1 joins the end of the line. The sequence becomes 3,1.
- For the third query, a person holding a ticket with menu number 15 joins the end of the line. The sequence becomes 3,1,15.
- For the fourth query, guide the person at the front into the restaurant. That person holds menu number 3, so print 3. The sequence becomes 1,15.
- For the fifth query, a person holding a ticket with menu number 3 joins the end of the line. The sequence becomes 1,15,3.
- For the sixth query, guide the person at the front into the restaurant. That person holds menu number 1, so print 1. The sequence becomes 15,3.
Sample Input 2
7 1 3 1 1 1 4 1 1 1 5 1 9 1 2
Sample Output 2
Note that there may be no queries of the second type.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
N 人の人があるコンテストに参加し、i 位の人のハンドルネームは S_i でした。
上位 K 人のハンドルネームを辞書順に出力してください。
辞書順とは?
辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、相異なる文字列 S と文字列 T の大小を判定するアルゴリズムを以下に説明します。
以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。
- S と T のうち長さが短い方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
- S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j がアルファベット順で T_j より小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
- S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。
制約
- 1 \leq K \leq N \leq 100
- K, N は整数
- S_i は英小文字からなる長さ 10 以下の文字列
- i \neq j ならば S_i \neq S_j
入力
入力は以下の形式で標準入力から与えられる。
N K S_1 S_2 \vdots S_N
出力
答えを改行区切りで出力せよ。
入力例 1
5 3 abc aaaaa xyz a def
出力例 1
aaaaa abc xyz
このコンテストには 5 人が参加し、1 位の人のハンドルネームは abc 、2 位の人のハンドルネームは aaaaa 、3 位の人のハンドルネームは xyz 、4 位の人のハンドルネームは a 、5 位の人のハンドルネームは def でした。
上位 3 人のハンドルネームは abc、aaaaa、xyz であるため、これを辞書順に並べ替えて aaaaa 、abc 、xyz の順に出力します。
入力例 2
4 4 z zyx zzz rbg
出力例 2
rbg z zyx zzz
入力例 3
3 1 abc arc agc
出力例 3
abc
Score : 200 points
Problem Statement
There were N participants in a contest. The participant ranked i-th had the nickname S_i.
Print the nicknames of the top K participants in lexicographical order.
What is lexicographical order?
Simply put, the lexicographical order is the order of words in a dictionary. As a formal description, below is an algorithm to order distinct strings S and T.
Let S_i denote the i-th character of a string S. We write S \lt T if S is lexicographically smaller than T, and S \gt T if S is larger.
- Let L be the length of the shorter of S and T. For i=1,2,\dots,L, check whether S_i equals T_i.
- If there is an i such that S_i \neq T_i, let j be the smallest such i. Compare S_j and T_j. If S_j is alphabetically smaller than T_j, we get S \lt T; if S_j is larger, we get S \gt T.
- If there is no i such that S_i \neq T_i, compare the lengths of S and T. If S is shorter than T, we get S \lt T; if S is longer, we get S \gt T.
Constraints
- 1 \leq K \leq N \leq 100
- K and N are integers.
- S_i is a string of length 10 consisting of lowercase English letters.
- S_i \neq S_j if i \neq j.
Input
The input is given from Standard Input in the following format:
N K S_1 S_2 \vdots S_N
Output
Print the nicknames, separated by newlines.
Sample Input 1
5 3 abc aaaaa xyz a def
Sample Output 1
aaaaa abc xyz
This contest had five participants. The participants ranked first, second, third, fourth, and fifth had the nicknames abc, aaaaa, xyz, a, and def, respectively.
The nicknames of the top three participants were abc, aaaaa, xyz, so print these in lexicographical order: aaaaa, abc, xyz.
Sample Input 2
4 4 z zyx zzz rbg
Sample Output 2
rbg z zyx zzz
Sample Input 3
3 1 abc arc agc
Sample Output 3
abc
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
英小文字のみからなる長さ N の文字列 S が与えられます。
S の文字を並び替えて得られる文字列(S 自身を含む)であって、長さ K の回文を部分文字列として 含まない ものの個数を求めてください。
ただし、長さ N の文字列 T が「長さ K の回文を部分文字列として含む」とは、
ある (N-K) 以下の非負整数 i が存在して、1 以上 K 以下の任意の整数 j について T_{i+j}=T_{i+K+1-j} が成り立つことをいいます。
ここで、T_k は文字列 T の k 文字目を表すものとします。
制約
- 2\leq K \leq N \leq 10
- N,K は整数
- S は英小文字のみからなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N K S
出力
S の文字を並び替えて得られる文字列であって、長さ K の回文を部分文字列として含まないものの個数を出力せよ。
入力例 1
3 2 aab
出力例 1
1
aab を並び替えて得られる文字列は aab, aba, baa の 3 つであり、このうち aab および baa は長さ 2 の回文 aa を部分文字列として含んでいます。
よって、条件をみたす文字列は aba のみであり、1 を出力します。
入力例 2
5 3 zzyyx
出力例 2
16
zzyyx を並べて得られる文字列は 30 個ありますが、そのうち長さ 3 の回文を含まないようなものは 16 個です。よって、16 を出力します。
入力例 3
10 5 abcwxyzyxw
出力例 3
440640
Score : 300 points
Problem Statement
You are given a string S of length N consisting only of lowercase English letters.
Find the number of strings obtained by permuting the characters of S (including the string S itself) that do not contain a palindrome of length K as a substring.
Here, a string T of length N is said to "contain a palindrome of length K as a substring" if and only if there exists a non-negative integer i not greater than (N-K) such that T_{i+j} = T_{i+K+1-j} for every integer j with 1 \leq j \leq K.
Here, T_k denotes the k-th character of the string T.
Constraints
- 2 \leq K \leq N \leq 10
- N and K are integers.
- S is a string of length N consisting only of lowercase English letters.
Input
The input is given from Standard Input in the following format:
N K S
Output
Print the number of strings obtained by permuting S that do not contain a palindrome of length K as a substring.
Sample Input 1
3 2 aab
Sample Output 1
1
The strings obtained by permuting aab are aab, aba, and baa. Among these, aab and baa contain the palindrome aa of length 2 as a substring.
Thus, the only string that satisfies the condition is aba, so print 1.
Sample Input 2
5 3 zzyyx
Sample Output 2
16
There are 30 strings obtained by permuting zzyyx, 16 of which do not contain a palindrome of length 3. Thus, print 16.
Sample Input 3
10 5 abcwxyzyxw
Sample Output 3
440640