Problem:


Problem B: Spellcasters

n 人の魔法使いがいる。彼らには 1 から n までの番号があり、i 番目の魔法使いは魔力 ri ( 1 ≤ i ≤ n ) を持っている。いま彼らは強力な魔法使いと対峙しており、その敵の魔力は S である。n 人の魔法使いは協力して戦うのが得意で、特に 2 人で協力して戦うことを好む。2 人の魔法使いが協力した場合、魔力は単純にその和となり、強力な魔法などを駆使してある程度強い敵にも勝てるようになる。あなたの仕事は魔力 S を持つ敵に対して勝つことができる魔法使いのペア (i, j) ( i &ne; j かつ 1 ≤ i ≤ n かつ 1 ≤ j ≤ n ) の総数を出力することである。ただし (i, j) と (j, i) は同じ組として数える。一方の魔力が他方の魔力よりも大きいとき、大きい魔力を持っている側が勝つ。等しい場合は相打ちで勝ったことにならない。

Input

入力は複数のテストケースからなる。 各テストケースは以下の形式に従う。

n S
r1
r2
…
rn

各変数の意味は問題文中の通りである。
入力の終わりは、ふたつの0が一文字の空白で区切られる一行で示される。

Constraints

入力はすべて整数

1 ≤ n ≤ 20,000

1 ≤ ri ≤ 100 ( 1 ≤ i ≤ n )

1 ≤ S ≤ 100

テストケースの数は 100 を超えない。

Output

条件を満たす組 (i, j) (i &ne; j) の総数を各ケースに付き 1 行に出力せよ。

Sample Input

3 7
1
3
10
0 0

Sample Output

2



Sample input:
3 7
1
3
10
0 0


Sample output:
2

Submission status: Wrong Answer

Solution code:
while True:
    n,S = map(int, raw_input().split())
    if n == 0 and S == 0:
        break
    r = [input() for i in range(n)]
    ans = 0
    r.sort()
    for i in range(n):
        tmp = S - r[i] + 1
        if (tmp <= 0):
            ans += n - 1
        else:
            left,right = 0,n
            while (right - left > 1):
                med = (right + left) / 2
                if (r[med] <=  tmp):
                    left = med
                else:
                    right = med
            ans += (len(r) - left) - 1
    print ans / 2

Submission status: Time Limit Exceeded

Solution code:
while True:
    n,S = map(int, raw_input().split())
    if n == 0 and S == 0:
        break
    r = []
    for i in range(n):
        r.append(input())
    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
           if r[i] + r[j] > S:
               ans += 1
    print ans

Submission status: Time Limit Exceeded

Solution code:
import bisect
while True:
    n,S = map(int, raw_input().split())
    if n == 0 and S == 0:
        break
    r = []
    for i in range(n):
        r.append(input())
    ans = 0
    r.sort()
    for i in range(n):
        tmp = S - r[i] + 1
        d = r[0:i] + r[i:]
        index = bisect.bisect_right(d, tmp)
        ans += index
    print ans / 2

Submission status: Time Limit Exceeded

Solution code:
import bisect
while True:
    n,S = map(int, raw_input().split())
    if n == 0 and S == 0:
        break
    r = []
    for i in range(n):
        r.append(input())
    ans = 0
    r.sort()
    for i in range(n):
        tmp = S - r[i] + 1
        if (tmp <= 0):
            ans += n - 1
        else:
            d = r[0:i] + r[i + 1:]
            index = bisect.bisect_right(d, tmp)
            ans += index
    print ans / 2

Submission status: Time Limit Exceeded

Solution code:
import bisect
while True:
    n,S = map(int, raw_input().split())
    if n == 0 and S == 0:
        break
    r = [input() for i in range(n)]
    ans = 0
    r.sort()
    for i in range(n):
        tmp = S - r[i] + 1
        if (tmp <= 0):
            ans += n - 1
        else:
            d = r[0:i] + r[i + 1:]
            index = bisect.bisect_right(d, tmp)
            ans += index
    print ans / 2

Submission status: Time Limit Exceeded

Solution code:
while True:
    n,S = map(int, raw_input().split())
    if n == 0 and S == 0:
        break
    r = [input() for i in range(n)]
    ans = 0
    r.sort()
    for i in range(n):
        tmp = S - r[i] + 1
        if (tmp <= 0):
            ans += n - 1
        else:
            d = r[0:i] + r[i + 1:]
            left,right = 0,n - 1
            while (right - left > 1):
                med = (right + left) / 2
                if (d[med] <=  tmp):
                    left = med
                else:
                    right = med
            ans += (len(d) - left) - 1
    print ans / 2

Submission status: Time Limit Exceeded

Solution code:
while 1:
    n,s=map(int,input().split())
    if not n:break
    a=sorted([int(input()) for _ in range(n)],reverse=1)
    b=0
    try:
        for i in range(n):
            for j in range(i+1,n):
                if a[i]+a[j]>s:b+=1
                else:raise Exception;pass
    except:pass
    print(b)

Submission status: Time Limit Exceeded

Solution code:
while 1:
    n,s=map(int,input().split())
    if not n:break
    a=sorted([int(input()) for _ in range(n)],reverse=1)
    b=0
    for i in range(n):
        try:
            for j in range(i+1,n):
                if a[i]+a[j]>s:b+=1
                else:raise Exception;break
        except:break
    print(b)

Submission status: Time Limit Exceeded

Solution code:
while 1:
    n,s=map(int,input().split())
    if not n:break
    a=sorted([int(input()) for _ in range(n)],reverse=1)
    b=0
    for i in range(n):
        for j in range(i+1,n):
            if a[i]+a[j]>s:b+=1
            else:break
        if a[i]+a[j]<=s:break
    print(b)

Submission status: Time Limit Exceeded

Solution code:
while 1:
	n,S = map(int,raw_input().split())
	if n == 0: break
	r = sorted([int(raw_input()) for i in range(n)], reverse = True)
	c = 0
	for i in range(n):
		if r[i] < S/2:
			break
		for j in range(i+1,n):
			if r[i]+r[j] > S:
				c += 1
			else:
				break
	print c

Submission status: Time Limit Exceeded

Solution code:
while 1:
	n,S = map(int,raw_input().split())
	if n == 0: break
	r = sorted([int(raw_input()) for i in range(n)], reverse = True)
	c = 0
	for i in range(n):
		if r[i] >= S:
			c += n-i-1
			continue
		elif r[i] < S/2:
			break
		for j in range(i+1,n):
			if r[i]+r[j] > S:
				c += 1
			else:
				break
	print c

Submission status: Memory Limit Exceeded

Solution code:
while 1:
    n,s=map(int,input().split())
    if not n:break
    a=[int(input()) for _ in range(n)]
    b=0
    for i in range(n):
        for j in range(i+1,n):
            if a[i]+a[j]>s:b+=1
    print(sum([a[i]+a[j]>s for i in range(n) for j in range(i+1,n)]))

Submission status: Memory Limit Exceeded

Solution code:
while 1:
    n,s=map(int,input().split())
    if not n:break
    a=[int(input()) for _ in range(n)]
    print(sum([a[i]+a[j]>s for i in range(n) for j in range(i+1,n)]))

Submission status: Accepted

Solution code:
import bisect
while True:
    n,S = map(int, raw_input().split())
    if n == 0 and S == 0:
        break
    r = [input() for i in range(n)]
    ans = 0
    r.sort()
    for i in range(n):
        tmp = S - r[i] + 1
        if (tmp <= 0):
            ans += n - 1
        else:
            index = bisect.bisect_left(r, tmp)
            if (index <= i):
                ans += n - index - 1
            else:
                ans += n - index
    print ans / 2

Submission status: Accepted

Solution code:
import bisect

while(1):
    n,S=map(int,raw_input().split())
    if n==0:    break
    A=[]
    for i in range(n):
        A.append(int(raw_input()))
    A.sort()
    ans=0
    for i in range(1,n):
        ans+= max(0,i- bisect.bisect(A[:i],S-A[i]) )
    print ans

Submission status: Accepted

Solution code:
while 1:
    n,s=map(int,input().split())
    if n==0:break
    r=[0]*101
    for _ in [0]*n:r[int(input())]+=1
    a=0
    for i in range(101):
        if i*2>s:a+=(r[i]**2-r[i])//2
        a+=r[i]*sum(r[j] for j in range(max(i+1,s+1-i),101))
    print(a)

Submission status: Accepted

Solution code:
R = 101
while 1:
	n,S = map(int,raw_input().split())
	if n == 0: break
	r = [0]*R
	for i in range(n):
		r[int(raw_input())] += 1
	ans = 0
	for i in range(R):
		if 2*i > S:
			ans += r[i]*(r[i]-1)/2
		ans += r[i]*sum([r[j] for j in range(i+1,R) if i+j > S])
	print ans

Submission status: Accepted

Solution code:
R = 101
while 1:
	n,S = map(int,raw_input().split())
	if n == 0: break
	r = [0]*R
	for i in range(n):
		r[int(raw_input())] += 1
	ans = 0
	for i in range(R):
		if 2*i > S:
			ans += r[i]*(r[i]-1)/2
		ans += r[i]*sum([r[j] for j in range(max(i+1,S-i+1),R)])
	print ans

Submission status: Accepted

Solution code:
R = 101
while 1:
	n,S = map(int,raw_input().split())
	if n == 0: break
	d = [int(raw_input()) for i in range(n)]
	r = [d.count(i) for i in range(R)]
	ans = 0
	for i in range(R):
		if 2*i > S:
			ans += r[i]*(r[i]-1)/2
		ans += r[i]*sum([r[j] for j in range(max(i+1,S-i+1),R)])
	print ans

Submission status: Accepted

Solution code:
R = 101
while 1:
	n,S = map(int,raw_input().split())
	if n == 0: break
	d = [int(raw_input()) for i in range(n)]
	r = [0]*R
	for i in set(d): r[i] = d.count(i)
	ans = 0
	for i in range(R):
		if 2*i > S:
			ans += r[i]*(r[i]-1)/2
		ans += r[i]*sum([r[j] for j in range(max(i+1,S-i+1),R)])
	print ans

Submission status: Accepted

Solution code:
from itertools import accumulate
while True:
  n, s = map(int, input().split())
  if n == 0:break
  lst = [0] * 102
  for _ in range(n):
    lst[int(input())] += 1
  acc_lst = list(reversed(list(accumulate(reversed(lst)))))
  ans = 0
  for i in range(1, 101):
    if s + 1 - i > i:
      ans += lst[i] * acc_lst[s + 1 - i]
    else:
      ans += lst[i] * (lst[i] - 1) // 2
      ans += lst[i] * acc_lst[i + 1]
  print(ans)

Submission status: Runtime Error

Solution code:
import bisect
while True:
    n,S = map(int, raw_input().split())
    if n == 0 and S == 0:
        break
    r = [input() for i in range(n)]
    ans = 0
    r.sort()
    for i in range(n):
        tmp = S - r[i] + 1
        if (tmp <= 0):
            ans += n - 1
        else:
            d = r[0:i] + r[i + 1:]
            left,right = 0,n
            while (right - left > 1):
                med = (right + left) / 2
                if (d[med] <=  tmp):
                    left = med
                else:
                    right = med
            ans += (len(d) - left) - 1
    print ans / 2

Submission status: Runtime Error

Solution code:
while True:
    n,S = map(int, raw_input().split())
    if n == 0 and S == 0:
        break
    r = [input() for i in range(n)]
    ans = 0
    r.sort()
    for i in range(n):
        tmp = S - r[i] + 1
        if (tmp <= 0):
            ans += n - 1
        else:
            d = r[0:i] + r[i + 1:]
            left,right = 0,n
            while (right - left > 1):
                med = (right + left) / 2
                if (d[med] <=  tmp):
                    left = med
                else:
                    right = med
            ans += (len(d) - left) - 1
    print ans / 2

Submission status: Runtime Error

Solution code:
R = 101
while 1:
	n,S = map(int,raw_input().split())
	if n == 0: break
	r = [0]*R
	for i in range(n):
		r[int(raw_input())] += 1
	ans = 0
	for i in range(R):
		if 2*i > S:
			ans += r[i]*(r[i]-1)/2
		ans += r[i]*sum([r[j] for j in range(max(i+1,S-j+1),R)])
	print ans

Submission status: Runtime Error

Solution code:
R = 101
while 1:
	n,S = map(int,raw_input().split())
	if n == 0: break
	d = [int(raw_input()) for i in range(n)]
	r = [d.count(i) for i in set(d)]
	ans = 0
	for i in range(R):
		if 2*i > S:
			ans += r[i]*(r[i]-1)/2
		ans += r[i]*sum([r[j] for j in range(max(i+1,S-i+1),R)])
	print ans