潔癖朋友吃壽司卷

02-04

這是很久遠的問題了, 認識我的人應該都聽過這題的樣子. 但是這次在伯克利碰到兩個CS本科生@林習習和 @Estheroy, 給了他們這個題. 因為我常用的另一個題他們竟然聽過了.

我喜歡這種題當做面試題. 因為這題可以看人解決問題的思路.

現實模型

有兩種壽司卷, a個紅色壽司卷和b個藍色壽司卷(a和b都可以被2整除). 填滿在一個nxm的矩陣里. 所以nxm=a+b.

兩個有潔癖的人分壽司卷. 因為壽司卷放的很緊. 用筷子夾的時候要麼碰到上下兩個壽司卷(如果存在的話), 要麼會碰到左右兩個壽司卷(如果存在的話). 而另一個人是不會吃這個人碰到的壽司卷的.

設計一個演算法. 告訴這兩個人如何輪流夾壽司卷. 使得每個人都吃到a/2個紅色壽司卷b/2個藍色壽司卷.

某個解答的方法

我們假設 $nleq m$ .

讓 $r_i$ 為第 $i$ 列的紅色壽司的個數. 假設對於任意 $i$ , $r_ileq r_{i+1}$ . 因為我們暫時不會橫著夾任何東西, 所以可以有這樣的assumption.

我們的目標是讓兩個人取走一樣多的行.

case 1: 存在 $ineq j$ 使得 $r_i=r_j$ . 這樣兩個人各取一列. （這包含了n+1<m的case) 後面case假設case 1不成立.

case 2: 如果 $n+1=m$ , $mgeq 4$ . 則對於任意 $i$ , $r_i = i-1$ . 所以我們有 $r_1 + r_m = r_2 + r_{m-1}$ .

case 3: 如果 $n=m$ , $mgeq 4$ , $r_1neq 0$ . 則對於任意 $i$ , $r_i=i$ . $r_1 + r_m = r_2 + r_{m-1}$ .

case 4: 如果 $n=m$ , $mgeq 4$ , $r_1=0$ . 則矩陣里每行都有一個藍色的壽司卷. 我們可以紅色藍色對調並且旋轉一下矩陣獲得case 3.

case 5. n和m之間必須有一個是偶數. 現在只剩下要考慮 $(n,m)$ 為下列三種情況 ${(1,2),(2,2),(2,3)}$ . 利用a,b都是偶數這個屬性. 可以搞定最後的幾個可能.

如果足夠careful可以利用這個寫出一個O(nm)的演算法... 有點麻煩就是了...

更多問題:

題圖是遊戲 Asamis Sushi Shop.