Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 100 点
問題文
2018 年 1 月某日、高木さんは書類を書いています。書類には、その日の日付を yyyy/mm/dd という形式で書き込む欄があります。例えば、2018 年 1 月 23 日は 2018/01/23 となります。
書類を書き終えたあと、高木さんは日付欄の先頭に誤って 2017 と書いてしまっていたことに気がつきました。高木さんが日付欄に書いた文字列 S を入力すると、S の先頭の 4 文字を 2018 に修正して出力するプログラムを書いてください。
制約
- S は長さ 10 の文字列である。
- S の先頭の 8 文字は
2017/01/である。 - S の末尾の 2 文字は数字であり、1 以上 31 以下の整数を表す。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S の先頭の 4 文字を 2018 に置き換えて出力せよ。
入力例 1
2017/01/07
出力例 1
2018/01/07
入力例 2
2017/01/31
出力例 2
2018/01/31
Score : 100 points
Problem Statement
On some day in January 2018, Takaki is writing a document. The document has a column where the current date is written in yyyy/mm/dd format. For example, January 23, 2018 should be written as 2018/01/23.
After finishing the document, she noticed that she had mistakenly wrote 2017 at the beginning of the date column. Write a program that, when the string that Takaki wrote in the date column, S, is given as input, modifies the first four characters in S to 2018 and prints it.
Constraints
- S is a string of length 10.
- The first eight characters in S are
2017/01/. - The last two characters in S are digits and represent an integer between 1 and 31 (inclusive).
Input
Input is given from Standard Input in the following format:
S
Output
Replace the first four characters in S with 2018 and print it.
Sample Input 1
2017/01/07
Sample Output 1
2018/01/07
Sample Input 2
2017/01/31
Sample Output 2
2018/01/31
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
X 段重ねの鏡餅 (X ≥ 1) とは、X 枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。例えば、直径 10、8、6 センチメートルの餅をこの順に下から積み重ねると 3 段重ねの鏡餅になり、餅を一枚だけ置くと 1 段重ねの鏡餅になります。
ダックスフンドのルンルンは N 枚の円形の餅を持っていて、そのうち i 枚目の餅の直径は d_i センチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。
制約
- 1 ≤ N ≤ 100
- 1 ≤ d_i ≤ 100
- 入力値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N d_1 : d_N
出力
作ることのできる鏡餅の最大の段数を出力せよ。
入力例 1
4 10 8 8 6
出力例 1
3
直径 10、8、6 センチメートルの餅をこの順に下から積み重ねると 3 段重ねの鏡餅になり、これが最大です。
入力例 2
3 15 15 15
出力例 2
1
すべての餅の直径が同じときは、1 段重ねの鏡餅しか作れません。
入力例 3
7 50 30 50 100 50 80 30
出力例 3
4
Score : 200 points
Problem Statement
An X-layered kagami mochi (X ≥ 1) is a pile of X round mochi (rice cake) stacked vertically where each mochi (except the bottom one) has a smaller diameter than that of the mochi directly below it. For example, if you stack three mochi with diameters of 10, 8 and 6 centimeters from bottom to top in this order, you have a 3-layered kagami mochi; if you put just one mochi, you have a 1-layered kagami mochi.
Lunlun the dachshund has N round mochi, and the diameter of the i-th mochi is d_i centimeters. When we make a kagami mochi using some or all of them, at most how many layers can our kagami mochi have?
Constraints
- 1 ≤ N ≤ 100
- 1 ≤ d_i ≤ 100
- All input values are integers.
Input
Input is given from Standard Input in the following format:
N d_1 : d_N
Output
Print the maximum number of layers in a kagami mochi that can be made.
Sample Input 1
4 10 8 8 6
Sample Output 1
3
If we stack the mochi with diameters of 10, 8 and 6 centimeters from bottom to top in this order, we have a 3-layered kagami mochi, which is the maximum number of layers.
Sample Input 2
3 15 15 15
Sample Output 2
1
When all the mochi have the same diameter, we can only have a 1-layered kagami mochi.
Sample Input 3
7 50 30 50 100 50 80 30
Sample Output 3
4
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計で Y 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。
制約
- 1 ≤ N ≤ 2000
- 1000 ≤ Y ≤ 2 × 10^7
- N は整数である。
- Y は 1000 の倍数である。
入力
入力は以下の形式で標準入力から与えられる。
N Y
出力
N 枚のお札の合計金額が Y 円となることがありえない場合は、-1 -1 -1 と出力せよ。
N 枚のお札の合計金額が Y 円となることがありうる場合は、そのような N 枚のお札の組み合わせの一例を「10000 円札 x 枚、5000 円札 y 枚、1000 円札 z 枚」として、x、y、z を空白で区切って出力せよ。複数の可能性が考えられるときは、そのうちどれを出力してもよい。
入力例 1
9 45000
出力例 1
4 0 5
お年玉袋に 10000 円札 4 枚と 1000 円札 5 枚が入っていれば、合計枚数が 9 枚、合計金額が 45000 円になります。5000 円札 9 枚という可能性も考えられるため、0 9 0 も正しい出力です。
入力例 2
20 196000
出力例 2
-1 -1 -1
合計枚数が 20 枚の場合、すべてが 10000 円札であれば合計金額は 200000 円になり、そうでなければ 195000 円以下になるため、196000 円という合計金額はありえません。
入力例 3
1000 1234000
出力例 3
14 27 959
この他にも多くの候補があります。
入力例 4
2000 20000000
出力例 4
2000 0 0
Score : 300 points
Problem Statement
The commonly used bills in Japan are 10000-yen, 5000-yen and 1000-yen bills. Below, the word "bill" refers to only these.
According to Aohashi, he received an otoshidama (New Year money gift) envelope from his grandfather that contained N bills for a total of Y yen, but he may be lying. Determine whether such a situation is possible, and if it is, find a possible set of bills contained in the envelope. Assume that his grandfather is rich enough, and the envelope was large enough.
Constraints
- 1 ≤ N ≤ 2000
- 1000 ≤ Y ≤ 2 × 10^7
- N is an integer.
- Y is a multiple of 1000.
Input
Input is given from Standard Input in the following format:
N Y
Output
If the total value of N bills cannot be Y yen, print -1 -1 -1.
If the total value of N bills can be Y yen, let one such set of bills be "x 10000-yen bills, y 5000-yen bills and z 1000-yen bills", and print x, y, z with spaces in between. If there are multiple possibilities, any of them may be printed.
Sample Input 1
9 45000
Sample Output 1
4 0 5
If the envelope contained 4 10000-yen bills and 5 1000-yen bills, he had 9 bills and 45000 yen in total. It is also possible that the envelope contained 9 5000-yen bills, so the output 0 9 0 is also correct.
Sample Input 2
20 196000
Sample Output 2
-1 -1 -1
When the envelope contained 20 bills in total, the total value would be 200000 yen if all the bills were 10000-yen bills, and would be at most 195000 yen otherwise, so it would never be 196000 yen.
Sample Input 3
1000 1234000
Sample Output 3
14 27 959
There are also many other possibilities.
Sample Input 4
2000 20000000
Sample Output 4
2000 0 0
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
あなたが散歩していると、突然一体の魔物が出現しました。幸い、あなたは N 本の刀、刀 1、刀 2、…、刀 N を持っていて、次の二種類の攻撃を自由な順番で行うことができます。
- 持っている刀のうち一本を振る。刀 i (1 ≤ i ≤ N) を振ると、魔物は a_i ポイントのダメージを受ける。同じ刀を何度振ることもできる。
- 持っている刀のうち一本を投げつける。刀 i (1 ≤ i ≤ N) を投げつけると、魔物は b_i ポイントのダメージを受け、あなたはその刀を失う。すなわち、あなたは以後その刀を振ることも投げつけることもできなくなる。
魔物は、受けたダメージの合計が H ポイント以上になると消滅します。魔物を消滅させるには、最小で合計何回の攻撃が必要でしょうか。
制約
- 1 ≤ N ≤ 10^5
- 1 ≤ H ≤ 10^9
- 1 ≤ a_i ≤ b_i ≤ 10^9
- 入力値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N H a_1 b_1 : a_N b_N
出力
魔物を消滅させるために必要な最小の合計攻撃回数を出力せよ。
入力例 1
1 10 3 5
出力例 1
3
あなたは 1 本の刀を持っていて、振ると 3 ポイントのダメージ、投げつけると 5 ポイントのダメージを与えられます。刀を 2 回振ってから投げつけると 3 + 3 + 5 = 11 ポイントのダメージを与え、合計 3 回の攻撃で魔物が消滅します。
入力例 2
2 10 3 5 2 6
出力例 2
2
先ほどの刀に加えてもう 1 本別の刀もあり、こちらは振ると 2 ポイントのダメージ、投げつけると 6 ポイントのダメージを与えられます。両方の刀を投げつけると 5 + 6 = 11 ポイントのダメージを与え、2 回の攻撃で魔物が消滅します。
入力例 3
4 1000000000 1 1 1 10000000 1 30000000 1 99999999
出力例 3
860000004
入力例 4
5 500 35 44 28 83 46 62 31 79 40 43
出力例 4
9
Score : 400 points
Problem Statement
You are going out for a walk, when you suddenly encounter a monster. Fortunately, you have N katana (swords), Katana 1, Katana 2, …, Katana N, and can perform the following two kinds of attacks in any order:
- Wield one of the katana you have. When you wield Katana i (1 ≤ i ≤ N), the monster receives a_i points of damage. The same katana can be wielded any number of times.
- Throw one of the katana you have. When you throw Katana i (1 ≤ i ≤ N) at the monster, it receives b_i points of damage, and you lose the katana. That is, you can no longer wield or throw that katana.
The monster will vanish when the total damage it has received is H points or more. At least how many attacks do you need in order to vanish it in total?
Constraints
- 1 ≤ N ≤ 10^5
- 1 ≤ H ≤ 10^9
- 1 ≤ a_i ≤ b_i ≤ 10^9
- All input values are integers.
Input
Input is given from Standard Input in the following format:
N H a_1 b_1 : a_N b_N
Output
Print the minimum total number of attacks required to vanish the monster.
Sample Input 1
1 10 3 5
Sample Output 1
3
You have one katana. Wielding it deals 3 points of damage, and throwing it deals 5 points of damage. By wielding it twice and then throwing it, you will deal 3 + 3 + 5 = 11 points of damage in a total of three attacks, vanishing the monster.
Sample Input 2
2 10 3 5 2 6
Sample Output 2
2
In addition to the katana above, you also have another katana. Wielding it deals 2 points of damage, and throwing it deals 6 points of damage. By throwing both katana, you will deal 5 + 6 = 11 points of damage in two attacks, vanishing the monster.
Sample Input 3
4 1000000000 1 1 1 10000000 1 30000000 1 99999999
Sample Output 3
860000004
Sample Input 4
5 500 35 44 28 83 46 62 31 79 40 43
Sample Output 4
9