TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3375
  • 题目
  • P3375【2015重庆省队训练赛Round13】精明的壕
    限制 : 时间限制 : 50000 MS   空间限制 : 262144 KB
    问题描述

    众所周知,“土豪”是常见网络用语,指的是有钱、不理性消费、喜欢炫耀其财富的一类人,而“壕”是“土豪”的常见缩写。
    机缘巧合之下,nodgd成了壕。他有很多很多的钱,为了方便,他把他的钱存进了n张银票中,每张银票的里的前都是2的幂次,例如1元,4元,1024元,1048576元等等。nodgd觉得这样使用起来比较方便,任意价格的交易都可以用若干张银票来实现。不过nodgd有一个奇怪的癖好,一次交易坚决不会使用两张存款相等的银票。所以,任意价格的交易就都只有一种实现方式了。
    平时,nodgd的银票在家里整齐的放成了一叠,但是面值大大小小的没有什么顺序。有时候nodgd时间紧迫,随手从这一叠银票中抽出连续的一个子叠带在身上就出了门。有时候到需要用钱的时候nodgd突然发现自己无法拿出若干张面值互不相同的银票来达成这次交易,所以nodgd出门登车去时都要先清点一下手上的银票。nodgd是一个讲求效率的人,他要从他抽出的这一叠银票中选出一个子叠,设选出这一叠的价格最低的不能完成的交易的价格是A,银票的张数为B,则效率最高等价于最小。这个最小值nodgd当然知道怎么计算了,但是他想考考你。
    另外,nodgd是一个很有原则的人,每次抽出一叠银票使用后都会找一些面值与原来相等的银票原封不动地插入回原来的那一叠中。也就是说,家里那一叠银票是不会发生变化的。

    输入格式

    //输入文件C.in。
    第一行一个两个正整数n,m,表示银票张数,询问次数。
    第二行n个非负整数a1,a2,…,an,表示nodgd家里的那一叠银票从上到下面值依次是2a1,2a2,…,2an
    接下来m行,每行两个数L,R,表示nodgd这次出门时抽出了第L张到第R张银票。你要帮nodgd算出这时的最小值。

    输出格式

    //输出文件C.out。
    对每次询问输出一行,的最小值,保留8位小数输出。

    样例输入

    6 4
    2 0 1 3 0 2
    2 5
    2 6
    1 6
    3 4

    样例输出

    0.20000000
    0.11111111
    0.11111111
    1.00000000

    提示

    来源  by nodgd XieYutong搬运