algorithm - Codechef KCHAR 错误答案

Question

最近我正在解决以下问题 problem on codechef :

Alice has quarreled with Chef recently. So Chef gives a problem to Alice. Initially you are given an empty string and are allowed following two operations.

Operation-1: Every 'a' becomes 'c' and every 'c' becomes 'a'. For example, "acc" becomes "caa".
Operation-2: String is reversed. For Example, "acc" becomes "cca".

Chef gives following generating equation S_N = S_N-1 + "a" + Operation-1(Operation-2(S_N-1))

where S0 = "" (empty string).

Alice easily finds out next few sequences as:

S1 = "a"
S2 = "aac"
S3 = "aacaacc"

Now Chef asks to find Kth character of S_LOC, where LOC = 10²⁰¹⁷. You need to help Alice find the answer.

1 ≤ T ≤ 100
1 ≤ K ≤ 10¹⁸

我尝试使用以下代码解决问题:

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()是我的代码)。我向您的代码添加了 assert 来演示问题，但您可以删除它们并看到代码没有终止。

#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;
}