TIOJ-1614

2qbingxuan

2019-12-06

販賣機耶

https://tioj.ck.tp.edu.tw/problems/1614

Description

蝴蝶在路旁玩壞一台販賣機，它一次只能投一枚硬幣（故障？）。
重點是：投進一枚x元的硬幣，然後按退幣鈕，居然會吐出一枚價值 $f(x)$ 的硬幣耶！
更神秘的是，天才蝴蝶已經發現 $f(x) = x + (x-b_1) (x-b_2) (x-b_3) \dots (x-b_m)$。
現在蝴蝶手上有 $n$ 枚硬幣，分別是 $a_1 \dots a_n$，請問蝴蝶投進去會賺的硬幣有幾枚？

Solution

題目就是問$f(x)-x = \prod\limits _ {i=1}^m (x-b_i)$是不是正的
然後看有幾個$b_i$小於$x$就可以知道乘積的正負號了(國中數學??)
另外注意$x - b_i = 0$的case，然後也不要亂 unique ，要保持個數的奇偶性。

AC code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
const int N = 100025;

int n,m,a[N],b[N];
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];
    sort(b,b+m);
    int ans = 0;
    for(int i = 0; i < n; i++) {
        int j = lower_bound(b,b+m,a[i]) - b;
        if(!(a[i] == b[j] || (j&1))) ans++;
    }
    cout << ans << '\n';
}