3576 - 乔布斯比赛

你知道ACM比赛罚时很重要吗？ACM比赛首先按照过题数排名，过题数相同的队伍按照罚时排名（罚时小的队伍排在前面），如果罚时也相同则认为名次相同（名次相同时在排名表上队伍id 较小的队伍列在前面）。对于罚时，总体的罚时等于各题的罚时之和。对于某题的罚时，如果这道题最后没有通过（没有正确提交），则这题的罚时为0，否则这道题的罚时为：从比赛开始到该题第一次正确提交经过的时间+ 第一次通过之前的错误提交次数* 20 分钟。也就是说，对于某题，在你第一次通过后，以后的提交都不再算罚时。比如说你做A题要10分钟，B题要15分钟，如果先做A题再做B题，那么在ranking上的时间就是10 + （10）+ 15 = 35。如果先做B题再做A题总罚时就是15+(15)+10=40。现在乔布斯老师要做一场比赛，比赛有n道题，总时间是300分钟。假如乔布斯老师仅仅看题目（0秒）就可以知道他做每道题需要的时间，并且都是一次提交通过，你能计算出乔布斯老师在规定时间内最多做出多少道题及其Penalty（总罚时）吗。

Input

第一行是一个数字n 0<n<=25，代表题目数

第二行是n个数字，第i个数字代表乔布斯老师做出编号为i的题所需要的时间 ti( 0 < ti <= 300)。

Output

第一行输出乔布斯老师的出题数和Penalty（总时间）
以下按照顺序输出乔布斯老师出题的顺序,每行一个编号。（详见输出样例）PS：时间一样的按编号升序输出。

Examples

Input

3
299 1 2

Output

2 4
2
3

Solution C

#include<stdio.h>
typedef struct Time
{
	int time;
	int number;
}AB;
int main()
{
	AB a[25],temp;
	int n,i,j,k,num,alltime,ftime;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
	    scanf("%d",&a[i].time);
	    a[i].number=i+1;
	}
	for(i=0;i<n-1;i++)
	{
		k=i;
		for(j=k+1;j<n;j++)
		{
			if(a[k].time>a[j].time)
			k=j;
		}
		if(k!=i)
		{
			temp=a[i];
			a[i]=a[k];
			a[k]=temp;
		}
	}
	alltime=0;
	num=0;
	ftime=0;
	for(i=0;;i++)
	{
		ftime=ftime+a[i].time;
		if(ftime>300)
		{
			break;
		}
		else
		{
			alltime=alltime+ftime;
		    num++;
		}
	}
	printf("%d %d\n",num,alltime);
	for(i=0;i<num;i++)
	printf("%d\n",a[i].number);
	return 0;
}

Time Limit	1 second
Memory Limit	128 MB

Discuss Stats

上一题下一题