Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
今日の曜日を表す文字列 S が与えられます。
S は SUN,MON,TUE,WED,THU,FRI,SAT のいずれかであり、それぞれ日曜日、月曜日、火曜日、水曜日、木曜日、金曜日、土曜日を表します。
次の日曜日 (あす以降) が何日後か求めてください。
制約
- S は
SUN,MON,TUE,WED,THU,FRI,SATのいずれか
入力
入力は以下の形式で標準入力から与えられる。
S
出力
次の日曜日が何日後か出力せよ。
入力例 1
SAT
出力例 1
1
今日は土曜日です。よって、次の日曜日は 1 日後です。
入力例 2
SUN
出力例 2
7
今日は日曜日です。よって、次の日曜日は 7 日後です。
Score : 100 points
Problem Statement
Given is a string S representing the day of the week today.
S is SUN, MON, TUE, WED, THU, FRI, or SAT, for Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, and Saturday, respectively.
After how many days is the next Sunday (tomorrow or later)?
Constraints
- S is
SUN,MON,TUE,WED,THU,FRI, orSAT.
Input
Input is given from Standard Input in the following format:
S
Output
Print the number of days before the next Sunday.
Sample Input 1
SAT
Sample Output 1
1
It is Saturday today, and tomorrow will be Sunday.
Sample Input 2
SUN
Sample Output 2
7
It is Sunday today, and seven days later, it will be Sunday again.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
英大文字のみからなる文字列 S があります。また、整数 N が与えられます。
S の各文字を、アルファベット順で N 個後の文字に置き換えた文字列を出力してください。
ただしアルファベット順で Z の 1 個後の文字は A とみなします。
制約
- 0 \leq N \leq 26
- 1 \leq |S| \leq 10^4
- S は英大文字のみからなる
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
S の各文字を、アルファベット順で N 個後の文字に置き換えた文字列を出力せよ。
入力例 1
2 ABCXYZ
出力例 1
CDEZAB
アルファベット順で Z の 1 個後の文字は A であることに注意してください。
入力例 2
0 ABCXYZ
出力例 2
ABCXYZ
入力例 3
13 ABCDEFGHIJKLMNOPQRSTUVWXYZ
出力例 3
NOPQRSTUVWXYZABCDEFGHIJKLM
Score : 200 points
Problem Statement
We have a string S consisting of uppercase English letters. Additionally, an integer N will be given.
Shift each character of S by N in alphabetical order (see below), and print the resulting string.
We assume that A follows Z. For example, shifting A by 2 results in C (A \to B \to C), and shifting Y by 3 results in B (Y \to Z \to A \to B).
Constraints
- 0 \leq N \leq 26
- 1 \leq |S| \leq 10^4
- S consists of uppercase English letters.
Input
Input is given from Standard Input in the following format:
N S
Output
Print the string resulting from shifting each character of S by N in alphabetical order.
Sample Input 1
2 ABCXYZ
Sample Output 1
CDEZAB
Note that A follows Z.
Sample Input 2
0 ABCXYZ
Sample Output 2
ABCXYZ
Sample Input 3
13 ABCDEFGHIJKLMNOPQRSTUVWXYZ
Sample Output 3
NOPQRSTUVWXYZABCDEFGHIJKLM
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
高橋くんは整数を 1 つ買いに整数屋さんに行きました。
整数屋さんには 1 以上 10^9 以下の整数が売られていて、整数 N を買うためには A \times N + B \times d(N) 円が必要です。ここで、d(N) は N の十進表記での桁数です。
高橋くんの所持金が X 円のとき、高橋くんの買うことのできる最も大きい整数を求めてください。ただし、買うことのできる整数が 1 つもない場合は 0 を出力してください。
制約
- 入力は全て整数である。
- 1 \leq A \leq 10^9
- 1 \leq B \leq 10^9
- 1 \leq X \leq 10^{18}
入力
入力は以下の形式で標準入力から与えられる。
A B X
出力
高橋くんの買うことのできる最も大きい整数を出力せよ。ただし、買うことのできる整数が 1 つもない場合は 0 を出力せよ。
入力例 1
10 7 100
出力例 1
9
9 の値段は 10 \times 9 + 7 \times 1 = 97 円で、これが買うことのできる最大の整数です。 他の整数の値段の例をいくつかあげると
- 10: 10 \times 10 + 7 \times 2 = 114 円
- 100: 10 \times 100 + 7 \times 3 = 1021 円
- 12345: 10 \times 12345 + 7 \times 5 = 123485 円
です。
入力例 2
2 1 100000000000
出力例 2
1000000000
お店に売られている最大の整数を買うことができます。入力が 32 bit整数型に収まらないことがあることに注意してください。
入力例 3
1000000000 1000000000 100
出力例 3
0
入力例 4
1234 56789 314159265
出力例 4
254309
Score : 300 points
Problem Statement
Takahashi has come to an integer shop to buy an integer.
The shop sells the integers from 1 through 10^9. The integer N is sold for A \times N + B \times d(N) yen (the currency of Japan), where d(N) is the number of digits in the decimal notation of N.
Find the largest integer that Takahashi can buy when he has X yen. If no integer can be bought, print 0.
Constraints
- All values in input are integers.
- 1 \leq A \leq 10^9
- 1 \leq B \leq 10^9
- 1 \leq X \leq 10^{18}
Input
Input is given from Standard Input in the following format:
A B X
Output
Print the greatest integer that Takahashi can buy. If no integer can be bought, print 0.
Sample Input 1
10 7 100
Sample Output 1
9
The integer 9 is sold for 10 \times 9 + 7 \times 1 = 97 yen, and this is the greatest integer that can be bought. Some of the other integers are sold for the following prices:
- 10: 10 \times 10 + 7 \times 2 = 114 yen
- 100: 10 \times 100 + 7 \times 3 = 1021 yen
- 12345: 10 \times 12345 + 7 \times 5 = 123485 yen
Sample Input 2
2 1 100000000000
Sample Output 2
1000000000
He can buy the largest integer that is sold. Note that input may not fit into a 32-bit integer type.
Sample Input 3
1000000000 1000000000 100
Sample Output 3
0
Sample Input 4
1234 56789 314159265
Sample Output 4
254309
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
N 頂点の木 G が与えられます。 頂点には 1 から N までの番号がついており、i 本目の辺は頂点 a_i と頂点 b_i を結んでいます。
G の辺を何色かで塗り分けることを考えます。 このとき、各頂点について、その頂点を端点に持つ辺の色がすべて相異なるようにしたいです。
上記の条件を満たす塗り分けの中で、使用する色の数が最小であるようなものを 1 つ構築してください。
制約
- 2 \le N \le 10^5
- 1 \le a_i \lt b_i \le N
- 入力はすべて整数
- 与えられるグラフは木である
入力
入力は以下の形式で標準入力から与えられる。
N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}
出力
出力は N 行からなる。
1 行目に使用する色の数 K を出力せよ。
i+1 行目 (1 \le i \le N-1) に i 番目の辺の色を表す整数 c_i を出力せよ。ここで 1 \le c_i \le K でなければならない。
問題文中の条件を満たし、使用する色の数が最小であるような塗り分けが複数存在するときは、そのうちのどれを出力しても構わない。
入力例 1
3 1 2 2 3
出力例 1
2 1 2
入力例 2
8 1 2 2 3 2 4 2 5 4 7 5 6 6 8
出力例 2
4 1 2 3 4 1 1 2
入力例 3
6 1 2 1 3 1 4 1 5 1 6
出力例 3
5 1 2 3 4 5
Score : 400 points
Problem Statement
Given is a tree G with N vertices. The vertices are numbered 1 through N, and the i-th edge connects Vertex a_i and Vertex b_i.
Consider painting the edges in G with some number of colors. We want to paint them so that, for each vertex, the colors of the edges incident to that vertex are all different.
Among the colorings satisfying the condition above, construct one that uses the minimum number of colors.
Constraints
- 2 \le N \le 10^5
- 1 \le a_i \lt b_i \le N
- All values in input are integers.
- The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}
Output
Print N lines.
The first line should contain K, the number of colors used.
The (i+1)-th line (1 \le i \le N-1) should contain c_i, the integer representing the color of the i-th edge, where 1 \le c_i \le K must hold.
If there are multiple colorings with the minimum number of colors that satisfy the condition, printing any of them will be accepted.
Sample Input 1
3 1 2 2 3
Sample Output 1
2 1 2
Sample Input 2
8 1 2 2 3 2 4 2 5 4 7 5 6 6 8
Sample Output 2
4 1 2 3 4 1 1 2
Sample Input 3
6 1 2 1 3 1 4 1 5 1 6
Sample Output 3
5 1 2 3 4 5
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
長さ N の正整数列 A_1, A_2, \ldots , A_N と正の整数 K が与えられます。
A の空でない連続する部分列であって、要素の和を K で割った余りが要素の数と等しくなるものの数を求めてください。ただし、2 つの部分列が列として同じでも、取り出す位置が異なるならば区別するものとします。
制約
- 入力は全て整数である。
- 1 \leq N \leq 2\times 10^5
- 1 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \cdots A_N
出力
条件をみたす部分列の個数を出力してください。
入力例 1
5 4 1 4 2 3 5
出力例 1
4
(1), (4,2), (1,4,2), (5) の 4 つが条件をみたす部分列です。
入力例 2
8 4 4 2 4 2 4 2 4 2
出力例 2
7
(4,2) が 4 回、(2,4) が 3 回数えられています。
入力例 3
10 7 14 15 92 65 35 89 79 32 38 46
出力例 3
8
Score : 500 points
Problem Statement
Given are a sequence of N positive integers A_1, A_2, \ldots, A_N, and a positive integer K.
Find the number of non-empty contiguous subsequences in A such that the remainder when dividing the sum of its elements by K is equal to the number of its elements. We consider two subsequences different if they are taken from different positions, even if they are equal sequences.
Constraints
- All values in input are integers.
- 1 \leq N \leq 2\times 10^5
- 1 \leq K \leq 10^9
- 1 \leq A_i \leq 10^9
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \cdots A_N
Output
Print the number of subsequences that satisfy the condition.
Sample Input 1
5 4 1 4 2 3 5
Sample Output 1
4
Four sequences satisfy the condition: (1), (4,2), (1,4,2), and (5).
Sample Input 2
8 4 4 2 4 2 4 2 4 2
Sample Output 2
7
(4,2) is counted four times, and (2,4) is counted three times.
Sample Input 3
10 7 14 15 92 65 35 89 79 32 38 46
Sample Output 3
8
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
高橋君は双六で遊んでいます。
この双六には 0 から N までの番号がついた N + 1 個のマスがあります。高橋君はマス 0 からスタートし、ゴールするにはマス N にちょうど止まらなければなりません。
この双六では、1 から M までの M 種類の目が出るルーレットを使います。各手番で、高橋君はルーレットを回して出た目の数だけ進みます。この結果マス N を越えて進むことになる場合、ゲームオーバーとなります。
また、いくつかのマスは「ゲームオーバーマス」であり、それらのマスに止まってもゲームオーバーとなります。マスの情報は長さ N + 1 の文字列 S で与えられます。各 i (0 \leq i \leq N) について、S[i] = 1 のときマス i はゲームオーバーマスであり、S[i] = 0 のときマス i はゲームオーバーマスではありません。
高橋君がゲームオーバーとならずに最短手数でゴールするときの出目を順に答えてください。そのような目の出方が複数存在するときは、そのうち出目の列が辞書順で最小であるものを出力してください。ゲームオーバーとならずにゴールすることが不可能である場合は、 -1 を出力してください。
制約
- 1 ≤ N ≤ 10^5
- 1 ≤ M ≤ 10^5
- |S| = N + 1
- S は
0と1から成る - S[0] =
0 - S[N] =
0
入力
入力は以下の形式で標準入力から与えられる。
N M S
出力
ゴールすることが可能である場合、そのような最短の出目の列のうち辞書順で最小のものを出力せよ。ゴールすることが不可能である場合、-1 を出力せよ。
入力例 1
9 3 0001000100
出力例 1
1 3 2 3
1 , 3 , 2 , 3 の順に目を出すと、高橋君はマス 1 , 4 , 6 を経由してマス 9 に到達することが出来ます。高橋君が 3 手以内にマス 9 に到達することは不可能であり、また 4 手でマス 9 に到達するような出目の列の中ではこれが辞書順で最小です。
入力例 2
5 4 011110
出力例 2
-1
高橋君はマス 5 に到達することが出来ません。
入力例 3
6 6 0101010
出力例 3
6
Score : 600 points
Problem Statement
Takahashi is playing a board game called Sugoroku.
On the board, there are N + 1 squares numbered 0 to N. Takahashi starts at Square 0, and he has to stop exactly at Square N to win the game.
The game uses a roulette with the M numbers from 1 to M. In each turn, Takahashi spins the roulette. If the number x comes up when he is at Square s, he moves to Square s+x. If this makes him go beyond Square N, he loses the game.
Additionally, some of the squares are Game Over Squares. He also loses the game if he stops at one of those squares. You are given a string S of length N + 1, representing which squares are Game Over Squares. For each i (0 \leq i \leq N), Square i is a Game Over Square if S[i] = 1 and not if S[i] = 0.
Find the sequence of numbers coming up in the roulette in which Takahashi can win the game in the fewest number of turns possible. If there are multiple such sequences, find the lexicographically smallest such sequence. If Takahashi cannot win the game, print -1.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- |S| = N + 1
- S consists of
0and1. - S[0] =
0 - S[N] =
0
Input
Input is given from Standard Input in the following format:
N M S
Output
If Takahashi can win the game, print the lexicographically smallest sequence among the shortest sequences of numbers coming up in the roulette in which Takahashi can win the game, with spaces in between.
If Takahashi cannot win the game, print -1.
Sample Input 1
9 3 0001000100
Sample Output 1
1 3 2 3
If the numbers 1, 3, 2, 3 come up in this order, Takahashi can reach Square 9 via Square 1, 4, and 6. He cannot reach Square 9 in three or fewer turns, and this is the lexicographically smallest sequence in which he reaches Square 9 in four turns.
Sample Input 2
5 4 011110
Sample Output 2
-1
Takahashi cannot reach Square 5.
Sample Input 3
6 6 0101010
Sample Output 3
6