I don't know, what is the maximum possible sum of digits, but in these tests it is 31.
Simple, badly optimized, recursion passes quickly.

I solved it with next algo:
I bruteforce all possible connections (if graph consists of several not connected parts) and then add some edges for Euler path with greedy.

Of course its right algo, but some complicated (i think).
Does anyone knows more simple one?

INPUT:
5
2 2
3 3
4 4
5 5
6 6

OUTPUT:
29
4
2 3
2 4
3 5
4 6

Edited by author 01.08.2008 18:10

I only use bruteforce and I constantly get WA at first easy
tests (execution time is 0.01).
All the test I was able to imagine passed OK with no
corrections to the code...

I assume dominoe graph is ok when 1) there are no more than
two 'even' verteces AND 2) the graph is connected.

in main() I call func(0)
where func(int) is (simplified)

void func(int p) {
    if(p==6) return;
    if(ok()) save_this();
    for(i=1;i<=6;i++)for(j=i;j<=6;j++) {
        place_dominoe(i,j);
        func(p+1);
        remove_dominoe(i,j);
    }
}

In fact, this problem is easy, don't be frighten by the low AC ratio...

When I read the description of this problem, I immediately thought it as a Euler Path problem.

I try to add some edges so that will form a Euler Path.

First, I add edges according to greedy strategy,but soon I learnt it was wrong, a simple calc proved it won't work.

As far as I know, there isn't exist a greedy algo...
(It you used it got AC, email me: yyming@hotmail.com )

In spite of this, my pro runs quickly, it got AC in 0.015 sec :)
http://acm.timus.ru/status.aspx?space=1&pos=865497

830701 17:26:25
22 Apr 2005 Fu Dong 1063 Pascal Accepted
 0.015 149 KB

First, I connected all the blocks , then I used DFS to make a Eular_Graph and find the minimal cost.

I know this problem is a famous problem, maybe it is called "China post road problem", who can tell me the best solution to this problem.

I'm sorry, my English is so poor.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

short a[10000];
short sets[10000];
short p[10000];

int main()
{
  long i,n;
//  freopen("input.txt","rt",stdin);
//  freopen("output.txt","wt",stdout);

  while (scanf("%ld",&n)==1)
  {
  if (n==1) { printf("1\n"); continue; }
    long k,j,sum;
    sum=0;

    memset(a,0,sizeof(a));
    memset(sets,0,sizeof(sets));

    for (i=0; i<n; i++)
    {
      scanf("%ld",&k);
      for(j=2; j<=k; j++) a[j]--;
      sets[k]++;
      sum+=k;
    }
    for(j=2; j<=sum; j++) a[j]++;
    for(i=1; i<=sum; i++)
      for(j=2; j<=sets[i]; j++) a[j]--;

    memset(p,0,sizeof(p));
    unsigned long result=1;
    for(i=2; i<=sum; i++)
    if(!p[i])
    {
      j=i+i;
      while (j<=sum)
    { p[j]=1;
      k=j;
      while(k%i==0) {
        k/=i;
        a[i]+=a[j];
      }
      j+=i;
    }

      for(j=a[i]; j>=1; j--) result*=i;
    }
    printf("%lu\n",result);
  }

  exit(0);
  return 0;
}

If you got WA,try these tests...
3
1 1
1 1
1 1
Answer:
0
0
-----------
2
1 1
2 2
Answer:
3
1
1 2