Codechef KCHAR错误答案

Question

最近我解决了以下problem on codechef：

爱丽丝最近和厨师争吵。所以Chef给Alice一个问题。最初，您将获得一个空字符串，并且允许执行两个操作。

操作-1：每个'a'变为'c'，每个'c'变为'a'。例如，“acc”变为“caa”。 操作-2：字符串反转。例如，“acc”变为“cca”。

厨师给出以下生成方程式SN = SN-1 +“a”+操作-1（操作-2（SN-1））

其中S0 =“”（空字符串）。

爱丽丝很容易发现接下来的几个序列：

S1 =“a” S2 =“aac” S3 =“aacaacc”

现在，Chef要求找到SLOC的Kth字符，其中LOC = 102017.您需要帮助Alice找到答案。

1≤T≤100 1≤K≤1018

我试图使用以下代码解决问题：

scanf("%lld",&t);
while(t--)
{
    scanf("%lld",&k);
    count=0;
    while(1)
    {
        lg=(double)log(k)/log(2);
        av=pow(2,lg);
        if(av!=k)
        {
            diff=k-av;
            k=av-diff;
            count++;
        }
        else
        {
            if(count%2==0)
            {
                printf("a\n");
            }
            else
            {
                printf("c\n");
            }
            break;
        }
    }       

}

解决方案有什么问题？

我已经尝试了各种输入，但我得到了正确答案，但是当我提交时，我正在获得WA。任何人都可以提供一些解决方案失败的测试用例。

Answer 1

您的代码不适用于k=576460752303423478。它不会终止。我没有完全调试它，但根本原因是数值不准确：av应该是小于或等于k的2的最大幂，但它最终大于k。我希望还有其他情况会终止，但会产生错误的结果。

为了找到失败的案例，我编写了自己的代码版本，并尝试对k的许多值进行测试。这没有发现任何东西，所以然后尝试近2的力量。这找到了上面的例子。

这是找到问题情况的代码（这里x()是你的代码，y()是我的代码）。我将asserts添加到您的代码中以证明问题，但您可以删除它们并看到代码不会终止。

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

char x(long long int k) {
    long long int count=0;
    while(1) {
        long long int lg=(double)log(k)/log(2);
        long long int av=pow(2,lg);
        assert((av & (av-1)) == 0); // av is a power of 2
        assert(av <= k);  // ... that's at most k
        if(av!=k) {
            long long int diff=k-av;
            k=av-diff;
            count++;
        } else {
            if(count%2==0) return 'a';
            return 'c';
        }
    }
}

char y(long long int k) {
    int count = 0;
    long long int j = 1;
    while(j < k) j *= 2;
    while (1) {
        if (j == k) {
            return count % 2 ? 'c' : 'a';
        } else if (k > j) {
            k = 2*j-k;
            count += 1;
        }
        j >>= 1;
    }
}

int main(int argc, char **argv) {
    int t = 60;
    while(t--) {
        for (int k = -10; k < 10; k++) {
            long long int r = (1LL<<t) + k;
            if (r <= 0) continue;
            printf("%lld\n", r);
            printf("y: %c\n", y(r));
            printf("x: %c\n", x(r));
            if (x(r) != y(r)) exit(1);
        }
    }
    return 0;
}

Answer 2

虽然@PaulHankin解释了你的解决方案有什么问题

这是我用C ++ 14编写的公认解决方案

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

LL k;
int T;
string f(int N, LL K){
    LL len = (1LL<<N)-1;
    LL pLen = (1LL<<(N-1)) - 1;
    if(K == len/2 + 1LL) return "a";
    if(K == len - pLen/2) return "c";
    return f(N-1, K < len/2+1LL? K : K-len/2-1LL);
}

int main() {
    cin >> T;
    while(T--){
        cin >> k;
        cout << f(60, k) << endl;
    }
    return 0;
}

我的解决方案基于以下主要观察结果：

1. S_n = S_(n-1) + "a" + REPLACE(S_(n-1), mid_point, "c")
2. K <= 10^18暗示n <= 60，其长度足以覆盖所有Ks
3. 基于1，对于每个n，有两个特殊的位置，你知道S_n的答案： 3A。 Len(S_n)/2 + 1（这是中点，它必须是"a"） 3B。 Len(S_n) - Len(S_(n-1))/2（这是3/4四分位数，它必须是"c"）

然后算法很简单：看看K是否是当前S_n的特殊位置，如果是，我们找到了答案;否则，答案等于在K'中搜索相对位置S_(n-1)

Answer 3

而不是每次按照shole的答案执行60次迭代，你可以尝试这样做：

N = ceil(log(k)/log(2)); 

第一次迭代。