Edited by author 13.07.2017 16:25

What is the problem i try with with python 3 & C but every time it says compilation error. What is the problem here???

Just a sort problem

del

Edited by author 06.01.2015 21:37

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

After so many calculation and math I have solved the problem.....
Here we can have two worst cases...

Case 1:
having all the right shoes first.so here needed time is 2*b and we have now all the left shoes remaining...so total time is 2*b+40...

Case 2:
we may have 39 right shoes so time needed here is (39*2=78)...then we have only one right foot left but we may encounter all the left shoes and here needed time is 40+2*(a-40)....> 40 for the first 40 shoes and 2*(a-40) is for the remaining shoes as they needed to be thrown away...then we have the only one right foot left and it need 1 second...
so total time = 78+40+2*(a-40)+1 = 119+2*a-80 = 2*a-39

ans=max(Case 1,Case 2)


Edited by author 22.02.2020 03:07

    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

Why

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

For this Test case , AC solution gives output 2 which should be 1.

25 28
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 1
5 19
19 20
20 21
21 22
22 23
23 24
24 25
25 14
15 22
6 22
1 10 22

Edited by author 20.02.2020 05:33

Edited by author 20.02.2020 05:33

Help pls,
I have WA #20

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

#include <bits/stdc++.h>
#include<cstdio>
#include <queue>
#define pb push_back
#define mp make_pair
//Macro
#define eps 1e-9
#define pi acos(-1.0)
#define ff first
#define ss second
#define re return
#define QI queue
#define SI stack
#define SZ(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define sq(a) ((a)*(a))
#define distance(a,b) (sq(a.x-b.x) + sq(a.y-b.y))
#define iseq(a,b) (fabs(a-b)<eps)
#define eq(a,b) iseq(a,b)
#define ms(a,b) memset((a),(b),sizeof(a))
#define G() getchar()
#define MAX3(a,b,c) max(a,max(b,c))
#define II ( { int a ; read(a) ; a; } )
#define LL ( { Long a ; read(a) ; a; } )
#define DD ({double a; scanf("%lf", &a); a;})

double const EPS=3e-8;
using namespace std;

#define FI freopen ("input_B.txt", "r", stdin)
#define FO freopen ("output_B.txt", "w", stdout)

typedef long long Long;
typedef long long int64;


//For loop

#define forab(i, a, b) for (__typeof (b) i = (a) ; i <= b ; ++i)
#define rep(i, n) forab (i, 0, (n) - 1)
#define For(i, n) forab (i, 1, n)
#define rofba(i, a, b) for (__typeof (b)i = (b) ; i >= a ; --i)
#define per(i, n) rofba (i, 0, (n) - 1)
#define rof(i, n) rofba (i, 1, n)
#define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
#define for1(i, a, b) for(int i=a; i<b; i++)

template< class T > T gcd(T a, T b) { return (b != 0 ? gcd(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd(a, b) * b); }
#define __(args...) {dbg,args; cerr<<endl;}

#define __1D(a,n) rep(i,n) { if(i) printf(" ") ; cout << a[i] ; }
#define __2D(a,r,c,f) forab(i,f,r-!f){forab(j,f,c-!f){if(j!=f)printf(" ");cout<<a[i][j];}cout<<endl;}

signed main ()
{
    ios_base :: sync_with_stdio(0);cin.tie(0);cin.tie(0);

    int n;
    unsigned int a;
    priority_queue <unsigned int> pq;

    scanf("%d", &n);

    bool odd = (n%2==1);

    for(int i=n/2; i>=0; --i){
        scanf("%u", &a);
        pq.push(a);
    }
    n-=n/2+1;

    for(int i=0; i<n; i++){
        scanf("%u", &a);
        pq.push(a);
        pq.pop();
    }
    if(odd)printf("%u\n", pq.top());
    else{
        a=pq.top();
        pq.pop();

       // cout << fixed << setprecision(1) << (a+pq.top())/2.0 << endl;
       printf("%.1f\n", (a + pq.top() ) / 2.0);
    }
    return 0;
}