/home/toolbox/public_html/solutions/114/11414/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 #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 1002
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()
52 {
53 /* FUNCTION dump */
54 int i;
55
56 for (i=0; cnt>i; i++)
57 {
58 /* for i */
59 printf("%d ", paths[i]);
60 } /* for i */
61 printf("\n");
62 } /* FUNCTION dump */
63
64 int compare(const void *a, const void *b)
65 {
66 /* FUNCTION compare */
67 return ( *(int*)b - *(int*)a );
68 } /* FUNCTION compare */
69
70 void getInput()
71 {
72 /* FUNCTION getInput */
73 int i;
74
75 scanf(" %d ", &cnt);
76 for (i=0; cnt>i; i++)
77 {
78 /* for i */
79 scanf(" %d ", &paths[i]);
80 } /* for i */
81 qsort(paths, cnt, sizeof(int), compare);
82 } /* FUNCTION getInput */
83
84 int reduce()
85 {
86 /* FUNCTION reduce */
87 int first = 0;
88 int valid = TRUE;
89 int i;
90 int tmp;
91
92 while ((valid) && ((cnt - first) > 0))
93 {
94 /* while */
95 tmp = paths[first];
96 /* make sure remaining list as enough members to subtract 1 from */
97 valid = (cnt - first) >= tmp;
98 if (valid)
99 {
100 /* do subtract */
101 first++;
102 for (i=first; tmp>=i; i++)
103 {
104 /* for i */
105 paths[i] = paths[i] - 1;
106 valid = (valid) && (paths[i] >= 0);
107 } /* for i */
108 } /* do subtract */
109 /* drop trailing zeroes */
110 if (valid)
111 {
112 while ((0 < cnt) && (0 == paths[cnt]))
113 {
114 cnt --;
115 }
116 }
117 } /* while */
118 return valid;
119 } /* FUNCTION reduce */
120
121 void process()
122 {
123 /* FUNCTION process */
124 /* steps:
125 * make sure sum of elements is even
126 * reduce list
127 */
128
129 int sum = 0;
130 int i;
131
132 if (0 == cnt)
133 {
134 /* it worked */
135 printf("Yes\n");
136 } /* it worked */
137 else
138 {
139 /* actually have something in array */
140 for (i=0; cnt>i; i++)
141 {
142 sum = sum + paths[i];
143 }
144 if (0 != (sum % 2))
145 {
146 /* fail */
147 printf("No\n");
148 } /* fail */
149 else
150 {
151 /* even sum, so now reduce the list */
152 if (reduce())
153 {
154 /* it worked */
155 printf("Yes\n");
156 } /* it worked */
157 else
158 {
159 /* fail */
160 printf("No\n");
161 } /* fail */
162 } /* even sum, so now reduce the list */
163 } /* actually have something in array */
164 } /* FUNCTION process */
165
166 int main()
167 {
168 /* main */
169 int i;
170
171 init();
172 for (i=0; i<numberOfTimes; i++)
173 {
174 /* while */
175 getInput();
176 process();
177 } /* while */
178
179 return EXIT_SUCCESS;
180 } /* main */
181
182