A. Almost Prime
This is a straightforward implementation problem: factor every number from 1 to n into product of primes and count the number of distinct prime divisors.B. Regular Bracket Sequence
Read the string from left to right and calculate the balance of brackets at each step (i.e., the difference between the number of "(" and ")" characters written out). We need to keep this balance non-negative. Hence, every time when the balance equals 0 and we read the ")" character, we must omit it and not write it out. The answer to the problem is twice the number of ")" characters that we wrote out.C. Parquet
We'll derive several necessary conditions for the parquet to be possible. If some of them is not fulfilled, the answer is "IMPOSSIBLE".1. m*n must be even, because it equals the total area of the parquet, and the area of each plank is even.
2. Suppose m (the number of columns) is odd. Paint the living room in two colors — black and white — in the following way: the first column is black, the second one is white, the third one is black, ..., the last one is black. The number of black squares is n greater than the number of white squares. The planks 1x2 and 2x2 contain an equal number of black and white squares, so we must compensate the difference with 2x1 planks, and their number must be at least n/2. In this case we can parquet the last column with these planks, decrease b by n/2 and decrease m by one.
3. If n is odd, then by similar reasoning a ≥ m / 2.
4. Now m and n are even. A similar reasoning shows that the number of 1x2 planks used must be even, and the number of 2x1 planks used must be even. So, if a is odd, we decrease it by 1, and the same with b.
5. Now we must have mn ≤ 2a + 2b + 4c, because otherwise the total area of planks would not be enough.
6. If all the conditions were fulfilled, we can finish the parquet: divide it into 2x2 squares, and use one 2x2 plank, two 1x2 planks, or two 2x1 planks to cover each square.
D. Tickets
If we picture the graph of the number of 10-euro banknotes, it will be a broken line, starting at the point (0, k) and ending at the point (m+n, n+k-m). Exactly m segments on the line are 'going down', and other n segments are 'going up'. Hence the total number of possible graphs is C(m + n, m) (the binomial coefficient). We need to find out the number of graphs which don't go under the X axis. To do that, we'll calculate the complementary number: the number of graphs which go under the X axis, or, equivalently, intersect the line y=-1.Here we'll use the so-called 'reflection principle'. Consider any graph that intersects the line y=-1, and take the last point of intersection. Reflect the part of the graph from this point to the end with respect to the line y=-1. We'll have a new graph, ending at the point (m + n, - 2 - n - k + m). Conversely, any graph ending at this point will intersect the line y=-1, and we can apply the same operation to it. Hence, the number of graphs we're interested in equals the number of graphs starting at the point (0, k) and ending at the point (m + n, - 2 - n - k + m). Let a and b be the number of segments in such a graph which go up and down, respectively. Then a + b = m + n, a - b + k = - 2 - n - k + m. It follows that a = m - k - 1, and there are C(m + n, m - k - 1) such graphs.
So, the probability that the graph will go down the X axis is C(m + n, m - k - 1) / C(m + n, m) = (m!n!) / ((n + k + 1)!(m - k - 1)!) = (m(m - 1)... (m - k)) / ((n + 1)(n + 2)... (n + k + 1)). The answer to the problem is 1 - (m(m - 1)... (m - k)) / ((n + 1)(n + 2)... (n + k + 1)).
E. Multithreading
It's clear that we must have 1 ≤ w ≤ Σi ni. If this condition is true, we show how to achieve the desired result in the following cases:1. N = 1, w = n1. Obvious.
2. N ≥ 2, w ≥ 2. For w = 2, the schedule is the following: 1, all loops of processes 3..N, n2 - 1 loops of the second process, 1, 2, n1 - 1 loops of the first process, 2. For w > 2, we just need to move several loops from the middle of the sequence to the end.
3. N ≥ 2, w = 1, and there exists an index i such that ni = 1. Then the schedule is the following: i, all loops of other processes, i.
Now we'll show that in any other case the result w is impossible. The case N = 1, w ≠ n1 is obvious. We have one more case left: N ≥ 2, w = 1, and ni > 1 for each i. Suppose that there exists a schedule which results in y = 1. Consider the last writing operation in this schedule; suppose it is executed by the process i. Then the corresponding reading operation should have read the value y=0. This means that there were no writing operations before. But this is impossible, since ni > 1, and this process executed ni - 1 read/write loops.
Why WA on test 3?
#include<iostream>
#include<string>
using namespace std;
string a;
long int k(long int );
int main(){
cin>>a;
long int j=a.length(),b,d=0,g=0;
long int c=0;
for(long int i=0;i<j-1;i++)
{
b=k(i);
if(b>1)
i+=b-1;
if(b!=0)
{
d=d+b;
}
else
{
d=0;
}
if(d>g)
g=d;
}
cout<<g<<endl;
cin>>g;
return 0;
}
long int k(long int h)
{
if(a[h]==')')
return 0;
long int s=0,f=0,n=0,j;
j=a.length();
for(long int i=h;i<j;i++)
{
if(a[i]=='(')
s++;
if(a[i]==')')
f++;
if(f==s)
{
n=i-h;
return n+1;
}
}
return n;
}
Is there any other technique to achieve the formula for problem D except the reflection method?
Here in problem D tickets isn't the permuation important.If suppose we have a favourable order i.e. order which will smoothly run so we can also permute the people having 10 euros and 20 euros amongst themselves in m! and n! ways.This will account for a different pattern .I am unable to guess why is that not taken into account.
Good tutorial
Can anyone explain how the reflection principle work in D? I cant see how - 2 - n - k + m has been derived?
If points y1 and y2 are symmetric with respect to y0, then we must have
y0-y1 == y2-y0, which givesy2 == 2*y0 - y1. In this case y0 == -1, y1 == n+k-m.Old is Gold..