P7060 [NWRRC2014]Alarm Clock

Alice likes her digital alarm clock. She sets them up every evening. Last night Alice had a dream about her clock. Unfortunately, the only thing she is able to remember is the number of highlighted segments of the clock. Alice wonders what time was set on the clock in her dream.

Alice's clock have four digits: two for hours and two for minutes. For example, the clock below shows 9:309:30 (note the leading zero).

The clock uses following digit representation.

输入格式

The only line of the input file contains single integer nn — the number of highlighted segments of the clock in Alice's dream (0 \le n \le 30)(0≤n≤30) .

输出格式

Output five characters in \text{hh:mm}hh:mm format — the time shown on the clock in Alice's dream. The time must be correct: 0 \le \text{hh} < 240≤hh<24 and 0 \le \text{mm} < 600≤mm<60 . If there are many possible correct times, output any of them. If there is none, output Impossible.

题意翻译

Alice梦见了一个时间，但她只记得了这个时间在电子钟上显现出来的段数，现在给出这个段数，让你反推Alice梦见的时间（若有多个答案，输出任意一个均可）
段数：想必大家都听说过用火柴拼数字的游戏，比如1要用两个火柴，2要用5根火柴，8要用7根火柴等等（如题目图片所示），这里的段数指的就是一个时间的每一个数字，需要火柴数量的和（比如09：30，就要6+6+5+6=23个火柴）。
时间：本题输出的时间仅有小时和分钟，其中小时在0到23之间，分钟在0到59之间

输入一个整数n，n在0到30以内，代表Alice梦见的段数
输出一个字符串，如果有合法的时间满足输入的段数，则输出这个时间（有多个输出任意一个均可），否则输出Impossible

注意时间的前导零

 思路

计算分钟的全部种类所需的火柴数，相同火柴数只存放一种组合，小时同理，把分钟和小时的不同火柴数分别存放不同数组：分钟组和小时组。小时组和分钟组组合判断是否存在一种组合使小时组某一种所需的火彩数+分钟组某一种所需火柴数=所输入的火柴数。

代码

 1 #include <stdio.h>
 2 int a[10]={6,2,5,5,4,5,6,3,7,6};  //0——9所需要的火柴数
 3 int b[15][2]={0};                 //存放分钟组
 4 int c[15][2]={0};                 //存放小时组
 5 int main(){
 6     int m[20]={0},n[20]={0};
 7     int m1=0,n1=0; 
 8     int i,j;
 9     int f=0;
10     int num;
11     for(i=0;i<6;i++){
12         for(j=0;j<10;j++){
13             b[a[i]+a[j]][0]=i;
14             b[a[i]+a[j]][1]=j;
15             m[a[i]+a[j]]=a[i]+a[j];
16         }
17     }
18     for(i=0;i<2;i++){
19         for(j=0;j<10;j++){
20             c[a[i]+a[j]][0]=i;
21             c[a[i]+a[j]][1]=j;
22             n[a[i]+a[j]]=a[i]+a[j];    
23         }
24     }
25     for(i=0;i<4;i++){             //因为2和4组合所需的火柴数已存在不计算；
26         c[a[2]+a[i]][0]=2;
27         c[a[2]+a[i]][1]=i;
28         n[a[2]+a[i]]=a[i]+a[2];
29     }
30     for(i=0;i<20;i++){             //除去分钟组可能的火柴数数组的空白
31         if(m[i]!=0)continue;
32         for(j=i+1;j<20;j++){
33             if(m[j]!=0&&m[i-1]!=m[j]){
34                 m[i]=m[j];
35                 m[j]=0;
36                 m1++;
37                 break;
38             }
39         }
40     }
41     for(i=0;i<20;i++){           //除去小时组可能的火柴数数组的空白
42         if(n[i]!=0)continue;
43         for(j=i+1;j<20;j++){
44             if(n[j]!=0&&n[i-1]!=n[j]){
45                 n[i]=n[j];
46                 n[j]=0;
47                 n1++;
48                 break;
49             }
50         }
51     }
52     scanf("%d",&num);
53     for(i=0;i<n1;i++){                       //判断是否存在一种组合
54         for(j=0;j<m1;j++){
55             if(n[i]+m[j]==num){
56                 f=1;
57                 break;
58             }
59         }
60         if(f==1)break;
61     }
62     if(f==1){
63         printf("%d%d",c[n[i]][0],c[n[i]][1]);
64         printf(":");
65         printf("%d%d",b[m[j]][0],b[m[j]][1]);
66     }else printf("Impossible");
67     
68     return 0;
69 }