Problem I. Ignition

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Ignition timing, in a spark ignition internal combustion engine, is the process of setting the angle relative to piston position that a spark will occur in the combustion chamber near the end of the compression stroke. The need for timing the spark is because fuel does not completely burn the instant the spark fires, the combustion gasses take a period of time to expand, and the angular or rotational speed of the engine can lengthen or shorten the time frame in which the burning and expansion should occur. The angle is described as a certain angle advanced before top dead center (BTDC), measured in degrees. Advancing the spark BTDC means that the spark is energized prior to the point where the combustion chamber reaches its minimum size, since the purpose of the power stroke in the engine is to force the combustion chamber to expand. The ignition timing will need to become increasingly advanced as the engine speed increases so that the air-fuel mixture has the correct amount of time to fully burn.

Newer engines typically use computerized ignition systems. The computer has a timing map (lookup table) with spark advance values for various engine speeds, measured in rotations per minute (RPM). The computer will send a signal to the ignition coil at the indicated time in the timing map in order to fire the spark plug.

Since embedded computers used in ignition systems have limited memory, timing maps store advance values only for some engine speeds. Missing values are calculated by linear interpolation between two nearest stored values.

Your program is given:

  1. a timing map consisting of N pairs (ri; di), where ri is an engine speed, di — corresponding advance value;
  2. a list M of engine speeds ti.
It must calculate advance values for each speed. Values must be rounded down to the nearest integer.

Input file format

Input file contains integer N followed by N pairs of integers ri di and then by integer M and M integers ti.

Output file format

Output file must contain M integers ai — calculated advance values.

Constraints

2 ≤ N ≤ 100; 1 ≤ r1 < … rN ≤ 10000; 1 ≤ di ≤ 90;

1 ≤ M ≤ 100; r1 ≤ ti ≤ rN;

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2
1000 10  2000 20
1
1200
12
2
3
500 50 600 60 900 70
4
600 574 579 850
60 57 57 68

Explanation

В настоящей задаче участникам предлагалось вычислить значение кусочно-линейной функции в заданных точках. При этом следовало округлить результат вниз к ближайшему целому.

Для каждого из заданных значений аргумента функции следует сначала определить, к какому линейному участку заданной функции аргумент относится. Можно, например, перебрать все линейные участки простым циклом. Далее необходимо вычислить значение функции в предположении, что на участке она изменяется линейно. Задача может быть полностью решена в целых числах, для этого получившуюся формулу следует выразить таким образом, чтобы в ней имелось лишь одна операция деления. После этого, деление можно выполнить последним действием и сделать его целочисленным.


0.075s 0.010s 13