Problem:


Score : 100 points

Problem Statement

Ringo Kingdom Congress is voting on a bill.

N members are present, and the i-th member (1 ≤ i ≤ N) has w_i white ballots and b_i blue ballots. Each member i will put all the w_i white ballots into the box if he/she is in favor of the bill, and put all the b_i blue ballots into the box if he/she is not in favor of the bill. No other action is allowed. For example, a member must not forfeit voting, or put only a part of his/her white ballots or a part of his/her blue ballots into the box.

After all the members vote, if at least P percent of the ballots in the box is white, the bill is passed; if less than P percent of the ballots is white, the bill is rejected.

In order for the bill to pass, at least how many members must be in favor of it?

Constraints

1 ≤ N ≤ 10^5

1 ≤ P ≤ 100

1 ≤ w_i ≤ 10^9

1 ≤ b_i ≤ 10^9

All input values are integers.

Input

Input is given from Standard Input in the following format:

N P
w_1 b_1
w_2 b_2
:
w_N b_N

Output

Print the minimum number of members in favor of the bill required for passage.

Sample Input 1

4 75
1 1
1 1
1 1
1 1

Sample Output 1

3

This is a "normal" vote, where each of the four members has one white ballot and one blue ballot. For the bill to pass, at least 75 percent of the four, that is, at least three must be in favor of it.

Sample Input 2

4 75
1 1
1 1
1 1
100 1

Sample Output 2

1

The "yes" vote of the member with 100 white ballots alone is enough to pass the bill.

Sample Input 3

5 60
6 3
5 9
3 4
7 8
4 7

Sample Output 3

3



Sample input:
4 75
1 1
1 1
1 1
1 1


Sample output:
3

Submission status: Wrong Answer

Solution code:
from itertools import accumulate


def solve(l, r):
    if l > r:
        return l
    m = (l + r) // 2
    w, b = whites[m], blues[m]
    if w * 100 // (w + b) < p:
        l = m + 1
    else:
        r = m - 1
    return solve(l, r)


n, p = map(int, input().split())
wbs = [tuple(map(int, input().split())) for _ in range(n)]
ass = [(sum(t), t[0], i) for i, t in enumerate(wbs)]
ass.sort(reverse=True)
whites = list(accumulate(wbs[i][0] for s, t, i in ass))
blues = [wbs[i][1] for s, t, i in ass[1:]]
blues = list(reversed(list(accumulate(reversed(blues))))) + [0]

# print(list(whites))
# print(list(blues))
print(solve(0, n - 1) + 1)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate


def solve(l, r):
    if l > r:
        return l
    m = (l + r) // 2
    w, b = whites[m], blues[m]
    if w * 100 // (w + b) < p:
        l = m + 1
    else:
        r = m - 1
    return solve(l, r)


n, p = map(int, input().split())
wbs = [tuple(map(int, input().split())) for _ in range(n)]
ass = [(sum(t), i) for i, t in enumerate(wbs)]
ass.sort(reverse=True)
whites = list(accumulate(wbs[i][0] for s, i in ass))
blues = [wbs[i][1] for s, i in ass[1:]]
blues = list(reversed(list(accumulate(reversed(blues))))) + [0]

# print(list(whites))
# print(list(blues))
print(solve(0, n - 1) + 1)

Submission status: Accepted

Solution code:
n,p=map(int,input().split())
l=[]

for i in range(n):
    l.append(list(map(int,input().split())))
l.sort(key=lambda x:-(x[0]*(100-p)+x[1]*p))
z=0
for i in range(n):
    z+=-l[i][1]*p
i=0
while z<0:
    z+=l[i][0]*(100-p)+l[i][1]*p
    i+=1
print(i)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N,P = map(int,input().split())
W,B = np.array([input().split() for _ in range(N)], dtype=np.int64).T

#(100-P)W - PB の和が0以上
#全員青の状態から始めて、改善量が高い人から順にとる

X = B.sum()*P # 改善しないといけない値

improve = (100-P)*W + P*B
improve.sort()
improve = improve[::-1]
np.cumsum(improve, out=improve)

answer = (improve < X).sum() + 1
print(answer)

Submission status: Accepted

Solution code:
n, p = map(int, input().split())

e = [tuple(map(int, input().split())) for _ in range(n)]
# e = [(w,b), ...]

e2 = sorted(((100 - p) * w + p * b for w, b in e), reverse=True)

rest = p * sum(b for _, b in e)

cur = 0
while rest > 0 and cur < n:
    rest -= e2[cur]
    cur += 1
print(cur)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
xs = []
value = 0
for _ in range(N):
    w, b = map(int, input().split())
    xs.append((100-P)*w+P*b)
    value -= P*b

xs.sort(reverse=True)

for i, x in enumerate(xs, 1):
    value += x
    if value >= 0:
        print(i)
        break

Submission status: Accepted

Solution code:
n, p = map(int, input().split())
w, b = [], []
for _ in range(n):
    ww, bb = map(int, input().split())
    w.append(ww)
    b.append(bb)

s = []
for ww, bb in zip(w, b):
    s.append((100 - p) * ww + p * bb)
s.sort(reverse=True)

score = -sum(b) * p

cnt = 0
while score < 0:
    score += s[cnt]
    cnt += 1
print(cnt)

# (100-p)*w-p*b>=0

Submission status: Accepted

Solution code:
N,P=[int(i) for i in input().split()]
wb=[[int(j) for j in input().split()] for i in range(N)]
xs = [(100-P)*w+P*b for w,b in wb]
xs.sort()
xs.reverse()

score=0
for i in range(N):
    score-=P*wb[i][1]
for i in range(N):
    score+=xs[i]
    if score>=0:
        print(i+1)
        break

Submission status: Accepted

Solution code:
from itertools import accumulate


def solve(l, r):
    if l > r:
        return l
    m = (l + r) // 2
    w, b = whites[m], blues[m]
    if w * 100 // (w + b) < p:
        l = m + 1
    else:
        r = m - 1
    return solve(l, r)


n, p = map(int, input().split())
wbs = [tuple(map(int, input().split())) for _ in range(n)]
ass = [(w * (100 - p) + b * p, i) for i, (w, b) in enumerate(wbs)]
ass.sort(reverse=True)
whites = list(accumulate(wbs[i][0] for _, i in ass))
blues = [wbs[i][1] for _, i in ass[1:]]
blues = list(reversed(list(accumulate(reversed(blues))))) + [0]

# print(list(whites))
# print(list(blues))
print(solve(0, n - 1) + 1)

Submission status: Accepted

Solution code:
N, P = map(int, input().split())
B = 0
Q = []
for i in range(N):
    w, b = map(int, input().split())
    B += b
    Q.append((100 - P)*w + P*b)
Q.sort()
s = 0
for i in range(N):
    s += Q[-i-1]
    if B*P <= s:
        print(i+1)
        break

Submission status: Accepted

Solution code:
import sys
N,P = map(int,raw_input().split())
src = [tuple(map(int,raw_input().split())) for i in range(N)]

if P == 100:
  print(N)
  sys.exit()

wsum = sum(r[1] for r in src)
score = -wsum * P

xs = [w*(100-P) + b*P for w,b in src]
xs.sort(reverse=True)
i = 0
while score < 0:
  score += xs[i]
  i += 1
print(i)