TopCoder Statistics - Problem Statement

Problem Statement

Onise likes to play with paper and paint. He has a piece of paper with dimensions width x height. He does the following steps with the paper:

Fold the paper along the line x = xfold (the left side of the paper is folded over the right side).
Divide the paper vertically into cnt+1 equal sections. Then, cnt times, take the topmost section and fold it over the section below it.
Paint a rectangle with the lower-left corner at (x1, y1) and the upper-right corner at (x2, y2). Note that (0, 0) is now the lower-left corner of the paper in its current folded state, not its original state. The paint will seep through all the layers of the folded paper. See the image below for clarification.
Unfold the paper.

For example, let's say Onise has a piece of paper that is 5 x 6. He performs the described steps where xfold is 2, cnt is 2, and the coordinates of the painted rectangle's corners are (1, 1) and (3, 2). The following will happen (note that the paper starts out blue in the images and gets painted white):

You are given ints width and height, and ints xfold, cnt, x1, y1, x2 and y2. Return the total area of of the paper that is not covered in paint after Onise is done.

Definition

Class:: PaperAndPaintEasy
Method:: computeArea
Parameters:: int, int, int, int, int, int, int, int
Returns:: long
Method signature:: long computeArea(int width, int height, int xfold, int cnt, int x1, int y1, int x2, int y2)
(be sure your method is public)

Constraints

width and height will be between 1 and 10^9, inclusive.
xfold will be between 0 and width, inclusive.
cnt will be between 0 and 1000, inclusive.
cnt+1 will be a divisor of height.
0 <= x1 < x2 <= max(xfold, width-xfold) and 0 <= y1 < y2 <= height/(cnt+1).

Examples

5

6

2

2

1

1

3

2

Returns: 21

The example from the problem statement.
3

13

1

0

1

8

2

12

Returns: 35
12

12

7

3

3

1

6

2

Returns: 124
4

5

4

0

0

0

1

1

Returns: 19
4

8

4

3

0

1

2

2

Returns: 24
4

8

3

0

1

1

3

2

Returns: 30
202780277

318110070

40044318

9

1144186

10474356

2849401

25512278

Returns: 63993590307824790
183231704

961118929

139138222

0

13795917

176594069

22743322

281632570

Returns: 174227815089245206
298140737

517853687

236446916

42

39184978

612986

47019319

2238239

Returns: 153298260286005841
101553691

555214754

39721029

1

28980980

44235662

36289181

62715046

Returns: 55843903355844278
371467989

562753706

114275920

0

105034727

49872394

190933401

419686250

Returns: 173860946395520082
328591338

35739716

290007576

115

6131468

64832

199005605

192483

Returns: 8407236367924612
585340691

793305207

505054788

2

252473233

39901138

499276031

77553381

Returns: 436475781269150295
523558807

418626050

309432663

37

116654897

3157497

261252008

6959421

Returns: 184202986320132254
791773532

348099372

764003440

17

37102181

465292

137719524

878552

Returns: 274867409038394664
832920957

347377000

763748668

9

73216211

193867

273208265

2370964

Returns: 284983562271916620
909215791

190057927

11372631

0

515619759

19128092

731524154

157465544

Returns: 142936004553223717
936413403

843042487

846408809

6

668316159

15953559

779248572

26302036

Returns: 781400413453858254
407561575

20682689

11122285

0

26409154

219678

87391083

5580392

Returns: 8102562623537869
31529429

373758048

11213310

95

5373812

805795

15673290

1058536

Returns: 11392795668005856
16802903

767705484

3936496

38

5203092

664943

10707790

810783

Returns: 12868371379123572
797277663

70975909

254365933

0

85171138

8211261

165282462

10435669

Returns: 56231106316828283
557546664

900941757

305104153

2

40081499

172437312

280014456

238291309

Returns: 412960974040716369
228343168

391224761

11393270

28

16434949

2964021

96432070

4831713

Returns: 85000611822255620
55091045

750795688

55067067

0

10895011

90534577

11141636

565412056

Returns: 41245002375155585
414711275

222529246

338200609

1

48231093

13623407

66150185

23500900

Returns: 91577404510263226
218497889

898883479

45850966

12

125494855

40084182

129916261

47249367

Returns: 195992300123124401
497787643

793152323

184976959

16

85673968

4098728

173563089

38837513

Returns: 291013941945373199
569014428

250178980

132622486

1

391460450

83457863

424952722

98158030

Returns: 141370765219104592
142423843

533955465

43663818

2

22338608

32417855

59665056

34256538

Returns: 75724463896692753
998860005

663371588

377849505

432

113323755

950616

115551408

994949

Returns: 662529822810509106
264972332

920660459

63744004

0

258672

3102364

1432660

62752017

Returns: 243809492847768060
568288094

580798415

540171765

994

16011007

213897

22101068

473215

Returns: 326918092006158990
762918794

470787974

761392548

1

200958050

99009534

226652070

112333388

Returns: 358488306611477196
277880003

98495148

10815414

5

242381905

7903703

244779716

10058336

Returns: 27338833605475266
297516492

314731016

133454383

7

52296943

6718871

81795470

18453525

Returns: 88099187678241344
304242749

372212795

181396102

0

38844675

255326177

77458063

321459338

Returns: 108135793153054519
714624728

766666509

485788795

20

185059126

20004076

279924429

29144662

Returns: 521266172737628892
890704736

258622956

635263038

61

203555794

81111

432465297

669935

Returns: 220105669114174800
36148827

178895206

33887509

13

6603555

4879178

7349058

8928876

Returns: 6424584984710046
127419826

760232953

66551311

0

333194

103860162

10516936

208498382

Returns: 94737533319087698
553805769

522009643

525527222

78

77307681

3128729

136008446

4508842

Returns: 282691870345001312
579918750

385975333

566204327

0

102989204

175873514

389674985

239777276

Returns: 205514032726385628
302927647

935315096

221575802

357

44017009

27608

158908458

820115

Returns: 240143539307013902
310002674

291939084

42115006

1

111243137

51075624

161681621

95905450

Returns: 85979599762263048
85895375

859395541

13156291

28

60327583

26240155

66526068

26625830

Returns: 73748774847154000
1000000000

1000000000

436304306

999

85624127

218624

496059932

480663

Returns: 800557928668624000
1000000000

1000000000

812553186

999

680312499

846609

808292472

958087

Returns: 985733048569906000
1000000000

1000000000

202731673

999

253632272

11440

442685262

182135

Returns: 967729599871950000
1000000000

1000000000

714266976

799

16269909

1003530

550528472

1067924

Returns: 958596117013494400
1000000000

1000000000

663766679

799

141761812

245672

187293106

562746

Returns: 976901136777990400
1000000000

1000000000

0

999

130949998

482934

807329194

570757

Returns: 940598349869692000
1000000000

1000000000

1000000000

799

570542410

404146

770809525

507131

Returns: 983500392929380000
1000000000

1000000000

0

319

31264943

218086

48390685

450497

Returns: 998726332536332160
1000000000

1000000000

1000000000

799

31936928

283099

168596366

808482

Returns: 942561163588196800
1000000000

1000000000

0

499

14779

1688634

572367183

1748624

Returns: 982832289642020000
1000000000

1000000000

1000000000

639

505654943

27231

884822340

66047

Returns: 990580632523550720
1000000000

1000000000

0

124

508632349

1960523

765863784

3706181

Returns: 943870235955096250
1000000000

1000000000

1000000000

799

181113789

86110

268840470

221107

Returns: 990525728996034400
1000000000

1000000000

0

499

94918

908907

123918

1453200

Returns: 999992107751500000
1000000000

1000000000

1000000000

799

41147950

830341

41777014

864371

Returns: 999982874361664000
1000000000

1000000000

0

999

88429846

100169

169959506

137311

Returns: 996971825368280000
1000000000

1000000000

1000000000

399

263729562

82938

864988350

368636

Returns: 931288626714390400
1000000000

1000000000

0

799

70682338

112152

72502496

240326

Returns: 999813362454806400
1000000000

1000000000

1000000000

511

166736319

266598

218973366

999759

Returns: 980391339204829696
1000000000

1000000000

0

624

200170698

410868

528866424

775346

Returns: 925123524486857500
1000000000

1000000000

1000000000

624

99512066

562358

477258580

697291

Returns: 968143456016523750
1000000000

1000000000

0

999

172861346

548005

894538860

793968

Returns: 822494033624018000
1000000000

1000000000

1000000000

639

650502083

54180

846459997

196992

Returns: 982089509366932480
1000000000

1000000000

0

624

43617656

1404796

200989286

1513607

Returns: 989297647230043750
1000000000

1000000000

1000000000

639

143081185

82400

841164881

565946

Returns: 783964429525749760
1000000000

1000000000

0

19

554574686

23551008

611870697

24711885

Returns: 998669727572767060
1000000000

1000000000

1000000000

511

42793382

71734

789155028

118528

Returns: 982118273606182912
1000000000

1000000000

0

399

263435393

612167

848094670

1265748

Returns: 847151122031625200
1000000000

1000000000

1000000000

159

603364326

456

844668456

606

Returns: 999994208700880000
1000000000

1000000000

0

1

137588385

172993914

426172455

238816685

Returns: 962009193692284060
1000000000

1000000000

1000000000

79

81878628

1761122

280354071

7427199

Returns: 910033828588231120
1000000000

1000000000

0

79

28215277

4452391

308423921

11354061

Returns: 845287392637161600
1000000000

1000000000

1000000000

511

461392602

110061

812372627

402569

Returns: 947435793841817600
1000000000

1000000000

0

79

439402673

1917750

520343514

2660544

Returns: 995190210316019680
1000000000

1000000000

1000000000

319

182750655

548287

213664097

550949

Returns: 999973666693566720
1000000000

1000000000

1000000000

0

0

0

1

1

Returns: 999999999999999999
1000000000

1000000000

0

0

0

0

1

1

Returns: 999999999999999999
1000000000

1000000000

3

0

1

1

3

2

Returns: 999999999999999996
1000000000

1000000000

88888888

999

123

456

456

789

Returns: 999999999778222000
1000000000

1000000000

500000000

1

0

0

500000000

500000000

Returns: 0
5

6

1

2

0

0

1

1

Returns: 24
1000000000

1000000000

1000000000

0

0

0

1000000000

1000000000

Returns: 0
1000000000

1000000000

49997

999

1

1

5574

5

Returns: 999999999955416000
1000000000

1000000000

5000456

4

0

0

123

45678

Returns: 999999999943816060
1000000000

1000000000

1

1

0

0

10

10

Returns: 999999999999999780
1000000000

1000000000

5678999

999

1

1

4000

45689

Returns: 999999634587376000
1000000000

1000000000

1000000

999

56

45

100

678

Returns: 999999999944296000
1000000000

1000000000

500000000

9

0

0

1

1

Returns: 999999999999999980
10728

187640400

1728

399

0

0

13

27

Returns: 2013005930400
12

12

0

3

3

1

6

2

Returns: 132
1000000000

1000000000

0

999

0

0

1

1

Returns: 999999999999999000
1000000000

1000000000

0

0

0

0

1000000000

1000000000

Returns: 0
1000000000

1000000000

999999999

999

0

0

999999999

1

Returns: 999999000000000000
1000000000

1000000000

9999

999

0

0

100

100

Returns: 999999999980000000
10000000

10000000

1

1

1

1

2

2

Returns: 99999999999998
1000000000

1000000000

1

1

1

3

17

9

Returns: 999999999999999808
10000000

10000000

0

0

0

0

10000000

10000000

Returns: 0
1000000000

1000000000

999999999

999

1

1

999999990

99999

Returns: 900002001099978000
500000000

600000000

20000

2

1

1

30000000

20000000

Returns: 298198800210059994
987654321

322222220

700000000

4

3000

10000

4000

11000

Returns: 318244167895212620
1000000000

1000000000

3

1

1

1

3

156

Returns: 999999999999998760
1000000000

1000000000

1234

999

21343

11343

31345

31366

Returns: 999999799729954000
1000000000

1000000000

5000000

9

1

1

1000000

1000000

Returns: 999980000039999980
1000000000

1000000000

600000000

999

1

5

100000000

100000

Returns: 980001000199990000
1000000000

1000000000

100

4

1

1

4

3

Returns: 999999999999999940
100000000

100000000

0

0

1

1

2

2

Returns: 9999999999999999
1000000000

1000000000

500000001

9

0

0

90000000

80000000

Returns: 856000000000000000
1000000000

1000000000

0

0

0

0

999999999

999999999

Returns: 1999999999
1000000000

1000000000

100

9

50000

50000

500000

500000

Returns: 999997975000000000
1000000000

1000000000

1

1

1

1

2

2

Returns: 999999999999999998
100000000

100000000

0

0

0

0

1

1

Returns: 9999999999999999
99999999

88888888

55555555

87

158900

89

898999

99999

Returns: 8875874691879272
1000000000

1000000000

500000000

1

1

1

30

30

Returns: 999999999999996636
99999999

99999999

50000000

0

0

0

5000000

9999999

Returns: 9899999810000001
5

6

0

2

1

1

3

2

Returns: 24
1000000000

1000000000

500000000

1

1

1

499999999

499999999

Returns: 7999999984
1000000000

1000000000

0

1

0

0

1

1

Returns: 999999999999999998
1000000000

1000000000

5

9

10

12

11

13

Returns: 999999999999999990
10

10

3

4

4

1

6

2

Returns: 90
1000000000

1000000000

5

4

0

0

5

5

Returns: 999999999999999750
1000000000

1000000000

1

999

0

0

1000000

500

Returns: 999999499999500000
1000000000

1000000000

200000000

999

1

1

100

99

Returns: 999999999980596000
99999999

99999999

56238723

8

1

1

8

8

Returns: 9999999799999119
1000000000

1000000000

0

0

0

0

499999999

499999999

Returns: 750000000999999999
1000000

1000000

0

99

0

0

1

1

Returns: 999999999900
1000000000

1000000000

100000000

0

0

0

100000000

10000000

Returns: 998000000000000000
1000000000

1000000000

2

4

1

1

3

2

Returns: 999999999999999985
1000000000

1000000000

10000000

99

100

100

10000

10000

Returns: 999999980398000000
1000000000

1000000000

600

9

1

1

7

7

Returns: 999999999999999280
1000000000

1000000000

1

0

2

2

50

50

Returns: 999999999999997696
999999999

900000000

12545576

999

1

1

57857

45544

Returns: 899994729228384000
1000000000

1000000000

2

1

1

1

3

3

Returns: 999999999999999988
10

9

1

2

1

1

2

2

Returns: 87
123123

3243435

34455

4

111

222

3333

4444

Returns: 399205414665
1000000000

1000000000

499999999

1

0

0

450000000

450000001

Returns: 189999998200000000
100000000

100000000

50000000

1

0

0

40000000

40000000

Returns: 3600000000000000
100000000

100000000

0

0

1

1

900000

100000000

Returns: 9910000100899999
999999999

999999999

1245612

2

0

0

1

1

Returns: 999999997999999995
1000000000

1000000000

0

0

1

1

1000000000

1000000000

Returns: 1999999999
1000000

4000000

300000

499

10

5

200

150

Returns: 3999972450000
999999999

999999999

99999999

8

0

0

99999999

99999999

Returns: 820000001599999983
13

3

1

0

9

1

10

2

Returns: 38
1000000000

1000000000

100000000

0

0

0

100000000

100000000

Returns: 980000000000000000
1000000000

1000000000

0

0

1

1

1000

1000

Returns: 999999999999001999
12

12

2

2

0

0

6

1

Returns: 120
1000000000

1000000000

1000000

999

0

0

1

1

Returns: 999999999999998000
1000000000

1000000000

500000000

3

1

1

5

5

Returns: 999999999999999872
960000000

100000000

0

0

1

1

90005000

100000000

Returns: 86999500190004999
1000000000

1000000000

0

0

1

1

2

2

Returns: 999999999999999999
1000000000

1000000000

100

9

100000

10

2000000

20

Returns: 999999999810000000
6

6

3

5

0

0

1

1

Returns: 24
12

12

7

3

3

1

4

2

Returns: 136
100000000

100000000

0

1

1

1

2

2

Returns: 9999999999999998
1000000000

1000000000

500000000

15

1

1

10

10

Returns: 999999999999997408
100000000

100000000

10000

99

0

0

10

10

Returns: 9999999999980000
5

6

2

2

0

0

1

1

Returns: 24
1000000000

1000000000

500000000

999

0

0

1000000

1000000

Returns: 998000000000000000
100000000

100000000

99999999

99

1

122

34234

233243

Returns: 9999201956880700
123123000

324343500

34455

99

1113

2225

33334

44444

Returns: 39933872682820200
1000000000

1000000000

1000000000

999

0

0

1

1

Returns: 999999999999999000
1000000000

1000000000

4

99

2

2

1000000

1000000

Returns: 999900000200000000
1000000000

1000000000

500000000

1

0

0

1

1

Returns: 999999999999999996
429496722

429496722

1

2

1

1

429496700

29496700

Returns: 146461229653055481
100000

100000

3

0

1

1

3

2

Returns: 9999999996
1000000000

1000000000

55555

0

0

0

55555

1000000000

Returns: 999888890000000000
100000

999999

55555

332

0

0

55555

3000

Returns: 99900000
1000000000

1000000000

999999999

0

0

0

1

1000000000

Returns: 999999998000000000
1000000000

1000000000

0

0

0

0

99999999

99999999

Returns: 990000000199999999
1000000000

1000000000

500000000

999

0

0

500000000

1000000

Returns: 0
10000000

999999999

555555

332

0

0

55555

3000

Returns: 9999888991110000
1000000000

1000000000

2

0

0

0

1

1

Returns: 999999999999999998
1000000000

1000000000

100000000

0

1

1

100000000

100000000

Returns: 980000000399999998
1000000000

1000000000

500000000

999

1

1

135746

432107

Returns: 999882687542060000

Statistics

Problem Statement for "PaperAndPaintEasy"

Problem Statement

Definition

Constraints

Examples