QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#344337#8244. Digit TranslationHaidy_Yasser#WA 247ms137136kbC++142.0kb2024-03-04 03:18:352024-03-04 03:18:35

Judging History

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

  • [2024-03-04 03:18:35]
  • 评测
  • 测评结果:WA
  • 用时:247ms
  • 内存:137136kb
  • [2024-03-04 03:18:35]
  • 提交

answer

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

#define pb push_back
#define sz(x) int(x.size())
#define all(vec) vec.begin(), vec.end()
#define rall(vec) vec.rbegin(), vec.rend()
#define cin(v) for (auto& cn : v)  cin >> cn;
#define cout(v) for (auto &cn : v) cout << cn << " ";
#define MOD int(1e9+7)
// #define endl "\n"
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

void Haidy()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    //freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
#endif
}
 
void solve();
int main()
{
    Haidy();
    int t = 1;
    // cin >> t;
    for(int i = 1;i<=t; i++)
    {
        solve();
    }
    return 0;
}
// int dx[] = {0, 0, 1, -1, 1, -1, 1, -1};
// int dy[] = {1, -1, 0, 0, 1, -1, -1, 1};

string s;
int n;
vector<int> dp, vis;
set<string> num = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};

int rec(int i){
    if(i == n) return 0;
    if(~dp[i]) return dp[i];
    int ans = 1e9;
    for(int j = 1; j <= 5; j++){
        if(i + j <= n){
            string sub = s.substr(i, j);
            if(num.count(sub)){
                ans = min(ans, rec(i + j) + 1);
            }
        }
    }
    ans = min(ans, rec(i + 1) + 1);
    return dp[i] = ans;
}

ll cnt = 1;
ll mod = 9302023;
void paths(int i){
    if(i == n) return;
    ll cur = 0;
    if(vis[i]) return;
    vis[i] = 1;
    for(int j = 1; j <= 5; j++){
        if(i + j <= n){
            string sub = s.substr(i, j);
            if(num.count(sub)){
                if(dp[i] == dp[i + j] + 1){
                    cur++;
                    paths(i + j);
                }
            }
        }
    }
    if(dp[i] == dp[i + 1] + 1){
        cur++;
        paths(i + 1);
    }
    cur = max(cur, 1LL);
    cnt = (cnt * cur) % mod;
}
 
void solve()
{
    cin >> s;
    n = sz(s);
    dp.assign(n+2, -1);
    vis.assign(n+2, 0);
    cout << rec(0) << endl;
    paths(0);
    cout << cnt;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

icecreamcone

output:

10
1

result:

ok 2 lines

Test #2:

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

input:

onetwo

output:

2
1

result:

ok 2 lines

Test #3:

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

input:

twone

output:

3
2

result:

ok 2 lines

Test #4:

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

input:

a

output:

1
1

result:

ok 2 lines

Test #5:

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

input:

zero

output:

1
1

result:

ok 2 lines

Test #6:

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

input:

one

output:

1
1

result:

ok 2 lines

Test #7:

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

input:

two

output:

1
1

result:

ok 2 lines

Test #8:

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

input:

three

output:

1
1

result:

ok 2 lines

Test #9:

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

input:

four

output:

1
1

result:

ok 2 lines

Test #10:

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

input:

five

output:

1
1

result:

ok 2 lines

Test #11:

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

input:

six

output:

1
1

result:

ok 2 lines

Test #12:

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

input:

seven

output:

1
1

result:

ok 2 lines

Test #13:

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

input:

eight

output:

1
1

result:

ok 2 lines

Test #14:

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

input:

nine

output:

1
1

result:

ok 2 lines

Test #15:

score: 0
Accepted
time: 247ms
memory: 137136kb

input:

enfzncejemisgzoqnzkgtltxvxybvwddlpsndjyemdcbxyifzjygquvkvbmuhoblihvbxuthwryohdosidsfuzpzgixpkconlbpgscilqqvpblzmwuyrmvwngpnftlcmkjrjsdvgosnnbkldmrrkmucrqyulyxpqehztlssgpmcdsmzylvzaclzgvzaaajsfyyssmthmlaxmudbmmubwdtuifgryoxhorzhjvqxmjcqirlcmvfuttraqyjeztbilbvygakdhxzvyrqcddljjcgzcolvqljabluixyerpevtp...

output:

999618
2

result:

ok 2 lines

Test #16:

score: -100
Wrong Answer
time: 164ms
memory: 49184kb

input:

zerofoureightfourzerofourthreesixfiveonesixoneighteighthreefoursixzeroeighteightzeroneightsevenfourseveneightwoeightwosixninesevenseventwonineightonezerosixonesixsixsixzeroeightsixzerothreefoursevenfourfiveninefiveninetwofouronesevenseventhreesixfoursixfourninesixonesevenzerofourzeroninezeroseveneig...

output:

290113
4667259

result:

wrong answer 2nd lines differ - expected: '4873734', found: '4667259'