Show all threads Hide all threads Show all messages Hide all messages | The maximum sum of digits | Igor Parfenov | 1063. Domino Puzzle | 27 Aug 2022 00:49 | 1 | 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. | How to solve it fast and cool? | Laise | 1063. Domino Puzzle | 22 Dec 2016 13:27 | 2 | 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? Only use buffered i/o )). | Some tests | Denis Koshman | 1063. Domino Puzzle | 1 Aug 2008 17:57 | 2 | 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 INPUT: 3 1 2 4 5 6 6 OUTPUT: 13 2 1 4 2 6 Edited by author 01.08.2008 18:11 | please give a hint! | Ilya Semenov (NSU) | 1063. Domino Puzzle | 1 Aug 2008 15:30 | 4 | 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); } } > 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); > } > } > if the graph is connected and two odd(!) or no odd vertices, so the graph is Euler one. The graph should be connected only with regard to non-isolated nodes. | An easy task,and an easy WA task... | Yu Yuanming | 1063. Domino Puzzle | 1 Aug 2008 15:28 | 2 | 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=865497The algo is greedy once you connect all components | I got Accepted, but who can tell me the best solution. | Fu Dong | 1063. Domino Puzzle | 1 Aug 2008 15:28 | 7 | 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. I think we could get a better answer through greed,the algorithm will be very fast then. But ... I got wa , I didn't know why. It is not called "China post road problem". In that problem road can't be add, you can use Eular Road to solve that problem, and I think you can also use it in this problem. 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. In China post road problem net is given but here we are to build best euler net. I think that correct solution uses some sort of full search and belong to NP-problems. Thus main question- Are the problen of NP type. ASK FOR SOLUTION: cpp_student@163.com THX!:) Once you connect all components, you don't need to find an Euler cycle, just pick all odd-degree nodes sequentially, except for the last two (sorted ascendingly). Anyway, the search for cheapest connection plan is recursive. | What wrong with this solution??? | <P><P><P> | 1063. Domino Puzzle | 6 Jun 2008 13:01 | 7 | #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; } You've made a terrible mistake. What does it mean "sum+=k"? IS NOT A PASCAL STYLE! Use "sum=sum+k"! Crazy Lemming you are not very informed with C and C++! It can be done in the way you say and in the way he made it! In c++ and in C(as i suppose) sum+=k adds k to sum! In pascal can be different but in C or C++ it isn't! Edited by author 06.06.2008 13:04 Edited by author 06.06.2008 13:04 | The tests are........ | Sean38 | 1063. Domino Puzzle | 15 Dec 2007 06:20 | 1 | 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 | Where is problem 1063, send the problem here if you get AC. | Practise makes Perfect | 1063. Domino Puzzle | 9 Mar 2003 06:36 | 1 | | admin,where can I see the problem? | Lin | 1063. Domino Puzzle | 6 Mar 2003 17:02 | 3 | | I found the most simple way to do this problem:for each test case,just output two lines each line contain only a number "0".Then you'll get accepted. | Huang Yizheng | 1063. Domino Puzzle | 15 Nov 2001 00:59 | 3 | | Haha...Is it a fault of the online judge system? | Huang Yizheng | 1063. Domino Puzzle | 9 Nov 2001 12:10 | 1 | |
|
|