Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
(1,2,…,N) を並び替えた数列 P と整数 X が与えられます。 数列 P の i 番目の項の値は P_i です。 P_k = X を満たす k を出力してください。
制約
- 1 \leq N \leq 100
- 1 \leq X \leq N
- P は (1,2,…,N) を並び替えてできる数列
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X P_1 P_2 \ldots P_N
出力
答えを出力せよ。
入力例 1
4 3 2 3 1 4
出力例 1
2
P = (2,3,1,4) なので、P_2 = 3 です。したがって、2 を出力します。
入力例 2
5 2 3 5 1 4 2
出力例 2
5
入力例 3
6 6 1 2 3 4 5 6
出力例 3
6
Score : 100 points
Problem Statement
You are given a sequence P that is a permutation of (1,2,…,N), and an integer X. The i-th term of P has a value of P_i. Print k such that P_k = X.
Constraints
- 1 \leq N \leq 100
- 1 \leq X \leq N
- P is a permutation of (1,2,…,N).
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N X P_1 P_2 \ldots P_N
Output
Print the answer.
Sample Input 1
4 3 2 3 1 4
Sample Output 1
2
We have P = (2,3,1,4), so P_2 = 3. Thus, you should print 2.
Sample Input 2
5 2 3 5 1 4 2
Sample Output 2
5
Sample Input 3
6 6 1 2 3 4 5 6
Sample Output 3
6
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
ナオヒロ君はモンスターを飼っています。モンスターの現在の体力は H です。
また、ナオヒロ君は N 種類の傷薬を持っています。傷薬は効き目の弱い順に 1 から N までの番号がついています。
傷薬 n をモンスターに与えると、モンスターの体力が P_n 増加します。ここで、P_1 \lt P_2 \lt \dots \lt P_N が成り立ちます。
ナオヒロ君は傷薬を 1 つモンスターに与えることで、モンスターの体力を X 以上にしたいです。
目標を達成できる傷薬のうち最も効き目の弱いものの番号を出力してください。(制約下においてそのような傷薬が存在することが保証されています。)
制約
- 2 \leq N \leq 100
- 1 \leq H \lt X \leq 999
- 1 \leq P_1 \lt P_2 \lt \dots \lt P_N = 999
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N H X P_1 P_2 \dots P_N
出力
目標を達成できる傷薬のうち最も効き目の弱いものの番号を出力せよ。
入力例 1
3 100 200 50 200 999
出力例 1
2
それぞれの傷薬をモンスターに 1 つ与えたときのモンスターの体力の変化は以下の通りです。
- 傷薬 1 をモンスターに与えるとモンスターの体力は 100 + 50 = 150 になります。
- 傷薬 2 をモンスターに与えるとモンスターの体力は 100 + 200 = 300 になります。
- 傷薬 3 をモンスターに与えるとモンスターの体力は 100 + 999 = 1099 になります。
与えた後に体力が X = 200 以上になっている傷薬は、傷薬 2 と傷薬 3 です。このうち最も効き目の弱い傷薬である傷薬 2 が答えになります。
入力例 2
2 10 21 10 999
出力例 2
2
入力例 3
10 500 999 38 420 490 585 613 614 760 926 945 999
出力例 3
4
Score : 100 points
Problem Statement
Naohiro has a monster. The monster's current health is H.
He also has N kinds of potions, numbered from 1 to N in ascending order of effectiveness.
If you give the monster potion n, its health will increase by P_n. Here, P_1 \lt P_2 \lt \dots \lt P_N.
He wants to increase the monster's health to X or above by giving it one of the potions.
Print the number of the least effective potion that can achieve the purpose. (The constraints guarantee that such a potion exists.)
Constraints
- 2 \leq N \leq 100
- 1 \leq H \lt X \leq 999
- 1 \leq P_1 \lt P_2 \lt \dots \lt P_N = 999
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N H X P_1 P_2 \dots P_N
Output
Print the number of the least effective potion that can achieve the purpose.
Sample Input 1
3 100 200 50 200 999
Sample Output 1
2
Below is the change in the monster's health when one of the potions is given to the monster.
- If potion 1 is given, the monster's health becomes 100 + 50 = 150.
- If potion 2 is given, the monster's health becomes 100 + 200 = 300.
- If potion 3 is given, the monster's health becomes 100 + 999 = 1099.
The potions that increase the monster's health to at least X = 200 are potions 2 and 3. The answer is the least effective of them, which is potion 2.
Sample Input 2
2 10 21 10 999
Sample Output 2
2
Sample Input 3
10 500 999 38 420 490 585 613 614 760 926 945 999
Sample Output 3
4
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
英小文字からなる文字列 S, T が与えられます。S の長さは N、T の長さは M です。(N \leq M が制約で保証されています)
S が T の 接頭辞 であるとは、T のはじめ N 文字からなる文字列が S と一致することを言います。
S が T の 接尾辞 であるとは、T の後ろ N 文字からなる文字列が S と一致することを言います。
S が T の接頭辞であり、かつ接尾辞でもある場合は 0 を、
S が T の接頭辞であるが、接尾辞でない場合は 1 を、
S が T の接尾辞であるが、接頭辞でない場合は 2 を、
S が T の接頭辞でも接尾辞でもない場合は 3 を出力してください。
制約
- 1 \leq N \leq M \leq 100
- S は英小文字からなる長さ N の文字列
- T は英小文字からなる長さ M の文字列
入力
入力は以下の形式で標準入力から与えられる。
N M S T
出力
問題文の指示に従って答えを出力せよ。
入力例 1
3 7 abc abcdefg
出力例 1
1
S は T の接頭辞ですが接尾辞ではありません。よって 1 を出力します。
入力例 2
3 4 abc aabc
出力例 2
2
S は T の接尾辞ですが接頭辞ではありません。
入力例 3
3 3 abc xyz
出力例 3
3
S は T の接頭辞でも接尾辞でもありません。
入力例 4
3 3 aaa aaa
出力例 4
0
S と T が完全に一致する場合もあります。この場合、S は T の接頭辞であり、かつ接尾辞でもあります。
Score : 200 points
Problem Statement
You are given two strings S and T consisting of lowercase English letters. The lengths of S and T are N and M, respectively. (The constraints guarantee that N \leq M.)
S is said to be a prefix of T when the first N characters of T coincide S.
S is said to be a suffix of T when the last N characters of T coincide S.
If S is both a prefix and a suffix of T, print 0;
If S is a prefix of T but not a suffix, print 1;
If S is a suffix of T but not a prefix, print 2;
If S is neither a prefix nor a suffix of T, print 3.
Constraints
- 1 \leq N \leq M \leq 100
- S is a string of length N consisting of lowercase English letters.
- T is a string of length M consisting of lowercase English letters.
Input
The input is given from Standard Input in the following format:
N M S T
Output
Print the answer according to the instructions in the problem statement.
Sample Input 1
3 7 abc abcdefg
Sample Output 1
1
S is a prefix of T but not a suffix, so you should print 1.
Sample Input 2
3 4 abc aabc
Sample Output 2
2
S is a suffix of T but not a prefix.
Sample Input 3
3 3 abc xyz
Sample Output 3
3
S is neither a prefix nor a suffix of T.
Sample Input 4
3 3 aaa aaa
Sample Output 4
0
S and T may coincide, in which case S is both a prefix and a suffix of T.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
N 人の木こり 1,2,\dots,N が斧を 1 個ずつ持っています。
全員が斧を池に落としてしまいました。
池に N 個の斧 1,2,\dots,N が沈んでいました。
各木こり i は「自分が持っていた斧は斧 A_i である」と主張しています。
一方、この池の女神は、各斧 i を持っていたのは木こり B_i であることを知っています。
N 人の木こり全員が本当のことを言っているかどうかを判定してください。
制約
- 1 \leq N \leq 100
- 1 \leq A_i \leq N
- 1 \leq B_i \leq N
- A_i \neq A_j\;(i \neq j)
- B_i \neq B_j\;(i \neq j)
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
出力
N 人の木こり全員が本当のことを言っているならば Yes を、そうでないならば No を出力せよ。
入力例 1
3 3 1 2 2 3 1
出力例 1
Yes
N 人の木こり全員が本当のことを言っています。
入力例 2
4 1 2 3 4 1 3 2 4
出力例 2
No
木こり 2,3 の 2 人は嘘をついています。
入力例 3
5 2 4 5 1 3 4 1 5 2 3
出力例 3
Yes
Score : 200 points
Problem Statement
N woodcutters 1, 2, \dots, N each have one axe.
All of them dropped their axes into a pond.
N axes 1, 2, \dots, N were found sunk in the pond.
Each woodcutter i claims that "I owned axe A_i."
On the other hand, the goddess of this pond knows that the woodcutter who owned axe i is woodcutter B_i.
Determine whether all N woodcutters are telling the truth.
Constraints
- 1 \leq N \leq 100
- 1 \leq A_i \leq N
- 1 \leq B_i \leq N
- A_i \neq A_j\;(i \neq j)
- B_i \neq B_j\;(i \neq j)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
Output
Output Yes if all N woodcutters are telling the truth, and No otherwise.
Sample Input 1
3 3 1 2 2 3 1
Sample Output 1
Yes
All N woodcutters are telling the truth.
Sample Input 2
4 1 2 3 4 1 3 2 4
Sample Output 2
No
Woodcutters 2 and 3 are lying.
Sample Input 3
5 2 4 5 1 3 4 1 5 2 3
Sample Output 3
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋くんは、プログラミングコンテストを主催することにしました。
コンテストは A 問題、B 問題、C 問題、D 問題、E 問題の 5 問からなり、それぞれの配点は a 点、b 点、c 点、d 点、e 点です。
コンテストには 31 人が参加し、全員が 1 問以上解きました。
より具体的には、文字列 ABCDE の空でない（連続するとは限らない）部分列すべてについて、その部分列を名前とする参加者が存在し、その参加者は名前に含まれる文字に対応する問題をすべて解き、それ以外の問題は解きませんでした。
例えば、A さんは A 問題のみを、BCE さんは B 問題、C 問題、E 問題を解きました。
参加者の名前を、取った点数が大きいほうから順に出力してください。 ただし、参加者が取った点数は、その参加者が解いた問題の配点の合計です。
ただし、同じ点数を獲得した参加者については、名前が辞書順で小さいほうを先に出力してください。
辞書順で小さいとは？
辞書順とは、一言で説明すると「単語が辞書に載っている順番」を意味します。
より厳密には、英大文字からなる相異なる文字列 S,T について、S が T より辞書順で小さいとは、以下の条件のどちらかが成り立つことを意味します。
- S の長さ |S| が T の長さより短く、T の先頭 |S| 文字が S と一致する
- ある整数 1\leq i\leq\min\lbrace|S|,|T|\rbrace が存在して、次の 2 つの条件を両方を満たす
- 1\leq j\lt i を満たすすべての整数 j に対して S の j 文字目と T の j 文字目が等しい
- S の i 文字目が T の i 文字目よりアルファベット順で小さい
例えば、S= AB ,T= ABC とすると、ひとつめの条件が成り立つため S は T より小さいです。
また、S= ABD ,T= ACD とすると、ふたつめの条件が i=2 で成り立つため S は T より小さいです。
制約
- 100\leq a\leq b\leq c\leq d\leq e\leq 2718
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
a b c d e
出力
31 行出力せよ。 i 行目 (1\leq i\leq 31) には、i 番目に高い得点を獲得した参加者の名前を出力せよ。 同じ得点を獲得した参加者については、それらのうち辞書順で小さい名前をもつ参加者を先に出力せよ。
入力例 1
400 500 600 700 800
出力例 1
ABCDE BCDE ACDE ABDE ABCE ABCD CDE BDE ADE BCE ACE BCD ABE ACD ABD ABC DE CE BE CD AE BD AD BC AC AB E D C B A
それぞれの参加者の得点は以下のようになります。
例えば、ADE さんと BCE さんは同じ得点を獲得していますが、ADE さんのほうが辞書順で小さい名前をもつため、ADE さんを先に出力してください。
入力例 2
800 800 900 900 1000
出力例 2
ABCDE ACDE BCDE ABCE ABDE ABCD CDE ACE ADE BCE BDE ABE ACD BCD ABC ABD CE DE AE BE CD AC AD BC BD AB E C D A B
入力例 3
128 256 512 1024 2048
出力例 3
ABCDE BCDE ACDE CDE ABDE BDE ADE DE ABCE BCE ACE CE ABE BE AE E ABCD BCD ACD CD ABD BD AD D ABC BC AC C AB B A
Score : 300 points
Problem Statement
Takahashi decided to hold a programming contest.
The contest consists of five problems: A, B, C, D, E, with scores a, b, c, d, e, respectively.
There are 31 participants, and all of them solved at least one problem.
More specifically, for every non-empty subsequence (not necessarily contiguous) of the string ABCDE, there is a participant named after that subsequence who solved the problems corresponding to the letters in their name and did not solve the other problems.
For example, participant A solved only problem A, and participant BCE solved problems B, C, and E.
Print the names of the participants in order of their obtained scores, from the largest to the smallest. The score obtained by a participant is the sum of the scores of the problems they solved.
If two participants obtained the same score, print the one whose name is lexicographically smaller first.
What does "lexicographically smaller" mean?
In short, "lexicographically smaller" refers to the order in which words would appear in a dictionary.
More precisely, for distinct strings S,T consisting of uppercase English letters, S is lexicographically smaller than T if either of the following conditions holds:
- The length |S| of S is less than the length of T, and the first |S| characters of T match S.
- There exists an integer 1\leq i\leq\min\{ |S|,|T|\} that satisfy both of the following two conditions:
- For every integer j with 1\leq j\lt i, the j-th character of S equals the j-th character of T.
- The i-th character of S is alphabetically smaller than the i-th character of T.
For example, if S= AB and T= ABC, the first condition holds, so S is lexicographically smaller than T.
If S= ABD and T= ACD, the second condition holds for i=2, so S is lexicographically smaller than T.
Constraints
- 100\leq a\leq b\leq c\leq d\leq e\leq 2718
- All input values are integers.
Input
The input is given from Standard Input in the following format:
a b c d e
Output
Print 31 lines. The i-th line (1\leq i\leq 31) should contain the name of the participant who obtained the i-th highest score. If multiple participants have the same score, print them in lexicographical order.
Sample Input 1
400 500 600 700 800
Sample Output 1
ABCDE BCDE ACDE ABDE ABCE ABCD CDE BDE ADE BCE ACE BCD ABE ACD ABD ABC DE CE BE CD AE BD AD BC AC AB E D C B A
The score of each participant is as follows:
For example, ADE and BCE obtained the same score, and ADE is lexicographically smaller, so print ADE before BCE.
Sample Input 2
800 800 900 900 1000
Sample Output 2
ABCDE ACDE BCDE ABCE ABDE ABCD CDE ACE ADE BCE BDE ABE ACD BCD ABC ABD CE DE AE BE CD AC AD BC BD AB E C D A B
Sample Input 3
128 256 512 1024 2048
Sample Output 3
ABCDE BCDE ACDE CDE ABDE BDE ADE DE ABCE BCE ACE CE ABE BE AE E ABCD BCD ACD CD ABD BD AD D ABC BC AC C AB B A