Magicians at our University want to be alchemists. They work with crystals - they can mix some set of crystals and get another set of crystals. Of course, it is needed that these changes comply with the rules because to change the set of crystals would be impossible otherwise even for magicians!
As in real life, a lot of work is needed to do to change sets of crystals. Therefore, each rule has a fixed amount of work it requires to apply.
Magicians buy potato chips and find some magical crystals in the packages. There can't exist more than one crystal of the same type, because the stronger crystal of the same type consumes the weaker and, finally, the one crystal is left.
There is a special set of crystals called "the dream set". When magician owns all crystals of the dream set and nothing more, he is very proud of that (equally to a kid who collects all puponauts).
You are given the set magician owns initially, the dream set and the rules. You need to answer whether it is possible to get only the dream set and to print the minimal needed amount of work to get it. They will decide themselves if it is worth doing.
Notes:
For example, if he owns crystals {1, 2, 3} and the rule is that we can change {2, 3} to {3, 4}, the magician can get {1, 3, 4} if he wants. But that would not satisfy him if the dream set was {1, 4}.
The first line contains the number of test cases T (1 ≤ T ≤ 50).
In the first line of every test case there are two integers n (1 ≤ n ≤ 12) and m (1 ≤ m ≤ 1000) - the number of different types of crystals and the number of rules.
The set of crystals is described with the number of its elements size (1 ≤ size ≤ n) and then size number of distinct integers, which shows the types of crystals belonging to the set (0 ≤ type ≤ n - 1). All numbers are separated by spaces.
In the second line of every test case there is an initial set of crystals owned by a magician.
In the the third line there is the dream set.
In the following m lines the rules are described as “work S1 S2” - (1 ≤ work ≤ 109), S1 and S2 are the sets of crystals. The integer amount of work is needed to be done to change the set S1 to the set S2.
For each test case output one line containing “Case #tc: YES work” or “Case #tc: NO” where tc is the number of the test case (starting from 1), “YES” or “NO” shows whether is it possible to get the dream set of crystals and work is the minimal amount of work which is needed to be done to get this set.
2
1 1
1 0
1 0
1 1 0 1 0
3 1
2 0 1
1 2
1000000000 1 1 1 2
Case #1: YES 0
Case #2: NO
Povilas is developing a social network called "Dwidder". He almost have it finished. However, there is one major problem. Povilas is very polite and he would never publish swear words. But you can't say that about other users of "Dwidder".
Povilas has almost solved this problem. He already prepared a dictionary which contains all the swear words. He will check every message word by word and see if any of the words are in the dictionary.
However, "Dwidder" users are pretty smart. They know that if you leave the first and last letter in place and shuffle the inside ones, the word will remain readable. For elamxpe, you can raed tihs snetence, dno't you? "Dwidder" users are not afraid to use this ability for the worse.
Povilas needs your help. He is giving you the dictionary and the words from the message. You must tell if there are swear words in the message, even if the inside letters are shuffled.
The first line contains the number of test cases T (T ≤ 10). In the first line of every test case there are numbers n and m (1 ≤ n, m ≤ 1000) — the size of the dictionary and the count of words in the message. In the following line there are n strings — words from the dictionary — separated by a single space. In the next line there are m strings — words from the message — separated by a single space. Every word consists of lowercase English letters and none of them are longer than 10 characters.
For each test case output one line containing “Case #tc: s”, where tc is the number of the test case (starting from 1) and s is a string consisting of zeroes and ones. The i-th character of the string corresponds to the i-th word from the message, '1' meaning that the word is a swear word and '0' that it's not.
1
2 5
pig goat
pig gaot peg goat gota
Case #1: 11010
Hello, guys,
Could you help me to improve my program? I already posted this question on several online judges, but nobody answered. So I hope to receive an answer from you. Sorry for posting this directly to the problemset (not to my blog) :)
I don't remember the exact problem statement. But the input is 10 positive integers and I think that my program is correct. I get TLE (time limit exceeded). It might be ineffective but I don't know why.
Here is my program:
#include <cstdio>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const int Maxn = 10;
int a[Maxn];
int x;
int Tribonacci(int x)
{
if (x == 0) return 0;
if (x <= 2) return 1;
return Tribonacci(x - 3) + Tribonacci(x - 2) + Tribonacci(x - 1);
}
int Fibonacci(int x)
{
if (x == 0) return 0;
if (x == 1) return 1;
return Fibonacci(x - 2) + Fibonacci(x - 1);
}
int toPower(int x, int p)
{
int res = 1;
for (int i = 0; i < p; i++)
res = ll(res) * x % mod;
return res;
}
int friendlyFibonacciFunction(int x)
{
return toPower(Fibonacci(x + 25), Tribonacci(x + 20));
}
int myFunction(int x)
{
if (x < Maxn) return a[x];
int sum = 0, res = 0;
for (int i = 1; i <= Maxn; i++) {
sum = (sum + myFunction(x - i)) % mod;
res = (res + ll(friendlyFibonacciFunction(i)) * sum % mod) % mod;
}
return res;
}
int main()
{
for (int i = 0; i < Maxn; i++)
scanf("%d", &a[i]);
scanf("%d", &x);
printf("%d", myFunction(x));
return 0;
}
Could you submit your correct program which solves the problem correctly and effectively?
The first line contains the number of test cases T (1 ≤ T ≤ 104).
In the first line of every test case there are 11 integers a0, a1, ..., a9 (1 ≤ ai ≤ 109) and x (0 ≤ x ≤ 2·109).
For each test case output one line containing “Case #tc: answer” where tc is the number of the test case (starting from 1) and answer is the result of myFunction(x).
2
1 2 3 4 5 6 7 8 9 10 10
1 2 3 4 5 6 7 8 9 9 9
Case #1: 853943371
Case #2: 9
Birute loves modular arithmetics, but hates long problem statements.

Given n, find f(n).
The first line contains the number of test cases T (T ≤ 50). In the following T lines there are integer values of number n (1 ≤ n ≤ 10007).
For each test case output one line containing “Case #tc: num”, where tc is the number of the test case (starting from 1) and num is the value of f(n).
2
1
2
Case #1: 1
Case #2: 0
Fun fact: 1 is neither prime nor composite number.
You are given an array (s) of positive integers having the length n.
Let's define the subarray as the array between some indexes l and r (l ≤ r and elements are sl, sl + 1, ..., sr). We call the subarray "simple" if mn is the minimal element in this subarray, mx is the maximal element in this subarray, a is a given parameter and inequality
is satisfied.
You need to find the size of the biggest possible simple subarray.
The first line contains the number of test cases T (1 ≤ T ≤ 50).
In the first line of every test case there are two integers n (1 ≤ n ≤ 105) and a (1 ≤ a ≤ 109) - the size of the array and the described parameter.
In the second line of every test case there are n integers si (1 ≤ si ≤ 109) - the elements of the array.
For each test case output one line containing “Case #tc: size” where tc is the number of the test case (starting from 1) and size is the size of the biggest possible simple subarray.
2
2 1
1 2
2 1
1 3
Case #1: 2
Case #2: 1
Everybody knows video game called "Snake". Martynas is developing an upgraded version of the original – "Snake++".
This is the game mechanics:
An example of snake's, whose starting length is 4, movement is showed in the following image (black squares are obstacles, gray squares are snake, black dot is food). In the fourth step snake have came out of the pit (you can see 4 segments of snake).

Martynas has generated some fields. The problem is that some fields are too small — snake cannot leave the pit without hitting the wall or itself. Your job is to find if the field is too small or not.
The first line contains the number of test cases T (T ≤ 50). In the first line of every test case there are integers n, m and k (3 ≤ n, m ≤ 10, 2 ≤ k ≤ 5) – the height of the field, the width of the field and the starting length of the snake. In every following n lines there are m symbols: 'x' for starting pit, '#' for obstacle, little letter 'o' for food and dot '.' for unoccupied square.
For each test case output one line containing “Case #tc: fit”, where tc is the number of the test case (starting from 1) and fit is text "Fits perfectly!" (without quotes) if snake can leave the pit and "Oh no, snake's too fat!" otherwise.
2
3 5 5
#####
.x#..
###.#
3 5 5
#####
.x#o.
###.#
Case #1: Fits perfectly!
Case #2: Oh no, snake's too fat!
Magicians can be really annoying at University. I am not sure if you have seen those types of people, but if you saw them, you would know that their favourite hobby is to throw their cast magic balls to the wall. The balls even gain some power from other magic balls!
If you asked why it is a problem, the answer is that it bothers both students (because their can't sleep during lectures as the balls have a lot of power) and a lady who needs to clear the wall every time.
Some non-magicians who are tired just because of the balls of power want to take some revenge. Of course, it is dangerous to approach all magicians, who throw balls, at once, so they want to sort things out with the magician who owns the widest range of power.
Let's call the power of the ball P.
As all magicians are unique, they can throw balls of different power (Pinitial). The number of previously thrown balls which are simultaneously located to the right and above the thrown ball is added to its power. So it can become quite powerful after that!
More formally, the final power of the ball Pfinal = Pinitial + |{i|X < xi and Y < yi}|, where (X;Y) describes the current ball coordinates, (xi;yi) describes the i-th (previously thrown) ball coordinates, for each possible i, and |S| shows the size of the set S.
It is said that the magician currently owns the range of power between 1 and Pfinal. All magicians who threw balls before can't own any power in this range (they lose some part of their range if this is the case).
For example, if the first magician owns a range (5; 7) and the second magician throws a ball of power P = 6, the first magician owns a range (6; 7) (the width is equal to 1), while the second one (1; 6) (the width is equal to 5).
You are given a list (which has size n) with the following information
You are supposed to answer which magician (to print its id) owns the widest range of power and to print the width of this range after each such throw. If there are several possibilities, choose the magician with the smallest id.
Note: it is guaranteed that each magician throws at most one ball.
The first line contains the number of test cases T (1 ≤ T ≤ 5).
In the first line of every test case there is an integer n (1 ≤ n ≤ 105) - the number of list entries.
In every following n lines there are four integer numbers id (0 ≤ id ≤ 109), Pinitial (1 ≤ Pinitial ≤ 109), x (0 ≤ x ≤ 109), y (0 ≤ y ≤ 109) - the id of the magician, the initial power of the thrown ball and the coordinates of his ball in the wall.
Note: It is guaranteed that it will be at most 1000 distinct values of x and at most 1000 distinct values of y.
For each test case output one line containing “Case #tc:”, where tc is the number of the test case (starting from 1).
Then output lines “id width” - id of the magician owning the widest range and width - the maximum width of any owned range after each given throw.
2
2
1 1 1 1
0 1 0 1
2
1 2 1 1
0 1 0 1
Case #1:
1 0
0 0
Case #2:
1 1
1 1
Tomas never buys neither sugar nor salt (these are the only seasonings he use) from a shop — he makes his own. For that purpose he has Sugar-n-Salt-O-Matic. It's a special machine which produces sugar and salt, and does that simultaneously.
The Sugar-n-Salt-O-Matic is a pretty simple machine. There are some holes distributed on a plane, which are used to drop grains of seasoning. Below is a single cup which can move in any of the four directions (north, south, east or west) and be placed under any of the holes with coordinates (x, y) (0 ≤ x, y ≤ 100). At a specific time t from the hole a single grain of sugar or salt is dropped. If at that moment the cup is below the hole, the grain will fall into the cup.
There are some issues regarding this machine. At the beginning (at the time t = 0) the cup can be placed under any of the holes, but per single unit of time it can only move from current hole to the adjacent one (respecting the 4 directions movement), or stay in the same place. Also at the same time there might be multiple holes dropping grains of seasoning. This makes some of the sugar and/or salt fall onto the ground.
Obviously, the sugar is ruined even if a single grain of salt falls into the cup, and vice versa. Tomas wants only pure sugar and pure salt. Luckily, he can take the cup away at any moment of time.
Tomas must decide if he should collect sugar or salt. Given the number of holes and the timings of seasoning production find the maximum number of grains of sugar ant the maximum number of grains of salt Tomas can collect.
The first line contains the number of test cases T (T ≤ 20).
In the first line of every test case there is an integer m (1 ≤ m ≤ 103) – the number of grains of seasoning dropped.
In the following m lines there are integer values of t, x, y and q (1 ≤ t ≤ 100, 0 ≤ x, y ≤ 100) – the time of the dropping, the coordinates of the hole and the type of the seasoning dropped (single lowercase character, "u" (without quotation mark) for sUgar and "a" for sAlt) — sorted in increasing order.
Note: it is guaranteed that all triples of t, x and y are pairwise distinct.
For each test case output one line containing “Case #tc: sugar salt”, where tc is the number of the test case (starting from 1), sugar is the maximum number of sugar grains collected and salt is the maximum number of salt grains collected.
2
5
1 1 1 a
2 1 2 u
3 1 2 u
3 1 3 a
4 2 2 u
5
1 0 0 a
1 0 1 a
1 1 0 a
1 1 1 a
2 0 0 u
Case #1: 3 1
Case #2: 0 1
It is not so easy to meet with your friend in the forest when you are both lost. You might ask how that would happen? Well, imagine, you are going with your friend, you are quite fast and your friend is slow. As there is a big fog, you turn around and you can't find your friend.
There is quite a shock, of course. But it is interesting to know what the expected time to meet with your friend would be, if you just waited in your place or went to any neighbouring place completely at random (with the same probability). We assume that your friend would do the same.
For example, if you are at place which has 3 neighbouring places, you would wait with the probability equal to 0.25 and you go to any of the 3 places with probability equal to 0.25. Assume, that you are doing the same operation each moment of time (as well as your friend).
You meet with your friend at the i-th place, if you and your friend happen to be at the same i-th place for the first time after some number of described steps.
The place is neighbouring to the given place if they are connected by a path.
The first line contains the number of test cases T (1 ≤ T ≤ 50).
In the first line of every test case there are two integers n (1 ≤ n ≤ 15) and m (0 ≤ m ≤ n·(n - 1) / 2) - the number of places in the forest and the number of paths. Two places have at most one path between them.
In the following m lines of every test case there two numbers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) - the places connected by an undirected i-th path.
In the last line of every test case there are two integers a and b (1 ≤ a, b ≤ n) - the first friend's initial place and the second friend's initial place.
Note: the forest is not necessarily connected.
For each test case output one line containing “Case #tc: exp1 exp2 ... expn” where tc is the number of the test case (starting from 1) and expi shows the expected numbers of steps to meet at the i-th place.
The answer will be considered correct if the absolute or relative error does not exceed 10 - 7 compared with the judge's answer.
If it is not possible to meet at the i-th place, print "N/A" as its expectation.
2
2 0
1 2
3 2
1 2
2 3
1 3
Case #1: N/A N/A
Case #2: 17.589743589744 4.800000000000 17.589743589744
Vilmantas is a real numberphile. He is fascinated by numbers, but most of all he likes numbers, which are named after famous scientist and mathematicians. For example, there are Mersenne primes (MP = 2p - 1, where p is prime), Graham's number (extremely large number, no way to define it here in commonly known notation).
Vilmantas would love to have numbers named after him. This is what he came up with. He takes some positive number and extracts every 2-digit number in the given order. For example, if we extract number 10324, we get a sequence of S = {10, 03, 32, 24}. Then he checks for three conditions:
The previous number 10324 breaks two of the conditions: 3 is prime and while GCD(10, 3) = GCD(3, 32) = 1, 32 and 24 are not coprime (GCD(32, 24) = 8).
If some number satisfies all three of the conditions, then it is called Vilmantas' number.
Given numbers a and b, count the Vilmantas' numbers in range [a;b].
The first line contains the number of test cases T (T ≤ 10). In the following T lines there are integers a and b (1 ≤ a ≤ b ≤ 1011).
For each test case output one line containing “Case #tc: num”, where tc is the number of the test case (starting from 1) and num is the count of Vilmantas' numbers from a to b inclusive.
4
1 9
23 23
25 25
100 200
Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 11
Only integers coprime to zero are 1 and - 1.
A sheep lives on an infinite field. The sheep wants to eat some grass. Grass only exists in one place. That place is a circle defined by a center point (Gx, Gy) and a radius Gr.
The sheep would gladly eat all the grass. But if you read the title of this task you noticed that there is also a wolf on that field. The wolf wants to eat the sheep, but we don't want that to happen.
The wolf is tied to a pole at position (Wx, Wy) with a rope of length Wr.
Find the area of grass that the sheep can eat without being eaten by the wolf. We can assume that the sheep starts in a safe location.
The first line contains the number of test cases T (1 ≤ T ≤ 10000).
Each test case consists of 2 lines. The first line contains integers Gx, Gy and Gr. The second line contains integers Wx, Wy and Wr. ( - 105 ≤ Gx, Gy, Wx, Wy ≤ 105, 1 ≤ Gr, Wr ≤ 105)
For each test case output one line containing “Case #tc: A”, where tc is the number of the test case (starting from 1) and A is the area of grass that the sheep can eat safely with a maximum absolute or relative error of 10 - 6.
2
0 0 5
0 10 5
0 0 5
5 0 5
Case #1: 78.53981634
Case #2: 47.83057387