Page 1 of 2
10779 - Collectors Problem
Posted: Mon Sep 18, 2006 6:39 pm
by emotional blind
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 ?
I am getting
Wrong Answer
Posted: Mon Sep 18, 2006 10:43 pm
by mf
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:
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.
Posted: Wed Sep 20, 2006 7:46 am
by emotional blind
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.
Posted: Wed Sep 20, 2006 11:51 am
by mf
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:
Posted: Wed Sep 20, 2006 6:13 pm
by emotional blind
mf: I have sent you my code
Posted: Thu Sep 21, 2006 11:02 am
by mf
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
Posted: Thu Sep 21, 2006 7:31 pm
by emotional blind
Thanks a Lot mf.
I got ACCEPTED at last.
Your input/output helped me a lot.
Posted: Sat Jul 18, 2009 3:43 pm
by kevinufo
Could anyone provide some hints about this problem?
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.
Thanks in advance.
Re: 10779 - Collector's Problem
Posted: Wed Jul 22, 2009 10:44 pm
by mf
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.
Re: 10779 - Collector's Problem
Posted: Wed Sep 23, 2009 5:28 pm
by crip121
never mind, i made a stupid mistake. ACed...
Re: 10779 - Collector's Problem
Posted: Mon Mar 24, 2014 10:39 pm
by pratikjain1993
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;
adj[sink].push_back(src);
}
FOR(j,1,m)
{
nodes++;
if(mp[i].count(j))
{
if(mp[i][j]==1)
continue;
out.pb(make_pair(nodes,j));
adj[src].push_back(nodes);
cap[src][nodes] = mp[i][j]-1;
}
else
{
in.pb(make_pair(nodes,j));
adj[nodes].push_back(sink);
cap[nodes][sink]=1;
}
}
}
FORL(i,0,out.size())
{
FORL(j,0,in.size())
{
if(out[i].second==in[j].second)
{
adj[out[i].first].push_back(in[j].first);
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)
{
adj[i].clear();
}
}
}
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...
Re: 10779 - Collector's Problem
Posted: Tue Mar 25, 2014 12:38 am
by brianfry713
Post your full code.
Re: 10779 - Collector's Problem
Posted: Thu Mar 27, 2014 4:00 pm
by pratikjain1993
Re: 10779 - Collector's Problem
Posted: Thu Mar 27, 2014 9:33 pm
by brianfry713
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
Re: 10779 - Collector's Problem
Posted: Sun Jul 13, 2014 2:34 pm
by OmarEltobgy
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
The answer should be: