trang chủ / đề bài / clrsym

Đối xứng sạch

Đề bài

Mô tả

Xét một ma trận vuông A kích thước n×n gồm các phần tử 0 và 1. Hàng được đánh số từ 1 đến n từ trên xuống, cột được đánh số từ 1 đến n từ trái sang.

Ma trận A được gọi là sạch (clear) nếu không có hai ô chứa số 1 nào có chung cạnh.

Ma trận A được gọi là đối xứng (symmetrical) nếu nó trùng với chính nó khi lật theo trục ngang và/hoặc trục dọc. Một cách hình thức, với mọi cặp (i,j) thoả 1≤i,j≤n, cả hai điều kiện sau phải thoả:

  • Ai,j=An−i+1,j
  • Ai,j=Ai,n−j+1

Độ sắc (sharpness) của ma trận A là số ô chứa số 1 trong ma trận.

Cho số nguyên x, hãy tìm số nguyên dương n nhỏ nhất sao cho tồn tại một ma trận sạch và đối xứng kích thước n×n có độ sắc đúng bằng x.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên x (1≤x≤100).

Dữ liệu ra

In ra một số nguyên duy nhất — giá trị n nhỏ nhất cần tìm.

Ràng buộc

  • 1≤x≤100

Ví dụ

Input Output Giải thích
4 3 Đặt số 1 tại bốn ô góc của ma trận 3×3 cho ma trận sạch, đối xứng, độ sắc 4.
9 5 Mẫu xen kẽ "bàn cờ" trên ma trận 5×5 cho ta tới 13 ô, ta chỉ giữ lại 9 ô phù hợp để vẫn đối xứng và sạch.
3 5 Không tồn tại ma trận 1×1 hay 3×3 nào sạch + đối xứng và có đúng 3 ô số 1 — ma trận nhỏ nhất phải có cạnh 5.

Bình luận

  • haicuccutdep123
    haicuccutdep123
    đã bình luận 4 months trước

    nice

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0