The 2017 International Congress of Monsters gathers N monsters coming from all over the world. Their chairman has to solve the following problem: if the i th monster ( 1 ≤ i ≤ N ) has k i fingers, indexed from 0 to k i - 1 , so he can lift j of those fingers ( 0 ≤ j ≤ k i ), obtaining a certain number, in the following way: if a certain finger is lifted, 2 finger index is added to the current number. As a result, the i th monster can count on his fingers nri distinct numbers. Therefore, the demanded result is nr1 + nr2 + ... + nr nr modulo 10 9 + 7
Task
Compute the required sum, modulo 10 9 + 7
Input Format
The first line of the input file, monsters.in contains the number N.
The second line contains N positive integers, k1, k2, . . ., kn , representing the numbers of fingers of each monster.
Output Format
The output file, monsters.out, must contain a single positive integer, the requested sum, modulo 10 9 + 7
Constraints
Subtasks
| Subtask | Score | Additional input constraints |
|---|---|---|
| 1 | 40 | N ≤ 1.000, k i ≤ 10.000 |
| 2 | 100 | N ≤ 200.000, k i ≤ 1.000.000.000 |
Sample Input
2
3 7
Sample Output
136
Explanation
The first monster can obtain 8 numbers:
0 - no finger was lifted;
1 - the index of the lifted finger is 0; 2 - the index of the lifted finger is 1; 3 - the indexes of the lifted fingers are 0 and 1; 4 - the index of the lifted finger is 2; 5 - the indexes of the lifted fingers are 0 and 2;
6 - the indexes of the lifted fingers are 1 and 2; 7 - the indexes of the lifted fingers are 0, 1 and 2;
The second monster can obtain 128 numbers
It is known that the human DNA is represented by an integer number. On a microscopical level, the DNA consists of numerous genes. Considering the binary representation of the corresponding number of the DNA, we notice the following rule: digit 1 on the i th position indicates the presence of the i th gene, whereas digit 0 indicates its absence (i is a positive integer ). Moreover, it was observed that any two distinct adults can give birth to a child whose DNA only contains the i th gene if and only if the DNAs of both of the adults contain that gene.
Task
Generate an array of 2000 non-negative integers representing the DNAs of a group of adults so that the total number of children with distinct DNAs that can be born from adults belonging to this group is as big as possible. (as big as possible doesn’t mean optimum). The scoring will respect the table below.
Constraints
Score
| Score | NR - the number of children with distinct DNAs | |
|---|---|---|
| 1 | 37 | 200,000 ≤ NR ≤ 549,999 |
| 2 | 74 | 550,000 ≤ NR ≤ 600,000 |
| 3 | 74 + 1,5 * ( ( X - 600,001 ) * 1 ⁄ 40000 + 1 ) | 600,001 ≤ NR ≤ 999,999 |
| 4 | 100 | 1,000,000 ≤ NR |
Example
Considering that the adults have the following DNAs: 1, 5, 3, 6, 9, 12, the distinct DNAs of the children will be: 1, 0, 4, 2, 8.
Gigel wants to test his cooking abilities and goes to the market to get some supplies. At the market, there are M types of objects sold as promotional packages for a period of N days. On the i th day, Gigel has two options: he either buys the promotional package available on that day or not. The promotional package is represented by a non-empty subset of the set of the M types of objects and it has a certain price.
Task
Knowing M, N, the price and the composition of each of the N promotional packages, find the minimal price that Gigel should pay in order to buy at least one object of each of the M types.
Input Format
The first line of the input file, promotion.in contains 2 numbers, M and N.
The next N lines describe the N promotional packages in this way: the ( 1 + i ) th line (1 ≤ i ≤ N ) contains NR and P, which stand for the number of objects in the promotional package from that day and its price. Then, on the same line, there are given NR numbers which represent the indexes of the objects that belong to that package.
Output Format
In the output file, promotion.outprint a positive integer number equal to the minimal price that should be paid in order to buy at least one object of every type.
Constraints
Subtasks
| Subtask | Score | Additional input constraints |
|---|---|---|
| 1 | 50 | M ≤ 10, N ≤ 100 |
| 2 | 80 | M ≤ 15, N ≤ 1.000 |
| 3 | 100 | M ≤ 17, N ≤ 1.000 |
Sample Input
5 4
3 10 1 3 2
2 8 1 4
3 11 5 4 3
5 27 1 4 2 3 5
Sample Output
21
Explanation
The chosen packages are the first and the third ones, thus obtaining a minimal cost of 10+11 = 21. Note that Gigel buys one object of type 1, one object of type 2, two objects of type 3, one object of type 4 and one object of type 5.
After going to a public garden, Antonio returns home, where he finds a string of N non-negative integers and a number X. Feeling bored, he decides to invent a game with this array in N steps. Therefore, at each step, Antonio performs 2 actions:
Task
Determine the values kept in mind by Antonio at each step.
Input Format
The first line of the input file, comeback.in contains numbers N and X.
On the second line of this file there are N space-separated elements corresponding to the array.
Output Format
The output file, comeback.out has N lines:
The i th line contains two integers separated by a space, the sum of the sums of valid subsequences at step i and their number.
Constraints
Subtasks
| Subtask | Score | Additional input constraints |
|---|---|---|
| 1 | 40 | N ≤ 1.000 |
| 2 | 100 | N ≤ 100.000 |
Sample Input
3 5
1 2 3
Sample Output
14 5
15 5
13 5
Explanation
Stage 1. The sum of the sums of valid subsequences: 1 + 2 + 3 + (1 + 2) + (2 + 3)=14
There are 5 valid subsequences.
The array becomes 2, 3, 1.
Stage 2. The sum of the sums of valid subsequences: 2 + 3 + 1 + (2 + 3) + (3 + 1)=15
There are 5 valid subsequences.
The array becomes 3, 1, 2.
Stage 3. The sum of the sums of valid subsequences: 3 + 1 + 2 + (3 + 1) + (1 + 2)=13.
There are 5 valid subsequences.
The array becomes 1, 2, 3.
One morning, Răzvăran decided to invite his two friends, Matthew and Peter, to go for a walk in a well-known public garden. This garden has the shape of a tree with N nodes (indexed from 1 to N) and between N-1 pairs of nodes there are paths which measure 10 meters. In each i node, there is an i spring. The friends only accept the invitation if the walk respects the following rules: Matthew, a pretentious young man, wants to get to all of the springs walking as few meters as possible and Peter, wanting to rise up to the challenge, says that he wants to visit M springs in a pre-established order: P 1 , P 2 , … , P m. Răzvăran now wonders in how many ways they can walk, knowing that both the entrance and the exit are at the first spring, which is at the same time the root of the tree.
Task
Determine the number of ways in which the three friends can walk. This number must be printed modulo 10 9+7
Input Format
The first line of the input file, walk.in there are two positive integers, N and M, which represent the number of springs of the public garden and the number of springs Peter wants to visit.
The next line contains N-1 numbers T 2 , T 3 , … , T n representing the parent array corresponding to the tree. On the next line there are M distinct numbers P 1 , P 2 , … , P m.
Output Format
On the first line of the output file, walk.out you shall print the required number.
Constraints
Subtasks
| Subtask | Score | Additional input constraints |
|---|---|---|
| 1 | 20 | 1 ≤ M ≤ N ≤ 10 |
| 2 | 60 | 1 ≤ M ≤ N ≤ 4.000 |
| 3 | 100 | 1 ≤ M ≤ N ≤ 400.000 |
Sample Input
7 3
1 1 2 2 2 3
5 4 7
Sample Output
3 . 4
Explanation
The correct ways the three friends can walk are:
1 2 5 2 4 2 6 2 1 3 7 3 1
1 2 6 2 5 2 4 2 1 3 7 3 1
1 2 5 2 6 2 4 2 1 3 7 3 1
Moreover, three invalid walks are :
1 2 5 2 4 2 1 3 7 3 1 (the 6th spring is not visited)
1 2 4 2 5 2 6 2 1 3 7 3 1 (they visit the 4th spring before the 5th one)
1 2 4 2 5 2 6 2 4 2 1 3 7 3 1 (the length of the walk is not minimal)
This is a communication (interactive) problem!
Antonio is known in his city, Barlad, for being the winner of the last edition of
JBOI, a contest for juniors only. As he is a senior from now on, he wants to show his best friend, Zetul, that he can solve harder problems too.
In order to do this, Zetul hid an Easter Egg in the Public Garden, a beautiful park
in their hometown. The Public Garden contains N islands, connected by N-1 bridges, so
that the set of the N islands is beautiful.
Now, Antonio should find the Easter Egg asking Zetul several questions: Antonio
will give Zetul a set of islands and Zetul will tell him whether or not, among the set, there
is the island where the Easter Egg is hidden. The only condition Zetul is asking for is the
set of islands to be beautiful. A set of islands is beautiful if any two islands are connected
by some bridges . More precisely, there is a path of bridges between any two islands from
the set.
You should help Antonio find the Easter Egg, using as few questions as you can,
to show Zetul that Antonio can solve senior problems too!
In a test case, there will be at least one Easter Egg hidden, so make sure your program supports multiple Easter Eggs findings. There will be maximum 60 findEgg calls in a test case, the time limit is for all these calls.
Task
You need to implement a function findEgg that determines the island where the Easter Egg is hidden.
You can call a function query to help you find the Easter Egg. This function will return 1, if the egg is found on the islands from the query and 0 if not.
| Subtask | N | Points | Percentage |
|---|---|---|---|
| 1 | N ≤ 16 | 30 | 100%, 0 ≤ Q ≤ 4 |
| 80%, 5 ≤ Q ≤ 6 | |||
| 66%, 7 ≤ Q ≤ 10 | |||
| 40%, 11 ≤ Q ≤ 14 | |||
| 25%, Q = 15 | |||
| 15%, Q = 16 | |||
| 2 | N ≤ 500 | 40 | 100% 0 ≤ Q ≤ 9 |
| 85%, 10≤ Q ≤11 | |||
| 66%, 12≤ Q ≤ 45 | |||
| 3 | N = 512 | 30 | 100% 0 ≤ Q ≤ 9 |
| 75%, 10≤ Q ≤11 | |||
| 66%, 12≤ Q ≤ 45 |
Implementation Details
You have to submit exactly one cpp file. This file implements findEgg as
described above using the following signature: (There will not be a main)
int findEgg(int N, vector < pair < int, int > > bridges);
The signature of query is as follows:
int query(vector < int > islands);
Example
For N = 5, and bridges: (1, 2), (1, 3), (2,4), (4,5)
The set {1, 2, 3} is beautiful. The set {1, 2, 4, 5} is beautiful. The set {1, 2, 3, 5} is
NOT beautiful(The islands are 1-indexed).
You are given an array V, consisting of N integers V1, V2 ... VN.
Your task is to find the result of XOR (1 ≤ i ≤ j ≤ N) (Vi + Vj )
Input Format
The first line contains integer N - the size of the array. The second linde contains N space-separated integers V1 V2, ..., VN.
Output Format
The first line contains the required answer.
Subtasks
| Subtask | Constraints | Scoring |
|---|---|---|
| 1 | 1 ≤ N ≤ 4*103, 1 ≤ Vi ≤ 5 * 108 | 7 points |
| 2 | 1 ≤ N ≤ 106, 1 ≤ Vi ≤ 4 * 103 | 11 points |
| 3 | 1 ≤ N ≤ 106, 1 ≤ Vi ≤ 106 | 21 points |
| 4 | 1 ≤ N ≤ 105, 1 ≤ Vi ≤ 5 * 108 | 38 points |
| 5 | 1 ≤ N ≤ 106, 1 ≤ Vi ≤ 5 * 108 | 23 points |
Sample Input
4
3 9 6 6
Sample Output
20
Note:
(1, 1) : 3 + 3 = 6
(1, 2) : 3 + 9 = 12
(1, 3) : 3 + 6 = 9
(1, 4) : 3 + 6 = 9
(2, 2) : 9 + 9 = 18
(2, 3) : 9 + 6 = 15
(2, 4) : 9 + 6 = 15
(3, 3) : 6 + 6 = 12
(3, 4) : 6 + 6 = 12
(4, 4) : 6 + 6 = 12
6 ^ 12 ^ 9 ^ 9 ^ ^18 ^ 15 ^ 15 ^ 12 ^ 12 ^ 12 = 20
The scientific committee is in deep trouble: they could come up with a nice task,
but they are not sure they can build the test data for it. The problem statement sounds like
this:
“Being given a string containing only 0s and 1s, compute the number of distinct
non-empty subsequences that appear in it”
Here, by subsequence of a string, we understand a string that can be obtained from
the initial string by erasing some of its characters (possibly none). Two subsequences are
considered different if and only if they differ in at least one place or they have different
lengths. For example, string “101” has 6 different non-empty subsequences: “0”, “1”,
“10”, “01”, “101” and “11”.
Now, the committee could, of course, generate the tests randomly and compute the
answer for each of them with the official source, but this idea doesn’t satisfy the author.
They want to have full control over the output. They want to know, for each value K in a
given file, how many binary strings have exactly K different non-empty subsequences
and what is the shortest such string. If there are more strings meeting the requirements,
the committee will be pleased with any such string. As the answer to the first request
might be very big, they want to know just the number modulo 1.000.000.007.
Input Format
On the first line of the input file, there will be a number T representing the number of values K that follow. On the next T lines there’ll be the values of K for which you need to answer to the 2 queries described in the statement
Output Format
For each value K in the input file, you’ll have to print 2 lines:
On the first line, you should print the number of binary strings that have exactly K
different non-empty subsequences modulo 1.000.000.007, or, if you want to skip this
query -1. If you print any number different from -1, we’ll consider that you’ve tried to
answer the question.
On the second line, you should print -1 if you want to skip the query. Otherwise,
you should print L binary digits separated by spaces, digits that should form one of the
binary strings of minimal length that have exactly K different non-empty subsequences.
Subtasks
There will be 3 subtasks for this problem. You can skip queries only in the first subtask by printing -1s as explained in the Output section.
| Subtask | Constraints | Scoring |
|---|---|---|
| 1 | T = 2000 and K takes all the values from 1 to 2000 in order | In order to get a non-zero score, each of your
answers must be either correct, either skipped.
Let A be the number of correct answers to the
first requirement and B the number of correct
answers to the second one. You’ll get: 43 * ( 0.3 * A + 0.7 * B) * 1 / 2000 points |
| 2 | T ≤ 10, K ≤ 100.000 | 39 points |
| 3 | T ≤ 10, K ≤ 1.000.000 | 18 points |
Sample Input
3
2
3
8
Sample Output
2
0 0
4
1 0
-1
1 1 0 0
Explanation:
For K = 2, we have exactly 2 strings that with 2 different non-empty
subsequences: “00” (with subsequences “0” and “00”) and “11” (with subsequences “1”
and “11”). To be noted that string “11” has the minimum length too and it would be
accepted by the grader as a correct answer.
For K = 3, we have 4 strings fulfilling the requirement: “10” (with subsequences
“0”, “1” and “10”), “01” (with subsequences “0”, “1” and “01”), “000” (with
subsequences “0”, “00” and “000”), “111” (with subsequences “1”, “11” and “111”)
We skipped the first query for K = 8 and “1100” has exactly 8 different non-empty
subsequences: “0”, “00”, “1” “11”, “110”, “1100”, “10” and “100”.
This is just an example to clarify the information in the statement. As you can
see, T is not 2000, so this couldn’t be a test from subtask 1, which means that by
skipping a query, we get 0 points.
Ghiţă is a guy really keen on competitive programming. His favourite activities
are playing with permutations and spending time with his wife, Ana. At their 10thanniversary, Ana gave him a very beautiful permutation as she knew this is the best
present Ghiţă could receive.Let Pj be the j thelement of the permutation for every j with 1 ≤ j ≤ N.
Ghiţă was so excited by his present that he began computing the value Qifor each i with 1 ≤ i ≤ N. Qi is defined as the number of increasing subsequences that he could
find in the prefix of length i of his permutation.
More formally, for each i with 1 ≤ i ≤ N, Qi is the number of integer arrays j1, j2 ... jk so that 1 ≤ j1 < j2 < ... < jk-1 < jk ≤ i and Pj1 < Pj2 < ... < Pjk.
He thought that Q, even though it wasn’t a permutation, was pretty nice too.
That’s why he saved it near the permutation P.
Everything was ok until Lică Sămădăul came. He wanted to use Ghiţă’s
surveillance system for immoral purposes and Ghiţa, being a fair man, didn’t help him.
Enraged by Ghiţă’s answer, Lică Sămădăul hired Buză Spartă to help him steal Ghiţă’s
most valuable assets: his permutation and his wife. And so he did.
The next day Ghiţă found out that P was missing and now, the only solution for
Ghiţă to recover the permutation is by using the array Q that he still has. You can guess
that your job is to help Ghiţă recover array P being provided with array Q.
Input Format
On the first line of the input there is N, the length of the permutation. On the second line, separated by spaces, there are Q1, Q2, ... ,QN.
Output Format
On the first and only line of the output, you should print the array P representing the stolen permutation.
Constraints
Scoring
| Subtask | Restriction | T = Number of digits of Q(N) | Maximum input size | Score |
|---|---|---|---|---|
| 1 | N ≤ 9 | - | - | 10 points |
| 2 | N ≤ 400 | T ≤ 18 | - | 15 points |
| 3 | N ≤ 700 | - | - | 18 points |
| 4 | N ≤ 40.000 | T ≤ 171 | 4.5 MB | 17 points |
| 5 | N ≤ 70.000 | T ≤ 258 | 10 MB | 11 points |
| 6 | N ≤ 70.000 | T ≤ 314 | 16 MB | 7 points |
| 7 | N ≤ 70.000 | - | 85 MB | 16 points |
| 8 | N ≤ 70.000 | - | 111 MB | 6 points |
Sample Input 1
4
1 2 5 6
Sample Output 1
3 2 4 1
Sample Input 2
6
1 3 5 9 11 21
Sample Output 2
1 6 3 4 2 5
Explanation:
In the first example, N = 4 and P = {3, 2, 4, 1}
Q1 = 1 because {3} is the only increasing subsequence of {3}
Q2 = 2 because {3} and {2} are the only increasing subsequences of {3, 2}
Q3 = 5 because {3}, {3, 4}, {2}, {2, 4} and {4} are the only increasing
subsequences of {3, 2, 4}
Q4 = 6 because {3}, {3, 4}, {2}, {2, 4}, {4} and {1} are the only increasing
subsequences of {3, 2, 4, 1}.