Statistics

Problem Statement for "AutomaticVacuumCleaner"

Problem Statement

An automatic vacuum cleaner is cleaning a rectangular room. The floor of the room is divided into a grid of unit squares with R rows by C columns.

The robot starts in the top left corner. When cleaning the room, the robot cleans one square at a time, and it proceeds along the room in a zig-zag fashion: first, it cleans the entire first row from left to right, then the entire second row from right to left, then the third row from left to right again, and so on. Here is the order in which the robot would clean a room with R=5 and C=6: 

 1  2  3  4  5  6
12 11 10  9  8  7
13 14 15 16 17 18
24 23 22 21 20 19
25 26 27 28 29 30

Note that the robot always moves from a cell to another cell that shares a side with the previous one. Such a movement will be called a move.

The robot just executed the following program:

  1. Move to the top left corner.
  2. Clean the first A cells, and remember the last cell you cleaned.
  3. Clean another B cells (still continuing the pattern defined above).
  4. Using as few moves as possible, return to the cell you remembered in step 2.

You are given the longs R, C, A, and B. Compute and return the number of moves the robot made in step 4 of the above program.

Definition

Class:
AutomaticVacuumCleaner
Method:
getDistance
Parameters:
long, long, long, long
Returns:
long
Method signature:
long getDistance(long R, long C, long A, long B)
(be sure your method is public)

Constraints

  • R will be between 1 and 10^18, inclusive.
  • C will be between 1 and 10^18, inclusive.
  • A will be between 1 and 10^18, inclusive.
  • B will be between 0 and 10^18, inclusive.
  • A+B will not exceed R*C

Examples

  1. 5

    6

    2

    2

    Returns: 2

    After step 2 the robot remembered the cell marked "2" in the example shown above. After step 3 (i.e., after cleaning two more cells) the robot was in cell "4". To get back to cell "2", it made two moves to the left.

  2. 5

    6

    9

    5

    Returns: 3

    The robot needs three moves to get from cell labeled 14 to cell labeled 9 in the figure shown above.

  3. 5

    6

    9

    0

    Returns: 0

    Note that B may be zero. As the robot made no moves in step 3, it doesn't need any moves in step 4 either.

  4. 1

    1

    1

    0

    Returns: 0

  5. 2

    2

    1

    0

    Returns: 0

  6. 2

    2

    1

    1

    Returns: 1

  7. 2

    2

    1

    2

    Returns: 2

  8. 2

    2

    1

    3

    Returns: 1

  9. 2

    2

    2

    0

    Returns: 0

  10. 2

    2

    2

    1

    Returns: 1

  11. 2

    2

    2

    2

    Returns: 2

  12. 1

    500

    30

    450

    Returns: 450

  13. 500

    1

    30

    450

    Returns: 450

  14. 500

    500

    3

    249974

    Returns: 520

  15. 3

    3

    2

    2

    Returns: 2

  16. 3

    3

    9

    0

    Returns: 0

  17. 4

    5

    13

    7

    Returns: 3

  18. 4

    5

    13

    2

    Returns: 2

  19. 5

    3

    9

    4

    Returns: 4

  20. 3

    3

    6

    3

    Returns: 3

  21. 4

    4

    16

    0

    Returns: 0

  22. 5

    5

    15

    0

    Returns: 0

  23. 3

    4

    9

    2

    Returns: 2

  24. 10

    24

    85

    2

    Returns: 2

  25. 26

    27

    95

    330

    Returns: 18

  26. 28

    23

    439

    23

    Returns: 21

  27. 3

    32

    69

    23

    Returns: 23

  28. 15

    31

    320

    137

    Returns: 17

  29. 27

    16

    297

    75

    Returns: 9

  30. 7

    21

    12

    21

    Returns: 3

  31. 19

    4

    58

    6

    Returns: 2

  32. 10

    8

    72

    3

    Returns: 3

  33. 7

    27

    80

    30

    Returns: 26

  34. 483

    142

    431

    957

    Returns: 111

  35. 165

    397

    23019

    25728

    Returns: 370

  36. 315

    113

    27217

    3600

    Returns: 48

  37. 365

    486

    7757

    7404

    Returns: 388

  38. 69

    159

    4866

    5369

    Returns: 71

  39. 286

    146

    12224

    8898

    Returns: 118

  40. 218

    397

    2967

    26412

    Returns: 276

  41. 244

    474

    17374

    4603

    Returns: 147

  42. 85

    470

    14288

    16074

    Returns: 128

  43. 41

    325

    7470

    5008

    Returns: 208

  44. 8

    455

    2318

    264

    Returns: 264

  45. 133

    258

    15523

    14963

    Returns: 59

  46. 169

    488

    14251

    10429

    Returns: 131

  47. 449

    231

    17178

    29714

    Returns: 274

  48. 263

    280

    22890

    16336

    Returns: 104

  49. 354

    314

    735

    3801

    Returns: 45

  50. 55

    103

    344

    5206

    Returns: 106

  51. 486

    125

    16678

    21551

    Returns: 223

  52. 500

    499

    1

    249499

    Returns: 499

  53. 499

    500

    1

    249499

    Returns: 997

  54. 987654321987654321

    912345678912345678

    901234567901234567

    908765432912345678

    Returns: 886543210890123456

  55. 764499943268846130

    547923206807857699

    473920501949338261

    902396530849183258

    Returns: 193449882766532142

  56. 985933328280795925

    391233733798176078

    914292628560973225

    417138627894717305

    Returns: 101678517772392715

  57. 694825424210530033

    504583468240906208

    244854188670604321

    562799229345924737

    Returns: 43340670205320963

  58. 924185247759973108

    655206119558285855

    801920350965988717

    199216539960669480

    Returns: 199216539960669480

  59. 469920158698521483

    154050746331981335

    382758006936202887

    400600312653585052

    Returns: 66289644129859858

  60. 848759097548761542

    28387196824524727

    528534940854241638

    353418875055097335

    Returns: 8871084462655753

  61. 699968529154054923

    25625642322439060

    689091319238409049

    382731786204581710

    Returns: 18370746755543742

  62. 9988899001743338

    75203826876848439

    650595544393223618

    743423704372388040

    Returns: 8614564396096360

  63. 499033038035763278

    98703502012855642

    694043529601723104

    38166385857760183

    Returns: 38166385857760183

  64. 147634038715793167

    402430949023155923

    467748790707173423

    985699416693206872

    Returns: 180837518646895028

  65. 66901607562570900

    416162584796542943

    67224999013056616

    171420664745248630

    Returns: 171420664745248630

  66. 317074724663687939

    724208745377453245

    825796155040559530

    395900880377374278

    Returns: 395900880377374278

  67. 854655219458347604

    261739116895330483

    263756055961141285

    369968934570722875

    Returns: 149475421088316489

  68. 287624057338675345

    442885325636476446

    284187065224529461

    28160580732616308

    Returns: 28160580732616308

    Watch out for integer overflow.

  69. 1608690483

    1176514666

    815236606699073761

    225047659090764332

    Returns: 678042116

  70. 1123745004

    1433269625

    102537841366466864

    364086301320613222

    Returns: 1091340518

  71. 1988397939

    1589027078

    67653937922580942

    110642040931577349

    Returns: 620329051

  72. 1503507367

    1233075428

    735304767380178772

    394687539998603157

    Returns: 337007621

  73. 1914339453

    1070862085

    972937983454570205

    171392092100713015

    Returns: 584350021

  74. 539360598

    1895269061

    416053414772155359

    322985026789405658

    Returns: 820577896

  75. 1028538083

    617872382

    421309058675144208

    121866554245179294

    Returns: 638887446

  76. 742972185

    1815810154

    786290025751265056

    121449191310884719

    Returns: 294586819

  77. 1254624162

    667974942

    152403764497953268

    285456931241641308

    Returns: 436250502

  78. 88950771

    631405171

    22850175693170170

    25827039292798924

    Returns: 528295916

  79. 438915294

    1251402997

    396451569337607483

    84657577229631439

    Returns: 722646969

  80. 789185679

    407649111

    96847126220067393

    105196540088696343

    Returns: 485849961

  81. 319362747

    949107686

    199073800568675889

    81018499986221637

    Returns: 995875161

  82. 888327517

    1325636770

    227122660549739233

    732977784134370001

    Returns: 975990309

  83. 1964610832

    139328536

    4689191049707601

    150483827687150078

    Returns: 1182734048

  84. 257207248653748846

    5

    224112527153692542

    672872001470155715

    Returns: 134574400294031145

  85. 1

    395651350868609826

    271055958337039114

    2354219049774699

    Returns: 2354219049774699

  86. 208298782536159338

    1

    26157799199739748

    151403632137198803

    Returns: 151403632137198803

  87. 3

    39418596827109652

    58880086553160198

    47805570903383034

    Returns: 7891356701264822

  88. 296260513779005615

    4

    743989778187460375

    92084771143785735

    Returns: 23021192785946435

  89. 4

    385760588520043816

    599520968867564417

    883381703589488756

    Returns: 111860526549401126

  90. 5

    300349692445177401

    739478780554164898

    239633003813943472

    Returns: 83507589748791140

  91. 2

    341010364572042199

    417424444343068832

    56786799866969345

    Returns: 56786799866969345

  92. 52806909033508694

    5

    245510719568094383

    39923307088320

    Returns: 7984661417664

  93. 461940582178033694

    5

    206095406551377071

    231841335451574524

    Returns: 46368267090314908

  94. 1000000000000000000

    1000000000000000000

    1000000000000000000

    1000000000000000000

    Returns: 1000000000000000000

  95. 5

    5

    6

    9

    Returns: 1

  96. 1

    500

    30

    45

    Returns: 45

  97. 5

    6

    6

    1

    Returns: 1

  98. 5

    6

    8

    4

    Returns: 4

  99. 287624057338675360

    442885325636476400

    284187065224529470

    28160580732616308

    Returns: 28160580732616308

  100. 4

    4

    1

    12

    Returns: 6

  101. 1000

    1

    1

    1

    Returns: 1

  102. 544656

    2323232323

    332323

    1222

    Returns: 1222

  103. 10

    1

    2

    3

    Returns: 3

  104. 3

    4

    3

    1

    Returns: 1

  105. 5

    5

    5

    1

    Returns: 1

  106. 5

    5

    10

    5

    Returns: 5

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: