Comptar submatrius de dimensions 1x9 i 9x1 amb tots els dígits 1,2,...,9 X99383
Donada una matriu de dígits 1,2,…,9, hem de comptar quantes submatrius 1×9 (subfila consecutiva de mida 9) i quantes submatrius 9×1 (subcolumna consecutiva de mida 9) contenen tots els dígits 1,2,…,9.
Per exemple, fixeu-vos en aquesta matriu:
1234567891 2345678912 3456789123 4567891234 5678912345 6789123456 7891234567 8912345678 9123456789
Resulta que a cada fila hi ha dues subfiles de mida 9 amb tots els dígits, i a cada columna hi ha una subcolumna de mida 9 amb tots els dígits (la mateixa columna és una subcolumna). Per tant, en aquest cas la resposta seria 18 10.
Entrada
L’entrada té varis casos. Cada cas comença amb dos nombres n,m en una primera línia. Després ve una matriu de n×m dígits 1,2,…,9 (n línies amb m dígits cadascuna).
Sortida
Per a cada cas, el programa ha d’escriure en una nova línia el nombre de submots de files i el nombre de submots de columnes que tenen mida 9 i a on hi apareixen tots els dígits 1,2,…,9.
Observació
No calen optimitzacions per a superar els jocs de proves privats. Qualsevol implementació més o menys raonable els passarà.
Avaluació sobre 10 punts:
- Solució lenta: 5 punts.
- solució ràpida: 10 punts.
Entenem com a solució ràpida una que és correcta, de cost lineal i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.
Public test cases
Input
9 9 288676776 629375814 752291357 341417161 164978235 935829482 493524593 576783648 817112929 9 10 7629814537 6547839216 4985162734 3286594713 7462395817 6921837546 3298471563 7984352167 4673285914 10 9 126748953 247638554 383826612 118275191 851349426 579182767 692417835 464554379 735961248 926793983 21 18 876434658192736458 435796841237659526 629846357128946789 771259836487951254 239634275819639677 378515162741596832 946996731322327193 595178227584321965 181343916258545311 862731495666898448 229482584973324527 317627849135163774 454864353497782982 763259678235419151 638245739168254335 985935127864976599 546342869517638243 171243896571843816 892156982347595767 328524719365827428 216812943756861674 23 14 33247862753941 96188753577138 67861875614293 25939381321655 52794647959222 71353928146757 19516219862346 88672494435854 44425136798249 36143517289641 93229863574122 17367785916728 64498372823673 82786591341515 78921345687999 29832956174381 55514517429836 41655869235147 33273622842254 96149533516462 17367488998718 45293681754673 61529874361529 11 20 36651843297568194325 47538261929845137624 55941964931725846391 18671429853562819473 84186253479862145736 62324156789342156722 49653872145279368187 93485327619485362719 71498531762187596348 26354621798693247158 37915783264915783264 26 12 532649817533 673177564422 812819726778 748385792164 551684279336 999986188241 266761435585 124562713899 485273941617 357428757955 633317862459 517869324158 171165599393 449631985742 698864178244 865476436811 254378691536 933573225357 582232767199 726915853985 371747342773 117189519562 449621984424 641395876248 888864338811 678459231687 25 30 694857321964873516489725341689 774736219485726319842754175165 158364185973264581794678521349 825297643815726958176943297482 986859413724659817561342986753 549676259254178326998261354791 431528963147564298317567649457 217931591494588431625979432396 393762635338195948173526718144 762185374963726669769978863638 674443829541637973252813547965 158714717635849216839724156519 435267198889452452484442735873 669869158642973518443215221782 371614839576214891825673482229 286961432587391324157839679437 532513976428558777778358394396 998316472865139135516186958143 827297635148284649932592545958 714539412876543966261964713665 753614892579714283659727166511 741598362754125782394165827394 265962418375976338685471239682 978635241925763891243563482917 692731854237568941327659841329 9 1 4 7 5 8 3 1 6 2 9 15 19 3645687219345867318 2818369527438165787 5754734762513894276 8118155169784326151 1599474617953283529 6972395148679142835 7376845697123849664 9463324168597231943 4285384257961837452 3637516472513898787 2811133878649125378 4928761354937654812 8254617938254617191 4691832574693812574 7243914765823914225 24 12 795836412791 728461539782 826889951869 764542239684 675428319238 199913885715 931364466173 417235618947 552187729496 288626154522 343772973351 964391532664 196159841888 836245397189 615818465775 774435226433 427996674247 286529959956 568161518592 349652881721 151374143364 992783332188 633247797819 815359148672 17 1 1 9 4 8 6 7 5 3 2 1 4 8 6 7 9 3 5 30 29 65142987367342968158152796348 89163245789173526472431867592 93571648254713982633926475819 67261953478898826594387125966 24576291621935647821215153127 38218763712385746948449244751 56425817934266952719894881678 71889324376128595366778718433 12742189536751347285961437282 85967572869417253137133616844 45654435152582446823552532515 68133678275663121294626945367 92399916491534834678435359959 29828291548299598355347173126 33671663726318669527214224897 84916752383656375446951691978 21542381967145913962778288332 16285825634921782739863466481 57764943516872927181182915294 38479523956784154513499869625 45253152739468131852647392513 87867485961239296675513177159 64385249713697546391827543741 93531658149273658294136734868 79612959438126757483619221996 16996361924735861927918653487 31144851672384951726579481632 52928763541938627562491836275 28279538164971532868892135764 38971264539872783169542837163 8 15 235148967235418 326487195684327 812764539841276 173458296173548 213597864293517 789245631784295 539872614593782 892361745892316 4 13 9562783419562 6327498516327 2784963512748 4956832174956 19 23 75634128979318456279752 54816975329641785229338 17676798597326148397526 62922575234179685685291 39358415269731485468419 93781927356414257936867 26497352618945372152943 48564869273519846814174 81243243851926781543685 72135139135827469771492 57879681492683147569826 15658398939738549261738 64982976518342579618251 49316825764139825417369 58421769356481273986547 31795419637824159823764 38617594237126958471326 37942158637982641573928 19673485296148379526148 8 14 87361594278136 21876953468271 41852739648152 98516732498561 46851932746851 91782564391782 45182793645218 47385961234785 8 23 41729368541792356841297 27436158927239561874392 39812576485912358467912 29357146829537184637592 21637549812634975182463 16529873415627893712456 86275194386152769438152 42591738656148392758416 17 5 63636 31969 49325 88788 12171 77517 96292 54444 25853 31336 13729 49168 62685 88571 77214 96942 54497 1 9 987251643 19 10 9623548719 8529164378 1483962578 4972976341 5793469612 9836417526 2253191457 6116883884 3349555975 1664434739 7822948163 8788622292 3271339341 1497716956 4535291417 9953857685 2397164528 5149585874 6677473739 25 15 637245189764326 661665427485652 332118743117989 287289316543798 946656248291474 824731111356863 158194565839541 573347992928337 795222689662115 419473874474229 931865427785693 386996854213784 663558738848952 868179342557368 229785413696875 532652961939461 464371686425526 177227295361197 785483527194683 321834134762859 651248379657912 991563742893774 145296837149248 618211427596835 639857421368957 26 2 22 84 63 95 17 76 48 31 59 22 84 65 93 16 77 49 38 71 94 63 52 25 16 87 49 38 9 16 7689245137246589 9516238741695283 6251784398514168 3564719823522456 2658134976251834 5655199855287345 9182345769139941 4623579184263759 4287965312478695 7 8 63774162 59814466 11331926 83224649 82419924 67281848 64954112 10 20 45739218461927534685 31739542861374958261 26143785926982517434 58669254781369254789 62471853692741853696 96219485732618496778 19857312649735182643 81319563478216959932 78925768391483625197 81567324918743961825 7 28 6459817236415897263941587623 4137962854312839617549823167 5963871245173862947682531974 1742359687421359762841975326 8137652948173658154639728154 4396152789364275189364297581 9314785623912935781462938751 8 6 123128 117446 262568 154321 384553 254233 134547 132965 19 6 936891 549555 153616 672747 391488 817263 224922 768379 485134 536895 679551 143698 352463 995726 881387 217912 766239 428174 534845 3 27 364289157364892519432867519 495872613475912864314659872 635491827694351798623745198 2 12 962418573962 714935862174 14 11 58496237158 35716328549 29262782999 48593271468 12673459814 66945936282 97859124763 71439825677 83123663391 54314548156 35282787525 39764258139 42517369842 38861257439 26 27 654673821947563825128349677 113861191249357681439275458 339922446178925347526893141 762184679352177548163927599 521347985623594718593264382 485236752183769456951374826 246519312459684132759585634 897754225899711915364782913 958497536218529471386628275 174675463732634815973426769 612868148916853492765183456 739921891544545269345871692 363563927184476598123467548 544182634159768264237589614 282449859425192351927684351 518296562398287689735241647 795314978564913721643785921 927737644273328419372654839 859364789521648392579815185 471475192156843777148932657 163758416239752438165794293 646121328467591342481539766 334987214952368789456321772 785641329786514293457186218 167892453421897651243435144 436518297453861273594218621 29 12 174752918634 945146273891 619875128123 351757797742 863419275535 738593563216 426948349378 282131911989 597684832494 771262686757 814326454561 945875127226 619258743613 136345298175 323964569812 448256371978 217778935338 561833818741 683641293465 359592142257 496117664694 872489756589 134325577122 725963481833 966857329146 389624175318 941649285371 812537946865 159243876159 17 15 239653487123695 572849731566557 498112118333712 615754763591824 353961579862438 844298294598266 781543927625181 167335845734949 926426356587373 299687452319697 435372681945735 542213549867552 173259846173818 958234671656466 114718362495729 352941867223741 598274631536784 30 4 5179 4348 9525 2994 6456 7283 1611 3762 8837 5175 4428 2549 6981 5352 1296 7674 9513 3232 8967 4848 1381 2169 5634 9476 6795 7813 8322 3257 4548 1981 15 12 315624978513 681492753656 471652483948 879845316292 194532178674 338476921583 975218364337 516985237429 789347526161 293652714815 645326819743 162897435956 455365646298 825936147872 334875631924 26 20 63964857217693584235 85387647153289647124 41475179246831572993 19723585613729485668 56299311567983241751 32511785938746215347 94658979881671543289 27132851364789215572 78866446479913821416 61545221795468323825 25887133722872459136 43114863846734215896 32493498516372894559 99778679352148618241 16223235633223882166 84685731927567997837 57986314254634526723 51316934152786271598 62897526431899143352 14586273918541469475 35469662795158634914 87756899849372752681 46139487526115387269 23249158243769815246 79271845632923998623 98925871364939526737 12 3 885 421 136 259 942 618 577 793 364 825 431 186 20 14 82964715382923 26687461675256 37458642479192 79321297834569 15749526718331 44196179253174 52264384531548 91915858967285 68872935146817 83533313292423 36857236184952 29648762573691 17384185425766 74421458618139 48266849721534 95999611399348 82115597926235 61716974832517 57948123567984 38135476298135 25 3 688 397 813 922 749 255 431 164 576 619 398 925 881 597 742 133 418 366 954 679 281 735 897 122 543 24 27 463579812271598463719452864 613618597243465278193642579 985623471958724916379825418 847361592897218356479218351 867432591562834765289314925 992985147289635174916382563 133341247358964531278945687 229398325649174295831624792 851453982167352896147472816 577135665772539684157293258 484242875936412448894521449 655971638425791119387147134 396329245519928221626788375 718417854697275677561899921 923584777283484732413375647 242666126861146363928456176 139898519318363495712864463 674753691284557853269412858 566175482394617589245631715 483932963248751943286723294 855441339374856219378416529 398346387125946378354962182 717538217659418328192764531 921245917836491875236985147 19 4 6522 4988 8411 1779 9134 3847 2265 5353 7696 6822 4985 8518 9479 1231 3654 5367 2743 7192 6826 19 6 887462 111146 249631 366513 794987 655398 973274 438759 522825 811447 147468 983132 769316 495583 356271 674894 232659 828925 511747 29 3 751 393 682 865 247 414 139 976 528 781 852 267 395 643 138 416 974 529 224 633 372 845 718 167 996 581 459 223 634 5 19 5483217692538471692 5379168245372146895 6593471286973425168 4185397624153897624 1697842531694782531 4 26 93587261498396274153986274 14973582614379568241379856 65273481926591652487391652 72438516972584971632854971 10 19 1728437612958473162 2963862417953648232 4359271653849251679 6492173854216973896 7278361724953867127 8617923458167539243 5847361928457391268 9536712894536729481 3188415379628116254 4821376958243786915 9 28 9482532754618932596481735233 8536432951876259347629851365 4965372184731269584731485296 3195874261395818327514968317 1273645891273483675912241454 7719254368764392781594326781 6147928465137972796854132722 2759138624759127932851647979 5824713596852741398761593248 28 1 2 4 8 3 5 7 6 1 9 2 4 5 8 6 3 7 5 1 4 2 8 9 6 3 7 5 1 4 7 27 941652378943275168925473168 973158462791534629873516429 853462179829673514892673514 287543961287379182645379182 439621758347268193542719683 943675128937469852193456827 652839147697584213745986132 23 25 4651372859416348763251984 7399183672594176835249716 9813745627349517236843131 2964538716627584361928756 6747982471536986978345123 3575266795715642389774847 5186397244972638512497679 1928578633813689724542665 8332495268134579937126458 4469629583217469693632914 7655351756489312575888132 3898964427368195766211481 5211843985685576431969393 9144182313541811118354726 1693736836946721283697541 8917217194784146875923272 6376529841487296351775659 2239856379412386597846869 4722915762483967125232915 5469172388969636847529136 3551548627391451985462371 7889147653246572981345672 9645138276942983475162983 29 12 491268375493 946352817662 263555186949 178873244895 889781219557 615938472188 432497721331 994664493424 557112535276 728249658713 366726364962 141585249649 273479812897 889317176715 626134987588 472253765664 927696624371 583861438129 769922591953 334748353838 945361872412 351876249287 498261375766 316237196845 392657148391 247193865274 923157846293 319963175284 527498631527
Output
2 8 18 1 3 14 45 66 26 66 51 10 17 73 106 107 0 1 55 23 11 66 0 4 90 142 38 0 19 0 80 48 35 0 56 0 0 28 1 0 7 40 25 72 0 23 31 6 0 0 49 6 64 0 0 0 0 38 23 0 7 0 18 22 103 77 22 77 24 39 0 33 20 21 57 73 0 10 22 56 0 17 91 87 0 26 0 37 0 27 34 0 37 0 45 8 61 9 0 11 57 0 71 77 25 66