11438 - Integer Transmission EXTREME

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Khaled_912
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm

11438 - Integer Transmission EXTREME

Post by Khaled_912 » Thu Apr 24, 2008 1:42 pm

Any ideas on this one? Finding the minimum and the maximum is an easy task, but counting isn't. I thought about many DP approaches, but none seems to work. Any hints please?

Khaled_912
New poster
Posts: 33
Joined: Fri Jan 06, 2006 5:51 pm

Re: 11438 - Integer Transmission EXTREME

Post by Khaled_912 » Thu Apr 24, 2008 7:00 pm

nevermind... I got it. It has a O(number_of_zeros * number_of_ones) solution. Here are some extra cases if anyone might need them:

Input:

Code: Select all

1000 1000 1
1000 1000 298347928379879798798720
1000 1000 999999999999999999999999999999999
Output:

Code: Select all

Case 1: 1000 1 5357543035931336604742125245300009052807024058527668037218751941851755255624680612465991894078479290637973364587765734125935726428461570217992288787349287401967283887412115492710537302531185570938977091076523237491790970633699383779582771973038531457285598238843271083830214915826312193418602834034688
Case 2: 555974423571664033815804589243553849851258056649719919687842027223208475 1099511627775 10715086071852927895472850491519664723226172928744459847579908876176642604792148276241217362054492966210064718916306163335640044188739681266119374480651996816638255121404699707721118132032500352222464128504693675390102722888525081961240149071131316550955727512073714428857325554105542558247213753958400
Case 3: 204895117890205821248568630327709626680689973874093999269136602187030057673511125186725917191722642961500 73786976294838206463 10715086071862673209339033995631484603387674826220384847862185504635210271107196004295661458356137841671926385963016199639586421236787107911526121984313330105908119475888450260246956358924923888563238712442665836617347644804278510019510490361421019937212104784293118526741284801823118145350509833224192

Post Reply

Return to “Volume 114 (11400-11499)”