ChocolateDividingHard
SRM 636 · 2014-08-25 · by Errichto
Problem Statement
Mirosz adores sweets.
He has just bought a rectangular bar of chocolate.
The bar is divided into a grid of square cells.
Different cells may have a different quality.
You are given the description of the bar in a
Mirosz is now going to divide the chocolate into 16 parts: one for him and one for each of his 15 friends. He will do the division by making six cuts: three horizontal and three vertical ones. Each cut must go between two rows or columns of cells. Each of the 16 parts must be non-empty. The quality of a part is the sum of the qualities of all cells it contains.
Mirosz is well-mannered and he will let his friends choose their pieces first. His friends are even more addicted to chocolate than he is. Therefore, they will certainly choose the pieces with higher quality first, and Mirosz will be left with the worst of the 16 pieces.
You are given the
Constraints
- chocolate will contain between 4 and 75 elements, inclusive.
- All elements in chocolate will contain between 4 and 75 characters, inclusive.
- All elements in chocolate will contain the same number of characters.
- All elements in chocolate will contain only digits.
{
"95998",
"21945",
"23451",
"99798",
"74083"
}
Returns: 3
One of two optimal ways to cut this chocolate is shown below. 9 | 5 | 9 9 | 8 --|---|-----|--- 2 | 1 | 9 4 | 5 2 | 3 | 4 5 | 1 --|---|-----|--- 9 | 9 | 7 9 | 8 --|---|-----|--- 7 | 4 | 0 8 | 3 This way of cutting produces parts with the following qualities: 9, 5, 18, 8, 4, 4, 22, 6, 9, 9, 16, 8, 7, 4, 8, 3. The quality of the worst part (the one that Mirosz will get) is 3. Here is another way of cutting the same chocolate: 9 | 5 9 | 9 | 8 --|-----|---|--- 2 | 1 9 | 4 | 5 --|-----|---|--- 2 | 3 4 | 5 | 1 9 | 9 7 | 9 | 8 --|-----|---|--- 7 | 4 0 | 8 | 3 If Mirosz cuts the chocolate in this way, the quality of his part will be 2, which is worse than 3.
{
"12942",
"23456",
"99798",
"98998",
"67675"
}
Returns: 5
{
"129420",
"234560",
"997980",
"989980",
"676760"
}
Returns: 6
{"75356291270936062","61879202375922897","36129319478450361","06320615547656937","45254744307868843","14920689266495048","71727226106159490","91771159776736563","94812939088509638","56115984810304444","76317596217857418","59753883189643338"}
Returns: 44
{"540222992905480185398259270574548762061472910140789726663812289275573630033","268338420186669909856526909112531386339567126236333995706719164213968814746","362015514104976894438926728102031252715426833634378372945785208344537371984","247996723920610130286849577687221913505109363306525101270138850062532064293","525397829156169156474829046765230779652599125262001485500178912909066437340","186306566226236327538646480226235085854486029854627681432476199819595955557","743325006441898429520471196663459981493258539373445684705562127018489704589","638982640142611023035873765325209027283499981003308007594328868760609070960","263815626495820636625795894000138610194735530593185856457058183146365751504","576016791458165194400246034386954555334672408027469615519949537912647314577","379237308971067133834310043791440386028135453286579103127799053284816641386","606373485728799695135528302441223951429211282163887439271737880397439451771","018398251180556254285258116485806666683721078895444969790540141729587979298","370814402301577881185053761990928921574726103082492997384695619621088471081","311750941971533024906006164264525610837124270774384287893430904665968672201","490838557258704914391187167617758861638574644047496507543204172170343310776","370222992868108838257201735712362694805284114118135975248731298459059577908","640675165619403822689584463374338597124687757232690561129556902963676254129","954315591805772463879168703427534068517909497755235171943407160686430342293","189702239546888614894750984335643515058102712894273969959382959420028048531","712160758644794001974196992046129455622608088700817226146362176132816109909","999080704410276486311705335427327245417171198868690762215787511265909816956","954813081414904856292904898583388789209540153638450850259200750740880836071","336472479696649814899879073680935574931002786680261360368628811381986088276","136162298244208001452540340298021759991035668788024298235356358623844967623","412524946979626271236712128992434606312919093642986569992701076637288491691","177475243145535632518458208689917676392738482177629464406266478137999182022","439193031504122860895504442864108219823193507806887368002218920961845384837","819410176978319321310726254968841783710539462325758720378084860150631884743","085752527674672070215270361035355020204984543961982701757053800303455043407","895113585670408988911476982224106637187856116924916285073326758542272167870","482176904401855653607054362269539747339791179854146041590928171065920810229","137741577727931740156848150394427194441235148243258054969198542571128463970","914251256965096152320754792001094649786673382999243418087217519983871451981","200326788788729671561860226326666610408286150237395691734588344025278116943","076907597882451285808637468253570372143021298537149122860806173302836151580","335269491699989516079554180430693232371561451622429576017070041587914180437","519952111934632958026729458693464371584907362759582376511382828477558248994","470340707351401805842617433253892848048075147427931193158473954161085084618","553366607912071378006105835217164691481194391650451383866387216777035345794","059126254552201134924727272943649551498853393426020494231657912069129116465","807601970396771462870803946782284176363594383630819111427296636053809271819","274488599852693457072454573884004664413490879116843208858266888244897358336","469073513401449027071452397142999918479831175078797052381018317428287380597","296085990220542375237375014185005735424568543972426353156586297962526973857","366518143759529258146319918415142093839425579414321972075938474874179113860","712466774983796533042650781088081427396704273839453610681089007171000693310","615750241301629722559879960491472058074424589761937016122161239656655018798","686791695309738971036623127196054853032784669456751533946887405082305774360","227024177783561221922152742378512214652522899033336561836285237450135589798","814247825121949563420436004185286623525047153101643819419929660522875501236","769825116259464550505002754898664749572329368713995495960369347041190322478","462763402910178204920039384553690898130552769791186219340915376575301356742","613034675721724472149872927502085380767442736203637716918760189629718664857","479932814425593522616807685091950954357709471845238018799518823830276148395","491914815806777550143180907756497608001813481466490901203198747409400783051","199858041183492288148181351686995192107437787227262172220508297927249182882","725541970114174195908844752962234901298230667288778573940456692304426469445","163162239755793674825289836972519047560635216796178817820639802917683947480","159798771655639849032920315273409598377635228122048340393012473522571237959","863297041290703060312789925620709040754195175793726214307889151275252864393","182466107550468376493230418840158526156124170109970513554668896670385197724","767656607184562644401459191865561449031941307883226383494771349685508993055","033577105544923278338919700227742209119686288827860653743078762294126394934","919695882256753552073405236940331213901126014391790050686270424877167201003","652933938218865800487215155385861266579593499181140083609137933251809970210","350564595055980893418590619731776724393890511512854835096062359123582183344","618903506236952108212562793257938720093928513943966414604921834909138422275","789287820300925208611734676025613761545596808520512687264878332908074854436","409652040767476421611441926581341408634721660234398662976546870122085470738","971403299688262841063264021227014257776836672077173721145467189826594379959","278998462796454272355926556541669470238429274891128830695240628588711574623","002236239308024288357140419871384727341591525244271906957157295667423793865","381911321146054793261925314811341664719923720309627041592073320686389291783","725600604765084336516346285354946438499067587942793630458016602465216335013"}
Returns: 1492
Submissions are judged against all 136 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ChocolateDividingHard with a public method int findBest(vector<string> chocolate) · 136 test cases · 2 s / 256 MB per case