壊れたパスカルの三角形

壊れたパスカルの三角形

締め切りが 2018/02/21 10:00 AM なので，その 1 分後に投稿されるように予約

設問

【パスカルの三角形】


パスカルの三角形は、上記のように隣り合った数の和を下段に書くことで作ることができます。

【問題】
パスカルの三角形を作るとき、隣り合った数の和を下段に追加していきますが、一か所だけ差を計算してしまっています。
次の図では、4段目・左から3つ目の値が、2 - 1 = 1になっているので、そこから下の部分の数が通常のパスカルの三角形と異なっています。



このような、壊れてしまったパスカルの三角形の一番下の段が入力として与えられたとき、“何段目の”、“左から何番目”の値を求める際に差を計算してしまったのかを特定するプログラムを書いてください。
※「差」は、『大きい方の値から小さい方の値を引く』と考えてください。

【入力・出力】
入力データは1行目にパスカルの三角形の段数k、2行目にk個の整数値が半角スペース区切りで与えられます。
kは最大60です。
k個の整数値は、壊れたパスカルの三角形のk段目を表しています。

これらの値を読み込み、間違えた計算方法で計算してしまった部分（差を計算した部分）を特定し、その段数と左から数えて何番目に当たるかを半角スペース区切りで出力してください。

（例）
※上記の問題文の図を使った例になります。

<入力>

    1.    7
    2.    1 6 13 14 9 4 1

<出力>

    1.    4 3
==================================================

プログラムは簡単なのであるが，k = 60 のときに，32 ビット整数はおろか，64 ビット実数で表現できる整数でも精度が不足して，正しい解が求まらない。
k = 60 のとき，出現する最も大きな数値は 59132290782430712 であるが，これに 1 を足しても 59132290782430713 にはならない

> class(59132290782430712)
[1] "numeric"
> 59132290782430712+1
[1] 59132290782430712

R では gmp パッケージを使えば問題ない。

library(gmp)

f = function(s) {

  s = unlist(strsplit(s, " "))
  y = as.bigz(s)
  n = length(y)
  x = as.bigz(1)
  for (i in 2:n) {
    x = c(x, as.bigz(0))+c(as.bigz(0), x)
  }
  cat(sum(x == y)+1, which(x != y)[1], "\n")
}

しかし，整数で扱える範囲で計算する（10の10乗を法として計算する）ことで，問題は回避できる。

f = function(s) {
  s = gsub("\n", " ", s)
  s = unlist(strsplit(s, " "))
  y = NULL
  for (t in s) {
    m = nchar(t)
    y = c(y, as.numeric(substr(t, max(1, m-9), m))) # 1e10 を法とする数値として解釈
  }
  n = length(y)
  x = 1 # パスカルの三角形を作る
  for (i in 2:n) {
    x = (c(x, 0)+c(0, x)) %% 1e10 # 1e10 を法として計算
  }
  cat(sprintf("%d %d\n", sum(x == y)+1, which(x != y)[1])) # どのように違うかに基づいて答えを出す
}

# f(readLines(file("stdin", "r"))[-1])

x1 = "1 6 13 14 9 4 1"

x2 = "1 11 49 123 204 252 252 204 123 49 11 1"

x3 = "1 23 253 1771 8855 33649 100947 245157 490314 817190 1144066
1352078 1352078 1144066 817190 490314 245157 98667 29089 6575 1771
253 23 1"

x4 = "1 39 741 9119 81591 565197 3153503 14562537 56777028 189763772
550304436 1398372924 3139455436 6271204644 11213769996 18044494260
26247932190 34644933810 41615977590 45587202210 45587202210
41615977590 34644933810 26247932190 18044494260 11213769996
6271204644 3139455436 1398372924 550304436 189763772 56777028
14562537 3153503 565197 81591 9119 741 39 1"

x5 = "1 47 1142 18152 210516 1902124 13971440 85875832 450939170
2054407014 8217773916 29135877368 92263710084 262596771388
675248867776 1575580701224 3348108992719 6499270398125
11554258485614 18851684897584 28277527346376 39049918716424
49699896548176 58343356817424 63205303218876 63205303218876
58343356817424 49699896548176 39049918716424 28277527346376
18851684897584 11554258485616 6499270398159 3348108992991
1575580702584 675248872536 262596783764 92263734836 29135916264
8217822536 2054455634 450978066 85900584 13983816 1906884 211876
18424 1176 49 1"

x6 = "1 59 1711 32509 455126 5006386 45057474 341149446 2217471399
12565671261 62828356305 279871768995 1119487075980 4047376351620
13298522298180 39895566894540 109712808959985 277508869722315
647520696018735 1397281501935165 2794563003870330 5189902721473470
8964377427999630 14420954992868970 21631432489303455
30284005485024837 39602161018878633 48402641245296107
55317304280338408 59132290782430712 59132290782430712
55317304280338408 48402641245296107 39602161018878633
30284005485024837 21631432489303455 14420954992868970
8964377427999630 5189902707355366 2794562806216874
1397280217187701 647515557028879 277494737500211 109684544515777
39853170228228 13250068965252 4004979685308 1091222631772
265739546891 57689366449 11280923797 2019817943 327031342
45057474 5006386 455126 32509 1711 59 1"

f(x1) # 4 3
f(x2) # 5 3
f(x3) # 22 18
f(x4) # 7 4
f(x5) # 33 2
f(x6) # 46 39

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

Python では，Int64 なので問題ない。

>>> import scipy as sp
>>> a = sp.array([59132290782430712])
>>> a.dtype
dtype('int64')
>>> a
array([59132290782430712])
>>> a+1
array([59132290782430713]) 識別されている

def f(s):
  s = s.split()
  n = len(s)
  y = []
  for i in range(n):
    y.append(int(s[i]))
  #print(y)
  x = [1]
  for i in range(2, n+1):
    x1 = x+[0]
    x2 = [0]+x
    for i in range(len(x1)):
      x1[i] += x2[i]
    x = x1
  position = 0
  line = n+1
  for i in range(len(x)):
    if x[i] != y[i]:
      if position == 0:
        position = i+1
      line -= 1
  print(line, position)

# int(input()) # 読み飛ばし
# f(input())   # 文字列を引数として渡す

x1 = "1 6 13 14 9 4 1"
x6 = "1 59 1711 32509 455126 5006386 45057474 341149446 2217471399 12565671261 62828356305 279871768995 "\
"1119487075980 4047376351620 13298522298180 39895566894540 109712808959985 277508869722315 647520696018735 "\
"1397281501935165 2794563003870330 5189902721473470 8964377427999630 14420954992868970 21631432489303455 "\
"30284005485024837 39602161018878633 48402641245296107 55317304280338408 59132290782430712 59132290782430712 "\
"55317304280338408 48402641245296107 39602161018878633 30284005485024837 21631432489303455 14420954992868970 "\
"8964377427999630 5189902707355366 2794562806216874 1397280217187701 647515557028879 277494737500211 "\
"109684544515777 39853170228228 13250068965252 4004979685308 1091222631772 265739546891 57689366449 "\
"11280923797 2019817943 327031342 45057474 5006386 455126 32509 1711 59 1"
f(x1) # 4, 3
f(x6) # 46, 39