Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
文字列 S が文字列 T の部分文字列であるとは、次の条件を満たすような整数 i, j (1 \leq i \leq j \leq |T|) が存在することを言います。
- T の i 文字目から j 文字目までを順番を変えずに抜き出してできる文字列が S と一致する。
文字列 T を oxx を 10^5 個結合した文字列として定めます。
文字列 S が与えられるので、 S が T の部分文字列である場合は Yes を、そうでない場合は No を出力してください。
制約
- S は
oとxのみからなる文字列である。 - S の長さは 1 以上 10 以下である。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S が条件を満たす場合は Yes を、そうでない場合は No を出力せよ。
入力例 1
xoxxoxxo
出力例 1
Yes
T のはじめの方を抜き出すと oxxoxxoxxoxx... となっています。
T の 3 文字目から 10 文字目までを抜き出した文字列は S と一致するので、 S は T の部分文字列です。よって Yes を出力します。
入力例 2
xxoxxoxo
出力例 2
No
T から文字列をどのように抜き出しても S と一致しないので、S は T の部分文字列でありません。よって No を出力します。
入力例 3
ox
出力例 3
Yes
Score : 200 points
Problem Statement
A string S is said to be a substring of a string T when there is a pair of integers i and j (1 \leq i \leq j \leq |T|) that satisfy the following condition.
- The extraction of the i-th through j-th characters of T without changing the order equals S.
Let T be the concatenation of 10^5 copies of oxx.
Given a string S, print Yes if S is a substring of T, and No otherwise.
Constraints
- S is a string consisting of
oandx. - The length of S is between 1 and 10 (inclusive).
Input
Input is given from Standard Input in the following format:
S
Output
If S satisfies the condition, print Yes; otherwise, print No.
Sample Input 1
xoxxoxxo
Sample Output 1
Yes
T begins like this: oxxoxxoxxoxx...
Since the extraction of 3-rd through 10-th characters of T equals S, S is a substring of T, so Yes should be printed.
Sample Input 2
xxoxxoxo
Sample Output 2
No
Since there is no way to extract from T a string that equals S, S is not a substring of T, so No should be printed.
Sample Input 3
ox
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
数直線の原点に高橋君がいます。高橋君は座標 X にあるゴールに移動しようとしています。
座標 Y には壁があり、最初、高橋君は壁を超えて移動することができません。
座標 Z にあるハンマーを拾った後でなら、壁を破壊して通過できるようになります。
高橋君がゴールに到達することが可能か判定し、可能であれば移動距離の最小値を求めてください。
制約
- -1000 \leq X,Y,Z \leq 1000
- X,Y,Z は相異なり、いずれも 0 でない
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
X Y Z
出力
高橋君がゴールに到達することが可能であれば、移動距離の最小値を出力せよ。不可能であれば、かわりに -1 と出力せよ。
入力例 1
10 -10 1
出力例 1
10
高橋君はまっすぐゴールに向かうことができます。
入力例 2
20 10 -10
出力例 2
40
ゴールは壁の向こう側にあります。まずハンマーを拾い、壁を壊すことでゴールに到達することができます。
入力例 3
100 1 1000
出力例 3
-1
Score : 200 points
Problem Statement
Takahashi is at the origin of a number line. He wants to reach a goal at coordinate X.
There is a wall at coordinate Y, which Takahashi cannot go beyond at first.
However, after picking up a hammer at coordinate Z, he can destroy that wall and pass through.
Determine whether Takahashi can reach the goal. If he can, find the minimum total distance he needs to travel to do so.
Constraints
- -1000 \leq X,Y,Z \leq 1000
- X, Y, and Z are distinct, and none of them is 0.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
X Y Z
Output
If Takahashi can reach the goal, print the minimum total distance he needs to travel to do so. If he cannot, print -1 instead.
Sample Input 1
10 -10 1
Sample Output 1
10
Takahashi can go straight to the goal.
Sample Input 2
20 10 -10
Sample Output 2
40
The goal is beyond the wall. He can get there by first picking up the hammer and then destroying the wall.
Sample Input 3
100 1 1000
Sample Output 3
-1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1, 2, \dots, N の番号が、辺には 1, 2, \dots, M の番号が付けられています。
辺 i \, (i = 1, 2, \dots, M) は頂点 u_i, v_i を結んでいます。
このグラフがパスグラフであるか判定してください。
単純無向グラフとは
単純無向グラフとは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいいます。
パスグラフとは
頂点に 1, 2, \dots, N の番号が付けられたN 頂点のグラフがパスグラフであるとは、(1, 2, \dots, N) を並べ変えて得られる数列 (v_1, v_2, \dots, v_N) であって、以下の条件を満たすものが存在することをいいます。
制約
- 2 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
- 入力される値は全て整数
- 入力で与えられるグラフは単純
入力
入力は以下の形式で標準入力から与えられる。
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
出力
与えられたグラフがパスグラフなら Yes、そうでないなら No と出力せよ。
入力例 1
4 3 1 3 4 2 3 2
出力例 1
Yes
与えらえたグラフは下図のようであり、これはパスグラフです。
入力例 2
2 0
出力例 2
No
与えらえたグラフは下図のようであり、これはパスグラフではありません。
入力例 3
5 5 1 2 2 3 3 4 4 5 5 1
出力例 3
No
与えらえたグラフは下図のようであり、これはパスグラフではありません。
Score : 300 points
Problem Statement
You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, 2, \dots, N, and the edges are numbered 1, 2, \dots, M.
Edge i \, (i = 1, 2, \dots, M) connects vertices u_i and v_i.
Determine if this graph is a path graph.
What is a simple undirected graph?
A simple undirected graph is a graph without self-loops or multiple edges whose edges do not have a direction.
What is a path graph?
A graph with N vertices numbered 1, 2, \dots, N is said to be a path graph if and only if there is a sequence (v_1, v_2, \dots, v_N) that is a permutation of (1, 2, \dots, N) and satisfies the following conditions:
Constraints
- 2 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
- All values in the input are integers.
- The graph given in the input is simple.
Input
The input is given from Standard Input in the following format:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
Output
Print Yes if the given graph is a path graph; print No otherwise.
Sample Input 1
4 3 1 3 4 2 3 2
Sample Output 1
Yes
Illustrated below is the given graph, which is a path graph.
Sample Input 2
2 0
Sample Output 2
No
Illustrated below is the given graph, which is not a path graph.
Sample Input 3
5 5 1 2 2 3 3 4 4 5 5 1
Sample Output 3
No
Illustrated below is the given graph, which is not a path graph.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 個の袋があります。
袋 i には L_i 個のボールが入っていて、袋 i の j(1\leq j\leq L_i) 番目のボールには正の整数 a_{i,j} が書かれています。
それぞれの袋から 1 つずつボールを取り出します。
取り出したボールに書かれた数の総積が X になるような取り出し方は何通りありますか？
ただし、書かれた数が同じであっても全てのボールは区別します。
制約
- N \geq 2
- L_i \geq 2
- 袋に入っているボールの個数の総積は 10^5 を超えない。すなわち、\displaystyle\prod_{i=1}^{N}L_i \leq 10^5
- 1 \leq a_{i,j} \leq 10^9
- 1 \leq X \leq 10^{18}
- 入力に含まれる値は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N X
L_1 a_{1,1} a_{1,2} \ldots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \ldots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \ldots a_{N,L_N}
出力
答えを出力せよ。
入力例 1
2 40 3 1 8 4 2 10 5
出力例 1
2
袋 1 の 3 番目のボールと袋 2 の 1 番目のボールを選ぶと、a_{1,3} \times a_{2,1} = 4 \times 10 = 40 となります。
袋 1 の 2 番目のボールと袋 2 の 2 番目のボールを選ぶと、a_{1,2} \times a_{2,2} = 8 \times 5 = 40 となります。
これ以外に総積が 40 になる取り出し方は存在しないので、答えは 2 です。
入力例 2
3 200 3 10 10 10 3 10 10 10 5 2 2 2 2 2
出力例 2
45
書かれた数が同じであっても全てのボールは区別することに注意してください。
入力例 3
3 1000000000000000000 2 1000000000 1000000000 2 1000000000 1000000000 2 1000000000 1000000000
出力例 3
0
総積が X になる取り出し方が 1 つも存在しないこともあります。
Score : 300 points
Problem Statement
We have N bags.
Bag i contains L_i balls. The j-th ball (1\leq j\leq L_i) in Bag i has a positive integer a_{i,j} written on it.
We will pick out one ball from each bag.
How many ways are there to pick the balls so that the product of the numbers written on the picked balls is X?
Here, we distinguish all balls, even with the same numbers written on them.
Constraints
- N \geq 2
- L_i \geq 2
- The product of the numbers of balls in the bags is at most 10^5: \displaystyle\prod_{i=1}^{N}L_i \leq 10^5.
- 1 \leq a_{i,j} \leq 10^9
- 1 \leq X \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X
L_1 a_{1,1} a_{1,2} \ldots a_{1,L_1}
L_2 a_{2,1} a_{2,2} \ldots a_{2,L_2}
\vdots
L_N a_{N,1} a_{N,2} \ldots a_{N,L_N}
Output
Print the answer.
Sample Input 1
2 40 3 1 8 4 2 10 5
Sample Output 1
2
When choosing the 3-rd ball in Bag 1 and 1-st ball in Bag 2, we have a_{1,3} \times a_{2,1} = 4 \times 10 = 40.
When choosing the 2-nd ball in Bag 1 and 2-nd ball in Bag 2, we have a_{1,2} \times a_{2,2} = 8 \times 5 = 40.
There are no other ways to make the product 40, so the answer is 2.
Sample Input 2
3 200 3 10 10 10 3 10 10 10 5 2 2 2 2 2
Sample Output 2
45
Note that we distinguish all balls, even with the same numbers written on them.
Sample Input 3
3 1000000000000000000 2 1000000000 1000000000 2 1000000000 1000000000 2 1000000000 1000000000
Sample Output 3
0
There may be no way to make the product X.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
0, 1, ? からなる文字列 S および整数 N が与えられます。
S に含まれる ? をそれぞれ 0 または 1 に置き換えて 2 進整数とみなしたときに得られる値の集合を T とします。
たとえば、S= ?0? のとき、
T=\lbrace 000_{(2)},001_{(2)},100_{(2)},101_{(2)}\rbrace=\lbrace 0,1,4,5\rbrace です。
T に含まれる N 以下の値のうち最大のものを (10 進整数として) 出力してください。
N 以下の値が T に含まれない場合は、代わりに -1 を出力してください。
制約
- S は
0,1,?からなる文字列 - S の長さは 1 以上 60 以下
- 1\leq N \leq 10^{18}
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
S N
出力
答えを出力せよ。
入力例 1
?0? 2
出力例 1
1
問題文中で例示したとおり、T=\lbrace 0,1,4,5\rbrace です。 T に含まれる N 以下の値は 0 と 1 なので、そのうちの最大である 1 を出力します。
入力例 2
101 4
出力例 2
-1
T=\lbrace 5\rbrace であるため、N 以下の値は T に含まれません。
入力例 3
?0? 1000000000000000000
出力例 3
5
Score : 400 points
Problem Statement
You are given an integer N and a string S consisting of 0, 1, and ?.
Let T be the set of values that can be obtained by replacing each ? in S with 0 or 1 and interpreting the result as a binary integer.
For instance, if S= ?0?, we have T=\lbrace 000_{(2)},001_{(2)},100_{(2)},101_{(2)}\rbrace=\lbrace 0,1,4,5\rbrace.
Print (as a decimal integer) the greatest value in T less than or equal to N.
If T does not contain a value less than or equal to N, print -1 instead.
Constraints
- S is a string consisting of
0,1, and?. - The length of S is between 1 and 60, inclusive.
- 1\leq N \leq 10^{18}
- N is an integer.
Input
The input is given from Standard Input in the following format:
S N
Output
Print the answer.
Sample Input 1
?0? 2
Sample Output 1
1
As shown in the problem statement, T=\lbrace 0,1,4,5\rbrace. Among them, 0 and 1 are less than or equal to N, so you should print the greatest of them, 1.
Sample Input 2
101 4
Sample Output 2
-1
We have T=\lbrace 5\rbrace, which does not contain a value less than or equal to N.
Sample Input 3
?0? 1000000000000000000
Sample Output 3
5