gpt4 book ai didi

c# - Google CodeJam Bathroom Stalls 2017 Qualification Round 大数据集错误

转载 作者:太空宇宙 更新时间:2023-11-03 15:06:09 24 4
gpt4 key购买 nike

我正在尝试解决 Google CodeJam 2017 "Bathroom Stalls" problem C - 链接中提供了解决方案,下面我的 C# 代码在 small1 和 2 集上运行良好。大集合看起来解决得很好,但在线判断失败了,因为不正确。有谁知道为什么?我尝试使用 ulong,我尝试检测溢出,我通过 bruteforce 与小集合进行比较以找到相同的解决方案。

    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

最佳答案

正如@Jo 在评论中所说,您对案例 #11 的回答不正确(应该是:

案例 #11:500000000000000000 499999999999999999

)

我怀疑错误出在您用于将整数拆分为子问题的公式中(再次转换回 ulong 时您可能会失去精度)。

您可以通过避免将 float 除以 2.0 并改为移动值来解决此问题。这是我解决它的方法(在 Python 中):

def split(value):

n = value >> 1

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

关于c# - Google CodeJam Bathroom Stalls 2017 Qualification Round 大数据集错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43462883/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com