Description

Writer: jjjjj19980806       Description: pclightyear        Difficulty: ★★★☆☆

In mathematics, a Markov matrix is a square matrix used to describe the transitions of a Markov chain. Each of its entries is a nonnegative real number representing a probability. It has found use throughout a wide variety of scientific fields, including population genetics.

Consider a country with n cities. Originally, each city has its own population, which can be described as a state vector X₀. As the time pass by, the population will move from one city to another. The whole progress can be described as a n × n Markov matrix A.

In this problem, if the state vector of the city population now is X_n, after a year, the state vector will become X_n+1, where X_n+1 = AX_n.

Now, you are given the original population in each city by a state vector X₀ and the Markov matrix A. You need to calculate how many years it takes to let the first city’s population to drop below or equal to a specific number p, or it will never drop below p.

Input

The first line contains an integer T, representing the number of test cases.

For each test case:

The first line contains an integer n, representing the number of the cities.

The next n lines contain n floating-point number a_ij, representing each entry in the Markov matrix A.

The next line contains n integers X_i, representing each entry in the state vector X₀.

The next line contains an integer p, representing the specific number of population.

It is guaranteed that:

• 1 ≤ T ≤ 5
• 1 ≤ n ≤ 5
• 0 ≤ X_0i ≤ 10⁶

Output

Please output how many years it takes to let the first city’s population to drop below p, or output "Never" if it will never drop below p.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Writer: jjjjj19980806       Description: pclightyear        Difficulty: ★★★☆☆

Given n numbers, you need to find a number k such that SUM is minimum,

where we define SUM = ( a1 ^ k ) + ( a2 ^ k ) + ... + ( an ^ k )

(^ stands for the "xor" bitwise operation of the two operand)

Input

The first line contains an integer n, representing the number of numbers.

The next line contains n integers ai, representing each given number.

It is guaranteed that:

• n ≤ 10⁵
• 0 ≤ ai ≤ 10⁶
• All numbers ( ai and k ) are unsigned numbers

Output

Please output the value of SUM.

Note SUM may exceed INT.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Ovuvuevuevue Enyetuenwuevue Ugbemugbem Osas is a shopaholic.

There are n different items in a store and Osas wants to buy every of them.

The i-th item cost a_i dollars, but the price fluctuates greatly recently.

Tomorrow the i-th item's price will be b_i dollars. Osas has an special ability that he can know the price tomorrow.

Because he's a shopaholic, he wants to buy every items in at most two days. Osas must buy at least k item at first day, or he will be crazy.

Help Osas find out the minimum money he should pay to buy every kinds of item in the shop.

Input

Input contains third lines.

First line contains two integer n ( 1 <= n <= 10⁵ ) and k ( 0 <= k <= n ).

Second line contains n integer a₁ ~ a_n ( 1 <= a_i <= 10⁵).

Third line contains n integer b₁ ~ b_n ( 1 <= b_i <= 10⁵ ).

Output

Output only contains one integer -- the minimum price Osas needs to pay.

remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

"Wow! Look at that youbike! It's so fasion...."

"Hey! Look! Is he.... is he the famous "The king on Akina Mount"(秋名山車神)...? The one who dominates all youbikers on Akina Mount? No way!"

-----------------------------------------------------------

The world's largest youbike racing contest is holding in NTHU. All the best youbike racers come to this place, including "The king on Akina Mount" !!! But now, he has several problems to solve......

Due to youbikes cannot afford really high speed for too long since the components might break and racers would be in danger, so the race commitee sets up several checkpoints along the contest track. Every racer can choose to change a totally new youbike and go, or just pass the checkpoint without changing a new one.

For The king on Akina Mount (we'll just call him "the king" in convenience), his speed is the fastest without any doubt. However, his youbike might break, too. But changing another youbike also takes time, we call it "penalty". The king wants to minimize the penalty, so that he could win this race. He ask you, the legendary mechanic, for help!

• The youbike race begins at position 0, ends at the endpoint. 
• While arriving each checkpoint, you can choose either to change a new youbike or continue with the original one. 
• Each youbike has the same damage degree k, and the damage degree will decrease 1 every 1 distance. Changing a new one means reset the damage degree to k. When the damage degree is lower than 0, the youobike breaks and the king loses. 
• Initially, the king is at position 0, and he's riding a totally new youbike, which means the damage degree is initially k.
• Given the position of every checkpoint and the location of endpoint, your task is to find out the minimum number of changing a new youbike. If he cannot reach the end, just output "The Legend Falls."

Sweet caution:

Do not break the speed when riding youbike.

Input

The first line contains two positive integers, n, k.

The second line contains n positive integers indicate the position of every checkpoint. The position has been sorted in ascending order. The last station indicates the endpoint.

The track is a straight line, and every checkpoint is on the right side of the initial position "0".

1<= n, k <= 100000, the distance between every consecutive checkpoints will not exceed 100000.

0 <= the position of checkpoints <= 2^31-1.

Output

Output the minimum penalty, or "The Legend Falls." if the king cannot reach the end.

Take the sample IO as an example, a new youbike can ride at most 5 unit long. The king will change another youbike at stations locate at 4 and 9, and finally reach the end point(14). 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Attention: This problem uses partial judge to judge your answer!

One day, Knuckles is on his way for finding his queen. He encounters an old wizard, murmuring "You shall not....You shall not....". Knuckles decides to ignore the crazy wizard and continues his journey. Suddenly, that old crazy wizard blocks his way and says "YOU SHALL NOT PASS!!!"
The wizard, who is actually the legendary wizard Gandalf, is guarding this path. But Knuckles dones't care much. What he only cares is that the old man just blocks his way to his queen, which makes him very mad, and launches a duel to Gandalf.
This is a real man duel for spitter to wizard, sputum to magic spell, mysterious creature to man, legend to legend, a duel that whoever wins will change the whole world...... .
After minutes of fighting, they both feel tired, so they makes an agreement: Gandalf will cast his strongest spell to attack, and Knuckles needs to defend it. If Knuckles defends successfully, Knuckles wins; otherwise,  Gandalf wins.
Gandalf will cast a spell "Pegasus Meteor Spell(天馬流星咒)". The spell will summon meteors from Pegasus and hit the ground hardly. The meteors will hit in a n*n square range. Knuckles needs to stop all the meteors, otherwise he'll be hit and lose the fight. 
Knuckles will use "Sputum of the North Star(北斗神痰)" to defend. He will spit k sputum. Each time he spit, the next sputum will be more powerful. In other word, the power of sputums is sorted in ascending order. 
He's going to spit on every meteor that falls onto the ground. The power of his sputum must be equal to or more powerful than the meteor he spits to destroy the meteor. If he spits a sputum that is weaker than the target meteor, the meteor will directly fall onto Knuckles' head and he'll lose. That is, each meteor can be spitted only once.
Knuckles will give you n, k, the power of each meteor and where will it fall, the sequence of the power of his sputum. You're going to tell him if he could win this fight or not.

• There are some meteors falling in a n*n area. The meteor's power of section (i,j) is denoted as "M(i,j)". There's no meteor if M(i,j) = 0. 
• You have a sequence of sputum denoted as "S(i)", sorted in ascending order.
• If any sputum S(i) >= M(j,k), meteor M(j,k) can be destroyed by sputum S(i). At the same time, the sputum S(i) will be brken, too, which means that you can only use one sputum once. 
• If all of the meteors can be destroyed (which means all elements in M are 0), Knuckles wins. Otherwise, he loses.

Input

The first line contains two positive integer n and k.
The next n lines, each line contains exactly n numbers, indicating the power of the meteors which will fall onto this place. 0 means no meteor will fall on this place.
The last line contains k numbers, which indicate the power of every sputum. As the description says, the power will be in ascending order.
1 <= n <= 100, 1 <= k <= n*n, and the power of meteors and the power of sputums will be in range [1,10000].

Output

You should output only one line. If Kunckles wins, output "Victory belongs to the Spitters!", otherwise output "Fly you fool."

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

This is a bonus problem. You can get 2 total points at most if you solve this problem.

After rain comes sunshine and rainbow.

5/17 is the International Day Against Homophobia, Transphobia and Biphobia(國際不再恐同日), which is also the day that legislative committees trial the special law about LGBT. They eventually pass a draft that fully in line with the referendum, which make Taiwan be the first Asia country that pass a law for LGBT.

Knuckles is on his way of finding his queen. When he arrived Taiwan and see a lot of rainbow flags, he wondered that these rainbow flags might be a clue of the location of his queen. He will give some operations about these flags, you are going to help him, or he'll spit on you.

• There are colors on these flags. The colors include: "Red", "Orange", "Yellow", "Green", "Blue", "Purple", which are the color of rainbow.

• Knuckles has a sequence of colors. Initially, the sequence is empty.

• Knuckles has several operations: insert, erase1, erase2, reverse, show.

  • insert <color> <dest>: means insert <color> after the location of <dest>. For example, insert Yellow 5 means insert a "Yellow" after the 5-th location. If <dest> is larger than the length of the sequence, just regard it as the last location of the sequence.

  • erase1 <dest>: means erase the color locates at <dest>. For example, erase1 4 will erase the 4-th color in the sequence. If <dest> is larger than the length of the sequence, just regard it as the last location of the sequence.

  • erase2 <color>: means erase all <color> in the sequence. For example, erase2 Purple will erase all the "Purple" in the sequence. After the operation, There should be no "Purple" in the sequence.

  • reverse <dest1> <dest2>: means reverse the elements from <dest1> to <dest2>. If the order was originally {"Yellow", "Purple", "Blue"}, after reversing, the order should become {"Blue", "Purple", "Yellow"}. If <dest1> or <dest2> is larger than the length of the sequence, just regard it as the last location of the sequence.

  • show: show the sequence according to the order.

You are going to implement a linked list that support these operations. We have implemented show operation, what you have to do is to implement the remaining operations: insert, erase1, erase2, reverse.

Input

The first line contains an integer n, indicates the number of operations.

There are n lines below. Each line contains one operations described above.

<color> will only appear the 6 colors described above.

insert: 0 <= <dest> <= 10000

erase1: 1 <= <dest> <= 10000

reverse: 1 <= <dest1>, <dest2> <= 10000

1 <= n <= 5000

Output

When show operation is called, you should output the correct sequence after operating.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss