Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
数字のみからなる、長さがちょうど 9 の文字列 S が与えられます。
S には 0 から 9 までのうち、ちょうど 1 つの数字を除いた 9 種類の数字が一度ずつ登場します。
S に登場しない唯一の数字を出力してください。
制約
- S は数字のみからなる長さ 9 の文字列である。
- S の文字はすべて相異なる。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S に登場しない唯一の数字を出力せよ。
入力例 1
023456789
出力例 1
1
文字列 023456789 には 1 のみが登場していません。
よって、1 を出力します。
入力例 2
459230781
出力例 2
6
文字列 459230781 には 6 のみが登場していません。
よって、6 を出力します。
文字列に数字が現れる順番は昇順とは限らないので注意してください。
Score : 100 points
Problem Statement
You are given a string S of length exactly 9 consisting of digits.
One but all digits from 0 to 9 appear exactly once in S.
Print the only digit missing in S.
Constraints
- S is a string of length 9 consisting of digits.
- All characters in S are distinct.
Input
Input is given from Standard Input in the following format:
S
Output
Print the only digit missing in S.
Sample Input 1
023456789
Sample Output 1
1
The string 023456789 only lacks 1.
Thus, 1 should be printed.
Sample Input 2
459230781
Sample Output 2
6
The string 459230781 only lacks 6.
Thus, 6 should be printed.
Note that the digits in the string may not appear in increasing order.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
v と w のみからなる文字列 S が与えられます。
S の中に、下に尖っている部分が何箇所あるかを出力してください（入出力例にある図もご参照ください）。
制約
- S は
vとwのみからなる文字列 - S の長さは 1 以上 100 以下
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを整数として出力せよ。
入力例 1
vvwvw
出力例 1
7
上の画像のように、vvwvw という文字列には下に尖った部分が 7 箇所あります。
入力例 2
v
出力例 2
1
入力例 3
wwwvvvvvv
出力例 3
12
Score : 100 points
Problem Statement
You are given a string S consisting of v and w.
Print the number of "bottoms" in the string S (see the figure at Sample Input/Output).
Constraints
- S is a string consisting of
vandw. - The length of S is between 1 and 100, inclusive.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer as an integer.
Sample Input 1
vvwvw
Sample Output 1
7
The image above shows the seven "bottoms" in the string vvwvw.
Sample Input 2
v
Sample Output 2
1
Sample Input 3
wwwvvvvvv
Sample Output 3
12
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
英小文字からなる文字列 S が与えられます。S の空でない部分文字列は何種類ありますか？
ただし、部分文字列とは連続する部分列のことを指します。例えば、xxx は yxxxy の部分文字列ですが、xxyxx の部分文字列ではありません。
制約
- S は英小文字からなる長さ 1 以上 100 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
yay
出力例 1
5
S の空でない部分文字列は以下の 5 種類です。
ayayyayay
入力例 2
aababc
出力例 2
17
入力例 3
abracadabra
出力例 3
54
Score: 200 points
Problem Statement
You are given a string S consisting of lowercase English letters. How many different non-empty substrings does S have?
A substring is a contiguous subsequence. For example, xxx is a substring of yxxxy but not of xxyxx.
Constraints
- S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
yay
Sample Output 1
5
S has the following five different non-empty substrings:
ayayyayay
Sample Input 2
aababc
Sample Output 2
17
Sample Input 3
abracadabra
Sample Output 3
54
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
高橋君の家には N 本の麺からなるパスタがあり、i 本目の麺の長さは A_i です。
高橋君はこれから M 日間の食事計画を立てており、
i 日目にはパスタの麺のうち長さがちょうど B_i であるようなものを 1 本選び、食べようと考えています。
もし、1 日目から M 日目の間に 1 日でもそのような麺が無い日があれば、食事計画は失敗となります。
また、同じ麺を複数の日に食べることはできません。
高橋君が食事計画を最後まで実行することは可能ですか？
制約
- 1 \leq M \leq N \leq 1000
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
出力
高橋君が食事計画を最後まで実行できる場合は Yes を、そうでない場合は No を出力せよ。
入力例 1
3 2 1 1 3 3 1
出力例 1
Yes
1 日目に 3 本目の麺を、2 日目に 1 本目の麺を食べれば良いので、高橋君の食事計画は実行可能です。
入力例 2
1 1 1000000000 1
出力例 2
No
長さがちょうど 1 の麺が存在する必要があります。
入力例 3
5 2 1 2 3 4 5 5 5
出力例 3
No
長さが 5 の麺は 1 本しか存在しないため、2 日目に食事をとる事が出来ません。
Score : 200 points
Problem Statement
There is pasta consisting of N noodles at Takahashi's home. The length of the i-th noodle is A_i.
Takahashi has a meal plan for the next M days.
On the i-th day, he is going to choose a pasta noodle of length exactly B_i and eat it.
If no such noodle is available on any day, his plan fails.
Additionally, he cannot eat the same noodle on multiple days.
Can Takahashi accomplish his meal plan?
Constraints
- 1 \leq M \leq N \leq 1000
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
Output
If Takahashi can accomplish his meal plan, print Yes; otherwise, print No.
Sample Input 1
3 2 1 1 3 3 1
Sample Output 1
Yes
He can eat the 3-rd noodle on the 1-st day and the 1-st noodle on the 2-nd day, so his meal plan is feasible.
Sample Input 2
1 1 1000000000 1
Sample Output 2
No
A noodle of length exactly 1 is needed.
Sample Input 3
5 2 1 2 3 4 5 5 5
Sample Output 3
No
Since there are only 1 noodle of length 5, he cannot have a meal on the 2-nd day.
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は全 10^9 巻の漫画『すぬけ君』を読むことにしました。
初め、高橋君は『すぬけ君』の単行本を N 冊持っています。i 番目の単行本は a_i 巻です。
高橋君は『すぬけ君』を読み始める前に限り次の操作を 0 回以上何度でも繰り返せます。
- 現在持っている単行本が 1 冊以下の場合、何もしない。そうでない場合、現在持っている単行本から 2 冊を選んで売り、代わりに好きな巻を選んで 1 冊買う
その後、高橋君は『すぬけ君』を 1 巻、2 巻、3 巻、\ldots と順番に読みます。ただし、次に読むべき巻を持っていない状態になった場合、(他の巻を持っているかどうかに関わらず)その時点で『すぬけ君』を読むのをやめます。
高橋君が『すぬけ君』を最大で何巻まで読めるかを求めてください。ただし、1 巻を読めない場合の答えは 0 とします。
制約
- 1 \leq N \leq 3 \times 10^5
- 1 \leq a_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N a_1 \ldots a_N
出力
答えを出力せよ。
入力例 1
6 1 2 4 6 7 271
出力例 1
4
『すぬけ君』を読み始める前に「7 巻と 271 巻を選んで売り、代わりに 3 巻を選んで 1 冊買う」という内容で操作をすると、高橋君は 1 巻、2 巻、3 巻、4 巻、6 巻を 1 冊ずつ持っている状態になります。
この状態から『すぬけ君』を読み始めると、高橋君は 1 巻、2 巻、3 巻、4 巻を読み、続いて 5 巻を読もうとしますが持っていないためこの時点で『すぬけ君』を読むのをやめます。
操作の方法を変えても 5 巻を読むことは出来ないため、4 が答えです。
入力例 2
10 1 1 1 1 1 1 1 1 1 1
出力例 2
5
高橋君は同じ巻を 2 冊以上持っているかもしれません。
この入力に対しては以下のように 4 回操作をしてから『すぬけ君』を読み始めることで 5 巻まで読むことが出来、これが最大です。
- 1 巻を 2 冊選んで売り、代わりに 2 巻を選んで 1 冊買う
- 1 巻を 2 冊選んで売り、代わりに 3 巻を選んで 1 冊買う
- 1 巻を 2 冊選んで売り、代わりに 4 巻を選んで 1 冊買う
- 1 巻を 2 冊選んで売り、代わりに 5 巻を選んで 1 冊買う
入力例 3
1 5
出力例 3
0
高橋君は 1 巻を読めません。
Score : 300 points
Problem Statement
Takahashi is going to read a manga series "Snuke-kun" in 10^9 volumes.
Initially, Takahashi has N books of this series. The i-th book is Volume a_i.
Takahashi may repeat the following operation any number of (possibly zero) times only before he begins to read:
- Do nothing if he has 1 or less books; otherwise, sell two of the books he has and buy one book of any volume instead.
Then, Takahashi reads Volume 1, Volume 2, Volume 3, \ldots, in order. However, when he does not have a book of the next volume to read, he stops reading the series (regardless of the other volumes he has).
Find the latest volume of the series that he can read up to. If he cannot read any, let the answer be 0.
Constraints
- 1 \leq N \leq 3 \times 10^5
- 1 \leq a_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N a_1 \ldots a_N
Output
Print the answer.
Sample Input 1
6 1 2 4 6 7 271
Sample Output 1
4
Before he begins to read the series, he may do the following operation: "sell books of Volumes 7 and 271 and buy one book of Volume 3 instead." Then, he has one book each of Volumes 1, 2, 3, 4, and 6.
If he then begins to read the series, he reads Volumes 1, 2, 3, and 4, then tries to read Volume 5. However, he does not have one, so he stops reading at this point.
Regardless of the choices in the operation, he cannot read Volume 5, so the answer is 4.
Sample Input 2
10 1 1 1 1 1 1 1 1 1 1
Sample Output 2
5
Takahashi may have multiple books of the same volume.
For this input, if he performs the following 4 operations before he begins to read the series, he can read up to Volume 5, which is the maximum:
- Sell two books of Volume 1 and buy a book of Volume 2 instead.
- Sell two books of Volume 1 and buy a book of Volume 3 instead.
- Sell two books of Volume 1 and buy a book of Volume 4 instead.
- Sell two books of Volume 1 and buy a book of Volume 5 instead.
Sample Input 3
1 5
Sample Output 3
0
Takahashi cannot read Volume 1.