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

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

※2019/06/27 Ajouter un commentaire au problème B

F sera bientôt mis à jour

• E peut être ajouté si vous vérifiez le graphique complet

A - Security

• Mauvais seulement si les valeurs sont les mêmes successivement

	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 Récemment, il y a une tendance à faire fondre le temps en raison du problème B ...

--Calculer le total de tous --Calculer la plus petite valeur absolue ――Cependant, comparez par valeur absolue, mais notez que ce n'est pas la valeur absolue que vous voulez comme valeur

--Explication Comme vous pouvez le voir sur le PDF, ce problème est un problème arithmétique, vous pouvez donc AC sans boucle.

	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

• Globalement $ (ba (-1)) $ moins $ (un multiple de c + un multiple de d-un multiple de c et un multiple de d) $, un nombre qui n'est ni un multiple de c ni un multiple de d ) $ -Un multiple de $ c et un multiple de d $ peuvent être calculés en trouvant le multiple commun minimum de C et D.

Site de référence: Deux modes de preuve du principe d'inclusion

	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

modèle 1: A_1 \leq B_1 A_1 + A_2 \leq B_2

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

Si le motif 2 tient, le motif 1 doit tenir. .. ..

• La preuve est sur le Youtube officiel

--Tri par date limite

• Cependant, si la date limite est la même, trier par le temps que cela prend
• Après le tri, déterminez si l'heure actuelle ne dépasse pas la date limite
• Si la date limite est dépassée, c'est NG, et si tout le travail est terminé, c'est 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

Site de référence: Je suis toujours redevable Record de dévotion professionnelle de Kenchon (AtCoder ABC 131 E - Amitiés (500 points))

――Même si vous écoutez le commentaire, vous n'avez pas de graphique complet ou d'indice de compréhension, donc seul le code AC basé sur le commentaire est publié. .. ..

• À partir de i = 1, c'est parce que 1 est amené au centre du graphique en étoile
• Tout d'abord, listez tous les côtés partant du sommet 1, puis écrivez autant de côtés que nécessaire. Par politique

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

		/*
		 *La limite inférieure de K est 0
		 *Graphique complet (toutes les distances d'un sommet à l'autre sont de 1)
		 *
		 *La limite supérieure de K est(n-1)(n-2)/2
		 *étoile (partant d'un sommet et s'étendant vers un autre)
		 *La combinaison de tous les sommets est n(n-1)/2 pièces
		 *Puisqu'il a des côtés, de la combinaison de tous les sommets(n-1)Tirer
		 */

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