Statistics

Problem Statement for "BannerWithNails"

Problem Statement

This problem and the division 2 easy problem NailingABanner are two different problems. Make sure to read the statement carefully to note the differences.


You were asked to attach a very long banner to an equally long wooden fence. You did that by using some nails.

The banner is exactly 2^60 (two to the power of 60) units long.

You started by using the first nail to attach the top left corner of the banner to the fence and then the second nail to attach the top right corner. The location of the first nail is coordinate 0, the location of the second nail is coordinate 2^60.


From this point on, you were adding more nails to the banner. The nails were added in rounds. In each round, you first identified all pairs of nails that were currently adjacent (i.e., had no other nail between them), and then for each such pair you placed another nail exactly half-way between the two adjacent nails. Within each round, these new nails were placed from the left to the right, i.e., their coordinates increased.

For example:

  • Round 1: Exactly one nail (nail #3) was placed into the middle of the banner.
  • Round 2: We placed two nails. Nail #4 was placed between nails #1 and #3, and then nail #5 was placed between nails #3 and #2. (Nail #4 is in one fourth of the banner, nail #5 is in its three fourths.)
  • Round 3: The five nails we had already placed formed four pairs of adjacent nails. Thus, in this round we added four new nails - one into the middle of each of the four segments of the banner.

The process terminated after placing the nail number 2^60 + 1. It can be shown that at this moment there were nails precisely at all integer coordinates between 0 and 2^60, inclusive.


You are given the coordinate X of a nail. Return the number of this nail.

Definition

Class:
BannerWithNails
Method:
number
Parameters:
long
Returns:
long
Method signature:
long number(long X)
(be sure your method is public)

Constraints

  • X will be between 0 and 2^60, inclusive.

Examples

  1. 0

    Returns: 1

    The nail placed at coordinate 0 was nail #1.

  2. 576460752303423488

    Returns: 3

    The nail placed at coordinate 2^59 is the nail #3. (The number 576460752303423488 equals 2^59.)

  3. 468374361246531584

    Returns: 24

  4. 1152921504606846975

    Returns: 1152921504606846977

    The nail at coordinate 2^60 - 1 is the very last nail placed. Its number is 2^60 + 1.

  5. 1152921504606846976

    Returns: 2

  6. 144173241876164931

    Returns: 648547373241505955

  7. 593588263146915922

    Returns: 436627441938440726

  8. 891339906305781388

    Returns: 255532676364078547

  9. 1444627880656616

    Returns: 72147883280468976

  10. 21065618412756336

    Returns: 36687097594362605

  11. 727672435468264032

    Returns: 29384280313673611

  12. 986207816313420096

    Returns: 16711947819689588

  13. 548194760315859072

    Returns: 6644985409854322

  14. 1019692271275886336

    Returns: 4243386281020965

  15. 558129508687545856

    Returns: 1670948255170307

  16. 815008047178185728

    Returns: 960903101457537

  17. 788404390055172096

    Returns: 473956517251471

  18. 451899697650978816

    Returns: 195901025666240

  19. 289358758592552960

    Returns: 88029801220668

  20. 225789927518978048

    Returns: 42074933841732

  21. 223843773076045824

    Returns: 21007770960739

  22. 523476528514662400

    Returns: 12789901986097

  23. 772193525957787648

    Returns: 7343731043110

  24. 1085859649850441728

    Returns: 4270136174122

  25. 255553063319240704

    Returns: 1343226020744

  26. 961726358779592704

    Returns: 1008342677779

  27. 821540432115662848

    Returns: 470748409445

  28. 802058296075747328

    Returns: 233051753127

  29. 1083754126409465856

    Returns: 133316256466

  30. 977052599683383296

    Returns: 63478174935

  31. 518703604702380032

    Returns: 24909155211

  32. 349534004178845696

    Returns: 11194165863

  33. 238754232084201472

    Returns: 5184396122

  34. 1119253417303212032

    Returns: 4232255598

  35. 583698119552663552

    Returns: 1617353061

  36. 344037028343578624

    Returns: 697075639

  37. 1023532275477774336

    Returns: 506745136

  38. 35026244277895168

    Returns: 138295321

  39. 392674969949044736

    Returns: 89965557

  40. 190868226375155712

    Returns: 39109430

  41. 172026874862501888

    Returns: 19280538

  42. 612777552649388032

    Returns: 12847153

  43. 1098757500238299136

    Returns: 8191562

  44. 1004455274141974528

    Returns: 3924247

  45. 842966427957723136

    Returns: 1815251

  46. 76511715642048512

    Returns: 559083

  47. 611079975415578624

    Returns: 401089

  48. 1087922775219240960

    Returns: 254756

  49. 726319789122781184

    Returns: 106824

  50. 51281222319472640

    Returns: 34227

  51. 560381494258827264

    Returns: 24349

  52. 487303553430323200

    Returns: 11656

  53. 797840821486354432

    Returns: 6932

  54. 995014042672168960

    Returns: 3817

  55. 423901314926247936

    Returns: 1402

  56. 406449866370187264

    Returns: 694

  57. 1083115710382604288

    Returns: 498

  58. 454863562364420096

    Returns: 180

  59. 297237575406452736

    Returns: 82

  60. 234187180623265792

    Returns: 40

  61. 324259173170675712

    Returns: 22

  62. 792633534417207296

    Returns: 15

  63. 1008806316530991104

    Returns: 9

  64. 288230376151711744

    Returns: 4

  65. 144115188075855870

    Returns: 324259173170675713

  66. 99999999997

    Returns: 576460802303423488

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: