54B

时间:2022-09-07 15:53:14

The Hedgehog recently remembered one of his favorite childhood activities, — solving puzzles, and got into it with new vigor. He would sit day in, day out with his friend buried into thousands of tiny pieces of the picture, looking for the required items one by one.

Soon the Hedgehog came up with a brilliant idea: instead of buying ready-made puzzles, one can take his own large piece of paper with some picture and cut it into many small rectangular pieces, then mix them and solve the resulting puzzle, trying to piece together the picture. 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 only relying on the picture drawn on the pieces.

All puzzle pieces turn out to be of the same size X × Y, because the picture is cut first by horizontal cuts with the pitch of X, then with vertical cuts with the pitch of 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. The Hedgehog 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.

Input

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.

Output

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.

Examples
Input
2 4
ABDC
ABDC
Output
3
2 1
Input
2 6
ABCCBA
ABCCBA
Output
1
2 6
111
枚举边长,然后枚举每个子方块,用hash检查
#include<iostream>
#include<set>
#include<cstdio>
using namespace std;
typedef long long ll;
char board[30][30];
set<ll>used;
int A,B,ans,x,y;
bool check(int x,int y)
{
used.clear();
int t1=A/x,t2=B/y;
for(int i=1;i<=t1;i++)for(int j=1;j<=t2;j++)
{
ll temp[5];
int cnt=0;
for(int i=1;i<5;i++) temp[i]=0;
++cnt;
for(int ii=1;ii<=x;ii++)for(int jj=1;jj<=y;jj++)
{
temp[cnt]*=171;
temp[cnt]+=board[(i-1)*x+ii][(j-1)*y+jj];
}
++cnt;
for(int ii=x;ii>=1;ii--)for(int jj=y;jj>=1;jj--)
{
temp[cnt]*=171;
temp[cnt]+=board[(i-1)*x+ii][(j-1)*y+jj];
}
++cnt;
if(x==y)
{
for(int jj=y;jj>=1;jj--)for(int ii=1;ii<=x;ii++)
{
temp[cnt]*=171;
temp[cnt]+=board[(i-1)*x+ii][(j-1)*y+jj];
}
++cnt;
for(int jj=x;jj>=1;jj--)for(int ii=1;ii<=y;ii++)
{
temp[cnt]*=171;
temp[cnt]+=board[(i-1)*x+ii][(j-1)*y+jj];
}
++cnt;
}
for(int k=1;k<cnt;k++) if(used.count(temp[k])) return false;
for(int k=1;k<cnt;k++) used.insert(temp[k]);
}
return true;
}
int main()
{
cin>>A>>B;
for(int i=1;i<=A;i++)
{
for(int j=1;j<=B;j++)
cin>>board[i][j];
}
x=y=1<<10;
for(int i=A;i>=1;i--)for(int j=B;j>=1;j--)
{
if(A%i==0&&B%j==0) if(check(i,j))
{
ans++;
// cout<<i<<" "<<j<<endl;
if(i*j<x*y) {x=i;y=j;}
else if(i*j==x*y) if(i<x){x=i;y=j;}
}
}
cout<<ans<<endl;
cout<<x<<" "<<y<<endl;
return 0;
}

54B的更多相关文章

  1. ZIP压缩算法详细分析及解压实例解释

    最近自己实现了一个ZIP压缩数据的解压程序,觉得有必要把ZIP压缩格式进行一下详细总结,数据压缩是一门通信原理和计算机科学都会涉及到的学科,在通信原理中,一般称为信源编码,在计算机科学里,一般称为数据 ...

  2. Sql Server 2012新特性 Online添加非空栏位&period;

    我们都知道,Sql Server在一个数据量巨大的表中添加一个非空栏位是比较费心的,缺乏经验的DBA或是开发人员甚至可能鲁莽地直接添加导致阻塞相应业务,甚至可能因为资源欠缺造成实例的全局问题.当然这都 ...

  3. Moon&period;Orm性能报告

    以下为有网友公司的评估测试及使用规范 大家可以下载word看看 http://pan.baidu.com/s/1hquvRuc 一.和ADO.NET进行的压力测试 说明:2000并发用户,此图为一网友 ...

  4. python之路2(基础详解)

    python一切都是对象: 列子:

  5. JAVA 调用matlab 出错总结

    1.Java:Unsupported major.minor version 51.0 (unable to load class 出现该错误是由于class编译器的JDK版本高于运行期的JDK版本. ...

  6. 一种用css实现图片在父框中等比缩放并垂直居中的办法

    一个网页中往往会有很多图片,而网站的编辑上传图片时可能并不一定按照为父框设定的那个宽高来传,这样图片往往会将父框撑开或者被父框截断.一种比较好的解决的办法是这样的: HTML代码结构: <div ...

  7. Struts2&plus;Spring3&plus;Hibernate3&plus;Maven构建&lpar;基于Eclipse&rpar;

    长时间不做后台了,整理一下资料,以便翻阅. Eclipse.JDK安装略…… Maven下载地址:http://maven.apache.org/download.cgi 版本比较新的Eclipse基 ...

  8. 在JasperReport中填充JavaBean(4)

    使用Parameters参数对象传递字符串的示例,本节将演示打印List接口中Userinfo.java实体类的示例,打印的数据源不是来自于Parameters对象,而是JRBeanCollectio ...

  9. Unix&sol;Linux环境C编程入门教程&lpar;1&rpar; Solaris 11 64bit环境搭建

    Unix/Linux版本众多,我们推荐Unix/Linux初学者选用几款典型的Unix/Linux操作系统进行学习. 本文就带大家来安装Solaris 11 64位并且配置好C/C++开发环境 本文所 ...

随机推荐

  1. c&plus;&plus;多态的实现

    在面试中常常会有面试官问道,c++的多态的实现机制.那么,多态到底该如何实现呢? 多态的简单介绍 一般来说,多态分为两种,静态多态和动态多态.静态多态也称编译时多态,主要包括模板和重载.而动态多态则是 ...

  2. 谷歌console开发人员官方文档(注意是谷歌)

    https://developers.google.com/web/tools/chrome-devtools/debug/console/console-ui?hl=en#opening-the-c ...

  3. IE、FF、Safari、OP不同浏览器兼容报告

    IE.FF.Safari.OP不同浏览器兼容报告 1         浏览器内核简介 Trident IE浏览器(GreenBrowser绿色浏览器, 遨游浏览器....都是IE) Geckos Fi ...

  4. hdu----&lpar;2222&rpar;Keywords Search&lpar;trie树&rpar;

    Keywords Search Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)T ...

  5. hdoj 2111 Saving HDU

    Saving HDU Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total ...

  6. 在azure中建立DDC集群

    在Azure上建立DDC集群 建立3台虚拟机作为UCP集群,3台虚拟机作为DTR集群. 资源组:HYD-DockerDateCenter 虚拟机size:DS3 4核14G 系统:ubuntu14.0 ...

  7. 数组查找算法的C语言 实现-----线性查找和二分查找

    线性查找  Linear Search 用户输入学生学号的成绩 二分查找  Binary Search 要求数据表是已经排好序的 程序存在小的瑕疵

  8. js中uuid不被识别

    后台传了uuid值给前台,然后js报错 原因:反正就是js不认你这个字符串,他觉得你这是应该是数字,但是后面想了想,也不是数字啊,然后就不认了. 解决办法:告诉他,为夫这里是字符串.拼接html的时候 ...

  9. iptables防火墙详解(二)

    -- 基于状态的iptables 如果按照tcp/ip来划分连接状态,有11种之多(课后可以自己去读一下相关知识) 但iptables里只有4种状态:ESTABLISHED.NEW.RELATED及I ...

  10. Gym 101889:2017Latin American Regional Programming Contest(寒假自训第14场)

    昨天00.35的CF,4点才上床,今天打的昏沉沉的,WA了无数发. 题目还是满漂亮的. 尚有几题待补. C .Complete Naebbirac's sequence 题意:给定N个数,他们在1到K ...

相关文章