trang chủ / bài tập / 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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0