1, Martial arts script (simulation)

Title: Martial Arts script

    Xiao Ming arrives X During the cave exploration, I found a damaged martial arts secret script (more than 2000 pages! Of course, it is forged). He noticed that pages 10 and 11 of the book were on the same page, but pages 11 and 12 were not on the same page.

    Xiao Ming only wants to practice the martial arts from page 81 to page 92 of the book, but he doesn't want to take the whole book with him. How many pieces of paper does he have to tear off to take away?

This is an integer. Please submit this number through the browser and do not fill in any redundant content.

10 | 11 | 12 | 13 | 14 | 15... 80 | 81 | 82 | 83... 90 | 91 92 | 93. Just pay attention to the format of the page.
Answer: 7

2, Cut noodles (find rules)

Title: cutting noodles

    One high gluten ramen, cut a knife in the middle, and you can get two noodles.

    If you fold it in half once and cut it in the middle, you can get three noodles.

    If you fold it in half for two times and cut a knife in the middle, you can get five noodles.

    So, how many noodles will you get if you fold it in half for 10 times and cut it in the middle?

The answer is an integer. Please submit the answer through the browser. Don't fill in any extra content.

Law finding: 2^n + 1
Answer: 1025

3, Guess letters (Analog)

Title: guessing letters

    hold abcd...s The sequence composed of 19 letters was spliced repeatedly 106 times to obtain a string with a length of 2014.

    Next, delete the first letter (i.e. the beginning letter) a)，And the third, fifth and other letters in all odd positions.

    Delete the new position of the odd letter string. If this goes on, there is only one letter left. Please write that letter.

The answer is a lowercase letter. Please submit the answer through the browser. Don't fill in any extra content.

You can simulate directly. The deleted letters are marked as 1 with vis array.

public class Main {
    public static void main(String[] args) {
        int[] nums = new int[2015];
        int index = 0;
        for (int i = 1; i <= 106; i++) {
            for (int j = 1; j <= 19; j++) {
                nums[index++] = j;
            }
        }
        // index = 2014
        int[] vis = new int[2015];
        while (index != 1) {
            int tmp = 0;
            for (int i = 0; i < 2014; i++) {
                // Each deleted number is marked as 1. Only the number that has not been deleted (= 0)
                if (vis[i] == 0) {
                    tmp++;
                    if (tmp % 2 == 1) {
                        vis[i] = 1;
                        index--;
                    }
                }
            }
        }
        for (int i = 0; i < 2014; i++) {
            if (vis[i] == 0) {
                System.out.println(nums[i]);
            }
        }
    }
}

Answer: q

4, V. fill in the blanks for the procedure

6, Strange fraction (Analog)

Title: strange fraction

    When he was in primary school, Xiao Ming often invented new algorithms by himself. Once, the teacher asked:

    1/4 Multiply by 8/5 

    Xiao Ming actually spliced molecules and denominators together. The answer is: 18/45 (See Figure 1.png)

    The teacher just wanted to criticize him. On second thought, the answer happened to be right. Damn it!

    For both numerator and denominator, it is 1~9 What other formulas can be used to calculate the single digit in the?

    Please write down the number of all the different formulas (including the examples in the question).

    Obviously, after exchanging the numerator and denominator, for example: 4/1 Multiply by 5/8 It meets the requirements. This is a different formula.

    But for the same numerator and denominator, 2/2 Multiply by 3/3 There are too many such types to be counted!

Note: the answer is an integer (considering symmetry, it must be even). Please submit via browser. Don't write superfluous content.

Note that in the title, only the denominator of one fraction is required to be different, and there is no requirement for the denominator of two fractions! It also allows the exchange of numerators and denominators, which is a different formula. You can simulate directly according to the meaning of the topic. Pay attention to using the maximum common divisor gcd to simplify the score and compare the simplest form.

public class Main {
    // Find the greatest common divisor to divide
    static int gcd (int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
    public static void main(String[] args) {
        // The numerator and denominator are single digits from 1 to 9
        // Numerator and denominator cannot be the same
        int ans = 0;
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++) {
                if (j == i) {
                    continue;
                }
                for (int k = 1; k <= 9; k++) {
                    for (int l = 1; l <= 9; l++) {
                        if (l == k) {
                            continue;
                        }
                        // i j k l simulates the numerator denominator of two fractions respectively
                        int a1 = i * 10 + k;
                        int a2 = j * 10 + l;
                        int tmp1 = gcd(a1, a2);
                        a1 = a1 / tmp1;
                        a2 = a2 / tmp1;
                        int b1 = i * k;
                        int b2 = j * l;
                        int tmp2 = gcd(b1, b2);
                        b1 = b1 / tmp2;
                        b2 = b2 / tmp2;
                        if (a1 == b1 && a2 == b2) {
                            ans++;
                            System.out.println(a1 + "/" + a2);
                        }
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

Answer: 14

7, Poker ranking (greedy)

Title: Poker sequence

    A A 2 2 3 3 4 4， A total of four pairs of playing cards. Please line them up.
    Requirements: two A There is one card in the middle, two cards between two 2, three cards between two 3, and four cards between two 4.

    Please fill in the lowest dictionary order of all the required permutations.

For example: 22 AA3344 than A2A23344 Dictionary order is small. Of course, they are not the answers to meet the requirements.


Please submit your answer through the browser. “ A"Never use lowercase letters a，And don't use "1" instead. There must be no spaces between characters.

Put the smallest dictionary order first, and meet the requirements of the topic, and put the number in turn.
Answer: 2342A3A4

8, Divide candy (simulation)

Pay attention to sitting in a circle in the topic!!, On the left of the first child is the last child. First record the number of sweets to be divided, and then add them to themselves, rather than adding and dividing.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scan.nextInt();
        }
        int ans = 0;
        while (true) {
            int[] cnt = new int[n];
            int index = 0;
            for (int i = 0; i < n; i++) {
                cnt[index++] = nums[i] / 2;
                nums[i] = nums[i] / 2;
            }
            for (int i = 0; i < index; i++) {
                if (i == 0) {
                    nums[n - 1] += cnt[i];
                } else {
                    nums[i - 1] += cnt[i];
                }
            }
            for (int i = 0; i < n; i++) {
                if (nums[i] % 2 == 1) {
                    nums[i]++;
                    ans++;
                }
            }
            int tmp = nums[0];
            int i;
            for (i = 1; i < n; i++) {
                if (tmp != nums[i]) {
                    break;
                }
            }
            if (i == n) {
                System.out.println(ans);
                break;
            }
        }
    }
}

9, Underground palace treasure taking (DFS search)

I only thought of DFS. The submission was only 42 points. The following examples timed out. The positive solution is memory search: DFS+DP.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int ans = 0;
    // Only right and down
    static int[] xx = {0, 1};
    static int[] yy = {1, 0};
    static int[][] vis = new int[51][51];
    static LinkedList<Integer> price = new LinkedList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int k = scan.nextInt();
        int[][] map = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = scan.nextInt();
            }
        }
        price.add(map[0][0]);
        vis[0][0] = 1;
        dfs (map, k, 0, 0);
        price = new LinkedList<>();
        vis = new int[51][51];
        dfs (map, k, 0, 0);
        System.out.println(ans);
    }
    static void dfs(int[][] map, int k, int x, int y) {
        int n = map.length;
        int m = map[0].length;
        if (x == n - 1 && y == m - 1 && k == price.size()) {
            ans++;
            ans %= 1000000007;
            return;
        }
        if (k < price.size()) {
            return;
        }
        for (int i = 0; i < 2; i++) {
            int tmpx = x + xx[i];
            int tmpy = y + yy[i];
            if (tmpx >= n || tmpy >= m || vis[tmpx][tmpy] == 1) {
                continue;
            }
            int flag = 1;
            for (int j = 0; j < price.size(); j++) {
                if (map[tmpx][tmpy] <= price.get(j)) {
                    flag = 0;
                    break;
                }
            }
            vis[tmpx][tmpy] = 1;
            if (flag == 1) {
                price.add(map[tmpx][tmpy]);
                dfs(map, k, tmpx, tmpy);
                price.removeLast();
                // Because when you can take each step, you can choose not to take it
                // Therefore, it needs to be traversed in two cases, and the backtracking can only be carried out after traversing in two cases
                dfs(map, k, tmpx, tmpy);
                // to flash back
                vis[tmpx][tmpy] = 0;
            } else {
                dfs(map, k, tmpx, tmpy);
                // to flash back
                vis[tmpx][tmpy] = 0;
            }
        }
    }
}

Be sure to pay attention to each step. If you can take it, you can choose not to take it or take it, so you should search separately, and then trace back after traversing the two cases.

10, ※ matrix flip coin (mathematical reasoning, BigInteger sqrt)

When a Q operation is performed on each coin, all coins in row i * x and column j * y will be flipped, where i and j are positive integers with any feasible operation, and the line number and column number start from 1.

If the matrix size is 5x6, perform Q operation for the coins in row 1 and column 1, which can make (1,1) (1,2) (1,3)... (1,6); (2,1) (2,2) (2,3) … (2,6)； (3,1)... Until the last (5,6) flip once. So how many flips will be performed for the coins in row i and column j?

(1,4) will flip because (1,1) (1,2) (1,4) performs Q operation, so it depends on how many factors there are in the factor of 4 (including yourself). For coins in row i and column j, the number of flips performed = the number of factors of i * the number of factors of j. If the number of turns is odd, it indicates that it was originally the opposite side; If the number of flips is even, it indicates that it was originally facing up (because it is facing up after all Q operations are performed).

To make the number of factors of i * the number of factors of J = odd, then i and j must be square, because only the number of factors of square is odd, and only odd * odd = odd, odd * even = even, even * even = even, so we must ensure that the number of factors of i and j are odd, that is, i and j are required to be square.

If we want to find the number of coins on all the reverse sides, we don't just look at the number of square numbers in N and m respectively. The factor number of square number * the factor number of square number = odd number (the original coin is also the reverse side). The knowledge of permutation and combination is used here. M squares * n squares = mn kinds and possibly = mn reverse coins.

How to find the number of squares= sqrt(n), for example, 1-4, sqrt(4) = 2 = 1, 4, so the answer = sqrt(m) * sqrt(n).

sqrt(m) * sqrt(n) for most of the inputs in the topic, it is beyond the data range, so it must be converted into BigInteger to calculate sqrt. Since BigInteger has no sqrt function, it must be implemented in binary, as shown below.

class Solution {
    public int sqrt(int m) {
        if (m == 0 || m == 1) {
            return 1;
        }
        int left = 0;
        int right = m;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (mid == m / mid) {
                return mid;
            } else if (mid < m / mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left - 1;
    }
}

After knowing the bisection simulation sqrt method, you only need to change the above int to BigInteger. The final code is as follows:

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String n = scan.next();
        String m = scan.next();
        // sqrt(n,m) rounded down
        // The answer is sqrt(n) * sqrt(m)
//        System.out.println((int)Math.sqrt(n) * (int)Math.sqrt(m));
        // The above answers do not answer all data scales
        // The maximum data is 10 ^ 1000, which requires Big
        BigInteger left = new BigInteger("0");
        BigInteger right = new BigInteger(n);
        BigInteger right1 = new BigInteger(m);
        System.out.println(search(left, right, new BigInteger(n)).multiply(search(left, right1, new BigInteger(m))));

    }
    static BigInteger search(BigInteger left, BigInteger right, BigInteger n) {
        BigInteger mid;
        // left <= right
        while (left.compareTo(right) == -1 || left.compareTo(right) == 0) {
            // mid = (l+r) / 2
            mid = left.add(right).divide(new BigInteger("2"));
            if (mid.compareTo(n.divide(mid)) == 0) {
                // mid == n / mid; mid * mid == n
                return mid;
            } else if (mid.compareTo(n.divide(mid)) == -1) {
                // mid < n / mid
                left = mid.add(new BigInteger("1"));
            } else {
                // mid > n / mid
                right = mid.subtract(new BigInteger("1"));
            }
        }
        return left.subtract(new BigInteger("1"));
    }
}