c++ - Codechef Q-为什么我收到 “Wrong Answer”错误

Question

问题-利沃夫动物园的小象非常喜欢幸运数字。每个人都知道幸运数字是正整数，其小数表示仅包含幸运数字4和7。例如，数字47、744、4是幸运数字，而5、17、467不是。

令F4(X)为X的十进制表示形式的位数4，而F7(X)为X的十进制表示形式的位数7。例如，F4(456)= 1，F4(444) = 3，F7(1)= 0，F7(747)=2。小象想知道最大乘积F4(X)∙F7(X)，其中L≤X≤R。换句话说，他想知道值(value)
max {F4(X)∙F7(X):L≤X≤R}。

1 <= L <= R <= 1018

例:
1)对于范围， 1100 答案将为1 {47,74}

2)4199 6000答案将是4 {4747，4477}

我觉得我的代码是正确的，但是提交后得到的结论是错误的答案。谁能帮助我找出问题出在哪里？

我的算法不会错(非常简单)。我仔细检查了实现(它处理了所有可能的情况)。很难相信某些输入是错误的。

这是C++代码:

#include <cstdio>
#include <cstring>
using namespace std;
char buf1[20],buf2[20];
int *L, *R, *ans, len, ansn;
bool flagL, flagR;

inline int count(int n)
{
    int a=0,c=0;
    for(;a<len;a++) if(ans[a] == n) c++;
    return c;
}
inline int max(int a, int b) { return a>b ? a:b; }
inline int min(int a, int b) { return a<b ? a:b; }

inline void f(int i, int n)
{
    int a=0,n4=0,n7=0,t;
    for(;a<=i;a++) if(ans[a] == 4) n4++; else if(ans[a] == 7) n7++;
    while(n)
    {
        if(n4 == n7)
        {
            n4 += n/2;
            n7 += (n-n/2);
            break;
        }
        else if(n4 > n7)
        {
            t = min(n,n4-n7);
            n -= t;
            n7 += t;
        }
        else if(n7 > n4)
        {
            t = min(n,n7-n4);
            n -= t;
            n4 += t;
        }
    }
    ansn = max(ansn,n4*n7);
}

void solve(int i, bool flagL, bool flagR)
{
    while(i<len)
    {
        if(flagL && !flagR)
        {
            if(4 > L[i])
            {
                f(i-1,len-i);
                return;
            }
                    if(4 == L[i])
            {
                ans[i] = 4;
                solve(i+1, 1, 0);
                ans[i] = 7;
                f(i,len-i-1);
                return;
            }
            if(7 > L[i])
            {
                ans[i] = 7;
                f(i,len-i-1);
                return;
            }
            if(7 == L[i])
            {
                ans[i] = 8;
                f(i,len-i-1);
                ans[i] = 7;
                i++;
                continue;
            }
            // else
                ans[i] = 9;
                if(ans[i] > L[i])
                {
                    f(i,len-i-1);
                    return;
                }
                else
                {
                    i++;
                    continue;
                }
        }
        if(!flagL && flagR)
        {
            if(7 < R[i])
            {
                f(i-1,len-i);
                return;
            }
            if(7 == R[i])
            {
                ans[i] = 4;
                f(i,len-i-1);
                ans[i] = 7;
                i++;
                continue;
            }
            if(4 < R[i])
            {
                ans[i] = 4;
                f(i,len-i-1);
                return;
            }
            if(4 == R[i])
            {
                ans[i] = 3;
                f(i,len-i-1);
                ans[i] = 4;
                i++;
                continue;
            }
            // else
                ans[i] = 0;
                if(ans[i] < R[i])
                {
                    f(i,len-i-1);
                    return;
                }
                else
                {
                    i++;
                    continue;
                }
        }
        if(flagL && flagR)
        {
            if(R[i] - L[i] == 1)
            {
                ans[i] = L[i];
                solve(i+1,1,0);
                ans[i]++;
                solve(i+1,0,1);
                return;
            }
            bool four = 4 > L[i] && 4 < R[i];
            bool sev = 7 > L[i] && 7 < R[i];
            if (four && sev)
            {
                f(i-1,len-i);
                return;
            }
            else if (four && !sev)
            {
                ans[i] = 4;
                f(i,len-i-1);
            }
            else if (!four && sev)
            {
                ans[i] = 7;
                f(i,len-i-1);
            }
            if (L[i] == 4 || L[i] == 7 || R[i] == 4 || R[i] == 7)
            {
                if(L[i] == R[i]) { ans[i] = L[i]; i++; continue; }

                if(L[i] == 4 && R[i] == 7)
                {
                    ans[i] = 4;
                    solve(i+1,1,0);
                    ans[i] = 7;
                    solve(i+1,0,1);
                    ans[i] = 5;
                    f(i,len-i-1);
                    return;
                }
                if(R[i] - L[i] >= 2)
                {
                    ans[i] = L[i]+1;
                    f(i,len-i-1);

                    if(L[i] == 4 || L[i] == 7)
                    {
                        ans[i] = L[i];
                        solve(i+1,1,0);
                    }
                    if(R[i] == 4 || R[i] == 7)
                    {
                        ans[i] = R[i];
                        solve(i+1,0,1);
                    }
                    return;
                }
            }
            else
            {
                if (R[i] - L[i] >= 2)
                {
                    ans[i] = L[i]+1;
                    f(i,len-i-1);
                    return;
                }
                ans[i] = L[i];
            }
        }
        i++;
    } // end of while
    ansn = max(ansn, count(4)*count(7));
}

int main()
{
    int a,t; scanf("%d\n",&t);
    while(t--) // test cases
    {
        scanf("%s %s",&buf1,&buf2);
        len = strlen(buf2);
        L = new int[len];
        R = new int[len];
        ans = new int[len];
        for(a=0;a<len;a++) R[a] = buf2[a]-48;
        for(a=0;a<len-strlen(buf1);a++) L[a] = 0;
        int b=a;
        for(;a<len;a++) L[a] = buf1[a-b]-48;
        flagL = flagR = 1; ansn = 0;
        solve(0,1,1);
        printf("%d\n",ansn);
    }
    return 0;
}

算法:

首先，将L，R的数字放入长度= no的数组L []，R []中。并初始化数组ans []来跟踪答案整数(F4(ans)* F7(ans)最大的整数)。

在左侧填充L到0，以使其长度等于R。 (所以1,100变成001,100)
这是在main()本身中完成的，然后再调用solve()

真正的逻辑:
为i在范围(0，len(R))中运行循环
对于每个i，比较L [i]和R [i]

变量 flagL 和 flagR 告诉您是否需要分别检查L和R。

假设L []，R []最初是:
238967
首先，我们需要从第0个索引开始检查它们(因此，solve(0,1,1)或solve(0，true，true))。

现在4和7都在 L [0]和R [0]之间落入 。因此{4,7}的任何排列都可以放在3位数字中，而ans []不会超出 [L，R] 范围。因此答案将为2。

如果范围是:
238和545

在 2和5之间的 中只有4个落入，因此我们将4放入ans [0]中，并且{4,7}的任何排列都可以放在其余位置。所以答案还是2。

如果范围是:
238和410

L [0]和R [0]之间都不是4或7。
但请注意，R [0]为4。

因此，我们现在有2个选择，分别是4和L [0] +1(这是递归的地方)

为什么L [0] +1？因为如果将L [0] +1放在ans [0]中，则ans [0]会落在L [0]和R [0]之间(对此R [0]-L [0]> = 2)并且不管我们把剩下的数字放在哪，ans []都不会超出范围。但是我们还必须检查ans [0]是否为4。在最后一个示例中，它无济于事，但是如果R> = 477则将这样做。

因此答案将是1。(如果R> = 477，则为2)

让我们讨论另一个例子:

射程:4500 5700

因为R [0]和L [0]仅相差1，所以我们必须检查两者，一次是ans [i] = L [i]，然后ans [i] = R [i](或ans [i ] ++)

现在，如果我们检查ans [i] = 4，则不再需要比较ans [i]和R [i]，因为ans [0] ans 将始终为< R 。所以我们像这样递归地调用solve():solve(i + 1，true，false)

下次，当ans [0] = R [0]时，我们将不必将ans与L进行比较(因为ans> L，所以我们把剩下的2个地方都放进去)。然后我们像这样调用solve():solve(i + 1，false，true)。

您将了解其工作方式，并且，如果您查看我的代码，就不会遗漏任何可能的测试用例。我不知道为什么要得到WA。

PS:安德鲁指出了错误。条件的顺序是错误的。 if块 4 == L[i]应该在if块 7 > L[i]之前。现在，代码可以正常工作。

Answer 1

        if(7 > L[i]) // 7 > 4 ?
        {
            ans[i] = 7;
            f(i,len-i-1);
            return;
        }
        if(4 == L[i])  // how is this ever reachable?
        {
            ans[i] = 4;
            solve(i+1, 1, 0);
            ans[i] = 7;
            f(i,len-i-1);
            return;
        }

我想你的意思是:

-            if(7 > L[i])
+            if(7 < L[i])