ceils cant be negative

Edited by author 26.05.2024 06:13

These are some of the things I had to overcome:
1)Testing on something like:
6
5 5 1 1 2 2
and
6
5 5 1 1 1 2

2)There cant be 2 out of place pairs in the ascending/descending order

3)Swapping elements across all pairs

Hope this helps someone.

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main() {
    int x1, y1, x2, y2, x0, y0, l;

    cin >> x1 >> y1 >> x2 >> y2;
    cin >> x0 >> y0 >> l;
    cout << fixed << setprecision(2); // <|ENG: Set 2 symbols after dot |> <|RUS: stavim 2 simvola dlia tochki |>
    //<|ENG: get all sides |>
    //<|RUS: poluchaem vse storonui |>
    double firstEdge = sqrt(pow(x1 - x0, 2) + pow(y1 - y0, 2));
    double secondEdge = sqrt(pow(x2 - x0, 2) + pow(y2 - y0, 2));
    double field = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
    double ans2 = max(firstEdge, secondEdge) - l; // <|ENG: Second answer - max length |> <|RUS: Vtoroi otvet = prosto maximum do krainih tochek |>

    double ans1;
    //<|ENG: get the squares of the sides|>
    //<|RUS: Vosvodim v kvadrat storonui |>
    double a = firstEdge * firstEdge;
    double b = secondEdge * secondEdge;
    double c = field * field;
    //<|ENG: checking if there are obtuse angles on the side that is the pineapple field |>
    //<|RUS: Proverka est li typie ygli vosle toi storoni kotoraiy iavliaetsia polem c ananasami |>
    if (a+c < b || b+c < a) {
        ans1 = min(firstEdge, secondEdge) - l;
    }
    else {
        //<|ENG: get half the perimeter of triangle|>
        //<|RUS: poluchaem poly perimetr treygolnika |>
        double p = (firstEdge + secondEdge + field) / 2;
        //<|ENG: get square of triangle|>
        //<|RUS: poluchaem ploshad treygolnika |>
        double S = sqrt(p * (p - firstEdge) * (p - secondEdge) * (p - field));

        //<|ENG: If the area is zero and the field with pineapples does not exist (test: 2 2 2 2 3 3 1)|>
        //<|RUS: Esli ploshad ravna 0 i polia c ananasami kak bu net (test: 2 2 2 2 3 3 1)|>
        if (S == 0 && field == 0) {
            ans1 = min(firstEdge, secondEdge) - l;
        }
        //<|ENG: If the area is zero and more than one side is not zero (test: -5 0 5 0 1 0 1)|>
        //<|RUS: Esli ploshad ravna 0 i ni odna storona ne ravna 0 (test:  -5 0 5 0 1 0 1)|>
        else if (S == 0 && firstEdge != 0 && secondEdge != 0 && field != 0) {
            ans1 =  0;
        }
        else {
            //<|ENG: Default. We just look for the height using the formula|>
            //<|RUS: Obichni slychai. Prosto po formule S = a*h/2 (test:  -5 0 5 0 1 0 1)|>
            double d = 2 * S / field;
            ans1 = d - l;
        }
    }
    //<|ENG: If, after subtracting the rope, the length becomes negative, then do 0|>
    //<|RUS: Esli sle vichetania verevki otvet stal menihe nylia to delayem 0|>
    ans1 = ans1 < 0 ? 0 : ans1;
    ans2 = ans2 < 0 ? 0 : ans2;

    //<|ENG: Next just cout "round(ans1 * 100) / 100" and "round(ans2 * 100) / 100"|>
    //<|RUS: Teper prosto vivedi "round(ans1 * 100) / 100" i "round(ans2 * 100) / 100"|>

    //!!!!!!!!!!!!!!!!!!!
    //cout << round(ans1 * 100) / 100 << endl;
    //cout << round(ans2 * 100) / 100;
    return 0;

    //<|ENG: Thanks a lot for your time here!|>
    //<|RUS: Spasibo chto pochitali i uia vam pomog (navernoe)|>
    // :)
}

#include <iostream>
#include <cmath>

using namespace std;

int main(){
    double x1 = 0, y1 = 0, x2 = 0, y2 = 0;
    double px = 0, py = 0;
    double length;

    double A = 0;
    double B = -1;
    double C = 0;
    double slope = 0;

    cin>>x1>>y1>>x2>>y2>>px>>py>>length;

    // get the equation of pineapple line in the form Ax + By + c = 0

    if((x2 - x1) != 0){
        slope = (y2 - y1) / (x2 - x1);
        A = slope;
        C = y2 - slope * x2;
    }

    if((x2 - x1) == 0){
        A = 1;
        B = 0;
        C = -x1;
    }

    // now since we have Ax + By + C = 0
    // we can find the shortest distance between the point and the line

    double short_dist = fabs(A*px + B*py + C) / sqrt(pow(A, 2) + pow(B, 2));
    double dist_x1y1 = fabs(sqrt(pow(px-x1, 2) + pow(py-y1, 2)));
    double dist_x2y2 = fabs(sqrt(pow(px-x2, 2) + pow(py-y2, 2)));

    // once we have calculated the shorted distance, we need to
    // find out the point lying on that pineapple line which is
    // closest to the peg

    double slope_new = 0;
    double B_new = 0;
    double C_new = 0;
    double A_new = 0;
    bool status = true;

    if((x2 - x1) == 0){
        slope_new = 0; // the other line has slope of inifinity, so this is parallel
        B_new = 1;
        A_new = 0;
        C_new = -py;
        status = false;
    }

    if((y2 - y1) == 0){
        B_new = 0;
        A_new = 1;
        C_new = -px;
        status = false;
    }

    if(status){
        slope_new = -1.0/slope;
        C_new = py - slope_new*px;
        A_new = slope_new;
        B_new = -1;
    }

    // calculating the point of intersection

    double inter_X = (-C*B_new - B*(-C_new)) / (A*B_new - B*A_new);
    double inter_Y = (A*(-C_new) - (-C*A_new))/(A*B_new - B*A_new);

    // now check whether this point lies between the given points or not ?
    // to do that we need to check whether both of the above calculated
    // coordinates lie between the range of x1, y1 and x2, y2

    double min_x_coor = min(x1, x2);
    double min_y_coor = min(y1, y2);
    double max_x_coor = max(x1, x2);
    double max_y_coor = max(y1, y2);

    if(inter_X >= min_x_coor && inter_X <= max_x_coor && inter_Y >= min_y_coor && inter_Y <= max_y_coor){
        // this means, the point lies on the line
        double one_pineapple_distance = short_dist - length;
        if(one_pineapple_distance <= 0){
            cout<<"0.00"<<endl;
        }
        else
            printf("%.2f\n", one_pineapple_distance);

        // now to eat all the pineapples
        double larger_distance = max(dist_x1y1, dist_x2y2);
        if(larger_distance - length <= 0){
            cout<<"0.00"<<endl;
        }
        else
            printf("%.2f\n", larger_distance - length);
    }

    // or else the perpendicuar point does not lies on the line
    else{
        // first shorter one
        double shorter_distance = min(dist_x1y1, dist_x2y2);
        double larger_distance = max(dist_x1y1, dist_x2y2);

        double pineapple_1 = shorter_distance - length;
        if(pineapple_1 <= 0){
            cout<<"0.00"<<endl;
        }
        else
            printf("%.2f\n", pineapple_1);

        double pineapple_all = larger_distance - length;
        if(pineapple_all <= 0){
            cout<<"0.00"<<endl;
        }
        else
            printf("%.2f\n", pineapple_all);
    }
    return 0;
}

I used DSU algorithm and AC 0.046.
test:
10
4 5 3 6 9 10 8 7 2 1
answer: Not a proof.

Admins, please increase Memory Limit in this task.
It is wrong that solutions with O(Q*log2(10^9)) memory - segment tree on hash table - has not got any chance to pass Memory Limit without additional input queries coordinates compression (because 100000 * 30 * (3*double + char) is obviously > 64 Mb).

This data structure is quite complex even without input queries coordinates compression, why not to AC such solutions? Nowadays commonly used ML is 256 Mb, not 64.

Edited by author 19.05.2024 12:37

Edited by author 19.05.2024 12:39

There is only one eligible lowered numbered ball at any round. Keeping track of this should result in O(n) solution

Stack 1,10,100,1000,10000,100000,... vertically:

1
10
100
1000
10000
100000
...
the cumulative sums of digits from the top are:
1,3,6,10,15,21,... which are in the form of combination(N,2) = N*(N-1)/2

checking whether one is at Kth digit is the same as finding if there is integer solution to:
N*(N-1)/2 = K-1

one way is to solve the quadratic equation for N (in double) and cast N to integer and check the above relation.
regards,
So Sui Ming



Edited by author 16.01.2024 19:27

Edited by author 16.01.2024 19:27

Write down the sequence, on paper, by hand.
Now, right down the index of each digit on the sequence.
Do you know prefix sums and binary search? It's kinda useful for many problems btw...

Edited by author 15.05.2024 05:54

I solved 1009 and 1012. Now im using new algorithm (log(n)) and program works fast and correct with my tests.

Can you give more tests?

My code is here:
--------------
#include <iostream>
using namespace std;

int compare(const void * x1, const void * x2) {
    return (*(int*)x1 - *(int*)x2);
}

int main() {
    long N;
    cin >> N;
    int *m = new int [N];

    for (int i = 0; i < N; ++i) {
        cin >> m[i];
    }
    qsort(m, N, sizeof(int), compare);

    if (N % 2 == 0) {
        cout << (((m[(N - 1)/ 2] + m[N / 2]) / 2.0)*10)/10;
    }
    else {
        cout << m[N/2];
    }

    return 0;
}
--------------
Tell me please where I made a mistake

I can't understand it...
If N1 takes 2 stones at first move, he will lose, won't he?
1:8 - 2 = 6
2:6 - 2 = 4
1:4 - 2 = 2
2:2 - 1 = 1
1:1 - 1 = 0
Please, tell me, where I'm wrong?

if the cube is at e2, neighbors are:
e1 (near), e3 (far), d2 (left) and f2 (right)

for your convenience
24 orientations of cube:
1 2 3 4 5 6
1 2 4 5 6 3
1 2 5 6 3 4
1 2 6 3 4 5
2 1 3 6 5 4
2 1 4 3 6 5
2 1 5 4 3 6
2 1 6 5 4 3
3 5 1 6 2 4
3 5 2 4 1 6
3 5 4 1 6 2
3 5 6 2 4 1
4 6 1 3 2 5
4 6 2 5 1 3
4 6 3 2 5 1
4 6 5 1 3 2
5 3 1 4 2 6
5 3 2 6 1 4
5 3 4 2 6 1
5 3 6 1 4 2
6 4 1 5 2 3
6 4 2 3 1 5
6 4 3 1 5 2
6 4 5 2 3 1

test:
4
1 4 2 3 6 5
1 4 3 6 5 2
1 4 5 2 3 6
1 4 6 5 2 3
ans:
1
1 2 3 4

:)