ABC --131- A & B & C & D & E

AtCoder ABC 131 A&B&C&D&E AtCoder - 131

※2019/06/27 Add comment to B problem

F will be updated soon

• E may be added if you check the complete graph

A - Security

--Bad only if the values are the same in succession

	private void solveA() {
		char[] wk = next().toCharArray();
		for (int i = 1; i < wk.length; i++) {
			if (wk[i] == wk[i - 1]) {
				out.println("Bad");
				return;
			}
		}
		out.println("Good");
	}

B - Bite Eating Recently, there is a tendency to melt time due to the B problem ...

--Calculate the total of all --Calculate the smallest absolute value ――However, compare by absolute value, but note that it is not the absolute value that you want as a value

――As you can see from the explanation PDF, this problem is an arithmetic problem, so you can AC without a loop.

	private void solveB() {
		int n = nextInt();
		int l = nextInt();

		int total = 0;
		int temp = Integer.MAX_VALUE;
		for (int i = 1; i <= n; i++) {
			total += l + i - 1;
			if (Math.abs(temp) > Math.abs(l + i - 1)) {
				temp = (l + i - 1);
			}
		}
		out.println(total - temp);
	}

C - Anti-Division

--Overall $ (ba (-1)) $ minus $ (multiple of c + multiple of d-multiple of c and multiple of d) $, a number that is neither a multiple of c nor a multiple of d ) $ -A multiple of $ c and a multiple of d $ can be calculated by finding the least common multiple of C and D.

Reference site: Two proofs of the inclusion principle

	private void solveC() {
		long a = nextLong();
		long b = nextLong();
		long c = nextLong();
		long d = nextLong();

		long res1 = (b / c) - ((a - 1) / c);
		long res2 = (b / d) - ((a - 1) / d);
		long lcm = getLcm2Args(c, d);
		long res4 = (b / lcm) - ((a - 1) / lcm);

		out.println((b - (a - 1)) - (res1 + res2 - res4));
	}

	public long getLcm2Args(long num1, long num2) {
		return num1 * num2 / getGcd2Args(num1, num2);
	}

	public long getGcd2Args(long num1, long num2) {
		try {
			long wkVal1 = Long.max(num1, num2);
			long wkVal2 = Long.min(num1, num2);
			long res = wkVal1 % wkVal2;
			if (res != 0) {
				return getGcd2Args(wkVal2, res);
			} else {
				return wkVal2;
			}

		} catch (Exception e) {
			System.out.println("num1 : " + num1 + " / num2:" + num2);
			e.printStackTrace();
			return -1;
		}

	}

D - Megalomania

pattern 1: A_1 \leq B_1 A_1 + A_2 \leq B_2

Pattern 2: A_2 \leq B_2 A_1 + A_2 \leq B_1

If pattern 2 holds, pattern 1 should hold. .. ..

--Proof is on official Youtube

--Sort by deadline --However, if the deadline is the same, sort by the time it takes --After sorting, determine if the current time does not exceed the deadline. --If the deadline is exceeded, it is NG, and if all the work is completed, it is OK.

	private void solveD() {
		int n = nextInt();
		int[][] ab = Stream.generate(() -> new int[] { nextInt(), nextInt() }).limit(n).toArray(int[][]::new);

		Arrays.sort(ab, (x, y) -> {
			int ret = Integer.compare(x[1], y[1]);
			return ret != 0 ? ret : Integer.compare(x[0], y[0]);
		});

		long curTime = 0;
		for (int i = 0; i < n; i++) {
			curTime += ab[i][0];
			if (curTime > ab[i][1]) {
				out.println("No");
				return;
			}
		}
		out.println("Yes");
	}

E - Friendships

Reference site: I am always indebted Kenchon's competition professional devotion record (AtCoder ABC 131 E --Friendships (500 points))

――Even if you listen to the commentary, you don't have a complete graph or a clue to understanding, so only the AC code based on the commentary is released. .. .. --Starting from i = 1 is because we bring 1 to the center of the star graph --First, list all the edges extending from vertex 1, and then write as many edges as you need. By policy

	private void solveE() {
		int n = nextInt();
		int k = nextInt();

		/*
		 *The lower limit of K is 0
		 *Complete graph (all distances from one vertex to another are 1)
		 *
		 *The upper limit of K is(n-1)(n-2)/2
		 *star (starting from one vertex and extending to another vertex)
		 *The combination of all vertices is n(n-1)/2 pieces
		 *Since it is edged, from the combination of all vertices(n-1)Pull
		 */

		long cntEdge = (n - 1) * (n - 2) / 2;
		if (k > cntEdge) {
			out.println(-1);
			return;
		}

		long maxCnt = cntEdge - k + (n - 1);
		long cnt = 0;

		StringBuilder builder = new StringBuilder();
		for (int i = 1; i <= n; i++) {
			for (int j = i; j <= n; j++) {
				if (i == j) {
					continue;
				}
				if (cnt < maxCnt) {
					builder.append(i + " " + j + System.lineSeparator());
				}
				cnt++;
			}
		}

		out.println(maxCnt);
		out.println(builder.toString());
	}