実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
整数 A,B が与えられます。
以下の条件を満たす整数 x が何通りあるか求めてください。
- 条件：3 つの整数 A,B,x をうまく並べることで、等差数列を作ることができる。
なお、3 つの整数 p,q,r をこの順に並べた列が等差数列であるとは、q-p が r-q と一致することをいいます。
制約
- 1\leq A,B \leq 100
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
問題文中の条件を満たす整数 x が何通りあるかを出力せよ。 なお、答えは有限であることが証明できる。
入力例 1
5 7
出力例 1
3
以下のように、x=3,6,9 はいずれも条件を満たします。
- x=3 のとき、例えば x,A,B と並べることで等差数列 3,5,7 を作ることができます。
- x=6 のとき、例えば B,x,A と並べることで等差数列 7,6,5 を作ることができます。
- x=9 のとき、例えば A,B,x と並べることで等差数列 5,7,9 を作ることができます。
逆に、これ以外に条件を満たす x は存在しません。 よって答えは 3 です。
入力例 2
6 1
出力例 2
2
x=-4,11 のみが条件を満たします。
入力例 3
3 3
出力例 3
1
x=3 のみが条件を満たします。
Score : 100 points
Problem Statement
You are given two integers A and B.
How many integers x satisfy the following condition?
- Condition: It is possible to arrange the three integers A, B, and x in some order to form an arithmetic sequence.
A sequence of three integers p, q, and r in this order is an arithmetic sequence if and only if q-p is equal to r-q.
Constraints
- 1 \leq A,B \leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
A B
Output
Print the number of integers x that satisfy the condition in the problem statement. It can be proved that the answer is finite.
Sample Input 1
5 7
Sample Output 1
3
The integers x=3,6,9 all satisfy the condition as follows:
- When x=3, for example, arranging x,A,B forms the arithmetic sequence 3,5,7.
- When x=6, for example, arranging B,x,A forms the arithmetic sequence 7,6,5.
- When x=9, for example, arranging A,B,x forms the arithmetic sequence 5,7,9.
Conversely, there are no other values of x that satisfy the condition. Therefore, the answer is 3.
Sample Input 2
6 1
Sample Output 2
2
Only x=-4 and 11 satisfy the condition.
Sample Input 3
3 3
Sample Output 3
1
Only x=3 satisfies the condition.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
高橋君は AtCoder Land を目指しています。 目の前に看板が置かれているので、ここが AtCoder Land であるかどうか判定したいです。
文字列 S,T が空白区切りで与えられます。
S= AtCoder かつ T= Land であるかどうか判定してください。
制約
- S,T は英大小文字からなる長さ 1 以上 10 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
S= AtCoder かつ T= Land であるならば Yes を、そうでないならば No を出力せよ。
入力例 1
AtCoder Land
出力例 1
Yes
S= AtCoder かつ T= Land です。
入力例 2
CodeQUEEN Land
出力例 2
No
S= AtCoder ではありません。
入力例 3
aTcodeR lANd
出力例 3
No
大文字と小文字は区別します。
Score : 100 points
Problem Statement
Takahashi is heading to AtCoder Land. There is a signboard in front of him, and he wants to determine whether it says AtCoder Land.
You are given two strings S and T separated by a space.
Determine whether S= AtCoder and T= Land.
Constraints
- S and T are strings consisting of uppercase and lowercase English letters, with lengths between 1 and 10, inclusive.
Input
The input is given from Standard Input in the following format:
S T
Output
If S= AtCoder and T= Land, print Yes; otherwise, print No.
Sample Input 1
AtCoder Land
Sample Output 1
Yes
S= AtCoder and T= Land.
Sample Input 2
CodeQUEEN Land
Sample Output 2
No
S is not AtCoder.
Sample Input 3
aTcodeR lANd
Sample Output 3
No
Uppercase and lowercase letters are distinguished.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は英小文字からなる文字列 S をキーボードで入力しようとしました。
高橋君は画面を見ずにキーボードだけを見てタイピングをしていました。
誤って別の英小文字を入力してしまったときにはその直後にバックスペースキーを押しましたが、バックスペースキーが壊れていたため誤って入力された文字は消去されず、実際に入力された文字列は文字列 T となりました。
また、英小文字以外のキーを誤って押してしまうことはありませんでした。
T のうち高橋君が誤って入力した文字でないものを正しく入力された文字であると定めます。
正しく入力された文字が T の何文字目であるか答えてください。
制約
- S, T は長さ 1 以上 2 \times 10^5 以下の英小文字からなる文字列
- T は問題文中の手続きにより得られる文字列
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
S の長さを |S| として、正しく入力された文字が A_1, A_2, \ldots, A_{|S|} 文字目であるとき A_1, A_2, \ldots, A_{|S|} の値をこの順に空白区切りで出力せよ。
ただし、出力は昇順になるようにせよ。すなわち、各 1 \leq i \leq |S| - 1 に対して A_i < A_{i + 1} を満たすようにせよ。
入力例 1
abc axbxyc
出力例 1
1 3 6
高橋君のタイピングの一連の流れは以下のようになります。
aを入力する。bを入力しようとするが、誤ってxを入力してしまう。- バックスペースキーを押すが、文字の削除は行われない。
bを入力する。cを入力しようとするが、誤ってxを入力してしまう。- バックスペースキーを押すが、文字の削除は行われない。
cを入力しようとするが、誤ってyを入力してしまう。- バックスペースキーを押すが、文字の削除は行われない。
cを入力する。
正しく入力された文字は 1, 3, 6 文字目です。
入力例 2
aaaa bbbbaaaa
出力例 2
5 6 7 8
入力例 3
atcoder atcoder
出力例 3
1 2 3 4 5 6 7
高橋君が誤った文字を入力することはありませんでした。
Score: 200 points
Problem Statement
Takahashi tried to type a string S consisting of lowercase English letters using a keyboard.
He was typing while looking only at the keyboard, not the screen.
Whenever he mistakenly typed a different lowercase English letter, he immediately pressed the backspace key. However, the backspace key was broken, so the mistakenly typed letter was not deleted, and the actual string typed was T.
He did not mistakenly press any keys other than those for lowercase English letters.
The characters in T that were not mistakenly typed are called correctly typed characters.
Determine the positions in T of the correctly typed characters.
Constraints
- S and T are strings of lowercase English letters with lengths between 1 and 2 \times 10^5, inclusive.
- T is a string obtained by the procedure described in the problem statement.
Input
The input is given from Standard Input in the following format:
S T
Output
Let |S| be the length of S. If the correctly typed characters are the A_1-th, A_2-th, \ldots, A_{|S|}-th characters of T, print the values of A_1, A_2, \ldots, A_{|S|} in this order, separated by spaces.
Ensure that the output is in ascending order. That is, A_i < A_{i + 1} should hold for each 1 \leq i \leq |S| - 1.
Sample Input 1
abc axbxyc
Sample Output 1
1 3 6
The sequence of Takahashi's typing is as follows:
- Type
a. - Try to type
bbut mistakenly typex. - Press the backspace key, but the character is not deleted.
- Type
b. - Try to type
cbut mistakenly typex. - Press the backspace key, but the character is not deleted.
- Try to type
cbut mistakenly typey. - Press the backspace key, but the character is not deleted.
- Type
c.
The correctly typed characters are the first, third, and sixth characters.
Sample Input 2
aaaa bbbbaaaa
Sample Output 2
5 6 7 8
Sample Input 3
atcoder atcoder
Sample Output 3
1 2 3 4 5 6 7
Takahashi did not mistakenly type any characters.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
1,2,\ldots,N と番号づけられた N 人が M 回、一列に並んで集合写真を撮りました。i 番目の撮影で左から j 番目に並んだ人の番号は a_{i,j} です。
ある二人組は M 回の撮影で一度も連続して並ばなかった場合、不仲である可能性があります。
不仲である可能性がある二人組の個数を求めてください。なお、人 x と人 y からなる二人組と人 y と人 x からなる二人組は区別しません。
制約
- 2 \leq N \leq 50
- 1 \leq M \leq 50
- 1 \leq a_{i,j} \leq N
- a_{i,1},\ldots,a_{i,N} には 1,\ldots,N が 1 回ずつ現れる
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M
a_{1,1} \ldots a_{1,N}
\vdots
a_{M,1} \ldots a_{M,N}
出力
答えを出力せよ。
入力例 1
4 2 1 2 3 4 4 3 1 2
出力例 1
2
人 1 と人 4 からなる二人組と、人 2 と人 4 からなる二人組がそれぞれ不仲である可能性があります。
入力例 2
3 3 1 2 3 3 1 2 1 2 3
出力例 2
0
入力例 3
10 10 4 10 7 2 8 3 9 1 6 5 3 6 2 9 1 8 10 7 4 5 9 3 4 5 7 10 1 8 2 6 7 3 1 8 4 9 5 6 2 10 5 2 1 4 10 7 9 8 3 6 5 8 1 6 9 3 2 4 7 10 8 10 3 4 5 7 2 9 6 1 3 10 2 7 8 5 1 4 9 6 10 6 1 5 4 2 3 8 9 7 4 5 9 1 8 2 7 6 3 10
出力例 3
6
Score : 200 points
Problem Statement
N people numbered 1,2,\ldots,N were in M photos. In each of the photos, they stood in a single line. In the i-th photo, the j-th person from the left is person a_{i,j}.
Two people who did not stand next to each other in any of the photos may be in a bad mood.
How many pairs of people may be in a bad mood? Here, we do not distinguish a pair of person x and person y, and a pair of person y and person x.
Constraints
- 2 \leq N \leq 50
- 1 \leq M \leq 50
- 1 \leq a_{i,j} \leq N
- a_{i,1},\ldots,a_{i,N} contain each of 1,\ldots,N exactly once.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M
a_{1,1} \ldots a_{1,N}
\vdots
a_{M,1} \ldots a_{M,N}
Output
Print the answer.
Sample Input 1
4 2 1 2 3 4 4 3 1 2
Sample Output 1
2
The pair of person 1 and person 4, and the pair of person 2 and person 4, may be in a bad mood.
Sample Input 2
3 3 1 2 3 3 1 2 1 2 3
Sample Output 2
0
Sample Input 3
10 10 4 10 7 2 8 3 9 1 6 5 3 6 2 9 1 8 10 7 4 5 9 3 4 5 7 10 1 8 2 6 7 3 1 8 4 9 5 6 2 10 5 2 1 4 10 7 9 8 3 6 5 8 1 6 9 3 2 4 7 10 8 10 3 4 5 7 2 9 6 1 3 10 2 7 8 5 1 4 9 6 10 6 1 5 4 2 3 8 9 7 4 5 9 1 8 2 7 6 3 10
Sample Output 3
6
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
正の整数 N が与えられます。
A\leq B\leq C かつ ABC\leq N であるような正の整数の組 (A,B,C) の個数を求めてください。
なお、制約の条件下で答えは 2^{63} 未満であることが保証されます。
制約
- 1 \leq N \leq 10^{11}
- N は整数である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
4
出力例 1
5
条件を満たす組は (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2) の 5 つです。
入力例 2
100
出力例 2
323
入力例 3
100000000000
出力例 3
5745290566750
Score : 300 points
Problem Statement
You are given a positive integer N.
Find the number of triples of positive integers (A, B, C) such that A\leq B\leq C and ABC\leq N.
The Constraints guarantee that the answer is less than 2^{63}.
Constraints
- 1 \leq N \leq 10^{11}
- N is an integer.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
4
Sample Output 1
5
There are five such triples: (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2).
Sample Input 2
100
Sample Output 2
323
Sample Input 3
100000000000
Sample Output 3
5745290566750