JMC 2015-2016 模擬予選 問題５
kagamiz logo
第 15 回 日本情報オリンピック　模擬予選 ５

2015年12月12日
kagamiz

問題
５ 		　　　 楽しい楽しい花の水やり (Watering Flower is So Fun)

問題

ミズゴロウのゴロウくんは, 花を育てている. 毎日水やりをすることで, 日々花は美しくなっていく. 最近, ゴロウくんは花の水やりのスケジュールを立てるのに悩んでいる. ゴロウくんのために, 時刻 0 から時刻 T までの花の水やりのスケジュールを立てるのを手伝ってあげよう.

ゴロウくんは N 本の花を育てていて, N 本は一直線上に咲いている. それぞれの花にはみずみずしさがあり, 時刻 0 の時点で左から i 番目の花のみずみずしさは Ai という正の整数で表される. それぞれの花のみずみずしさは, 時刻が 1 増えると, その瞬間に Bi だけ減少する. ここで, 花のみずみずしさが 0 以下になるとその花は枯れてしまう. そこで, 時刻 i と時刻 i + 1 (0 ≦ i ≦ T - 1) の間に, 次の水やりという操作を行うことが出来る.

水やり : 左から i 番目の花を花 i とする. 1 つ花を選ぶ(ここでは花 x を選んだとする). このとき, 花 x - K から花 x + K までのそれぞれの花のみずみずしさを C だけ増やす. (みずみずしさが時刻 0 での初期値 Ai を超える可能性があることに注意せよ.) ここで x - K が 0 以下になる場合は 1 番目の花まで, x + K が N を超える場合は N 番目の花までみずみずしさが増えるとする.

ゴロウくんは水やりに慣れているため, 時刻 i と時刻 i + 1 (0 ≦ i ≦ T - 1) の間に何度でも水やりを行うことが出来る. まったく水やりを行わない時刻があっても構わない. また, 同じ花に対して何回も水やりを行っても良い. しかし, ゴロウくんはできるだけ水やりを行う回数を減らしたいと考えている. ゴロウくんのために, 時刻 T までに花を枯らさないよう水やりを行うとき, その回数の最小値を求めるプログラムを作成せよ.

入力

入力は 3 行からなる.

1 行目に, 4 つの整数 N, K, C, T (1 ≦ N ≦ 5 × 106, 0 ≦ K ≦ [N / 2], 1 ≦ C ≦ 107, 1 ≦ T ≦ 1000) が空白区切りで入力される. ここで, [N / 2] は N / 2 の整数部分を表す.

2 行目に, 4 つの整数 Sa, Xa, Ya, Za (0 ≦ Sa, Xa, Ya ≦ 107 - 1, 1 ≦ Za ≦ 107) が空白区切りで入力される. Sa, Xa, Ya < Za が保証されている.

3 行目に, 4 つの整数 Sb, Xb, Yb, Zb (0 ≦ Sb, Xb, Yb ≦ 107 - 1, 1 ≦ Zb ≦ 107) が空白区切りで入力される. Sb, Xb, Yb < Zb が保証されている.

2, 3 行目の整数を用いて, 問題文中で与えられている Ai と Bi は以下の C++ 言語のコードで生成される. Xa と Sa の積 (Xb と Sb の積) が 32 ビット符号付き整数に収まらない可能性があることに注意せよ. 

void generate(int A[], int B[])
{
    for (int i = 1; i <= N; i++){
        A[i] = Sa + 1;
        B[i] = Sb + 1;
        Sa = (Xa * Sa + Ya) % Za;
        Sb = (Xb * Sb + Yb) % Zb;
    }
}

出力

1 行に, 時刻 T までに水やりを行う回数の最小値を出力せよ.

入出力例

入力例 1 入力例 2 入力例 3 
3 0 1 5
1 1 5 11
0 0 0 1
  
16 3 8 5
9 9 8 47
0 2 9 37
  
1234567 89 1 987
7777779 6543210 6172819 10000000
584 5849 58499 5849999
出力例 1 出力例 2 出力例 3 
9
   
37
  
37025278961263

入力例 1 について, それぞれの花の時刻 0 でのみずみずしさ Ai と, 花のみずみずしさの減少量 Bi は次のようになっている :
A1 = 2, A2 = 7, A3 = 1,
B1 = 1, B2 = 1, B3 = 1.
次の水やりの仕方は, 最小の水やりの回数である 9 回を達成できる例である.

入力例 2 の最初の 5 本の花のみずみずしさ Ai と, 花のみずみずしさの減少量 Bi は次のようになっている :
A1 = 10, A2 = 43, A3 = 11, A4 = 5, A5 = 45,
B1 = 1, B2 = 10, B3 = 28, B4 = 27, B5 = 25.

入力例 3 の答えが 32 ビット符号付き整数の範囲を超えていることに注意せよ.

この問題は public_sate さんから頂いた問題です. この場を借りてお礼申し上げます.

※各入出力例のデータは，右クリック等によりファイルに保存して利用可能です．