#P3575. [POI2014] DOO-Around the world

[POI2014] DOO-Around the world

题目描述

After trying hard for many years, Byteasar has finally received a pilot license.

To celebrate the fact, he intends to buy himself an airplane and fly around the planet 3-SATurn (as you may have guessed, this is the planet on which Byteotia is located).

Specifically, Byteasar plans to fly along the equator.

Unfortunately, the equator is rather long, necessitating refuels.

The flight range (on full tank) of each aircraft is known.

There is a number of airports along the equator, and a plane can be refueled when it lands on one.

Since buying an airplane is a big decision, Byteasar asks your help.

He is about to present you with a list of different plane models he is considering.

Naturally, these differ in their flight range.

For each plane model, he would like to know the minimum number of landings (including the final one) he would have to make in order to complete the journey.

Note that for each airplane model, the journey may start at a different airport.

通过几年的努力,Byteasar最终拿到了飞行员驾驶证。为了庆祝这一事实,他打算买一架飞机并且绕Byteotia星球赤道飞行一圈。但不幸的是赤道非常长所以需要中途加几次油。现在已知赤道上面所有飞机场,所有飞机从飞机场起飞降落也可以加油。因为买飞机是个十分重大的决定,Byteasar决定寻求你的帮助。他将会让你模拟不同的飞行路线。自然这些飞机一次能走的航程是不同的。对于每次模拟,他想要知道最少需要降落多少次(包括最后一次)。需要注意的是起点可以任意选取。

输入格式

The first line of the standard input contains two integers nn and ss (2n1 000 0002\le n\le 1\ 000\ 000, 1s1001\le s\le 100),separated by a single space, denoting the number of airports along the equator and the number of airplane models Byteasar is considering.

The second line contains nn positive integers l1,l2,,lnl_1,l_2,\cdots,l_n (l1+l2++ln109l_1+l_2+\cdots+l_n\le 10^9), separated by single spaces, specifying the distances between successive airports along the equator.

The number lil_i is the distance between the ii-th and (i+1)(i+1)-st (or nn-th and first if i=ni=n) in kilometers.

The third line contains ss integers d1,d2,,dsd_1,d_2,\cdots,d_s (1dil1+l2++ln1\le d_i\le l_1+l_2+\cdots+l_n), separated by single spaces. The number did_i is the ii-th airplane model's flight range in kilometers, i.e., the maximum distance it can fly before landing and refueling.

输出格式

Your program should print ss lines to the standard output: the ii-th of these should contain a single integer, namely, the minimum lumber of flight segments (and thus also landings) necessary to fly the ii-th airplane around the planet 3-SATurn along the equator, starting at an airport of choice, or the word NIE (Polish for no) if it is impossible to complete the journey with this airplane.

6 4
2 2 1 3 3 1
3 2 4 11

4
NIE
3
2

提示

通过几年的努力,Byteasar最终拿到了飞行员驾驶证。为了庆祝这一事实,他打算买一架飞机并且绕Byteotia星球赤道飞行一圈。但不幸的是赤道非常长所以需要中途加几次油。现在已知赤道上面所有飞机场,所有飞机从飞机场起飞降落也可以加油。因为买飞机是个十分重大的决定,Byteasar决定寻求你的帮助。他将会让你模拟不同的飞行路线。自然这些飞机一次能走的航程是不同的。对于每次模拟,他想要知道最少需要降落多少次(包括最后一次)。需要注意的是起点可以任意选取。