###### 编程介的小学生

2019-04-22 15:11# 一个天气遇到的计算的运算的算法，怎么利用C语言的程序的设计的方式实现的

Problem Description

"Man, this year has the worst weather ever!", David said as he sat crouched in the small cave where we had sought shelter from yet another sudden rainstorm.

"Nuh-uh!", Diana immediately replied in her traditional know-it-all manner.

"Is too!", David countered cunningly. Terrific. Not only were we stuck in this cave, now we would have to listen to those two nagging for at least an hour. It was time to cut this discussion short.

"Big nuh-uh. In fact, 93 years ago it had already rained five times as much by this time of year."

"Duh", David capitulated, "so it's the worst weather in 93 years then."

"Nuh-uh, this is actually the worst weather in 23 years.", Diana again broke in.

"Yeah, well, whatever", David sighed, "Who cares anyway?".

Well, dear contestants, you care, don't you?

Your task is to, given information about the amount of rain during different years in the history of the universe, and a series of statements in the form "Year X had the most rain since year Y", determine whether these are true, might be true, or are false. We say that such a statement is true if:

The amount of rain during these two years and all years between them is known.

It rained at most as much during year X as it did during year Y.

For every year Z satisfying Y < Z < X, the amount of rain during year Z was less than the amount of rain during year X.

We say that such a statement might be true if there is an assignment of amounts of rain to years for which there is no information, such that the statement becomes true. We say that the statement is false otherwise.

Input

The input will consist of several test cases, each consisting of two parts.

The first part begins with an integer 1 <= n <= 50000, indicating the number of different years for which there is information. Next follow n lines. The ith of these contains two integers -109 <= yi <= 109 and 1 <= ri <= 109 indicating that there was ri millilitres of rain during year yi (note that the amount of rain during a year can be any nonnegative integer, the limitation on ri is just a limitation on the input). You may assume that yi < yi+1 for 1 <= i < n.

The second part of a test case starts with an integer 1 <= m <= 10000, indicating the number of queries to process. The following m lines each contain two integers -109 <= Y < X <= 109 indicating two years.

There is a blank line between test cases. The input is terminated by a case where n = 0 and m = 0. This case should not be processed.

Technical note: Due to the size of the input, the use of cin/cout in C++ might be too slow in this problem. Use scanf/printf instead. In Java, make sure that both input and output is buffered.

Output

There should be m lines of output for each test case, corresponding to the m queries. Queries should be answered with "true" if the statement is true, "maybe" if the statement might be true, and "false" if the statement is false.

Separate the output of two different test cases by a blank line.

Sample Input

4

2002 4920

2003 5901

2004 2832

2005 3890

2

2002 2005

2003 2005

3

1985 5782

1995 3048

2005 4890

2

1985 2005

2005 2015

0

0

Sample Output

false

true

maybe

maybe

- 点赞
- 回答
- 收藏
- 复制链接分享

*0*条回答

#### 为你推荐

- 这个问题除了循环运算以外，怎么才能优化C语言的算法实现？
- r语言
- Golang
- erlang
- 1个回答

- 表达式计算，利用符号运算的法则化简表达式，C语言的思路
- r语言
- Golang
- erlang
- 1个回答

- C语言关于一个运算法则的问题怎么才能解决呢，谢谢
- lines
- instance
- 算法
- 1个回答

- 求内存数据转整形的c算法
- c
- 算法
- 位运算
- 3个回答

- 生产者与消费者问题 ~
- 设计
- 面向对象
- 数据
- 3个回答