Statistics

Problem Statement for "SequenceTransmission"

Problem Statement

Warning: This problem statement contains superscripts and/or subscripts. It may not display properly outside of the applet.


Tomek and Wojtek are testing their new revolutionary BitX network transmission technology. It is based on a system of incredibly precise clocks. The transmission protocol uses a single cable and just two different voltages, called high and low. During the transmission of a sequence of bits the signal is high while '1' bits are being transmitted and low while '0' bits are being transmitted. Therefore, during the transmission of a sequence of bits b0, b1, ..., bm - 1 the number of signal changes is equal to the number of indices i between 0 and m - 2, inclusive, such that bi is different from bi + 1.

Tomek is going to transmit n elements of the arithmetic sequence a * x + b to Wojtek using BitX. He will transmit the binary representations of numbers a * 1 + b, a * 2 + b, ..., a * n + b sequentially, without any breaks or delimiters between consecutive numbers. For example, if a = 3, b = 5, n = 4, the sequence of bits he will transmit will be 10001011111010001. The number of signal changes will therefore be equal to 8.

You are given longs a, b and n. Return the total number of signal changes during Tomek's transmission.

Definition

Class:
SequenceTransmission
Method:
signalChanges
Parameters:
long, long, long
Returns:
long
Method signature:
long signalChanges(long a, long b, long n)
(be sure your method is public)

Constraints

  • a will be between 1 and 40,000, inclusive.
  • b will be between 1 and 1018, inclusive.
  • n will be between 1 and 1012, inclusive.

Examples

  1. 3

    5

    4

    Returns: 8

    This example is from the problem statement.

  2. 1

    576460752303423487

    1

    Returns: 1

    b consists of only 1s in binary representation.

  3. 1

    1

    10

    Returns: 18

    The sequence transmitted is (2, 3, 4, 5, 6, 7, 8, 9, 10, 11).

  4. 40000

    1000000000000000000

    1000000000000

    Returns: 27066924353831

  5. 1

    1

    1

    Returns: 1

  6. 40000

    1000000000000000000

    999999999999

    Returns: 27066924353807

  7. 40000

    999999999999999999

    1000000000000

    Returns: 26066924353832

  8. 40000

    999999999999999999

    999999999999

    Returns: 26066924353810

  9. 39999

    1000000000000000000

    1000000000000

    Returns: 29066886499125

  10. 39999

    1000000000000000000

    999999999999

    Returns: 29066886499100

  11. 39999

    999999999999999999

    1000000000000

    Returns: 29066886499126

  12. 39999

    999999999999999999

    999999999999

    Returns: 29066886499099

  13. 1

    123456789987654321

    123456654321

    Returns: 3939382979593

  14. 1

    31

    1

    Returns: 1

  15. 4

    7

    2

    Returns: 2

  16. 25438

    863917536364163696

    299593337847

    Returns: 8516043439569

  17. 26387

    714461970430993728

    929268277475

    Returns: 27960520163752

  18. 9897

    86075769235581063

    228943991340

    Returns: 6638638596022

  19. 19690

    351160642422379556

    930427015810

    Returns: 27902119760141

  20. 18904

    417020471548390091

    367344820614

    Returns: 10891729626022

  21. 24555

    558126406084144311

    271925370275

    Returns: 7579874830859

  22. 38477

    230482089613217613

    83030626212

    Returns: 2386518206494

  23. 7857

    782683054587941583

    874185117808

    Returns: 27398992774398

  24. 4345

    613004354534243061

    927373442225

    Returns: 27515484571919

  25. 476

    962025379015825773

    863970034047

    Returns: 28552389094738

  26. 20019

    607672520635965228

    474947381869

    Returns: 13769575318858

  27. 10457

    484668406638298953

    203448964759

    Returns: 6021925809935

  28. 8017

    671799203832393286

    219280062419

    Returns: 7246303888010

  29. 23725

    612241163854634550

    432651466416

    Returns: 12967132662093

  30. 31856

    447707387412926620

    940327856084

    Returns: 27768320911047

  31. 16514

    145010868956563095

    116105278960

    Returns: 3138243993018

  32. 10210

    406318576445175250

    71408038965

    Returns: 2289212819157

  33. 3517

    475873165813198320

    426046909363

    Returns: 12729359004936

  34. 16192

    347818543848992419

    432914960515

    Returns: 12544143634776

  35. 39870

    187543764642749955

    554192150533

    Returns: 16514022865380

  36. 9295

    493181510715197640

    263595619126

    Returns: 7853633665079

  37. 6324

    407233187554822485

    217216229006

    Returns: 6971096870496

  38. 751

    914849715939622246

    533427622511

    Returns: 16716695722282

  39. 30299

    379349973016342086

    826022699795

    Returns: 25666783413004

  40. 31298

    178874371113139796

    673474560555

    Returns: 20672254336627

  41. 24413

    54315698674640282

    437128231342

    Returns: 12193292154141

  42. 9012

    623474512356863285

    618181636618

    Returns: 19349906132576

  43. 905

    11425128115478421

    797937402706

    Returns: 22974777333556

  44. 30739

    495664518531556234

    109481649113

    Returns: 3247190952944

  45. 31165

    463536835098803029

    962793450890

    Returns: 28940978830524

  46. 12586

    649645329283884262

    615431440076

    Returns: 18926069428799

  47. 2014

    190039673695637067

    219380794136

    Returns: 6687905689108

  48. 13779

    878648400732634638

    710129588492

    Returns: 20762608328411

  49. 12915

    359561423564977032

    645462790296

    Returns: 19241118563769

  50. 30930

    362910454303655991

    783001789191

    Returns: 24046103021006

  51. 25147

    818570358458691177

    808108304204

    Returns: 24694246359956

  52. 6160

    352988896403559629

    921742456908

    Returns: 27004331431566

  53. 8425

    288579302873140251

    591244523078

    Returns: 16431778553426

  54. 12196

    151104583545708442

    374737421570

    Returns: 11098154087611

  55. 23795

    597267202188411711

    806862818855

    Returns: 23846739829989

  56. 39329

    297483954601011898

    817725638751

    Returns: 24042431721188

  57. 39848

    9292

    999855767679

    Returns: 27549174569975

  58. 39996

    999999999990924261

    999999999972

    Returns: 29066861756490

  59. 39993

    999999999999999996

    999999377254

    Returns: 29066777860939

  60. 39996

    999999999999999993

    999999999999

    Returns: 29066861757282

  61. 39997

    5475123

    1000000000000

    Returns: 27055595851604

  62. 39349

    999999999953052848

    1539155

    Returns: 46461864

  63. 39956

    999999999999995943

    999999999917

    Returns: 28065592357868

  64. 39999

    999999999935810650

    2106575

    Returns: 63100928

  65. 40000

    999999999999999998

    999999998960

    Returns: 28066924321865

  66. 4

    2

    4

    Returns: 11

  67. 4

    2

    4

    Returns: 11

  68. 3

    7

    9

    Returns: 21

  69. 3

    3

    3

    Returns: 5

  70. 1

    1

    1

    Returns: 1

  71. 4

    7

    9

    Returns: 16

  72. 4

    3

    3

    Returns: 2

  73. 4

    6

    2

    Returns: 5

  74. 2

    10

    8

    Returns: 23

  75. 4

    1

    5

    Returns: 12

  76. 38

    97405

    5

    Returns: 40

  77. 40

    99631

    997

    Returns: 6518

  78. 19

    99853

    107

    Returns: 855

  79. 25

    2

    994

    Returns: 6941

  80. 24

    100000

    21

    Returns: 135

  81. 9

    99728

    1000

    Returns: 8429

  82. 31

    64413

    995

    Returns: 8877

  83. 22

    20337

    985

    Returns: 7118

  84. 39

    100000

    970

    Returns: 7807

  85. 19

    1017

    998

    Returns: 6798

  86. 273

    48

    948262

    Returns: 12851717

  87. 245

    760457653

    999999

    Returns: 14937585

  88. 399

    3012

    1

    Returns: 8

  89. 1

    1

    2

    Returns: 2

  90. 376

    996377000

    901069

    Returns: 13150615

  91. 400

    999996673

    68651

    Returns: 876896

  92. 372

    35845172

    55492

    Returns: 749847

  93. 69

    998633464

    245203

    Returns: 3309086

  94. 301

    16

    32506

    Returns: 361393

  95. 12

    1000000000

    995393

    Returns: 13358251

  96. 925

    190

    999846620

    Returns: 19550195669

  97. 70

    56491

    695229257

    Returns: 11784126652

  98. 1920

    1

    941970565

    Returns: 16492733680

  99. 53

    9999999999998

    5737

    Returns: 123248

  100. 15

    239237952

    803765467

    Returns: 13287828460

  101. 698

    9999999255630

    999999579

    Returns: 23494598557

  102. 889

    1501831

    999999896

    Returns: 19504969602

  103. 3344

    6

    984605492

    Returns: 21171843761

  104. 213

    77

    999999868

    Returns: 18483945006

  105. 26

    9999999999938

    1000000000

    Returns: 22835640121

  106. 40000

    999999999772207369

    999999999197

    Returns: 29066924322460

  107. 12

    12505

    999999999794

    Returns: 21397273117920

  108. 1

    5354

    831

    Returns: 6082

  109. 39945

    999999999999999493

    13402873

    Returns: 391436835

  110. 39999

    999999999999999655

    998736596548

    Returns: 29028380388448

  111. 39998

    999999999999999995

    5898354

    Returns: 173853776

  112. 1

    999999999997573802

    47953

    Returns: 1382904

  113. 2

    16502

    95141

    Returns: 871351

  114. 39985

    49

    1

    Returns: 7

  115. 12

    238512

    999890563796

    Returns: 21394638970475

  116. 39999

    1000000000000000000

    1000000000

    Returns: 28068020567

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: