3
1 2 10
2 3 100
3 4 1000
1
1 2 10

Answer: 2 2 3 100 3 4 1000

#include <bits/stdc++.h>

int main()
{
    int n,i,j,k;

    scanf("%d",&n);

    for(i=1; i<=n; i++){
            if(i==1 && n!=1){
                printf("(");
            }
        for(j=1; j<=i; j++){
            if(i==1 && n==i){
                printf("(sin(1))+%d",n);
            }
            else if(i==1){
                printf("(sin(1)+%d)",n);
            }
            else {
                if(j%2==0){
                    printf("-sin(%d",j);
                }
                else if(j==1){
                    printf("sin(%d",j);
                }
                else {
                    printf("+sin(%d",j);
                }
                if(j==i){
                    //printf(")");
                    for(k=1; k<=i; k++){
                        printf(")");
                    }
                }
            }
        }
        //if(i==n){
          //  printf(")");
       // }
       if(i!=1 && i!=n){
        printf("+%d)",n+1-i);
       }
       else if(i!=1 && i==n){
        printf("+%d",n+1-i);
       }

    }
    return 0;
}

My algorythm has maximum O(n^2) complexity. I have TLE 18 test.
But, when i artificially set limits for n (amount of layers) to 200 and for k (amount of bricks in a single layer) to 290, my program still gets TLE 18 test, i really have no idea how is it possible. It should get WA\AC if inputs are more than limits since i do not see any possibility of an endless cycle in my algo.

Edited by author 27.02.2020 21:19

Edited by author 27.02.2020 21:36

Could anybody give me some tricky tests? This problem seems to be trivial but I got WA. I guess it's all about format of result.

Just a sort problem

My O(N^2) solution works for 0.187s
but 10000 * 10000 = 1e8, it means that O(N^2) solution should work only for 1
second (not less), but in this task there is 0.5 sec and O(N^2) solution gets AC

5
0 -100000000
1 -100000000
1 -99999999
-1 100000000
0 100000000
I think, this answer is wrong:
0 -100000000
1 -100000000
-1 100000000
But my AC program doesn't think so.

I have WA#2 and i don't understand what is wrong..
If I understood problem correctly, my program works well on all tests, which I tried.

Edited by author 23.02.2020 18:27

    For each vertex in tree find the nearest vertex from the way to root, in which we need to change direction. If such vertex doesn't exist, let it be -1. Let's call this vertex as bad[V], where V - some vertex in tree.
    To answer on query for vertex X, let's travel in "bad" array from X until we meet bad[X]=-1. Let's save visited vertices (excluding query vertex X) to some array (let's call this array "change"). Now it's quety obvious, that we need to change directions only in those visited vertices to "activate" path from root to leaf.     Before changing values in "bad" array for vertex from X to root, let's take some vertex V from "change" array. Before query there was a set of vertices which have the same "bad" vertex as a V (bad[V]=bad[V_1]=bad[V_2]=...=bad[V_n], V_i - vertex from the set), and now we need to change their "bad" value to V, because we change direction in vertex V.
    Finally, we need to set bad[V]=-1 to all vertices from X to root.
    To do all operations efficiently we can use heavy-light decomposiotion + segment tree. So, the total complexity would be O(N + Q*(log(N))^2), N - number of vertices in tree.

Edited by author 06.06.2019 17:11

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
 int a;
 int n;
 cin >> n;
 vector<int> v;
 for (int i = 0; i < n; i++) {
  cin >> a;
  v.push_back(a);
 }
 n = 0;
 sort(v.rbegin(), v.rend());
 for (int i = v.size()-1; i > (v.size()-2) / 2; i--)
  n += (v[i]+1)/2;
 cout << n << endl;
}

Sort the n teams and take the first (n/2 + 1) team's people (by people i mean, array[i]/2 + 1).

If you have problem understanding what i have just written or for better understanding, give this a go : https://ideone.com/vD6SAm

Well, you have to know how to determine the distance between two points first.
It can be calculated by, dis = sqrt((x1-x2)^2+(y1-y2)^2).

You can say that, we can just calculate the distance in between the points but why the raidius of the nails are given. Its because the rope is wrapped around each and every nails. But the rope is not in fully contact with nails. The more nails we get, the less contact we have in between rope and nails.

The amount of which the rope is in contact with nail is : s = parameter of a nail/the number of nails.

So we are just required to print out : d(d is the sum of the distance between them) + number of nails * s(s is the amount which the rope is in contact with nails)

If you have problem understanding my word or for better understanding, give this a go : https://ideone.com/t1M3rK

Edited by author 21.02.2020 01:31

List<long> coll = new List<long>();
            List<decimal> answer = new List<decimal>();
            List<string> a = new List<string>();
            string line;
            while (true)
            {
                line = Console.ReadLine();

                answer.Clear();
                coll.Clear();
                a.AddRange(line.Split());
                a.RemoveAll(x => x.Equals(""));

                for (int i = 0; i < a.Count; i++)
                {
                    coll.Add(long.Parse(a[i]));

                }

                for (int i = 0; i < coll.Count; i++)
                {
                    var d = (decimal)Math.Sqrt(coll[i]);
                    answer.Insert(0, d);
                }
                Console.Clear();
                for (int i = 0; i < answer.Count; i++)
                {

                    Console.WriteLine(answer[i].ToString("0.0000##"));
                }
            }


Edited by author 21.02.2020 00:40

This problem can be solved using greedy technic.
Method is to divide the given number from 9 to 2. Each time we will continue to divide and update the number as we go. We will keep dividing N with the same number utill its impossible to do so.And for each division we will save the number which was divisible by given number. And by "save" i mean pushing the number in a stack or a in a vector or an array. If you are using other than stack you might print out the numbers in a reverse manner.

And when we are getting "-1"?
I already wrote that, we keep updating the number. so after we pass the 9 to 2 loop, we should be left with a value of 1 in the variable N ( given number ). Incase N!=1 we are just printing "-1".

For the case N=1 or N=0? for the case 1 you should just print "1" and for the case 0 print "10", we can not print 01 since this refers to number, 1.

If you have problem understanding what i have just written or for better understanding, give this a go : https://ideone.com/709cog

Edited by author 21.02.2020 00:34

Edited by author 21.02.2020 00:38

Edited by author 21.02.2020 00:41

I solve reccurence, then pow to n(which takes log n to quickpow), but it's also TL.

How can i improve this not writing my own long arithmetic?

My submission (8764478) goes wrong on the following tests, but it has an AC on the judge system.

The right answer for all test cases below is "equal".

RRGB GRBR
RRGY GRYR
RRBG BRGR
RRBY BRYR
RRYG YRGR
RRYB YRBR
RGRB BRGR
RGRY YRGR
RGBR GRBR
RGYR GRYR
RBRG GRBR
RBRY YRBR
RBGR BRGR
RBYR BRYR
RYRG GRYR
RYRB BRYR
RYGR YRGR
RYBR YRBR
GRGB BGRG
GRGY YGRG
GGBR BGRG
GGBY BGYG
GGYR YGRG
GGYB YGBG
GBRG BGRG
GBGY YGBG
GBYG BGYG
GYRG YGRG
GYGB BGYG
GYBG YGBG
BRBY YBRB
BGBY YBGB
BBYR YBRB
BBYG YBGB
BYRB YBRB
BYGB YBGB

Help pls,
I have WA #20

can u give me a test? (all answers of my program on tests which i generated are right)

VAR
s:string;
k,n,l,c:Longint;
begin
read(s);      l:=length(s);
val(s,n,c);
if (n<3) and (n>0) then
begin
k:=0;
    case s[l] of
    'a','A': write('window');
    'D','d': write('window');
    'b','B': write('aisle');
    'c','C': write('aisle');
    end;
end;
if (n>=3) and (n<=20) then
begin
k:=0;
    case s[l] of
    'a','A': write('window');
    'f','F': write('window');
    'b','B': write('aisle');
    'd','D': write('aisle');
    'E','e': write('aisle');
    'c','C': write('aisle');
    end;
end;
if (n>=21) and (n<=65) then
begin
k:=0;
    case s[l] of
    'a','A': write('window');
    'k','K': write('window');
    'g','G': write('aisle');
    'd','D': write('aisle');
    'h','H': write('aisle');
    'c','C': write('aisle');
    'b','B': write('neither');
    'e','E': write('neither');
    'f','F': write('neither');
    'J','j': write('neither');
    end;
end;
if n>65 then  write('neither');
end.

Edited by author 20.11.2012 23:14

#include<iostream>
using namespace std;
int main()
{

int n;
cin>>n;
switch(n)
{case 2:
cout<<10;break;
case 4:
cout<<670;break;
case 6:
cout<<55252;break;
case 8:
cout<<4816030;break;
}
return 0;
}

Solution #1: AC in 0.8 sec

Just calculate sum using Gauss's method.

Int[-1..1] f(x)dx ~= (5*f(-sqrt(3/5)) + 8*f(0) + 5*f(+sqrt(3/5))) / 9

Number of parts, N = (int)7e6

Length of part number i = (1e-4)*koef^i, where koef = 1 + x/N. Try some different x = 0.1 ... 10, and get AC =)

Solution #2: WA 11 on MSVC or AC on Java, Pascal, GNU C++

http://en.wikipedia.org/wiki/Residue_theorem says that we have to find all complex roots of the polynom.

I do not like exact formulas for degree 3 and 4.

There is numerical way to find all complex roots for any degree of polynom.

Just take point z = (0,0) and shift it to any direction in such a way that |P(z+shift)| < |P(z)|. Shift it while |P(z)| > eps. Now z is a root. This method works not only for polynoms, it works even for arbitrary "holomorphic function" (see Complex Analysis). Prove is smth like this http://en.wikipedia.org/wiki/Maximum_modulus_principle

The only thing that I need now -- to calculate f(z) for any complex z.

And using only "double" of Microsoft Visual C++ I can't. I have no enough precision and get WA 11 =(

Using BigDecimal (java), extended (pascal) or long double (GNU C/C++) this method gets AC (the task is from Petrozavodsk, so I have original tests).

P.S. 2 Admins: Ну сколько можно добавлять задачки с контестов, где у С++ программистов был под рукой long double, и это было важно. Даешь GNU C/C++!

Edited by author 27.10.2012 08:08