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

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

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
  • Проголосовать: не нравится

»
10 лет назад, скрыть # |
 
Проголосовать: нравится 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);
  }
}
→ Ответить
»
10 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить