Codechef KCHAR错误的答案

最近我解决以下problem on codechef：Codechef KCHAR错误的答案

爱丽丝已经与厨师发生争吵最近。所以厨师给艾丽丝一个问题。最初给你一个空字符串，并允许执行两个操作。

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

厨师给出以下生成方程小号_Ñ = S _N-1 + “一” +操作-1（操作-2（S _N-1））

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

爱丽丝容易找出未来数序列：

S1 = “一”
S2 = “AAC”
S3 = “aacaacc”

现在厨师要求找到S的第K个字符_LOC，其中LOC = 10 。你需要帮助爱丽丝找到答案。

1≤：T≤100
1≤ķ≤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时，我提交。任何人都可以提供一些解决方案失败的测试案例。

来源

2017-07-05 sibasish jena

您是否检查过大k的数值不准确？大k似乎不太可能完全等于pow（2，double（log（k）/ log（2）））'。 –

例如，当k是'1ULL << 29'时 –

是的，即使k = 10^18也给出正确的答案 –

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

以找到发生故障的情况下，我写我自己的代码版本，并试图测试它的k许多值。这没有任何东西，所以然后尝试接近2的权力。那找到了上面的例子。

下面是查找问题案例的代码（这里是x()是您的代码，y()是我的代码）。我将assert s添加到了代码中，它演示了这个问题，但是您可以删除它们并查看代码没有终止。

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

来源

2017-07-05 20:07:36

虽然@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; 
}

我的解决方案是基于以下主要意见：

S_n = S_(n-1) + "a" + REPLACE(S_(n-1), mid_point, "c")
K <= 10^18意味着n <= 60，其长度足够长，以覆盖所有K小号
基于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的特殊地位，如果是的，我们已经找到了答案，否则，答案是等于搜索在S_(n-1)

来源

2017-07-06 03:10:03 shole

相对位置K'而不是执行每一次迭代60按shole的回答可以改为尝试这个办法：对于第一次迭代

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

。

来源

2017-12-30 11:58:18 hari

Codechef KCHAR错误的答案

回答

相关问题