切換
舊版
前往
大廳
主題

ZeroJudge - e599: 10813 - Traditional BINGO 解題心得

Not In My Back Yard | 2020-01-11 23:16:31 | 巴幣 0 | 人氣 569

題目連結:


題目大意:
給定一正整數 n ,代表有 n 組測試資料。每組第一~五列分別給定 5 、 5 、 4 、 5 、 5 個正整數,代表一張賓果卡。而賓果卡的第一行(注意,不是列)會出現 1 ~ 15 、第二行出現 16 ~ 30 、第三行出現 31 ~ 45 、第四行出現 46 ~ 60 、第五行為 61 ~ 75 ,而賓果卡的中間有一個空白處可以變成任何數字(更正:本格可以在任意時間的時候標記為「出現」)

接著給定 75 個正整數,代表一種數字 1 ~ 75 的一種排列。試問到輸入到第幾個數字的時候,該張賓果卡可以喊「BINGO」。賓果的條件為行、列或是對角線的五個數字皆有出現過。

輸出格式參見範例輸出。



範例輸入:
1
10 17 39 49 64
12 21 36 55 62
14 25    52 70
7 19 32 56 68
5 24 34 54 71
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75


範例輸出:
BINGO after 14 numbers announced


解題思維:
本題就是直接每輸入一個數字,就檢查一次賓果卡的每一列、每一行以及兩條對角線,是否有任何一條上有五個數字都有出現過。而中間可以直接變成任何數字,所以該格可以直接當作出現過了。

一旦檢查達到賓果的條件,就輸出該數字是第幾個喊的數字,即是所求。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

胖胖貓
『賓果卡的中間有一個空白處,可以變成任何數字。』總覺得這句話的意思應該是從不曾出現過的數字且能選的號碼落在31-45中選擇一個填入才對...,賓果沒有填入相同數字的吧...
2020-01-13 01:06:01
Not In My Back Yard
因為這句話是我憑藉著以前解 UVa 原題所留下來的記憶。而我跑去確認了一下 uDebug 發現以下測資:

1 16 31 46 61
2 17 32 47 62
3 18 48 63
4 19 34 49 64
5 20 35 50 65
3 18 48 63 61 31 46 16 2 32
47 62 1 17 49 65 4 19 34 64
5 20 35 50 6 7 8 9 10 11
12 13 14 15 21 22 23 24 25 26
27 28 29 30 33 36 37 38 39 40
41 42 43 44 45 51 52 53 54 55
56 57 58 59 60 66 67 68 69 70
71 72 73 74 75

而答案是 BINGO after 4 numbers announced

所以中間那格式真的可以變成所有數字的。而回去看題目原文「A player may mark the centre FREE SPACE at any time.」,代表玩家可以在任意時間標記中間的格子。

所以比較大的問題是本人的敘述,因為實際上中間的格子並沒有變成任何數字。它單純只是可以在喊任何數字的時候標記而已。

感謝提出意見XD
2020-01-13 14:06:00

相關創作

更多創作