a246: 漣漪
標籤 : 2020 npsc pF 決賽
通過比率 : 3人/3人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-04-19 09:30

內容

某個下雨天,你盯著湖面,發現水面上因為下雨而有了一圈圈的漣漪。不知道為什麼的, 你突然想知道這片水面上共有幾個不同的產生了建設性干涉的位置。

講的稍微白話一點,假設整個水面是個無限寬廣的二維平面,而有個雨滴在時間 0 落在 (x, y) 的位置,則在時間 t 的時候,這個雨滴所產生的圓就是以 (x, y) 為圓心,半徑為 t 的圓。 而產生了建設性干涉的位置就是多於一個圓經過的點。

現在,給定了每個雨滴落在水面上的位置 (xi , yi),並假定每個雨滴都是在時間 0 碰到水面。在這無限可能的所有時間點當中,總會有個時間點 T 使得這個時間點的相異的產生建設性干涉的位置的數量是最多的,你想要知道這個最多的數量會是多少。 然而,因為誰也沒辦法預測雨滴的落點會在哪裡,所以我們會利用以下的 C 程式碼來產生每個雨滴的 xi , yi

unsigned s = initSeed;

int left[30] = { 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1 };

int right[30] = { 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1 };

int gen(){

unsigned t = (s & 13) ^ (s << 13) ^ (s >> 16) ^ (s << 14) ^ (s >> 17) ^ (s << 3) ^ (s >> 6);

unsigned r = (t & 880301) ^ (t >> 11) ^ (t << 11) ^ (t >> 12) ^ (t << 12);

unsigned u = (t & 110029) ^ (t << 21) ^ (t << 14) ^ (t >> 11) ^ (t >> 9);

unsigned h = (s ^ t ^ r ^ u);

for (int i = 0; i < 30; i++) if (left[i]) h ^= (h << i);

for (int i = 0; i < 30; i++) if (right[i]) h ^= (h >> i);

return s = h % 1000000001;

}

int x[50], y[50];

void generateTestcase(int n) {

for (int i = 0; i < n; i++) { 

x[i] = gen() ^ i;

y[i] = gen() ^ gen() ^ i;

}

}

陣列 x 跟 y 中分別存的就是每個點的 xi 跟 yi

輸入說明

輸入共有一行,包含兩個整數,分別是 n 及 initSeed,代表雨滴的數量以及給以上程式用的初始種子。

1.  1 ≤ n ≤ 50

2.  0 ≤ initSeed ≤ 109 

3.  保證輸入中不會有超過一個雨滴落在同一個位置

輸出說明

輸出共有一行,包含一個整數,為最大的產生建設性干涉的位置的數量。

範例輸入 #1
#test input 1:
1 1

#test input 2:
2 998244353
範例輸出 #1
#test output 1:
0

#test output 2:
2
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1K
公開 測資點#9 (5%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1K
公開 測資點#11 (5%): 1.0s , <1K
公開 測資點#12 (5%): 1.0s , <1K
公開 測資點#13 (5%): 1.0s , <1K
公開 測資點#14 (5%): 1.0s , <1K
公開 測資點#15 (5%): 1.0s , <1K
公開 測資點#16 (5%): 1.0s , <1K
公開 測資點#17 (5%): 1.0s , <1K
公開 測資點#18 (5%): 1.0s , <1K
公開 測資點#19 (5%): 1.0s , <1K
提示 :

greedy, math (CF 800)

對於凃某辰而言 (CF 3500)

標籤:
2020 npsc pF 決賽
出處:
npsc [管理者:
haha (大學長)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」