程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Codeforces 509D. Restoring Numbers 構造+數學

Codeforces 509D. Restoring Numbers 構造+數學

編輯:關於C++

 

 

 

D. Restoring Numbers time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Vasya had two arrays consisting of non-negative integers: a of size n and b of size m. Vasya chose a positive integer k and created an n?×?m matrix v using the following formula:

\

Vasya wrote down matrix v on a piece of paper and put it in the table.

A year later Vasya was cleaning his table when he found a piece of paper containing an n?×?m matrix w. He remembered making a matrix one day by the rules given above but he was not sure if he had found the paper with the matrix v from those days. Your task is to find out if the matrix w that you've found could have been obtained by following these rules and if it could, then for what numbersk,?a1,?a2,?...,?an,?b1,?b2,?...,?bm it is possible.

Input

The first line contains integers n and m (1?≤?n,?m?≤?100), separated by a space — the number of rows and columns in the found matrix, respectively.

The i-th of the following lines contains numbers wi,?1,?wi,?2,?...,?wi,?m (0?≤?wi,?j?≤?109), separated by spaces — the elements of the i-th row of matrix w.

Output

If the matrix w could not have been obtained in the manner described above, print "NO" (without quotes) in the single line of output.

Otherwise, print four lines.

In the first line print "YES" (without quotes).

In the second line print an integer k (1?≤?k?≤?1018). Note that each element of table w should be in range between 0 and k?-?1 inclusively.

In the third line print n integers a1,?a2,?...,?an (0?≤?ai?≤?1018), separated by spaces.

In the fourth line print m integers b1,?b2,?...,?bm (0?≤?bi?≤?1018), separated by spaces.

Sample test(s) input
2 3
1 2 3
2 3 4
output
YES
1000000007
0 1 
1 2 3 
input
2 2
1 2
2 0
output
YES
3
0 1 
1 2 
input
2 2
1 2
2 1
output
NO
Note

By \ we denote the remainder of integer division of b by c.

It is guaranteed that if there exists some set of numbers k,?a1,?...,?an,?b1,?...,?bm, that you could use to make matrix w, then there also exists a set of numbers that meets the limits 1?≤?k?≤?1018, 1?≤?ai?≤?1018, 1?≤?bi?≤?1018 in the output format. In other words, these upper bounds are introduced only for checking convenience purposes.



 

 

/**
 * Created by ckboss on 15-4-2.
 */

import java.util.*;

public class CF509D {

    int n,m;
    long[][] w;
    long[] a,b;

    long gcd(long a,long b){
        if(b==0) return a;
        return gcd(b,a%b);
    }

    CF509D(){
        Scanner in = new Scanner(System.in);
        n=in.nextInt(); m=in.nextInt();
        w=new long[n][m];
        a=new long[n];
        b=new long[m];
        for(int i=0;i=g){
                    flag=false; break;
                }
            }
        }
        if(flag==false){
            System.out.println("NO");
        }
        else{
            System.out.println("YES");
            System.out.println(g);
            for(int i=0;i

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved