Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 6 ] 
[runda 14] - Łańcuchy 
Autor Wiadomość
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post [runda 14] - Łańcuchy
Dość możliwe, że mam bugi, więc jak się wam nie zgodzą outy, to nie musicie panikować ;p. Nie chcę mi się na żaden serwer wrzucać, mam nadzieję, że się nie obrazicie, że tak po chamsku tu wkleiłem 1000 liczb :D.
In:
10
100
26120 17264 6411 25908 5762 2857 30124 30254 10299 23623 29372 9219 19689 3062 4549 9960 25981 6836 10075 16109 14421 25014 25333 27778 22451 12168 2299 4665 19566 6133 4896 25549 22759 31526 10994 18020 26687 2062 12975 1553 199 15877 20571 1181 14520 12722 12047 17799 16421 6447 27284 31561 11053 25448 22833 31197 14709 24260 10176 12928 28630 13064 31751 7350 27986 12920 4422 12430 3149 17983 781 22055 9209 31248 14928 28275 275 27406 12477 22843 21709 7657 333 7267 27915 74 25882 4208 8401 6514 20336 13895 28156 11806 29734 6711 23857 23469 5423 26682
100
21780 28292 3180 5496 11706 30642 6852 17165 6240 26064 11639 15884 12125 9515 3503 16580 16981 2854 11865 22850 12976 4313 3122 6423 29770 8446 21541 29275 1644 14 17364 26097 30972 167 30837 26381 20976 12849 8159 6132 26376 9153 16356 17411 701 16189 2018 15091 21365 10946 24725 29019 14328 2626 11823 2678 5159 30578 30891 12071 27372 12515 28254 22074 4717 17518 29903 25069 27525 14550 15304 13999 11636 31401 1709 12071 6613 4199 8205 4472 11473 23014 11127 27076 7571 24309 18831 28143 17147 28992 16992 20133 12439 9588 10740 6558 8143 26531 13090 4384
100
31071 12009 9384 7366 4875 5200 9338 14209 30093 20721 19801 476 16083 26460 17062 18308 29799 31802 13945 23303 23087 8753 5614 17116 8534 7432 20415 17572 906 24588 26904 29615 7784 19378 21670 31682 9012 28285 16370 2327 11982 19746 19181 29094 24033 30187 24011 931 29022 25433 4373 7496 5929 29197 23546 29140 11026 28136 31975 8148 1030 31346 20567 31905 8582 23160 2539 14634 19801 23290 957 17395 1406 25924 6130 3166 16997 31834 14478 2858 27999 10649 14732 13369 6994 7324 303 13718 24497 605 4755 10166 19371 22428 9863 4862 28067 14981 18079 28294
100
25825 653 7812 31773 23943 3485 30607 9613 2246 17778 4758 16160 25937 30788 21510 21346 27666 12709 30258 23593 29981 22701 13803 3283 26850 27732 11601 4559 4518 24351 20712 26975 8500 22015 17135 14747 16079 20086 28909 18362 12652 28667 12172 29837 31262 3232 18602 25164 29394 5362 12206 10133 17724 800 20504 13234 19985 352 10845 18459 16503 20367 13041 11067 7610 11287 10149 30839 21824 17430 20275 12653 8383 28349 22295 29817 28845 14326 17313 31870 31992 329 9801 19939 19960 10240 3650 13531 20898 13193 26450 30954 20734 10013 15072 27045 23003 9119 1871 10425
100
28865 7879 8586 21806 7975 2175 21728 31725 12774 24461 13587 29056 15342 31091 22187 31002 12599 403 24976 23767 11771 29591 12760 23364 15907 5392 31454 3618 14591 12893 8340 11879 1337 8911 15130 22918 22796 22539 30863 15344 19121 31919 20775 17627 17690 26168 16765 18242 13539 24099 555 11309 390 1618 23449 6706 9934 23730 18706 13884 654 8731 13853 24971 10898 10359 13066 6396 24278 19495 5579 22923 27638 7330 4101 11798 4582 30815 27495 19044 17123 8182 24635 22373 20137 1154 14906 21691 19943 21833 16293 13178 25072 4255 3729 3628 7347 7175 25731 8729
100
9453 10140 1084 28101 27293 24751 11734 6329 697 14258 23824 2182 26911 15700 16871 18184 31694 23278 10086 7656 6742 27166 15550 2916 26253 28593 29849 29779 15236 199 28332 14179 953 305 8075 1446 16270 286 10946 9293 20474 759 8993 31667 22911 16519 9559 6045 21340 19039 195 31936 5891 6777 25222 30595 973 1307 14045 18439 2797 25086 13486 20324 14243 17328 18272 8758 1970 15927 19184 9305 10259 247 20033 4592 27115 18390 20404 6572 955 26525 10233 27723 29398 31137 5925 25950 4377 27300 10244 12624 13014 28918 23984 5284 24849 11743 24418 14462
100
1007 322 5769 8293 4459 15994 29465 11591 5195 1416 18982 20925 8018 7024 689 23441 184 12000 1218 30334 18903 3603 7863 19510 551 26357 21723 26026 1132 21128 20282 12677 6446 12166 22964 21497 31082 4168 10833 9151 30343 16358 25044 30809 7307 8864 31379 11675 14223 30076 6533 105 19825 12593 30109 10434 24520 5188 18774 21758 2589 6257 656 27219 20568 22348 9370 11934 12664 8744 4240 16224 21127 20792 10215 31239 21965 3572 70 14704 12869 7358 1943 3241 8013 27078 2911 19195 26785 23851 11850 10536 16010 14947 26891 13297 22099 3804 19298 21467
100
28413 29667 18046 15923 3636 10182 29062 30544 2433 16949 31859 18968 12224 2030 17696 22726 9941 8602 17060 10986 20891 14833 15071 23728 21021 18213 30291 21350 31753 894 26165 6969 19297 22849 28868 21055 13172 17879 22490 17595 23053 30763 28097 7836 4842 11860 3143 22086 12143 5748 533 13461 30364 14048 27196 7711 22845 8577 8721 442 13920 30330 20795 4159 17420 31242 14346 8589 28720 16820 14347 27344 19930 15518 19161 27139 25257 6968 23349 10931 26757 23069 13401 18438 22413 29758 31626 20477 19537 61 26605 27638 7746 15639 11419 29301 14951 20998 18679 17955
100
5713 17830 13120 9751 20304 28758 4450 21333 18919 28129 29714 12180 25982 21086 18457 14661 6231 9812 29168 2256 1987 28194 18318 13089 28822 16542 23678 13667 29656 12541 21556 19979 7101 4083 11937 26393 11479 18458 17157 30106 6027 22936 23813 29298 7618 14589 12285 20568 224 5482 5271 4898 19450 18936 17565 27715 3652 343 2315 146 6600 15030 3689 15181 6750 29411 21335 21085 6360 19636 25962 24539 15997 9637 24630 13524 27833 7106 25260 18761 18 7624 28327 28026 15710 18055 26305 8293 31795 1930 7787 12169 14752 26362 12349 1007 20506 21696 3722 16491
100
10681 23274 568 5408 21925 11600 3022 27714 4555 23671 23247 21536 7380 12213 20295 19041 25687 27286 14755 19597 25421 383 19653 20944 17606 401 30296 4603 7899 12240 4449 15820 23012 9093 10007 3183 6123 24545 12789 16964 12384 12514 5901 5347 5133 20347 18847 4190 11597 4335 19690 25030 4217 9598 2114 10992 4260 10819 8547 17272 3208 4701 20741 2823 1983 11085 26033 12498 25655 16543 26834 5219 20448 8909 6671 9116 15015 5472 13528 23033 26792 26712 13375 17685 29855 16590 2314 12912 22176 21720 30214 27247 17161 7853 1694 7332 30132 19209 21419 24912
Out:
0
0
0
1
0
0
1
0
0
0


8 mar 2011, o 20:20
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: [runda 14] - Łańcuchy
Opis rozwiązania można?


14 mar 2011, o 10:05
Zobacz profil
Gwiazda 3
Avatar użytkownika

Dołączył(a): 27 maja 2009, o 18:20
Posty: 126
Post Re: [runda 14] - Łańcuchy
Póki co w skrócie - nasze kryterium połączeń łańcuchów pozwala nam wyznaczyć graf skierowany możliwych połączeń. Pytamy w zadaniu o liczbę pokryć takiego grafu cyklami. To z kolei sprowadza się do policzenia permanentu macierzy sąsiedztwa grafu. Na szczęście wszystko dzieje się modulo 2, więc permanent jest równy wyznacznikowi - a ten możemy obliczyć w n^3.


14 mar 2011, o 10:36
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post Re: [runda 14] - Łańcuchy
Widać Kamilu, że się październikowej delty nie czytało... Nieładnie, nieładnie. Ale i bez tego raczej nie było to trudne wymyślenia (ja się w miarę prędko skapłem, że rozłożenie na cykle, to permutacja blabla, a permutacja to permanent blabla, a czyli to to, co było w październikowej delcie :P).
Muszę powtórzyć, że straszne z was brzydale, że nikt mi nie potwierdził, bo się okazało, że miałem buga i mam tylko 1 pkt :<.

EDIT: Eh, meh, co za głupi błąd, nie chciało mi się myśleć, co dokładnie oznacza ten warunek na długości łańcuchów, więc wpisałem bez przemyślenia jakieś if(max(war[i], war[j])<=2*max(war[i], war[j])) ze świadomością, że to może być źle, ale to się zobaczy, czy będzie działać. No i oczywiście działało i oczywiście było źle, bo trzeba było if(max(war[i], war[j])<=2*war[i]) :<. Oczywiście teraz accepted. Nie zalicza się to do takich zupełnie najgłupszych błędów, jakie można zrobić, ale trochę dobija fakt, że miałem świadomość, że to może być źle, ale ze względu na swoje lenistwo nie sprawdziłem tego :/.


14 mar 2011, o 18:40
Zobacz profil
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Re: [runda 14] - Łańcuchy
No cóż, mogłem czytać delty.
Dla pocieszenia brzydalu - 1 pkt to zawsze (no, prawie) więcej niż 0 pkt.
Btw. też masz tak straszny czas w wieżach na przykładowym?


14 mar 2011, o 18:58
Zobacz profil
Gwiazda 2Gwiazda 2Gwiazda 2Gwiazda 2

Dołączył(a): 22 lis 2009, o 14:14
Posty: 217
Post Re: [runda 14] - Łańcuchy
Nie zacząłem pisać jeszcze wież.


14 mar 2011, o 19:00
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Utwórz nowy wątek Odpowiedz w wątku  [ Posty: 6 ] 


Kto przegląda forum

Użytkownicy przeglądający ten dział: Google [Bot] i 1 gość


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Szukaj:
Skocz do:  
cron


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group. Forum style based on STSoftware Hestia.
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL