tceic.com

# 国家集训队2009论文集浅谈数位类统计问题

【摘要】

【关键字】

【正文】

【例题 1】Amount of degrees (ural 1057)

int calc(int x,int k)//统计[0..x]内二进制表示含k个1的数的个数 { int tot=0,ans=0;//tot记录当前路径上已有的1的数量,ans表示答案 for (int i=31;i>0;--i) { if (x&(1<<i)) { ++tot; if (tot>k) break;

x=x^(1<<i); } if ((1<<(i-1))<=x) { ans+=f[i-1][k-tot]; } } if (tot+x==k) ++ans; return ans; }

【例题 2】Sorted bit sequence (spoj 1182)

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 0000 0000 0000 0000 0000 0000 0000 0010 0000 0000 0000 0000 0000 0000 0000 0100 0000 0000 0000 0000 0000 0000 0000 0011 0000 0000 0000 0000 0000 0000 0000 0101

1111 1111 1111 1111 1111 1111 1111 1100 1111 1111 1111 1111 1111 1111 1111 1011 1111 1111 1111 1111 1111 1111 1111 1101 1111 1111 1111 1111 1111 1111 1111 1110

【例题 3】Sequence (spoj 2319)

【例题 4】Tickets (sgu 390)

L

R

【例题 5】Graduated Lexicographical Ordering (zju 2599)

【总结】

【感谢】

【附录】

Create a code to determine the amount of integers, lying in the set [X;Y] and being a sum of exactly K different integer degrees of B. Example. Let X=15, Y=20, K=2, B=2. By this example 3 numbers are the sum of exactly two integer degrees of number 2: 17 = 24+20, 18 = 24+21, 20 = 24+22.

Input
The first line of input contains integers X and Y, separated with a space (1 ≤ X ≤ Y ≤ 2311). The next two lines contain integers K and B (1 ≤ K ≤ 20; 2 ≤ B ≤ 10).

Output

Output should contain a single integer — the amount of integers, lying between X and Y, being a sum of exactly K different integer degrees of B.

Sample
Input: 15 20 2 2 Output: 3

Let's consider the 32 bit representation of all integers i from m up to n inclusive (m ≤ i ≤ n; m × n ≥ 0, -2^31 ≤ m ≤ n ≤ 2^31-1). Note that a negative number is represented in 32 bit Additional Code. That is the 32 bit sequence, the binary sum of which and the 32 bit representation of the corresponding positive number is 2^32 (1 0000 0000 0000 0000 0000 0000 0000 0000 in binary). For example, the 32 bit representation of 6 is 0000 0000 0000 0000 0000 0000 0000 0110 and the 32 bit representation of -6 is 1111 1111 1111 1111 1111 1111 1111 1010 because 0000 0000 0000 0000 0000 0000 0000 0110 (6) + 1111 1111 1111 1111 1111 1111 1111 1010 (-6) ------------------------------------------------= 1 0000 0000 0000 0000 0000 0000 0000 0000 (2^32) Let's sort the 32 bit representations of these numbers in increasing order of the number of bit 1. If two 32 bit representations that have the same number of bit 1, they are sorted in lexicographical order. For example, with m = 0 and n = 5, the result of the sorting will be

No. 1 2 3 4 5 6

Decimal number Binary 32 bit representation 0 1 2 4 3 5 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001 0000 0000 0000 0000 0000 0000 0000 0010 0000 0000 0000 0000 0000 0000 0000 0100 0000 0000 0000 0000 0000 0000 0000 0011 0000 0000 0000 0000 0000 0000 0000 0101

with m = -5 and n = -2, the result of the sorting will be No. 1 2 3 4 Decimal number Binary 32 bit representation -4 -5 -3 -2 1111 1111 1111 1111 1111 1111 1111 1100 1111 1111 1111 1111 1111 1111 1111 1011 1111 1111 1111 1111 1111 1111 1111 1101 1111 1111 1111 1111 1111 1111 1111 1110

Given m, n and k (1 ≤ k ≤ min{n m + 1, 2 147 473 547}), your task is to write a program to find a number corresponding to k-th representation in the sorted sequence.

Input
The input consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 1000. The following lines describe the data sets. For each data set, the only line contains 3 integers m, n and k separated by space.

Output
For each data set, write in one line the k-th number of the sorted numbers.

Example
Sample input: 2 053 -5 -2 2 Sample output: 2 -5

You are given the sequence of all K-digit binary numbers: 0, 1,..., 2K-1. You need to fully partition the sequence into M chunks. Each chunk must be a consecutive subsequence of the original sequence. Let Si (1 ≤ i ≤ M) be the total number of 1's in all numbers in the ith chunk when written in binary, and let S be the maximum of all Si, i.e. the maximum number of 1's in any chunk. Your goal is to minimize S.

Input
In the first line of input, two numbers, K and M (1 ≤ K ≤ 100, 1 ≤ M ≤ 100, M ≤ 2^K), are given, separated by a single space character.

Output
In one line of the output, write the minimum S that can be obtained by some split. Write it without leading zeros. The result is not guaranteed to fit in a 64-bit integer.

Example
Input: 34 Output: 4

Conductor is quite a boring profession, as all you have to do is just to sell tickets to the passengers. So no wonder that once upon a time in a faraway galaxy one conductor decided to diversify this occupation. Now this conductor sells several tickets at a time to each passenger. More precisely, he successively gives tickets to the passenger until the sum of the digits on all the tickets given becomes not less than some integer number k. Then this process repeats for the next passenger. Initially conductor has a tape of tickets numbered successively from l to r, inclusive. This way of tickets distribution is quite good, because passengers are glad to get several tickets when they pay only for one. But there is one disadvantage. Since each passenger gets several tickets, it is possible

that conductor won't be able to serve all passengers. Your task is to help conductor in this difficult situation. You should calculate how many passengers is the conductor able to serve.

Input
Input file contains three integer numbers l, r and k (1 ≤ l ≤ r ≤ 1018 , 1 ≤ k ≤ 1000) .

Output
Output should contain exactly one number — the answer to the problem. Sample input 40 218 57 Sample output 29

Consider integer numbers from 1 to n. Let us call the sum of digits of an integer number its weight. Denote the weight of the number x as w(x). Now let us order the numbers using so called graduated lexicographical ordering, or shorter grlex ordering. Consider two integer numbers a and b. If w(a) < w(b) then a goes before b in grlex ordering. If w(a) = w(b) then a goes before b in grlex ordering if and only if the decimal representation of a is lexicographically smaller than the decimal representation of b. Let us consider some examples.

120 < grlex4 since w(120) = 1 + 2 + 0 = 3 < 4 = w(4). 555 < grlex78 since w(555) = 15 = w(78) and "555" is lexicographicaly smaller than "78". 20 < grlex200 since w(20) = 2 = w(200) and "20" is lexicographicaly smaller than "200".

Given n and some integer number k, find the position of the number k in grlex ordering of integer numbers from 1 to n, and the k-th number in this ordering.

Input

There are several lines in the input file, and each line stands two integers n and k (1 <= k <= n <= 1018). A line with n = k = 0 ends up the input.

Output
For each line in the input, output one line in the output file. First print the position of the number k in grlex ordering of integer numbers from 1 to n, and then the integer that occupies the k-th position in this ordering. Sample Input 20 10 00 Sample Output 2 14