diff options
| -rw-r--r-- | 10054/in | 75 | ||||
| -rwxr-xr-x | 10054/necklace.bin | bin | 0 -> 19600 bytes | |||
| -rw-r--r-- | 10054/necklace.c | 111 | ||||
| -rw-r--r-- | 10954/addall.py | 16 | ||||
| -rw-r--r-- | 10954/in | 9 | ||||
| -rw-r--r-- | 11926/in | 469 | ||||
| -rw-r--r-- | 11926/multi.c | 46 | ||||
| -rw-r--r-- | 514/in | 3 | ||||
| -rwxr-xr-x | 514/rails | bin | 0 -> 105376 bytes | |||
| -rw-r--r-- | 514/rails.cpp | 46 | ||||
| -rwxr-xr-x | 514/test | bin | 0 -> 105176 bytes | |||
| -rw-r--r-- | 514/test.cpp | 37 | ||||
| -rw-r--r-- | log.org | 7 |
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 Binary files differnew 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); + } +} @@ -0,0 +1,3 @@ +5 +5 4 1 2 3 +0 diff --git a/514/rails b/514/rails Binary files differnew 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 Binary files differnew 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; + } +} @@ -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?? |