From ff0c2a07783d1732fb364677b053b7344c924fbe Mon Sep 17 00:00:00 2001 From: Familia Date: Mon, 28 Jul 2008 15:05:06 -0500 Subject: [PATCH] =?utf8?q?10373=20-=20The=20brick=20stops=20here=20(DP,=20?= =?utf8?q?programaci=C3=B3n=20din=C3=A1mica)?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- 10373 - The brick stops here/10373 | Bin 0 -> 10155 bytes 10373 - The brick stops here/10373.cpp | 69 +++++++++++++++++++++++++++++++++ 10373 - The brick stops here/in.txt | 39 +++++++++++++++++++ 3 files changed, 108 insertions(+) create mode 100755 10373 - The brick stops here/10373 create mode 100644 10373 - The brick stops here/10373.cpp create mode 100644 10373 - The brick stops here/in.txt diff --git a/10373 - The brick stops here/10373 b/10373 - The brick stops here/10373 new file mode 100755 index 0000000000000000000000000000000000000000..815e1d4badac6377e7263f2346638e27afe5c088 GIT binary patch literal 10155 zcwX&Ve{fUBo!=)t84(-*!ZfB3B2&}AB*;H7#7;tsv0uOmzk+c};K;Kq3F{SGQl%$i zasf<*Qyj$?r_KG*Hos`oxisY(U(03amFqb%7bl%e&y)J5nQ10RuXIj6=nc6^d!+H8 z`+j!!Nl%K?ayOZq`y?LwZ&&<4Lkn ziYM1j0nfd#nCnHjgG4pSYKntP6NW32I^Z@_n$4se&O_K^i`(%VGY}|dERa&&aJNv{ zEw=c3D4xynSozoW89jA$`tF&I+Etm+}kbDw!y!^?1nLSb)DT z{TLSDuaWp$^8}uf_y;onZi&w_fqyD-tHdu!+#>OJC4Nk%_mkUATR z-MXiO>W|1GsDWH=W5#DyA{pdu$>~<2m)U*-R!g^rq=b zdnq(sL+a9ZP@cQ@zCMvz>!y^M6(#hGG?^7BQ3&3d^OP*J0woI}Zf1&OlrV%U&5U!5 zl7?X2X2v*1i9;UXXE{d6Lo0ztIYtdaXwsQMj!~0PGjNn+)F`w8xSM0tEVLPT2SM3- ztl_u!5C1B8;qs1MJ41ty5Mz{n?zuNK_%PYA2Z;FIXx>BZlDy;|T;Gj)nk5&PCdbup zZ$Q=GJPDC1A9^!!@l_Y%mDeXE|6~=J#i4Pt@(gs6Xa1yGi?Ga;#Zgn5`-C=I_L4T6 zysR7_PyEh`sUFs5hr6yM56>!zhGU1Xpzw*6l)r0VbY|`$8<{*jMJ++Gu%qeE@Yr$0j%erX={k7KG-573kkY1KKJOSA9lUj!Tlihw zP0QTFyK3Ds&F7J35v8H%lsbgiq46Wv=g|6pBjrbnUe%sdE~@m)sO_E{R%_FzWTGlg zOKIaHs$*CiPioUjN;}u0O+R!DE!9m5MznFHn4%ezV#Jx$-s0tJoYdato*PoyTdA(M zjq#doG&!dx)uBOjb|!N)sl83vjkjoTANgfcdrL_keyi%pYm=@)IRj2|<%>|k;i@6^ zr!M!Tb{@??^9s61yHExH^W4v;+03K#lhV#-%bi{|H8ehuNbS3jN~BX;FC=G_yy)S{ zRlgYigYmK`8ihkO7*t5o%4_{bO1qHiN?YX@ZT>ha{s!84xT-e&Jt|bH+?e2u%flj@ zq?Q)7OPBpch^m|Hzd$v-z{(!m21GUCO?kfT(MG}}+F5%~>trZqsuhfYF$ymk(N2>f zoo6IV1FK~g-E@YkSV|&!r3!ud6z|KY(3el4XU=odY3liM64@?)n$w;J?P<_{#A#!K zHkPG5!)ece_6%rWoy8D5h3-prouLfNUVLR(yL8b@1xR&Wvb7TLMwE6$JB5@FGciI= zCACWmXOB_Z+qFv%xp^~PI&wCpomx*L@8|=I$R{hh4HfPFAd|U>39=KY=K~b=Y%;A3 zYiHrPk}3Pk@#EuVLqEHUmYt&PUu)5(${zhTm6jWf*m>F6IanfvJ7Bi3mS zwjx0P9_yET64x=KKN^Y0jh?gXXd77kL zZZqY<9ZY%1?cxig5>-8+h_xA9DcM>LBo))U)IH=-u^?FBlJV{2b`j_LKf=MA5;nW) zBRCt#!9L)0a=s}B}r2RYcI3UaVr&6Gd<^(3(`L?IVSN%lQ5mE$`BX|E$j$e+no7&oL^Q@$8|0++Dmo{mhm0dlFu$d5O z_1XkSO{>`dmPy+_Ph)-kt@SO9EuNLpSTGjs3(^L5l`VaPw{dmDI*~!+$DYCeVOjsE zs#=EK=m-;UQ!xgYGcg7i+WJ)RmMIqR^l>pp>*ZLro*HKDrjciYT*00m&v2HcDr@Oi zc|oRrf=0pq!`W0r4BC>&5ZH>PGK6Z-WS0 zZN`GZI%7@qy48rP^T!i){+MZaJFhLJJ($wsfXma`>7lM^X3C%_&^}(E7nxXITvN6m zDp2_2DUed3tSDVr>?~bUTA@@bYUeFjLH7v$1*Mlrh&6msi~`3zo(|Rx313N!ttHUfqCIvDI*+36!_rBUXF0C z9GGU#`ASVqjYAOyz=U&FWkaq>#a!Ln_9rYuJQRtUo4_7~AL;K8h7lI*N%ZQzm@nKLj9W08=%Ea9*a+{BWT`zpvEV@q^%>!y<>$2( zUYXrBKTDWcv%q}w?-7bvLs*X@B_{Da$>ZM*?zf1D4-U$(JvkbF%a1G>s zFV`km4~;3}om9xXoryIOcvvS*E8=_|>n4TezALmbu~q^P>#FA*Vm)O&mKW~@YfXgp z&}mBaX_nLLkZv~973(j1J%FP&9@cHms#wo~ zS7PHGVxp|jgE@3U73b8}W9c<*Jj|mr6fsu7gF9;D;hR;I6h3bij^)m^hip8|*=lO^ zr3LxnNio}a!Q3sLyL?}>@%VS7V(|^BkayC?8ztUoaqjzxo%cP-74m*y zeD)CvExR8vqvRh55m~VdG(4 zuU3d}g@wF-w(**Y*IY4oeSgVv-_LNy-A=sr?=H^rJW`%#xjBFbyaRL0kC_7ASfv=J z)?>Bhl>#1&#tIv>;@nC;Zw2vQoI`I_0dJZ%IuRST;+7Zi+GwM+dXD_Ol4p(0=%*O_ z2U|Ktx|V|c>aQ1PJJw^>7yB&xnN5^9Fwzm(h533EQ@wNi^Zs!&SGH*U@rw0quSahI^|c@sVo+)0XrwK_)6QH z#n*9sB8!VTK9j{_1V@J~yny5Cl!Z$eVEdP6U{3+A z$r~psdpDDB>)y@S-{rtugRH+o?FE}$lEn+zZ7kPb3bofJCh9BZ%VKsf$qkQN@zs1= z^Q^VQqyEIwW6FjL_2Yfyw&}+iYPn7S*Gc}_qZY1Ue^pSPACkQMNG|`v`o3O(f6j7e zz2N_f<<5tJE2v`l+-BA9MkROdi};%ecgsDoLgNv3#Tp-q<9dd>7gl>RMW!X#S;IMZGd>ly;FeyQxWqG^}}6)_m$jytfcvvk$mf}L!~rs)?J5NCARK5 z>>`YhT~>YWmGRcyhd+1Z-(7e_#<$A&Z#r`AQ%>#kJmEVeu5eVdza@-M!h4vkuS{>< zo%jXe_H6ohGruN$m#sbDC;S}sw-tX?rnl}|lv26zscHIKi+TAgocZ}xJM-^iv=IJx zIUXw=3)l{%m)`_XzAk6Z9#+C0%54(_b{XWQ9b()}?B7pbU2og9eW$*qqjMK7Zs_fK z=&rUbpj||?FK7k>-nA{wjVuaLPn1AJ@9m59`1*9dE75(40Veh?fkc1*AxnX_tv#2& z1@7G0x>d^}D6{;zT>aTx8|v5Gy2k5|Mwz~8%l3_}TXelc4-neZ)S%<;hH3b9)Y9A`RyKY(8wVS4+0+gi7Fv@vYGWY_~-*_wVM-0?+i=iR&X&PM#_ zT|wEf!G4uQ-bA52w$8VNR_1%w`a?ngfu3u+YO_D8he$QgKwf^yX{rCHt2mM(Z@PTw zN{l^+=to`KDaa##lh5zkwH1MQL=RDq^#$$CzzdbjdxNGP_3LIR5kBDU8DRW+kSNuE10A51MgRZ+ literal 0 HcwPel00001 diff --git a/10373 - The brick stops here/10373.cpp b/10373 - The brick stops here/10373.cpp new file mode 100644 index 0000000..b201a0b --- /dev/null +++ b/10373 - The brick stops here/10373.cpp @@ -0,0 +1,69 @@ +//10373 - The brick stops here +#include +using namespace std; + +const int MAXM = 20, MAXN = 200, MAXSUM = MAXM * 1000; + +unsigned int dp[MAXM+1][MAXSUM+1]; +int w[MAXN], p[MAXN]; + +void check(bool b){ + while (!b); +} + +int main(){ + int runs; + scanf("%d", &runs); + for (int run=0; run=1; --i){ //i va descendiendo para no ir a usar el mismo ladrillo dos veces. + for (int j=0; j <=sum; ++j){ + if (j - w[k] >= 0){ + dp[i][j] = std::min(dp[i][j], dp[i-1][j-w[k]] + p[k]); + } + } + } + } + + int c; + scanf("%d", &c); + while (c--){ + int m, cmin, cmax; + scanf("%d %d %d", &m, &cmin, &cmax); + check(0 <= m && m <= 20); + check(1 <= cmin && cmin <= 999); + check(1 <= cmax && cmax <= 999); + + unsigned int answer = INT_MAX; + for (int j=m*cmin; j<=m*cmax && j <=sum; ++j){ + //if (answer > dp[m][j]) printf("better answer: dp[%d][%d] = %u\n", m, j, dp[m][j]); + answer = std::min(answer, dp[m][j]); + } + if (answer < INT_MAX){ + printf("%u\n", answer); + }else{ + printf("impossible\n"); + } + } + } + return 0; +} diff --git a/10373 - The brick stops here/in.txt b/10373 - The brick stops here/in.txt new file mode 100644 index 0000000..870ca8f --- /dev/null +++ b/10373 - The brick stops here/in.txt @@ -0,0 +1,39 @@ +2 + +11 +550 300 +550 200 +700 340 +300 140 +600 780 +930 785 +730 280 +678 420 +999 900 +485 390 +888 800 +3 +2 500 620 +9 550 590 +9 610 620 + +11 +55 300 +55 200 +70 340 +30 140 +60 780 +93 785 +73 280 +67 420 +99 900 +48 390 +88 800 +5 +2 50 62 +9 55 59 +9 61 62 +8 2 999 +8 999 1 + + -- 2.11.4.GIT