A - Task Scheduling Problem

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $100100$ points

Problem Statement

You have three tasks, all of which need to be completed.

First, you can complete any one task at cost $00$.

Then, just after completing the $\mathrm{ii}$-th task, you can complete the $\mathrm{jj}$-th task at cost $|Aj-Ai||Aj-Ai|$.

Here, $|x||x|$ denotes the absolute value of $\mathrm{xx}$.

Find the minimum total cost required to complete all the task.

Constraints

• All values in input are integers.
• $\mathrm{1\le A1,A2,A3\le 1001\le A1,A2,A3\le 100}$

---

Input

Input is given from Standard Input in the following format:

A1A1 A2A2 A3A3

Output

Print the minimum total cost required to complete all the task.

---

Sample Input 1 Copy

Copy

1 6 3

Sample Output 1 Copy

Copy

5

When the tasks are completed in the following order, the total cost will be $55$, which is the minimum:

• Complete the first task at cost $00$.
• Complete the third task at cost $22$.
• Complete the second task at cost $33$.

---

Sample Input 2 Copy

Copy

11 5 5

Sample Output 2 Copy

Copy

6

---

Sample Input 3 Copy

Copy

100 100 100

Sample Output 3 Copy

Copy

0 最大的减去最小的。

import java.util.Arrays;import java.util.Scanner;import static java.lang.Math.*;public class Main {        public static void main(String[] args) {        Scanner in = new Scanner(System.in);        int [] a = new int[3];        for(int i = 0;i < 3;i ++) {            a[i] = in.nextInt();        }        Arrays.sort(a);        System.out.println(a[2] - a[0]);    }}

 B - String Rotation

---

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $200200$ points

Problem Statement

You are given string $\mathrm{SS}$ and $\mathrm{TT}$ consisting of lowercase English letters.

Determine if $\mathrm{SS}$ equals $\mathrm{TT}$ after rotation.

That is, determine if $\mathrm{SS}$ equals $\mathrm{TT}$ after the following operation is performed some number of times:

Operation: Let $\mathrm{S=S1S2...S|S|S=S1S2...S|S|}$. Change $\mathrm{SS}$ to ${\mathrm{S|S|S1S2...S|S|-1S|S|S1S2...S|S|-1}}^{}$.

Here, $|X||X|$ denotes the length of the string $\mathrm{XX}$.

Constraints

• $\mathrm{2\le |S|\le 1002\le |S|\le 100}$
• $|S|=|T||S|=|T|$
• $\mathrm{SS}$ and $\mathrm{TT}$ consist of lowercase English letters.

---

Input

Input is given from Standard Input in the following format:

SSTT

Output

If $\mathrm{SS}$ equals $\mathrm{TT}$ after rotation, print Yes; if it does not, print No.

---

Sample Input 1 Copy

Copy

kyototokyo

Sample Output 1 Copy

Copy

Yes

• In the first operation, kyoto becomes okyot.
• In the second operation, okyot becomes tokyo.

---

Sample Input 2 Copy

Copy

abcarc

Sample Output 2 Copy

Copy

No

abc does not equal arc after any number of operations.

---

Sample Input 3 Copy

Copy

aaaaaaaaaaaaaaabaaaaaaaaaaaaaaab

Sample Output 3 Copy

Copy

Yes 排着遍历拼接。

import java.util.Arrays;import java.util.Scanner;import static java.lang.Math.*;public class Main {    static boolean check(String a,String b) {        if(a.length() != b.length())return false;        for(int i = 0;i < a.length();i ++) {            if(a.charAt(i) == b.charAt(0) && (a.substring(i, a.length()) + a.substring(0, i)).equals(b)) {                return true;            }        }        return false;    }    public static void main(String[] args) {        Scanner in = new Scanner(System.in);        String a = in.nextLine();        String b = in.nextLine();        System.out.println(check(a,b) ? "Yes" : "No");    }}

 C - Modulo Summation

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $300300$ points

Problem Statement

You are given $\mathrm{NN}$ positive integers ${\mathrm{a1,a2,...,aNa1,a2,...,aN}}^{}$.

For a non-negative integer $\mathrm{mm}$, let $\mathrm{f(m)=(m mod a1)+(m mod a2)+...+(m mod aN)f(m)=(m mod a1)+(m mod a2)+...+(m mod aN)}$.

Here, $\mathrm{X mod YX mod Y}$ denotes the remainder of the division of $\mathrm{XX}$ by $\mathrm{YY}$.

Find the maximum value of $\mathrm{ff}$.

Constraints

• All values in input are integers.
• $\mathrm{2\le N\le 30002\le N\le 3000}$
• $\mathrm{2\le ai\le 1052\le ai\le 105}$

---

Input

Input is given from Standard Input in the following format:

NNa1a1 a2a2 ...... aNaN

Output

Print the maximum value of $\mathrm{ff}$.

---

Sample Input 1 Copy

Copy

33 4 6

Sample Output 1 Copy

Copy

10

$\mathrm{f(11)=(11 mod 3)+(11 mod 4)+(11 mod 6)=10f(11)=(11 mod 3)+(11 mod 4)+(11 mod 6)=10}$ is the maximum value of $\mathrm{ff}$.

---

Sample Input 2 Copy

Copy

57 46 11 20 11

Sample Output 2 Copy

Copy

90

---

Sample Input 3 Copy

Copy

7994 518 941 851 647 2 581

Sample Output 3 Copy

Copy

4527 一个数对多个数去摸和要最大。 对于m，m%a1最大值是a1 - 1，也就是说令m = t1 * a1 - 1（t1 >= 1)时m%a1最大,同样如果对于a1~n都满足m = ti * ai - 1,总和就会最大，实际上就是满足m = t1 * a1 - 1 = t2 * a2 - 1 = ... = tn * an - 1,即t1 * a1 = t2 * a2 = ... = tn * an = m + 1，所以m + 1是a1~n的公倍数，是存在的。 答案就显而易见是所有属的和-n。

import java.util.Arrays;import java.util.Scanner;import static java.lang.Math.*;public class Main {    static boolean check(String a,String b) {        if(a.length() != b.length())return false;        for(int i = 0;i < a.length();i ++) {            if(a.charAt(i) == b.charAt(0) && (a.substring(i, a.length()) + a.substring(0, i)).equals(b)) {                return true;            }        }        return false;    }    public static void main(String[] args) {        Scanner in = new Scanner(System.in);        int n = in.nextInt();        int d;        int ans = -n;        for(int i = 0;i < n;i ++) {            d = in.nextInt();            ans += d;        }        System.out.println(ans);    }}

 

D - Islands War

---

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $400400$ points

Problem Statement

There are $\mathrm{NN}$ islands lining up from west to east, connected by $\mathrm{N-1N-1}$ bridges.

The $\mathrm{ii}$-th bridge connects the $\mathrm{ii}$-th island from the west and the $(i+1)(i+1)$-th island from the west.

One day, disputes took place between some islands, and there were $\mathrm{MM}$ requests from the inhabitants of the islands:

Request $\mathrm{ii}$: A dispute took place between the ${\mathrm{aiai}}^{}$-th island from the west and the ${\mathrm{bibi}}^{}$-th island from the west. Please make traveling between these islands with bridges impossible.

You decided to remove some bridges to meet all these $\mathrm{MM}$ requests.

Find the minimum number of bridges that must be removed.

Constraints

• All values in input are integers.
• $\mathrm{2\le N\le 1052\le N\le 105}$
• $\mathrm{1\le M\le 1051\le M\le 105}$
• $\mathrm{1\le ai<bi\le N1\le ai<bi\le N}$
• All pairs $(ai,bi)(ai,bi)$ are distinct.

---

Input

Input is given from Standard Input in the following format:

NN MMa1a1 b1b1a2a2 b2b2::aMaM bMbM

Output

Print the minimum number of bridges that must be removed.

---

Sample Input 1 Copy

Copy

5 21 42 5

Sample Output 1 Copy

Copy

1

The requests can be met by removing the bridge connecting the second and third islands from the west.

---

Sample Input 2 Copy

Copy

9 51 82 73 54 67 9

Sample Output 2 Copy

Copy

2

---

Sample Input 3 Copy

Copy

5 101 21 31 41 52 32 42 53 43 54 5

Sample Output 3 Copy

Copy

4

import java.util.Arrays;import java.util.Comparator;import java.util.Scanner;import static java.lang.Math.*;class bridge{    public int a;    public int b;    public bridge() {        a = b = 0;    }}public class Main {    public static void main(String[] args) {        Scanner in = new Scanner(System.in);        int n = in.nextInt();        int k = in.nextInt();        bridge [] s = new bridge[k];        for(int i = 0;i < k;i ++) {            s[i] = new bridge();            s[i].a = in.nextInt();            s[i].b = in.nextInt();        }        Arrays.sort(s,new Comparator
             
              () {            public int compare(bridge x,bridge y) {                if(x.a == x.b)return x.b - y.b;                return x.a - y.a;            }        });        int ans = 0,r = 0;        for(int i = 0;i < k;i ++) {            if(s[i].a >= r) {                ans ++;                r = s[i].b;            }            else if(r > s[i].b)r = s[i].b;        }        System.out.println(ans);    }}