QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#344322#8244. Digit TranslationHaidy_Yasser#WA 237ms148820kbC++141.8kb2024-03-04 01:07:592024-03-04 01:08:00

Judging History

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

  • [2024-03-04 01:08:00]
  • 评测
  • 测评结果:WA
  • 用时:237ms
  • 内存:148820kb
  • [2024-03-04 01:07:59]
  • 提交

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;
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(){
    for(int i = 0; i < n; i++){
       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 && dp[i] == dp[i + 1] + 1){
                        cnt = (cnt * 2) % mod;
                    }
                }
            }
        
       }
    }
}
 
void solve()
{
    cin >> s;
    n = sz(s);
    dp.assign(n+2, -1);
    cout << rec(0) << endl;
    paths();
    cout << cnt;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

icecreamcone

output:

10
1

result:

ok 2 lines

Test #2:

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

input:

onetwo

output:

2
1

result:

ok 2 lines

Test #3:

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

input:

twone

output:

3
2

result:

ok 2 lines

Test #4:

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

input:

a

output:

1
1

result:

ok 2 lines

Test #5:

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

input:

zero

output:

1
1

result:

ok 2 lines

Test #6:

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

input:

one

output:

1
1

result:

ok 2 lines

Test #7:

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

input:

two

output:

1
1

result:

ok 2 lines

Test #8:

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

input:

three

output:

1
1

result:

ok 2 lines

Test #9:

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

input:

four

output:

1
1

result:

ok 2 lines

Test #10:

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

input:

five

output:

1
1

result:

ok 2 lines

Test #11:

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

input:

six

output:

1
1

result:

ok 2 lines

Test #12:

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

input:

seven

output:

1
1

result:

ok 2 lines

Test #13:

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

input:

eight

output:

1
1

result:

ok 2 lines

Test #14:

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

input:

nine

output:

1
1

result:

ok 2 lines

Test #15:

score: 0
Accepted
time: 237ms
memory: 148820kb

input:

enfzncejemisgzoqnzkgtltxvxybvwddlpsndjyemdcbxyifzjygquvkvbmuhoblihvbxuthwryohdosidsfuzpzgixpkconlbpgscilqqvpblzmwuyrmvwngpnftlcmkjrjsdvgosnnbkldmrrkmucrqyulyxpqehztlssgpmcdsmzylvzaclzgvzaaajsfyyssmthmlaxmudbmmubwdtuifgryoxhorzhjvqxmjcqirlcmvfuttraqyjeztbilbvygakdhxzvyrqcddljjcgzcolvqljabluixyerpevtp...

output:

999618
2

result:

ok 2 lines

Test #16:

score: -100
Wrong Answer
time: 213ms
memory: 50012kb

input:

zerofoureightfourzerofourthreesixfiveonesixoneighteighthreefoursixzeroeighteightzeroneightsevenfourseveneightwoeightwosixninesevenseventwonineightonezerosixonesixsixsixzeroeightsixzerothreefoursevenfourfiveninefiveninetwofouronesevenseventhreesixfoursixfourninesixonesevenzerofourzeroninezeroseveneig...

output:

290113
7457277

result:

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