/ Vijos / 题库 /

教主的难题

教主的难题

描述

一个数x可以按以下规则生成数字:
1、将任意两位交换,若交换的数字为a和b,生成的代价为((a and b)+(a xor b))*2

例如134可以生成431,因为431可以从134的个位(4)与百位(1)交换后得到,代价为((1 and 4)+(1 xor 4))*2=10。

2、将其中一位数删除,但是删除的数要满足大等于它左边的数,且小等于它右边的数,并且定义最高位左边的数为个位,个位右边的数为最高位。若删除的数字为a,它左边的数为b,它右边的数为c,则生成的代价为a+(b and c)+(b xor c)。

例如212,可以删除百位的2得到12,或删除个位的数得到21,但是因为2>1,所以1是不能被删除的。特别地,若x为两位数,它能删除当且仅当x的两位数相同,若x为一位数,它是不能被删除的。

3、在两位数字之间,也可以是数字的前面或后面加入一位数,同样地,加入的数要满足大等于它左边的数,且小等于它右边的数,并且定义最高位左边的数为个位,个位右边的数为最高位。若加入的数字为a,它左边的数为b,它右边的数为c,则生成的代价为a+(b and c)+(b xor c)。

例如241,它可以在2与4之间加入一个3,生成2341,也可以在数的末尾加入一个1或者2,当然还有其它可以生成的数,但是不能在4和1之间加入数字。

你的任务是,S一开始为n个不同的给定数组成的集合,每次可以从S中取出一个数生成一个满足生成规则的数加入S中,并且取出的数仍然存在于S中。生成的数的位数不能大于S初始集合最大的数的位数。问在S元素最多的情况下,总代价最小是多少。

格式

输入格式

输入的第1行为一个正整数n,为集合S初始元素个数。

第2行包含n个正整数a1,a2, ..., an,数之间空格隔开,为S中初始元素。

输出格式

输出包括一个正整数,为最小代价。

样例1

样例输入1

2
111 22

样例输出1

12

限制

对于20%的数据,有ai<100;
对于40%的数据,有ai<1000;
对于50%的数据,有n=1;
对于60%的数据,有ai<10000;
对于100%的数据,有ai<100000,n≤5,保证的任何一位不包含0。

时限1s

提示

111删除1得到11,代价为2,11删除1得到1,代价为2,总代价2+2=4。111无法生成1111因为n=111为一个3位数,而1111为一个4位数。

利用交换/添加规则无法得到更多不同的数,所以最小代价为2+2=4。

信息

ID
1422
难度
6
分类
搜索 | 树结构 | 生成树 点击显示
标签
递交数
405
已通过
115
通过率
28%
上传者