/ OIer TK / 题库 /

Cai0715的花园

Cai0715的花园

测试数据来自 system/1689

背景

为了帮助菌国的百姓,不让他们受病毒的折磨。同是也为了击退小毒物的攻击。嘟嘟受到高人(不,是高菌~)的指示,要去采花,用花粉来制造解药。于是,他找到了cai0715,希望获得他的帮忙。Cai0715说,要我帮忙可以,不过先答对我的问题吧。

描述

Cai0715拥有一个花园,这个花园非常的小,把它看作棋盘的话,只有3*3个格子的大小。初始时每个格子都是没有花的,所以需要种一些花卉使得花园变得美丽一点。

现在,Cai0715的手上有四种类型的花,杜鹃花、山茶花、牡丹花、水仙花,每种类型的花都拥有一个美丽值且无限量供应。你可以按照下面的规则种花。

1、你可以在任意格子种植杜鹃花。

2、如果想种植山茶花,则当时与它相邻的某个格子里必须有杜鹃花。

3、如果想种植牡丹花,则当时与它相邻的某个格子里必须有杜鹃花和山茶花。

4、如果想种植水仙花,则当时与它相邻的某个格子里必须有杜鹃花、山茶花和牡丹花。

5、每个格子不能同时栽种两种花。

6、如果两个格子相邻,当且仅当它们拥有一条公共边。

7、每种植一次花,需要花费单位1的时间。

8、你可以在任意时刻铲除某个格子的花,不需要花费时间。

现在,给定你每种花的美丽值,让你求出最少需要多少时间,可以使得花园的美丽值不低于Cai0715要求的最低美丽值W。如果怎样都无法达到,请输出Impossible。(花园的美丽值=Sum[每个格子中花的美丽值])

格式

输入格式

第一行1个数,N,代表共有N个测试点。

以下N行,每行5个数,Wb,Wr,Wg,Wy,W,分别代表杜鹃花、山茶花、牡丹花、水仙花的美丽值和Cai0715要求的最低美丽值。

输出格式

共N行,每行一个数,最少需要的时间,或Impossible。

样例1

样例输入1

4
1 1 1 1 3
1 2 4 8 21
1 1 1 100 500
7 20 53 94 395

样例输出1

3
7
Impossible
11

限制

各个测试点2s

提示

对于 30% 的测试数据,1<=Wb,Wr,Wg,Wy<=100,W<=100,N<=1。

对于 60% 的测试数据,1<=Wb,Wr,Wg,Wy<=10^8,W<=10^8,N<=10。

对于 100% 的测试数据,1<=Wb,Wr,Wg,Wy<=10^8,W<=10^8,N<=1000。

注意时限是2S

信息

ID
1636
难度
(无)
分类
动态规划 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者