BIGSEQ - Sequence
You are given the sequence of all K-digit binary numbers: 0, 1,..., 2K-1. You need to fully partition the sequence into M chunks. Each chunk must be a consecutive subsequence of the original sequence. Let Si (1 ≤ i ≤ M) be the total number of 1's in all numbers in the ith chunk when written in binary, and let S be the maximum of all Si, i.e. the maximum number of 1's in any chunk. Your goal is to minimize S.
Input
In the first line of input, two numbers, K and M (1 ≤ K ≤ 100, 1 ≤ M ≤ 100, M ≤ 2^K), are given, separated by a single space character.
Output
In one line of the output, write the minimum S that can be obtained by some split. Write it without leading zeros. The result is not guaranteed to fit in a 64-bit integer.
Example
Input: 3 4 Output: 4
Added by: | Minilek |
Date: | 2008-01-10 |
Time limit: | 4.924s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | MIT 1st Team Contest 2007 |