## 10779 - Collectors Problem

Moderator: Board moderators

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:

### 10779 - Collectors Problem

I tried this one with maximum flow.
At first I create a capacity graph cap[][] and then call maxFlow function?

Here is my method to create capacity graph.

Code: Select all

``````#define SIZE 100
int cap[SIZE][SIZE];

int maxFlow( int numberOfVert, int source, int destination ){
........

return flow;
}

int main()
{

int T, nPerson, nSticker, nst;
int i, j, k, a, u;
int frq[110], frq1[110];
//freopen("10779.in","r",stdin);
cin>>T;
for(u=1;u<=T;u++){
cin>>nPerson>>nSticker;
memset( cap, 0, sizeof( cap ) );
for(i=1;i<=nPerson;i++){
cin>>nst;
if(i==1){
for(j=1;j<=nSticker;j++)frq1[j]=0;

for(j=1;j<=nst;j++){
cin>>a;
cap[0][a]++;
frq1[a]++;
}
}
else{
for(j=1;j<=nSticker;j++)frq[j]=0;

for(j=1;j<=nst;j++){
cin>>a;
frq[a]++;
}

for(j=1;j<=nSticker;j++)if(frq[j]>1)for(k=1;k<=nSticker;k++)if(!frq[k])cap[k][j]++;
}
}
for(j=1;j<=nSticker;j++)cap[j][nSticker+1]=1;
cout<<"Case #"<<u<<": "<<maxFlow(nSticker+2, 0, nSticker+1 )<<endl;
}
return 0;
}
``````
Is there any problem in my of capacity graph creation ?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
I think that your program won't work in the following test case:

Code: Select all

``````1
4 6
12  4 4 4 4 5 5 5 5 6 6 6 6
2   1 1
20  2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6
20  2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6
``````
Correct output should be:

Code: Select all

``Case #1: 4``
In this scenario, only person #2 is willing to buy Bob's tickets, and he can sell only one ticket of type 1.
But your program, as I understand it, will try to buy several tickets from him.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
Thanks mf,
I got the point I think!
I changed my code but again Wrong Answer

Code: Select all

``````
#define SIZE 200
int cap[SIZE][SIZE];

int maxFlow( int numberOfVert, int source, int destination ){
........

return flow;
}

int main()
{

int T, nPerson, nSticker, nst;
int i, j, k, a, u, total;
int frq[110], frq1[110];
//freopen("10779.in","r",stdin);
cin>>T;
for(u=1;u<=T;u++){
cin>>nPerson>>nSticker;
memset( cap, 0, sizeof( cap ) );
total=nSticker+1;
for(i=1;i<=nPerson;i++){
cin>>nst;
if(i==1){
for(j=1;j<=nSticker;j++)frq1[j]=0;

for(j=1;j<=nst;j++){
cin>>a;
cap[0][a]++;
frq1[a]++;
}
}
else{
for(j=1;j<=nSticker;j++)frq[j]=0;

for(j=1;j<=nst;j++){
cin>>a;
frq[a]++;
}

for(j=1;j<=nSticker;j++){
if(frq[j]>1){
for(k=1;k<=nSticker;k++){
if(!frq[k])cap[k][nSticker+j]++;
}
cap[nSticker+j][j]+=(frq[j]-1);
//total++;
}
}
}
}
for(j=1;j<=nSticker;j++)cap[j][2*nSticker+1]=1;
cout<<"Case #"<<u<<": "<<maxFlow(2*nSticker+2, 0, 2*nSticker+1 )<<endl;
}
return 0;
}``````
I need hint, plz help.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
I believe it won't work on this test case. Can't say for sure, unless you post your complete code, so that I could compile it.

Code: Select all

``````1
5 7
12  4 4 4 4 5 5 5 5 6 6 6 6
2   1 1
20  2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6
20  2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6
24  1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6
``````
Correct output:

Code: Select all

``Case #1: 4``

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
mf: I have sent you my code

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Here are a few test cases:

Code: Select all

``````12

2 4
3 1 1 1
4 3 3 4 4

7 5
4 5 4 5 5
46 4 1 1 4 1 4 5 4 5 1 2 2 5 5 5 2 3 5 5 2 5 5 5 5 1 5 1 1 2 3 3 4 5 1 1 4 2 3 5 2 2 5 5 4 4 3
41 2 5 3 5 3 5 1 3 1 5 4 5 5 3 5 1 2 3 2 1 1 3 4 5 1 1 4 3 2 2 2 2 3 5 2 3 1 3 3 1 4
12 1 3 4 3 2 3 1 1 2 4 2 2
31 5 5 3 2 2 1 3 4 5 4 1 3 5 4 3 2 3 5 5 1 4 3 3 2 4 1 3 5 3 3 4
19 5 1 1 3 4 1 2 2 1 5 1 4 1 4 1 3 1 3 3
44 3 2 2 3 5 1 1 5 3 2 2 4 3 2 3 1 5 5 2 2 4 2 1 4 1 5 5 5 1 4 5 5 4 3 1 3 4 5 1 2 4 4 5 4

7 20
19 6 8 13 5 10 6 5 10 11 10 20 19 19 9 15 5 4 18 2
18 1 20 6 18 10 12 8 14 16 11 3 4 3 7 10 3 11 15
12 7 18 20 4 17 8 7 20 11 2 6 5
16 16 9 12 20 16 3 19 17 9 7 18 7 13 4 10 17
22 11 20 7 1 9 6 20 2 11 19 7 9 19 18 20 6 10 14 14 17 6 10
13 9 10 5 2 1 12 8 8 1 5 5 14 6
32 20 12 11 4 18 20 10 9 4 5 3 16 3 3 18 8 3 7 14 17 10 19 9 17 11 2 17 12 4 1 1 20

7 24
14 5 23 13 16 14 5 5 3 14 16 22 22 3 15
11 9 8 2 10 8 22 5 10 24 15 18
4 17 21 6 14
50 5 17 10 24 18 13 4 13 2 2 6 4 17 7 6 1 15 23 3 13 3 7 4 23 19 20 4 2 19 22 14 13 9 3 5 11 3 11 22 5 22 17 19 14 13 14 8 2 10 5
50 1 16 6 17 6 23 24 21 21 1 21 19 19 8 2 13 15 23 20 4 23 18 11 7 24 2 7 6 22 13 17 7 17 2 17 10 11 7 4 1 22 24 2 22 18 21 23 1 13 6
50 13 17 15 24 2 5 18 17 23 20 19 6 23 20 18 21 7 23 24 9 22 22 23 10 17 13 24 7 20 18 4 14 2 18 12 9 18 24 5 20 5 5 13 16 20 13 3 16 23 22
33 13 8 7 12 6 9 11 13 24 21 16 20 15 17 15 4 22 15 1 16 1 17 16 22 21 24 10 4 19 5 17 10 22

9 14
20 13 10 2 12 4 9 8 4 9 14 9 12 5 9 2 14 5 14 13 5
49 12 13 10 9 2 10 14 2 13 6 4 1 6 12 1 7 4 7 7 5 12 12 9 7 8 1 14 5 11 2 3 13 12 7 4 4 7 5 11 4 12 1 11 1 10 3 8 9 4
30 9 1 5 8 10 7 3 14 6 10 7 4 5 4 12 11 5 3 11 1 3 1 12 2 4 10 7 11 3 11
46 14 13 14 1 10 13 14 11 14 7 8 13 14 4 6 4 8 2 3 3 9 8 12 2 4 11 14 6 5 2 8 10 11 14 5 9 4 3 3 9 11 11 3 12 5 13
10 3 1 13 7 9 2 11 13 5 2
43 7 12 8 3 9 13 9 9 2 8 8 4 5 4 3 2 10 2 5 14 11 11 7 4 5 4 5 10 5 14 12 3 14 10 9 10 11 10 9 12 13 5 2
21 4 10 13 2 13 13 14 3 12 7 7 8 1 4 7 3 2 13 13 4 5
37 12 8 5 10 2 14 1 7 4 8 14 14 12 6 6 4 6 12 7 11 8 3 12 14 7 6 4 4 1 4 6 4 11 3 13 1 13
39 9 3 9 3 12 13 7 11 14 10 14 7 4 2 7 6 6 1 12 6 9 11 7 9 10 5 2 10 4 12 13 9 14 4 8 9 10 4 11

7 18
21 2 2 13 18 11 1 8 8 1 2 17 8 17 13 3 14 17 11 10 13 18
3 6 1 1
44 14 1 17 10 1 6 2 16 5 15 11 2 18 9 10 16 8 11 11 18 11 12 2 12 16 17 5 11 11 15 2 14 17 18 6 16 9 8 4 4 5 3 5 3
4 13 16 13 6
22 7 4 11 9 2 6 5 6 17 15 4 12 9 11 5 5 7 10 14 16 13 17
15 4 2 12 1 11 18 11 7 14 3 15 9 7 18 5
27 11 13 8 1 5 18 13 1 14 2 7 6 14 14 18 7 16 7 17 1 5 2 15 11 9 1 12

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

10 24
24 7 5 1 17 14 6 23 19 6 13 14 3 1 8 20 16 11 24 1 2 15 20 13 7
36 21 7 10 2 23 7 21 1 21 1 18 20 20 9 23 20 4 14 6 12 4 21 4 18 23 17 5 3 21 12 1 20 4 20 6 20
46 18 14 15 23 11 1 9 13 9 2 11 19 17 16 17 24 24 8 9 21 10 2 14 10 20 3 22 17 3 1 18 3 18 13 3 14 10 22 17 7 15 22 5 1 21 15
11 22 2 22 19 7 5 12 5 6 24 17
11 3 23 18 5 12 6 9 12 21 22 11
3 5 21 19
35 1 13 24 9 20 24 23 15 7 9 4 19 2 22 18 9 24 9 9 12 4 15 18 5 3 2 10 5 4 17 23 17 16 4 7
32 11 11 7 8 3 6 7 5 3 3 22 20 15 1 24 11 10 13 22 20 19 12 17 12 24 17 22 17 3 10 22 22
16 14 14 18 19 12 7 21 1 19 15 12 6 18 23 11 23
19 19 16 15 7 11 18 10 1 15 20 24 24 8 15 7 18 10 19 16

10 20
18 16 4 12 8 12 8 8 2 8 4 4 14 7 11 5 9 4 7
31 3 11 1 10 5 8 15 4 17 17 5 7 9 4 15 11 15 11 6 12 10 16 12 17 2 17 16 18 7 18 6
29 17 17 11 18 11 13 9 4 4 16 7 1 18 13 4 14 11 11 6 7 9 17 6 3 8 2 6 12 8
24 3 15 9 9 15 10 20 1 10 5 20 13 14 16 10 7 20 6 15 9 9 8 3 3
0
31 14 19 19 14 16 6 20 14 2 18 18 17 12 10 20 11 15 10 16 9 3 14 7 2 1 10 9 17 17 16 9
7 9 13 4 18 9 1 8
11 12 11 1 4 10 2 3 16 6 15 2
16 8 15 19 20 2 4 19 12 5 3 18 12 3 2 6 13
34 6 11 14 6 9 14 7 18 13 12 13 9 18 16 16 7 18 16 4 11 2 9 2 11 15 1 20 8 19 1 6 5 6 14

10 18
21 4 11 18 4 5 8 5 4 4 14 8 14 6 16 4 8 7 14 2 11 7
42 7 6 14 18 7 11 7 1 2 12 13 4 11 16 16 6 17 3 9 15 3 16 5 10 2 8 12 12 10 14 8 13 10 18 13 4 6 14 6 14 11 11
28 13 2 3 3 1 4 14 12 3 9 13 6 6 13 9 18 6 12 18 7 3 9 15 15 4 14 4 17
33 10 14 7 4 2 8 13 11 3 7 9 18 13 5 1 14 17 3 18 7 15 16 5 18 11 13 13 1 14 18 2 17 8
31 11 16 18 13 10 4 16 3 8 6 3 11 15 16 18 16 8 16 5 12 9 8 4 12 7 10 10 18 4 4 9
35 13 16 17 9 6 14 12 2 8 5 6 2 4 2 3 3 2 9 6 4 4 4 3 14 4 7 3 15 15 14 9 7 8 1 2
46 18 5 18 17 7 14 15 7 1 8 8 8 13 4 15 15 10 5 8 8 3 5 12 16 9 15 5 17 12 13 3 7 14 14 9 10 8 4 9 9 16 4 12 11 11 6
44 1 15 17 17 16 11 18 16 9 16 4 1 6 12 2 4 1 3 17 12 8 5 15 17 5 8 13 4 6 1 5 13 1 10 3 11 17 3 17 14 13 13 15 3
4 16 10 13 9
17 13 11 16 12 2 4 11 6 5 14 14 13 1 7 11 8 9

8 20
17 5 14 19 10 13 20 11 13 7 15 7 13 6 15 17 13 14
44 7 6 1 16 15 6 17 9 3 20 4 5 1 3 10 15 3 12 15 2 16 20 3 7 18 6 20 18 1 17 1 18 6 5 3 17 18 16 1 16 9 1 10 8
25 1 19 7 10 4 13 12 18 8 18 2 18 12 14 7 7 13 1 10 5 8 17 16 1 14
40 17 7 13 5 7 19 1 1 9 17 19 9 10 7 7 16 14 11 9 18 6 14 9 1 19 3 2 9 13 20 14 17 10 16 18 10 5 18 13 1
33 20 17 4 4 14 5 6 1 16 6 15 14 8 17 19 15 13 1 6 10 4 6 8 20 9 16 12 20 19 8 14 2 11
45 7 6 6 10 4 10 3 5 6 15 10 4 2 13 7 1 9 1 16 13 2 20 2 11 8 6 14 18 13 8 18 10 16 6 13 10 2 10 11 19 7 17 11 7 1
1 7
29 19 4 12 17 15 5 3 12 3 16 13 6 13 18 19 12 14 8 3 19 8 5 7 11 15 1 19 19 6

5 25
29 12 21 20 2 21 6 16 23 2 19 9 17 5 6 20 22 16 6 23 8 10 6 20 15 18 5 3 17 19
35 13 18 18 16 13 19 22 14 11 5 1 21 25 11 4 10 4 17 15 19 8 10 20 7 4 17 10 5 16 10 22 19 23 7 9
23 8 21 21 12 2 9 6 15 21 7 15 18 1 22 11 21 12 20 1 6 21 20 6
33 7 9 7 16 4 19 9 15 4 24 15 6 2 15 7 14 17 21 6 17 20 9 9 5 7 18 21 19 11 24 9 14 20
28 12 11 24 6 17 16 16 23 20 4 19 6 3 3 20 22 1 10 10 4 5 8 21 9 8 12 22 14
``````
Output of my accepted program:

Code: Select all

``````Case #1: 2
Case #2: 3
Case #3: 18
Case #4: 12
Case #5: 12
Case #6: 15
Case #7: 19
Case #8: 23
Case #9: 16
Case #10: 15
Case #11: 15
Case #12: 23
``````

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
Thanks a Lot mf.
I got ACCEPTED at last.
Your input/output helped me a lot.

kevinufo
New poster
Posts: 2
Joined: Mon Oct 08, 2007 6:16 pm
As far as I know, this problem can be solved by max-flow algorithm,
but I can't figure out how to map the problem to the corresponding graph.
I think any explanation or example will help.

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

### Re: 10779 - Collector's Problem

If I recall correctly, here's how to solve this problem.

The trick is to build a graph, such that every path in it will correspond to a series of exchanges of duplicate stickers, starting with Bob giving away one of his duplicates, and ending with him receiving a new sticker.

The graph has n subgraphs, one for each person (including Bob).

i-th subgraph has the following vertices:
• m input vertices In(i, j) and m output vertices Out(i, j), where j=1..m (j denotes sticker's type)
• a source s(i) and a sink t(i)
And the edges are:
• from In(i, j) to t(i) of capacity 1 for all j's such that i-th person doesn't yet have j-th sticker
(a flow on this edge means that i-th person decides to buy j-th sticker)
• from t(i) to s(i) of infinite capacity, if i > 1.
(if i=1, s(1) and t(1) will be source and sink; if i>1, we actually need only one vertex here, but let's keep two just for consistency)
• from s(i) to Out(i, j) of capacity equal to the number of duplicate stickers of type j that i-th person has;
(each unit of flow here corresponds to a sale of j-th sticker by i-th person)
• an edge from Out(i, k) to In(j, k) for all i,j,k of capacity 1
The value of maximum flow from s(1) to t(1) should give you the maximum number of additional stickers that Bob can gain by trading his duplicate stickers.

crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

### Re: 10779 - Collector's Problem

never mind, i made a stupid mistake. ACed...

pratikjain1993
New poster
Posts: 2
Joined: Sun Mar 23, 2014 10:31 pm

### Re: 10779 - Collector's Problem

I made the graph using this function :

Code: Select all

``````void build_graph()
{
int i,j;
nodes=0;
vector <pii> in,out;
FOR(i,1,n)
{
int src = ++nodes;
int sink = ++nodes;
if(i>1)
{
cap[sink][src]=1000000;
}
FOR(j,1,m)
{
nodes++;
if(mp[i].count(j))
{
if(mp[i][j]==1)
continue;
out.pb(make_pair(nodes,j));
cap[src][nodes] = mp[i][j]-1;
}
else
{
in.pb(make_pair(nodes,j));
cap[nodes][sink]=1;
}
}
}
FORL(i,0,out.size())
{
FORL(j,0,in.size())
{
if(out[i].second==in[j].second)
{
cap[out[i].first][in[j].first] = 1;
}
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
#endif // ONLINE_JUDGE
int t,tc;
scanf("%d",&t);
FOR(tc,1,t)
{
int k,i,j;
SETZERO(cap);
si(n);si(m);
FOR(i,1,n)
{
mp[i].clear();
si(k);
FOR(j,1,k)
{
int x;
si(x);
mp[i][x]++;
}
}
build_graph();
assert(nodes<600);
printf("Case #%d: %d\n",tc,max_flow()+mp[1].size());
FOR(i,0,nodes)
{
}
}
}
``````
I have created only those output nodes which have non zero flow capacity( that is there is 1 or more duplicates available) from s(i) ... Similarly only those input nodes which are to have flow capacity=1... I am getting WA.. I have tried a lot but am unable to find the mistake... Please somebody help...

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10779 - Collector's Problem

Check input and AC output for thousands of problems on uDebug!

pratikjain1993
New poster
Posts: 2
Joined: Sun Mar 23, 2014 10:31 pm

### Re: 10779 - Collector's Problem

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10779 - Collector's Problem

Input:

Code: Select all

``````20
6 20
15 20 2 1 16 15 9 20 16 7 14 1 15 6 7 20
42 16 20 7 6 4 10 5 11 6 3 4 19 19 17 18 19 10 10 6 16 19 5 11 17 19 4 11 16 10 10 14 6 1 20 3 5 1 7 15 6 2 10
11 20 6 13 18 16 3 4 11 13 20 14
1 10
23 11 18 6 1 11 3 13 3 17 9 3 4 15 1 17 4 16 16 10 9 6 17 11
26 19 15 20 12 3 10 8 5 19 6 5 9 20 18 3 17 18 18 20 13 18 16 16 13 3 17
10 22
15 3 14 12 15 8 13 19 21 9 18 21 12 22 5 13
27 14 11 9 15 4 7 20 9 16 6 6 15 11 15 15 11 5 4 2 12 15 20 10 1 13 8 10
30 10 20 7 21 9 13 13 10 17 10 17 11 16 20 1 2 12 13 12 14 15 13 3 7 9 10 5 19 15 12
18 1 9 12 21 15 2 10 3 19 17 17 5 10 14 5 9 3 15
21 15 7 9 17 13 15 3 15 12 15 4 16 15 13 5 12 5 7 21 5 1
38 21 3 1 12 5 7 13 19 3 5 4 12 19 14 2 21 7 13 12 10 7 4 20 11 15 1 15 11 5 13 2 4 15 22 13 19 6 3
24 9 7 17 18 2 8 19 20 14 10 9 22 14 13 19 22 3 19 13 14 2 3 13 3
36 12 15 12 17 16 3 3 20 19 18 21 5 15 19 16 2 5 15 13 15 10 12 18 4 2 7 3 3 19 5 18 6 18 7 22 11
26 1 8 4 18 7 8 10 1 22 9 5 12 19 18 21 9 13 3 8 17 5 8 11 8 3 16
42 8 13 11 15 13 16 18 7 20 2 14 20 1 1 1 12 19 18 9 3 6 11 9 22 13 16 10 20 19 1 20 2 13 6 16 2 22 11 8 19 10 21
6 10
3 1 6 2
21 8 6 7 8 8 4 2 10 9 8 4 1 1 7 5 1 2 4 10 2 3
41 6 10 2 7 4 4 2 5 3 9 1 1 8 10 4 10 1 4 9 4 4 9 10 1 9 3 4 10 5 7 2 2 8 3 8 1 9 10 8 1 10
39 4 8 9 7 9 10 1 7 5 6 5 7 6 4 1 10 5 5 8 6 6 7 1 4 7 9 5 6 9 4 5 2 3 6 1 1 7 1 7
46 6 4 9 4 7 2 3 1 6 2 9 4 8 9 9 6 7 5 2 7 10 6 1 3 3 1 5 9 3 4 2 10 7 2 3 5 3 7 7 1 10 5 6 7 3 4
38 1 10 6 10 9 3 10 1 6 2 8 4 6 1 7 5 7 9 10 1 3 8 7 3 8 4 8 4 8 3 8 9 2 5 10 3 8 1
8 18
41 18 12 7 6 5 1 10 1 14 16 11 18 9 2 13 6 5 10 7 14 8 17 11 4 4 9 13 6 16 5 15 13 15 3 1 1 4 10 17 15 6
32 12 12 8 6 15 11 14 3 4 3 2 14 4 5 3 17 11 16 1 5 10 15 8 10 13 9 18 11 3 3 2 15
37 7 18 10 17 13 12 2 13 11 14 15 16 16 11 6 11 11 10 2 6 15 10 18 5 7 9 8 9 8 2 4 14 1 11 11 12 2
27 4 13 5 16 10 18 8 13 8 17 4 10 4 17 17 1 3 5 9 8 11 16 9 14 10 8 4
19 17 5 11 2 17 14 16 6 11 5 18 1 1 2 10 2 18 6 3
14 10 9 8 2 5 16 13 14 3 14 15 1 18 5
6 15 18 16 2 11 18
14 9 17 17 16 18 14 3 18 13 10 7 2 9 11
8 19
14 13 7 17 17 11 2 2 2 7 6 5 2 18 15
35 10 10 19 5 5 4 5 3 8 4 19 3 9 4 10 1 16 13 17 13 4 19 11 3 3 16 4 4 12 18 7 2 8 6 3
3 6 8 11
36 8 7 12 17 10 2 17 4 14 15 16 14 11 5 13 13 17 16 13 9 11 19 11 15 2 10 4 7 14 12 16 3 18 8 16 6
18 13 9 16 5 2 10 12 6 1 2 4 13 11 12 5 10 19 16
18 7 1 11 1 9 4 3 4 11 15 9 16 9 14 12 10 13 19
2 18 19
48 18 12 12 8 13 18 4 10 4 10 7 14 8 15 18 7 15 6 3 5 19 8 15 8 17 8 7 13 4 3 14 2 12 3 9 2 17 10 8 1 19 14 12 4 6 7 11 2
6 25
8 20 12 8 24 22 7 9 20
49 2 9 14 3 15 14 16 19 18 22 6 11 24 2 14 19 15 13 14 10 15 18 5 3 2 5 24 10 13 20 1 14 3 15 18 19 5 11 15 24 9 22 9 7 23 24 2 12 11
12 23 25 9 4 2 11 8 3 20 23 24 23
21 4 14 6 24 18 16 13 16 24 9 1 7 8 25 11 21 12 25 19 12 11
6 15 23 7 19 17 4
2 16 16
7 14
49 14 11 3 1 6 6 3 11 14 3 4 14 2 7 13 7 1 3 5 10 7 11 7 3 10 9 1 6 4 4 10 2 12 12 2 4 2 2 12 1 4 1 12 4 5 10 10 6 11
47 13 3 8 5 3 1 12 4 7 13 5 2 14 14 11 13 3 12 1 12 10 2 10 7 5 1 1 1 4 11 10 2 11 2 4 14 2 13 1 8 12 5 7 11 2 2 10
12 13 10 14 7 9 10 11 14 10 11 12 11
34 7 12 2 8 13 1 8 12 1 13 7 3 6 3 4 7 10 6 3 3 6 9 12 13 4 11 6 14 6 2 5 12 11 4
28 9 4 11 4 2 9 10 4 12 11 5 2 6 11 5 9 14 11 4 12 14 12 3 12 3 2 14 14
34 3 1 6 4 11 8 5 4 3 8 13 11 10 1 3 6 5 9 3 13 10 14 11 7 14 8 9 1 5 6 10 7 7 14
32 1 7 14 4 7 5 3 4 14 3 4 4 5 12 6 1 7 4 11 11 3 4 5 2 8 10 11 12 14 10 7 1
4 15
50 4 5 15 8 14 7 14 12 2 13 8 13 15 9 4 8 10 7 10 3 14 15 6 4 9 4 13 12 6 9 3 1 5 10 8 3 8 13 14 10 2 7 14 1 7 2 8 1 15 9
45 6 9 8 9 9 11 6 12 8 6 14 9 11 8 8 5 1 13 11 10 14 2 15 15 15 8 14 1 8 8 2 5 8 9 13 1 4 10 12 4 8 10 4 3 3
28 14 10 15 9 4 14 2 10 5 2 2 3 2 1 2 3 12 9 4 1 9 7 11 12 2 3 14 5
41 8 8 2 2 7 11 12 5 12 6 1 13 14 4 6 7 5 1 3 6 4 4 6 2 6 3 4 15 1 8 3 15 15 4 1 14 14 12 3 11 2
9 12
5 5 8 4 4 6
48 1 6 10 1 4 3 1 10 5 2 1 2 10 1 11 7 2 4 9 3 8 2 7 7 2 3 6 6 10 11 3 3 4 4 3 8 10 7 9 6 8 1 7 9 6 5 3 7
49 3 1 7 4 11 2 5 5 7 2 3 6 4 5 1 11 11 12 8 5 9 1 4 1 7 12 6 4 6 5 3 8 5 10 3 8 3 7 12 1 1 2 6 8 10 11 7 12 10
49 8 10 7 3 11 1 2 8 8 11 12 11 6 9 8 8 4 10 7 3 10 7 9 8 2 10 10 12 2 7 2 9 5 8 12 7 12 5 6 8 4 6 10 1 6 5 1 9 6
39 3 7 5 11 6 10 1 3 10 2 2 3 10 10 2 1 4 5 10 9 4 5 6 1 5 11 9 9 11 6 7 2 1 11 4 10 1 4 5
46 5 6 4 7 7 5 11 10 9 8 10 1 12 8 1 9 10 2 9 9 7 4 2 11 6 5 9 6 9 5 11 1 10 2 7 4 10 6 5 7 5 6 11 9 5 3
29 3 4 5 3 11 8 4 9 6 8 9 11 4 1 10 9 2 3 7 9 1 4 5 11 9 11 1 9 3
0
16 9 11 9 11 1 9 2 1 2 10 2 4 5 2 5 1
6 22
25 10 12 15 15 18 13 11 2 7 5 12 19 14 6 16 2 12 6 8 3 3 1 12 16 19
48 7 22 16 2 15 4 13 7 16 6 18 4 7 2 6 16 19 19 22 10 21 9 13 4 11 15 4 20 6 20 15 12 19 8 13 11 9 1 16 2 6 11 3 10 10 9 4 4
44 3 13 21 11 3 2 20 15 3 17 21 1 9 8 17 15 21 4 1 19 17 1 3 3 1 12 12 9 13 16 12 15 4 8 2 5 8 21 17 10 15 13 8 22
16 3 14 17 4 12 13 20 10 15 22 11 3 9 19 15 22
12 6 2 12 5 6 19 3 20 4 15 11 12
1 9
8 21
12 20 4 8 4 21 12 13 19 2 15 13 7
19 11 13 16 13 1 9 4 12 19 8 15 10 9 16 10 18 10 5 14
15 11 15 10 1 6 6 21 20 18 6 7 7 17 20 20
17 5 21 6 1 7 20 10 13 12 18 9 21 20 20 12 9 13
10 7 16 4 6 13 21 10 19 4 5
6 2 19 20 21 1 18
36 18 7 17 9 1 2 8 20 1 18 6 11 14 10 6 17 14 18 14 2 13 15 6 7 15 1 4 14 21 21 17 15 4 10 21 2
41 8 20 12 2 4 20 13 13 4 6 5 19 19 4 11 12 7 15 5 6 16 16 5 14 12 19 15 19 17 17 9 1 15 18 2 16 17 14 7 20 19
5 22
4 21 2 22 3
31 8 2 17 15 5 1 4 18 19 10 15 6 18 2 16 22 16 18 19 9 19 13 22 22 22 13 18 1 11 20 1
21 21 15 6 1 15 10 19 9 17 9 15 12 9 8 9 2 4 3 11 20 16
32 19 15 19 12 14 7 10 14 22 8 6 5 9 18 12 3 4 4 11 16 14 19 2 22 19 3 3 5 20 16 12 16
30 8 3 21 12 12 10 11 18 13 14 2 6 1 4 8 5 12 1 16 7 22 15 1 2 15 5 21 8 16 12
5 6
47 6 1 4 6 2 5 2 5 2 6 5 5 5 3 1 5 6 1 1 3 3 4 5 3 3 5 4 2 2 3 4 5 4 6 4 5 4 4 1 6 1 5 2 5 2 2 1
42 2 1 1 2 3 6 4 5 2 6 4 3 2 2 1 3 5 5 1 2 6 1 5 6 6 1 4 5 2 2 5 2 3 4 1 3 3 5 5 2 2 2
0
36 1 4 4 5 6 4 5 5 3 3 4 6 3 5 4 3 1 2 4 1 5 4 3 5 6 5 6 5 6 3 6 5 5 1 3 2
1 1
2 5
12 2 5 2 2 4 3 1 3 1 2 3 3
2 2 2
8 11
39 2 9 9 9 5 1 2 10 9 4 4 10 5 8 2 8 5 10 9 2 2 1 10 8 8 9 3 11 9 9 11 10 6 8 6 8 8 7 6
0
0
48 2 11 4 3 7 6 10 4 7 11 2 5 6 7 11 8 7 8 3 4 4 6 1 7 2 6 2 6 9 10 2 10 7 3 11 2 8 9 3 1 7 3 3 1 9 2 6 2
39 7 6 8 1 4 4 3 7 3 8 5 10 7 1 5 9 11 4 3 7 7 3 2 9 5 11 4 4 5 6 10 11 11 4 1 1 7 1 7
18 6 11 6 1 10 11 7 9 3 9 4 7 9 3 2 2 2 6
40 5 11 1 4 8 4 2 8 9 11 3 5 5 1 10 3 10 9 9 5 10 6 7 5 3 9 7 2 11 10 4 4 9 4 5 5 6 5 10 3
13 10 5 7 10 3 9 6 10 7 11 6 10 6
3 11
19 3 10 11 1 3 3 9 4 8 11 9 1 7 9 2 6 2 8 2
9 6 8 10 10 5 4 6 8 2
49 8 3 2 8 3 2 10 10 5 4 7 1 2 3 9 4 6 9 9 7 9 1 1 7 8 3 8 3 10 9 3 5 9 4 1 1 3 8 8 8 1 3 8 2 3 3 3 8 9
2 5
41 3 4 3 4 1 4 3 2 3 5 5 3 3 4 4 5 4 2 5 2 3 1 2 2 2 3 3 4 4 5 2 3 3 4 1 5 5 5 2 4 5
47 3 2 2 4 1 2 5 3 5 4 5 1 1 1 3 3 5 3 4 1 3 3 1 5 3 2 5 1 5 4 3 5 2 1 3 4 2 4 1 3 3 1 4 3 1 3 2
4 20
7 4 13 4 10 19 6 6
20 6 18 8 19 17 14 19 9 8 18 17 18 20 16 10 10 13 8 3 4
2 5 10
38 9 14 4 7 11 1 20 17 18 7 7 6 13 17 6 20 14 15 9 6 10 19 7 3 18 9 18 16 5 20 10 13 5 5 20 15 6 11
9 14
3 11 13 3
3 6 6 5
42 7 2 12 11 5 14 2 1 5 9 14 6 11 10 4 3 13 13 14 11 3 1 14 14 11 2 9 2 8 13 14 12 13 9 8 3 8 9 1 10 3 14
42 11 8 5 14 4 1 11 1 2 11 14 13 5 13 7 7 4 5 4 1 3 12 8 3 3 14 4 12 1 1 13 11 8 2 8 12 14 5 12 1 13 9
10 4 7 3 10 11 8 11 9 8 8
36 11 10 14 12 5 14 12 4 9 4 3 2 13 14 4 8 1 3 2 11 6 6 14 13 14 5 9 9 10 14 9 4 7 6 1 11
10 11 12 10 14 14 11 10 12 1 3
46 1 4 6 4 9 3 2 9 7 8 1 3 5 7 4 11 12 5 7 13 13 5 8 10 2 3 5 13 1 7 8 13 8 12 2 14 14 1 6 5 8 6 7 12 12 8
19 8 12 12 4 10 14 10 5 14 12 7 10 10 11 4 8 4 1 9
6 16
44 1 16 10 13 14 9 10 10 16 5 5 3 5 9 5 4 5 2 15 6 5 12 6 8 5 6 2 5 1 12 9 1 11 2 13 9 10 7 2 9 11 6 11 15
34 15 2 3 16 16 8 5 11 13 12 15 2 14 3 2 9 11 3 3 12 15 11 5 5 12 13 16 2 8 14 15 6 16 1
41 15 8 10 10 5 5 8 6 2 11 8 10 5 10 13 1 8 7 5 13 3 2 12 4 9 9 2 14 8 3 3 7 10 12 16 14 1 7 4 2 1
27 12 6 4 8 6 11 14 10 7 16 11 2 3 3 11 5 1 2 7 3 8 16 15 7 14 15 14
35 16 14 11 11 3 14 2 8 8 16 2 15 15 12 16 2 15 10 6 15 12 12 1 3 11 15 10 8 13 7 8 13 4 2 7
50 15 9 14 7 8 15 5 6 11 4 7 9 14 12 7 9 7 7 11 2 6 4 9 2 10 1 14 14 2 5 4 1 13 1 7 4 16 11 9 10 14 16 2 11 11 8 3 2 14 14
``````
AC output:

Code: Select all

``````Case #1: 13
Case #2: 15
Case #3: 3
Case #4: 18
Case #5: 12
Case #6: 8
Case #7: 14
Case #8: 15
Case #9: 4
Case #10: 18
Case #11: 12
Case #12: 4
Case #13: 6
Case #14: 5
Case #15: 11
Case #16: 11
Case #17: 5
Case #18: 5
Case #19: 3
Case #20: 16
``````
Check input and AC output for thousands of problems on uDebug!

OmarEltobgy
New poster
Posts: 1
Joined: Sat Aug 24, 2013 2:08 pm

### Re: 10779 - Collector's Problem

Try this input:

Code: Select all

``````1
3 6
6 1 1 2 3 4 4
4 2 2 3 3
6 1 4 5 5 6 6
``````
``````Case #1: 6