Older files and necklace

13 files changed, 819 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);
+    }
+}
diff --git a/10954/addall.py b/10954/addall.py
new file mode 100644
index 0000000..bb45348
--- /dev/null
+++ b/10954/addall.py
@@ -0,0 +1,16 @@
+import sys
+
+while True:
+    line=sys.stdin.readline()
+    line=sys.stdin.readline()
+    lineint=[int(i) for i in line.rstrip().split(" ")]
+    curr_sum=lineint[0]
+    cost=0
+    for x in range(1, len(lineint)):
+        curr_sum+=lineint[x]
+        cost+=curr_sum
+    print(cost)
+    print(curr_sum)
+    print(sorted(lineint))
+    break
+    
diff --git a/10954/in b/10954/in
new file mode 100644
index 0000000..7ca45da
--- /dev/null
+++ b/10954/in
@@ -0,0 +1,9 @@
+17
+7 6 60 70 78 44 86 21 7 11 33 44 93 87 68 72 92 
+2
+56 91
+0
+
+	   1	2	3	4
+curr sum   1	3	6	10
+cost	   0	3	9	19
diff --git a/11926/in b/11926/in
new file mode 100644
index 0000000..649ac36
--- /dev/null
+++ b/11926/in
@@ -0,0 +1,469 @@
+1 2
+79605 256359
+923378 995289 927224
+964536 994182 357264
+4 0
+528005 562991
+202299 862624
+65954 431983
+820798 869954
+4 0
+422364 761696
+952672 954943
+994775 998813
+637936 776903
+4 3
+774481 834708
+297270 601398
+139492 288558
+180892 996530
+98789 116978 650329
+626794 951884 370642
+458628 781292 573184
+2 0
+587791 884830
+63208 439380
+1 1
+668363 691124
+359157 540314 687586
+1 1
+281785 639064
+828058 986855 187203
+2 3
+285254 360489
+758483 978839
+989819 991983 890487
+768786 939504 687936
+928130 955296 610345
+4 1
+519777 680468
+631096 980779
+108713 416252
+897669 977731
+80016 878096 701047
+4 2
+887459 905001
+710144 930003
+230827 605905
+603261 702038
+115476 372402 509626
+335330 675107 955781
+3 3
+982895 999124
+344917 403033
+255302 294245
+841165 998276 972055
+578884 848772 152585
+279877 389495 788989
+2 0
+17386 775089
+933557 986346
+3 4
+119987 366140
+699131 917366
+726279 750120
+598291 864260 156037
+222497 337395 888601
+477800 560740 729975
+201417 584745 827108
+3 3
+624458 806829
+437047 852865
+493485 620604
+687340 846469 459998
+186147 456505 97490
+214389 269646 554066
+4 2
+669539 948597
+681642 790523
+980918 990614
+369836 583217
+816375 915941 485967
+160955 455803 134935
+1 4
+570785 742112
+453043 749111 820642
+398583 759264 525240
+53823 496490 741163
+408194 946978 717604
+1 3
+764330 973676
+251415 393656 741385
+139750 471028 76092
+229503 958221 237906
+0 3
+540811 647196 479077
+155016 480358 23711
+975062 989184 544695
+3 4
+162315 978066
+671505 849162
+992577 995585
+693035 834097 778957
+462950 507458 520341
+602700 977872 596432
+832203 893719 350689
+3 1
+891373 950705
+396770 767834
+362274 421329
+539949 773640 483065
+2 3
+162368 503452
+506577 579729
+863607 898963 709376
+620513 804773 172449
+159663 311243 291766
+2 3
+123909 267015
+911430 986479
+915495 987254 944111
+830765 901196 306385
+768596 774223 877245
+0 4
+193391 850559 374357
+699968 951920 238060
+849802 870850 377036
+777786 982532 537932
+0 1
+5353 319104 794949
+3 0
+667635 944985
+537088 731685
+267681 755971
+1 3
+849415 923889
+804925 948399 24165
+254440 518086 242360
+199979 653134 609699
+1 1
+387240 467092
+913229 943522 903536
+4 1
+697707 715988
+169375 273086
+876921 904624
+494259 838971
+129740 237981 182783
+4 4
+504301 784385
+817217 829335
+613024 960434
+477219 944738
+186324 469739 472921
+573564 606155 387425
+222794 943093 824312
+176382 378279 781079
+2 2
+657928 696194
+133763 366432
+737459 903798 502262
+235112 977576 8329
+4 1
+801945 976027
+769114 859335
+311657 977040
+164955 272411
+47500 271385 689504
+3 0
+28778 520234
+578048 697771
+347932 818451
+2 1
+351315 513589
+693110 699547
+290645 925945 343885
+2 3
+54582 204722
+748279 771133
+414956 871140 299650
+579911 617949 865041
+899837 983804 170976
+3 4
+654601 848683
+444123 952780
+554819 683483
+476682 711198 219411
+688291 883253 510498
+135012 175547 326265
+185250 244986 944174
+1 0
+875818 973411
+2 0
+429749 433071
+355564 606701
+2 3
+632647 633447
+452051 840715
+160382 538240 25999
+155564 597572 245409
+362354 649313 755906
+3 3
+597966 669653
+317098 847184
+653144 846305
+934645 974793 883446
+390372 993648 696920
+264436 821984 165017
+3 2
+320780 529320
+895078 901677
+393638 783989
+636726 955220 684055
+517580 735996 439960
+4 1
+554720 996941
+566416 921354
+906204 990251
+548191 612692
+900429 950176 260677
+1 2
+925826 997425
+137716 727301 601093
+5984 877825 599792
+3 2
+754202 782066
+762248 844952
+430348 591022
+805227 867645 274755
+539787 600933 888633
+3 0
+435458 534999
+682584 736683
+368460 535842
+1 0
+76724 737846
+0 1
+794717 918511 795488
+4 0
+66216 145094
+73764 76001
+886449 980865
+143224 667777
+1 3
+330694 331226
+165999 425436 427718
+275796 644150 838796
+644256 909422 489619
+4 2
+276977 322507
+383384 892073
+728585 752079
+784533 962212
+761616 899590 115658
+618113 835428 426250
+1 0
+10115 476340
+3 0
+165844 190168
+945577 979615
+969168 972081
+1 0
+789550 980875
+0 1
+593891 824296 658597
+1 2
+959752 990357
+629032 730298 515195
+247144 629577 457796
+1 2
+985684 992049
+155542 768411 693799
+847778 916930 136445
+0 2
+738703 798369 541915
+318636 501572 127342
+3 3
+301724 417979
+726300 951689
+671575 765483
+461860 758503 639884
+826323 836468 168455
+920979 953574 212151
+4 3
+904446 922638
+583441 857385
+815241 881844
+814455 867860
+876850 964876 439484
+521854 957134 816080
+823578 930542 60237
+4 3
+933353 998893
+248202 926153
+891736 924463
+257779 333383
+73548 753206 446084
+724863 804093 924908
+826803 861559 740548
+1 2
+490243 934924
+952798 953907 80623
+35413 452150 904883
+4 2
+506506 589699
+290676 423894
+701419 754018
+982153 987356
+639781 903515 220824
+627836 824250 946921
+0 2
+290915 659129 460885
+453088 513249 468291
+3 2
+914222 975440
+815008 931462
+29936 641237
+532350 725542 696525
+823026 953852 915780
+3 1
+543872 747929
+477876 576652
+509643 596972
+228735 742802 994649
+2 0
+970498 982445
+900866 955461
+3 2
+871359 881448
+532467 639786
+695766 965620
+615733 649525 471774
+957258 970273 903906
+1 0
+965794 993954
+2 0
+72233 857263
+477650 814763
+1 3
+213280 240331
+7037 800354 769779
+545883 714404 641486
+693213 963864 724047
+1 3
+339131 646553
+645326 721068 592506
+548748 718758 653326
+514542 945007 709381
+1 0
+38694 298886
+1 2
+275406 490440
+209736 759819 635138
+978394 991700 985093
+1 2
+866811 956588
+947516 998910 719397
+642699 764144 534241
+3 3
+28499 79304
+269498 632260
+113038 959289
+217259 772716 311359
+486968 875848 586842
+969958 989518 870070
+2 4
+697235 917342
+911987 967307
+492139 657694 721803
+534522 735188 364796
+222230 916968 600294
+977187 984086 521822
+1 0
+634236 960623
+0 2
+109198 984734 891501
+695665 725966 170334
+3 3
+944677 952423
+152920 356383
+554578 805179
+184455 380888 698178
+230185 514275 921022
+808743 869797 898380
+1 2
+144181 631017
+950213 951280 95445
+773180 923981 530121
+2 1
+934739 963952
+385753 576021
+297370 782211 653764
+0 1
+815808 825180 553607
+4 3
+711850 996727
+414414 654367
+850194 976992
+785607 997597
+13826 137251 975710
+108518 429446 581135
+156754 173758 884166
+3 3
+269141 860234
+823658 967395
+761571 989041
+748336 896807 391479
+819336 907501 997843
+531185 784574 929943
+1 1
+795973 902304
+444029 480342 559763
+2 2
+68239 953659
+593572 956002
+918818 966858 288131
+706459 968502 629311
+4 2
+643467 869435
+688832 785581
+783328 865962
+66489 127971
+898058 915814 871061
+347712 749992 694549
+1 4
+253486 713749
+74839 440258 800419
+186910 453062 720163
+908973 961297 427484
+740357 813980 641905
+2 3
+605315 744279
+748561 880194
+357737 869472 740796
+774294 909556 611857
+122005 479597 306405
+3 1
+558711 577865
+869885 877431
+997596 999662
+517992 721391 485629
+0 1
+743122 807235 821376
+3 4
+426104 557778
+421600 985572
+11808 650525
+591898 859849 566550
+202876 810378 205267
+26600 27344 482148
+103810 277185 352198
+2 1
+925699 930346
+325954 762927
+981406 989460 672617
+2 0
+266517 350353
+270814 327997
+1 1
+413898 454905
+714457 917719 874016
+4 3
+77240 948509
+522456 574501
+566242 791242
+945165 991859
+224662 735327 128244
+550616 640193 109802
+574537 991191 568024
+0 0
\ No newline at end of file
diff --git a/11926/multi.c b/11926/multi.c
new file mode 100644
index 0000000..5802d09
--- /dev/null
+++ b/11926/multi.c
@@ -0,0 +1,46 @@
+#include <stdio.h>
+#include <stdlib.h>
+#define mil 1000000
+
+int main(){
+    int n, m;
+    scanf("%d %d", &n, &m);
+    while(n>0 || m>0){
+	int i, j, start, end, mult, s, s2, conflict=0, interval;
+	unsigned int *bitset;
+	bitset = (int*) calloc(mil, sizeof(unsigned int));
+	
+	for(i=0; i<n && !conflict; i++){
+	    scanf("%d %d", &start, &end);
+	    if(end-start == 1){
+		if(bitset[start] == 1 && bitset[end] == 1)
+		    conflict=1;
+	    }
+	    for(s=start; s<=end && !conflict; s++){
+		if(s > start && bitset[s] == 1 && s < end)
+		    conflict=1;
+		bitset[s]|=1;
+	    }
+	}
+	for(i=0; i<m && !conflict; i++){
+	    scanf("%d %d %d", &start, &end, &mult);
+	    interval=start-end;
+	    for(s=start; s<mil && !conflict; s+=mult){
+		for(s2=s; s2<=s+interval; s2++){
+		    if(s2>s && s2<(s+interval) && bitset[s2] == 1){
+			conflict=1;
+			break;
+		    }
+		    bitset[s2]|=1;
+		}
+	    }
+	}
+	if(conflict==1)
+	    printf("CONFLICT\n");
+	else
+	    printf("NO CONFLICT\n");
+	free(bitset);
+	
+	scanf("%d %d", &n, &m);
+    }
+}
diff --git a/514/in b/514/in
new file mode 100644
index 0000000..5389a20
--- /dev/null
+++ b/514/in
@@ -0,0 +1,3 @@
+5
+5 4 1 2 3
+0
diff --git a/514/rails b/514/rails
new file mode 100755
index 0000000..e5289b5
--- /dev/null
+++ b/514/rails
diff --git a/514/rails.cpp b/514/rails.cpp
new file mode 100644
index 0000000..d2f373b
--- /dev/null
+++ b/514/rails.cpp
@@ -0,0 +1,46 @@
+#include <iostream>
+#include <stack>
+using namespace std;
+
+bool in(stack<int> s, int num){
+    bool found=false;
+    while(!found && s.size()>0){
+	found=(s.top()==num);
+	s.pop();
+    }
+    return found;
+}
+
+int main(){
+    int num;
+    cin>>num;
+    while(num!=0){
+	stack<int> s, orig;
+	for(int i=num; i>0; i--)
+	    orig.push(i);
+	
+	bool possible=true, end=false;
+
+	while(!end){
+	    int x;
+	    cin>>x;
+	    if(x==0){
+		cout<<endl;
+		end=true;
+	    }
+	    else{
+		for(int i=0; i<num-1 && possible; i++){
+		    while(!in(s, x)){
+			s.push(orig.top());
+			orig.pop();
+		    }
+		    if(x!=s.top())
+			possible=false;
+		    cin>>x;
+		}
+		possible? cout<<"Yes\n" : cout<<"No\n";
+	    }
+	}
+	cin>>num;
+    }
+}
diff --git a/514/test b/514/test
new file mode 100755
index 0000000..2483dfc
--- /dev/null
+++ b/514/test
diff --git a/514/test.cpp b/514/test.cpp
new file mode 100644
index 0000000..2f79f72
--- /dev/null
+++ b/514/test.cpp
@@ -0,0 +1,37 @@
+#include <iostream>
+#include <stack>
+using namespace std;
+
+bool in(stack<int> s, int num){
+    bool found=false;
+    while(!found && s.size()>0){
+	found=(s.top()==num);
+	s.pop();
+    }
+    return found;
+}
+
+int main(){
+    int num;
+    cin>>num;
+    while(num!=0){
+	stack<int> s, orig;
+	for(int i=num; i>0; i--)
+	    orig.push(i);
+	
+	bool possible=true, end=false;
+	int x;
+	for(int i=0; i<num && possible; i++){
+	    cin>>x;
+	    while(!in(s, x)){
+		s.push(orig.top());
+		orig.pop();
+	    }
+	    if(x!=s.top())
+		possible=false;
+
+	}
+	possible? cout<<"Yes\n" : cout<<"No\n";
+	cin>>num;
+    }
+}
diff --git a/log.org b/log.org
index ed8bff7..7045172 100644
--- a/log.org
+++ b/log.org
@@ -15,3 +15,10 @@
   - A segment tree perhaps?
 - Attempting a (naive) linear array first to see if it works (half expecting it to fail on time limit)
   - Failed on TLE
+* TODO 1203
+- Min priority queue with decrease-key
+* TODO 10954
+- Min priority queue, popping each element and adding it 
+- Adding up costs of a simple array would not work since adition of sums would not necespasarily be smallest (adding other sums to additions could be shortest)
+* TODO 11995
+- Would need all STL DS??