<< problem 150 - Searching a triangular array for a sub-triangle ... | Exploring Pascal's pyramid - problem 154 >> |

# Problem 151: Paper sheets of standard sizes: an expected-value problem

(see projecteuler.net/problem=151)

A printing shop runs 16 batches (jobs) every week and each batch requires a sheet of special colour-proofing paper of size A5.

Every Monday morning, the foreman opens a new envelope, containing a large sheet of the special paper with size A1.

He proceeds to cut it in half, thus getting two sheets of size A2. Then he cuts one of them in half to get two sheets of size A3

and so on until he obtains the A5-size sheet needed for the first batch of the week.

All the unused sheets are placed back in the envelope.

At the beginning of each subsequent batch, he takes from the envelope one sheet of paper at random.

If it is of size A5, he uses it. If it is larger, he repeats the 'cut-in-half' procedure until he has what he needs and any remaining sheets are always placed back in the envelope.

Excluding the first and last batch of the week, find the expected number of times (during each week) that the foreman finds a single sheet of paper in the envelope.

Give your answer rounded to six decimal places using the format x.xxxxxx .

# My Algorithm

I solved this problem twice. My first attempt was running a Monte-Carlo simulation - and never achieved enough precision. That code is still present below.

My second (and successful) attempt `evaluate`

s the exact probabilities of each possible combination.

Its parameter is a simple container with 5 elements, where the first represents the number of A1 sheets, the second element stands for the number of A2 sheets, etc.

The initial parameter is `{ 1, 0, 0, 0, 0 }`

. If at some point we have no A5, no A4, 2x A3, no A4 and 1x A5 then it would be `{ 0, 0, 2, 0, 1 }`

.

Each sheet size is picked and the function calls itself recursively. The probability for picking a single sheet is `1 / numSheets`

.

If there are multiple sheets of the same sheet size `i`

then the probability increases to `sheets[i] / numSheets`

.

# My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.

#include <iostream>
#include <vector>
#include <iomanip>
// return number of batch where a single sheet is in the envelope
// parameter is a list of the number of available sheets, starting with A1
// e.g. 0x A5, 0x A4, 2x A3, 0x A4, 1x A5 is encoded as { 0, 0, 2, 0, 1 }

double evaluate(std::vector<unsigned int> sheets)
{
// count sheets
unsigned int numSheets = 0;
for (auto s : sheets)
numSheets += s;
// a single sheet ?
double single = 0;
if (numSheets == 1)
{
// only one sheet of A5 left => last batch
if (sheets.back() == 1)
return 0;
// except if the single sheet is A1 (first batch)
if (sheets.front() == 0)
single = 1;
}
// process all sheet sizes
for (size_t i = 0; i < sheets.size(); i++)
{
if (sheets[i] == 0)
continue;
auto next = sheets;
// use one piece of the sheet size
next[i]--;
// cut it into smaller pieces
for (size_t j = i + 1; j < next.size(); j++)
next[j]++;
// how likely do we pick this sheet size ?
double probability = sheets[i] / (double)numSheets;
// analyze next batch
single += evaluate(next) * probability;
}
return single;
}
// I kept this code for historical reasons ... it's not called in main()

double montecarlo()
{
// more rounds improve precision
const unsigned int NumRounds = 1000000;
// different seeds yields different results ...
srand(111);
// how often a single sheet is observed
unsigned int singleSheet = 0;
for (unsigned int round = 0; round < NumRounds; round++)
{
// 1 => DIN A1, 2 => A2, ... 5 => A5
// this stack of sheets may contain some sizes multiple times
const unsigned int SheetSizes = 5;
unsigned int sheets[SheetSizes] = { 1,0,0,0,0 }; // one sheet A1 on Monday morning
unsigned int numSheets = 1;
// until all sheets are used (on Friday afternoon)
while (numSheets > 0)
{
// a single sheet ?
if (numSheets == 1)
singleSheet++;
// pick a random sheet
unsigned int pick = rand() % numSheets;
unsigned int current = 0;
// select sheet size
while (pick >= sheets[current])
pick -= sheets[current++];
// and remove one sheet
sheets[current]--;
// reduce total number of sheets, too
numSheets--;
// if the current sheet is larger than A5 then cut it into smaller sheets
while (++current < SheetSizes)
{
sheets[current]++;
numSheets++;
}
}
// don't count the first and last batch (always one sheet)
singleSheet -= 2;
}
return singleSheet / (double)NumRounds;
}
int main()
{
std::cout << std::fixed << std::setprecision(6);
// start with one A1 sheet
std::cout << evaluate({ 1,0,0,0,0 }) << std::endl;
// my first approach was using a Monte-Carlo simulation but it converges too slowly
//std::cout << montecarlo() << std::endl;
return 0;
}

This solution contains 19 empty lines, 29 comments and 3 preprocessor commands.

# Interactive test

*This feature is not available for the current problem.*

# Benchmark

The correct solution to the original Project Euler problem was found in 0.02 seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

(compiled for x86_64 / Linux, GCC flags: `-O3 -march=native -fno-exceptions -fno-rtti -std=c++11 -DORIGINAL`

)

See here for a comparison of all solutions.

**Note:** interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without `-DORIGINAL`

.

# Changelog

May 23, 2017 submitted solution

May 23, 2017 added comments

# Difficulty

Project Euler ranks this problem at **35%** (out of 100%).

# Links

projecteuler.net/thread=151 - **the** best forum on the subject (*note:* you have to submit the correct solution first)

Code in various languages:

Java: github.com/nayuki/Project-Euler-solutions/blob/master/java/p151.java (written by Nayuki)

# Heatmap

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.

yellow problems score less than 100% at Hackerrank (but still solve the original problem).

gray problems are already solved but I haven't published my solution yet.

blue problems are solved and there wasn't a Hackerrank version of it at the time I solved it or I didn't care about it because it differed too much.

red problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte.

*Please click on a problem's number to open my solution to that problem:*

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

26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |

51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 |

76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |

101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |

126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |

151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |

176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |

201 | 202 | 203 | 204 | 205 | 206 | 207 | 208 | 209 | 210 | 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |

226 | 227 | 228 | 229 | 230 | 231 | 232 | 233 | 234 | 235 | 236 | 237 | 238 | 239 | 240 | 241 | 242 | 243 | 244 | 245 | 246 | 247 | 248 | 249 | 250 |

251 | 252 | 253 | 254 | 255 | 256 | 257 | 258 | 259 | 260 | 261 | 262 | 263 | 264 | 265 | 266 | 267 | 268 | 269 | 270 | 271 | 272 | 273 | 274 | 275 |

276 | 277 | 278 | 279 | 280 | 281 | 282 | 283 | 284 | 285 | 286 | 287 | 288 | 289 | 290 | 291 | 292 | 293 | 294 | 295 | 296 | 297 | 298 | 299 | 300 |

301 | 302 | 303 | 304 | 305 | 306 | 307 | 308 | 309 | 310 | 311 | 312 | 313 | 314 | 315 | 316 | 317 | 318 | 319 | 320 | 321 | 322 | 323 | 324 | 325 |

326 | 327 | 328 | 329 | 330 | 331 | 332 | 333 | 334 | 335 | 336 | 337 | 338 | 339 | 340 | 341 | 342 | 343 | 344 | 345 | 346 | 347 | 348 | 349 | 350 |

351 | 352 | 353 | 354 | 355 | 356 | 357 | 358 | 359 | 360 | 361 | 362 | 363 | 364 | 365 | 366 | 367 | 368 | 369 | 370 | 371 | 372 | 373 | 374 | 375 |

376 | 377 | 378 | 379 | 380 | 381 | 382 | 383 | 384 | 385 | 386 | 387 | 388 | 389 | 390 | 391 | 392 | 393 | 394 | 395 | 396 | 397 | 398 | 399 | 400 |

401 | 402 | 403 | 404 | 405 | 406 | 407 | 408 | 409 | 410 | 411 | 412 | 413 | 414 | 415 | 416 | 417 | 418 | 419 | 420 | 421 | 422 | 423 | 424 | 425 |

426 | 427 | 428 | 429 | 430 | 431 | 432 | 433 | 434 | 435 | 436 | 437 | 438 | 439 | 440 | 441 | 442 | 443 | 444 | 445 | 446 | 447 | 448 | 449 | 450 |

451 | 452 | 453 | 454 | 455 | 456 | 457 | 458 | 459 | 460 | 461 | 462 | 463 | 464 | 465 | 466 | 467 | 468 | 469 | 470 | 471 | 472 | 473 | 474 | 475 |

476 | 477 | 478 | 479 | 480 | 481 | 482 | 483 | 484 | 485 | 486 | 487 | 488 | 489 | 490 | 491 | 492 | 493 | 494 | 495 | 496 | 497 | 498 | 499 | 500 |

501 | 502 | 503 | 504 | 505 | 506 | 507 | 508 | 509 | 510 | 511 | 512 | 513 | 514 | 515 | 516 | 517 | 518 | 519 | 520 | 521 | 522 | 523 | 524 | 525 |

526 | 527 | 528 | 529 | 530 | 531 | 532 | 533 | 534 | 535 | 536 | 537 | 538 | 539 | 540 | 541 | 542 | 543 | 544 | 545 | 546 | 547 | 548 | 549 | 550 |

I scored 13,183 points (out of 15300 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.

Look at my progress and performance pages to get more details.

My username at Project Euler is

**stephanbrumme**while it's stbrumme at Hackerrank.

# Copyright

I hope you enjoy my code and learn something - or give me feedback how I can improve my solutions.

All of my solutions can be used for any purpose and I am in no way liable for any damages caused.

You can even remove my name and claim it's yours. But then you shall burn in hell.

The problems and most of the problems' images were created by Project Euler.

Thanks for all their endless effort.

<< problem 150 - Searching a triangular array for a sub-triangle ... | Exploring Pascal's pyramid - problem 154 >> |