acm2011年长春赛区题目

The 2013 ACM/ICPC Asia Changchun Regional Contest

A. Hard Code

Description

Some strange code is sent to Da Shan High School. It's said to be the prophet's note. The note is

extremely hard to understand. However, Professor Meng is so smart that he successfully found

the pattern of the code. That is, the length of the code is the product of two prime numbers. He

tries to reallocate the code into a grid of size N*M, where M is the bigger prime. In specific, he

writes down the letters of the code to the cells one by one, from left to right, and from top to

button. In this way, he found the code eventually readable.

lowercase letters. It’s guaranteed the length of the string equals to N * M.

Output

For each test case, output N lines, each line with M letters representing the readable code after

the reallocation.

Sample Input

1

2 5

klmbbileay

Sample Output

klmbb

The 2013 ACM/ICPC Asia Changchun Regional Contest

B. Golden Radio Base

Background

that includes the digit sequence "11" can always be rewritten in standard form, using the

algebraic properties of the base φ — most notably that φ + 1 = φ

2

. For instance, 11(φ) = 100(φ).

Despite using an irrational number base, when using standard form, all on-negative integers have

a unique representation as a terminating (finite) base-φ expansion. The set of numbers which

possess a finite base-φ representation is the ring Z[1 + √5/2]; it plays the same role in this

numeral systems as dyadic rationals play in binary numbers, providing a possibility to multiply.

Other numbers have standard representations in base-φ, with rational numbers having recurring

representations. These representations are unique, except that numbers (mentioned above)

with a terminating expansion also have a non-terminating expansion, as they do in base-10; for

There are multiple test cases. Each line of the input consists of one positive integer which is not

larger than 10^9. The number of test cases is less than 10000. Input is terminated by

end-of-file.

Output

For each test case, output the required answer in a single line. Note that trailing 0s after the

decimal point should be wiped. Please see the samples for more details.

The 2013 ACM/ICPC Asia Changchun Regional Contest

Sample Input

1

2

3

1010.0001

10100.0101

Hint

Besides φ + 1 = φ

2,

, we have another useful property of GRB, i.e., 2 * φ

2

= φ

3

The 2013 ACM/ICPC Asia Changchun Regional Contest

C. Little Tiger vs. Deep Monkey

Description

A crowd of little animals is visiting a mysterious laboratory – The Deep Lab of SYSU.

“Are you surprised by the STS (speech to speech) technology of Microsoft Research and the cat

face recognition project of Google and academia? Are you curious about what technology is

behind those fantastic demos?” asks the director of the Deep Lab. “Deep learning, deep

The test is composed of N binary choice questions. And different questions may have different

chooses the correct answer; otherwise, he gets nothing. The overall score is counted as the sum

of scores one gets from each question. The one with a larger overall score wins; tie happens

when they get the same score.

Little Tiger assumes that Deep Monkey will choose the answer randomly as he doesn’t believe

the monkey is smart. Now, Little Tiger is wondering “what score should I get at least so that I will

not lose in the contest with probability of at least P? ”. As little tiger is a really smart guy, he can

evaluate the answer quickly.

You, Deep Monkey, can you work it out? Show your power!

Input

The first line of input contains a single integer T (1 ≤ T ≤ 10) indicating the number of test cases.

The 2013 ACM/ICPC Asia Changchun Regional Contest

Output

For each test case, output only a single line with the answer.

Sample Input

1

3 0.5

1 2 3

Sample Output

3