QQ扫一扫联系
数字变换
给定一个包含5个数字（0-9）的字符串，例如 “02943”，请将“12345”变换到它。 你可以采取3种操作进行变换
1. 交换相邻的两个数字
2. 将一个数字加1。如果加1后大于9，则变为0
3. 将一个数字加倍。如果加倍后大于9,则将其变为加倍后的结果除以10的余数。
最多只能用第2种操作3次，第3种操作2次 求最少经过多少次操作可以完成变换。
时间限制：1000
内存限制：65536
输入
有最多 100,000 组数据 每组数据就是包含5个数字的字符串
输出
对每组数据，输出将12345变换到给定字符串所需要的最少操作步数。如果无法变换成功，输出-1
样例输入
12435 99999 12374
样例输出
1 -1 3
提示
由于测试数据太多，如果对每组数据都从头进行搜索，就会超时。 建议先做预处理，即以“12345”作为初始状态做一遍彻底的广搜，找出“12345”经合法变换能够到达的所有字符串，并记录到达这些字符串各需要多少步操作。 然后对读入的每组数据，在上述预处理记录的结果中进行查询即可。
圣诞老人的礼物
圣诞节来临了，在城市A中圣诞老人准备分发糖果，现在有多箱不同的糖果，每箱糖果有自己的价值和重量，每箱糖果都可以拆分成任意散装组合带走。圣诞老人的驯鹿最多只能承受一定重量的糖果，请问圣诞老人最多能带走多大价值的糖果。
时间限制：1000
内存限制：65536
输入
第一行由两个部分组成，分别为糖果箱数正整数n(1 = n = 100)，驯鹿能承受的最大重量正整数w（0<w<10000），两个数用空格隔开。其余n行每行对应一箱糖果，由两部分组成，分别为一箱糖果的价值正整数v和重量正整数w，中间用空格隔开。
输出
输出圣诞老人能带走的糖果的最大总价值，保留1位小数。输出为一行，以换行符结束。
样例输入
4 15 100 4 412 8 266 7 591 2
样例输出
1193.0
忍者道具
忍者道具有很多种，苦无，飞镖，震爆弹。L君热衷于收集忍者道具，现在他有N个道具，每个道具的重量分别是C1、C2…CN。现在他想把这N个道具装到载重量为W的工具包里，请问他最少需要多少个工具包？
时间限制：1000
内存限制：65536
输入
第一行包含两个用空格隔开的整数，N和W。 接下来N行每行一个整数，其中第i+1行的整数表示第i个道具的重量Ci。
输出
输出一个整数，最少需要多少个工具包。
样例输入
5 1996 1 2 1994 12 29
样例输出
2
提示
对于100%的数据，1=N=18，1=Ci=W=10^8。
求逆序对问题
给定N个数的序列a1,a2,...aN，定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。
时间限制：1000
内存限制：256000
输入
本题有多个测试点，每个测试点分为两行：第一行为序列中数字的个数N（1 ≤ N ≤ 200000），第二行为序列a1, a2 ... aN(0 ≤a ≤ 10000000)，由空格分开。N=0表示输入结束。
输出
每个测试点一行，输出一个整数，为给序列中“重要逆序对”的个数。
样例输入
10
0 9 8 7 6 5 4 3 2 1
0
样例输出
16
提示
请注意答案范围，如果使用printf输出long long类型，请用%lld
