QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#877578#9757. Brownian BearsanahartmannAC ✓1ms4992kbC++141.5kb2025-01-31 23:32:522025-01-31 23:32:52

Judging History

This is the latest submission verdict.

  • [2025-01-31 23:32:52]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 4992kb
  • [2025-01-31 23:32:52]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int l, b1, b2, d;

int dp[100][100][31];

int solve(int u1, int u2, int dat)
{
    int u1p = 1, u1d = 1, u2p = 1, u2d = 1;
    if (dat > d)
    {
        return 0;
    }

    if (u1 > l || u2 > l || u1 < 1 || u2 < 1)
    {
        return 0;
    }

    if (dp[u1][u2][dat] != -1)
    {
        return dp[u1][u2][dat];
    }

    if (u1 == u2)
    {
        return 1;
    }

    if (u1 == 1)
    {
        u1d = 0;
    }
    if (u1 == l)
    {
        u1p = 0;
    }

    if (u2 == 1)
    {
        u2d = 0;
    }

    if (u2 == l)
    {
        u2p = 0;
    }
    // cout << dp[u1][u2][dat] << " " << u1 << " " << u2 << " " << dat << endl;
    dp[u1][u2][dat] = solve(u1 + u1p, u2 + u2p, dat + 1) + solve(u1 - u1d, u2 + u2p, dat + 1) + solve(u1 + u1p, u2 - u2d, dat + 1) + solve(u1 - u1d, u2 - u2d, dat + 1);

    return dp[u1][u2][dat];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> l >> b1 >> b2 >> d;

    for (int i = 0; i < 100; i++)
    {
        for (int j = 0; j < 100; j++)
        {
            for (int k = 0; k < 31; k++)
            {
                dp[i][j][k] = -1;
            }
        }
    }

    int r = l * 2;
    int a = solve(b1, b2, 0);
    if (a == 0)
    {
        r = 1;
    }
    else

        if (r % a == 0)
    {

        r /= a;
        a /= a;
    }

    cout
        << a << "/" << r << endl;
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 4992kb

input:

4 1 2 2

output:

3/8

result:

ok single line: '3/8'

Test #2:

score: 0
Accepted
time: 0ms
memory: 4992kb

input:

6 2 5 2

output:

0/1

result:

ok single line: '0/1'

Test #3:

score: 0
Accepted
time: 1ms
memory: 4864kb

input:

2 1 2 1

output:

1/2

result:

ok single line: '1/2'