Google CodeJam 욕실 포장 마차 2017 자격 대형 데이터 세트 오류

해결책은 링크에서 제공되며 아래의 C# 코드는 small1에 적합합니다. & 2 세트. 큰 세트는 정상적으로 처리되었지만 온라인 판사는 이 (가)으로 잘못 작성되었습니다. 누구나 아이디어가 있습니까? 나는 ulong을 사용해 보았습니다. 오버플로를 탐지하려고 시도했지만, 동일한 솔루션을 찾기 위해 bruteforce를 통해 작은 세트와 비교를 실행했습니다.Google 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으로 부동 소수점 나누기를 피하고 대신 값을 이동하여이 문제를 해결할 수 있습니다. 다음은 파이썬에서이 문제를 해결 한 방법입니다 :

def split(value): 

    n = value >> 1 

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

출처

2018-03-04 09:45:05 carrdelling

Google CodeJam 욕실 포장 마차 2017 자격 대형 데이터 세트 오류

답변

관련 문제