Subscribed unsubscribe Subscribe Subscribe

0w1

CFR 803 A. Maximal Binary Matrix ( Greedy )

Problem - A - Codeforces

題意:
構造一個字典序最大的 N * N 的 01 矩陣,其中洽有 k 個 1,而且對於主對角線是對稱的。若不存在則輸出 -1。

制約:
The first line consists of two numbers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ 1e6).

解法:
首先若 K > N * N 顯然無解。
接著由上到下依序考慮每一排,先放一個在主對角線上,接著再兩個兩個放在排和列上。

時間 / 空間複雜度:
O( K ) / O( N^2 )

N, K = map( int, input().split() )
if K > N * N:
  exit( print( -1 ) )
G = [ [ 0 for i in range( N ) ] for j in range( N ) ]
for i in range( N ):
  if K == 0: break
  G[ i ][ i ] = 1
  K -= 1
  for j in range( i + 1, N ):
    if K <= 1: break
    G[ i ][ j ], G[ j ][ i ] = 1, 1
    K -= 2
for i in range( N ):
  print( ' '.join( str( v ) for v in G[ i ] ) )