Codeforces 460D. Little Victor and Set

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 lxr;
  • 1 ≤ |S| ≤ k;
  • lets denote the i-th element of the set S as si; 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 ≤ lr ≤ 1012; 1 ≤ kmin(106, rl + 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.

Example

Note

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

题意简述

给出 $l、r、k$,在区间 $[l,r]$ 内选出不超过 k 个整数,使得这些数的异或和最小。

分析

首先,如果区间大小较小,可以直接暴力算出结果。

如果区间大小较大,按照 $k$ 的不同大小来考虑:

  • 如果 $k=1$,显然选择 $l$ 最优;
  • 如果 $k\ge 2$,因为区间较大,必然可以选出相邻的两个数使其异或和为 $1$;
  • 如果 $k\ge 4$,因为区间较大,必然可以选出两组异或和为 $1$ 的数对,四个数的异或和就为 $0$。

剩下的就是考虑 $k=3$ 时,是否存在一种方案使得三个数异或和为 $0$ 了。

假设对于一组解 $l\le c\lt b\lt a\le r$,且 $a\oplus b\oplus c = 0$,那么考虑 $a$ 在二进制下的最高位必然为 $1$,由于 $b\gt c$,所以 $b$ 的这一位也是事 $1$,而 $c$ 的这一位必然为 $0$。

再考虑后一位,如果 $c$ 的这一位为 $0$,那么必然可以将 $a、b$ 的这一位都设为 $1$,并将前一位设为 $0$。这样一来,$a、b$ 都缩小了但依然比 $c$ 大,因此 $a、b、c$ 还是一组合法的解。

直到 $c$ 在第二位上为 $1$ 时,因为 $a\gt b$,所以这一位上 $a$ 必然为 $1$,$b$ 必然为 $0$。至此,不论后面的数怎么改变,$a、b、c$ 的大小关系都不会再变动了,也就是说,我们可以让 $a$ 尽量小,$c$ 尽量大,通过改变 $b$ 来调整异或和。显然,我们可以贪心地将 $a$ 后面的位都调整为 $0$,将 $b、c$ 后面的位都调整为 $1$。这样调整之后,$a$ 变得更小,$c$ 变得更大,且满足 $c\lt b\lt a$,因此 $a、b、c$ 依然在区间 $[l,r]$ 内。

也就是说,对于任意一种可行方案,我们都可以将其改造成以上形式。且以上形式中 $c$ 一定可以被表示成 $2^n-1$,所以不同的总类数不超过 $\log_2 r$ 种,一一枚举即可。

发表评论