問題文

今日は 2018 年 12 月 25 日。 クリスマス当日です。
これにちなんで、Y 年 M 月 D 日が何年後のクリスマスかどうかを計算するプログラムを書きなさい。
ただし、そもそもクリスマスではない場合は NOT CHRISTMAS DAY と出力しなさい。

制約

• Y は 2018 以上 2299 以下の整数
• M は 1 以上 12 以下の整数
• D は 1 以上 31 以下の整数
• Y 年 M 月 D 日は、グレゴリオ暦において存在する日付である。

入力例 1

2018 12 25

出力例 1

0

2018 年 12 月 25 日は今年のクリスマスなので、0 年後です。

入力例 2

2018 12 24

出力例 2

NOT CHRISTMAS DAY

2018 年 12 月 24 日はクリスマスイブですが、クリスマス当日ではありません。

入力例 3

2234 12 25

出力例 3

216

2234 年 12 月 25 日は 216 年後のクリスマスですが、そもそもこんな時代までクリスマスは続いていくのでしょうか。

問題文

2018 年も間もなく終わりです。2019 年 5 月 1 日に新元号になることが発表されて以来、2018 年は「㍻の終焉を告げる」年になりました。

さて、古くから続く PAKEN 国は、情報暦 1 年 1 月 1 日に第 1 代天皇が即位し、第 i 代天皇は丁度 a_i 年間在位しました。天皇の退位式は情報暦の一年の一番最後の日である 12 月 31 日、即位式は情報暦の一年の一番最初の日である 1 月 1 日に行われるので、元号は天皇が変わる年の 12/31 と 1/1 の間に変わります。
現在の天皇は第 N+1 代天皇であるため、第 1 代から第 N 代天皇に関する在位期間のデータが与えられます。

PAKEN 国では、第 i 代 (1 \leq i \leq N) 天皇がいる最後の年のことを「〇〇時代の終焉を告げる」年といいます。
情報暦 2018 年までに、何回「〇〇時代の終焉を告げる年」があったのでしょうか。ただし 2018 年も含めて数えるものとします。また、現在は情報暦 2018 年より後であるとします。

制約

• N は 1 以上 8000 以下の整数
• a_i は 1 以上 10000 以下の整数

入力例 1

3
700
700
700

出力例 1

2

第 1 代天皇は情報暦 1 年 ～ 700 年まで在位しています。その為、情報暦 700 年は「〇〇時代の終焉を告げる」年になります。
第 2 代天皇は情報暦 701 年 ～ 1400 年まで在位しています。その為、情報暦 1400 年は「〇〇時代の終焉を告げる」年になります。
第 3 代天皇は情報暦 1401 年 ～ 2100 年まで在位しています。その為、情報暦 2100 年は「〇〇時代の終焉を告げる」年になります。
第 4 代天皇は情報暦 2101 年から在位しており、現在の天皇です。
そのため、現在までに情報暦 700, 1400, 2100 年が「〇〇時代の終焉を告げる」年ですが、その中で 2018 年もしくはそれ以前のものは 2 回です。
ですので、2 と出力します。

入力例 2

2
2018
1

出力例 2

1

第 1 代天皇は情報暦 1 年 ～ 2018 年まで在位しています。その為、情報暦 2018 年は「〇〇時代の終焉を告げる」年になります。
第 2 代天皇は情報暦 2019 年 ～ 2019 年まで在位しています。その為、情報暦 2019 年は「〇〇時代の終焉を告げる」年になります。
第 3 代天皇は情報暦 2020 年から在位しており、現在の天皇です。
そのため、現在までに情報暦 2018, 2019 年が「〇〇時代の終焉を告げる」年ですが、その中で 2018 年もしくはそれ以前のものは 1 回です。
ですので、1 と出力します。

入力例 3

1
10000

出力例 3

0

そもそも最初の天皇が退位するのが情報暦 10000 年なので、2018 年以前に「〇〇時代の終焉を告げる年」は一回もありません。

入力例 4

20
188
186
234
175
172
157
244
108
81
297
331
323
185
162
216
143
141
225
200
177

出力例 4

10

問題文

PAKEN 植物園は、竹を育てています。E869120 君は、定期的に竹を観察しています。

植物園にある竹は、毎晩 1.5 倍伸びます。具体的には、今までの高さが A だったとき、高さが 「A \times 1.5 を小数点以下切り捨てた値」まで増えます。
例えば、1 日目の昼に高さ 2 だった竹は、2 日目の昼には高さ 3 になり、3 日目の昼には高さ 4 となります。その後、6, 9, 13, 19, 28, ... と高さが増えていきます。

E869120 君の情報によると、何日か前の昼 (今日ではない) に観察した時の竹の高さは整数 A でしたが、今日の昼見たら竹の高さは整数 B でした。
彼は A の値をノートに記録していましたが、ノートを紛失してしまいました。
彼のために、A としてあり得る通り数を求めてください。
ただし、竹は昼には一切伸びず、夜にしか伸びないとします。

制約

• B は 2 以上 10000 以下の整数

入力

入力は以下の形式で標準入力から与えられる。

B

入力例 1

10

出力例 1

2

A としてあり得る値は、5, 7 の 2 通りです。それぞれの場合、竹の長さの変化は以下のようになります。
A = 5 の場合： 5 → 7 → 10
A = 7 の場合： 7 → 10

それ以外の A の値場合、今日の高さ B が 10 となる訳がありません。

入力例 2

5

出力例 2

0

このような場合、A としてあり得るものはありません。何故なら、
A = 1 の場合： 1 → 1 → 1 → ... (竹は全く成長しない)
A = 2 の場合： 2 → 3 → 4 → 6 ...
A = 3 の場合： 3 → 4 → 6 ...
A = 4 の場合： 4 → 6 ...
A = 5 の場合： 今日の高さ B が 5 なので、今日より前に測った竹の高さが 5 となることはあり得ない
A \geq 6 の場合： 竹が縮むことはないのであり得ない
よって、答えは 0 通りです。

入力例 3

8092

出力例 3

21

答えの最大は B = 8092 のときで、21 通りです。

入力例 4

3687

出力例 4

12

問題文

なぎさちゃんの別荘は N 個の部屋と N-1 本の通路からなり、各部屋には 1 から N の、各通路には 1 から N-1 の番号が割り振られています。i 番目の通路は部屋 i と 部屋 i+1 を双方向に繋いでおり、整数 C_i が書かれています。

いろはちゃんは今朝、この内のある部屋で目が覚めました。忍者であるいろはちゃんは、忍術を使って抜け出すことにしました。いろはちゃんの気分は整数で表され、これが高いほど忍術が成功しやすいです。気分の値は初め 0 であり、通路 i を通ると気分に C_i が加算されますが、仕掛けが作動してその通路が通れなくなります。
スタートする部屋を r として、通路を 0 回以上通って好きな部屋で立ち止まるときの、気分の最大値を X_r とします。
全ての部屋 i に対して X_i を求めて下さい。

入力

入力は、以下の形式で標準入力より与えられます。

N
C_1
C_2
C_3
...
C_{N-1}

出力

全部で N 行出力してください。
i 行目には X_i 、つまり部屋 i から始めたときの気分の最大値を出力してください。

入力例 1

5
70
10
50
20

出力例 1

150
80
80
130
150

この入力例において、別荘の図は以下のようになっています。

例えば部屋 3 から出発した場合、3 → 2 → 1 というルートを通り部屋 1 で立ち止まるとき、気分が 10 + 70 = 80 が得られます。
また、これより良い気分を得る方法はありません。

入力例 2

8
70
10
-2000
10000
-2000
50
20

出力例 2

8080
8010
8000
10000
10000
8000
8050
8070

この入力は、小課題 1, 2 の制約を満たしません。

入力例 3

7
-45
-45
-45
-45
-45
-45

出力例 3

0
0
0
0
0
0
0

問題文

あなたはプロのピアニストであり，今月は茨城県の各地で行われる運動会でピアノを弾くことになりました．茨城県のピアノは高橋流による特殊なものであり，以下の特徴を持ちます．

• 88 の鍵盤が横一列にあり，全ての鍵盤に正の整数が 1 つずつ刻まれています．左から 1, 2 番目以外の鍵盤について，刻まれた整数は 1 つ左の鍵盤と 2 つ左の鍵盤のものの和に等しいです．
  • たとえば，左から 1, 2 番目に 3, 2 とあった場合， 3 番目以降は 5, 7, 12, 19, ... と続きます．
• 1 つ以上の鍵盤の組合せを「和音」と呼びます．特に，隣り合う 2 鍵を含んでいないようなものを「美しい和音」と呼びます．
  • たとえば，「左から 1, 3, 6, 88 番目」や「左から 5 番目」は美しい和音ですが，「左から 5, 7, 8 番目」は美しい和音ではありません．
• 和音の「高橋値」は，和音を構成する鍵盤に刻まれた整数の総和で表されます．
  • たとえば，左から i 鍵目に刻まれた整数を A_i とおくと，「左から 86, 9, 1, 20 番目」から成る和音の高橋値は A_{86} + A_9 + A_1 + A_{20} に等しいです．

運動会は全部で Q 回行われます． i 回目の運動会において，開催校は創立 X_i 周年であることから，あなたは高橋値が X_i であるような美しい和音を曲に織り交ぜることにしました． i 回目の運動会で弾くピアノの左から 1, 2 番目の鍵盤にはそれぞれ a_i, b_i が刻まれているとわかっているので，各 i に対し，与えられたピアノで高橋値 X_i となる美しい和音が何通りあるか答えてください．

入力

1 行目には，質問の回数 Q が与えられます．

2 行目から Q 行にわたって，i 回目の運動会に関する情報 a_i, b_i, X_i が空白区切りで与えられます．

Q
a_1 b_1 X_1
a_2 b_2 X_2
a_3 b_3 X_3
...
a_Q b_Q X_Q

出力

全部で Q 行出力してください． i 行目には， i 番目の質問に対する解答を出力してください．

入力例 1

2
1 1 1
1 1 9

出力例 1

2
2

入力例 2

3
1 2 32
5 2 1
2 1 70

出力例 2

1
0
2

問題文

ぬけす君はダンスプログラミングの祭典「KACoder」に出場するために、予選までの Q 日間、体にいいとされる妖精のミックスジュースを飲むことにしました。
妖精 1 羽の「美味しさ」は正の整数で表され、ミックスジュースの「美味しさ」は原料となった妖精の美味しさの合計です。
あなたは i 日目の朝に A_i 以上 B_i 以下の整数の美味しさの妖精をそれぞれ 1 羽ずつ仕入れ、1 羽以上を選んでミキサーにかけます。なお鮮度の観点から、使わなかった妖精はその日の夜に廃棄し、以後使うことはありません。
このとき、i 日目に作るミックスジュースの美味しさとしてあり得る値は何通りあるでしょうか。答えは非常に大きくなる可能性があるため、10^9+7 で割ったあまりを答えて下さい。

入力

入力は標準入力より以下のように与えられます。

Q
A_1 B_1
A_2 B_2
...
A_Q B_Q

• 1 行目には、予選までの日数 Q が与えられます。
• 2 行目から Q 行に渡って、i+1 行目には i 日目の朝に仕入れる妖精の情報 A_i, B_i が与えられます。

出力

全部で Q 行出力してください。
i 行目には、i 番目の質問に対する解答を出力してください。

入力例 1

4
1 3
3 7
4 7
3141592 3141592

出力例 1

6
21
14
1

例えば、3 日目の妖精の美味しさは 4, 5, 6, 7 です。そのうち 1 個以上選ぶ方法は 15 通りあり、ミックスジュースの美味しさはそれぞれ

• 4, 5, 6, 7, 4+5, 4+6, 5+6, 4+7, 5+7, 6+7, 4+5+6, 4+5+7, 4+6+7, 5+6+7, 4+5+6+7

ですが、そのうち 5+6 と 4+7 だけ 11 と同じ値になっているので、美味しさとしてありうる値は 14 通りあります。

問題文

高橋くんは N 日間の間に、M 個の宿題を受けとります。そのうち K 個以上の宿題を提出する必要があります。しないと留年です。
1 \leq i \leq M 番目の宿題の配布日は S_i で、締め切り日は E_i です。S_i 以降 E_i までの日 (両方の期限の当日も含む) にその宿題をすると提出できます。

また、各日付には「その日のやりたくなさ」があります。i 日目のやりたくなさは X_i です。
高橋くんは各日において、「宿題をどれか一つする」または「宿題をしない」を選べます。一日に二つ以上の宿題はできません。
このとき、K 個以上の宿題をやりつつ、高橋君が宿題をやった日の「やりたくなさ」の合計を最小化するときの、「やりたくなさ」の合計を出力してください。

ただし、どうやっても宿題を K 個以上行うことができない場合、-1 を出力してください。

入力

入力は以下の形式で標準入力から与えられます。

N M K
X_1 X_2 X_3 ... X_N
S_1 E_1
S_2 E_2
S_3 E_3
...
S_M E_M

入力例 1

4 3 2
5 6 3 7
1 1
2 3
3 4

出力例 1

8

入力例 2

5 5 5
8 6 9 1 20
1 2
3 4
5 5
4 5
3 5

出力例 2

-1

問題文

あなたは正整数 N が与えられます。 あなたは、 012345+-*/ を使って、50000 文字以下で、答えが N になる数式を作ってください。 6789%^()が使えないことに注意してください。 ただし、数字を連結して、2桁以上の数として利用することは禁止します。 また、初めがマイナスであるような式や、マイナス記号を単項演算子として使う事も禁止します。

(禁止される例: 8-2*(4*2) , 55+42 , -4+2*4 , 5*5+3*-2 ,) さらにジャッジの都合上、項の値が10^{800}以上になった場合も不正解とします。 ただし、式は* /を先に計算します。 また、優先順位が同じときは左から計算します。 さらに、割り算は小数点以下は切り捨てます(sample3を見てください)。

制約

1 ≦ N ≦ 10^{150}

入力例 1

7

出力例 1

5+2

5+2 = 7 なので、正しいです。ほかにも、3+4 や、2*3+1 や、 3*5/2 なども正しいです。

入力例 2

19

出力例 2

5*5-2*3

入力例 3

24

出力例 3

5*5/4*4

この問題の場合、5*5/4を先に計算して、小数点以下を切り捨てて6になってから、*4 をするので答えは24です。