文档章节

codeforces 495D Sonya and Matrix

o
 osc_odyg6b92
发布于 2018/07/13 16:13
字数 758
阅读 7
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

Since Sonya has just learned the basics of matrices, she decided to play with them a little bit.

Sonya imagined a new type of matrices that she called rhombic matrices. These matrices have exactly one zero, while all other cells have the Manhattan distance to the cell containing the zero. The cells with equal numbers have the form of a rhombus, that is why Sonya called this type so.

The Manhattan distance between two cells (x1,y1) and (x2,y2)is defined as |x1-x2|+|y1-y2|.For example For example, the Manhattan distance between the cells (5,2) and (7,1) equals to |57|+|21|=3.

Note that rhombic matrices are uniquely defined by n, m, and the coordinates of the cell containing the zero.

She drew a n×m rhombic matrix. She believes that you can not recreate the matrix if she gives you only the elements of this matrix in some arbitrary order (i.e., the sequence of nm numbers). Note that Sonya will not give you n and m, so only the sequence of numbers in this matrix will be at your disposal.

Write a program that finds such ann×m rhombic matrix whose elements are the same as the elements in the sequence in some order.

 

Input

The first line contains a single integer t(1≤t≤106) — the number of cells in the matrix.
The second line contains tintegers a1,a2,…,at (0≤ai<t) — the values in the cells in arbitrary order.
Output
In the first line, print two positive integers n and m (n×m=t) — the size of the matrix.
In the second line, print two integers xand y (1≤x≤n, 1≤y≤m) — the row number and the column number where the cell with 0
is located.

If there are multiple possible answers, print any of them. If there is no solution, print the single integer −1.
Examples
Input

20
1 0 2 3 5 3 2 1 3 2 3 1 4 2 1 4 2 3 2 4

Output

4 5
2 2

Input

18
2 2 3 2 4 3 3 3 0 2 4 2 1 3 2 1 1 1

Output

3 6
2 3

Input

6
2 1 0 2 1 2
Output
-1
Note

You can see the solution to the first example in the legend. You also can choose the cell (2,2)
for the cell where 0 is located. You also can choose a 5×4 matrix with zero at (4,2).

In the second example, there is a 3×6 matrix, where the zero is located at (2,3) there.

In the third example, a solution does not exist.

推数学公式

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#pragma comment(linker, "/stck:1024000000,1024000000")
#pragma GCC diagnostic error "-std=c++11"
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define ios() ios::sync_with_stdio(true)
#define INF 0x3f3f3f3f
#define mem(a) (memset(a,0,sizeof(a)))
typedef unsigned long long ull;
typedef long long ll;
//设0的坐标为(x,y)
//左上角的值为a=x+y-2;
//右下角的值为b=n+m-x-y;
//a+b=n+m-2
//b为最大值
//所以有y=n+m-b-x;
//n,m暴力求解x为最小的i使得a[i]!=i*4;
int t,n,m,a[1000006],dp[1000006],x,pos=-1,val_x,val_y;
int main()
{
    scanf("%d",&t);
    for(int i=0;i<t;i++)
    {
        scanf("%d",&x);
        pos=max(pos,x);
        a[x]++;
    }
    printf("\n");
    int flag=0;
    for(int i=1;;i++)
        if(a[i]!=4*i){val_x=i;break;}
    for(int i=1;i<=t;i++)
    {
        if(t%i) continue;
        n=i,m=t/i;
        val_y=n+m-pos-val_x;
        memset(dp,0,sizeof(dp));
        for(int row=1;row<=n;row++)
            for(int col=1;col<=m;col++)
                dp[abs(row-val_x)+abs(col-val_y)]++;
        for(int j=0;j<=pos;j++)
            if(a[j]!=dp[j]) goto eg;
        flag=1;
        eg:;
        if(flag) break;
    }
    if(flag) printf("%d %d\n%d %d\n",n,m,val_x,val_y);
    else printf("-1\n");
    return 0;
}

 

o
粉丝 1
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
点阵字符设计工具--MATPaint

MATPaint 是 MATrix Paint 的缩写,用于设计点阵字符,最高支持 32x32 像素。 该工具的功能: 新建、打开和保持文件 记住上次状态 保持模式为 PNG 图像 为微控制器生成十六进制码 打印预览和...

匿名
2012/11/26
750
0
一种没有语料字典的分词方法

前几天在网上闲逛,看到一篇美文,说的是怎么在没有语料库的情况下从文本中提取中文词汇,理论部分讲得比较多,但都还是很浅显易懂的,其中涉及一部分信息论的理论,其实只要大学开过信息论这...

wyh817
2016/04/26
407
2
利用Camera和Matrix实现有趣的卡片效果

这篇文章主要讲解一个翻转切换内容的卡片效果,主要利用Camera和Matrix来实现,加深对Camera和Matrix的理解~好了,我们先看下效果吧 (动态效果图如无法查看欢迎进github查看~~)(效果的灵感来...

MrZhangKe
2016/08/08
3.1K
2
Pure 编程语言

Pure 是一个高级的函数式编程语言. It offers equational definitions with pattern matching, full symbolic rewriting capabilities, dynamic typing, eager and lazy evaluation, lexica......

匿名
2010/06/10
1.7K
0
数学软件--MATLAB

MATLAB是矩阵实验室(Matrix Laboratory)的简称,是美国MathWorks公司出品的商业数学软件,用于算法开发、数据可视化、数据 分析以及数值计算的高级技术计算语言和交互式环境,主要包括MAT...

匿名
2010/04/28
5.2W
2

没有更多内容

加载失败,请刷新页面

加载更多

SQL 语句大全

点击上方“掌上编程”,选择“置顶或者星标” 优质文章第一时间送达! 一、基础 「1、说明:创建数据库」 CREATE DATABASE database-name    「2、说明:删除数据库」 drop database ...

GeneralMa
昨天
0
0
山东创睦网络科技有限公司:使用Python爬取全球新冠肺炎疫情数据

使用Python爬取全球新冠肺炎疫情数据 导入所需库包 获取实时数据的url 正式编写程序 查看输出结果 导入所需库包 在获取数据之前,我们需要先安装好所需的包requests和pandas: 1.如果是使用p...

osc_qv1fwke0
30分钟前
14
0
如何1年获得别人3年的工作经验(深度好文)

最近有同学问我,为什么你的工作年限不长,技术却这么厉害,我笑了笑,啥也没说。 我不是不想回答,是不知道怎么回答。在他们的定位可能就是,每方面都懂一点,遇到问题能够快速解决,就是比...

zhang_rick
今天
1
0
新基建带动行业

什么是“新基建”? 什么是“新基建”? 根据央视发布的信息来看,其涵盖了5G基站建设、新能源汽车充电桩、大数据中心、人工智能、工业互联网,特高压,城际以及城轨交通,涉及了七大领域和相...

osc_anefoz50
31分钟前
0
0
怕入错行?这群技术人写了本“择业指南”

计算机专业好找工作吗?哪些方向是当前的主流和热门方向呢? 计算机专业的你是不是还在为职业发展纠结犹豫呢? 刚经历完高考选专业的你是不是还在迷茫徘徊呢? 那么福利来啦! 《软件技术职业...

阿里云云栖号
31分钟前
21
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部