QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#222308#3837. The Matching System BUET_POTATOES#AC ✓6ms7776kbC++201.6kb2023-10-21 16:40:572023-10-21 16:40:58

Judging History

你现在查看的是最新测评结果

  • [2023-10-21 16:40:58]
  • 评测
  • 测评结果:AC
  • 用时:6ms
  • 内存:7776kb
  • [2023-10-21 16:40:57]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int nmax = 100;
const int N = 1e3 + 5, MOD = 1e9 + 7;
int dp[N][N];
int getAns(int n){
    dp[0][0] = 0;
    for(int i = 1; i < n; i++)dp[i][0] = 1;
    dp[n][0] = 2;

    for(int i = 1; i <= n - 2; i++){
        for(int j = 1; j <= n; j++)dp[j][i - 1] = (dp[j][i - 1] + dp[j - 1][i - 1]) % MOD;
        for(int j = 0; j <= n; j++){
            dp[j][i] = 0;
//            for(int k = 0; k <= j; k++){
//                dp[j][i] += dp[j - k][i - 1] + 1;
//            }
            dp[j][i] += dp[j][i - 1] + (j + 1);
            dp[j][i] %= MOD;
        }
    }

//    for(int i = 0; i <= n - 2; i++){
//        for(int j = 0; j <= n; j++)cout << dp[j][i] << ' ';
//        cout << endl;
//    }
//    cout << dp[n][n - 2] << "\n";
    return dp[n][n - 2];
}

int getAns2(int n){
    long long ans = 4;
    for(int i = 3, cur = 3, j = 0; i <= n; i++, j++){
        ans += cur;
        if(j)cur++, j = -1;
    }
    return ans % MOD;
}

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

    int n;
    cin >> n;
    if(n == 1){
        cout << "0\n0\n1\n*\n0\n2\n";
        return 0;
    }

    if(n == 2){
        cout << "*0\n00\n3\n*0\n00\n4\n";
        return 0;
    }

    cout << string(n - 2, '*') << "0*\n";
    cout << "0" << string(n - 1, '1') << "\n";
    cout << getAns(n) << "\n";

    cout << string((n + 1) / 2, '*') << string(n / 2, '0') << "\n";
    cout << string(n, '0') << "\n";
    cout << getAns2(n) << "\n";



    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3664kb

input:

3

output:

*0*
011
8
**0
000
7

result:

ok Accepted

Test #2:

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

input:

1

output:

0
0
1
*
0
2

result:

ok Accepted

Test #3:

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

input:

2

output:

*0
00
3
*0
00
4

result:

ok Accepted

Test #4:

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

input:

4

output:

**0*
0111
31
**00
0000
10

result:

ok Accepted

Test #5:

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

input:

5

output:

***0*
01111
119
***00
00000
14

result:

ok Accepted

Test #6:

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

input:

6

output:

****0*
011111
456
***000
000000
18

result:

ok Accepted

Test #7:

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

input:

10

output:

********0*
0111111111
99892
*****00000
0000000000
40

result:

ok Accepted

Test #8:

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

input:

20

output:

******************0*
01111111111111111111
31775330
**********0000000000
00000000000000000000
130

result:

ok Accepted

Test #9:

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

input:

30

output:

****************************0*
011111111111111111111111111111
37652369
***************000000000000000
000000000000000000000000000000
270

result:

ok Accepted

Test #10:

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

input:

50

output:

************************************************0*
01111111111111111111111111111111111111111111111111
637736708
*************************0000000000000000000000000
00000000000000000000000000000000000000000000000000
700

result:

ok Accepted

Test #11:

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

input:

100

output:

**************************************************************************************************0*
0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
990322733
**************************************************00000000000000000000000000000000000000...

result:

ok Accepted

Test #12:

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

input:

200

output:

******************************************************************************************************************************************************************************************************0*
011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok Accepted

Test #13:

score: 0
Accepted
time: 2ms
memory: 6932kb

input:

499

output:

************************************************************************************************************************************************************************************************************************************************************************************************************...

result:

ok Accepted

Test #14:

score: 0
Accepted
time: 5ms
memory: 7336kb

input:

888

output:

************************************************************************************************************************************************************************************************************************************************************************************************************...

result:

ok Accepted

Test #15:

score: 0
Accepted
time: 3ms
memory: 7564kb

input:

999

output:

************************************************************************************************************************************************************************************************************************************************************************************************************...

result:

ok Accepted

Test #16:

score: 0
Accepted
time: 6ms
memory: 7776kb

input:

1000

output:

************************************************************************************************************************************************************************************************************************************************************************************************************...

result:

ok Accepted