Anubis is worried, french soldiers are practicing target shooting with cannonballs on the sphinxes again! This time he will try to stop that the other parts of the sphinx will have the same fate as its nose.
To stop the cannons, he can summon thunderbolts that destroy everything they touch, including cannonballs. But Egyptian gods do not have as much followers as they once had, and that limits their powers.
Anubis can only summon thunderbolts in a specific moment of time. Luckily, this moment is the same moment the cannonballs are in the air. Anubis will use this chance to destroy the maximum possible number of cannonballs.
To summon the bolts, Anubis needs to temporarily shift to our plane of existence. Therefore, he can only hit targets that are in the same plane.
Help Anubis destroy the greatest possible number of cannonballs.
The first line has a single integer N, the number of cannonballs. Each of the next N lines has 3 integers xi, yi and zi, the position of the ith cannonball in the moment Anubis can summon the thunderbolts.
Limits
Print a single integer, the greatest number of cannonballs Anubis can destroy.
3
0 0 0
0 0 0
0 0 0
3
3
0 0 0
1 1 1
2 2 2
3
4
1 0 0
0 1 0
0 0 1
1 1 1
3
Not many people know, but it was in Ancient Egypt that the first banks were created. The main bank was the pharaoh's, who decided, from time to time, to seize some accounts.
Given N, the number of accounts in the Pharaoh's Bank (that was its name), each account had an amount of money in menes (old Egyptian coin) that could be positive or negative (negative means they owe that quantity to the bank), that is, each account can be represented by an integer ai.
The pharaoh could only take accounts from a continuous segment, that is, he can take all accounts i, i + 1, ..., j, for some i ≤ j. So the pharaoh is interested in knowing, for some intervals [L, R] (corresponding to accounts aL, aL + 1, ..., aR), what is the continuous subsegment of maximum sum, that is, which segment he can seize to get the greatest amount of money.
This was explained to the clients as being an offering to Amon-Ahcid, the Egyptian god of money. Doing constant offerings, the god would be pleased and allow the economic system to prosper. This, surprisingly, lasted for more than 500 years, until in one of these seizes the clients rebelled, took the palace, and killed the pharaoh. The bank was sacked and the system collapsed. Banks were only heard of again centuries later.
Your task is, given a record of the accounts and some queries, answer for each one the subsegment of maximum sum, and its size.
The first line has a single integer N, the number of accounts. The second line has N integers a1, ..., aN, the balance in each account.
The third line has an integer Q the number of queries, and each of the next Q lines has two integers L and R, the interval that should be queried.
Limits
Print two integers, the maximum subsegment sum and the size of that subsegment. If there are multiple possible sizes, print the greatest.
3
-1 -2 -3
1
1 1
-1 1
8
1 2 -1 4 9 8 -1 2
4
1 3
1 4
2 5
7 8
3 2
6 4
14 4
2 1
3
0 0 0
1
1 3
0 3
In ancient Egypt, the construction of the pyramids is surrounded by mystery. Many researchers consider that the technology necessary to build them wasn't available at the time, and suspect that the Egyptian had extraterrestrial help to build them.
An example of those mysteries are the "It-miha" numbers. In the Egyptian province of It-miha was found a stone engraved with a sequence of numbers. Apparently the numbers had no link, until Poincaré, in the end of the XIX century, conjectured that the numbers written on that stone were the 500 first numbers that have no perfect square divisors.
A perfect square is a number is a number that has an integer square root, like 1, 4, 9, 16, 25, etc. We say a number is free of perfect square divisors if it is not divisible by any perfect square greater than 1.
It may seem simple to us, today, to determine such numbers, but we must remember that in that time, more than 3500 years ago, even the number system was different, and it made any calculation very difficult.
The "It-miha" numbers are very frequent in pyramids construction. The base of the Quéops pyramid, for example, is 210 × 210 and its height is 105 meters. All its dimensions are "It-miha" numbers!!!
The first ten "It-miha" numbers are 1, 2, 3, 5, 6, 7, 10, 11, 13 and 14. Your task is to, given an integer N, determine the Nth "It-miha" number.
The first line has a single integer Q, the number of queries.
Each of the next Q lines has an integer N.
Limits
For each query, print the Nth "It-miha" number.
5
1
2
4
12
371
1
2
5
17
609
Your team is already making plans to visit Egypt. One of the places you want to meet is the famous Cairo Market. To save time, you decided you will get in through the door in the southwest of the market and get out through the northeast door. Besides, you will always walk toward the exit, that is, only north or east.
The Egyptian salesmen have a very peculiar rule: If you buy something from one of them, you can only buy again from another salesman that is older. The punishment for disrespecting this rule is loosing a hand. Of course this would harm your performance in the ICPC finals, and, for this reason, you will follow the local tradition. As it is not elegant to give the same kind of souvenir to your friends, so you decided that you will only buy at most one gift from each salesman.
The market is very organized. The places where the stores are all have the same width and height. Each place is identified by a coordinate (x, y) that indicates the column and the line that store is. When you are in a store, you can go to any store strictly north and/or east, that is, from (x1, y1) you can go to any other (x2, y2) where x2 ≥ x1 and y2 ≥ y1.
Knowing the age of the salesman and the store each of them works, determine the maximum number of items you can buy.
The first line has an integer N, the number of salesmen.
Each of the next N lines has two integers each, xi and yi, meaning the ith salesman is in the store with coordinates (xi, yi).
The salesmen are listed in ascending order of age, that is, from the youngest to the oldest. Two salesman can share the same store, in this case you can negotiate (or not) with each of them in any order. All salesmen are guaranteed to be within the market.
Limits
Print a single integer, the maximum number of items you can buy.
2
1 1
1 2
2
2
2 1
1 1
1
3
1 1
1 2
2 1
2
4
1 1
1 2
2 1
2 2
3
Nefertiti was queen of Egypt, wife to Akhenaton, and is considered one of the most beautiful women in the history of the world. Her statue, which can be seen in the Altes Museum in Berlin, Germany, proves her rare beauty. The sculptor didn't even finish the work, leaving the iris of the left eyeball undone, to avoid the God's wrath.
The life of the queen of Egypt was very busy, and she had to take care of many things, including the court's food menu. Akhenaton was known for hating that the food repeated often, and even in regular intervals. He wished the dishes were not only different, but also that is would be almost impossible to discover when a dish would be repeated. This created a huge problem for the court's chefs, that had to create new dishes as well as plan the order they would be served.
Nerfertiti had, then, an idea. She made a list of N dishes that would be repeated. One request of her was that the difference between the dish served in the ith day and i was at most K. Such demand, as well as being for religious reasons, was also due to the fact that the ingredients for the dish i were acquired during this interval, and could not wait so much or they would rot.
Your task is, for each integer N (the number of different dishes) and an integer K, count the number of different arrangements of the dishes are valid. Notice that each arrangement can be modeled as a permutation p of {1, 2, ..., N}, and an arrangement is valid if |p(i) - i| ≤ K, for all i from 1 to N.
The input has a single integer K.
Limits
You should print 200 lines, in the ith line print the number of arrangements of size N = i that are valid. Print these numbers modulo 109 + 7.
3
1
2
6
24
78
230
675
2069
6404
19708
The sample output only shows the first 10 lines of output.
Every self-respecting computer scientist knows the book "The Hitchhiker's Guide to the Galaxy" and knows the fundamental answer to life, the universe and everything. However what few know is that Douglas Adams' story is based on an Egyptian legend, of an oracle in the city of Eskendereyya (Alexandria).
In ancient times, the city founded in 331 BC by Alexander the Great was one of the main cities in the world, housing the Lighthouse of Alexandria (one of the seven wonders of the ancient world), the Great Library (the largest one of its time) and many other fantastic works. Legend says that Alexandria's Oracle lived there. The citizens of Alexandria would hand to the oracle small notes with two numbers, and receive another note back, that would be the fundamental answer of the universe related to the two numbers given.
In his treaty in 227 AC, Cleomenes of Naucratis (administrator of Alexandria while Alexander went to conquest) reported a few results obtained by the oracle:
Modern studies show that the oracle returned a generalization of the factorial of an integer number. As we know,
The oracle returned, given N and K, the K-factorial of N, that is,
in which the product was done while the diference is greater or equal to 1. We can represent the K-factorial of a number as that number followed by K exclamation points:
It is said that after reading about the oracle of Eskendereyya, Douglas Adams was inspired to do his work. Also, in Egypt is also the inspiration behind The Restaurant at the End of the Universe, but that is a story for another time...
Your task is to determine the answer the oracle gave to some notes.
The first line has a single integer Q, the number of queries.
The next Q lines each has an integer N followed by some exclamation points.
Limits
For each query, print the requested number.
4
3!
10!!!
19!!!!
4!!
6
280
65835
8
Ramses II was the most prestigious of the Egyptian pharaohs. He reigned from 1279 BC to 1213 BC, and built many temples, including the famous Nubian temples. The most famous is built on stone, in Abu Simpel, near the second Nilo fall, where he is also sculptured.
With Nefertari and many other wives he had probably more than 6 children, with whom he liked to play a game called "highest pyramid". The game was played the following way: The kids got some blocks of different dimensions (that could be rotated), and should with these cubes build a pyramid as high as they could. To build it they could not place a bigger block over a smaller one, that is, if the block A is over block B, then both the width and the depth of A should not exceed B's.
Amen-hotep, Ramses' firstborn, was very good in this game, and many times he was able to build pyramids higher than his dad could. Ramses decided to call the court's mathematician, Narmer, to find, for each set of blocks, the highest pyramid possible.
The first line has a single integer N, the number of blocks.
Each of the next N lines has three integers xi, yi and zi, the dimensions of each block.
Limits
Print a single integer, the height of the highest pyramid that is possible to build with the blocks.
5
10 10 10
50 50 50
40 40 40
20 20 20
30 30 30
150
2
20 20 20
30 33 10
33
2
100 10 10
100 12 8
110
Zé Coquinho is a famous artisan that makes sculptures with coconuts. The dried coconuts are cut in half and bows are made with the shells, and used to build sculptures. The sculptures are very famous, and are searched by collectors all over the world.
This is the most famous coconut sculpture made by Zé Coquinho. Zé Coquinho's sculptures are sequences os bowls glued to each other. A bowl open to the left is represented as ')' and a bowl open to the right is represented as '('. A well-formed sculpture is defined the following way:
A marking characteristic of Zé Coquinho's sculptures is that they are never well-formed.
The Museum of Modern Art of Graviúna wants to make an exposition of Zé Coquinho's works. To organize the exposition, the museum decided to ordem the sculptures in lexicographic order. The museum considers '(' comes before ')' so, for example, "(((" < "(()" < ")((". The size of an sculpture is the number of bowls used in it.
Given N and K, you should determine the Kth sculpture Zé Coquinho made, in lexicographic order. You can consider Zé Coquinho created all possible non-well-formed sculptures of size N.
The first line has a single integer Q, the number of queries.
Each of the next Q lines has two integers N and K.
Limits
For each query, print a single line, the Kth sculpture of size N made by Coquinho, in lexicographic order. If there is no such sculpture, print "-1" instead.
4
4 1
4 5
6 64
7 14
((((
())(
-1
((())()