d396: 00524 - Prime Ring Problem

出處：UVA524

檢測平台：https://zerojudge.tw/ShowProblem?problemid=d396

有一個環（ring）是由 n 個圈圈所組成的（在這裡 n 一定是個偶數），我們想要把 1 到 n 的自然數各放到一個圈圈中，使得相鄰 2 個圈圈中的數的和一定是質數。下圖為 n=6 的情形。

每組測試資料只包含一整數 n（0 < n <= 16）

看到上面的輸入範圍就決定暴力DFS解了，但為了幫忙加速一下，還是建立一個1~31(15+16)的質數表來加速運算。

程式碼如下：

如果有任何疑問歡迎留言或私訊討論。

prime = [0 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0
 , 1 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 
 0 , 0 , 1 , 0 , 1]

a = []
n = 0
index = 0
def dfs(d , d1 , count , ss):
  if prime[d+d1] == 0: return
  if count == n:
    if prime[1 + d1] == 1:
      print(ss)
    return

  global a
  for i in range(2 , n+1):
    if a[i] == 1: continue
    a[i] = 1
    dfs(d1 , i , count+1 , ss + str(i) + " ")
    a[i] = 0
  


try:
  while True:
    ans= ""
    a = []
    index += 1
    n = int(input())
    a = [0]*(n+1);
    ans = "1 "
    a[1] = 1
    print("Case " + str(index) + ":" )
    for i in range(2 , n+1 , 2):
      a[i] = 1
      #ans += str(i) + " "
      dfs(1 , i , 2 , ans + str(i) + " ")
      a[i] = 0
      
except EOFError:pass

c292: APCS2017-0304-3數字龍捲風

 題目來源：APCS2017-0304

檢測平台：https://zerojudge.tw/ShowProblem?problemid=c292

首先先定義四個方向的X、Y偏移量：

EX.

a = [[0 , -1] , [-1 , 0] , [0 , 1] , [1 , 0]]

這題乍看可能不好著手，這時需要做的就是好好檢視測試數據，

仔細觀察測資，你會發現基本上每個方向移動的步數為1,1,2,2,3,3......

好囉，程式碼如下：

如果有問題歡迎留言或私訊討論囉。

a = [[0 , -1] , [-1 , 0] , [0 , 1] , [1 , 0]]

n = int(input())
d = int(input())
t = []
for i in range(n):
  t.append([int(i) for i in input().split()])

x = y = int(len(t) / 2)
s = str(t[x][y])

end = 0
for i in range(1,len(t)+1):
  if end == 1: break
  for k in range(0 , 2):
    if end == 1:break
    for j in range(i):
      x += a[d][0]
      y += a[d][1]
      if x < 0 or y < 0 or x == len(t) or y == len(t):
        end = 1
        break;
      s += str(t[x][y])
    d += 1
    d %= 4
print(s)

e621: 1. 免費停車 (Free Parking)

題目來源：https://toi-reg.csie.ntnu.edu.tw/question/201910/B1-FreeParking.pdf

線上檢驗：https://zerojudge.tw/ShowProblem?problemid=e621

求範圍區間內，不能被指定數字整除的數字，

要注意的是開頭跟結尾兩個數字都不能算進來。

程式碼如下：

有問題歡迎留言或傳訊討論。

n = int(input())
while n > 0:
  n -= 1
  ans = ""
  s,e,d = tuple([int(i) for i in input().split()])
  for i in range(s+1 , e):
    if i % d != 0:
      ans += str(i) + " "
  if ans != "":
    print(ans)
  else: 

print("No free parking spaces.") 

e623: 2. PPAP

題目來源：https://toi-reg.csie.ntnu.edu.tw/question/201910/B2-PPAP.pdf

檢測系統：https://zerojudge.tw/ShowProblem?problemid=e623

四種物品循環，每新的一輪重複次數+1，所以分別需要4、8、12、.....。

這題測資不大，可以直接用遞迴或迴圈，先算出輸入的測資需要循環幾次，

再找出該次循環內的物品。

程式碼如下：

有問題歡迎留言或來信討論。

n = int(input())
count = 0
while n > count * 4:
  n -= count * 4
  count += 1

index = int(n / count)
if n % count != 0:
  index += 1

a = ["Pen" , "Pineapple" , "Apple" , "Pineapple pen"]
print(a[index-1])

f259: 皓宇的青蛙

 題目來源：高中生程式解題系統

https://zerojudge.tw/ShowProblem?problemid=f259

這題測資量很大，c++的話可以用set來處理，

PYTHON我用set或dict都是超時，

所以這題我選用c++來解題。

額外要注意的是資料量真的很大，

所以記得加上cin.tie(0),cin.sync_with_stdio(0)

程式碼如下，有問題歡迎留言、來信、私訊討論

#include <iostream>
#include <set>

using namespace std;

int main()
{
    cin.tie(0) , cin.sync_with_stdio(0);
    string s;
    set<string> sets;
    while(cin >> s) {
        if(sets.count(s) == 1) {
            cout << 1 <<"\n";
        }
        else {
            sets.insert(s);
            cout << 0 << "\n";
        }
    }

    return 0;
}

c315: I, ROBOT 前傳

題目來源：https://zerojudge.tw/ShowProblem?problemid=c315

這題只要對於條件判斷式的運用有一定的熟悉度，相信不會太困難，而我這題選擇用switch case的方式來解決，概念上差不多。

算是初期很好的練習題目。 

以下附上我的程式，有任何問題歡迎留言或私訊我。 

#include <iostream>
/*4
0 10
1 4
2 3
3 6*/

using namespace std;

int main()
{
    int x = 0 , y = 0;
    int n , m , o;
    cin >> n;
    while(n--) {
        cin >> m >> o;
        switch(m) {
            case 0:
                y += o;
                break;
            case 1:
                x += o;
                break;
            case 2:
                y -= o;
                break;
            case 3:
                x -= o;
                break;
        }
        
    }
    cout << x << " " << y;

    return 0;
}