結果
| 問題 | No.1747 Many Formulae 2 |
| ユーザー |
 ねるち
|
| 提出日時 | 2022-05-21 08:35:27 |
| 言語 | Nim (2.0.2) |
| 結果 |
AC
|
| 実行時間 | 5 ms / 2,000 ms |
| コード長 | 25,373 bytes |
| コンパイル時間 | 3,415 ms |
| コンパイル使用メモリ | 62,280 KB |
| 実行使用メモリ | 4,348 KB |
| 最終ジャッジ日時 | 2023-10-20 15:40:38 |
| 合計ジャッジ時間 | 4,968 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,348 KB |
| testcase_01 | AC | 2 ms
4,348 KB |
| testcase_02 | AC | 5 ms
4,348 KB |
| testcase_03 | AC | 1 ms
4,348 KB |
| testcase_04 | AC | 1 ms
4,348 KB |
| testcase_05 | AC | 2 ms
4,348 KB |
| testcase_06 | AC | 1 ms
4,348 KB |
| testcase_07 | AC | 2 ms
4,348 KB |
| testcase_08 | AC | 1 ms
4,348 KB |
| testcase_09 | AC | 1 ms
4,348 KB |
| testcase_10 | AC | 2 ms
4,348 KB |
| testcase_11 | AC | 2 ms
4,348 KB |
| testcase_12 | AC | 1 ms
4,348 KB |
| testcase_13 | AC | 1 ms
4,348 KB |
| testcase_14 | AC | 2 ms
4,348 KB |
| testcase_15 | AC | 5 ms
4,348 KB |
| testcase_16 | AC | 2 ms
4,348 KB |
| testcase_17 | AC | 2 ms
4,348 KB |
| testcase_18 | AC | 1 ms
4,348 KB |
ソースコード
import sugar
template exit* = quit 0
template write*( v :varargs[untyped] ) = stdout.write v
type Bool* = bool
type Int* = int
type Char* = char
type String* = string
type Interval = HSlice[Int,Int]
####################
### operator ###
####################
proc less*[T](x,y:T):Bool = x > y
proc more*[T](x,y:T):Bool = x < y
proc plus*[T](x,y:T):T = x + y
proc times*[T](x,y:T):T = x * y
proc less*[T](x:T):proc(y:T):Bool = return proc(y:T):Bool = x > y
proc more*[T](x:T):proc(y:T):Bool = return proc(y:T):Bool = x < y
proc plus*[T](y:T):proc(x:T):T = return proc(x:T):T = x + y
proc times*[T](y:T):proc(x:T):T = return proc(x:T):T = x * y
####################
### template ###
####################
template Make*(body :untyped) :auto =
let f = proc() :auto = body
f()
template Sum*(body:untyped) :auto =
iterator it() :auto = body
var ans = 0
for x in it(): ans += x
ans
template Max*(body:untyped) :Int =
iterator it() :Int = body
var ans = Int.low
for x in it(): ans.max= x
ans
template Min*(body:untyped) :Int =
iterator it() :Int = body
var ans = Int.high
for x in it(): ans.min= x
ans
template All*(body:untyped) :Bool =
iterator it() :Bool = body
var ans = true
for x in it():
if not x:
ans = false
break
ans
template Any*(body:untyped) :Bool =
iterator it() :Bool = body
var ans = false
for x in it():
if x:
ans = true
break
ans
####################
### iterator ###
####################
iterator items*(p :(Int,Int,Int)) :Int =
let (l,r,n) = p
var i = l
while i < r:
yield i
i += n
iterator items*( p :(Int,Int) ) :Int =
let (L,R) = p
for i in L..<R:
yield i
iterator items*( N :Int ) :Int =
for i in 0..<N:
yield i
iterator infty*() :Int =
var i=0
while true:
yield i
i.inc
iterator reverse*( L, R :Int ) :Int =
var i = R
while i > L:
i.dec
yield i
iterator reverse*( N :Int ) :Int =
for i in reverse(0, N):
yield i
################
### Vect ###
################
type Vect[T] = seq[T]
proc `$`[T]( v :Vect[T] ) :String =
for x in v: result &= $x & ' '
proc vect*[T]( n :Int ): Vect[T] =
newSeq[T]( result, n )
proc vect*[T]( N :Int; X :T ) :Vect[T] =
result = vect[T] N
for i in N:
result[i] = X
proc vect*[T]( S :openArray[T] ) :Vect[T] =
result = vect[T] S.len
for i, e in S:
result[i] = e
proc vect*[T](n :Int, f :proc(i:Int):T) :Vect[T] =
result = vect[T] n
for i in n: result[i] = f(i)
proc runLength[T](v :openarray[T]) :Vect[(T,Int)] =
result = vect[(T,Int)] []
var now :T = v[0]
var cnt = 1
for x in v[1..<v.len]:
if now == x:
cnt.inc
else:
result.push (now,cnt)
now = x
cnt = 1
result.push (now,cnt)
proc elem[T](v :openarray[T], a :T) :Bool =
for x in v:
if x == a: return true
return false
proc arg*[T](v :openarray[T], a :T) :Int =
for i, x in v:
if x == a: return i
return v.len
proc push*[T]( V :var Vect[T]; X :T ) =
V.setLen(V.len+1)
V[V.len-1] = X
proc countIf*[T]( S :openarray[T], f :proc(x:T):Bool ) :Int =
for e in S:
if f(e):
result.inc
proc map*[X,Y](v :openarray[X], f :proc(x:X):Y) :Vect[Y] =
result = vect[Y] v.len
for i in v.len: result[i] = f(v[i])
proc reverse*[T](v :openarray[T]) :Vect[T] =
result = vect[T] v.len
for i in v.len:
result[v.len-i-1] = v[i]
converter toVect(s :String) :Vect[Char] =
for c in s: result.push c
proc full*[T](s :openarray[T], x :T) :Vect[T] =
result = vect[T] s.len
for i in s.len: result[i] = x
proc `full=`*[T](s :var Vect[T], x :T) =
for i in s.len: s[i] = x
proc cumulative*[T](v :openarray[T]) :Vect[T] =
result = vect[T] v.len + 1
if v.len == 0: return
for i in v.len: result[i+1] = result[i] + v[i]
proc sum[T](v :openarray[T]) :T =
for x in v: result = result + x
proc dim[T](a :openarray[T]) :Int =
for i in a.len.reverse:
if a[i] != 0: return i
return -1
proc normalization[T](a :var Vect[T]) =
a.setLen a.dim+1
proc `+`*[T](a, b :openarray[T]) :Vect[T] =
result = vect[T] max(a.len,b.len)
for i in max(a.len,b.len):
if i < a.len: result[i] += a[i]
if i < b.len: result[i] += b[i]
result.normalization
proc `-`*[T](a, b :openarray[T]) :Vect[T] =
var c = vect[T] b.len
for i in b.len: c[i] = -b[i]
return a + c
proc `*`*[T](a, b :openarray[T]) :Vect[T] =
result = vect[T] a.len + b.len - 1
for i in a.len:
for j in b.len:
result[i+j] += a[i]*b[j]
result.normalization
proc `div`*[T](a, b :openarray[T]) :Vect[T] =
result = vect[T] a.dim+1 - b.dim
var t = vect[T] a
for i in reverse(b.dim, a.dim+1):
if t[i] mod b[b.dim] != 0: return
result[i-b.dim] = t[i] div b[b.dim]
for j in b.dim+1:
t[i+j-b.dim] -= b[j] * result[i-b.dim]
proc `mod`*(a, b :openarray[Int]) :Vect[Int] =
result = vect[Int] a
var t = vect[Int] a.dim+1 - b.dim
for i in reverse(b.dim, a.dim+1):
if result[i] mod b[b.dim] != 0: return
t[i-b.dim] = result[i] div b[b.dim]
for j in b.dim+1:
result[i+j-b.dim] -= b[j] * t[i-b.dim]
result.normalization
################
### tens ###
################
type Tens[T] = object
data :Vect[T]
shape :Vect[Int]
proc tens*[T]( S :varargs[Int] ) :Tens[T] =
var N :Int = 1
for s in S: N *= s
result.data = vect[T](N)
result.shape = @S
proc `[]`[T]( t :Tens[T], s :varargs[Int] ) :T =
var n = 0
var r = 1
for i in reverse(s.len):
n += s[i] * r
r *= t.shape[i]
return t.data[n]
proc `[]=`[T]( t :var Tens[T], s :varargs[Int], e :T ) =
var n = 0
var r = 1
for i in reverse(s.len):
n += s[i] * r
r *= t.shape[i]
t.data[n] = e
proc `full=`*[T]( S :var Tens[T]; X :T ) =
for i in S.data.len: S.data[i] = X
iterator items[T]( t :Tens[T] ) :T =
for x in t.data: yield x
#####################
### algorithm ###
#####################
type IndexDefect = object of Defect
proc upperBound*(i :Interval; p :proc(i:Int):Bool) :Int =
var (ok, ng) = (i.a-1, i.b+1)
while ng - ok > 1:
let mid = (ng + ok) div 2
if p(mid): ok = mid
else: ng = mid
if ok < i.a: raise new IndexDefect
return ok
proc upperBound*[T](v :Vect[T], x :T) :Int =
upperBound(0..<v.len) do (i:Int)->Bool: v[i] <= x
proc lowerBound*(i :Interval; p :proc(i:Int):Bool) :Int =
var (ng, ok) = (i.a-1, i.b+1)
while ok - ng > 1:
let mid = (ng + ok) div 2
if p(mid): ok = mid
else: ng = mid
if ok > i.b: raise new IndexDefect
return ok
proc lowerBound*[T](v :Vect[T]; x :T) :Int =
lowerBound(0..<v.len) do (i:Int)->Bool: v[i] >= x
iterator shakutori*(n,m :Int, p :(Int,Int) -> Bool) :(Int,Int) =
var s = n
while s < m:
let t = upperBound(s..m, (i:Int) => p(s,i))
if t - s == n:
s.inc
else:
yield (s,t)
s = t
proc doubling*[T](a :T, n :Int, f :proc(x,y:T):T) :T =
result = a
var (a,n) = (a,n-1)
while true:
if n mod 2 == 1:
result = f(result,a)
if n <= 1: break
a = f(a,a)
n.div= 2
####################
### Priority ###
####################
type Priority[T] = object
data :Vect[T]
compare :proc(x,y:T):bool
proc priority*[T]() :Priority[T] =
result.data = vect[T](1)
result.compare = proc(x,y:T):bool = x < y
proc priority*[T]( compare :proc(x,y:T):bool ) :Priority[T] =
result.data = vect[T](1)
result.compare = compare
proc exist[T]( p :Priority[T] ) :bool = p.data.len > 1
proc push[T]( p :var Priority[T], e :T ) =
var n = p.data.len
p.data.add(e)
while n div 2 != 0 and p.compare( p.data[n], p.data[n div 2] ):
swap( p.data[n], p.data[n div 2] )
n = n div 2
proc priority*[T](v :openarray[T]) :Priority[T] =
result = priority[T]()
for x in v: result.push x
proc front[T]( p :Priority[T] ) :T = p.data[1]
proc trash[T]( p :var Priority[T] ) =
let N = p.data.len - 1
p.data[1] = p.data[N]
p.data.setLen(N)
var n = 1
while true:
if n * 2 >= N: break
if n * 2 + 1 >= N:
if p.compare( p.data[n], p.data[n * 2] ): break
swap( p.data[n], p.data[n * 2] )
n = n * 2
continue
if not p.compare( p.data[n * 2], p.data[n] ) and
not p.compare( p.data[n * 2 + 1], p.data[n] ):
break
if p.compare( p.data[n * 2], p.data[n * 2 + 1] ):
swap( p.data[n], p.data[n * 2] )
n = n * 2
else:
swap( p.data[n], p.data[n * 2 + 1] )
n = n * 2 + 1
proc pop[T]( p :var Priority[T] ) :T =
result = p.front
p.trash
#################
### coord ###
#################
type Coord* = tuple[x:int,y:int]
proc `+`[A,B](a,b :(A,B)) :(A,B) = (a[0]+b[0], a[1]+b[1])
proc `-`[A,B](a,b :(A,B)) :(A,B) = (a[0]-b[0], a[1]-b[1])
proc `*`[A,B,C](a :(A,B); b :C) :(A,B) = (a[0]*b, a[1]*b)
proc `div`[A,B,C](a :(A,B); b :C) :(A,B) = (a[0] div b, a[1] div b)
proc `mod`[A,B,C](a :(A,B); b :C) :(A,B) = (a[0] mod b, a[1] mod b)
proc elem(i :Interval, n :Int) :Bool =
if i.a <= n and n <= i.b: true
else: false
##################
### number ###
##################
proc `mod`(a,b :Int) :Int =
result = system.`mod`(a,b)
if result < 0: result += b
proc `mod=`*[A,B](a :var A, b :B) = a = a mod b
proc `div=`*[A,B](a :var A, b :B) = a = a div b
proc `^`*[T](a :T, b :Int) :T =
if b==0: 1
else: doubling[T](a,b,proc(x,y:T):T = x*y)
proc fact[I]( n :I ) :I =
var memo {.global.} = vect[I] [I(1)]
if n.Int >= memo.len:
for i in (memo.len,n.Int+1):
memo.push memo[i-1] * i
return memo[n.Int]
iterator divisor*(N :Int) :Int =
var i = 1
var s = vect[Int] []
while i*i < N:
if N mod i == 0:
yield i
s.push N div i
i.inc
if i*i == N: yield i
for j in reverse(s.len):
yield s[j]
proc divisor*( N :Int ) :Vect[Int] =
result = @[]
for d in N.divisor:
result.add d
proc perm*[N,K]( n :N, k :K ) :N =
fact(n) div fact(n-k)
proc comb*[I](n,k :I) :I =
let k = min(k,n-k)
result = 1
for i in k.Int:
result *= (n-i)
result = result div (i+1)
proc eratos*( N :Int ) :Vect[Bool] =
result = vect[Bool] N+1
for i in (2,N+1): result[i] = true
var i = 2
while i * i <= N:
if result[i]:
var j = i * 2
while j <= N:
result[j] = false
j += i
i += 1
proc `ceilDiv`*( n: Int, m: Int ) :Int =
return (n + m - 1) div m
proc gcd*(a, b :Int) :Int =
if b == 0:
return a
return gcd(b, a mod b)
proc `gcd=`*(a :var Int, b :Int) =
a = gcd(a,b)
proc gcd*(v :openarray[Int]) :Int =
result = 0
for n in v:
result.gcd= n
proc lcm*(a, b :Int) :Int =
return a div gcd(a, b) * b
proc `lcm=`*(a :var Int, b :Int) =
a = lcm(a,b)
proc lcm*(v :openarray[Int]) :Int =
result = 1
for n in v:
result.lcm= n
proc floorSum(n, m, a, b :Int) :Int =
var (a,b) = (a,b)
if a >= m:
result += n * (n-1) div 2 * (a div m)
a.mod= m
if b >= m:
result += n * (b div m)
b.mod= m
let t = a * n + b
if t >= m:
result += floorSum(t div m, a, m, t mod m)
##################
### search ###
##################
iterator repetition*[T](v :openarray[T],k :Int) :Vect[T] =
var c = vect[Int](k)
for _ in v.len^k:
var r = vect[T] k
for i in k: r[i] = v[c[i]]
yield r
for j in reverse(k):
c[j].inc
if c[j] == v.len: c[j] = 0
else: break
iterator subSequence*[T](v :openarray[T]) :Vect[T] =
for t in repetition([false,true],v.len):
var r = vect[T] 0
for i,b in t:
if b: r.push v[i]
yield r
iterator permutation*[T](v :openarray[T]) :Vect[T] =
let n = v.len
var c = vect[Int](n) do (i:Int) -> Int: n-i
var t = vect[T] v
yield t
block outside:
for _ in infty():
block inside:
for i in reverse(n):
c[i].dec
if c[i] != 0:
swap(t[i], t[n-c[i]])
yield t
break inside
var k = t[i]
for j in (i,n-1):
t[j]=t[j+1]
t[n-1] = k
c[i] = n-i
break outside
iterator combination*[T](v :openarray[T],k :Int) :Vect[T] =
var c = vect[Int] k
var t, s = 0
for _ in infty():
for i in (t,v.len):
c[s] = i
s.inc
if s == k:
var r = vect[T] k
for i in k: r[i] = v[c[i]]
yield r
break
if s==0: break
s.dec
t = c[s] + 1
##################
### modint ###
##################
type ModInt = object
data :Int
var MOD :Int = int.high
converter toModInt*(n :Int) :ModInt =
result.data = n mod MOD
converter toInt*(n :ModInt) :Int =
n.data
proc inverse*(n: ModInt) :ModInt =
var (a,b,c,d) = (n.data, MOD, 1, 0)
while b > 0:
let t = a div b
a -= t * b; (a,b) = (b,a)
c -= t * d; (c,d) = (d,c)
return c
proc `$`*(a :ModInt) :String = $a.data
proc `+`*(a, b :ModInt) :ModInt = (a.data + b.data) mod MOD
proc `-`*(a, b :ModInt) :ModInt = (a.data - b.data) mod MOD
proc `*`*(a, b :ModInt) :ModInt = (a.data * b.data) mod MOD
proc `/`*(a, b :ModInt) :ModInt = a * b.inverse
proc `==`*(a, b :ModInt) :Bool = a.data == b.data
proc `+=`*(a :var ModInt, b :ModInt) = a = a + b
proc `-=`*(a :var ModInt, b :ModInt) = a = a - b
proc `*=`*(a :var ModInt, b :ModInt) = a = a * b
proc `/=`*(a :var ModInt, b :ModInt) = a = a / b
proc `div`*(a, b :ModInt) :ModInt = a * b.inverse
#################
### deque ###
#################
type Deque[T] = object
data :Vect[T]
head, tail, count, mask :Int
proc deque[T](v :openarray[T]): Deque[T] =
result = Deque[T](
data: newSeq[T](4),
head: 0, tail: 0, count: 0, mask: 3 )
for x in v: result.pushRight x
proc len[T](d :Deque[T]) :Int = d.count
proc `[]`[T](d :Deque[T], i :Int) :T =
d.data[(d.head + i) and d.mask]
proc peekLeft[T](d :Deque[T]) :T =
d.data[d.head]
proc peekRight[T](d :Deque[T]) :T =
d.data[(d.tail-1) and d.mask]
proc expand[T](d :var Deque[T]) =
if d.data.len == d.count:
let l = d.data.len
d.data.setLen(l * 2)
d.mask = d.mask * 2 + 1
if d.head >= d.tail:
for i in (d.head, l): d.data[i+l] = d.data[i]
d.head += l
proc pushLeft[T](d :var Deque[T], x :T) =
expand(d)
d.count.inc
d.head = (d.head-1) and d.mask
d.data[d.head] = x
proc pushRight[T](d :var Deque[T], v :T) =
expand(d)
d.count.inc
d.data[d.tail] = v
d.tail = (d.tail+1) and d.mask
proc popLeft[T](d :var Deque[T]) :T =
d.count.dec
result = d.data[d.head]
d.head = (d.head+1) and d.mask
proc popRight[T](d :var Deque[T]) :T =
d.count.dec
d.tail = (d.tail-1) and d.mask
result = d.data[d.tail]
#################
### Stack ###
#################
type Stack[T] = object
data :Deque[T]
proc stack[T](v :openarray[T]) :Stack[T] =
result.data = deque v
proc len*[T](s :Stack[T]) :Int = s.data.len
proc push*[T](s :var Stack[T], e :T) = s.data.pushRight(e)
proc front*[T](s :Stack[T]) :T = s.data.peekRight
proc pop*[T](s :var Stack[T]) :T = s.data.popRight
#################
### Queue ###
#################
type Queue[T] = object
data :Deque[T]
proc queue[T](v :openarray[T]) :Queue[T] =
result.data = deque v
proc len*[T](q :Queue[T]) :Int = q.data.len
proc push*[T](q :var Queue[T], e :T) = q.data.pushRight(e)
proc front*[T](q :Queue[T]) :T = q.data.peekLeft
proc pop*[T](q :var Queue[T]) :T = q.data.popLeft
###############
### set ###
###############
type AVL[T] = ref object
mid :T
l,r :AVL[T]
dep :Int
proc depth[T](t :AVL[T]) :Int =
if t == nil: 0 else: t.dep
proc len[T](t :AVL[T]) :Int =
if t == nil: 0
else: 1 + t.l.len + t.r.len
proc `shr`[T](t :var AVL[T]) =
var s = AVL[T]()
s.mid = t.mid; s.l = t.l.r; s.r = t.r;
s.dep = max(s.l.depth,s.r.depth)+1
t.mid = t.l.mid; t.r = s; t.l = t.l.l
t.dep = max(t.l.depth,s.dep)+1
proc `shl`[T](t :var AVL[T]) =
var s = AVL[T]()
s.mid = t.mid; s.l = t.l; s.r = t.r.l
s.dep = max(s.l.depth,s.r.depth)+1
t.mid = t.r.mid; t.r = t.r.r; t.l = s
t.dep = max(t.r.depth,s.dep)+1
type Set*[T] = object
avl :AVL[T]
`<` :(T,T) -> Bool
proc set*[T](v :openarray[T], `<`:proc(x,y:T):Bool =more) :Set[T] =
result.`<` = `<`
for x in v: result.push x
proc push*[T](s :var Set[T], x :T) =
let `<` = s.`<`
proc f(t :var AVL[T]) =
if t == nil:
t = AVL[T](); t.mid = x; t.dep = 1
elif x < t.mid:
t.l.f
if t.l.dep > t.r.depth: t.shr
elif t.mid < x:
t.r.f
if t.r.dep > t.l.depth: t.shl
s.avl.f
proc `$`*[T](s :Set[T]) :String =
proc f(t :AVL[T]) :String =
if t == nil: ""
else: "[" & f(t.l) & " " & $t.mid & " " & f(t.r) & "]"
f(s.avl)
proc elem*[T](s :Set[T], x :T) :Bool =
proc f(t :AVL[T]) :Bool =
if t == nil: false
elif s.`<`(x, t.mid): t.l.f
elif s.`<`(t.mid, x): t.r.f
else: true
s.avl.f
iterator items*[T](s :Set[T]) :T =
var a = stack [(s.avl,false)]
var b = stack[T] []
while a.len != 0:
let (n,f) = a.pop
if f: yield b.pop
if n==nil: continue
a.push (n.r,true)
a.push (n.l,false)
b.push n.mid
proc upperBound*[T](s :Set[T], x :T) :T =
let `<` = s.`<`
proc f(t :AVL[T]) :T =
if t == nil: raise new IndexDefect
if x < t.mid: return f(t.l)
if t.mid < x:
try: return f(t.r)
except IndexDefect: return t.mid
return t.mid
s.avl.f
proc lowerBound*[T](s :Set[T], x :T) :T =
let `<` = s.`<`
proc f(t :AVL[T]) :T =
if t == nil: raise new IndexDefect
if t.mid < x: return f(t.r)
if x < t.mid:
try: return f(t.l)
except IndexDefect: return t.mid
return t.mid
s.avl.f
proc max*[T](s :Set[T]) :T =
proc f(t :AVL[T]) :T =
if t.r == nil: t.mid
else: t.r.f
s.avl.f
proc min*[T](s :Set[T]) :T =
proc f(t :AVL[T]) :T =
if t.l == nil: t.mid
else: t.l.f
s.avl.f
################
### sort ###
################
proc `sort=`*[T](S :var Vect[T], compare :proc(x,y:T):Bool) =
var stack = stack[ (Bool,Int,Int) ] [(true, 0, S.len)]
while stack.len != 0:
var (B, L, R) = stack.pop
if R - L < 2: continue
if B:
stack.push( (false, L, R) )
stack.push( (true, L, (L+R) div 2) )
stack.push( (true, (L+R) div 2, R) )
continue
var temp = vect[T]( (L+R) div 2 - L )
for i in temp.len: temp[i] = S[L+i]
var (t, r) = (0, (L+R) div 2)
for i in (L,R):
if r == R or t != temp.len and compare(temp[t], S[r] ):
S[i] = temp[t]
t.inc
else:
S[i] = S[r]
r.inc
proc `sort=`*[T](v :var Vect[T]) =
v.sort= proc(x,y:T):Bool = x < y
proc sort*[T](v :openarray[T], comp :proc(x,y:T):Bool) :Vect[T] =
result = vect[T] v
result.sort= comp
proc sort*[T](v :openarray[T]) :Vect[T] =
v.sort proc(x,y:T):Bool = x < y
proc sorted*[T](v :openarray[T], comp :proc(x,y:T):Bool) :Bool =
for i in v.len - 1:
if not comp(v[i],v[i+1]) and comp(v[i+1],v[i]):
return false
return true
proc sorted*[T](v :openarray[T]) :Bool =
v.sorted proc(x,y:T):Bool = x < y
proc `max=`*[T]( x :var T; y :T ) =
if x < y: x = y
proc `min=`*[T]( x :var T; y :T ) =
if x > y: x = y
proc max[T](v :varargs[T]) :T =
result = T.low
for x in v: result.max = x
proc min[T](v :varargs[T]) :T =
result = T.high
for x in v: result.min = x
proc argMax*[T]( V :openArray[T] ) :Int =
var max = T.low
for i, e in V:
if e > max:
result = i
max = e
################
### read ###
################
proc getchar*() :Char
{.header:"stdio.h",importc:"getchar_unlocked".}
proc read*( T :typedesc ) :T =
when T is Char:
result = getchar()
discard getchar()
when T is String:
result = ""
while true:
var c = getchar()
if [' ', '\10', '\255'].elem c: break
result.add c
when T is Int:
var
sign = 1
c = getchar()
if c == '-':
sign = -1
c = getchar()
while '0' <= c and c <= '9':
result *= 10
result += c.Int() - '0'.Int()
c = getchar()
result *= sign
when T is tuple:
for r in result.fields:
r = r.type.read
proc read*( T :typedesc, N :Int ) :Vect[T] =
result = vect[T] N
for i in N:
result[i] = T.read
proc read(T :typedesc, H,W :Int) :Tens[T] =
result = Tens[T](H,W)
for i in H:
for j in W:
result[i,j] = T.read
proc parseDigit(s:String) :Int =
result = 0
for c in s:
result *= 10
result += c.Int - '0'.Int
####################
### disjoint ###
####################
type Disjoint* = object
data :Vect[Int]
proc disjoint*( n :Int ) :Disjoint =
result.data = vect[Int] n
for i in n: result.data[i] = -1
proc find*( d :var Disjoint, n :Int ) :Int =
if d.data[n] < 0: return n
d.data[n] = d.find( d.data[n] )
return d.data[n]
proc union*( d :var Disjoint, n, m :Int ) =
var n = d.find(n)
var m = d.find(m)
if n == m: return
if d.data[m] < d.data[n]: swap( n, m )
d.data[m] += d.data[n]
d.data[n] = m
proc same*( d :var Disjoint, n, m :Int ) :Bool =
d.find(n) == d.find(m)
proc size*( d :var Disjoint, n :Int ) :Int =
- d.data[d.find(n)]
###################
### segment ###
###################
type Segment*[T] = object
size :Int
data :Vect[T]
id :T
op :proc(x,y:T):T
proc segment*[T](V:Vect[T], e:T, F:proc(x,y:T):T) :Segment[T] =
result.id = e
result.op = F
result.size = 1
while result.size < V.len: result.size *= 2
result.data = vect[T](result.size * 2)
for i in V.len: result.data[result.size + i] = V[i]
for i in (V.len,result.size): result.data[result.size+i] = e
for i in reverse(1,result.size):
result.data[i] = F( result.data[2*i], result.data[2*i+1] )
proc `[]`[T](s :Segment[T], n :Int) :T = s.data[s.size+n]
proc `[]=`*[T]( S :var Segment[T], K :Int, X :T ) =
var k = K + S.size
S.data[k] = X
while(k > 1):
k = k div 2
S.data[k] = S.op( S.data[k*2], S.data[2*k+1] )
proc `[]`*[T](s :Segment[T]; p :Slice[Int]) :T =
var x,y = s.id
var (l,r) = (p.a + s.size, p.b + s.size + 1)
while l < r:
if l mod 2 == 1:
x = s.op(x, s.data[l])
l.inc
if r mod 2 == 1:
r.dec
y = s.op(s.data[r], y)
l = l div 2
r = r div 2
return s.op(x,y)
#################
### graph ###
#################
type
Node* = tuple[next:Int,weight:Int]
Graph* = Vect[Vect[Node]]
proc readGraph*(n,m:Int,weight=false) :Graph =
result = vect[Vect[(int,int)]] n
for i in m:
let a, b = Int.read - 1
var w = 1
if weight: w = Int.read
result[a].push (b,w)
result[b].push (a,w)
iterator edge*(g:Graph) :tuple[a,b,weight:Int] =
for i in g.len:
for j in g[i].len:
yield (i,g[i][j].next,g[i][j].weight)
proc `$`*(g :Graph) :String =
for i, a in g:
for (b,c) in a:
result &= "(" & $i & "->" & $b & " :" & $c & ") "
result &= '\n'
proc dijkstra*(g :Graph, s :Int) :Vect[Int] =
result = vect[Int](g.len, Int.high)
var p = priority[(Int,Int)] proc(x,y:Node):bool =
x.weight < y.weight
p.push (s,0)
while p.exist:
let (i, c) = p.pop
if result[i] < c: continue
result[i] = c
for (j, d) in g[i]:
if c+d < result[j]:
p.push (j,c+d)
##########################
#### ####
#### main ####
#### ####
##########################
proc isPrime(n :Int) :Bool =
var cnt = 0
for i in divisor n:
cnt += 1
return cnt == 2
let S = Make:
result = vect[Int] []
var s = String.read
for c in s: result.push c.Int - '0'.Int
var ans = 0
for v in [false,true].repetition S.len - 1:
var a = vect[Int] [S[0]]
for i in S.len - 1:
if v[i]: a.push S[i+1]
else: a[a.len-1] = a[a.len-1] * 10 + S[i+1]
if a.sum.isPrime: ans += 1
echo ans