1180: fractional line delimitation /p1068 [noip2009 popularization group] fractional line delimitation

 1180： The score line is drawn /P1068 [NOIP2009 Popularization group ] The score line is drawn

1180： The score line is drawn The time limit : 1000 ms         Memory limit : 65536 KB Submission number : 23795     Passing number : 11229 【 Title Description 】 The selection of Expo volunteers is in progress A The city is in full swing . In order to select the most suitable talents ,A The city conducted a written test for all the contestants who signed up , Only when the written test score reaches the interview score line can the contestant enter the interview . The interview score line is based on the number of planned applicants 150%150% Delimitation , That is, if you plan to enroll mm Volunteers , The interview score line is ranked No m×150%m×150%（ Rounding down ） The score of the best player , And the final contestants who enter the interview are all the contestants whose written test scores are not lower than the interview score line . Now please write a program to mark the interview score line , And output all enter the interview of the contestant's registration number and written test results . 【 Input 】 first line , Two integers n,m（5≤n≤5000,3≤m≤n）n,m（5≤n≤5000,3≤m≤n）, Separated by a space , among nn  The total number of contestants who signed up for the written examination ,mm  The number of volunteers who plan to enroll . Input data guarantee m×150%m×150% Rounded down, less than or equal to nn. Line two to line two  n+1n+1  That's ok , Each line contains two integers , Separated by a space , They are the registration numbers of the players k（1000≤k≤9999）k（1000≤k≤9999） And the written test results of the contestant s（1≤s≤100）s（1≤s≤100）. The data ensure that the registration numbers of players are different . 【 Output 】 first line , There are two integers , Separated by a space , The first integer represents the interview score line ; The second integer is the actual number of contestants who entered the interview . Start with the second line , Each line contains two integers , Separated by a space , The registration number and the written test results of the contestants entering the interview , According to the written test results from high to low output , If the scores are the same , According to the registration number from small to large order output . 【 sample input 】 6 3 1000 90 3239 88 2390 95 7231 84 1005 95 1001 88 【 sample output 】 88 5 1005 95 2390 95 1000 90 1001 88 3239 88 【 Tips 】 Sample explanation ：m×150%=3×150%=4.5m×150%=3×150%=4.5, Round down to 44. Guarantee 44 The score line for an individual to enter an interview is 8888, But because 8888 There's heavy division , So all grades are greater than or equal to 8888 All the contestants can enter the interview , So in the end 55 Individuals enter the interview .

 P1068 [NOIP2009 Popularization group ] The score line is drawn

# [NOIP2009 Popularization group ] The score line is drawn

## Title Description

The selection of Expo volunteers is in progress A The city is in full swing . In order to select the most suitable talents ,$A$ The city conducted a written test for all the contestants who signed up , Only when the written test score reaches the interview score line can the contestant enter the interview . The interview score line is based on the number of planned applicants $150\%$ Delimitation , That is, if you plan to enroll $m$ Volunteers , The interview score line is ranked No $m \times 150\%$（ Rounding down ） The score of the best player , And the final contestants who enter the interview are all the contestants whose written test scores are not lower than the interview score line .

Now please write a program to mark the interview score line , And output all enter the interview of the contestant's registration number and written test results .

## Input format

first line , Two integers $n,m(5 ≤ n ≤ 5000,3 ≤ m ≤ n)$, Separated by a space , among $n$ The total number of contestants who signed up for the written examination ,$m$ The number of volunteers who plan to enroll . Input data guarantee $m \times 150\%$ Rounded down, less than or equal to $n$.

Line two to line two $n+1$ That's ok , Each line contains two integers , Separated by a space , They are the registration numbers of the players $k(1000 ≤ k ≤ 9999)$ And the written test results of the contestant $ s(1 ≤ s ≤ 100)$. The data ensure that the registration numbers of players are different .

## Output format

first line , Yes $2$ It's an integer , Separated by a space , The first integer represents the interview score line ; The second integer is the actual number of contestants who entered the interview .

Start with the second line , Each row contains $2$ It's an integer , Separated by a space , The registration number and the written test results of the contestants entering the interview , According to the written test results from high to low output , If the scores are the same , According to the registration number from small to large order output .

## Examples #1

### The sample input #1

```
6 3 
1000 90 
3239 88 
2390 95 
7231 84 
1005 95 
1001 88
```

### Sample output #1

```
88 5 
1005 95 
2390 95 
1000 90 
1001 88 
3239 88
```

## Tips

【 Sample explanation 】

$m \times 150\% = 3 \times150\% = 4.5$, Round down to $4$. Guarantee $4$ The score line for an individual to enter an interview is $88$, But because $88$ There's heavy division , So all grades are greater than or equal to $88$ All the contestants can enter the interview , So in the end $5$ Individuals enter the interview .

NOIP 2009 Popularization group The second question is

【 Ideas 】

Here n Choose a score from the individuals Greater than or equal to 1.5m（ Rounding down ） People who . First arrange the order , Then we have to deal with Rounded down 1.5m. In fact, it's direct

(int)(1.5*m)

It should be so , As a result, I just wrote

m*3/2-1

But there's nothing wrong with it （ can A On the star ）.

【AC Code 】 

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<string>
#include<vector>
using namespace std;
const int N=1e5+10;
inline int fread()
{
	char ch=getchar();
	int n=0,m=1;
	while(ch<'0' or ch>'9')
	{
		if(ch=='-')m=-1;
		ch=getchar();
	}
	while(ch>='0' and ch<='9')n=(n<<3)+(n<<1)+ch-48,ch=getchar();
	return n*m;
}
int n,m,ans;
struct node
{
	int x,y;
}a[N];
void _sort()// Sort 
{
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++)
		{
			if(a[i].y<a[j].y)swap(a[i].y,a[j].y),swap(a[i].x,a[j].x);
			else if(a[i].y==a[j].y)
				if(a[i].x>a[j].x)swap(a[i].x,a[j].x),swap(a[i].y,a[j].y);
		}
}
signed main()
{
	n=fread(),m=fread();
	for(int i=0;i<n;i++)a[i].x=fread(),a[i].y=fread();
	_sort();
	cout<<a[m*3/2-1].y<<" ";
	for(int i=0;i<n;i++)
		if(a[i].y>=a[m*3/2-1].y)ans++;// Several of them passed the interview 
	cout<<ans<<"\n";
	for(int i=0;i<n;i++)
		if(a[i].y>=a[m*3/2-1].y)cout<<a[i].x<<" "<<a[i].y<<"\n";
	return 0;
}

Who says I can't do the orange problem ！！！

Pay attention to it

Pay attention to it