TopCoder Statistics - Problem Statement

Problem Statement

There are two frogs sitting on a two-dimensional plane. One frog starts at the coordinates (x1, y1), the other starts at coordinates (x2, y2).

Whenever the first frog jumps, it jumps in such a way that each of its coordinates either remains unchanged or it changes by exactly k1. For example, if the first frog has k1 = 4 and sits at (0, 0), it has nine options how to jump. It can jump to any of these coordinates: (-4, -4), (-4, 0), (-4, 4), (0, -4), (0, 0), (0, 4), (4, -4), (4, 0), or (4, 4).

The second frog moves in the same way, but each of its jumps can change each of its coordinates by k2.

If the frogs can eventually meet at the same coordinates, return 1. Otherwise, return 0.

Definition

Class:: FrogJumps
Method:: canMeet
Parameters:: long, long, long, long, long, long
Returns:: int
Method signature:: int canMeet(long x1, long y1, long x2, long y2, long k1, long k2)
(be sure your method is public)

Notes

Each frog may make arbitrarily many jumps, including zero.
The frogs may make their jumps in any order they want.
The frogs may meet anywhere on the plane, including points with coordinates that are not between -10^18 and 10^18.

Constraints

Each of x1, y1, x2, and y2 will be between -10^18 and 10^18, inclusive.
Each of k1 and k2 will be between 1 and 10^18, inclusive.

Examples

62705787029513

75803119209837

10058974523551

-50833621516003

9148219562

4976026881

Returns: 1
-28485481343944

24032406127463

-38683814723473

80760513467903

26391175853245

11170711112067

Returns: 1
92921706117938

41922519973499

41453679550279

-24910492903878

1549833217

8680864001

Returns: 1
56167538056368

67145852902862

-9889792820035

-33952032152033

6395854090

6051007489

Returns: 1
99223879608845

13296200504108

39762202999170

-67948537683587

5145281793

1654646410

Returns: 1
-93294660312104

76857131556091

98552542509551

-49444108648357

8468918842825

7148422401528

Returns: 1
588309393808

98710697992394

-185796408918

-10701641409211

7482326506

3541038218

Returns: 0
-74222120346848

-26106860777390

92970942899646

86830197137130

5569088513

4498952193

Returns: 1
-12970432585714

19721805629478

-78979883083030

96411193152843

3856269034

7933629674

Returns: 0
-26824215817214

51398240876981

-49873042046787

8263628663095

6427454795148

26680356118395

Returns: 0
-341033247149466554

-335050606544123651

-40591174080304894

946585406404362241

332415646838692626

360838246309099572

Returns: 0
-938314992959002298

-172235472875749372

-594782724698847699

65851206510221354

267006532954128011

595177127434936992

Returns: 0
-681200378124054742

732936007450361858

914041342726154501

758892111842312190

342733013010315890

413777943281324809

Returns: 1
-827152029147987967

149320379915782401

474161985234864389

-530615649123342082

212064823879252890

222271521192181296

Returns: 0
697648985628692718

-22228930518079229

-381849975330977400

908753934773190656

312657617067710066

85903166924058606

Returns: 0
-554117899521169152

111290179157133570

-16959242512840448

990947516949463039

98848443226698

23025184915457

Returns: 1
679831762355849448

56951405126418428

-471283358583424378

-675706829890901758

508988181447661732

4308967724047986

Returns: 1
-19079907358998524

-769592419341238274

-597286797120785301

-929373270972370388

61043564813386

97095327951105

Returns: 1
191081810968707071

36264565118599167

15518836719763846

-733318695769175804

90253887564033

73645896698113

Returns: 1
372637970280546308

18266886360295719

-946352519288911476

113191883750052906

1791473647749754

270022220282465244

Returns: 0
-283387383712600663

-334708849206849401

777567236690913541

-425708429737128150

21396238729217

87956301529089

Returns: 1
897600755587205379

746500913318658047

614933570618238790

17844300100823298

11342991035690

80200456985322

Returns: 0
-658060890974668603

310527676688593065

-266169533839179780

343876837268465924

333550286736904426

85158669232927104

Returns: 0
324532457173384141

811754989325385729

338462747495577866

-674766354255738624

21868595937281

71103594670337

Returns: 1
998336638912500134

153330906453025797

741197891609914861

-37954883968571140

15565782475050

84501491971594

Returns: 0
-999999580389276771

999999463122697971

-447252466560292611

-489586075926534429

88158951555593610

420942616950024040

Returns: 1
-999999784969802146

-655466105555810046

566410808439956558

194666593450006312

770023709096892777

374005203408730581

Returns: 0
-999999389948681452

999999750235659270

-395367784829438914

795331870122580947

877972262083305603

323645822993235918

Returns: 1
-999999132976437395

999999797064045043

521649362502547849

-129596296983180329

924270240010735092

280019140174653330

Returns: 1
-999999583590418122

999999644469163101

-137582559795113788

842358980561049995

387224583172335594

173123391320606146

Returns: 1
-999999924285528569

999999716610487388

-321574646496829301

961692885274531912

571376193309019286

406085063861913398

Returns: 1
-565139043168190971

999999603819644275

714704664086183938

-538103997924652921

589284268392698116

972051086028056258

Returns: 0
-999999391095474382

999999019419038528

-579564613694349652

-197987733669140932

432034709536471260

625816608511998290

Returns: 1
-999999737945324653

999999064137722163

225842430572025965

53060017897476354

761551881103219122

494032623798657921

Returns: 1
-999999287211322191

999999477936829359

563061756740935827

975585020803287569

577433423608048378

945029196136469066

Returns: 1
-999999968124928909

999999514033635846

455998341656891885

-465752984767295544

917765638746222

740802955074954

Returns: 1
-26411794156945412

999999524025014486

477484123121248510

298124691648939101

254093020743604

444645184793437

Returns: 0
-999999037066641742

999999863056892788

57443829519963500

-152219985459538120

919180954746440

787689219798366

Returns: 1
-999999080681784066

999999143924882864

547180016588902813

383949113012511443

703490119688657

392859183199985

Returns: 1
-999999414057559372

999999682587028388

448256470861919406

316601515346512336

381062456036782

633313294651986

Returns: 1
-999999537278007782

999999528172746751

615843678981370435

65622991062844585

801211884224307159

809680040082538677

Returns: 1
-999999514965875659

-905119811793381749

507601049503483991

-685452122952718077

508159802998367374

678582615476416451

Returns: 0
-999999310791513593

999999693382604238

-290792710962472349

-542502799251029489

545544042049737395

647830535120700358

Returns: 1
-999999978042438551

999999840562387838

121403068625719093

-310781923622605450

574046929671357546

478518402198742282

Returns: 1
-999999245640481203

999999774720903484

537312730191764189

604187003590115161

146190781660729195

254109411899237791

Returns: 1
-999999671024212287

999999123388427621

344728650763087398

-40691310535710804

482340480979174055

156991526209716445

Returns: 1
830339996898820099

999999018587006098

961897142502384878

-362702849731951102

929306480302051740

37579664925290830

Returns: 0
-999999545113089807

999999190398915825

423800253189794273

723187627670612391

773067997282415458

125100856064476708

Returns: 1
-999999017489768037

999999679624767072

-701969627849633632

624148302360999892

328005266354422585

868723965546774755

Returns: 1
-999999983800939962

999999010582362529

-6078048509403858

-146053833172163795

13522747418932464

773613841924761378

Returns: 1
-999999436609222008

-629389336760841980

-869272226971866660

-434259389897920184

558622973141070018

357141345916486260

Returns: 0
-999999706750894364

999999172602437426

-367512263351427632

-320626047625890742

19798676316226962

300190740902792586

Returns: 1
-999999204477827216

999999661959776090

300276662994407115

81589197945930280

216137199425814841

542069334023209745

Returns: 1
-999999049010464192

999999337129314797

-945581444695884904

281480424714948175

839117662570274186

230331939054283620

Returns: 1
-999999589623380723

-790675414349362947

481163063020544309

373233150084841474

158512640902534438

422914292934292286

Returns: 0
-999999620225927060

999999562213948269

585046954976137965

261002731138634721

887024938681887865

20282611716651641

Returns: 1
-999999146437887562

-475756894597894580

151413459990115720

661389593671653358

544969554035212490

638434984410063756

Returns: 0
-999999167132798379

999999554908343140

-324540143357595327

935430509946755897

31029497612235661

830876742999144149

Returns: 1
-999999060498540882

999999202067343139

18629693644199308

41650458184315939

529549899283713285

800609458726766450

Returns: 1
-999999707468513107

999999177511211079

40664448481578503

279301036976374714

386287853686426885

23849287314639410

Returns: 1
-777126984993398202

999999915445966589

-537714148555554816

-200276304731187825

147265403232058226

225979498099249058

Returns: 0
-999999315307495407

999999059819439677

-685476083253181887

627908501525678657

576042597883595290

102623057997317200

Returns: 1
-999999604252994870

999999310935699153

-191100944497133454

81636938464308949

43478272307040770

342509671362384386

Returns: 1
-999999545350243014

999999938372416789

161095995192209336

-317817322700163567

576974582172698314

522437762721247780

Returns: 1
-999999755075593300

258826026440973934

-204031847689294576

-920248288045440147

564453065095724145

80069280030064908

Returns: 0
-999999288983340299

999999114660460665

541182307405867228

-32272568018372354

704093688430162476

822697634785919287

Returns: 1
-999999285710401823

999999038034327557

-529528927227151852

463892925958697615

206355896689783687

383157954109903742

Returns: 1
-999999821481783537

999999758900672796

-972595139611893870

439766736551897643

818476616313202105

645054694414110631

Returns: 1
-10087491620831235

999999045553951676

724600618677570984

785792800073775251

698494633844010650

337196865304224025

Returns: 0
-999999303940533037

999999249364431749

-496468692675291949

-179956911027375211

710694064947286530

284809181326397954

Returns: 1
0

0

0

0

1000000

10000000

Returns: 1
-1000000000000000000

1000000000000000000

1000000000000000000

-1000000000000000000

1000000000000000000

1000000000000000000

Returns: 1
-1000000000000000000

1000000000000000000

1000000000000000000

-1000000000000000000

1

1000000000000000000

Returns: 1
-999999999999998997

999999999999999000

999999999999999000

-999999999999999003

999999999999999000

999999999999999000

Returns: 0
-999999999999998997

999999999999999000

999999999999999000

-999999999999998997

999999999999999000

999999999999999000

Returns: 0
999999999999999000

999999999999999000

999999999999999000

999999999999999000

999999999999999000

999999999999999000

Returns: 1
10

10

18

13

3

4

Returns: 1

These two frogs can meet. For example, they can do it as follows: The first frog jumps from (10, 10) to (10, 13). The second frog jumps from (18, 13) to (14, 13). The second frog jumps from (14, 13) to (10, 13) and the two frogs meet.
10

10

21

17

3

4

Returns: 1

These two frogs can meet as well. Here's one reasonably short solution: The second frog jumps from (21, 17) to (21, 13). The second frog jumps from (21, 13) to (17, 13). The first frog jumps from (10, 10) to (13, 13). The second frog jumps from (17, 13) to (13, 13) and the two frogs meet.
10

10

21

13

10

10

Returns: 0

Whatever these two frogs do, they will never meet.
987654321987654321

987654321987654321

-123456789123456789

-987654321987654321

1

2

Returns: 1

Sometimes meeting may require a lot of jumps.
4

7

4

7

4

7

Returns: 1

No need to jump, these frogs are already in the same location.
10000000000000

100000000000000

1000000000000000

10000000000000000

100000000000000000

1000000000000000000

Returns: 0

Watch out for integer overflow.
2

0

0

12

1000000000000000000

999999999999999999

Returns: 1
12

12

5

5

5

3

Returns: 1
0

0

1

0

8

6

Returns: 0
0

0

11

11

3

5

Returns: 1
0

0

1

1

7

4

Returns: 1
10

10

8

8

4

3

Returns: 1
751283740

47261949

-482432

49341

43253521

2354254252

Returns: 1

Statistics

Problem Statement for "FrogJumps"

Problem Statement

Definition

Notes

Constraints

Examples