Intervals

You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.
Write a program that: reads the number of intervals, their end points and integers c1, ..., cn from the standard input, computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,...,n,
writes the answer to the standard output.

Input

The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.

Output

The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,...,n.

Sample Input

5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

Sample Output

6

Source

Southwestern Europe 2002

题目类型：差分约束系统

算法分析：设Si表示集合Z中小于等于i的元素个数，则可由输入得到差分方程组Sai-1 - Sbi <= -Ci。Si还满足0 <= Si - Si-1 <= 1，则可得到方程组Si - Si-1 <= 1和Si-1 - Si <= 0，最后建图跑一个spfa即可

Burn the Linked Camp

It is well known that, in the period of The Three Empires, Liu Bei, the emperor of the Shu Empire, was defeated by Lu Xun, a general of the Wu Empire. The defeat was due to Liu Bei's wrong decision 阅读全文 »

Ouroboros Snake

Ouroboros is a mythical snake from ancient Egypt. It has its tail in its mouth and continously devours itself. The Ouroboros numbers are binary numbers of 2^n bits that have the property of "generating" the whole set of numbers from 0 to 2^n - 1. The generation works as follows: given an Ouroboros number, we place its 2^n bits wrapped in a circle. Then, we can take 2^n groups of n bits starting each time with the next bit in the circle. Such circles are called Ouroboros circles for the number n. We will work only with the smallest

Ouroboros number for each n.

Example: for n = 2, there are only four Ouroboros numbers. These are 0011;0110;1100; and 1001. In this case, the smallest one is 0011. Here is the Ouroboros circle for 0011:
The table describes the function o(n;k) which calculates the k-th number in the Ouroboros circle of the smallest Ouroboros number of size n. This function is what your program should compute.

Input

The input consists of several test cases. For each test case, there will be a line containing two integers n and k (1<=n<=15; 0<=k<2^n). The end of the input file is indicated by a line containing two zeros. Don抰 process that line.

Output

For each test case, output o(n;k) on a line by itself.

Sample Input

2 0

2 1

2 2

2 3

0 0

Sample Output

0

1

3

2

Source

Mid-Central European Regional Contest 2000

题目类型：欧拉回路

算法分析：这是经典的旋转鼓轮问题，构造出序列后直接从第k位二进制开始构造n位十进制即可

Code

KEY Inc., the leading company in security hardware, has developed a new kind of safe. To unlock it, you don't need a key but you are required to enter the correct n-digit code on a keypad (as if this were something new!). There are several models available, from toy safes for children (with a 2-digit code) to the military version (with a 6-digit code).

The safe will open as soon as the last digit of the correct code is entered. There is no "enter" key. When you enter more than n digits, only the last n digits are significant. For example (in the 4-digit version), if the correct code is 4567, and you plan to enter the digit sequence 1234567890, the door will open as soon as you press the 7 key.

The software to create this effect is rather simple. In the n-digit version the safe is always in one of 10^n-1 internal states. The current state of the safe simply represents the last n-1 digits that have been entered. One of these states (in the example above, state 456) is marked as the unlocked state. If the safe is in the unlocked state and then the right key (in the example above, 7) is pressed, the door opens. Otherwise the safe shifts to the corresponding new state. For example, if the safe is in state 456 and then you press 8, the safe goes into state 568.

A trivial strategy to open the safe is to enter all possible codes one after the other. In the worst case, however, this will require n * 10ⁿ keystrokes. By choosing a good digit sequence it is possible to open the safe in at most 10ⁿ + n - 1 keystrokes. All you have to do is to find a digit sequence that contains all n-digit sequences exactly once. KEY Inc. claims that for the military version (n=6) the fastest computers available today would need billions of years to find such a sequence - but apparently they don't know what some programmers are capable of...

Input

The input contains several test cases. Every test case is specified by an integer n. You may assume that 1<=n<=6. The last test case is followed by a zero.

Output

For each test case specified by n output a line containing a sequence of 10ⁿ + n - 1 digits that contains each n-digit sequence exactly once.

Sample Input

1

2

0

Sample Output

0123456789

00102030405060708091121314151617181922324252627282933435363738394454647484955657585966768697787988990

Source

Ulm Local 2004

题目类型：欧拉回路

算法分析：这是旋转鼓轮问题的一个直接应用，将两个相邻密码序列的前一个的后n-1位和后一个的前n-1位看作是一个顶点，边的id为0~10^n。这里直接dfs会爆栈，所以需要手动模拟dfs，对于建好的图按照顺序遍历输出。由于这里的图是按照从大到小的方向建的，所以最后直接倒着输出即可