newbie_forever_at_cp's blog

Wrong answer on 440 C
By newbie_forever_at_cp, history, 7 years ago, In English

hi every one. im having a doubt in codeforces problem 440 C. here is the link http://codeforces.net/problemset/problem/440/C. My approach was

A number x can be represented by having the number with only ones which is less than the given number. for eg if number is 40 one approach is taking 11. 

     Another is having the number with only ones which is greater than the given number. i.e. 111 for 40 then take absolute difference between the number and the given number i.e abs(11 – 40) = 29 and abs(111 – 40) which is 71.

     Now call the function again for the new n. in this case fun(29) and fun(49).

     Now added with the number of ones take the min of these two i.e min(fun(29) + 2, fun(71) + 3). that is the answer. Also if we can represent the number with the ones alone. for eg 11 then return 2 just. i.e without computing min(fun(11-11) + 2, fun(111- 11) + 3);

 But i got wrong answer in test 14. the input is 81924761239462. and the expected output is 321. And my output is 395. Can you please tell me what is wrong.

here is the link: http://ide.geeksforgeeks.org/kRLASR. And even in diagnostics it is not showing anything.

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If you are downvoting, can you plz tell me why you are doing so

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe it's because you're storing n as an int, maybe not.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    since, in the preprocessing directives, i ve given this line. #define int long long, i dont think that

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Have a look at my implementation of the same idea in a bit different way 32516193

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah, Same. just you are inserted ones into a vector and took lb and up and multiplied it with the quotient of x/*lb; But what i did is suppose if x is 55, then i took 11 and subtracted 11 from 55 which is 44 and calling again. Anyways after calling the function for x/*lb times, then it is going to be the same. But i cant figure out why my implementation has gone wrong.

    → Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Here is a much smaller test case. Try 80. The correct answer should be 11, while your program gives the answer 17.

This should be enough hint for you.

→ Reply