Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
3 つの箱 A,B,C があります。それぞれの箱には、整数が 1 つ入っています。
現在、箱 A,B,C に入っている整数はそれぞれ X,Y,Z です。
これらの箱に対して以下の操作を順に行った後の、それぞれの箱に入っている整数を求めてください。
- 箱 A と箱 B の中身を入れ替える
- 箱 A と箱 C の中身を入れ替える
制約
- 1 \leq X,Y,Z \leq 100
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
X Y Z
出力
箱 A,B,C に入っている整数を、順番に空白区切りで出力せよ。
入力例 1
1 2 3
出力例 1
3 1 2
箱 A と箱 B の中身を入れ替えた後、箱 A,B,C に入っている整数はそれぞれ 2,1,3 です。
箱 A と箱 C の中身を入れ替えた後、箱 A,B,C に入っている整数はそれぞれ 3,1,2 です。
入力例 2
100 100 100
出力例 2
100 100 100
入力例 3
41 59 31
出力例 3
31 41 59
Score : 100 points
Problem Statement
We have three boxes A, B, and C, each of which contains an integer.
Currently, the boxes A, B, and C contain the integers X, Y, and Z, respectively.
We will now do the operations below in order. Find the content of each box afterward.
- Swap the contents of the boxes A and B
- Swap the contents of the boxes A and C
Constraints
- 1 \leq X,Y,Z \leq 100
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
X Y Z
Output
Print the integers contained in the boxes A, B, and C, in this order, with space in between.
Sample Input 1
1 2 3
Sample Output 1
3 1 2
After the contents of the boxes A and B are swapped, A, B, and C contain 2, 1, and 3, respectively.
Then, after the contents of A and C are swapped, A, B, and C contain 3, 1, and 2, respectively.
Sample Input 2
100 100 100
Sample Output 2
100 100 100
Sample Input 3
41 59 31
Sample Output 3
31 41 59
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
N 種類の商品に対して人気投票を行いました。商品 i は A_i 票を得ています。
この中から人気商品 M 個を選びます。ただし、得票数が総投票数の \dfrac{1}{4M} 未満であるような商品は選べません。
人気商品 M 個を選べるなら Yes
、選べないなら No
を出力してください。
制約
- 1 \leq M \leq N \leq 100
- 1 \leq A_i \leq 1000
- A_i は相異なる
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 ... A_N
出力
人気商品 M 個を選べるなら Yes
、選べないなら No
を出力せよ。
入力例 1
4 1 5 4 2 1
出力例 1
Yes
総投票数は 12 です。1 位の得票数は 5 なので、これを選ぶことができます。
入力例 2
3 2 380 19 1
出力例 2
No
総投票数は 400 です。2,3 位の得票数は総得票数の \dfrac{1}{4\times 2} 未満なので、これらを選ぶことはできず、人気商品 2 個を選べません。
入力例 3
12 3 4 56 78 901 2 345 67 890 123 45 6 789
出力例 3
Yes
Score : 200 points
Problem Statement
We have held a popularity poll for N items on sale. Item i received A_i votes.
From these N items, we will select M as popular items. However, we cannot select an item with less than \dfrac{1}{4M} of the total number of votes.
If M popular items can be selected, print Yes
; otherwise, print No
.
Constraints
- 1 \leq M \leq N \leq 100
- 1 \leq A_i \leq 1000
- A_i are distinct.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 ... A_N
Output
If M popular items can be selected, print Yes
; otherwise, print No
.
Sample Input 1
4 1 5 4 2 1
Sample Output 1
Yes
There were 12 votes in total. The most popular item received 5 votes, and we can select it.
Sample Input 2
3 2 380 19 1
Sample Output 2
No
There were 400 votes in total. The second and third most popular items received less than \dfrac{1}{4\times 2} of the total number of votes, so we cannot select them. Thus, we cannot select two popular items.
Sample Input 3
12 3 4 56 78 901 2 345 67 890 123 45 6 789
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
青木君は任意の整数 x に対し、以下の操作を行うことができます。
操作: x を x と K の差の絶対値で置き換える。
整数 N の初期値が与えられます。この整数に上記の操作を 0 回以上好きな回数行った時にとりうる N の最小値を求めてください。
制約
- 0 ≤ N ≤ 10^{18}
- 1 ≤ K ≤ 10^{18}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
操作を 0 回以上好きな回数行った時にとりうる N の最小値を出力せよ。
入力例 1
7 4
出力例 1
1
最初、 N=7 です。
1 回操作を行うと、N は |7-4| = 3 となります。
2 回操作を行うと、N は |3-4|=1 となり、これが最小です。
入力例 2
2 6
出力例 2
2
1 回も操作を行わなかった場合の N=2 が最小です。
入力例 3
1000000000000000000 1
出力例 3
0
Score : 300 points
Problem Statement
Given any integer x, Aoki can do the operation below.
Operation: Replace x with the absolute difference of x and K.
You are given the initial value of an integer N. Find the minimum possible value taken by N after Aoki does the operation zero or more times.
Constraints
- 0 ≤ N ≤ 10^{18}
- 1 ≤ K ≤ 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K
Output
Print the minimum possible value taken by N after Aoki does the operation zero or more times.
Sample Input 1
7 4
Sample Output 1
1
Initially, N=7.
After one operation, N becomes |7-4| = 3.
After two operations, N becomes |3-4| = 1, which is the minimum value taken by N.
Sample Input 2
2 6
Sample Output 2
2
N=2 after zero operations is the minimum.
Sample Input 3
1000000000000000000 1
Sample Output 3
0
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
正の整数 X が以下の条件を満たすとき、 X はルンルン数であると言います。
- X を(leading zeroなしで)十進数表記した際に、隣り合うどの 2 つの桁の値についても、差の絶対値が 1 以下
例えば、 1234 , 1 , 334 などはルンルン数ですが、 31415 , 119 , 13579 などはルンルン数ではありません。
正の整数 K が与えられます。小さい方から K 番目のルンルン数を求めてください。
制約
- 1 \leq K \leq 10^5
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
K
出力
答えを出力せよ。
入力例 1
15
出力例 1
23
小さい方から 15 番目までのルンルン数を順に並べると、
1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11,
12,
21,
22,
23
ですので、答えは 23 です。
入力例 2
1
出力例 2
1
入力例 3
13
出力例 3
21
入力例 4
100000
出力例 4
3234566667
答えが 32 ビット符号付き整数の範囲に収まらない可能性があるので注意してください。
Score : 400 points
Problem Statement
A positive integer X is said to be a lunlun number if and only if the following condition is satisfied:
- In the base ten representation of X (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most 1.
For example, 1234, 1, and 334 are lunlun numbers, while none of 31415, 119, or 13579 is.
You are given a positive integer K. Find the K-th smallest lunlun number.
Constraints
- 1 \leq K \leq 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
K
Output
Print the answer.
Sample Input 1
15
Sample Output 1
23
We will list the 15 smallest lunlun numbers in ascending order:
1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11,
12,
21,
22,
23.
Thus, the answer is 23.
Sample Input 2
1
Sample Output 2
1
Sample Input 3
13
Sample Output 3
21
Sample Input 4
100000
Sample Output 4
3234566667
Note that the answer may not fit into the 32-bit signed integer type.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
高橋君は明日からの N 日間のうち K 日を選んで働くことにしました。
整数 C と文字列 S が与えられるので、次の 2 つの条件を満たすようにして働く日を選びます。
- ある日働いたら、その直後の C 日間は働かない
- S の i 文字目が
x
のとき、今日から i 日後には働かない
高橋君が必ず働く日をすべて求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- 0 \leq C \leq N
- S の長さは N
- S の各文字は
o
かx
- 問題文中の条件を満たすように働く日を選ぶことが可能
入力
入力は以下の形式で標準入力から与えられる。
N K C S
出力
高橋君が必ず働く日を昇順に改行区切りですべて出力せよ。
入力例 1
11 3 2 ooxxxoxxxoo
出力例 1
6
高橋君は 11 日間のうち 3 日働こうとしています。ある日働いたらその後 2 日間は働きません。
働く日としてありえる組み合わせは「1,6,10 日目」「1,6,11 日目」「2,6,10 日目」「2,6,11 日目」の 4 通りです。
したがって、6 日目に必ず働きます。
入力例 2
5 2 3 ooxoo
出力例 2
1 5
働く日としてありえる組み合わせは「1,5 日目」のみです。
入力例 3
5 1 0 ooooo
出力例 3
必ず働く日が存在しないこともあります。
入力例 4
16 4 3 ooxxoxoxxxoxoxxo
出力例 4
11 16
Score : 500 points
Problem Statement
Takahashi has decided to work on K days of his choice from the N days starting with tomorrow.
You are given an integer C and a string S. Takahashi will choose his workdays as follows:
- After working for a day, he will refrain from working on the subsequent C days.
- If the i-th character of S is
x
, he will not work on Day i, where Day 1 is tomorrow, Day 2 is the day after tomorrow, and so on.
Find all days on which Takahashi is bound to work.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- 0 \leq C \leq N
- The length of S is N.
- Each character of S is
o
orx
. - Takahashi can choose his workdays so that the conditions in Problem Statement are satisfied.
Input
Input is given from Standard Input in the following format:
N K C S
Output
Print all days on which Takahashi is bound to work in ascending order, one per line.
Sample Input 1
11 3 2 ooxxxoxxxoo
Sample Output 1
6
Takahashi is going to work on 3 days out of the 11 days. After working for a day, he will refrain from working on the subsequent 2 days.
There are four possible choices for his workdays: Day 1,6,10, Day 1,6,11, Day 2,6,10, and Day 2,6,11.
Thus, he is bound to work on Day 6.
Sample Input 2
5 2 3 ooxoo
Sample Output 2
1 5
There is only one possible choice for his workdays: Day 1,5.
Sample Input 3
5 1 0 ooooo
Sample Output 3
There may be no days on which he is bound to work.
Sample Input 4
16 4 3 ooxxoxoxxxoxoxxo
Sample Output 4
11 16
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
正整数 N が与えられます。
2 以上 N 以下の整数 K を決めて、N が K 未満になるまで次の操作を繰り返し行います。
- 操作:N が K で割り切れるとき、N を N/K に置き換える。そうでないとき、N を N-K に置き換える。
最終的に N が 1 になるような K の決め方は何通りありますか?
制約
- 2 \leq N \leq 10^{12}
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
最終的に N が 1 になるような K の決め方が何通りあるか出力せよ。
入力例 1
6
出力例 1
3
最終的に N が 1 になるような K は 2,5,6 の 3 通りです。
それぞれのとき、N は次のように変化します。
- K=2 のとき:6 \to 3 \to 1
- K=5 のとき:6 \to 1
- K=6 のとき:6 \to 1
入力例 2
3141
出力例 2
13
入力例 3
314159265358
出力例 3
9
Score : 600 points
Problem Statement
Given is a positive integer N.
We will choose an integer K between 2 and N (inclusive), then we will repeat the operation below until N becomes less than K.
- Operation: if K divides N, replace N with N/K; otherwise, replace N with N-K.
In how many choices of K will N become 1 in the end?
Constraints
- 2 \leq N \leq 10^{12}
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the number of choices of K in which N becomes 1 in the end.
Sample Input 1
6
Sample Output 1
3
There are three choices of K in which N becomes 1 in the end: 2, 5, and 6.
In each of these choices, N will change as follows:
- When K=2: 6 \to 3 \to 1
- When K=5: 6 \to 1
- When K=6: 6 \to 1
Sample Input 2
3141
Sample Output 2
13
Sample Input 3
314159265358
Sample Output 3
9