I used dp[901][8101] for dynamic programming,but I got TLE.Can anyone give me some hints?

Edited by author 22.10.2024 17:34

Post the code for this task, or what is wrong in my code?
import math
from decimal import Decimal, getcontext, ROUND_CEILING

getcontext().prec = 210

for _ in range(int(input())):
    H, l, h = map(int, input().split())
    H = Decimal(str(H))
    l = Decimal(str(l))
    h = Decimal(str(h))
    a = Decimal(str(math.sin(math.atan(H / l))))
    d = Decimal("4") * h * a
    g = Decimal(((H * H) + (l * l)) ** Decimal("0.5"))
    lm = Decimal("0")
    rm = Decimal("1e200")
    for i in range(700):
        mid = (lm + rm) / Decimal("2")
        if (d * (mid + 1) * mid) <= g:
            lm = mid
        else:
            rm = mid
    print(rm.quantize(Decimal('1'), rounding=ROUND_CEILING))

Edited by author 20.10.2024 02:41

In the statement, "any symbol" means NOT any valid ASCII char, but any byte, including those with codes 128..255. Common methods to read text in Rust, including stdin().read_line, expect valid UTF-8 and therefore crash on test 2 where bytes 128..255 are present. I got AC with this:

let mut reader = BufReader::new(stdin());
let mut s = Vec::new();
reader.read_until(10, &mut s).unwrap();

Nevermind. Solved.

I've detected my error with this input:

11 10
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5 9
6 10
7 11

5 roads can be blocked.

Edited by author 29.08.2011 22:33

Wrong answer, test 30. Don't now what to do

WA 15: "Teams are as close in their sizes as possible." It doesn't mean that the size of one of the commands must be exactly n//2.
Wa 25: "Every team has at least one member"

Edited by author 15.10.2024 20:07

use dynamic programming by subsets, one mask in DP state for one breath in a row and two masks in DP state for two breaths in a row, time complexity ~O(k * (n+m)^2 * 4^(n+m))

I had WA7....corrected one error but now getting WA18...Mods please give me 18th test case...
Thanks...

Edited by author 09.01.2009 13:12

Some of my AC solutions don't pass this test:
3
9999 10000 1 A
-9990 9999 999 B
-10000 9999 1000 C
1
9999 10000 -10000 9998

Right answer:
Power on. CELL_ID:A, SIGNAL_LEVEL:VIOLET
Signal changed. SIGNAL_LEVEL:INDIGO
Signal changed. SIGNAL_LEVEL:BLUE
Signal changed. SIGNAL_LEVEL:GREEN
Signal changed. SIGNAL_LEVEL:YELLOW
Signal changed. SIGNAL_LEVEL:ORANGE
Signal changed. SIGNAL_LEVEL:RED
Cell changed. CELL_ID:C, SIGNAL_LEVEL:ORANGE
Signal changed. SIGNAL_LEVEL:YELLOW
Signal changed. SIGNAL_LEVEL:GREEN
Signal changed. SIGNAL_LEVEL:BLUE
Signal changed. SIGNAL_LEVEL:INDIGO
Signal changed. SIGNAL_LEVEL:VIOLET

Edited by author 05.11.2014 21:55

Edited by author 05.11.2014 21:56

input:
2
1 600000
1
600001

output:
599999

The problem is not that difficult, therefore for me the most interesting question is the smallest program possible to write for this problem.
Let's define the size of the program as H x W in your solution. Mine is 6 x 8. Who's smaller? =)

For big tests (at least for n >= 44, but may be works for smaller n's) you can assume that firstt 4 numbers are 33 11 22 44

Edited by author 07.10.2024 02:40

Why I have WA#10? I can't think test to get wrong answer. PLS help me

Next my code:

#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

int main()
{
    double a, b, c, x, y, x2, y2;
    double X, Y, Z, X2, Y2, Z2;
    double result = 0;
    bool bflag = true;
    cin >> a >> b >> c;
    for (int i=0; i < 2; i++)
    {
        cin >> x >> y;
        if (x < c)
        {
            X = 0;
            Y = y - b - c;
            Z = x;
        }
        else if (x > c + a)
        {
            X = a;
            Y = y - b - c;
            Z = 2 * c + a - x;
        }
        else
        {
            if (y <= b)
            {
                X = x - c;
                Y = b - y;
                Z = 0;
            }
            else if (y <= b + c)
            {
                X = x - c;
                Y = 0;
                Z = y - b;
            }
            else if (y <= b)
            {
                X = x - c;
                Y = y - b - c;
                Z = c;
            }
            else
            {
                X = x - c;
                Y = b;
                Z = 2 * b + 2 * c - y;
            }
        }
        if (bflag)
        {
            x2 = x;
            y2 = y;
            X2 = X;
            Y2 = Y;
            Z2 = Z;
            bflag = false;
        }
    }
    //cout << X << ' ' << Y << ' ' << Z << ' ' << X2 << ' ' << Y2 << ' ' << Z2; это типа отладка
    X2 -= X;
    Y2 -= Y;
    Z2 -= Z;
    result = sqrt(X2 * X2 + Y2 * Y2 + Z2 * Z2);
    if (result < 1.E-8)
        cout << fixed << setprecision(6) << 0;
    else
        cout << fixed << setprecision(6) << result;

    return 0;
}

подскажите в какие там данные входные

If I delete a branch, does it means that I delete also its sub-braches?

#include <cstdio>

int ncall;
int call[100];

void solve(int K)
{
    if (!K) return;

    if (K % 2 == 0) {
        call[ncall] = ++ncall;
        if (K > 2) solve(K / 2);
    } else {
        call[ncall++] = -1;
        solve(K - 1);
    }
}

int main( void )
{
//    freopen( "p1278.in", "r", stdin );

    int K;
    scanf( "%d", &K );

    if (K > 1) solve(K);
    for (int i = 0; i < ncall; i++)
        printf( "CALL %d\n", call[i] < 0 ? ncall : call[i] );
    printf( "BELL&RET\n" );

    return 0;
}

When finding intersection of segments (a, b) and (c, d) I am finding t1, t2, such that a + (b - a) * t1 = c + (d - a) * t2, -eps <= t1 <= 1+eps, -eps <= t2 <= 1+eps.
This code doesn't work for eps=1e-12, but works for eps=0.

THIS IS MINDBLOWING

Do you know the test#3?
i use heap in this problem but got WA#3.
please help.
sorry for poor english.
thank.

Use stacks.
Push one letter by letter.
If stack.top() == current letter, pop the stack.
else push the letter in the stack.

wrong epsilon, precision problems