Techfest Coding Challenge
Shubham recently recalled that solving puzzles was one of his favorite childhood activities. But Shubham did not have any of the puzzle boxes left. He came up with a brilliant idea of making his own puzzle by taking his own large piece of paper with some picture and cut it into many smaller rectangular pieces, then mix them and solve the resulting puzzle, trying to piece together the picture; instead of buying ready-made puzzles. He later realised that the resulting task is even more challenging than the classic puzzle: now all the fragments have the same rectangular shape, and one can assemble the puzzle by only relying on the picture drawn on the pieces. Since Shubham cuts the picture first by horizontal cuts with the pitch of X, then with by vertical cuts with the pitch of Y, all puzzle pieces turn out to be of the same size (X × Y). If we denote the initial size of the picture as A × B, then A must be divisible by X and B must be divisible by Y (X and Y are integer numbers). However, not every such cutting of the picture will result in a good puzzle. Shubham finds a puzzle good if no two pieces in it are the same (It is allowed to rotate the pieces when comparing them, but it is forbidden to turn them over). Your task is to count for a given picture the number of good puzzles that you can make from it, and also to find the puzzle with the minimal piece size.
The first line contains two numbers A and B which are the sizes of the picture. They are positive integers not exceeding 20. Then follow A lines containing B symbols each, describing the actual picture. The lines only contain uppercase English letters.
In the first line print the number of possible good puzzles (in other words, the number of pairs (X, Y) such that the puzzle with the corresponding element sizes will be good). This number should always be positive, because the whole picture is a good puzzle itself. In the second line print two numbers — the sizes X and Y of the smallest possible element among all good puzzles. The comparison is made firstly by the area XY of one element and secondly — by the length X.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions