codeforces 460D：Little Victor and Set

Description

Little Victor adores the sets theory. Let us remind you that a set is a group of numbers where all numbers are pairwise distinct. Today Victor wants to find a set of integers S that has the following properties:

for all x the following inequality holds l ≤ x ≤ r;
1 ≤ |S| ≤ k;
lets denote the i-th element of the set S as s_i; value must be as small as possible.

Help Victor find the described set.

Input

The first line contains three space-separated integers l, r, k (1 ≤ l ≤ r ≤ 10¹²; 1 ≤ k ≤ min(10⁶, r - l + 1)).

Output

Print the minimum possible value of f(S). Then print the cardinality of set |S|. Then print the elements of the set in any order.

If there are multiple optimal sets, you can print any of them.

Examples

Input

8 15 3

Output

1
2
10 11

Input

8 30 7

Output

0
5
14 9 28 11 16

Note

Operation represents the operation of bitwise exclusive OR. In other words, it is the XOR operation.

正解：分类讨论

解题报告：

　　今天考试原题，直接上题解：

　　分类讨论。
　　首先注意到(2x) ⊕ (2x + 1) = 1。一个直接推论就是(2x) ⊕ (2x + 1) ⊕ (2x + 2) ⊕(2x + 3) = 0。而k ≥ 5的时候一定可以选出四个数其异或和为0(例如,如果l是偶数,那么选l, l + 1, l + 2, l + 3,否则选l + 1, l + 2, l + 3, l + 4。这样总是合法的,因为r ≥ l + 4)。
　　然后按照k的值分类讨论。
　　k = 1。答案就是l。
　　k = 2。如果r = l + 1,那么答案是min⁡(l ⊕ r, l),其中l表示只选一个数,l ⊕ r表示选两个数。否则答案一定为1。当r > l + 1的时候,如果l是偶数,那么答案是l ⊕ (l + 1),否则答案是(l + 1) ⊕ (l + 2)。
　　k = 3。答案不会超过1,因为从[l, r]中选两个数一定可以使得答案为1。我们关心的是三个数的异或和为0的情况。这3个数的最高位不可能相同(否则异或起来的最高位为1)。设这三个数为x, y, z(x < y <z),且y = 2 ^k + b, z = 2^ k + c, b < c。那么x ⊕ b ⊕ c = 0。为了让l ≤ x, y, z ≤ r,我们需要使得x尽量大而c尽量小。假设x ≥ 2 ^(k−1) ,那么可以推出z ≥ 2^( k−1) + 2^ k 。我们需要使x尽量大而c尽量小,那么令x = 2 ^(k − 1), z = 2 ^(k−1) + 2^ k ,可以得到y = z − 1。满足要求。那么如果x < 2^( k−1) 呢?我们会发现:此时z没必要≥ 2^ k ,因为取y = 2^( k−1 + b), z = 2 ^(k−1 )+ c依然满足条件。
　　所以枚举k并检查x = 2 ^k − 1, z = 2^ k + 2^( k−1) , y = z − 1这三个数是否在[l, r]内,如果在的话,就找到了一组解。
　　k = 4。如果r − l ≥ 4,那么答案一定为0。否则,枚举{x|x ∈ Z ∧ l ≤ x ≤ r}的所有子集,求异或和的最小值。

　　我的代码后面分类讨论部分写丑了。　　

 //It is made by jump~

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <algorithm>

 #include <ctime>

 #include <vector>

 #include <queue>

 #include <map>

 #include <set>

 using namespace std;

 typedef long long LL;

 LL l,r,len;

 int k;

 LL jilu1,jilu2,jilu3,num;

 inline int getint()

 {

     int w=,q=;

     char c=getchar();

     while((c<'' || c>'') && c!='-') c=getchar();

     if (c=='-')  q=, c=getchar();

     while (c>='' && c<='') w=w*+c-'', c=getchar();

     return q ? -w : w;

 }

 inline LL getlong()

 {

     LL w=,q=;

     char c=getchar();

     while((c<'' || c>'') && c!='-') c=getchar();

     if (c=='-')  q=, c=getchar();

     while (c>='' && c<='') w=w*+c-'', c=getchar();

     return q ? -w : w;

 }

 inline LL check(){

     LL t=;

     while( ((1LL<<t)-1LL) < l) t++;

     if(( (1LL<<t)+(1LL<<(t-1LL)) )<=r) return t;

     return -;

 }

 inline void work(){

     LL now;

     l=getlong(); r=getlong(); k=getint(); len=r-l+;

     if(k==) printf("%I64d 1\n%I64d",l,l);

     else if(k==) {

     if(l&) {

         if(r-l+==){

         if((l^r)<l)  printf("%I64d 2\n%I64d %I64d",l^r,l,r);

         else printf("%I64d 1\n%I64d",l,l);

         }

         else  printf("1 2\n%I64d %I64d",l+,l+);

     }

     else printf("1 2\n%I64d %I64d",l,l+);

     }

     else if(k==) {

     if((now=check())!=-) {

         printf("0 3\n"); printf("%I64d ",(1LL<<now)-1LL);

         printf("%I64d %I64d",(1LL<<now)+(1LL<<(now-1LL))-1LL, (1LL<<now)+(1LL<<(now-1LL) ) );

     }

     else { printf("1 2\n"); if(l&) printf("%I64d %I64d",l+,l+); else printf("%I64d %I64d",l,l+);  }

     }

     else{

     if(l&) {

         if(r-l+>) printf("0 4\n%I64d %I64d %I64d %I64d",l+,l+,l+,l+);

         else{

         now=l; num=; for(int i=;i<;i++) for(int j=i+;j<;j++) if( ((l+i)^(l+j)) < now) now=((l+i)^(l+j)),num=,jilu1=l+i,jilu2=l+j;

         if( (l^(l+)^(l+) ) < now) now=(l^(l+)^(l+) ),num=,jilu1=l,jilu2=l+,jilu3=l+; if( (l^(l+)^(l+) ) < now) now=(l^(l+)^(l+) ),num=,jilu1=l,jilu2=l+,jilu3=l+;

         if( (l^(l+)^(l+) ) < now) now=(l^(l+)^(l+) ),num=,jilu1=l,jilu2=l+,jilu3=l+; if( ((l+)^(l+)^(l+) ) < now) now=((l+)^(l+)^(l+)),num=,jilu1=l+,jilu2=l+,jilu3=l+;

         if( (l^(l+)^(l+)^(l+) ) < now) now=(l^(l+)^(l+)^(l+) ),num=;

         printf("%I64d %I64d\n",now,num); if(num==) printf("%I64d",now); else if(num==) printf("%I64d %I64d",jilu1,jilu2); else if(num==) printf("%I64d %I64d %I64d",jilu1,jilu2,jilu3); else printf("%I64d %I64d %I64d %I64d",l,l+,l+,l+);

         }

     }

     else printf("0 4\n%I64d %I64d %I64d %I64d",l,l+,l+,l+);

     }

 }

 int main()

 {

     work();

     return ;

 }

巴特西

codeforces 460D：Little Victor and Set

最新文章

热门文章