谷歌CodeJam浴室攤位2017年資格回合大數據集錯誤

我想解決Google CodeJam 2017 "Bathroom Stalls" problem C - 解決方案在鏈接中提供，我的C＃代碼在很小的作品很好1 & 2套。大集看起來解決好，但網上裁判失敗，因爲不正確。有人有想法嗎？我嘗試使用ulong s，我試圖檢測溢出，我通過bruteforce與小組進行比較以找到相同的解決方案。谷歌CodeJam浴室攤位2017年資格回合大數據集錯誤

private string SeatTreeSkip(ulong n, ulong k) 
    { 
     var q = new SortedSet<ulong>(); 
     q.Add(n); 
     var c = new Dictionary<ulong,ulong>(); 
     c[n] = 1; 
     for (ulong i = 0; i < n;) 
     { 
      ulong p = q.Last(); 
      ulong x0 = (ulong)Math.Ceiling((p - 1)/2.0); 
      ulong x1 = (ulong)Math.Floor((p - 1)/2.0); 
      if (p - 1 < 0) 
       p = p; 
      i += c[p]; 

      if (i < 0 || x0 < 0 || x1 < 0) 
       throw new Exception("overflow"); 
      if (i >= k) 
       return x0 + " " + x1; 

      q.Remove(p); 
      q.Add(x0); 
      q.Add(x1); 
      if (!c.ContainsKey(x0)) c.Add(x0, 0); 
      if (!c.ContainsKey(x1)) c.Add(x1, 0); 
      c[x0] += c[p]; 
      c[x1] += c[p]; 
     } 
     throw new Exception("k is over"); 
    }

輸入片段：

4 2 
5 2 
6 2 
1000 1000 
1000 1 
500000000000000000 249999999999999999 
1000000000000000000 500000000000000000 
999999999999999999 423539247696576511 
3 2 
500000000000000000 144115188075855872 
1000000000000000000 1

輸出片段：

Case #1: 1 0 
Case #2: 1 0 
Case #3: 1 1 
Case #4: 0 0 
Case #5: 500 499 
Case #6: 1 0 
Case #7: 1 0 
Case #8: 1 1 
Case #9: 0 0 
Case #10: 1 1 
Case #11: 500000000000000000 500000000000000000

來源

2017-04-18 cDima

看起來案例＃5和案例＃11應該有類似的答案。爲什麼他們中的一個有500 499和其他相同的數字？ –

由於@Jo的評論說，你的回答情況＃11是不正確的（應該是：

Case #11: 500000000000000000 499999999999999999

）

我懷疑這個錯誤出現在你用來將整數分成子問題的公式中（當你重新回到ulong時你可能會失去精度）。

您可以通過避免2.0的浮點除法並改變值來解決此問題。下面是我如何解決它（在Python中）：

def split(value): 

    n = value >> 1 

    return (n, n-1) if value % 2 == 0 else (n, n)

來源

2018-03-04 09:45:05 carrdelling

谷歌CodeJam浴室攤位2017年資格回合大數據集錯誤

回答

相關問題