This page is still under construction.

Parts of this page are still being built. What you see may change.

Digital Speedometer

Interview

Time limit1sMemory limit1024 MB

Summary
Apply hysteresis thresholds to a stream of sensor speeds so the integer display only changes when a reading crosses past the rising or falling threshold.
Level

Medium4 of 10

Topics
Implementation, Simulation, Math, Array
Solved
No attempts yet

Problem

A digital speedometer shows a vehicle's speed as integer miles per hour. There are occasions when the sensed speed varies between two integer values, such as during cruise control. Using a single threshold to round between adjacent integers often makes the display toggle rapidly between the two integers, which is distracting to the driver.

Your team must implement a smoothing technique for the display using separate rising and falling thresholds (t_rt\_r and t_ft\_f, t_f<t_rt\_f < t\_r, respectively). See Figure 1 for a graphical depiction of the Sample Input for use with the following rules.

Figure 1: Sensor reading from the Sample Input, with t_f=0.25t\_f=0.25 and t_r=0.75t\_r=0.75.

Each sensed speed, ss, falls between two adjacent integers ii and jj, i≤s<ji \le s < j, where j=i+1j = i + 1. When displaying the sensed speed ss as an integer:

  • When ss falls between ii and i+t_fi+t\_f, ss is displayed as ii.
  • When ss falls between i+t_ri+t\_r and jj, ss is displayed as jj.
  • When ss falls between i+t_fi+t\_f and i+t_ri+t\_r, ss is displayed as ii if the most recent preceding value for ss outside of range \[i+t_f,i+t_r]\[i+t\_f, i+t\_r] is less than i+t_ri+t\_r, and ss is displayed as jj if the most recent preceding value for ss outside of range \[i+t_f,i+t_r]\[i+t\_f, i+t\_r] is greater than i+t_ri+t\_r.
  • Any sensed speed, 0<s<10 < s < 1, must display as 11 because any non-zero speed, no matter how small, must display as non-zero to indicate that the vehicle is in motion.

Input

The first line of input contains t_ft\_f, the falling threshold. The second line of input contains t_rt\_r, the rising threshold. The speed sensor reports ss in increments of 0.10.1 mph. The thresholds are always set halfway between speed increments. All remaining lines until end-of-file are successive decimal speeds, ss, in miles per hour, one speed per line. The third line of input, which is the first measured speed, will always be 00. There are at most 10001000 observed speeds ss in input. 0<t_f,t_r<1;    t_f<t_r;    0≤s≤1200 < t\_f,t\_r < 1; \ \ \ \ t\_f < t\_r; \ \ \ \ 0 \le s \le 120

Output

Output is the list of speeds, one speed per line, smoothed to integer values appropriate to t_ft\_f and t_rt\_r.

Hint

InputOutputExplanation
0.25Value of t_ft\_f.
0.75Value of t_rt\_r.
00Initial input.
2.02Input greater than 00, below threshold of 2.252.25.
5.75Input greater than 2.02.0, in threshold range.
5.86Input greater than 2.02.0, exceeds upper threshold of 5.755.75.
5.76Input less than 5.85.8, in threshold range.
5.25Input less than 5.85.8, below threshold of 5.255.25.
5.75Input greater than 5.25.2, in threshold range.
0.81Input greater than 00 and less than 11.
0.21Input greater than 00 and less than 11.

Examples1

  1. Example 1

    Input
    0.25
    0.75
    0
    2.0
    5.7
    5.8
    5.7
    5.2
    5.7
    0.8
    0.2
    
    Expected output
    0
    2
    5
    6
    6
    5
    5
    1
    1