Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
A 以上かつ B 以下の整数はいくつありますか?
制約
- 1 \leq A \leq 100
- 1 \leq B \leq 100
- A, B は整数である。
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
A 以上かつ B 以下の整数の個数を出力せよ。
入力例 1
2 4
出力例 1
3
2 以上かつ 4 以下の整数は 2, 3, 4 の 3 つなので、 3 を出力してください。
入力例 2
10 100
出力例 2
91
入力例 3
3 2
出力例 3
0
3 以上かつ 2 以下の整数は存在しないので、 0 を出力してください。
Score : 100 points
Problem Statement
How many integers not less than A and not more than B are there?
Constraints
- 1 \leq A \leq 100
- 1 \leq B \leq 100
- A and B are integers.
Input
Input is given from Standard Input in the following format:
A B
Output
Print the number of integers not less than A and not more than B.
Sample Input 1
2 4
Sample Output 1
3
We have three integers not less than 2 and not more than 4: 2, 3, 4, so we should print 3.
Sample Input 2
10 100
Sample Output 2
91
Sample Input 3
3 2
Sample Output 3
0
We have no integers not less than 3 and not more than 2, so we should print 0.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
高橋商店では N 個の商品が売られています。i\, (1 \leq i \leq N) 番目の商品の定価は A_i 円です。
今日はセールが行われており、偶数番目の商品は定価の 1 円引きの値段で買うことができます。奇数番目の商品は定価で売られています。
あなたの所持金は X 円です。これら N 個の商品を全て買うことができますか?
制約
- 1 \leq N \leq 100
- 1 \leq X \leq 10000
- 1 \leq A_i \leq 100
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X A_1 A_2 \ldots A_N
出力
N 個の商品を全て買うことができるなら Yes
、できないなら No
と出力せよ。
入力例 1
2 3 1 3
出力例 1
Yes
1 番目の商品は 1 円、2 番目の商品は定価より 1 円引きの 2 円で買うことができます。あなたの所持金は 3 円なので、ちょうどの金額で 2 個の商品を全て買うことができます。
入力例 2
4 10 3 3 4 4
出力例 2
No
4 個の商品はそれぞれ 3 円、2 円、4 円、3 円で買うことができます。4 個の商品を全て買うためには 12 円必要ですが、あなたの所持金は 10 円なので全て買うことはできません。
入力例 3
8 30 3 1 4 1 5 9 2 6
出力例 3
Yes
Score : 200 points
Problem Statement
Takahashi's shop sells N products. The usual price of the i-th product is A_i yen (Japanese currency).
It has a bargain sale today, with a discount of 1 yen off the usual prices for the 2-nd, 4-th, and the subsequent even-indexed products. The 1-st, 3-rd, and the subsequent odd-indexed products are sold for their usual prices.
You have X yen. Can you buy all the N products with this money?
Constraints
- 1 \leq N \leq 100
- 1 \leq X \leq 10000
- 1 \leq A_i \leq 100
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X A_1 A_2 \ldots A_N
Output
If you can buy all the N products, print Yes
; otherwise, print No
.
Sample Input 1
2 3 1 3
Sample Output 1
Yes
You can buy the 1-st product for 1 yen and the 2-nd product for 2 yen, 1 yen off the usual price. You have just enough money, 3 yen, to buy both of them.
Sample Input 2
4 10 3 3 4 4
Sample Output 2
No
You can buy these four products for 3 yen, 2 yen, 4 yen, and 3 yen, respectively. You need 12 yen to buy all of them, and since you have only 10 yen, you cannot buy all of them.
Sample Input 3
8 30 3 1 4 1 5 9 2 6
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
長さ N の整数列 C が与えられます。以下の条件を全て満たす長さ N の整数列 A の個数を求めてください。
- 1 \leq A_i \leq C_i\, (1 \leq i \leq N)
- A_i \neq A_j\, (1 \leq i < j \leq N)
ただし、答えは非常に大きくなる可能性があるので、(10^9+7) で割った余りを出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq C_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N C_1 C_2 \ldots C_N
出力
条件を全て満たす整数列 A の個数を (10^9+7) で割った余りを出力せよ。
入力例 1
2 1 3
出力例 1
2
条件を全て満たす A は (1,2) と (1,3) の 2 つです。 例えば A=(1,1) は 2 つ目の条件を満たしません。
入力例 2
4 3 3 4 4
出力例 2
12
入力例 3
2 1 1
出力例 3
0
条件を全て満たす整数列は 1 つも存在しないので、0 と出力してください。
入力例 4
10 999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979
出力例 4
405924645
(10^9+7) で割った余りを出力することに注意してください。
Score : 300 points
Problem Statement
You are given a sequence C of N integers. Find the number of sequences A of N integers satisfying all of the following conditions.
- 1 \leq A_i \leq C_i\, (1 \leq i \leq N)
- A_i \neq A_j\, (1 \leq i < j \leq N)
Since the count may be enormous, print it modulo (10^9+7).
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq C_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N C_1 C_2 \ldots C_N
Output
Print the number of sequences A of N integers satisfying all of the following conditions, modulo (10^9+7).
Sample Input 1
2 1 3
Sample Output 1
2
We have two sequences A satisfying all of the conditions: (1,2) and (1,3).
On the other hand, A=(1,1), for example, does not satisfy the second condition.
Sample Input 2
4 3 3 4 4
Sample Output 2
12
Sample Input 3
2 1 1
Sample Output 3
0
We have no sequences A satisfying all of the conditions, so we should print 0.
Sample Input 4
10 999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979
Sample Output 4
405924645
Be sure to print the count modulo (10^9+7).
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
高橋王国は N 個の街と N-1 本の道路からなり、街には 1 から N の番号がついています。また、i\, (1 \leq i \leq N-1) 本目の道路は街 a_i と街 b_i を双方向に結んでおり、どの街からどの街へもいくつかの道路を通ることで移動できます。道路は全て同じ長さです。
Q 個のクエリが与えられます。i\, (1 \leq i \leq Q) 番目のクエリでは整数 c_i,d_i が与えられるので、以下の問題を解いてください。
- 現在高橋君は街 c_i に、青木君は街 d_i にいる。二人が同時に街を出発し、それぞれ街 d_i, c_i を目指して同じ速さで移動するとき、二人が街で出会うか道路上(両端の街を除く)で出会うかを判定せよ。ただし、二人とも最短経路で移動し、街の中を移動する時間は無視できるものとする。
制約
- 2 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq a_i < b_i \leq N\, (1 \leq i \leq N-1)
- 1 \leq c_i < d_i \leq N\, (1 \leq i \leq Q)
- 入力は全て整数
- どの街からどの街へもいくつかの道路を通ることで移動できる
入力
入力は以下の形式で標準入力から与えられる。
N Q a_1 b_1 a_2 b_2 \hspace{0.6cm}\vdots a_{N-1} b_{N-1} c_1 d_1 c_2 d_2 \hspace{0.6cm}\vdots c_Q d_Q
出力
Q 行出力せよ。
i\, (1 \leq i \leq Q) 行目には、i 番目のクエリにおいて二人が街で出会うなら Town
、道路上で出会うなら Road
と出力せよ。
入力例 1
4 1 1 2 2 3 2 4 1 2
出力例 1
Road
1 番目のクエリでは、高橋君は街 1、青木君は街 2 を同時に出発し、1 本目の道路上で出会います。よって Road
と出力してください。
入力例 2
5 2 1 2 2 3 3 4 4 5 1 3 1 5
出力例 2
Town Town
1 番目のクエリでは、高橋君は街 1、青木君は街 3 を同時に出発し、街 2 で出会います。よって Town
と出力してください。
2 番目のクエリでは、高橋君は街 1、青木君は街 5 を同時に出発し、街 3 で出会います。よって Town
と出力してください。
入力例 3
9 9 2 3 5 6 4 8 8 9 4 5 3 4 1 9 3 7 7 9 2 5 2 6 4 6 2 4 5 8 7 8 3 6 5 6
出力例 3
Town Road Town Town Town Town Road Road Road
Score : 400 points
Problem Statement
The Kingdom of Takahashi is made up of N towns and N-1 roads, where the towns are numbered 1 through N. The i-th road (1 \leq i \leq N-1) connects Town a_i and Town b_i, so that you can get from every town to every town by using some roads. All the roads have the same length.
You will be given Q queries. In the i-th query (1 \leq i \leq Q), given integers c_i and d_i, solve the following problem:
- Takahashi is now at Town c_i and Aoki is now at Town d_i. They will leave the towns simultaneously and start traveling at the same speed, Takahashi heading to Town d_i and Aoki heading to Town c_i. Determine whether they will meet at a town or halfway along a road. Here, assume that both of them travel along the shortest paths, and the time it takes to pass towns is negligible.
Constraints
- 2 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq a_i < b_i \leq N\, (1 \leq i \leq N-1)
- 1 \leq c_i < d_i \leq N\, (1 \leq i \leq Q)
- All values in input are integers.
- It is possible to get from every town to every town by using some roads.
Input
Input is given from Standard Input in the following format:
N Q a_1 b_1 a_2 b_2 \hspace{0.6cm}\vdots a_{N-1} b_{N-1} c_1 d_1 c_2 d_2 \hspace{0.6cm}\vdots c_Q d_Q
Output
Print Q lines.
The i-th line (1 \leq i \leq Q) should contain Town
if Takahashi and Aoki will meet at a town in the i-th query, and Road
if they meet halfway along a road in that query.
Sample Input 1
4 1 1 2 2 3 2 4 1 2
Sample Output 1
Road
In the first and only query, Takahashi and Aoki simultaneously leave Town 1 and Town 2, respectively, and they will meet halfway along the 1-st road, so we should print Road
.
Sample Input 2
5 2 1 2 2 3 3 4 4 5 1 3 1 5
Sample Output 2
Town Town
In the first query, Takahashi and Aoki simultaneously leave Town 1 and Town 3, respectively, and they will meet at Town 2, so we should print Town
.
In the first query, Takahashi and Aoki simultaneously leave Town 1 and Town 5, respectively, and they will meet at Town 3, so we should print Town
.
Sample Input 3
9 9 2 3 5 6 4 8 8 9 4 5 3 4 1 9 3 7 7 9 2 5 2 6 4 6 2 4 5 8 7 8 3 6 5 6
Sample Output 3
Town Road Town Town Town Town Road Road Road
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
高橋辞書には N 個の単語が載っており、i\, (1 \leq i \leq N) 番目の単語は s_i です。
高橋君と青木君は高橋辞書を使って 3 しりとりをします。 3 しりとりのルールは以下です。
- 高橋君と青木君は、高橋君から始めて交互に単語を言い合っていく。
- 各プレーヤーは前の人が言った単語の最後の 3 文字で始まる単語を言わなければならない。例えば、前の人が
Takahashi
と言った場合、次の人はship
、shield
などを言うことができ、Aoki
、sing
、his
などを言うことはできない。 - 大文字と小文字は区別される。例えば、
Takahashi
のあとにShIp
を言うことはできない。 - 言う単語がなくなった方が負ける。
- 高橋辞書に載っていない単語を言うことはできない。
- 同じ単語は何度でも使ってよい。
各 i\, (1 \leq i \leq N) について、高橋君が 3 しりとりを単語 s_i から始めたときどちらが勝つかを判定してください。ただし、二人とも最善に行動するとします。具体的には、自分が負けないことを最優先し、その次に相手を負かすことを優先します。
制約
- N は 1 以上 2 \times 10^5 以下の整数
- s_i は英小文字と英大文字のみからなる長さ 3 以上 8 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
N s_1 s_2 \vdots s_N
出力
N 行出力せよ。i\, (1 \leq i \leq N) 行目には、高橋君が 3 しりとりを単語 s_i から始めたとき、高橋君が勝つなら Takahashi
、青木君が勝つなら Aoki
、しりとりが永遠に続き勝敗が決まらないなら Draw
と出力せよ。
入力例 1
3 abcd bcda ada
出力例 1
Aoki Takahashi Draw
高橋君が abcd
から始めたとき、次に青木君が bcda
と言って高橋君は言う単語がなくなります。よって青木君が勝つので Aoki
と出力してください。
高橋君が bcda
から始めたとき、次に青木君は言う単語がなくなります。よって高橋君が勝つので Takahashi
と出力してください。
高橋君が ada
から始めたとき、二人とも ada
を繰り返すのでしりとりが終わることはありません。よって Draw
と出力してください。同じ単語を何度でも使用できることに注意してください。
入力例 2
1 ABC
出力例 2
Draw
入力例 3
5 eaaaabaa eaaaacaa daaaaaaa eaaaadaa daaaafaa
出力例 3
Takahashi Takahashi Takahashi Aoki Takahashi
Score : 500 points
Problem Statement
The Takahashi Dictionary lists N words; the i-th word (1 \leq i \leq N) is s_i.
Using this dictionary, Takahashi and Aoki will play 3-shiritori, which goes as follows.
- Takahashi and Aoki alternately say words, with Takahashi going first.
- Each player must say a word beginning with the last three characters of the previous word. For example, if a player says
Takahashi
, the next player can sayship
orshield
along with other choices, but notAoki
,sing
, orhis
. - Uppercase and lowercase are distinguished. For example, a player cannot say
ShIp
followingTakahashi
. - A player who becomes unable to say a word loses.
- A player cannot say a word not listed in the dictionary.
- The same word can be used multiple times.
For each i (1 \leq i \leq N), determine who will win when Takahashi starts the game by saying the word s_i. Here, we assume that both players play optimally. More specifically, each player gives first priority to avoiding his loss and second priority to defeating the opponent.
Constraints
- N is an integer between 1 and 2 \times 10^5 (inclusive).
- s_i is a string of length between 3 and 8 (inclusive) consisting of lowercase and uppercase English letters.
Input
Input is given from Standard Input in the following format:
N s_1 s_2 \vdots s_N
Output
Print N lines. The i-th line (1 \leq i \leq N) should contain Takahashi
if Takahashi wins when Takahashi starts the game by saying the word s_i, Aoki
if Aoki wins in that scenario, and Draw
if the game continues forever with neither of them losing in that scenario.
Sample Input 1
3 abcd bcda ada
Sample Output 1
Aoki Takahashi Draw
When Takahashi starts the game by saying abcd
, Aoki will say bcda
next, and Takahashi will then have no word to say, resulting in Aoki's win. Thus, we should print Aoki
.
When Takahashi starts the game by saying bcda
, Aoki will have no word to say, resulting in Takahashi win. Thus, we should print Takahashi
.
When Takahashi starts the game by saying ada
, both players will repeat ada
and never end the game. Thus, we should print Draw
. Note that they can use the same word any number of times.
Sample Input 2
1 ABC
Sample Output 2
Draw
Sample Input 3
5 eaaaabaa eaaaacaa daaaaaaa eaaaadaa daaaafaa
Sample Output 3
Takahashi Takahashi Takahashi Aoki Takahashi
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 本の木が左右一列に並んでおり、左から i\, (1 \leq i \leq N) 本目の木 i の高さは H_i です。
あなたは、好きな順番でこれら N 本の木を全て伐採します。具体的には、 (1,2, \ldots, N) の並び替えによって得られるある順列 P について、i=1,2,3,...,N の順に、
- H_{P_i-1}+H_{P_i}+H_{P_i+1} のコストを支払った後、木 P_i を伐採する。すなわち、H_{P_i} を 0 にする。
という操作を行います。ただし、H_0=0,H_{N+1}=0 とします。
言い換えると、ある木を伐採するのにかかるコストは木を伐採する直前での、その木と両隣の木の高さの総和となります。
支払うコストの総和が最小となるような P の個数を求めてください。答えは非常に大きくなる可能性があるので、(10^9+7) で割った余りを出力してください。
制約
- 1 \leq N \leq 4000
- 1 \leq H_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N H_1 H_2 \ldots H_N
出力
支払うコストの総和が最小となるような P の個数を (10^9+7) で割った余りを出力せよ。
入力例 1
3 4 2 4
出力例 1
2
支払うコストの総和が最小となるような P は、(1,3,2) と (3,1,2) の 2 つです。以下、木の伐採の例を示します。
P=(1,3,2) のとき
- 最初に木 1 を伐採する。この時に支払うコストは H_0+H_1+H_2=6 である。
- 次に木 3 を伐採する。この時に支払うコストは H_2+H_3+H_4=6 である。
- 最後に木 2 を伐採する。この時に支払うコストは H_1+H_2+H_3=2 である。
支払うコストの総和は 14 となります。
入力例 2
3 100 100 100
出力例 2
6
入力例 3
15 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422 25202363 350490028 783368691 102520060 44897764
出力例 3
54537651
(10^9+7) で割った余りを出力することに注意してください。
Score : 600 points
Problem Statement
There are N trees standing in a row from left to right. The i-th tree (1 \leq i \leq N) from the left, Tree i, has the height of H_i.
You will now cut down all these N trees in some order you like. Formally, you will choose a permutation P of (1, 2, \ldots, N) and do the operation below for each i=1, 2, 3, ..., N in this order.
- Cut down Tree P_i, that is, set H_{P_i} to 0, at a cost of H_{P_i-1}+H_{P_i}+H_{P_i+1}.
Here, we assume H_0=0,H_{N+1}=0.
In other words, the cost of cutting down a tree is the total height of the tree and the neighboring trees just before doing so.
Find the number of permutations P that minimize the total cost of cutting down the trees. Since the count may be enormous, print it modulo (10^9+7).
Constraints
- 1 \leq N \leq 4000
- 1 \leq H_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N H_1 H_2 \ldots H_N
Output
Print the number of permutations P, modulo (10^9+7), that minimize the total cost of cutting down the trees.
Sample Input 1
3 4 2 4
Sample Output 1
2
There are two permutations P that minimize the total cost: (1,3,2) and (3,1,2).
Below, we will show the process of cutting down the trees for P=(1,3,2), for example.
- First, Tree 1 is cut down at a cost of H_0+H_1+H_2=6.
- Next, Tree 3 is cut down at a cost of H_2+H_3+H_4=6.
- Finally, Tree 2 is cut down at a cost of H_1+H_2+H_3=2.
The total cost incurred is 14.
Sample Input 2
3 100 100 100
Sample Output 2
6
Sample Input 3
15 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422 25202363 350490028 783368691 102520060 44897764
Sample Output 3
54537651
Be sure to print the count modulo (10^9+7).