// Inputs: nothing to run default cases or // two integers on a single line wirh a space // between them for the dimensions of the // rectangle. // Created for this challenge: // https://www.sololearn.com/post/107845 // [CHALLENGE] SQUARED RECTANGLES // You want to replace the old carpet from your // NxM living room, so you go to the only carpet // store nearby to buy one. // Much to your surprise, the store only sells // square carpets (e.g. 1x1, 5x5, 42x42), all // at the same price. // You've wasted so much money remodeling your // house that you wish to spend as less money // as possible on the carpets. // Write a program to find the minimum number // of square carpets needed to cover your NxM // living room. // Carpets can't be overlapped or cut, and must // perfectly fit in the room (i.e. no spaces // between them). /* For example: Input: 3 5 Output: 4 (1x1, 1x1, 2x2, 3x3) 12344 DDDCC1 DDDCC2 DDDAB3 Input: 7 8 Output: 7 (1x1, 1x1, 2x2, 3x3, 3x3, 4x4, 4x4) 12345678 FFFFGGGG1 FFFFGGGG2 FFFFGGGG3 FFFFGGGG4 DDDEEECC5 DDDEEECC6 DDDEEEAB7 Input: 2 8 Output: 4 (2x2, 2x2, 2x2, 2x2) 12345678 AABBCCDD1 AABBCCDD2 Input: 13 11 Output: 6 (1x1, 4x4, 4x4, 5x5, 6x6, 7x7) 12345678901 FFFFFFFBBBB1 FFFFFFFBBBB2 FFFFFFFBBBB3 FFFFFFFBBBB4 FFFFFFFCCCC5 FFFFFFFCCCC6 FFFFFFFCCCC7 EEEEEEACCCC8 EEEEEEDDDDD9 EEEEEEDDDDD0 EEEEEEDDDDD1 EEEEEEDDDDD2 EEEEEEDDDDD3 Input: 17 16 Output: 8 (1x1, 3x3, 4x4, 5x5, 6x6, 6x6, 7x7, 10x10) 1234567890123456 HHHHHHHHHHEEEEEE1 HHHHHHHHHHEEEEEE2 HHHHHHHHHHEEEEEE3 HHHHHHHHHHEEEEEE4 HHHHHHHHHHEEEEEE5 HHHHHHHHHHEEEEEE6 HHHHHHHHHHFFFFFF7 HHHHHHHHHHFFFFFF8 HHHHHHHHHHFFFFFF9 HHHHHHHHHHFFFFFF0 GGGGGGGBBBFFFFFF1 GGGGGGGBBBFFFFFF2 GGGGGGGBBBADDDDD3 GGGGGGGCCCCDDDDD4 GGGGGGGCCCCDDDDD5 GGGGGGGCCCCDDDDD6 GGGGGGGCCCCDDDDD7 Input: 22 29 Output: 9 (2x2, 2x2, 4x4, 4x4, 4x4, 4x4, 11x11, 11x11, 18x18) 12345678901234567890123456789 IIIIIIIIIIIIIIIIIIHHHHHHHHHHH1 IIIIIIIIIIIIIIIIIIHHHHHHHHHHH2 IIIIIIIIIIIIIIIIIIHHHHHHHHHHH3 IIIIIIIIIIIIIIIIIIHHHHHHHHHHH4 IIIIIIIIIIIIIIIIIIHHHHHHHHHHH5 IIIIIIIIIIIIIIIIIIHHHHHHHHHHH6 IIIIIIIIIIIIIIIIIIHHHHHHHHHHH7 IIIIIIIIIIIIIIIIIIHHHHHHHHHHH8 IIIIIIIIIIIIIIIIIIHHHHHHHHHHH9 IIIIIIIIIIIIIIIIIIHHHHHHHHHHH0 IIIIIIIIIIIIIIIIIIHHHHHHHHHHH1 IIIIIIIIIIIIIIIIIIGGGGGGGGGGG2 IIIIIIIIIIIIIIIIIIGGGGGGGGGGG3 IIIIIIIIIIIIIIIIIIGGGGGGGGGGG4 IIIIIIIIIIIIIIIIIIGGGGGGGGGGG5 IIIIIIIIIIIIIIIIIIGGGGGGGGGGG6 IIIIIIIIIIIIIIIIIIGGGGGGGGGGG7 IIIIIIIIIIIIIIIIIIGGGGGGGGGGG8 AACCCCDDDDEEEEFFFFGGGGGGGGGGG9 AACCCCDDDDEEEEFFFFGGGGGGGGGGG0 BBCCCCDDDDEEEEFFFFGGGGGGGGGGG1 BBCCCCDDDDEEEEFFFFGGGGGGGGGGG2 Input: 38 34 Output: 9 (4x4, 6x6, 6x6, 6x6, 10x10, 10x10, 14x14, 14x14, 24x24) 1234567890123456789012345678901234 IIIIIIIIIIIIIIIIIIIIIIIIEEEEEEEEEE1 IIIIIIIIIIIIIIIIIIIIIIIIEEEEEEEEEE2 IIIIIIIIIIIIIIIIIIIIIIIIEEEEEEEEEE3 IIIIIIIIIIIIIIIIIIIIIIIIEEEEEEEEEE4 IIIIIIIIIIIIIIIIIIIIIIIIEEEEEEEEEE5 IIIIIIIIIIIIIIIIIIIIIIIIEEEEEEEEEE6 IIIIIIIIIIIIIIIIIIIIIIIIEEEEEEEEEE7 IIIIIIIIIIIIIIIIIIIIIIIIEEEEEEEEEE8 IIIIIIIIIIIIIIIIIIIIIIIIEEEEEEEEEE9 IIIIIIIIIIIIIIIIIIIIIIIIEEEEEEEEEE0 IIIIIIIIIIIIIIIIIIIIIIIIFFFFFFFFFF1 IIIIIIIIIIIIIIIIIIIIIIIIFFFFFFFFFF2 IIIIIIIIIIIIIIIIIIIIIIIIFFFFFFFFFF3 IIIIIIIIIIIIIIIIIIIIIIIIFFFFFFFFFF4 IIIIIIIIIIIIIIIIIIIIIIIIFFFFFFFFFF5 IIIIIIIIIIIIIIIIIIIIIIIIFFFFFFFFFF6 IIIIIIIIIIIIIIIIIIIIIIIIFFFFFFFFFF7 IIIIIIIIIIIIIIIIIIIIIIIIFFFFFFFFFF8 IIIIIIIIIIIIIIIIIIIIIIIIFFFFFFFFFF9 IIIIIIIIIIIIIIIIIIIIIIIIFFFFFFFFFF0 IIIIIIIIIIIIIIIIIIIIIIIIAAAABBBBBB1 IIIIIIIIIIIIIIIIIIIIIIIIAAAABBBBBB2 IIIIIIIIIIIIIIIIIIIIIIIIAAAABBBBBB3 IIIIIIIIIIIIIIIIIIIIIIIIAAAABBBBBB4 EEEEEEEEEEEEEEFFFFFFFFFFFFFFBBBBBB5 EEEEEEEEEEEEEEFFFFFFFFFFFFFFBBBBBB6 EEEEEEEEEEEEEEFFFFFFFFFFFFFFCCCCCC7 EEEEEEEEEEEEEEFFFFFFFFFFFFFFCCCCCC8 EEEEEEEEEEEEEEFFFFFFFFFFFFFFCCCCCC9 EEEEEEEEEEEEEEFFFFFFFFFFFFFFCCCCCC0 EEEEEEEEEEEEEEFFFFFFFFFFFFFFCCCCCC1 EEEEEEEEEEEEEEFFFFFFFFFFFFFFCCCCCC2 EEEEEEEEEEEEEEFFFFFFFFFFFFFFDDDDDD3 EEEEEEEEEEEEEEFFFFFFFFFFFFFFDDDDDD4 EEEEEEEEEEEEEEFFFFFFFFFFFFFFDDDDDD5 EEEEEEEEEEEEEEFFFFFFFFFFFFFFDDDDDD6 EEEEEEEEEEEEEEFFFFFFFFFFFFFFDDDDDD7 EEEEEEEEEEEEEEFFFFFFFFFFFFFFDDDDDD8 Input: 42 25 Output: 10 (1x1, 1x1, 2x2, 3x3, 4x4, 4x4, 5x5, 8x8, 17x17, 25x25) 1234567890123456789012345 JJJJJJJJJJJJJJJJJJJJJJJJJ1 JJJJJJJJJJJJJJJJJJJJJJJJJ2 JJJJJJJJJJJJJJJJJJJJJJJJJ3 JJJJJJJJJJJJJJJJJJJJJJJJJ4 JJJJJJJJJJJJJJJJJJJJJJJJJ5 JJJJJJJJJJJJJJJJJJJJJJJJJ6 JJJJJJJJJJJJJJJJJJJJJJJJJ7 JJJJJJJJJJJJJJJJJJJJJJJJJ8 JJJJJJJJJJJJJJJJJJJJJJJJJ9 JJJJJJJJJJJJJJJJJJJJJJJJJ0 JJJJJJJJJJJJJJJJJJJJJJJJJ1 JJJJJJJJJJJJJJJJJJJJJJJJJ2 JJJJJJJJJJJJJJJJJJJJJJJJJ3 JJJJJJJJJJJJJJJJJJJJJJJJJ4 JJJJJJJJJJJJJJJJJJJJJJJJJ5 JJJJJJJJJJJJJJJJJJJJJJJJJ6 JJJJJJJJJJJJJJJJJJJJJJJJJ7 JJJJJJJJJJJJJJJJJJJJJJJJJ8 JJJJJJJJJJJJJJJJJJJJJJJJJ9 JJJJJJJJJJJJJJJJJJJJJJJJJ0 JJJJJJJJJJJJJJJJJJJJJJJJJ1 JJJJJJJJJJJJJJJJJJJJJJJJJ2 JJJJJJJJJJJJJJJJJJJJJJJJJ3 JJJJJJJJJJJJJJJJJJJJJJJJJ4 JJJJJJJJJJJJJJJJJJJJJJJJJ5 IIIIIIIIIIIIIIIIIHHHHHHHH6 IIIIIIIIIIIIIIIIIHHHHHHHH7 IIIIIIIIIIIIIIIIIHHHHHHHH8 IIIIIIIIIIIIIIIIIHHHHHHHH9 IIIIIIIIIIIIIIIIIHHHHHHHH0 IIIIIIIIIIIIIIIIIHHHHHHHH1 IIIIIIIIIIIIIIIIIHHHHHHHH2 IIIIIIIIIIIIIIIIIHHHHHHHH3 IIIIIIIIIIIIIIIIIGGGGGDDD4 IIIIIIIIIIIIIIIIIGGGGGDDD5 IIIIIIIIIIIIIIIIIGGGGGDDD6 IIIIIIIIIIIIIIIIIGGGGGCCA7 IIIIIIIIIIIIIIIIIGGGGGCCB8 IIIIIIIIIIIIIIIIIEEEEFFFF9 IIIIIIIIIIIIIIIIIEEEEFFFF0 IIIIIIIIIIIIIIIIIEEEEFFFF1 IIIIIIIIIIIIIIIIIEEEEFFFF2 Input: 52 5 Output: 14 (1x1, 1x1, 2x2, 2x2, 5x5, 5x5, 5x5, 5x5, 5x5, 5x5, 5x5, 5x5, 5x5, 5x5) 12345 EEEEE1 EEEEE2 EEEEE3 EEEEE4 EEEEE5 FFFFF6 FFFFF7 FFFFF8 FFFFF9 FFFFF0 GGGGG1 GGGGG2 GGGGG3 GGGGG4 GGGGG5 HHHHH6 HHHHH7 HHHHH8 HHHHH9 HHHHH0 IIIII1 IIIII2 IIIII3 IIIII4 IIIII5 JJJJJ6 JJJJJ7 JJJJJ8 JJJJJ9 JJJJJ0 KKKKK1 KKKKK2 KKKKK3 KKKKK4 KKKKK5 LLLLL6 LLLLL7 LLLLL8 LLLLL9 LLLLL0 MMMMM1 MMMMM2 MMMMM3 MMMMM4 MMMMM5 NNNNN6 NNNNN7 NNNNN8 NNNNN9 NNNNN0 CCDDA1 CCDDB2 Input: 101 99 Output : 11 (1x1, 12x12, 12x12, 12x12, 16x16, 16x16, 16x16, 36x36, 49x49, 50x50, 51x51) 123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKBBBBBBBBBBBBHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH1 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKBBBBBBBBBBBBHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH2 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKBBBBBBBBBBBBHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH3 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKBBBBBBBBBBBBHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH4 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKBBBBBBBBBBBBHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH5 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKBBBBBBBBBBBBHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH6 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKBBBBBBBBBBBBHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH7 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKBBBBBBBBBBBBHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH8 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKBBBBBBBBBBBBHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH9 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKBBBBBBBBBBBBHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH0 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKBBBBBBBBBBBBHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH1 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKBBBBBBBBBBBBHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH2 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKCCCCCCCCCCCCHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH3 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKCCCCCCCCCCCCHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH4 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKCCCCCCCCCCCCHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH5 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKCCCCCCCCCCCCHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH6 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKCCCCCCCCCCCCHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH7 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKCCCCCCCCCCCCHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH8 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKCCCCCCCCCCCCHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH9 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKCCCCCCCCCCCCHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH0 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKCCCCCCCCCCCCHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH1 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKCCCCCCCCCCCCHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH2 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKCCCCCCCCCCCCHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH3 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKCCCCCCCCCCCCHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH4 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKDDDDDDDDDDDDHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH5 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKDDDDDDDDDDDDHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH6 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKDDDDDDDDDDDDHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH7 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKDDDDDDDDDDDDHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH8 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKDDDDDDDDDDDDHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH9 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKDDDDDDDDDDDDHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH0 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKDDDDDDDDDDDDHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH1 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKDDDDDDDDDDDDHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH2 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKDDDDDDDDDDDDHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH3 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKDDDDDDDDDDDDHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH4 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKDDDDDDDDDDDDHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH5 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKDDDDDDDDDDDDHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH6 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGG7 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGG8 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGG9 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGG0 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGG1 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGG2 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGG3 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGG4 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGG5 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGG6 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGG7 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGG8 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGG9 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGG0 KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGG1 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJAEEEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFGGGGGGGGGGGGGGGG2 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII3 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII4 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII5 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII6 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII7 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII8 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII9 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII0 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII1 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII2 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII3 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII4 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII5 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII6 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII7 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII8 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII9 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII0 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII1 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII2 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII3 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII4 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII5 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII6 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII7 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII8 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII9 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII0 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII1 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII2 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII3 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII4 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII5 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII6 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII7 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII8 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII9 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII0 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII1 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII2 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII3 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII4 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII5 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII6 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII7 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII8 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII9 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII0 JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII1 */ // Function to find the greatest common // denominator between the two numbers. // Make a mutable copy of the numbers and // while the second isn't zero, make the // first equal to the second & the second // the remainder of the original first divided // by the original second. fun gcd(first: Int, second: Int): Int { var one = first var two = second while (two > 0) one = two.also { two = one%two } return one } // gcd // Data class for a carpet holding it's // dimension. data class Carpet(val size: Int) { // Overriden function to provide the // dimension. override fun toString() = "${size}x$size" } // Carpet // List of saved rectangles with their best // carpet covering to save regenerating the // answer. val maximum = 55 val saved = Array(maximum) { Array?>(maximum) { null } } // Function to return the carpet area stored // in the list. fun area(list: MutableList) = list.sumBy { element -> element.size*element.size } // Recursive function to process the squares // in a rectangle returning a list of carpet // squares. fun test(length: Int, width: Int): MutableList = // If there is no rectangle, return an // empty list. if (length < 1 || width < 1) MutableList(0) { Carpet(0) } // Otherwise, if there isn't the list // already calculated, figure it out. else if (length >= maximum || width >= maximum || saved[length][width] == null) { // Calculate the greatest common // denominator and our initial guess // for best. For half the larger // dimension down to one, try spliting // the rectangle up vertically & // horizontally to find a better // combination. val value = gcd(length, width) var best = MutableList(length*width/ (value*value)) { Carpet(value) } var size = Math.max(length, width)/2+1 while (--size > 0) { // Split vertically into a square // and two remaining rectangles. The // rectangles are processed // recursively. If the result is the // best seen so far and all of the // area was filled, hold it as our // best. // +--+--+ // |S | | // +--+R1| // |R2| | // +--+--+ var attempt = MutableList(1) { Carpet(size) } attempt.addAll(test(length, width-size)) attempt.addAll(test(length-size, size)) if (best.size > attempt.size && area(attempt) == length*width) best = attempt // Split horizontally into a square // and two remaining rectangles. The // rectangles are processed // recursively. If the result is the // best seen so far and all of the // area was filled, hold it as our // best. // +--+--+ // |S |R2| // +--+--+ // | R1 | // +-----+ attempt = MutableList(1) { Carpet(size) } attempt.addAll(test(length-size, width)) attempt.addAll(test(size, width-size)) if (best.size > attempt.size && area(attempt) == length*width) best = attempt // The 13x11 solution shown above // requires a different pattern with // a filler square. You still split // vertically or horizontally, but // you now have two squares and three // remaining rectangles. The second // square is smaller than the first // so for one less than the first // square down to one, try spliting // the rectangle up vertically & // horizontally to find a better // combination. var middle = size while (--middle > 0) { // Split horizontally into two squares // and three remaining rectangles. // The rectangles are processed // recursively. If the result is the // best seen so far and all of the // area was filled, hold it as our // best. // +-----+--+ // | S | | // +--+--+R1| // | |F | | // |R3+--+--+ // | | R2 | // +--+-----+ attempt = MutableList(1) { Carpet(size) } attempt.add(Carpet(middle)) attempt.addAll(test(size+middle, width-size)) attempt.addAll(test( length-size-middle, width-size+middle)) attempt.addAll(test(length-size, size-middle)) if (best.size > attempt.size && area(attempt) == length*width) best = attempt // Split vertically into two squares // and three remaining rectangles. // The rectangles are processed // recursively. If the result is the // best seen so far and all of the // area was filled, hold it as our // best. // +----+-----+ // | | R1 | // | S +--+--+ // | |F | | // +----+--+R2| // | R3 | | // +-------+--+ attempt = MutableList(1) { Carpet(size) } attempt.add(Carpet(middle)) attempt.addAll(test(size-middle, width-size)) attempt.addAll(test( length-size+middle, width-size-middle)) attempt.addAll(test(length-size, size+middle)) if (best.size > attempt.size && area(attempt) == length*width) best = attempt } // while } // while // If the list can be saved, do so. // In either case, return the answer. if (length < maximum && width < maximum) saved[length][width] = best best // Otherwise, we have already figured out // the answer so return it. } else saved[length][width]!! // Function to process a rectangle displaying // it and it's result. The resulting list // gets sorted before display. fun process(length: Int, width: Int) { println("Input: $length $width") val list = test(length, width) list.sortBy { element -> element.size } println("Output: ${list.size} $list\n") } // process // Main function for the challenge. fun main(args: Array) { // Try reading a rectangle's dimension from // the user and process it causing an // exception for invalid length or width. try { val input = readLine()!!.split(" ").map { it.toInt() } if (input.size != 2 || input[0] < 1 || input[1] < 1) throw IllegalArgumentException( "Bad input!") process(input[0], input[1]) // On exception, complain and process the // test cases. } catch (error: Throwable) { println("Bad input using defaults!") for ((length, width) in listOf(listOf(3, 5), listOf(7, 8), listOf(2, 8), listOf(13, 11), listOf(22, 29))) process(length, width) } // try } // main

carpet ch