NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2011高中組初賽
 NPSC 2011 高中組 B.積木封裝

作者 主題: NPSC 2011 高中組 B.積木封裝  (閱讀 2422 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 225
    • 檢視個人資料
NPSC 2011 高中組 B.積木封裝
« 於: 十一月 06, 2012, 05:25:38 pm »

NPSC 2011 高中組 B.積木封裝

說明:給你 N 個由三個 1x1 的正方形組成 L 型的拼圖(或者說2x2的正方形挖掉其中一個1x1的角),請問你能收納這些拼圖的矩形周長最小為多少?(註:拼圖不能重疊)

測資範圍:N<=108

解法:數學推導,因為正方形的周長是最小的,再來就是最接近正方形的矩形,先算出能收納這些拼圖的最小正方形邊長為 N,再檢查 N*N(-1) 的矩形是否能收納,如果可以,則答案是 4*N-2,否則為 4*N。另外,前三個是特例,請直接輸出。

至於當面積剛好為 NxN 或是 N*(N-1) 時,為什麼一定能拼得出來,需要額外的證明。另外,有人可以提拱 N=27 時是如何拼出 9x9 的正方形嗎?

參考程式:(By sagit)
代碼: [選擇]
#include <cstdlib>
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int t, n, q, ans;
    cin >> t;
    while (t--)
    {
        cin >> n;
        switch (n)
        {
            case 1:
                ans=8;
                break;
            case 2:
                ans=10;
                break;
            case 3:
                ans=14;
                break;
            default:
                n*=3;
                q=int(sqrt(double(n)));
                if (n>q*q) q++;
                ans=q*4;
                if (n<=q*(q-1)) ans-=2;
                break;
        }
        cout << ans << endl;
    }
    return 0;
}
« 上次編輯: 十一月 07, 2012, 10:02:54 am 由 sagit »
記錄

ck99126

  • 新手
  • *
  • 文章數: 6
    • 檢視個人資料
Re: NPSC 2011 高中組 B.積木封裝
« 回覆 #1 於: 五月 07, 2013, 02:20:44 pm »

定義:若一面積為S的矩形被「填到最滿」,表示恰可放入floor(S/3)個2*2挖去一格的L形積木。
可運用歸納法來證明N*N(除了N=3)與N*(N+1)的矩形可以被填到最滿,
N要分為奇數與偶數的狀況來討論(這裡的N與原題的N不同)。

證明
一、N*N(除了N=3)的矩形可以被填到最滿
(1) N為奇數且N>3
已知N=5時成立(圖1-1)。
若N=6n+5(其中n>=0)時成立,
則N=6(n+1)+1成立(圖1-3),N=6(n+1)+3也成立(圖1-4)。
再來,若N=6n+3(其中n>=1)時成立,N=6n+5也成立(圖1-5)。
得證:N為奇數且N>3時,可以被填到最滿。

(2)N為正偶數
已知N=2時成立(圖1-2)
若N=6n+2(其中n>=0)時成立,
則N=6n+4成立(圖1-3),N=6(n+1)也成立(圖1-4)。
再來,若N=6n(其中n>=1)時成立,N=6n+2也成立(圖1-5)。
得證:N為正偶數時,可以被填到最滿。

故得證。
最後,由於N=3時無法被填到最滿,
只能透過圖1-6與1-7兩種排法獲得最小周長。

圖1-1  http://goo.gl/eOjjd
圖1-2  http://goo.gl/QC9L9
圖1-3  http://goo.gl/H5UV4
圖1-4  http://goo.gl/HKlh6
圖1-5  http://goo.gl/EPaig
圖1-6  http://goo.gl/Fz03n
圖1-7  http://goo.gl/u7fKf

二、N*(N+1)的矩形可以被填到最滿
(1) N為奇數且N>1
已知N=3時成立(圖2-1)。
若N=6n+3(其中n>=0)時成立,N=6n+5也成立(圖2-3)。
再來,若N=6n+5(其中n>=0)時成立,N=6(n+1)+1也成立(圖2-4)。
再來,若N=6n+1(其中n>=1)時成立,N=6n+3也成立(圖2-5)。
得證:N為奇數且N>1時,可以被填到最滿。

(2)N為正偶數
已知N=2時成立(圖2-2)。
若N=6n+2(其中n>=0)時成立,N=6n+4也成立(圖2-4)。
再來,若N=6n+4(其中n>=0)時成立,N=6(n+1)也成立(圖2-5)。
再來,若N=6n(其中n>=1)時成立,N=6n+2也成立(圖2-3)。
得證:N為正偶數時,可以被填到最滿。

故得證。

圖2-1  http://goo.gl/1K6lV
圖2-2  http://goo.gl/ITbvM
圖2-3  http://goo.gl/vXXCF
圖2-4  http://goo.gl/HltIj
圖2-5  http://goo.gl/VrWUv
記錄

darry140

  • 初級會員
  • **
  • 文章數: 32
    • 檢視個人資料
Re: NPSC 2011 高中組 B.積木封裝
« 回覆 #2 於: 六月 22, 2014, 07:47:05 pm »

記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2011高中組初賽
 NPSC 2011 高中組 B.積木封裝