/home/toolbox/public_html/solutions/103/10364/b.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdlib.h>
7 #include <math.h>
8 #include <stdint.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (TRUE)
14
15 /* fprintf(stderr, "functionName: message", varslist); */
16
17 /*
18 * Author: Isaac Traxler
19 * Date: 2018-09-12
20 * Purpose: fun
21 * Problem: 10364
22 */
23
24 /*
25 * This template reads data a specified number of times.
26 */
27
28 #define MAX_STICKS 25
29
30 int numberOfTimes;
31 int sticks[MAX_STICKS];
32 int stickCnt;
33 int perimeter;
34
35
36 void init()
37 {
38 /* FUNCTION init */
39 scanf("%d ", &numberOfTimes);
40 } /* FUNCTION init */
41
42 void dump()
43 {
44 /* FUNCTION dump */
45 } /* FUNCTION dump */
46
47 void getInput()
48 {
49 /* FUNCTION getInput */
50 int i;
51
52 perimeter = 0;
53 scanf(" %d ", &stickCnt);
54 for (i=0; i<stickCnt; i++)
55 {
56 /* read in lenght of each stick */
57 scanf(" %d ", &sticks[i]);
58 perimeter = perimeter + sticks[i];
59 } /* read in lenght of each stick */
60 } /* FUNCTION getInput */
61
62 int intcomp(const void *a, const void *b)
63 {
64 /* FUNCTION intcomp */
65 return ( *(int*)b - *(int*)a );
66 } /* FUNCTION intcomp */
67
68 int solvable(int goal, int idx)
69 {
70 /* FUNCTION solvable */
71 int toReturn;
72
73 DEBUG printf("goal = %d sticks[%d] = %d\n", goal, idx, sticks[idx]);
74 if (idx >= stickCnt)
75 {
76 /* if out of sticks */
77 toReturn = FALSE;
78 } /* if out of sticks */
79 else if (goal == sticks[idx])
80 {
81 /* goal found */
82 toReturn = TRUE;
83 sticks[idx] = 0;
84 } /* goal found */
85 else
86 {
87 /* not there yet -- keep trying */
88 if (sticks[idx] > goal)
89 {
90 /* number to big -- ignore */
91 toReturn = solvable(goal, (idx + 1));
92 } /* number to big -- ignore */
93 else
94 {
95 /* number get me closer -- use it */
96 toReturn = solvable((goal - sticks[idx]), (idx + 1));
97 if (toReturn)
98 {
99 /* valid solution -- so consume idx stick */
100 sticks[idx] = 0;
101 } /* valid solution -- so consume idx stick */
102 } /* number get me closer -- use it */
103 } /* not there yet -- keep trying */
104 return toReturn;
105 } /* FUNCTION solvable */
106
107 int possible(int goal)
108 {
109 /* FUNCTION possible */
110 int i;
111 int success = TRUE;
112
113 for (i=0; ((success) && (4>i)); i++)
114 {
115 /* do each side */
116 DEBUG printf("Side %d\n", i);
117 success = solvable(goal, 0);
118 } /* do each side */
119 return success;
120 } /* FUNCTION possible */
121
122 void process()
123 {
124 /* FUNCTION process */
125 int goal;
126
127 goal = perimeter / 4;
128
129 if ((4 * goal) != perimeter)
130 {
131 /* sum is not a multiple of 4 -- impossible! */
132 printf("no\n");
133 } /* sum is not a multiple of 4 -- impossible! */
134 else
135 {
136 /* make sure that longest stick is not bigger than a side */
137 qsort(&sticks[0], stickCnt, sizeof(int), intcomp);
138 if (goal < sticks[0])
139 {
140 /* longest stick is longer than a side */
141 printf("no\n");
142 } /* longest stick is longer than a side */
143 else
144 {
145 /* not just try it */
146 if (possible(goal))
147 {
148 /* is possible */
149 printf("yes\n");
150 } /* is possible */
151 else
152 {
153 /* is not possible */
154 printf("no\n");
155 } /* is not possible */
156 } /* not just try it */
157 } /* make sure that longest stick is not bigger than a side */
158 } /* FUNCTION process */
159
160 int main()
161 {
162 /* main */
163 int i;
164
165 init();
166 for (i=0; i<numberOfTimes; i++)
167 {
168 /* while */
169 getInput();
170 process();
171 } /* while */
172
173 return EXIT_SUCCESS;
174 } /* main */
175
176