Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
高橋君は，いつも頭の中に整数を 1 つ思い浮かべています．
はじめ，高橋君が思い浮かべている整数は 0 です．
これから，高橋君は + または - の記号を，あわせて 4 つ食べようとしています．
高橋君が + を食べると，思い浮かべている整数は 1 大きくなります．
一方，高橋君が - を食べると，思い浮かべている整数は 1 小さくなります．
高橋君が食べようとしている記号は，文字列 S で与えられます． S の i 文字目は，高橋君が i 番目に食べる記号です．
すべての記号を食べ終わった後，高橋君が思い浮かべている整数を求めてください．
制約
- S の長さは 4
- S の各文字は
+または-
入力
入力は以下の形式で標準入力から与えられる．
S
出力
すべての記号を食べ終わった後，高橋君が思い浮かべている整数を出力せよ．
入力例 1
+-++
出力例 1
2
- はじめ，高橋君が思い浮かべている整数は 0 です．
- 高橋君が食べる 1 番目の記号は
+です．これを食べた後，高橋君が思い浮かべている整数は 1 になります． - 高橋君が食べる 2 番目の記号は
-です．これを食べた後，高橋君が思い浮かべている整数は 0 になります． - 高橋君が食べる 3 番目の記号は
+です．これを食べた後，高橋君が思い浮かべている整数は 1 になります． - 高橋君が食べる 4 番目の記号は
+です．これを食べた後，高橋君が思い浮かべている整数は 2 になります．
よって，すべての記号を食べ終わった後，高橋君が思い浮かべている整数は 2 です．
入力例 2
-+--
出力例 2
-2
入力例 3
----
出力例 3
-4
Score : 100 points
Problem Statement
There is always an integer in Takahashi's mind.
Initially, the integer in Takahashi's mind is 0. Takahashi is now going to eat four symbols, each of which is + or -. When he eats +, the integer in his mind increases by 1; when he eats -, the integer in his mind decreases by 1.
The symbols Takahashi is going to eat are given to you as a string S. The i-th character in S is the i-th symbol for him to eat.
Find the integer in Takahashi's mind after he eats all the symbols.
Constraints
- The length of S is 4.
- Each character in S is
+or-.
Input
Input is given from Standard Input in the following format:
S
Output
Print the integer in Takahashi's mind after he eats all the symbols.
Sample Input 1
+-++
Sample Output 1
2
- Initially, the integer in Takahashi's mind is 0.
- The first integer for him to eat is
+. After eating it, the integer in his mind becomes 1. - The second integer to eat is
-. After eating it, the integer in his mind becomes 0. - The third integer to eat is
+. After eating it, the integer in his mind becomes 1. - The fourth integer to eat is
+. After eating it, the integer in his mind becomes 2.
Thus, the integer in Takahashi's mind after he eats all the symbols is 2.
Sample Input 2
-+--
Sample Output 2
-2
Sample Input 3
----
Sample Output 3
-4
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
整数 n に対して，n を十進法で表したときの各桁の和を S(n) で表すことにします． たとえば，S(101) = 1 + 0 + 1 = 2 です．
整数 N が与えられたとき，N が S(N) で割り切れるかどうかを判定してください．
制約
- 1 \leq N \leq 10^9
入力
入力は以下の形式で標準入力から与えられる．
N
出力
N が S(N) で割り切れるなら Yes を，割り切れないなら No を出力せよ．
入力例 1
12
出力例 1
Yes
この入力では N=12 です． S(12) = 1 + 2 = 3 なので，N は S(N) で割り切れます．
入力例 2
101
出力例 2
No
S(101) = 1 + 0 + 1 = 2 なので，N は S(N) で割り切れません．
入力例 3
999999999
出力例 3
Yes
Score : 200 points
Problem Statement
Let S(n) denote the sum of the digits in the decimal notation of n. For example, S(101) = 1 + 0 + 1 = 2.
Given an integer N, determine if S(N) divides N.
Constraints
- 1 \leq N \leq 10^9
Input
Input is given from Standard Input in the following format:
N
Output
If S(N) divides N, print Yes; if it does not, print No.
Sample Input 1
12
Sample Output 1
Yes
In this input, N=12. As S(12) = 1 + 2 = 3, S(N) divides N.
Sample Input 2
101
Sample Output 2
No
As S(101) = 1 + 0 + 1 = 2, S(N) does not divide N.
Sample Input 3
999999999
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
長さ N の数列 A_1, A_2, ..., A_N があります．最初，この数列の要素は 1, 2, ..., N を並び替えたものになっています．
スヌケ君は，この数列に対して次の操作を行うことができます．
- 数列のうち，連続した K 個の要素を選ぶ．その後，選んだ要素それぞれの値を，選んだ要素の中の最小値で置き換える．
スヌケ君は，上の操作を何回か繰り返すことで，この数列の要素をすべて等しくしたいです． 必要な操作の回数の最小値を求めてください． この問題の制約の下，このようなことは必ず可能であることが証明できます．
制約
- 2 \leq K \leq N \leq 100000
- A_1, A_2, ..., A_N は 1, 2, ..., N の並び替え
入力
入力は以下の形式で標準入力から与えられる．
N K A_1 A_2 ... A_N
出力
必要な操作の回数の最小値を出力せよ．
入力例 1
4 3 2 3 1 4
出力例 1
2
例えば，次のようにするとよいです：
- 1 回目の操作では，1, 2, 3 番目の要素を選ぶ．すると，数列 A は 1, 1, 1, 4 になる．
- 2 回目の操作では，2, 3, 4 番目の要素を選ぶ．すると，数列 A は 1, 1, 1, 1 になる．
入力例 2
3 3 1 2 3
出力例 2
1
入力例 3
8 3 7 3 1 8 4 6 2 5
出力例 3
4
Score : 300 points
Problem Statement
There is a sequence of length N: A_1, A_2, ..., A_N. Initially, this sequence is a permutation of 1, 2, ..., N.
On this sequence, Snuke can perform the following operation:
- Choose K consecutive elements in the sequence. Then, replace the value of each chosen element with the minimum value among the chosen elements.
Snuke would like to make all the elements in this sequence equal by repeating the operation above some number of times. Find the minimum number of operations required. It can be proved that, Under the constraints of this problem, this objective is always achievable.
Constraints
- 2 \leq K \leq N \leq 100000
- A_1, A_2, ..., A_N is a permutation of 1, 2, ..., N.
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 ... A_N
Output
Print the minimum number of operations required.
Sample Input 1
4 3 2 3 1 4
Sample Output 1
2
One optimal strategy is as follows:
-
In the first operation, choose the first, second and third elements. The sequence A becomes 1, 1, 1, 4.
-
In the second operation, choose the second, third and fourth elements. The sequence A becomes 1, 1, 1, 1.
Sample Input 2
3 3 1 2 3
Sample Output 2
1
Sample Input 3
8 3 7 3 1 8 4 6 2 5
Sample Output 3
4
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
整数 n に対して，n を十進法で表したときの各桁の和を S(n) で表すことにします． たとえば，S(123) = 1 + 2 + 3 = 6 です．
正の整数 n であって，m > n であるような任意の正の整数 m に対して \frac{n}{S(n)} \leq \frac{m}{S(m)} が成り立つようなものを， すぬけ数 と呼ぶことにします．
整数 K が与えられたとき，すぬけ数を小さいほうから K 個列挙してください．
制約
- 1 \leq K
- K 番目のすぬけ数は 10^{15} 以下
入力
入力は以下の形式で標準入力から与えられる．
K
出力
K 行出力せよ．i 行目には，i 番目に小さいすぬけ数を出力せよ．
入力例 1
10
出力例 1
1 2 3 4 5 6 7 8 9 19
Score : 500 points
Problem Statement
Let S(n) denote the sum of the digits in the decimal notation of n. For example, S(123) = 1 + 2 + 3 = 6.
We will call an integer n a Snuke number when, for all positive integers m such that m > n, \frac{n}{S(n)} \leq \frac{m}{S(m)} holds.
Given an integer K, list the K smallest Snuke numbers.
Constraints
- 1 \leq K
- The K-th smallest Snuke number is not greater than 10^{15}.
Input
Input is given from Standard Input in the following format:
K
Output
Print K lines. The i-th line should contain the i-th smallest Snuke number.
Sample Input 1
10
Sample Output 1
1 2 3 4 5 6 7 8 9 19