Блог пользователя javacoder1

DP SOLUTION NEEDED!!
Автор javacoder1, история, 8 лет назад, По-английски

You have a string of length 10^5 which is a binary representation of a number.The string has no leading zeros like 11001 represent the number 25. We have to represent it as sum of numbers of the form of 2^x or -2^x (x>=0) . Find the minimum number of numbers needed to do so. Please highlight the states you use and the transitions when replying !

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A binary number can be converted to a decimal by using the following formula: \sum_{i=0}^n a_i2^{n-i} Where a is the binary representation of the number. Therefore a simple solution is this: 

printf("2^%d", n);
for(int i = 1; i < n; i++) {
  if(a[i] == '1') {
    printf("+2^%d", n - i);
  }
}
→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    You didn't understand the problem. For example, take 7. The answer isn't 1+2+4, it is 8-1

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

http://codeforces.net/contest/132/problem/D

→ Ответить