It's very easy to calculate this integral. But if you don't know what's integral, there are solution

In-first, i calculated a k
k = (a^2 * b * pi / 8) (or a*a*b*0.39269908169872415480783042290994 :) )
In-second, you should calculate y (or other symbol) from 1 to -1 with division (if n = 5: 1, 3/5, 1/5, -1/5, -3/5, -1)
In-third, calculate F(y) = y*(1 - y^2 / 3). (F(1) = 2/3)
in-fourth, print k*(F(yi) - F(y(i-1))) in loop
example:
if n = 2: first calculate should be k*(F(1) - F(0)), second k*(F(0) - F(-1))
if n = 3: 1) k*(F(1) - F(1/3)); 2) k*(F(1/3) - F(-1/3)); 3) k*(F(-1/3) - F(1))
etc.

[code deleted]

Edited by moderator 02.09.2020 19:58

If you want to get AC for a Kotlin solution, you should probably use java.util.Scanner instead of readLine() and try multiple times. I was able to get AC only on the second try with the same code, got TLE first time.

Read tasks and deadlines from the programmer's handbook. similar greedy approach will work in this one.
Also, why is this tagged dp? my dp soln is giving tle

Друзья, если вам не принципиально какую задачу порешать вечером - ищите другую.
Решение к этой задаче легко придумать за 5 минут... А потом искать 4 часа ошибки (ибо они будут 100%)
Удачи.

Tree for minimum is enough.

hm.ok



Edited by author 25.08.2020 03:14

Why WA#8?

How to solve this problem using c++ ? My pick is  #MLE 14. I use (10^5 + 1000)*4 + 10^5 * 2
 = 589,84375 kilobytes of memory. I have no idea how to optimize it even more(

Edited by author 20.08.2020 02:34

Edited by author 20.08.2020 02:34

My AC code gives "No" on the following testcase due to the overflow
1000000000 1000000000 1000000000
0 0 0

How do you think what's the input-data in test-2? I did tested my program around 10 times :) but i didn't find mistake((

UPD: N = 1 )))
you mustn't test borders-cases in input data. You must check your algorithm.
In this case i have "out of range" (because v_arr has length = 0, but in this program i don't check it and i address to zero index).
If check border-case this algorithm is working

My program:
@@
#include <iostream>
#include <cmath>

struct Point {
    int64_t x;
    int64_t y;
};

struct Vector {
    double r;
    double angle;
};

int cmp(const void *a, const void *b){
    Vector* v1 = (Vector*)a;
    Vector* v2 = (Vector*)b;
    double ans1 = ((v1->angle) - (v2->angle));
    if (ans1 < 0){
        return -1;
    } else if (ans1 > 0){
        return 1;
    }
    double ans2 = ((v1->r) - (v2->r));
    if (ans2 < 0){
        return -1;
    } else if (ans2 > 0){
        return 1;
    }
    return 0;
}

int main()
{
    int N;
    std::cin >> N;
    Point p_arr[N];
    Vector v_arr[N-1];
    double dist = 0;
    int64_t dx, dy;
    for (int i = 0; i < N; ++i){
        std::cin >> p_arr[i].x >> p_arr[i].y;
    }
    for (int i = 0; i < N; ++i){
        for (int j = 0; j < i; ++j){
            dx = p_arr[j].x - p_arr[i].x;
            dy = p_arr[j].y - p_arr[i].y;
            v_arr[j].r = sqrt(dx*dx + dy*dy);
            v_arr[j].angle = atan2(dy, dx);
        }
        for (int j = i+1; j < N; ++j){
            dx = p_arr[j].x - p_arr[i].x;
            dy = p_arr[j].y - p_arr[i].y;
            v_arr[j-1].r = sqrt(dx*dx + dy*dy);
            v_arr[j-1].angle = atan2(dy, dx);
        }
        qsort(v_arr, N-1, sizeof(Vector), cmp);
        for (int j = N-2; j > 0; --j){
            v_arr[j].angle -= v_arr[j-1].angle;
        }
        dist += v_arr[0].r;
        for (int j = 1; j < N-1; ++j){
            if (v_arr[j].angle != 0){
                dist += v_arr[j].r;
            }
        }
    }
    printf("%.0f", (dist / 2));
}
@@




Edited by author 20.08.2020 00:55

and also
N=6,K=10
N=7,K=10
N=6,K=2

For some reason, my code gets the right answer for all small inputs (<12) but is 1 greater than both the large test cases I've found.
It gets that s(212) = 995645336, as compared to 995645335, and s(500) = 732986521245024, as compared to 732986521245023 given before.
Anyone have any test cases with an input between 11 and 212 to help me pinpoint this problem?

Edited by author 18.08.2020 20:03

I don't know any string of length 7 contains less than 7 distinct palindrome substrings. Anyone can put the answer for 7, pls?

1)
in:
3 5
..*..
!....
....$
out: 3

2)
in:
5 8
....AA.#
.######!
...BA*##
.#######
..B$...B
out: 3

3)
in:
5 8
....AA.#
.######!
....#*##
.#######
..B$...B
out: Impossible

4)
in:
1 3
$*!
out: Impossible

5)
in:
1 3
*!$
out: 2


I have used BFS, but still WA 22 :-(

Edited by author 26.10.2008 13:57

Edited by author 26.10.2008 14:04

Edited by author 26.10.2008 14:17

Try this test:
3 3
##$
#*#
!##
Answer: Impossible

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int Num = 0, ans = -2;

    cin >> Num;

    vector <int> fact;

    int n = 2;

    while (Num > 1)
    {
        if (n > 9) {
            ans = -1;
            break;
        }
        while (Num % n == 0) {
            Num /= n;
            fact.push_back(n);
        }
        n++;
    }

    sort(fact.begin(), fact.end());

    if (n < 10 & ans != -1)
    {
        ans = 0;
        for (int i = 0; i < fact.size(); i++) {
            //ans += fact.at(i) * (i*10);
            cout << fact[i];
        }
    }


    //cout << ans;
}

Hey! I solved this problem and here are some test that you may check for you solution:

0->10
1->1
2->2
3->3
4->4
5->5
6->6
7->7
8->8
9->9
10->25
11->-1
12->26
13->-1
14->27
15->35
16->28
17->-1
18->29
19->-1
20->45
21->37
22->-1
23->-1
24->38
25->55
26->-1
27->39
28->47
29->-1
30->56
31->-1
32->48
33->-1
34->-1
35->57
36->49
37->-1
38->-1
39->-1
40->58
41->-1
42->67
43->-1
44->-1
45->59
46->-1
47->-1
48->68
49->77
50->255
51->-1
52->-1
53->-1
54->69
55->-1
56->78
57->-1
58->-1
59->-1
60->256
61->-1
62->-1
63->79
64->88
65->-1
66->-1
67->-1
68->-1
69->-1
70->257
71->-1
72->89
73->-1
74->-1
75->355
76->-1
77->-1
78->-1
79->-1
80->258
81->99
82->-1
83->-1
84->267
85->-1
86->-1
87->-1
88->-1
89->-1
90->259
91->-1
92->-1
93->-1
94->-1
95->-1
96->268
97->-1
98->277
99->-1
100->455

Good Luck!