KMP + DP, O(n ^ 2)

2
87 4547
87 2945 1516
64 913 9864
-----------
9904.472185221

A solution that doesn't make use of the max number being 10,000 is using inclusion-exclusion principle. Because when we take the sets of K that have a gcd divisible by 2 and the sets of K that have a gcd divisible by 3, you count twice the ones with a gcd divisible by 6, so you have to subtract those. It's similar to a solution to this problem: https://open.kattis.com/problems/coprimeintegers

import java.util.*;
public class j {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int bin,sum = 0;
        int n=input.nextInt();
        int m=input.nextInt();
        int [] mas = new int [n];
        for(int i = 0;i<m;i++){
            bin = input.nextInt();
            sum += 1;
            mas[bin-1] = mas[bin-1] + 1;

        }
        for(int i = 0;i<n;i++){
            System.out.println(String.format("%.2f",mas[i]/(sum*0.01))+"%");
        }

    }
}

import java.util.*;
public class Main {

    public static void main(String[] args) {
        ArrayList<Integer> mas = new ArrayList<>();
        Scanner input = new Scanner(System.in);
        int n,bin,delta = 0;

        n = input.nextInt();
        for (int i = 0; i <n;i++){
            bin = input.nextInt();
            mas.add(bin);
        }

        n = input.nextInt();
        for (int i = 0; i <n;i++){
            bin = input.nextInt();
            mas.add(bin);
        }

        n = input.nextInt();
        for (int i = 0; i <n;i++){
            bin = input.nextInt();
            mas.add(bin);
        }

        Collections.sort(mas);
        delta = mas.size();
        for (int i = 0;i<mas.size()-1;i++){
            bin = mas.get(i);
            delta = delta - (mas.lastIndexOf(bin)-mas.indexOf(bin)+1);


        }
        delta = -1*delta-mas.size();
        System.out.print(delta);
    }
}

:P

import java.util.*;

public class ReverseRoot {
    public static void main(String[] args) {
        ArrayList<Long> list = new ArrayList<>();
        Scanner scn = new Scanner(System.in);
        while (scn.hasNextLong()) {
            long p = scn.nextLong();
            list.add(p);
        }
        scn.close();
        for (int i = list.size() - 1; i >= 0; i--) {
            System.out.printf("%.4f%n", Math.sqrt((double) list.get(i)));
        }
    }
}

Does anyone know about test number 5? If you do, please download the values for this test.

write line "#define int long long" and change "int main" to "signed main"

What test number 2 can be?

Edited by author 21.02.2021 00:09

program p1071;
var x,y,z,s,i:longint;
    out:boolean;
procedure check(p:longint);
var  x1,y1:longint;
     c:array[0..10000] of integer;
begin
     fillchar(c,sizeof(c),0);
     x1:=x;y1:=y;
     repeat
           inc(c[x1 mod p]);
           x1:=x1 div p;
     until x1=0;
     repeat
           if c[y1 mod p]>0 then dec(c[y1 mod p])
                            else exit;
           y1:=y1 div p;
     until y1=0;
     out:=true;
end;
begin
     readln(x,y);z:=0;out:=false;
     for i:=2 to x do
         if x mod i=y mod i then
         begin
              check(i);
              if out then break;
         end;
     if out then write(i)
            else write('No solution');
     readln;
end.

Does anyone have a clue on what test №16 is? If something, I am writing on Python.

Edited by author 19.02.2021 02:12

it wasted my whole day using string.
then i use array instead of boring string and accepted

a valid n digit number can be found from valid n-1 and n-2 digit numbers

Edited by author 16.02.2021 13:56

Edited by author 16.02.2021 13:56

[DELETED]

Edited by author 17.09.2022 01:09

You should find maximum matrix which is square, black and also contains white square inside rotated by 45 degrees. For instance:
1)
1 1 1 0 1 1 1
1 1 0 0 0 1 1
1 0 0 0 0 0 1
0 0 0 0 0 0 0
1 0 0 0 0 0 1
1 0 0 0 0 1 1
1 1 1 0 1 1 1
2)
1 1 1 1 0 1 1 1 1
1 1 1 0 0 0 1 1 1
1 1 0 0 0 0 0 1 1
1 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 1 1
1 1 1 0 0 0 1 1 1
1 1 1 1 0 1 1 1 1
are desired matrices maximum width of which you must find

Easy solution with O(p) and without using a primality of p. We can build a table of square roots modulo p and then...

test:
4
0 0
2 0
2 2
0 2
1 2
1
360

ans:
4
0

test:
4
0 0
2 0
2 2
0 2
2 1.5
3
180
-180
-180

ans:
3
1
1
0

Example: 31 9973 31
Why python is VERY slow in mod? Got tle here

Hello :) Could someone please give me test 48 or similar to let me understand what is wrong with my program ? :)