[JAVA] ABC - 131 - A & B & C & D & E.

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

※2019/06/27 Kommentar zum B-Problem hinzufügen

F wird bald aktualisiert

• E kann hinzugefügt werden, wenn Sie das vollständige Diagramm überprüfen

A - Security

• Nur schlecht, wenn die Werte nacheinander gleich sind

	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 In letzter Zeit besteht aufgrund des B-Problems die Tendenz, die Zeit zu schmelzen ...

--Berechnen Sie die Summe aller --Berechnen Sie den kleinsten Absolutwert ―― Vergleichen Sie jedoch nach dem absoluten Wert, aber beachten Sie, dass dies nicht der absolute Wert ist, den Sie als Wert wünschen

• Erläuterung Wie Sie beim Lesen der PDF-Datei sehen können, handelt es sich bei diesem Problem um ein arithmetisches Problem, sodass Sie AC ohne Schleife ausführen können.

	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

• Insgesamt $ (ba (-1)) $ minus $ (ein Vielfaches von c + ein Vielfaches von d - ein Vielfaches von c und ein Vielfaches von d) $, eine Zahl, die weder ein Vielfaches von c noch ein Vielfaches von d ist ) $
• Ein Vielfaches von $ c und ein Vielfaches von d $ kann berechnet werden, indem das minimale gemeinsame Vielfache von C und D ermittelt wird.

Referenzseite: Zwei Arten des Nachweises des Einschlussprinzips

	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

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

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

Wenn Muster 2 gilt, sollte Muster 1 gelten. .. ..

• Beweis ist auf dem offiziellen Youtube

• Nach Frist sortieren

• Wenn die Frist jedoch gleich ist, sortieren Sie sie nach der Zeit, die sie benötigt

• Stellen Sie nach dem Sortieren fest, ob die aktuelle Zeit die Frist nicht überschreitet

• Wenn die Frist überschritten wird, ist es NG, und wenn alle Arbeiten abgeschlossen sind, ist es 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

Referenzseite: Ich bin immer verschuldet Kenchons professioneller Andachtsrekord im Wettbewerb (AtCoder ABC 131 E - Freundschaften (500 Punkte))

――Selbst wenn Sie den Kommentar anhören, haben Sie kein vollständiges Diagramm oder keinen Hinweis auf das Verständnis, sodass nur der auf dem Kommentar basierende AC-Code freigegeben wird. .. .. --Start von i = 1 ist, weil 1 in die Mitte des Sterngraphen gebracht wird

• Listen Sie zunächst alle Seiten auf, die sich von Scheitelpunkt 1 erstrecken, und schreiben Sie dann so viele Seiten, wie Sie benötigen. Nach Richtlinien

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

		/*
		 *Die Untergrenze von K ist 0
		 *Vollständige Grafik (alle Abstände von einem Scheitelpunkt zum anderen sind 1)
		 *
		 *Die Obergrenze von K ist(n-1)(n-2)/2
		 *Stern (von einem Scheitelpunkt ausgehend bis zu einem anderen)
		 *Die Kombination aller Eckpunkte ist n(n-1)/2 Stücke
		 *Da es sich um eine Seite handelt, ergibt sich aus der Kombination aller Eckpunkte(n-1)ziehen
		 */

		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());
	}