10670 - Work Reduction

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

10670 - Work Reduction

Post by miras » Thu Jun 17, 2004 11:18 am

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.
Remember Never Give Up
Regrads
Miras

shuniu
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm

Post by shuniu » Thu Jun 17, 2004 4:57 pm

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
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Fri Jun 18, 2004 12:21 pm

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]
Remember Never Give Up
Regrads
Miras

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Fri Jun 18, 2004 12:29 pm

OK
got AC

thx to all of You...
Remember Never Give Up
Regrads
Miras

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Fri Jun 18, 2004 1:23 pm

[quote="miras"]

Code: Select all


NTH...

Remember Never Give Up
Regrads
Miras

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Fri Jun 25, 2004 3:56 am

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

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Fri Jun 25, 2004 12:14 pm

htl wrote: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
New poster
Posts: 48
Joined: Wed Oct 18, 2006 1:00 pm
Location: Dhaka, Bangladesh
Contact:

WA

Post by joy » Sun Sep 09, 2007 9:36 pm

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;
}
form kisui na ... class tai asol....
iF U hv d class u get the form....

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo » Mon Sep 10, 2007 7:10 pm

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 :)
regards,
nymo

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re:

Post by DD » Fri Jan 22, 2010 4:58 pm

shuniu wrote: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? :o
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10670 - Work Reduction

Post by uDebug » Wed Jun 25, 2014 1:31 pm

Replying to follow the thread.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 106 (10600-10699)”