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

Try these test cases.

Test 1:
0
Ans:2

Test 2:
1
Ans:2

Test 3:
2
Ans:3

Test 4:
Z0Z
Ans:36

Test 5:
21
Ans:4

Test 6:
ZIZ
Ans:No solution.
(Don't forget to put the full-stop at the end!!!)

Test 7:
AERGUFG12312OP
Ans:32

Test 8:
234DFG67
Ans:23

And this problem can be solved within int range.


Edited by author 09.12.2015 20:14

2 2 2
2.01 4.01
3.99 4.01

правильный ответ 1.9800000
у меня было 1.9900000

Дело в том что чтобы не париться с double я умножал сразу на 100 но оказалось что 2.01 * 100 == 200 а не 201. Пришлось вручную переводить две цифры после запятой и решение зашло!

import sys
n,k=map(int,input().split())
ans=0
nn=1
on=1
if n==1:
    print(0)
    sys.exit()
for i in range(100000000000000000000):
    if on<=k:
        nn+=on
        on+=on
        ans+=1
    elif k<n:
        nn+=k
        on+=k
        ans+=1
    if nn>=n:
        print(ans)
        sys.exit()
i can not understand why optimization my cod
if i got ac with you help i give you 1000 rubles

Edited by author 17.10.2018 22:35

Don't make 100+ submissions like I did.
Just check these tests to make sure you correctly understand the problem description.

Test #1:
10 20 0
5 3 4
turn
1 100
2 100
3 100
4 100
5 100
6
1 calls 20
2 calls 20
3 calls 20
4 calls 10
5 checks
dealing flop
80 80 80 80 80

answer:
6
4 checks
5 checks
1 checks
2 checks
3 checks
dealing turn

Test #2:
10 20 10
5 3 3
turn
1 11
2 12
3 100
4 100
5 100
7
1 calls 1
2 calls 2
3 raises 10 to 30
4 folds
5 calls 10
dealing flop
5 checks
0 0 50 80 45

answer:
4
3 bets 10
5 calls 10
dealing turn
5 bets 5

Test #3 (this is what 10th test about):
10 20 0
5 3 4
flop
1 200
2 100
3 100
4 200
5 100
3
1 calls 20
2 calls 20
3 raises 20 to 100
100 80 0 100 80

answer:
5
4 calls 90
5 folds
1 calls 80
2 folds
dealing flop

Test #4: (this is what 32th test about - pay attention to the order of players' turns)
10 20 0
2 2 1
river
1 1000
2 1000
10
2 calls 10
1 checks
dealing flop
1 bets 20
2 raises 30 to 50
1 calls 30
dealing turn
1 checks
2 checks
dealing river
900 830

answer:
2
1 bets 30
2 raises 70 to 100

Test #5: (This is what 33th test about, 0 - is the wrong answer!!!!)
10 20 0
3 3 3
flop
1 100
2 100
3 100
0
80 80 80

answer:
6
3 calls 20
1 calls 10
2 checks
dealing flop
1 checks
2 checks

Good luck!!!

Edited by author 12.06.2016 14:04

Edited by author 13.06.2016 20:51

Easy concept, just to think for a while. AC in one go!