## 648 - Stamps (II)

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

Moderator: Board moderators

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

### 648 - Stamps (II)

Can anybody explain the second sample input to me?
1 1 0
2 3 0
Why does the answer of 2 is 1 1, and the answer of 3 is tie.
thanx.

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
There are two types of stamps, let's call them A and B, both with value 1.

For the 1st case, there are three ways to allocate the stamps: (i) 2xA, (ii) 2xB, and (iii) 1A+1B. The first two only give 1 type of stamps, while the last one gives 2 different types of stamps, which is the 'best' combination, and it is unique. So the answer is 1 1.

For the 2nd case, there are 4 ways to allocate the stamps: (i) 3xA, (ii) 3xB, (iii) 2A+1B, and (iv) 1A+2B. The first two only gives one types of stamps, while the last two gives two different types of stamps. So the last two are better than the first two. Both (iii) and (iv) have the same total number of stamps (3), and the same highest single-value (1), so it is a tie.

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

### 648 help me!

i don't why i always get WA,could someone give some inputs and outputs?
thank!

Code: Select all

``````#include <iostream>
using namespace std;
#include <cstring>

int stamp[100];
int numOfType;
int customer;
int numOfStamp[100];
int stampUsed[100];
bool tie;
int stamp_list[5];
int now_stamp_list[5];
int now_type_sum;
int now_cnt;
int now_max;
bool ans;

void backtrack(int type,int sum,int type_sum,int cnt)
{
if(sum==customer)
{
ans=true;
int i;
int m;
if(now_type_sum<type_sum)
{
tie=false;
now_type_sum=type_sum;
now_cnt=cnt;
m=0;
for(i=0;i<cnt;i++)
{
now_stamp_list[i]=stamp_list[i];
if(stamp_list[i]>m)
m=stamp_list[i];
}
now_max=m;
}
else if(now_type_sum==type_sum)
{
if(cnt<now_cnt)
{
tie=false;
now_type_sum=type_sum;
now_cnt=cnt;
m=0;
for(i=0;i<cnt;i++)
{
now_stamp_list[i]=stamp_list[i];
if(stamp_list[i]>m)
m=stamp_list[i];
}
now_max=m;
}
else if(cnt==now_cnt)
{
m=0;
tie=false;
for(i=0;i<cnt;i++)
{
if(stamp_list[i]>m)
m=stamp_list[i];
}
if(m>now_max)
{
now_max=m;
now_cnt=cnt;
for(i=0;i<cnt;i++)
{
now_stamp_list[i]=stamp_list[i];
}
}
else if(m<now_max)
{
}
else
{
tie=true;
}
}
}
return;
}
if(type==numOfType)
{
return;
}
if(cnt==4)
{
return;
}

stampUsed[type]++;
sum+=stamp[type];
stamp_list[cnt]=stamp[type];
if(stampUsed[type]==1)
backtrack(type,sum,type_sum+1,cnt+1);
else
backtrack(type,sum,type_sum,cnt+1);
stampUsed[type]--;
sum-=stamp[type];

backtrack(type+1,sum,type_sum,cnt);
}

void output()
{
int i;
cout<<customer;
if(!ans)
{
cout<<" ---- none"<<endl;
}
else
{
cout<<" ("<<now_type_sum<<"): ";
if(tie)
cout<<"tie"<<endl;
else
{
for(i=0;i<now_cnt;i++)
cout<<now_stamp_list[i]<<" ";
cout<<endl;
}
}
}

int main()
{
int temp;
while(cin>>temp)
{
stamp[0]=temp;
numOfType=1;
while(cin>>temp && temp)
{
stamp[numOfType++]=temp;
}
while(cin>>customer && customer)
{
memset(stampUsed,0,sizeof(stampUsed));
tie=false;
now_type_sum=0;
now_cnt=0;
now_max=0;
ans=false;
backtrack(0,0,0,0);
output();
}
}
return 0;
}
``````

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Hi everyone,

I'm getting WA for this problem. Well I think that the problem description is very badly written. The terms like "types", "values" etc. go without any explanation. And they are wrongly used. For instance in the sample input, it calls 1 1 0 "two of the same type", yet in the sample output, it gives the number of types sold as "2"!...... So what does it mean? And I still do not understand what the phrase "highest single-value stamp" means..........

By the way, can somebody give me the correct output for

Code: Select all

``````1 1 2 2 0
1 2 3 4 5 6 7 8 9 0
``````
?

My WA code gives

Code: Select all

``````1 (1): tie
2 (2): 1 1
3 (2): tie
4 (3): tie
5 (3): tie
6 (4): 1 1 2 2
7 (3): tie
8 (2): tie
9 ---- none
``````
Thanks.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Hi,

After a whole day and no reply... Seeing that the acceptance rate is so high for this problem, I must have misinterpreted the problem statement badly....

Please also try this input:

Code: Select all

``````3 2 2 0
1 2 3 4 5 6 7 8 9 0
1 5 7 0
1 2 3 4 5 6 7 8 9 0
2 0
1 2 3 4 5 6 7 8 9 0``````

My WA code gives

Code: Select all

``````1 ---- none
2 (1): tie
3 (1): 3
4 (2): 2 2
5 (2): tie
6 (2): tie
7 (3): 2 2 3
8 (2): tie
9 (3): tie
1 (1): 1
2 (1): 1 1
3 (1): 1 1 1
4 (1): 1 1 1 1
5 (1): 5
6 (2): 1 5
7 (2): 1 1 5
8 (2): 1 7
9 (2): 1 1 7
1 ---- none
2 (1): 2
3 ---- none
4 (1): 2 2
5 ---- none
6 (1): 2 2 2
7 ---- none
8 (1): 2 2 2 2
9 ---- none
``````
Thanks again.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Both your outputs are correct.

"Highest single-value stamp" means just the largest value of stamp you've used (e.g. `1 2 5' is better than `1 3 4', because 5 > 4.)

Try this test case:

Code: Select all

``````4 2 1 3 0
6 0``````
The output should be "6 (3): 1 2 3"

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Thanks for your case. However, my WA code gives correct answer for this case too.....

How about this case? What should be the correct output:

Code: Select all

``````1 2 2 4 8 0
1 2 3 4 5 6 7 8 9 10 0
``````
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Code: Select all

``````1 (1): 1
2 (1): tie
3 (2): tie
4 (2): 2 2
5 (3): 1 2 2
6 (3): 1 1 2 2
7 (3): tie
8 (3): 2 2 4
9 (4): 1 2 2 4
10 (3): tie
``````

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Still output correctly.......

Should I just give up?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Could you post here your code? I'll check it with random inputs.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Last edited by Observer on Wed Sep 07, 2005 6:42 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Try this input:

Code: Select all

``````1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 0``````
Correct output:

Code: Select all

``````1 (1): 1
2 (1): 2
3 (2): 1 2
4 (2): 1 3
5 (2): 1 4
6 (3): 1 2 3
7 (3): 1 2 4
8 (3): 1 2 5
9 (3): 1 2 6
10 (4): 1 2 3 4
11 (4): 1 2 3 5
12 (4): 1 2 3 6
13 (4): 1 2 3 7
14 (4): 1 2 3 8
15 (4): 1 2 3 9
16 (4): 1 2 3 10
17 (4): 1 2 3 11
18 (4): 1 2 3 12
19 (4): 1 2 3 13
20 (4): 1 2 3 14
21 (4): 1 2 3 15
22 (4): 1 2 3 16
23 (4): 1 2 3 17
24 (4): 1 2 3 18
25 (4): 1 2 3 19
``````

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Thanks!!

Yes I've also just tried inputs like

Code: Select all

``````1 2 3 4 0
5 0``````
And at once I realize my mistake!!! (I just can't believe how careless I am..... Even a beginner won't get into mistakes as silly as this...... ) Got AC after modifying just ONE line..........

Thanks again for your help!!!!!!!! Now I can get some sleep
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 648 - Stamps (II)

Test data generator.

Code: Select all

``````#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[])
{
cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);

srand(time(NULL));
for (int cs = 1; cs <= 100; cs++)
{
int n = rand() % 25 + 1;
for (int i = 0; i < n; i++)
cout << rand() % 100 + 1 << ' ';
cout << "0\n";
n = rand() % 25 + 1;
for (int i = 0; i < n; i++)
cout << rand() % 200 + 1 << ' ';
cout << "0\n";
}

return 0;
}
``````