QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#222308 | #3837. The Matching System | BUET_POTATOES# | AC ✓ | 6ms | 7776kb | C++20 | 1.6kb | 2023-10-21 16:40:57 | 2023-10-21 16:40:58 |
Judging History
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