実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
高橋君のケーキが誰かに食べられてしまいました。ケーキを食べた犯人の候補として、人 1、人 2、人 3 の三人が挙げられています。
犯人の目撃者はりんごさんとすぬけくんの二人がいます。りんごさんは人 A が犯人でないことを覚えており、すぬけくんは人 B が犯人でないことを覚えています。
二人の記憶から犯人を一人に特定できるかどうか判定し、特定できるならばその人の番号を出力してください。
制約
- 1\leq A,B\leq 3
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
二人の記憶から犯人を一人に特定できるならばその人の番号を出力し、特定できないならば -1 を出力せよ。
入力例 1
1 2
出力例 1
3
二人の記憶から、人 3 が犯人であることが特定できます。
入力例 2
1 1
出力例 2
-1
二人の記憶からでは、人 2,3 のどちらが犯人か特定することができません。よって -1 を出力します。
入力例 3
3 1
出力例 3
2
Score : 100 points
Problem Statement
Takahashi's cake has been eaten by someone. There are three suspects: person 1, person 2, and person 3.
There are two witnesses, Ringo and Snuke. Ringo remembers that person A is not the culprit, and Snuke remembers that person B is not the culprit.
Determine if the culprit can be uniquely identified based on the memories of the two witnesses. If the culprit can be identified, print the person's number.
Constraints
- 1 \leq A, B \leq 3
- All input values are integers.
Input
The input is given from Standard Input in the following format:
A B
Output
If the culprit can be uniquely identified based on the memories of the two witnesses, print the person's number; otherwise, print -1.
Sample Input 1
1 2
Sample Output 1
3
From the memories of the two witnesses, it can be determined that person 3 is the culprit.
Sample Input 2
1 1
Sample Output 2
-1
From the memories of the two witnesses, it cannot be determined whether person 2 or person 3 is the culprit. Therefore, print -1.
Sample Input 3
3 1
Sample Output 3
2
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
初項が A、末項が B、公差が D であるような等差数列を出力してください。
なお、そのような等差数列が存在する入力のみが与えられます。
制約
- 1 \leq A \leq B \leq 100
- 1\leq D \leq 100
- 初項が A、末項が B、公差が D であるような等差数列が存在する
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
A B D
出力
初項が A、末項が B、公差が D であるような等差数列の項を順に空白区切りで出力せよ。
入力例 1
3 9 2
出力例 1
3 5 7 9
初項が 3、末項が 9、公差が 2 であるような等差数列は (3,5,7,9) です。
入力例 2
10 10 1
出力例 2
10
初項が 10、末項が 10、公差が 1 であるような等差数列は (10) です。
Score: 100 points
Problem Statement
Print an arithmetic sequence with first term A, last term B, and common difference D.
You are only given inputs for which such an arithmetic sequence exists.
Constraints
- 1 \leq A \leq B \leq 100
- 1 \leq D \leq 100
- There is an arithmetic sequence with first term A, last term B, and common difference D.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
A B D
Output
Print the terms of the arithmetic sequence with first term A, last term B, and common difference D, in order, separated by spaces.
Sample Input 1
3 9 2
Sample Output 1
3 5 7 9
The arithmetic sequence with first term 3, last term 9, and common difference 2 is (3,5,7,9).
Sample Input 2
10 10 1
Sample Output 2
10
The arithmetic sequence with first term 10, last term 10, and common difference 1 is (10).
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 250 点
問題文
あなたは3Dゲームの当たり判定を実装しようとしています。
3 次元空間内の直方体であって、2 点 (a,b,c),(d,e,f) を結ぶ線分を対角線とし、全ての面が xy 平面、yz 平面、zx 平面のいずれかに平行なものを C(a,b,c,d,e,f) と表します。
（この定義により C(a,b,c,d,e,f) は一意に定まります）
2 つの直方体 C(a,b,c,d,e,f) と C(g,h,i,j,k,l) が与えられるので、これらの共通部分の体積が正かどうか判定してください。
制約
- 0 \leq a < d \leq 1000
- 0 \leq b < e \leq 1000
- 0 \leq c < f \leq 1000
- 0 \leq g < j \leq 1000
- 0 \leq h < k \leq 1000
- 0 \leq i < l \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
a b c d e f g h i j k l
出力
2 つの直方体の共通部分の体積が正なら Yes、そうでなければ No を出力せよ。
入力例 1
0 0 0 4 5 6 2 3 4 5 6 7
出力例 1
Yes
2 つの直方体の位置関係は下図のようになっており、共通部分の体積は 8 です。
入力例 2
0 0 0 2 2 2 0 0 2 2 2 4
出力例 2
No
2 つの直方体は面で接していますが、共通部分の体積は 0 です。
入力例 3
0 0 0 1000 1000 1000 10 10 10 100 100 100
出力例 3
Yes
Score : 250 points
Problem Statement
You are trying to implement collision detection in a 3D game.
In a 3-dimensional space, let C(a,b,c,d,e,f) denote the cuboid with a diagonal connecting (a,b,c) and (d,e,f), and with all faces parallel to the xy-plane, yz-plane, or zx-plane.
(This definition uniquely determines C(a,b,c,d,e,f).)
Given two cuboids C(a,b,c,d,e,f) and C(g,h,i,j,k,l), determine whether their intersection has a positive volume.
Constraints
- 0 \leq a < d \leq 1000
- 0 \leq b < e \leq 1000
- 0 \leq c < f \leq 1000
- 0 \leq g < j \leq 1000
- 0 \leq h < k \leq 1000
- 0 \leq i < l \leq 1000
- All input values are integers.
Input
The input is given from Standard Input in the following format:
a b c d e f g h i j k l
Output
Print Yes if the intersection of the two cuboids has a positive volume, and No otherwise.
Sample Input 1
0 0 0 4 5 6 2 3 4 5 6 7
Sample Output 1
Yes
The positional relationship of the two cuboids is shown in the figure below, and their intersection has a volume of 8.
Sample Input 2
0 0 0 2 2 2 0 0 2 2 2 4
Sample Output 2
No
The two cuboids touch at a face, where the volume of the intersection is 0.
Sample Input 3
0 0 0 1000 1000 1000 10 10 10 100 100 100
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
英小文字からなる長さ N の文字列 S が与えられます。
長さ K の文字列 t の出現回数を、以下を満たす整数 i の個数として定義します。
- 1 \leq i \leq N-K+1
- S の i 文字目から i+K-1 文字目までからなる部分文字列が t に一致する。
長さ K の文字列に対する出現回数の最大値 x を求めてください。 また、出現回数が x となるような長さ K の文字列をすべて辞書順昇順に出力してください。
制約
- N, K は整数
- S は英小文字からなる長さ N の文字列
- 1 \leq K \leq N \leq 100
入力
入力は以下の形式で標準入力から与えられる。
N K S
出力
2 行出力せよ。
1 行目には、長さ K の文字列に対する出現回数の最大値 x を出力せよ。
2 行目には、出現回数が x となるような長さ K の文字列を辞書順昇順に、空白区切りで出力せよ。
入力例 1
9 3 ovowowovo
出力例 1
2 ovo owo
出現回数 2 の文字列として、以下が挙げられます。
- 文字列
ovoについて、i=1,7 が条件を満たすことから、ovoの出現回数は 2 です。 - 文字列
owoについて、i=3,5 が条件を満たすことから、owoの出現回数は 2 です。
出現回数が 2 よりも大きいような長さ 3 の文字列は存在しないので、求める最大値は 2 です。
一方で、出現回数が 2 よりも小さい文字列として、以下が挙げられます。
- 文字列
vowについて、i=2 が条件を満たすことから、vowの出現回数は 1 です。 - 文字列
oooについて、条件を満たす i が存在しないことから、oooの出現回数は 0 です。
入力例 2
9 1 ovowowovo
出力例 2
5 o
入力例 3
35 3 thequickbrownfoxjumpsoverthelazydog
出力例 3
2 the
Score : 200 points
Problem Statement
You are given a string S of length N consisting of lowercase English letters.
Define the number of occurrences of a string t of length K as the number of integers i that satisfy the following condition:
- 1 \leq i \leq N-K+1
- The substring of S from the i-th character to the (i+K-1)-th character matches t.
Find the maximum value x of the number of occurrences of a string of length K. Also, output all strings of length K with x occurrences in ascending lexicographical order.
Constraints
- N, K are integers.
- S is a string of length N consisting of lowercase English letters.
- 1 \leq K \leq N \leq 100
Input
The input is given from Standard Input in the following format:
N K S
Output
Output two lines.
The first line should contain the maximum value x of the number of occurrences of a string of length K.
The second line should contain all strings of length K with x occurrences in ascending lexicographical order, separated by spaces.
Sample Input 1
9 3 ovowowovo
Sample Output 1
2 ovo owo
The following strings have two occurrences:
- For the string
ovo, i=1,7 satisfy the condition, so the number of occurrences ofovois 2. - For the string
owo, i=3,5 satisfy the condition, so the number of occurrences ofowois 2.
There is no string of length 3 with more than two occurrences, so the maximum value is 2.
On the other hand, the following are examples of strings with fewer than two occurrences:
- For the string
vow, i=2 satisfies the condition, so the number of occurrences ofvowis 1. - For the string
ooo, there is no i that satisfies the condition, so the number of occurrences ofooois 0.
Sample Input 2
9 1 ovowowovo
Sample Output 2
5 o
Sample Input 3
35 3 thequickbrownfoxjumpsoverthelazydog
Sample Output 3
2 the
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋くんは、文字をいくつか持っています。
高橋くんが持っている文字は A, B, C のいずれかです。
はじめ、高橋くんは A を n _ A 個、B を n _ B 個、C を n _ C 個持っています。
高橋くんは、A を 1 つ、C を 1 つ、さらに追加で任意の 1 つの文字の合計 3 文字を使うことで、コンテストを 1 つ開催することができます。
具体的には、A を 2 つ、C を 1 つ使うと AAC を、A, B, C を 1 つずつ使うと ABC を、A を 1 つ、C を 2 つ使うと ACC を開催することができます。
高橋くんは、現在持っている文字を使ってコンテストをなるべく多く開催したいです。 高橋くんが最大でいくつのコンテストを開催することができるか求めてください。
T 個のテストケースが与えられるので、それぞれについて答えてください。
制約
- 1\le T\le2\times10 ^ 5
- それぞれのテストケースについて、
- 0\le n _ A\le10 ^ 9
- 0\le n _ B\le10 ^ 9
- 0\le n _ C\le10 ^ 9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{testcase} _ 1
\mathrm{testcase} _ 2
\vdots
\mathrm{testcase} _ T
\mathrm{testcase} _ i\ (1\le i\le T) は i 番目のテストケースを表しており、次の形式で与えられる。
n _ A n _ B n _ C
出力
T 行にわたって出力せよ。 i 行目 (1\le i\le T) には、i 番目のテストケースの答えを出力せよ。
入力例 1
5 3 1 2 100 0 0 1000000 1000000 1000000 31 41 59 1000000000 10000 1
出力例 1
2 0 1000000 31 1
1 つめのテストケースでは、AAC を 1 回、ABC を 1 回の計 2 回のコンテストを開催することができます。
よって、1 行目には 2 を出力してください。
Score : 300 points
Problem Statement
Takahashi has some letters.
Each letter he has is A, B, or C.
Initially, he has n _ A letters A, n _ B letters B, and n _ C letters C.
He can hold one contest by using one letter A, one letter C, and additionally any one letter, for a total of three letters.
Specifically, he can hold AAC by using two letters A and one letter C, ABC by using one letter each of A, B, and C, and ACC by using one letter A and two letters C.
He wants to hold as many contests as possible using the letters he currently has. Find the maximum number of contests he can hold.
T test cases are given, so report the answer for each of them.
Constraints
- 1\le T\le2\times10 ^ 5
- For each test case,
- 0\le n _ A\le10 ^ 9
- 0\le n _ B\le10 ^ 9
- 0\le n _ C\le10 ^ 9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{testcase} _ 1
\mathrm{testcase} _ 2
\vdots
\mathrm{testcase} _ T
\mathrm{testcase} _ i\ (1\le i\le T) represents the i-th test case and is given in the following format:
n _ A n _ B n _ C
Output
Output over T lines. On the i-th line (1\le i\le T), output the answer to the i-th test case.
Sample Input 1
5 3 1 2 100 0 0 1000000 1000000 1000000 31 41 59 1000000000 10000 1
Sample Output 1
2 0 1000000 31 1
In the first test case, he can hold AAC once and ABC once, for a total of two contests.
Therefore, output 2 on the first line.