Older files and necklace

3 files changed, 186 insertions, 0 deletions

diff --git a/10054/in b/10054/in
new file mode 100644
index 0000000..198a39d
--- /dev/null
+++ b/10054/in
@@ -0,0 +1,75 @@
+4
+5
+1 2
+2 1
+3 4
+4 5
+5 3
+5
+1 2
+2 3
+3 4
+4 5
+5 6
+55
+1 40
+20 15
+27 16
+1 22
+28 24
+6 49
+16 9
+14 10
+46 25
+40 12
+25 37
+40 24
+36 1
+18 24
+20 5
+9 12
+24 35
+10 19
+46 15
+23 8
+16 20
+18 1
+12 32
+44 30
+9 35
+19 24
+16 12
+22 27
+40 23
+1 20
+15 1
+31 22
+40 47
+44 40
+30 46
+18 10
+32 37
+30 25
+37 40
+1 7
+31 22
+27 27
+8 27
+18 1
+46 6
+40 24
+40 37
+47 5
+10 8
+9 49
+27 15
+40 14
+36 25
+7 30
+8 28
+5
+2 1
+2 2
+3 4
+3 1
+2 4
diff --git a/10054/necklace.bin b/10054/necklace.bin
new file mode 100755
index 0000000..ff9a051
--- /dev/null
+++ b/10054/necklace.bin
diff --git a/10054/necklace.c b/10054/necklace.c
new file mode 100644
index 0000000..f1d1e93
--- /dev/null
+++ b/10054/necklace.c
@@ -0,0 +1,111 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+
+#define NUM_COLORS 50
+
+typedef struct {
+    int c1, c2;
+} bead;
+
+bead *path;
+int adj[NUM_COLORS][NUM_COLORS] = {{0}};
+int path_counter = 0;
+
+int find_path(int x, int y, int curr)
+{
+    bead new_bead = {x, y};    
+    path[path_counter++] = new_bead;
+    adj[x][y]-=1;
+    adj[y][x]-=1;
+    int new_x, new_y;
+    int found = 0;
+    switch (curr) {
+    case 0:
+	for (int i=0; i<NUM_COLORS && !found; i++) {
+	    if (adj[x][i] >= 1) {
+		new_x = x; new_y = i;
+		found = 1;
+	    }
+	}
+	break;
+    case 1:
+	for (int i=0; i<NUM_COLORS && !found; i++) {
+	    if (adj[i][y] >= 1) {
+		new_x = i; new_y = y;
+		found = 1;
+	    }
+	}
+    }
+    if (found==0)
+	return 0;
+    curr = (curr+1)%2;
+    find_path(new_x, new_y, curr);
+    return 1;
+}
+
+int main()
+{
+    int tc, curr_tc = 0;
+    scanf("%d", &tc);
+    for (; curr_tc < tc; curr_tc++) {
+	int num_beads;
+	int start_x, start_y;
+	int color_count[50] = {0}, repeated_count[50] = {0};
+	
+	scanf("%d", &num_beads);	
+	path = malloc(sizeof(bead)*num_beads);
+	
+	int a, b;	
+	for (int x = 0; x < num_beads; x++) {
+	    scanf("%d %d", &a, &b);
+	    adj[a-1][b-1] += 1;
+	    adj[b-1][a-1] += 1;
+	    
+	    color_count[a-1] += 1;
+	    color_count[b-1] += 1;
+	    if (a == b) {
+		repeated_count[a-1] += 2;
+	    }	    
+	    if (x == 0) {
+		start_x = a-1;
+		start_y = b-1;
+	    }
+	}
+	int possible = 1;
+	for (int x = 0; x < NUM_COLORS; x++) {
+	    if (color_count[x] % 2 != 0) {
+		possible = 0;
+		break;
+	    }
+	    if (repeated_count[x] > 0 && color_count[x] < repeated_count[x]+2) {
+		possible = 0;
+		break;
+	    }
+	}
+	printf("Case #%d\n", curr_tc+1);
+	if (!possible) {
+	    printf("some beads may be lost\n");
+	}
+	else {
+	    path_counter = 0;
+	    int k=find_path(start_x, start_y, 0);
+	    /* printf("find_path: %d\n", k); */
+	    for (int x = 0; x < path_counter; x++) {
+		if (x%2 != 0)
+		    printf("%d %d\n", path[x].c1+1, path[x].c2+1);
+		else
+		    printf("%d %d\n", path[x].c2+1, path[x].c1+1);
+	    }
+	}
+	
+	printf("\n");	
+	for (int x=0; x < NUM_COLORS; x++) {
+	    for (int y=0; y < NUM_COLORS; y++) {
+		adj[x][y] = 0;
+		adj[y][x] = 0;
+	    }
+	}
+	free(path);
+    }
+}