Здравствуйте! Может кто подсказать, почему код не работает? Специально для задачи изучил дерево Фенвика и на питоне всё равно не заработало (на 9 задаче по времени не прошло)

******************************************************
n=int(input())
mas=[0]*n
xp=[0]*32002
for i in range(n):
    lis=list(map(int,input().split()))                #Принимается на ввод пара координат
    if (lis[0]-1)%4==0:
        if lis[0]!=1:
            mas[xp[lis[0]]+xp[lis[0]-2]]+=1

            for j in range(lis[0]+2,32002,4):
                xp[j]+=1
        else:
            mas[xp[lis[0]]]+=1
            for j in range(lis[0]+2,32002,4):
                xp[j]+=1

    else:
        if (lis[0]+1)%4==0:
            mas[xp[lis[0]]]+=1

            for j in range(lis[0]+4,32002,4):
                xp[j]+=1
        else:
            if lis[0]%2==0:
                if lis[0]!=0:
                    if lis[0]%4==0:
                        mas[xp[lis[0]]+xp[lis[0]-1]]+=1
                        xp[lis[0]+1]+=1
                        for j in range(lis[0]+3,32002,4):
                            xp[j]+=1
                    else:
                        mas[xp[lis[0]+1]-(xp[lis[0]+1]-xp[lis[0]-1]-xp[lis[0]-3])]+=1
                        for j in range(lis[0]+1,32002,4):
                            xp[j]+=1
                else:
                    mas[xp[lis[0]]]+=1
                    xp[lis[0]+1]+=1
                    for j in range(lis[0]+3,32002,4):
                        xp[j]+=1
    xp[lis[0]]+=1
for i in mas:
    print(i)
**************************************

Don't brute force :(

I use Python function .isdigit() to check if fraction is integer, but strings like "-12" gives False for .isdigit() check.

So, in test 26 one of the fractions is something like -x, where x is integer.

Edited by author 31.07.2024 13:33

hope they help someone

test 1
5
1
0
0
0
0
0

answer 1
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000

test 2
5
1
-11
47
-97
96
-36

answer 2
1.0000000000
2.0000000000
2.0000000000
3.0000000000
3.0000000000

test 3
5
1
-5
10
-10
5
-1

answer 3
1.0000000000
1.0000000000
1.0000000000
1.0000000000
1.0000000000

test 4
5
1
-19
66
-94
61
-15

answer 4
1.0000000000
1.0000000000
1.0000000000
1.0000000000
15.0000000000

test 5
5
1
-2
-3
4
-1
0

answer 5
-1.6180339887
0.0000000000
0.3819660113
0.6180339887
2.6180339887

test 6
5
1
47
47
-35
23
48

answer 6
-45.9605895781
-1.4565711031
-0.8277595971

test 7
5
1
-14
37
18
-42
-16

answer 7
-0.8937080620
-0.3737580555
1.2403250836
3.7621983673
10.2649426666

test 8
5
-37
41
34
-38
47
42

answer 8
-0.9916715391
-0.6140289854
1.6927104673

You can get AC with import java.math.BigDecimal, but in this case you should format output this way:

import java.text.DecimalFormat;

DecimalFormat df = new DecimalFormat("0.000000000000000000##E0");
out.write(df.format(answer).replace('E', 'e').replace(',', '.'));

where answer is your sum of the sequence.

-280 19326 6488 -15295

(x2-156x+115)(x2-124x-133)

540 is to big rating for task that can be solved O(p * log p) without using fact that p is prime, doesn't it?

P.S. I understand, that problem rating is auto-generated.

In suffix tree, if you will iterate for every edge from l to r, that are assigned to this edge, you will get TLE

Don't use int("smth"), because len of number can be greater than 4000 or use sys.set_int_max_str_digits() if you use python

Edited by author 26.07.2024 17:14

but stack overflow

be careful, you must output the number of stops in the new route k
and  NOT K+1
So, for example in C++
vector<int> res;
...

cout << res.size() - 1 << " "; // check this. not cout << res.size() << " ";


Edited by author 05.01.2014 23:39

U can use Python `eval(expression, variablesDict)` syntax and get easy AC.

Personally, I don’t understand the location of the streets and pedestrian crossings at all. It was hoped that the layout would be based on actual streets. I opened the map, and these two streets are generally parallel... The authors could at least draw a picture for the stupid...

January 1st 1600 is sunday, not monday!

Why can't I construct strings like "aa...a"? There is only one palindrome (the whole string) and it's the minimum value of palindromes obviously. Where is the contradiction the the statement?

1 3
d
c a
a b
b c

I'm the first one, who stuck on this test, my program written in Kotlin (probably, same rules applies to Java).
I don't understand, what is "maximum precision"? Should I use double, float or maybe bigdecimal?

My program calculates side lengths, area of the triangle (via sides), angles (via sides and acos), and result point C_2.

Any help is really welcome!

import kotlin.math.*

class Point(val x: Int, val y: Int) {

    constructor(raw: String) :
            this(raw.split(' ')[0].toInt(), raw.split(' ')[1].toInt())

    override fun toString(): String = "$x $y"
}

class Vector(p1: Point, p2: Point) {
    private val x = p1.x - p2.x
    private val y = p1.y - p2.y
    fun length(): Double = sqrt((x*x + y*y).toDouble())
}

fun angle(v1: Vector, v2: Vector, v3: Vector): Double =
    acos(
        (v1.length().pow(2) + v2.length().pow(2) - v3.length().pow(2))
                / (2 * v1.length() * v2.length())
    )

fun triangleSquare(v1: Vector, v2: Vector, v3: Vector): Double {
    val halvedSideSum = (v1.length() + v2.length() + v3.length()) / 2.0
    return sqrt(
        halvedSideSum *
                (halvedSideSum - v1.length()) *
                (halvedSideSum - v2.length()) *
                (halvedSideSum - v3.length())
    )
}

fun Double.fuzzyEquals(other: Double): Boolean = (abs(this - other) < 1e-10)

fun Double.fuzzyEqualsLow(other: Double): Boolean = (abs(this - other) < 1e-4)

fun main() {
    // input
    val pointA = Point(readln())
    val pointB = Point(readln())
    val pointC = Point(readln())

    // solution
    val fixedPointA = Point(0, 0)
    val fixedPointB = Point(pointB.x - pointA.x, pointB.y - pointA.y)
    val fixedPointC = Point(pointC.x - pointA.x, pointC.y - pointA.y)

    val sideAB = Vector(fixedPointA, fixedPointB)
    val sideBC = Vector(fixedPointB, fixedPointC)
    val sideAC = Vector(fixedPointA, fixedPointC)

    val angleBAC = angle(sideAB, sideAC, sideBC)
    val angleACB = angle(sideAC, sideBC, sideAB)
    val angleCBA = angle(sideBC, sideAB, sideAC)

    // find h
    val h = 2.0 / sideAC.length() * triangleSquare(sideAB, sideBC, sideAC)
    // tan ACB = h / x
    val x = h / tan(angleACB)
    val subtractVectorLength = 2.0 * x
    val ratio = (sideAC.length() - subtractVectorLength) / sideAC.length()

    if (ratio <= 0.0 || ratio.fuzzyEquals(0.0) || ratio.fuzzyEqualsLow(1.0)) println("YES")
    else {
        println("NO")
        println(fixedPointA)
        println(fixedPointB)
        println(
            "%.20f".format(fixedPointC.x * ratio) +
                " ${"%.20f".format(fixedPointC.y * ratio)}")
    }
}

Edited by author 22.07.2024 22:53

a < b и p1 = q1, p2 = q2, …, pa = qa.

3 3
a
b
c
a d
b e
c f

Please give me some test that can help me