Statistics

Problem Statement for "NailingABanner"

Problem Statement

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

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

You will start 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 will be adding more nails to the banner. The nails are going to be added in rounds. In each round, you first identify all pairs of nails that are currently adjacent (i.e., have no other nail between them), and then for each such pair you will place another nail exactly half-way between the two adjacent nails. Within each round, these new nails are placed from the left to the right, i.e., their coordinates increase.

For example:

  • Round 1: Exactly one nail (nail #3) is placed into the middle of the banner.
  • Round 2: We place two nails. Nail #4 is placed between nails #1 and #3, and then nail #5 is 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 already placed form four pairs of adjacent nails. Thus, in this round we will add four new nails - one into the middle of each of the four segments of the banner.

You are given the number N of a nail. Return the coordinate at which this nail will be placed.

Definition

Class:
NailingABanner
Method:
coordinate
Parameters:
long
Returns:
long
Method signature:
long coordinate(long N)
(be sure your method is public)

Notes

  • Watch out for integer overflow: both the input and the output can overflow a 32-bit integer variable.

Constraints

  • N will be between 1 and 10^12, inclusive.

Examples

  1. 1

    Returns: 0

    Nail #1 is placed at coordinate 0.

  2. 3

    Returns: 576460752303423488

    Nail #3 is placed exactly into the middle of the banner, at coordinate 2^59.

  3. 4

    Returns: 288230376151711744

    Nail #4 is placed halfway between nail #1 and nail #3, i.e., at coordinate 2^58.

  4. 24

    Returns: 468374361246531584

  5. 2

    Returns: 1152921504606846976

  6. 5

    Returns: 864691128455135232

  7. 65537

    Returns: 1152903912420802560

    This nail is placed quite close to the end of the banner. It is the last nail placed in one of the rounds. The next nail (#65538) is the first nail placed in the next round.

  8. 6

    Returns: 144115188075855872

  9. 7

    Returns: 432345564227567616

  10. 8

    Returns: 720575940379279360

  11. 9

    Returns: 1008806316530991104

  12. 10

    Returns: 72057594037927936

  13. 11

    Returns: 216172782113783808

  14. 12

    Returns: 360287970189639680

  15. 13

    Returns: 504403158265495552

  16. 14

    Returns: 648518346341351424

  17. 80

    Returns: 261208778387488768

  18. 97

    Returns: 567453553048682496

  19. 111

    Returns: 819655132181430272

  20. 392

    Returns: 605734149881331712

  21. 476

    Returns: 984036518580453376

  22. 1025

    Returns: 1151795604700004352

  23. 2896

    Returns: 476537135571140608

  24. 3754

    Returns: 959548195606626304

  25. 44346

    Returns: 407311883486363648

  26. 96812

    Returns: 550186822446088192

  27. 254549

    Returns: 1086101983963643904

  28. 437706

    Returns: 772123244512673792

  29. 745919

    Returns: 487368424616361984

  30. 798584

    Returns: 603179984370008064

  31. 900812

    Returns: 827981733738577920

  32. 1361475

    Returns: 344034439552040960

  33. 1511914

    Returns: 509443869323034624

  34. 1859244

    Returns: 891337242998472704

  35. 2058465

    Returns: 1110383048995635200

  36. 17523244

    Returns: 51266550711189504

  37. 40127548

    Returns: 225850494482907136

  38. 72492310

    Returns: 92486872269324288

  39. 105537857

    Returns: 660205046843047936

  40. 112999752

    Returns: 788399426807791616

  41. 125042259

    Returns: 995288121715195904

  42. 237183848

    Returns: 884472223107121152

  43. 529031949

    Returns: 1119253408444841984

  44. 580796312

    Returns: 94329075010633728

  45. 1124550984

    Returns: 54555918523695104

  46. 3717631809

    Returns: 842966874365886464

  47. 7565456455

    Returns: 877915248336568320

  48. 8408530689

    Returns: 1104226264782209024

  49. 15336428753

    Returns: 905499118053359616

  50. 25430350399

    Returns: 553680421691326464

  51. 33413403861

    Returns: 1089414070777413632

  52. 82690294625

    Returns: 234391429395251200

  53. 135492751505

    Returns: 1120269653801697280

  54. 270194222113

    Returns: 1113631908551458816

  55. 401268913579

    Returns: 530122304686915584

  56. 999999631062

    Returns: 944229721670942720

  57. 1000000000000

    Returns: 944230495390007296

  58. 100000000000

    Returns: 524800095367987200

  59. 867564656457

    Returns: 666493449808117760

  60. 111111

    Returns: 801737490695192576

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: