All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
Moderator: Board moderators
emotional blind
A great helper
Posts: 383 Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:
Post
by emotional blind » Mon Sep 18, 2006 6:39 pm
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
mf
Guru
Posts: 1244 Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Post
by mf » Mon Sep 18, 2006 10:43 pm
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.
emotional blind
A great helper
Posts: 383 Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:
Post
by emotional blind » Wed Sep 20, 2006 7:46 am
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:
Post
by mf » Wed Sep 20, 2006 11:51 am
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:
mf
Guru
Posts: 1244 Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Post
by mf » Thu Sep 21, 2006 11:02 am
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
Location: Bangladesh
Contact:
Post
by emotional blind » Thu Sep 21, 2006 7:31 pm
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
Post
by kevinufo » Sat Jul 18, 2009 3:43 pm
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.
mf
Guru
Posts: 1244 Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Post
by mf » Wed Jul 22, 2009 10:44 pm
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
Post
by crip121 » Wed Sep 23, 2009 5:28 pm
never mind, i made a stupid mistake. ACed...
pratikjain1993
New poster
Posts: 2 Joined: Sun Mar 23, 2014 10:31 pm
Post
by pratikjain1993 » Mon Mar 24, 2014 10:39 pm
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...
brianfry713
Guru
Posts: 5947 Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA
Post
by brianfry713 » Tue Mar 25, 2014 12:38 am
Post your full code.
Check input and AC output for thousands of problems on
uDebug !
brianfry713
Guru
Posts: 5947 Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA
Post
by brianfry713 » Thu Mar 27, 2014 9:33 pm
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
Post
by OmarEltobgy » Sun Jul 13, 2014 2:34 pm
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: