UVa 10038 題解 — C++

此筆記為UVa 10038的題目詳解，包含解題思路、C++範例程式碼。

Jolly Jumpers (ZeroJudge d097.)

題目

有n個整數的序列我們稱為jolly jumper，如果相鄰的2個數其差的絕對值恰好為1到n-1。例如：

1 4 2 3

就是jolly jumper（n=4）。因為相鄰2數的差的絕對值為3,2,1，就是1到n-1。但是

1 4 2 -1 6

不是jolly jumper（n=5）。因為相鄰2數的差的絕對值為3,2,3,7，並非1到n-1。

你的任務是寫一個程式來判斷一個整數序列是否為jolly jumper。

輸入 / 輸出說明

輸入說明	輸出說明

解題思路

我透過 a1、a2 儲存相鄰的兩個數字，並用 b 代表相鄰兩數的差的絕對值，以及使用 a 陣列表示 1 ≤ i ≤ n - 1 是否有相鄰兩數的差的絕對值 = i。

若 1 ≤ b ≤ n - 1 的範圍內且 a[b] = 0，則將 t + 1，最後如果 t = n - 1 就是 jolly jumper，反之則不是 jolly jumper。

範例程式碼

#include <bits/stdc++.h>
using namespace std;

int main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i;
	int n, a1, a2;
	
	while (cin >> n) {
		int a[n+1]={}, b, t = 0;
		
		cin >> a1;
		
		for (i=1;i<n;i++) {
			cin >> a2;
			
			b = abs(a1-a2);
			
			if (a[b] == 0 && b >= 1 && b < n) {
				a[b] = 1;
				t++;
			}
			
			a1 = a2;
		}
		
		if (t == n - 1)
			cout << "Jolly" << endl;
		else
			cout << "Not jolly" << endl;
	}

	return 0;
}

運行結果

AC (5ms, 352KB)

tags: CPE 1星

查看更多資訊請至：https://www.tseng-school.com/