2018暑假多校賽【第四場】-Problem D. Nothing is Impossible-YZHHHHHHH

Problem D. Nothing is Impossible

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Total Submission(s): 562    Accepted Submission(s): 329

Problem Description

m students, including Kazari, will take an exam tomorrow.

The paper consists of exactly n problems, the i-th problem contains ai correct answers and bi incorrect answers, i.e. the i-th problem contains ai+bi candidates in total.

Each student should choose exactly one candidate as answer for each problem. If the answer to a certain problem is correct, then the student will get one point. The student who gets the most points wins.

Students only know the structure of the paper, but they are able to talk with each other during the exam. They decide to choose a subset S of all n problems, and they will only be able to submit answers on these problems.

They want to know the maximum size of S that the winner among them will solve all the problems in S if they take the optimal strategy.

For sample 1, students can choose S={1}，and we need at least 4 students to guarantee the winner solve the only problem.

For sample 2, students can choose S={1,2,3}, and we need at least 24 students to guarantee the winner solve these three problems, but if |S|=4, we need at least 96students, which is more than 50.

Input

The first line of the input contains an integer T (1≤T≤100) denoting the number of test cases.

Each test case starts with two integers n,m (1≤n≤100,1≤m≤109), denoting the number of problems and the number of students. Each of next n lines contains two integers ai,bi （1≤bi≤100,ai=1）, indicating the number of correct answers and the number of incorrect answers of the i-th problem.

Output

For each test case, print an integer denoting the maximum size of S.

Sample Input

2

3 5

1 3

1 3

1 3

5 50

1 1

1 3

1 2

1 3

1 5

Sample Output

1

3

題意：

有n道題，m個學生，下面n行（左ai，右bi），ai 正确答案個數（ai==1），bi 錯誤答案個數

這群學生可以選擇裡面的一些題目，每個人隻能選一個答案，但他們能夠互相交流，他們想要有一個人可以拿到最多的分數。

一道題被一個人做對的機率是：1/（bi+1），兩道題被人做對的機率是

1/((b1+1) * (b2+1))。以此類推，當人數不夠的時候結束。

代碼：

記得開long long

#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
	int t;
	while (scanf("%d",&t) != EOF){
		long long n,m;
		while (t--) {
			scanf("%lld %lld",&n,&m);
			long long ans = 0, u, v, sum = 1;
			long long num[1000];
			for (int i = 0; i < n; i++){
				scanf("%lld %lld", &u, &v);
				num[i] = u+v;
			}
			sort(num,num+n);
			
			for (int i = 0; i < n; i++){
				sum *= num[i];
				if (sum > m) break;
				ans++;
			}
			printf("%lld\n",ans);
		}
	}
}