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錯誤的答案

回答

相關問題