/home/toolbox/public_html/solutions/114/11414/a.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 #include <ctype.h>
10
11 #define TRUE (1 == 1)
12 #define FALSE (1 != 1)
13
14 #define DEBUG if (FALSE)
15
16 /* fprintf(stderr, "functionName: message", varslist); */
17
18 /*
19 * Author: Isaac Traxler
20 * Date: 2022-10-05
21 * Purpose: fun
22 * Problem: 11414
23 */
24
25 /*
26 * This template reads data a specified number of times.
27 */
28
29 /* I accidentally submited 11417 as 11414 and got a wrong answer
30 * for 11414 (naturally). SO now I am trying to solve 11414 to
31 * get it off myunsolved list
32 */
33
34 /* This appears to be
35 * Graph Realization Problem
36 * that can be solved by the Erdős–Gallai theorem
37 */
38
39 #define MAX_PATHS 1012
40
41 int numberOfTimes;
42 int paths[MAX_PATHS];
43 int cnt;
44
45 void init()
46 {
47 /* FUNCTION init */
48 scanf("%d ", &numberOfTimes);
49 } /* FUNCTION init */
50
51 void dump(int start)
52 {
53 /* FUNCTION dump */
54 int i;
55
56 printf("dump (%d): ", cnt - start);
57 for (i=start; cnt>i; i++)
58 {
59 /* for i */
60 printf("%d ", paths[i]);
61 } /* for i */
62 printf("\n");
63 } /* FUNCTION dump */
64
65 int compare(const void *a, const void *b)
66 {
67 /* FUNCTION compare */
68 return ( *(int*)b - *(int*)a );
69 } /* FUNCTION compare */
70
71 void getInput()
72 {
73 /* FUNCTION getInput */
74 int i;
75
76 scanf(" %d ", &cnt);
77 for (i=0; cnt>i; i++)
78 {
79 /* for i */
80 scanf(" %d ", &paths[i]);
81 } /* for i */
82 qsort(paths, cnt, sizeof(int), compare);
83 } /* FUNCTION getInput */
84
85 int reduce()
86 {
87 /* FUNCTION reduce */
88 int first = 0;
89 int valid = TRUE;
90 int i;
91 int tmp;
92
93 DEBUG dump(0);
94 while ((valid) && ((cnt - first) > 0))
95 {
96 /* while */
97 qsort(&paths[first], (cnt-first), sizeof(int), compare);
98 printf("(first %d) (cnt %d)\n", first, cnt);
99 dump(first);
100 tmp = paths[first];
101 /* make sure remaining list as enough members to subtract 1 from */
102 first++;
103 valid = (cnt - first) >= tmp;
104 if (valid)
105 {
106 /* do subtract */
107 for (i=first; tmp>=i; i++)
108 {
109 /* for i */
110 paths[i] = paths[i] - 1;
111 valid = (valid) && (paths[i] >= 0);
112 } /* for i */
113 } /* do subtract */
114 /* drop trailing zeroes */
115 if (valid)
116 {
117 while ((0 < cnt) && (0 == paths[cnt-1]))
118 {
119 cnt --;
120 }
121 }
122 } /* while */
123 return valid;
124 } /* FUNCTION reduce */
125
126 void process()
127 {
128 /* FUNCTION process */
129 /* steps:
130 * make sure sum of elements is even
131 * reduce list
132 */
133
134 int sum = 0;
135 int i;
136
137 if (0 == cnt)
138 {
139 /* it worked */
140 printf("Yes\n");
141 } /* it worked */
142 else
143 {
144 /* actually have something in array */
145 for (i=0; cnt>i; i++)
146 {
147 sum = sum + paths[i];
148 }
149 if (0 != (sum % 2))
150 {
151 /* fail */
152 printf("No\n");
153 } /* fail */
154 else
155 {
156 /* even sum, so now reduce the list */
157 if (reduce())
158 {
159 /* it worked */
160 printf("Yes\n");
161 } /* it worked */
162 else
163 {
164 /* fail */
165 printf("No\n");
166 } /* fail */
167 } /* even sum, so now reduce the list */
168 } /* actually have something in array */
169 } /* FUNCTION process */
170
171 int main()
172 {
173 /* main */
174 int i;
175
176 init();
177 for (i=0; i<numberOfTimes; i++)
178 {
179 /* while */
180 getInput();
181 process();
182 } /* while */
183
184 return EXIT_SUCCESS;
185 } /* main */
186
187