头像

ACSaber




离线:17小时前


最近来访(22)
用户头像
fengwei2002
用户头像
帕格尼尼bin
用户头像
猪啊猪
用户头像
神龙大侠
用户头像
好饿
用户头像
像风逆境
用户头像
BestAc
用户头像
Robin.
用户头像
诺亚方舟.
用户头像
acw_fky
用户头像
铃兰の顶点
用户头像
然后
用户头像
Syw丶
用户头像
白篱
用户头像
InkSans
用户头像
__Reliauk__
用户头像
佐世保の时雨酱
用户头像
codehorse
用户头像
liuxiaocs


ACSaber
3个月前

IDA* 算法

棋盘类问题,问将棋盘变成某个状态需要多少步转换。

由于题目给定了超过 15 步返回 -1,这本身就是一个很明显的引导,显然是 IDA* 算法求解。

重点在于如何定义估值函数,显然应该统计当前棋盘和目标棋盘有多少个不同的点(跳过两个棋盘的空格问题),

然后如果当前空格不在一个位置,就再加一。

这是因为如果其他位置相同,那么空格位置必然相同,因此不能因为两个空格不在一个地方,而算两次成本。

两个棋盘空格位置不同应该只算一次成本。

import java.util.*;
class Main {
    static int x, y;
    static int N = 5;
    static int[][] w = new int[N][N];
    static int[][] target = new int[][]{
        {1,1,1,1,1},
        {0,1,1,1,1},
        {0,0,-1,1,1},
        {0,0,0,0,1},
        {0,0,0,0,0}
    };
    static Set<String> set = new HashSet<>();
    static int[][] dirs = new int[][]{{-2,-1},{-2,1},{-1,2},{-1,-2},{1,-2},{1,2},{2,1},{2,-1}};
    static int f() {
        int ans = 0;
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (target[i][j] == -1 || w[i][j] == -1) continue;
                if (target[i][j] != w[i][j]) ans++;
            }
        }
        if (target[x][y] != -1) ans++;
        return ans;
    }
    static String hash() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                sb.append(w[i][j]);
            }
            sb.append(" ");
        }
        return sb.toString();
    }
    static boolean dfs(int u, int maxDepth) {
        if (u + f() > maxDepth) return false;
        if (f() == 0) return true;
        for (int[] di : dirs) {
            int nx = x + di[0], ny = y + di[1];
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            swap(x, y, nx, ny);
            int a = x, b = y;
            x = nx;
            y = ny;
            if (dfs(u + 1, maxDepth)) return true;
            x = a;
            y = b;
            swap(x, y, nx, ny);
        }
        return false;
    }
    static void swap(int a, int b, int i, int j) {
        int tmp = w[a][b];
        w[a][b] = w[i][j];
        w[i][j] = tmp;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        sc.nextLine();
        while (t-- > 0) {
            set = new HashSet<>();
            for (int i = 0; i < 5; i++) {
                String ss = sc.nextLine();
                char[] cs = ss.toCharArray();
                for (int j = 0; j < 5; j++) {
                    w[i][j] = (cs[j] == '*') ? -1 : (int)(cs[j] - '0');
                    if (w[i][j] == -1) {
                        x = i;
                        y = j;
                    }
                }
            }

            // System.out.println(hash());

            int depth = 0;
            while (depth <= 15 && !dfs(0, depth)) depth++;

            // System.out.println(depth);
            // System.out.println(set.size());

            if (depth > 15) System.out.println(-1);
            else System.out.println(depth);
        }
    }
}



ACSaber
3个月前

IDA* 算法

估值函数:每次移动看做从中间九宫格移除一个数字,然后增加一个数字。即只能改变中间 8 个数字中的一个。

因此可以设计估值函数为 8 - (出现次数最多的数的个数)。

本题另外一个关键点在于对特殊形状的表格的映射存储。

由于给定的形状是 # 型的,但是输入是一维数组的形式进行输入,因此我们可以先使用一维数组接收输入,然后花一个 # 型的形状,搞清楚 # 中每个位置是在一维数组中的哪个下标。

进一步的然后搞情况几个方向使用用到的下标是哪些。

同时为方便,把反向方向和中心点也画出来。

import java.util.*;
class Main {
    static int[][] ops = new int[][] {
        {0, 2, 6, 11, 15, 20, 22},
        {1, 3, 8, 12, 17, 21, 23},
        {10, 9, 8, 7, 6, 5, 4},
        {19, 18, 17, 16, 15, 14, 13},
        {23, 21, 17, 12, 8, 3, 1},
        {22, 20, 15, 11, 6, 2, 0},
        {13, 14, 15, 16, 17, 18, 19},
        {4, 5, 6, 7, 8, 9, 10}
    };
    static int[] opposite = new int[]{5, 4, 7, 6, 1, 0, 3, 2};
    static int[] center = new int[]{6, 7, 8, 11, 12, 15, 16, 17};
    static int N = 24;
    static int[] w = new int[N];
    static char[] path = new char[200];

    static void update(int x) {
        int[] locs = ops[x];
        int t = w[locs[0]];
        for (int i = 0; i < 6; i++) {
            int cur = locs[i], next = locs[i + 1];
            w[cur] = w[next];
        }
        w[locs[6]] = t;
    }

    static int f() {
        int[] cnts = new int[4];
        int max = 0;
        for (int i = 0; i < 8; i++) {
            int loc = center[i];
            int x = w[loc];
            cnts[x]++;
            max = Math.max(max, cnts[x]);
        }
        return 8 - max;
    }

    // 已经进行了 u 步,最多进行 maxDepth 步,上一步的操作是 last
    static boolean dfs(int u, int maxDepth, int last) {
        if (u + f() > maxDepth) return false;
        if (f() == 0) return true;

        for (int i = 0; i < 8; i++) {
            if (opposite[i] != last) {
                update(i);
                path[u] = (char)(i + 'A');
                if (dfs(u + 1, maxDepth, i)) return true;
                update(opposite[i]);
            }
        }
        return false;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            String ss = sc.nextLine();
            ss = ss.replace(" ", "");
            if (ss.charAt(0) == '0') break;
            char[] cs = ss.toCharArray();
            if (cs[0] == 0) break;
            for (int i = 0; i < 24; i++) w[i] = (int)(cs[i] - '0');

            int depth = 0;
            while (!dfs(0, depth, -1)) depth++;

            if (depth == 0) System.out.print("No moves needed");
            else {
                for (int i = 0; i < depth; i++) {
                    System.out.print(path[i]);
                }
            }
            System.out.println("");
            System.out.println(w[6]);
        }
    }
}



ACSaber
3个月前

IDA* 算法

在迭代加深的基础上增加 f() 的估值函数。

如果当前消耗的修改次数+估值修改次数,超过了限制的 maxDepth 的话,直接返回 false

import java.util.*;
class Main {
    static int n;
    static int N = 20;
    static int[] w = new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            n = sc.nextInt();
            for (int i = 1; i <= n; i++) w[i] = sc.nextInt();
            int depth = 0;
            while (depth <= 5 && !dfs(0, depth)) depth++;
            if (depth >= 5) System.out.println("5 or more");
            else System.out.println(depth);
        }
    }
    // 通常爆搜函数的设计:要么是已经消耗了多少次交换次数,或者当前是第几次交换,这两种定义
    // 当前消耗的修改次数为 u;最多修改次数为 maxDepth
    static boolean dfs(int u, int maxDepth) {
        if (u + f() > maxDepth) return false;
        if (f() == 0) return true;
        for (int len = 1; len <= n; len++) {
            for (int l = 1; l + len - 1 <= n; l++) {
                int r = l + len - 1;
                for (int k = r + 1; k <= n; k++) {
                    int[] clone = w.clone();
                    int[] nw = move(w, l, r, k);
                    w = nw;
                    if (dfs(u + 1, maxDepth)) return true;
                    w = clone;
                }
            }
        }
        return false;
    }
    static int[] move(int[] arr, int l, int r, int k) {
        int[] ans = new int[N];
        int idx = 1;
        for (int i = 1; i <= l - 1; i++) ans[idx++] = arr[i];
        for (int i = r + 1; i <= k; i++) ans[idx++] = arr[i];
        for (int i = l; i <= r; i++) ans[idx++] = arr[i];
        for (int i = k + 1; i <= n; i++) ans[idx++] = arr[i];
        return ans;
    }
    static int f() {
        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (w[i] != w[i + 1] - 1) ans++;
        }
        // 这里其实是想计算 ans / 3 的上取整
        // a / b 的上取整 = (a + b - 1) / b 的下取整
        return (ans + 2) / 3;
    }
}



ACSaber
3个月前

双向 DFS

基本思路:

假设物品数组长度为 n,

  1. 先用 dfs1 对物品 [1, n / 2] 下标的物品进行爆搜,并将不超过 w 价值的数值放到 set 里面(去重)
  2. 使用 set 构造出列表 list,并进行排序
  3. 使用 dfs2 对物品 [n / 2 + 1, n] 下标物品进行爆搜,对于每个爆搜结果 k, 在 list 进行二分找到最大的符合 “cur + k <= w” 的值
import java.util.*;
class Main {
    static int N = 50;
    static int n;
    static long w;
    static int[] arr = new int[N];
    static Set<Long> set = new HashSet<>();
    static List<Long> list;
    static long ans = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        w = sc.nextLong();
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) arr[i] = sc.nextInt();
        dfs1(1, n / 2, 0);
        list = new ArrayList<>(set);
        Collections.sort(list);
        // System.out.println(list);
        dfs2(n / 2 + 1, n, 0);
        System.out.println(ans);
    }
    static void dfs1(int u, int max, long cur) {
        if (cur > w) return;
        if (u > max) {
            set.add(cur);
            return;
        }
        dfs1(u + 1, max, cur + arr[u]);
        dfs1(u + 1, max, cur);
    }
    static void dfs2(int u, int max, long cur) {
        if (cur > w) return;
        if (u > max) {
            int l = 0, r = list.size() - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (list.get(mid) + cur <= w) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            if (list.get(r) + cur <= w) {
                ans = Math.max(cur + list.get(r), ans);
            }
            return;
        }
        dfs2(u + 1, max, cur);
        dfs2(u + 1, max, cur + arr[u]);
    }
}



ACSaber
3个月前
import java.util.*;
class Main {
    static int N = 810, M = 810;
    static char[][] cs = new char[N][M];
    static int n, m;
    static int[] boy;
    static int[] gril;
    static Deque<int[]> x;
    static boolean[][] st = new boolean[N][M];
    static int[][] dir = new int[][]{{1,0}, {-1,0}, {0,1}, {0,-1}};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            n = sc.nextInt();
            m = sc.nextInt();
            sc.nextLine();
            x = new ArrayDeque<>();
            for (int i = 1; i <= n; i++) {
                char[] ss = sc.nextLine().toCharArray();
                for (int j = 1; j <= m; j++) {
                    st[i][j] = false;
                    cs[i][j] = ss[j - 1];
                    if (cs[i][j] == 'M') {
                       boy = new int[]{i, j}; 
                    } else if (cs[i][j] == 'G') {
                        gril = new int[]{i, j};
                    } else if (cs[i][j] == 'Z') {
                        st[i][j] = true;
                        x.addLast(new int[]{i, j});
                        cs[i][j] = 'X';
                    }
                }
            }
            int ans = bfs();
            System.out.println(ans);
        }
    }
    static Integer hash(int[] loc) {
        return loc[0] * m + loc[1];
    }
    static int bfs() {
        Deque<int[]> qa = new ArrayDeque<>(), qb = new ArrayDeque<>();
        Map<Integer, Integer> da = new HashMap<>(), db = new HashMap<>();
        qa.addLast(boy);
        da.put(hash(boy), 0);
        qb.addLast(gril);
        db.put(hash(gril), 0);
        int cnt = 0;
        while (!qa.isEmpty() && !qb.isEmpty()) {
            int t = 0;
            // 鬼:两步
            infection();
            infection();

            // log();

            t = move(qa, qb, da, db, cnt++);
            if (t != -1) return t;
        }
        return -1;
    }
    static int move(Deque<int[]> qa, Deque<int[]> qb, Map<Integer, Integer> da, Map<Integer, Integer> db, int cnt) {
        for (int i = 0; i < 3; i++) {
            int size = qa.size();
            while (size-- > 0) {
                int[] poll = qa.pollFirst();
                int dx = poll[0], dy = poll[1];
                if (cs[dx][dy] == 'X') continue;
                for (int[] d : dir) {
                    int nx = dx + d[0], ny = dy + d[1];
                    if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
                    if (cs[nx][ny] == 'X') continue;
                    int[] cur = new int[]{nx, ny};
                    int key = hash(cur);
                    if (da.containsKey(key)) continue;
                    if (db.containsKey(key)) {
                        // return cnt + 1 + db.get(key);
                        return cnt + 1;
                    } else {
                        qa.addLast(cur);
                        da.put(key, cnt + 1);
                    }
                }
            }
        }

        for (int i = 0; i < 1; i++) {
            int size = qb.size();
            while (size-- > 0) {
                int[] poll = qb.pollFirst();
                int dx = poll[0], dy = poll[1];
                if (cs[dx][dy] == 'X') continue;
                for (int[] d : dir) {
                    int nx = dx + d[0], ny = dy + d[1];
                    if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
                    if (cs[nx][ny] == 'X') continue;
                    int[] cur = new int[]{nx, ny};
                    int key = hash(cur);
                    if (db.containsKey(key)) continue;
                    if (da.containsKey(key)) {
                        // return cnt + 1 + da.get(key);
                        return cnt + 1;
                    } else {
                        qb.addLast(cur);
                        db.put(key, cnt + 1);
                    }
                }
            }
        }

        return -1;
    }
    static void log() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                System.out.print(cs[i][j]);
            }
            System.out.println("");
        }
        System.out.println("");
    }
    static void infection() {
        int size = x.size();
        while (size-- > 0) {
            int[] poll = x.pollFirst();
            int dx = poll[0], dy = poll[1];
            for (int[] d : dir) {
                int nx = dx + d[0], ny = dy + d[1];
                if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
                if (!st[nx][ny]) {
                    cs[nx][ny] = 'X';    
                    st[nx][ny] = true;
                    x.addLast(new int[]{nx, ny});
                }
            }
        }
    }
}



ACSaber
3个月前
import java.util.*;
class Main {
    static int[] a = new int[10];
    static int[] t = new int[10];
    static Map<String, Integer> dist = new HashMap<>();
    static Map<String, int[]> g = new HashMap<>();
    static Map<String, Character> op = new HashMap<>();
    static Deque<int[]> q = new ArrayDeque<>();

    static int[][] tmp = new int[2][4];    
    static void set(int[] cur) {
        for (int i = 0; i < 4; i++) tmp[0][i] = cur[i + 1];
        for (int i = 0; i < 4; i++) tmp[1][i] = cur[8 - i];
    }
    static int[] get() {
        int[] ans = new int[10];
        for (int i = 0; i < 4; i++) ans[i + 1] = tmp[0][i];
        for (int i = 0; i < 4; i++) ans[5 + i] = tmp[1][3 - i];
        return ans;
    }
    static int[] move0(int[] cur) {
        set(cur);
        for (int i = 0; i < 4; i++) {
            int c = tmp[0][i];
            tmp[0][i] = tmp[1][i];
            tmp[1][i] = c;
        }
        return get();
    }
    static int[] move1(int[] cur) {
        set(cur);
        int x = tmp[0][3], y = tmp[1][3];
        for (int i = 3; i >= 1; i--) {
            tmp[0][i] = tmp[0][i - 1];
            tmp[1][i] = tmp[1][i - 1];
        }
        tmp[0][0] = x;
        tmp[1][0] = y;
        return get();
    }
    static int[] move2(int[] cur) {
        set(cur);
        int c = tmp[1][1];
        tmp[1][1] = tmp[1][2];
        tmp[1][2] = tmp[0][2];
        tmp[0][2] = tmp[0][1];
        tmp[0][1] = c;
        return get();
    }

    static String getHash(int[] cur) {
        StringBuilder sb = new StringBuilder();
        for (int i : cur) {
            sb.append(String.valueOf(i) + "_");
        }
        return sb.toString();
    }

    static void bfs() {
        q.addLast(a);
        dist.put(getHash(a), 0);
        while (!q.isEmpty()) {
            int[] poll = q.pollFirst();

            // System.out.println(Arrays.toString(poll));
            // System.out.println(q.size());

            int di = dist.get(getHash(poll));
            if (check(poll, t)) {
                return;
            }
            List<int[]> list = new ArrayList<>();
            list.add(move0(poll));
            list.add(move1(poll));
            list.add(move2(poll));
            for (int i = 0; i < 3; i++) {
                int[] cc = list.get(i);
                String key = getHash(cc);
                if (!dist.containsKey(key)) {
                    // System.out.println(key);
                    q.addLast(cc);
                    dist.put(key, di + 1);
                    op.put(key, (char)('A' + i));
                    g.put(key, poll);
                    if (check(cc, t)) return;
                }
            }
        }
    }
    static boolean check(int[] a, int[] b) {
        for (int i = 1 ; i <= 8; i++) {
            if (a[i] != b[i]) return false;
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 1; i <= 8; i++) {
            t[i] = sc.nextInt();
            a[i] = i;
        }
        bfs();
        System.out.println(dist.get(getHash(t)));
        StringBuilder sb = new StringBuilder();
        if (dist.get(getHash(t)) != 0) {
            while (!check(t, a)) {
                sb.append(op.get(getHash(t)));
                t = g.get(getHash(t));
            }
            sb.reverse();
            System.out.println(sb.toString());
        }
    }
}


活动打卡代码 AcWing 3664. 数组补全

ACSaber
3个月前
import java.util.*;
class Main {
    static int[] a = new int[1009];
    static int[] s = new int[1009];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt(), p = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt();
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= k; i++) {
            a[i] = sc.nextInt();
            s[i] = s[i - 1] + a[i];
            list.add(a[i]);
        }

        for (int i = k + 1; i <= n; i++) {
            a[i] = 1;
            s[i] = s[i - 1] + a[i];
            list.add(a[i]);
        }

        int sum = s[n];
        if (sum > x) {
            System.out.print("-1");   
            return;
        }
        int m = list.size();
        Collections.sort(list);
            // System.out.print(list.get(m / 2));   
        int idx = k + 1;
        while (list.get(m / 2) < y) {
            // System.out.println(list.get(m / 2));
            // System.out.println(a[idx]);
            int curr = list.get(m / 2);
            int min = a[idx];
            int diff = y - min;
            // System.out.println(diff);
            if (sum + diff <= x) {
                sum += diff;
                list.set(0, a[idx] + diff);
                a[idx] += diff;
                idx++;
            } else {
                System.out.print("-1");   
                return;
            }
            Collections.sort(list);    
        }


       for (int i = k + 1; i <= n; i++) {
            System.out.print(a[i] + " ");   
        } 

    }
}



ACSaber
3个月前
import java.util.*;
class Main {
    static class Node{
        int l, r; //代表左右儿子的下标
        int cnt;  //存储当前值域中数字的个数
    }

    static int N = 100009;
    static Node[] tr = new Node[N * 30];
    static int[] version = new int[N]; 
    static int idx = 0; 
    static int[] a = new int[N];
    static List<Integer> list; // 离散化数组

    // 找「起始值」对应的「离散化值」,即「起始值」的排序数组的对应下标
    static int find(int x) {
        return Collections.binarySearch(list, x);
    }

    static int build(int l, int r) {
        // 先将当前节点构造出来
        int q = ++idx;
        tr[q] = new Node();

        // 如果是叶子节点,直接返回
        if (l == r) return q;

        // 如果不叶子节点,将左右儿子建立出来
        int mid = l + r >> 1;
        tr[q].l = build(l, mid);
        tr[q].r = build(mid + 1, r);
        return q;
    }

    // 上个版本 / 在 [l, r] 范围中的 x 位置 +1
    // [l, r] 起始都是传完整的区间
    static int insert(int p, int l, int r, int x) {
        // 新建节点
        int q = ++idx;
        tr[q] = new Node();
        // 将上个版本的信息复制过来
        tr[q].l = tr[p].l;
        tr[q].r = tr[p].r;
        tr[q].cnt = tr[p].cnt;
        if (l == r) {
            tr[q].cnt++;
            return q;
        } else {
            int mid = l + r >> 1;
            if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
            else tr[q].r = insert(tr[p].r, mid + 1, r, x);
            pushup(q, tr[q].l, tr[q].r);
            return q;
        }
    }

    static void pushup(int u, int l, int r) {
        tr[u].cnt = tr[l].cnt + tr[r].cnt;
    }

    // 上一版本/当前版本/ [l, r] 里面找第 k 小的数
    // [l, r] 起始都是传完整的区间
    static int query(int p, int q, int l, int r, int k) {
        if (l == r) return l;
        int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
        int mid = l + r >> 1;
        if (k <= cnt) return query(tr[p].l, tr[q].l, l, mid, k);
        else return query(tr[p].r, tr[q].r, mid + 1, r, k - cnt);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        Set<Integer> set = new HashSet<>();
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            set.add(a[i]);
        }

        // 离散化
        list = new ArrayList<>(set);
        Collections.sort(list);

        int size = list.size();

        // 建立空的线段树
        version[0] = build(0, size - 1);

        for (int i = 1; i <= n; i++) {
            version[i] = insert(version[i - 1], 0, size - 1, find(a[i]));
        }

        while (m-- > 0) {
            int l = sc.nextInt(), r = sc.nextInt(), k = sc.nextInt();
            int ans = query(version[l - 1], version[r], 0, size - 1, k);
            System.out.println(list.get(ans));
        }
    }
}


活动打卡代码 AcWing 3655. 楼层

ACSaber
3个月前
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt(), x = sc.nextInt();
            if (n == 1 || n == 2) System.out.println(1);
            else {
                int ans = 1;
                int cur = 2;
                while (n > cur) {
                    cur += x;
                    ans++;
                } 
                System.out.println(ans);
            }
        }
    }
}


活动打卡代码 AcWing 3629. 同心圆涂色

ACSaber
3个月前
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        Arrays.sort(a);
        double ans = 0;
        for (int i = n - 1, j = 0; i >= 0; i--, j++) {
            int r = a[i];
            double cur = r * r * 3.1415926535897932384626433832795028841971;
            if (j % 2 == 1) {
                ans -= cur;
            } else {
                ans += cur;
            }
        }
        System.out.println(new Formatter().format("%.6f", ans).toString());
    }
}