TopCoder

hxppythxught
Being intimate with yourself... Finding new horizons... And having fun!

User's AC Ratio

75.0% (12/16)

Submission's AC Ratio

47.5% (114/240)

Tags

Description

據說每年臺大資工系都會舉辦一場現充派對,要報名派對的人們必須 $K$ 個人一組一起報名,並且在進入派對會場時,每個人會得到一張名牌,上面記錄著其組別編號 $g_i$。

今年的現充派對正如火如荼的舉行著,在派對中大家會烤著肉喝著酒唱著歌,充分發揮社交能量。正當大家玩得盡興時,突然有一張紙條出現在各組別的桌子上,上面寫著這樣的一段文字:

每讀君子文,
心生無窮羨。
富貴而貌美,
益友處處見。
博學亦多聞,
良言句句典。
鄙人鄉下來,
才疏而學淺。
只識牛犁田,
不見幾世面。
閣下桃花旺,
佳人千百艷。
在下何能比,
偶囁己拙見。
故作與君識,
胡言一二遍。

在派對上發送這樣的紙條是一件相當危險的事情,因為臺大資工系的現充們將同時發揮裝弱的本領,開始假裝自己是邊緣人,破壞世界的和平及秩序。正當總召緊張的清點人數時,他們發現目前在派對會場的人數 $N$ 竟然是某個某個 $K$ 的倍數加上一,也就是說,有一名奇怪的沒有組別的不是現充的邊緣人混進來了。亂發這種紙條只有可能是邊緣人作的事,這個人罪大惡極,總召決定開始檢查每個人的名牌上的組別編號,並且他們決定請同樣是現充的你,寫一支程式幫忙找出那一位混進來的邊緣人其偽造的名牌上的組別編號是多少。

Input Format

輸入的第一行包含兩個整數 $N, K$,以一個空白隔開,表示目前派對裡的人數以及每一組的人數。第二行包含 $N$ 個整數 $g_i$,表示每個人名牌上的組別編號。

  • $2 \le K \le 10$
  • $K+1 \le N \le 2 \times 10^ 7$
  • $1 \le g_i \le 10^ 9$
  • 保證存在恰好一個整數 $x$,其出現在 $g_i$ 的次數恰為 $K$ 的倍數加上一;且對於其他非 $x$ 的整數,其出現在 $g_i$ 的次數恰為 $K$ 的倍數

Output Format

輸出一個整數,為混進來的邊緣人其偽造的名牌上的組別編號。

Sample Input 1

7 2
1 2 3 8 3 2 1

Sample Output 1

8

Sample Input 2

10 3
7 7 7 2 2 2 2 7 7 7

Sample Output 2

2

Hints

本題的輸入量較大,以下提供一個較為快速的讀入非負整數的函數。呼叫 nextint() 將會回傳標準輸入中下一個整數,如果已經讀完所有輸入,則會回傳 $0$。

#include <cstdio>
inline char readchar()
{
    const int S = 1 << 20;
    static char buf[S], *p = buf, *q = buf;
    if (p == q && (q = (p = buf) + fread(buf, 1, S, stdin)) == buf) return EOF;
    return *p++;
}

inline int nextint()
{
    int x = 0, c = readchar();
    while ((c < '0' || c > '9') && c != EOF) c = readchar();
    while ('0' <= c && c <= '9') x = (x << 3) + (x << 1) + (c ^ '0'), c = readchar();
    return x;
}

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資。 0
2 0~14 無特別限制。 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 4096 65536 1 2
1 1000 4096 65536 1 2
2 1000 4096 65536 2
3 1000 4096 65536 2
4 1000 4096 65536 2
5 1000 4096 65536 2
6 1000 4096 65536 2
7 1000 4096 65536 2
8 1000 4096 65536 2
9 1000 4096 65536 2
10 1000 4096 65536 2
11 1000 4096 65536 2
12 1000 4096 65536 2
13 1000 4096 65536 2
14 1000 4096 65536 2