# poj 3191 The Moronic Cowmpouter（负进制数转换）

Description

Inexperienced in the digital arts, the cows tried to build a calculating engine (yes, it’s a cowmpouter) using binary numbers (base 2) but instead built one based on base negative 2! They were quite pleased since numbers expressed in base −2 do not have a sign bit.

You know number bases have place values that start at 1 (base to the 0 power) and proceed right-to-left to base^1, base^2, and so on. In base −2, the place values are 1, −2, 4, −8, 16, −32, … (reading from right to left). Thus, counting from 1 goes like this: 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001, and so on.

Eerily, negative numbers are also represented with 1’s and 0’s but no sign. Consider counting from −1 downward: 11, 10, 1101, 1100, 1111, and so on.

Please help the cows convert ordinary decimal integers (range -2,000,000,000..2,000,000,000) to their counterpart representation in base −2.

Input

Line 1: A single integer to be converted to base −2

Output

Line 1: A single integer with no leading zeroes that is the input integer converted to base −2. The value 0 is expressed as 0, with exactly one 0.

Sample Input

Sample Output

Hint

Explanation of the sample:

# poj 3268 Silver Cow Party（spfa）

Language:
Silver Cow Party
 Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 20287 Accepted: 9289

Description

One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ XN). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse.

Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow’s return route might be different from her original route to the party since roads are one-way.

Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?

Input

Line 1: Three space-separated integers, respectively: N, M, and X
Lines 2..M+1: Line i+1 describes road i with three space-separated integers: Ai, Bi, and Ti. The described road runs from farm Ai to farm Bi, requiring Ti time units to traverse.

Output

Line 1: One integer: the maximum of time any one cow must walk.

Sample Input

Sample Output

Hint

Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 units), for a total of 10 time units.

# OpenJudge C15H:Lucky Draw（单调队列维护次小值）

In the Lucky village, people are crazy on a game called Lucky Draw. In this game, N players stand in a line, and each one is assigned an integer number. Then, the village master would randomly choose K continuous players. Among these K players, the one who has the largest number will win the first prize of A dollars. Also, the one with the second smallest number will win the second prize of B dollars. Different players may have same numbers. As an agreement, only the rightmost player who has the largest number owns the first prize, and the leftmost player who has the second smallest number owns the second prize. Note that the second smallest number should be greater than the smallest number. Therefore, if all of these K players have the same number, no one will win the second prize.

A big problem in this game is about fairness. Some players may have much more chance to win prizes than others. So, the village master wants to know how fair the game is. You should tell the village master how many players have the opportunity to win the prize. In addition, you need to calculate the variance of the expected prize moneys of these potential prize winners.

The second line contains N integers, indicate the numbers assigned to those players, listed from left to right. The numbers are guaranteed to fit in 32-bit signed integers.输出Output only one line containing an integer M and a real number V, separated by a single space. M is the number of players who have any chance to win the prize money. V is the variance of the expected prize money of these M players, rounded to four digits after the decimal point.样例输入

If players P1, P2, P3 are chosen, whose assigned numbers are 1 2 1, P2 wins 3 dollars.

If players P2, P3, P4 are chosen, whose assigned numbers are 2 1 3, P4 wins 1 dollar and P2 wins 2 dollars.

If players P3, P4, P5 are chosen, whose assigned numbers are 1 3 3, P5 wins 1 dollar and P4 wins 2 dollars.

If players P4, P5, P6 are chosen, whose assigned numbers are 3 3 3, only P6 wins 1 dollar.

P2, P4, P5 and P6 have a chance to win, and the expected prize moneys are 1.25, 0.75, 0.25 and 0.25 respectively.

The average expected prize money of these four players is 0.625 and the variance is 0.1719.