Por Costel the Pig has received a royal invitation to the palace of the Egg-Emperor of Programming, Azerah. Azerah had heard of the renowned pig and wanted to see him with his own eyes. Por Costel, having arrived at the palace, tells the Egg-Emperor that he looks "tasty". Azerah feels insulted (even though Por Costel meant it as a compliment) and, infuratied all the way to his yolk, threatens to kill our round friend if he doesn't get the answer to a counting problem that he's been struggling with for a while
Given an array of numbers, how many non-empty subsequences of this array have the sum of their numbers even ? Calculate this value mod 
(Azerah won't tell the difference anyway)
Help Por Costel get out of this mischief!
The file azerah.in will contain on its first line an integer 
, the number of test cases. Each test has the following format: the first line contains an integer 
(the size of the array) and the second line will contain 
integers 
(
), separated by single spaces.
It is guaranteed that the sum of over all test cases is at most 
The file azerah.out should contain lines. The 
-th line should contain a single integer, the answer to the -th test case.
2
3
3 10 1
2
4 2
3
3
Even though he isn't a student of computer science, Por Costel the pig has started to study Graph Theory. Today he's learning about Bellman-Ford, an algorithm that calculates the minimum cost path from a source node (for instance, node 1) to all the other nodes in a directed graph with weighted edges. Por Costel, utilizing his scarce programming knowledge has managed to scramble the following code in C++, a variation of the Bellman-Ford algorithm:
You can notice a lot of deficiencies in the above code. In addition to its rudimentary documentation, we can see that Por Costel has stored this graph as an array of edges (the array 
). An edge is stored as the triplet 
signifying an edge that spans from 
to 
and has weight 
. But even worse is the fact that the algorithm is SLOW!
As we want our hooved friend to walk away with a good impression about computer science, we want his code to execute as FAST as possible. In order to do so, we can modify the order of edges in the array so that the while loop executes a small number of times.
Given a directed graph of 
nodes and 
edges, you are asked to produce an ordering of the edges such that the Bellman-Ford algorithm written by Por Costel should finish after at most two iterations of the while loop(that is, the program should enter the while loop at most twice).
The first line of the file algoritm.in will contain an integer 
, the number of test cases.
Each of the test cases has the following format: on the first line, there are two numbers and (
), the number of nodes and the number of edges in the graph respectively.
The next lines describe the edges, each containing three integers 
signifying there is an edge from node to node with weight (
)
It is guaranteed that node 
has at least one outgoing edge.
The graph may contain self loops and/or multiple edges.
The output file algoritm.out should contain lines representing the answers to each test case.
For each test case you should output a permutation of numbers from to , representing the order of the edges you want in Por Costel's array of edges .
The edges are considered indexed by the order in which they are given in the input (the 
-th edge read is the edge with index ).
If there are multiple solutions, you are allowed to print any of them.
1
4 4
1 2 1
3 4 2
2 3 3
1 3 1
1 4 2 3
Bujor is really into gambling. He has casinos in his city, each of them having slot machines. In each day of the next days, he will visit each slot machine of each casino and will play a number of times. More formally, he has a matrix 
, where 
is the number of times in which he will play at the 
-th machine in the -th casino, each day.
The casinos all belong to the same firm, PCGE - Por Costel Gambling Enterprise. Por Costel has recently become a respected business pig. At the beginning of each day, the slot machines can be "manipulated". To be more specific, at the beginning of each day, Por Costel will send the same order to each casino, a list of numbers, which represent the expected-winnings with which to set each machine. The expected-winnings of a machine is the expected sum of money that one would win if he played at that machine once (it is real number, possibly even negative). The -th number on the list will represent the expected-winnings for the -th machine in every casino. More formally, Por Costel has matrix 
, where 
= expected-winnings for the -th machine in each casino, on the 
-th day.
The problem now is that Por Costel and Bujor are friends. Por Costel pities his friend and his gambling addiction. That's why he would like to be kind to him but without damaging his company's profits and without the other executives noticing. He wishes that each day, Bujor should achieve expected-winnings at exactly one casino, and expected-winnings 
at the rest. Lastly, there shouldn't be, after the days, a casino at which Bujor has not had expected-winnings of .
Knowing Bujor's matrix 
, you need to choose Por Costel's matrix such that the above conditions are met.
The input file bujor.in will contain on its first line the integer (
), the number of test cases.
Each of the tests will have the following format:
The first line will contain an integer (
), the number of days, casinos and slot machines within each casino.
On each of the next lines, there will be integers. The -th number of the -th line represents the value 
(
)
It is guaranteed that there exists at least one solution for any of the given test cases.
The output file bujor.out should contain the answer for each of the 
test cases.
More precisely, a test case should contain lines each having space separated numbers. This should represent a possible option for Por Costel's matrix P.
may take any real value, but they should fit into double precision floating point format. You need not leave extra empty lines between the test cases.
It is guaranteed that there exists at least one solution for any of the given test cases.
If there are multiple solutions, print any of them.
It is recommended that you print floating point numbers with 
digits of precision.
1
3
2 1 2
3 2 2
0 1 1
0.333333333 -0.666666667 0.000000000
0.666666667 0.666666667 -1.00000000
-0.666666667 0.333333333 1.000000000
Por Costel the pig is ready to change his status on Vasebook. But wait!! What's this?
It seems that the evil Mark Suckerberg was not truthful about his opinions of free speech on Vasebook. He has gathered up a censorship committee in order to censor the pig's message. Suckerberg is sick of seeing words, such as "cob", "pig", "yummy" and so on, all over Vasebook. He has come up with an entire list of these outrageous words. The committee will need to select a subset of letters from the message and replace them with '*'. After this process, none of the words in Suckerberg's list should appear as a substring in Por Costel's message.
You are part of the censorship committee, but, secretly, you are also a Por Costel fan. You know that each letter of the message has a certain importance in its context(the letter on position i has importance 
). You don't want Por Costel's message to lose its significance, but neither do you want to lose your job at VaseBook. Censor the message such that sum of the importance values of censored letters (letters replaced with '*') is minimum.
The first line of the file cenzura.in contains an integer (
), the number of tests.
Each of the tests has the following format:
First line contains an integer (
), the length of Por Costel's message.
The second line contains a string of characters, the message itself.
The third line will be a sequence of integer numbers (
) separated by single spaces. signifies the importance of the -th letter of the message.
The fourth line will contain an integer 
(
), the number of words in Suckerberg's list
The next lines will contain the aforementioned words. The length of each word is at most 
The total number of appearances of Suckerberg's words in Por Costel's message will not exceed 
.
Por Costel's message and Suckerberg's words are all comprised of lower case letters of the English alphabet(a to z).
The file cenzura.out should contain lines.
Each of these should contain a single number, the minimum sum of importance of censored letters such that the message is censored correctly on that particular test case.
1
23
cresteporciisefacepateu
1 2 3 4 5 6 7 8 9 8 9 9 2 3 2 1 4 7 8 6 5 6 7
3
porci
rcii
pateu
13
Por Costel the pig has found a legendary safe. It is said that it "holds so much food that a man may feast on it for countless years". He thinks it might be enough for breakfast.
However, he must first bypass its security mechanism which is very similar(surprisingly) to that of a suitcase.
In order to open the safe, one must insert a code of length ( digits from to 
). The code is inserted by the means of small wheels. These can be turned upward or downward. If a wheel indicates value , it can be moved upward to indicate value 
mod 
, or it can be moved downward to indicate value 
mod .
The legend says that the safe was crafted by elder pigs. That is why there exist distinct codes that open the safe. Also, the safe has deteriorated with the passing of time and now every wheel has an "error margin" given by a number 
. This means that a code 
will open the safe if there exists at least one code 
out of th elder pig codes such that 
for any in the range 
, where
means the minimum number of wheel turns in order to get from digit 
to digit 
means the -th digit of code .
Given that the system was designed by pigs, it was to be expected that it's not top-notch. There are many codes that open the safe. SO many in fact, that if one were to count them, he would have to do so mod . Calculate this value! Por Costel can't hold his appetite much longer!
The input file cifrul.in will contain on its first line an integer 
(
), the number of tests. On the following lines, each test will be described by the following:
The first line of a test case contains four integer numbers (
), (
), 
and (
).
The next lines will each contain integer numbers. These will be the codes of the elder pigs. The -th line describes the -th code.
Print lines in the file cifrul.out. The -th line should contain the answer for the -th test case.
2
1 2 10000 3
1
6
3 1 100 5
1 6 30
12
1331
Extraterrestrials are invading Earth! Happily, we have someone to protect us: the squealing hero of humanity, Por Costel the pig! He has a brilliant plan which employs tinfoil and a lot of staplers, but he also needs your help.
The alien invasion takes place in multiple steps. It is concentrated on a -kilometer long area (the kilometers are numbered 
through from left to right). The invasion consists of events of the following type:
1) An extraterrestrial ship enters the atmosphere and stops at distance 
from the ground, spanning from kilometer 
to kilometer 
(inclusive).
2) The last extraterrestrial ship that entered the atmosphere (from the ones that are still present) leaves.
All that Por Costel needs from you is to build him a radar. He needs the radar to tell him at certain points in time the height of the alien ship that is closest to the ground directly above kilometer .
The input file invazia.in will contain on the first line integers (
) and (
), the number of kilometers and the number of events respectively.
Next come lines that each describe an event:
- character 'I' followed by three integers (
) - a new ship appears - character 'E' - the last ship disappears
- character 'R' - followed by an integer number (
) - a radar query
It is guaranteed that for any 'E' operation there exists at least one alien ship in the atmosphere.
In the output file invazia.out you should print 
lines which contain the answers for each of Por Costel's radar queries ( is equal to the number of radar queries). In the case that there is no ship above kilometer , you should print the message "GUITZZZ!" (without the quotes).
12 6
I 1 7 10
R 3
I 1 12 1
E
I 5 12 2
R 7
10
2
Por Costel has discovered a writing from porcine mythology: "The Ballad of the Pig". The ballad describes a love story between a boar and a gilt. In one of the chapters, the boar tries to impress his significant other by erecting a pig pen. He fails, being tragically limited by his porcine nature. But then the ballad continues saying that the pig eventually found a fabulous orchard in the middle of a forest which he took as a home for himself and the gilt.
Por Costel is, however, not impressed by either forced rhymes, or exaggerated figurative speech. "A forest is full of orchards" he says. "It's just a matter of how you choose it".
You are provided with an x matrix which describes a "forest". Each cell has an integer value - the degree of its beauty. You are tasked with choosing an "orchard", meaning a subset of cells that satisfies the following conditions:
- It is non-empty
- It is connected(you can get from any cell to any other cell by passing only through cells that have a common side)
- The intersection of the subset with any row of the matrix is either empty, or a connected(the same of definition as above) subset of cells. In other words, on each row, the subset should have either no cell, or a continuous interval of cells.
The beauty of an orchard is defined as the sum of its cells' beauty degrees. Out of all orchards, pick the one with maximum beauty
The input livada2.in will contain on the first line (
), the number of tests.
Each of the tests has the following format: on the first line there will be two natural numbers and , the number of rows and the number of columns of the matrix (
).
Each of the next lines will contain integers separated by spaces. The 
-th number of the -th line will be 
the beauty degree of cell 
(
The output file livada2.out will contain lines and each of these lines will contain a single integer number, the maximum beauty of an orchard.
1
3 4
5 -3 0 0
-2 3 3 4
-7 -6 4 -5
17
Oberyn Martell and Gregor Clegane are dueling in a trial by combat. The fight is extremely important, as the life of Tyrion Lannister is on the line. Oberyn and Gregor are measuring their skill in combat the only way the two best fighters in Westeros can, a match of Starcraft. The one who supervises the match in none other than Por Costel the pig.
Oberyn and Gregor are both playing the Terrans, and they confront each other in the middle of the map, each with an army of Marines. Unfortunately, pigs cannot distinguish colors that well, that is why Por Costel can't figure out which marine belongs to which player. All he sees is marines in the middle of the map and, from time to time, two marines shooting each other. Moreover, it might be the case that Por Costel's imagination will play tricks on him and he will sometimes think two marines are shooting each other even though they are not.
People are starting to question whether Por Costel is the right person for this important job. It is our mission to remove those doubts. You will be given Por Costel's observations. An observation consists in the fact that Por Costel sees that marine and marine are shooting each other. We know that marines in the same team (Oberyn's or Gregor's) can never shoot each other. Your task is to give a verdict for each observation, saying if it is right or not.
An observation of Por Costel's is considered correct if, considering this observation true and considering all the correct observations up to this point true, there is a way to split the marines in "Oberyn's team" and "Gregor's team" such that no two marines from the same team have ever shot each other. Otherwise, the observation is considered incorrect.
"Elia Martell!!! You rushed her! You cheesed her! You killed her SCVs!"
The input file meciul.in will contain, on its first line, the number of tests (). A test has the following structure: the first line contains integers (
) and () and the next lines each contain a pair of integers and (
) describing an observation of Por Costel's.
The output file meciul.out will contain one line for each of Por Costel's observations, on each test. The line will contain "YES" if the observation is correct and "NO" otherwise. It is not necessary to leave extra spacing between the outputs of different test cases.
1
3 3
1 2
2 3
1 3
YES
YES
NO
We don't know how Por Costel the pig arrived at FMI's dance party. All we know is that he did.
The dance floor is hot because Por Costel broke the air conditioner. On the dance floor, the boys and girls are clumsy. There are boys at the party. The -th one has clumsiness level . There ale also girls at the party. The -th girl has clumsiness level as well. Por Costel finds that a pair of a boy and a girl can dance only if the product of their clumsiness levels is at most , i.e. girl clumsiness level * boy clumsiness level 
. Por Costel thinks that a sack of oats with a slice of leek could make a better dancing pair than the people at this party. Nonetheless, he would like to find out how many pairs (boy, girl) can dance. The input will contain the number representing the number of tests. The next lines will contain the number .
The input file perechi3.in will contain the number representing the number of tests. The next lines will each contain a single integer .
The output file perechi3.out should have lines. Line should hold the answer for the -th test.
11
1
4
5
10
100
99
16
64
49
50
48
1
8
10
27
482
473
50
280
201
207
198
Por Costel the pig is playing pinball. After many hours of studying the game by hitting the pinball table with his snout, Por Costel thinks that he figured out how it works.
There are springs on the pinball table that can launch the ball forward. If you look at the table from above, the -th spring is the -th from left to right. Springs are also characterized by their vertical position, that is, each spring also has a vertical coordinate .
If the ball hits the -th spring, the spring lauches it to another spring > . We say, in this case, that the ball bounces from the -th spring to the -th spring. There are two possibilities: Bounce up: 
, only if the last bounce was down. Bounce down: 
, only if the last bounce was up.
The first bounce doesn't have any restrictions: Por Costel launches the ball to the first spring, then the ball bounces either up or down or proceeds to bounce on a subsequence of springs that satisfy the above restrictions. Por Costel's score is the number of springs it bounces off of. Once the ball goes past the last spring, it stops.
Por Costel has spent a lot of time calculating the maximum score he can achieve if you launches the ball correctly. However, what he doesn't know is that (by hitting the table with his snout) he makes some springs change their vertical coordinate . Help Por Costel find the maximum score he can get at every moment.
The input file pinball.in contains on its first line the integer (). The second line contains integer numbers, the -th of which is the vertical coordinate of the -th spring (
). The third line contains the number (
) and each of the next lines contain two numbers each, and (
) representing the fact that the -th spring changes its vertical coordinate to .
It is guaranteed that there will never be two distinct indices and such that 
The output should contain 
lines. The first line should be the answer for the initial array and the next lines should be the answers after each of the changes.
10
1 10 2 5 6 3 4 8 9 7
3
1 11
7 17
8 12
7
6
8
6
Pay attention to the memory limit for this probem!
One night, Por Costel the pig took a walk. He was strolling peacefully when, all of a sudden, a firecracker exploded near him. Like any pig, he had the defensive reaction of squealing horrendously and running up and down along the sidewalk. Although his movement along the sidewalk seemed random, at a closer look you can see a pattern. Let's consider the sidewalk divided into positions indexed from 
to 
. At moment , Por Costel is at position 
. If, at some moment , Por Costel is at position 
, at moment 
he will be at position 
mod . In order to be prepared for the situation in which Por Costel jumps in panic in the middle of the street (God forbid!), his fans implore you to find out where Por Costel will be at any moment. A query 
means "On what position will Por Costel be at moment ?" The queries will be as random as Por Costel's movement. You will first receive 
and the other queries will be generated using the following method: if the answer for query 
is 
, the query 
will be 
mod 
.
In the input file pocnitoare.in you will find , 
, (
) and (Por Costel's position, 
), 
(number of queries, 
) and (first query, 
).
The output file pocnitoare.out should contain lines, the -th of which should contain integer (the answer to query ).
17 3 7 1 3 1
1
14
6
Por Costel the pig, our programmer in-training, has recently returned from the Petrozaporksk training camp. There, he learned a lot of things: how to boil a cob, how to scratch his belly using his keyboard, etc... He almost remembers a programming problem too:
A semipalindrome is a word 
for which there exists a subword 
such that is a prefix of and 
(reverse ) is a suffix of . For example, 'ababba' is a semipalindrom because the subword 'ab' is prefix of 'ababba' and 'ba' is suffix of 'ababba'.
Let's consider only semipalindromes that contain letters 'a' and 'b'. You have to find the 
-th lexicographical semipalindrome of length 
.
Por Costel doesn't remember if the statement was exactly like this at Petrozaporksk, but he finds this problem interesting enough and needs your help to solve it.
On the first line of the file semipal.in, there is an integer (
) representing the number of test cases. On the next lines there are 2 numbers, (
and K 
where 
is the number of semipalindromes of length .
In the output file semipal.out, there should be lines, the -th of which should contain the answer for the -th test.
2
5 1
5 14
aaaaa
bbabb