e970 - 1. 粉專抽獎 (Lucky Draw)

🔗 前往 ZeroJudge 原題

題目描述

題目描述一個 Facebook 粉絲團的抽獎演算法。給定留言數量 N 和 N 個隨機數字，根據演算法步驟計算中獎留言的索引值和對應的隨機數。

解題思路

題目要求模擬抽獎演算法。首先讀取留言數量 N 和 N 個隨機數字。然後，使用最後一個數字作為基數，找出除以基數餘數為 1 的索引值。將這些索引值對應的隨機數字加總，再將加總結果除以留言數量 N，得到的餘數即為中獎留言的索引值。如果餘數為 0，則中獎留言的索引值為 N。最後，輸出中獎留言的索引值和對應的隨機數。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(n)

程式碼

#include <stdio.h>
int main(){
	int n;
	scanf("%d",&n);
	int a[n];
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	int b=1,sum=0;
	for(;b<=n;b+=a[n-1])
		sum+=a[b-1];
	printf("%d %d",(sum-1)%n+1,a[(sum-1)%n]);
}