e970: 1. 粉專抽獎 (Lucky Draw)
Tags :
Accepted rate : 103人/107人 ( 96% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-04-03 20:30

Content

題目:https://toi-reg.csie.ntnu.edu.tw/question/201904/B1-LuckyDraw(Q).pdf

Facebook 粉絲團若想衝人氣、獲得高點閱率的話,最好的方式就是辦理贈獎活動。有些用心的粉絲團會挑選優秀的留言來給予獎品,但大部分的粉絲專頁都是採用隨機的抽獎方式。

已知某粉專採用的抽獎演算法步驟如下:

1、依照留言量 N 給定 N 個隨機數字。(範例 2 中 N 為 5。)

2、以這 N 個數字當中的最後一個數字 B 做為基數。(範例 2 中 B 為 2。)

3、找出索引值 1, 2, 3, …, N 之中除以基數 B 後餘數為 1 的索引值。(1, 2, …, 5 除以 2 後餘數為 1 的索引值為 1、3 和 5。)

4、索引值 1 對應到第一個隨機數字,索引值 N 對應到最後一個隨機數字,將上 一步驟找出的索引值對應到之隨機數字加總。(範例 2 中索引值 1、3 和 5 對應的隨機數字和為 20 + 7 + 2 = 29。)

5、將此加總後之數字除以留言量 N 所得餘數 M,第 M 則留言即為中獎留言。若 M 為 0 則以最後一則留言中獎。(29 除 5 的餘數為 4。)

Input

總共輸入兩行,第一行輸入一個正整數 N ( 3 ≤ N ≤ 10,000 ),表示共有幾則 留言;第二行輸入 N 個整數 ri (1 ≤i ≤N),代表粉絲專頁給定之隨機值 ( 2 ≤ ri ≤ 1,000 )。

Output

共輸出兩個正整數,以空白區隔,第一個正整數 M ( 1 ≤ M ≤ N ),代表中獎 留言之索引值,第二個數則為此索引值對應到之隨機數。

Sample Input #1
3
1000 100 10
Sample Output #1
1 1000
Sample Input #2
5
20 50 7 100 2
Sample Output #2
4 100
Sample Input #3
10
12 11 10 9 8 7 6 5 4 3
Sample Output #3
10 3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (3%): 1.0s , <1K
公開 測資點#1 (3%): 1.0s , <1K
公開 測資點#2 (3%): 1.0s , <1K
公開 測資點#3 (3%): 1.0s , <1K
公開 測資點#4 (3%): 1.0s , <1K
公開 測資點#5 (3%): 1.0s , <1K
公開 測資點#6 (3%): 1.0s , <1K
公開 測資點#7 (3%): 1.0s , <1K
公開 測資點#8 (3%): 1.0s , <1M
公開 測資點#9 (3%): 1.0s , <1M
公開 測資點#10 (3%): 1.0s , <1M
公開 測資點#11 (3%): 1.0s , <1M
公開 測資點#12 (3%): 1.0s , <1M
公開 測資點#13 (3%): 1.0s , <1M
公開 測資點#14 (3%): 1.0s , <1M
公開 測資點#15 (3%): 1.0s , <1M
公開 測資點#16 (3%): 1.0s , <1M
公開 測資點#17 (3%): 1.0s , <1M
公開 測資點#18 (3%): 1.0s , <1M
公開 測資點#19 (3%): 1.0s , <1M
公開 測資點#20 (3%): 1.0s , <1M
公開 測資點#21 (3%): 1.0s , <1M
公開 測資點#22 (3%): 1.0s , <1M
公開 測資點#23 (3%): 1.0s , <1M
公開 測資點#24 (3%): 1.0s , <1M
公開 測資點#25 (25%): 1.0s , <1K
Hint :
Tags:
出處:
2019年4月TOI練習賽新手組 [管理者:
pcshic (PCSHIC)
]


ID User Problem Subject Hit Post Date
21552
610078 (協同意大利麵的最後希望)
e970
175 2020-06-19 14:39