10670 - Work Reduction

[miras]

this prob. is quite nice...
i tried to solve it diuring the contest.. but i was getting TLEs later i used sth like greedy i now i got WA csn u give me some tests on with my prog. gives wrong results ??

PLZ.

[shuniu]

Greedy is the right way to go, couple things to watch for though:

Notice the output format, eg "Case 1, Case 2"
the name can be more than 1 character
the output order should be sorted by name if costs are equal
watch out for cases where A or B equals 0, then you could get into trouble for dividing by 0.

Input:

Code: Select all

7
100 51 3
ABC:10,1
ABD:1,10
BCD:5,5
100 49 3
DDD:10,1
BBB:1,10
AAAAA:5,5
1300 1 3
EASY:100,1
MEDIUM:1,100
HARD:1,1000
1500 88 3
SECOND:0,0
LAST:10,0
FIRST:0,10
1000 1000 3
A:100,100
B:10,10
C:0,0
100000 1 2
B:10000,10
A:10,10000
100000 9 1
ABC:10000,10000

Output:

Code: Select all

Case 1
ABD 49
BCD 245
ABC 490
Case 2
AAAAA 10
BBB 11
DDD 11
Case 3
EASY 10
MEDIUM 461
HARD 1299
Case 4
FIRST 0
SECOND 0
LAST 50
Case 5
A 0
B 0
C 0
Case 6
B 160
A 75610
Case 7
ABC 160000

[miras]

Code: Select all

Case 1
ABD 49
BCD 245
ABC 490
Case 2
AAAAA 10
BBB 11
DDD 11
Case 3
EASY 10
MEDIUM 381
HARD 650
Case 4
FIRST 0
SECOND 0
LAST 50
Case 5
A 0
B 0
C 0
Case 6
B 160
A 67810
Case 7
ABC 160000

[/pascal][/code]

[miras]

OK
got AC

thx to all of You...

[miras]

[quote="miras"]

Code: Select all

NTH...

[htl]

I don't know how to get the answer of case 1, could someone help me?

[misof]

I don't know how to get the answer of case 1, could someone help me?

Code: Select all

1
100 51 3 
ABC:10,1 
ABD:1,10 
BCD:5,5

You start with 100 and want to obtain 51 after some number of steps. In each step you may either decrease the number by 1, or divide it by 2. Clearly, in this case if we use division, the result will be too small. Therefore the only possibility is to make 49 decreasing steps. The corresponding costs are: 49*10=490 for ABC, 49*1=49 for ABD and 49*5=245 for BCD.

Code: Select all

Case 1 
ABD 49 
BCD 245 
ABC 490

[joy]

I dont understand why this code is wrong...
plz help.. i got too many WA

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

char name[105][22], str[88], ss[77];
int cst[105][4];

int callcost(int n, int rem, int x, int y)
{
	int cost=0;
	while((n+1)/2 >= rem && n!=rem)
	{		
		if(y < x*((n+1)/2))
			cost+=y;
		else
			break;
		n/=2;
	}
	if(n>rem)
		cost+=((n-rem)*x);
	return cost;
}




int main()
{
//	freopen("in.txt", "r", stdin);
	int t, test, i, j, n, rem_n, m, l, cost, k;
	scanf("%d", &test);
	for(t=0; t<test; t++)
	{
		scanf("%d %d %d", &n, &m, &l);
		for(i=0; i<l; i++)
		{
			scanf("%s", str);
			j=0;
			k=0;
			while(str[j]!=':')
				ss[k++]=str[j++];
			ss[k]=NULL;
			strcpy(name[i], ss);
			k=0;
			j++;
			while(str[j]!=',')
				ss[k++]=str[j++];
			ss[k]=NULL;
			cst[i][0]= atoi(ss);
			
			k=0;
			j++;
			while(str[j])
				ss[k++]=str[j++];
			ss[k]=NULL;
			cst[i][1]= atoi(ss);

			cost=callcost(n, m, cst[i][0], cst[i][1]);
			cst[i][2]=cost;
		}

		for(i=0; i<l; i++)
			for(j=i+1; j<l; j++)
				if(cst[i][2]>cst[j][2] || (cst[i][2]==cst[j][2] && strcmp(name[i], name[j])>0))
				{
					strcpy(str, name[i]);
					strcpy(name[i], name[j]);
					strcpy(name[j], str);
					int temp=cst[i][2];
					cst[i][2]=cst[j][2];
					cst[j][2]=temp;
				}
		printf("Case %d\n", t+1);
		for(i=0; i<l; i++)
			printf("%s %d\n", name[i], cst[i][2]);
	}
	return 0;
}

[nymo]

Joy, I 've not read your code properly, but why don't you use qsort() for this problem... it suits well here.
my cost calculation function goes here:

Code: Select all

int CostCalc(int i)
{
	int cost, rest;
		
	cost = 0;
	if (!(agencies[i].a))	return cost;

	rest = n;
	while (rest - (int)ceil((double)rest/2) >= m && (rest/2))
	{
		if ((int)ceil((double)rest/2) * agencies[i].a > agencies[i].b)
			cost += agencies[i].b; 
		else
			cost += (int)ceil((double)rest/2) * agencies[i].a;
		rest -= (int)ceil((double)rest/2);
	}
	if (rest > m)
		cost += (rest - m) * agencies[i].a;
	return cost;
}

Hope you get ACC

[DD]

Greedy is the right way to go, couple things to watch for though:

Notice the output format, eg "Case 1, Case 2"
the name can be more than 1 character
the output order should be sorted by name if costs are equal
watch out for cases where A or B equals 0, then you could get into trouble for dividing by 0.

Input:

Code: Select all

7
100 51 3
ABC:10,1
ABD:1,10
BCD:5,5
100 49 3
DDD:10,1
BBB:1,10
AAAAA:5,5
1300 1 3
EASY:100,1
MEDIUM:1,100
HARD:1,1000
1500 88 3
SECOND:0,0
LAST:10,0
FIRST:0,10
1000 1000 3
A:100,100
B:10,10
C:0,0
100000 1 2
B:10000,10
A:10,10000
100000 9 1
ABC:10000,10000

Output:

Code: Select all

Case 1
ABD 49
BCD 245
ABC 490
Case 2
AAAAA 10
BBB 11
DDD 11
Case 3
EASY 10
MEDIUM 461
HARD 1299
Case 4
FIRST 0
SECOND 0
LAST 50
Case 5
A 0
B 0
C 0
Case 6
B 160
A 75610
Case 7
ABC 160000

I think this problem should be solved by dymamic programming. How could you solve this problem by greedy?

[uDebug]

Replying to follow the thread.