B - Sensor Data Logging 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

ある測定では、時刻 0,1,\dots,T におけるセンサーの測定値を以下の規則で記録します。

  • 時刻 0 では、測定値を保存する。
  • 時刻 1,2,\dots,T では、「現時刻の測定値」と「直前に保存された測定値」との差の絶対値が X 以上であるとき、またその時に限り値を保存する。

時刻 i=0,1,\dots,T におけるセンサーの測定値は A_i でした。

測定値が保存された時刻と保存された値とを、時刻の昇順に出力してください。

制約

  • 1 \le T \le 100
  • 1 \le X \le 100
  • 0 \le A_i \le 100
  • 入力はすべて整数

入力

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

T X
A_0 A_1 \dots A_T

出力

測定値が k 回保存され、そのうち時刻の昇順に並べた時に i 回目の時刻が t_i 、測定値が a_i であったとき、以下の形式で出力せよ。

t_1 a_1
t_2 a_2
\vdots
t_k a_k

入力例 1

6 10
30 35 40 21 30 12 31

出力例 1

0 30
2 40
3 21
6 31

測定は以下の流れで進行します。

  • 時刻 0 の測定値は 30 であった。これを保存する。
  • 時刻 1 の測定値は 35 であった。最後に保存された測定値は 30 であり、この値との差の絶対値が 10 未満であるため、保存しない。
  • 時刻 2 の測定値は 40 であった。最後に保存された測定値は 30 であり、この値との差の絶対値が 10 以上であるため、保存する。
  • 時刻 3 の測定値は 21 であった。最後に保存された測定値は 40 であり、この値との差の絶対値が 10 以上であるため、保存する。
  • 時刻 4 の測定値は 30 であった。最後に保存された測定値は 21 であり、この値との差の絶対値が 10 未満であるため、保存しない。
  • 時刻 5 の測定値は 12 であった。最後に保存された測定値は 21 であり、この値との差の絶対値が 10 未満であるため、保存しない。
  • 時刻 6 の測定値は 31 であった。最後に保存された測定値は 21 であり、この値との差の絶対値が 10 以上であるため、保存する。

Score : 200 points

Problem Statement

In a certain measurement, the sensor readings at times 0,1,\dots,T are recorded according to the following rules.

  • At time 0, the reading is saved.
  • At times 1,2,\dots,T, the reading is saved if and only if the absolute difference between the current reading and the most recently saved reading is at least X.

The sensor reading at time i=0,1,\dots,T was A_i.

Output the times at which readings were saved and the saved values, in ascending order of time.

Constraints

  • 1 \le T \le 100
  • 1 \le X \le 100
  • 0 \le A_i \le 100
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T X
A_0 A_1 \dots A_T

Output

If k readings were saved, and the i-th saved reading in ascending order of time was at time t_i with value a_i, output in the following format:

t_1 a_1
t_2 a_2
\vdots
t_k a_k

Sample Input 1

6 10
30 35 40 21 30 12 31

Sample Output 1

0 30
2 40
3 21
6 31

The measurement proceeds as follows.

  • The reading at time 0 is 30. Save it.
  • The reading at time 1 is 35. The most recently saved reading is 30, and the absolute difference is less than 10, so it is not saved.
  • The reading at time 2 is 40. The most recently saved reading is 30, and the absolute difference is at least 10, so it is saved.
  • The reading at time 3 is 21. The most recently saved reading is 40, and the absolute difference is at least 10, so it is saved.
  • The reading at time 4 is 30. The most recently saved reading is 21, and the absolute difference is less than 10, so it is not saved.
  • The reading at time 5 is 12. The most recently saved reading is 21, and the absolute difference is less than 10, so it is not saved.
  • The reading at time 6 is 31. The most recently saved reading is 21, and the absolute difference is at least 10, so it is saved.