Добро пожаловать в редакционную статью Educational Codeforces Round 153, Rated for Div. 2. В этой редакционной статье мы углубимся в решения с полной логикой и подходом, которые я использовал для решения трех задач: «Не подстрока» (проблема A), «Необычные монеты» (проблема B) и «Игра на перестановку». (Задача С).
А. Не подстрока
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t--> 0) {
String s = sc.next();
if (s.equals("()")) {
System.out.println("NO");
continue; //come out of loop to next test case
}
else {
System.out.println("YES");
StringBuilder sb1 = new StringBuilder(""); //sb1 is of type (((())))
for (int i = 0; i < s.length(); i++) sb1.append('(');
for (int i = 0; i < s.length(); i++) sb1.append(')');
StringBuilder sb2 = new StringBuilder(""); //sb2 is of type ()()()
for (int i = 0; i < s.length(); i++) sb2.append("()");
if (sb1.toString().contains(s)) {
System.out.println(sb2.toString());
} else {
System.out.println(sb1.toString());
}
}
}
sc.close();
}
}
ЛОГИКА —
ЛОГИКА, которую я понял после решения этого вопроса —
Вопрос рассказал нам о строке «s» из «)» и «(» длиной «n». Нас просят найти другую строку длиной 2n, что делает разумную арифметическую последовательность скобок допустимой.
Теперь может быть три случая:
I: ((((….))))
II: ()()()…
III: комбинация двух вышеуказанных случаев I и II может иметь вид ()(())()
Теперь подумайте, что является общей подстрокой между I и II: Это — () и между I и II нет другой общей подстроки
Фактически, это () — единственно возможная допустимая последовательность скобок длиной 2 и один шаблон, который будет существовать во всех допустимых последовательностях скобок.
Таким образом, s==”()” не может создать допустимый t, потому что в противном случае t всегда будет содержать это. Так что скажите этому нет.
Теперь нам уже дана строка «s», и мы создали действительную скобочную строку «t» длиной 2 * s.length, т.е. мы создали две строки случая I и II длиной 2 * s.
Допустим, строка «s» не является () и существует как подстрока в случае I.
Из нашего вышеприведенного обсуждения мы можем гарантировать, что теперь она не может быть подстрокой в II, и наоборот. Следовательно, все, что нам нужно сделать, это напечатать другую строку, у которой не будет подстроки «s».
ЛОГИКА Я работал, когда давал конкурс —
Нам дана строка «s». Нам нужно найти другую строку «t», двойную длину «s», которая может быть допустимой последовательностью арифметических скобок и также не содержать «s» в качестве подстроки.
«s» может содержать любое количество «(» или «)», главное, чтобы он был удвоенной длины.
После рассмотрения тестовых примеров: единственный раз, когда «t» не может существовать, это когда «s»=»()», поскольку решение «t» имеет только два случая: «(())» или «()()»
И здесь «s» — это подстрока и в том, и в другом. Итак, для «s»=() верните нет, иначе да
Теперь настоящий вопрос в том, как найти «t»
например: «s»=)( тогда «t» не может быть ()(), потому что «s» здесь — это подстрока, возможно «t» — это (())
Анализ регулярного формирования брекетов может быть трех типов:
Я: все отдельно: ()()()….
II: одно помещено в другое: ((((….))))
III: комбинация двух вышеуказанных
Проблема с вопросом? Теперь нам нужно найти «t» размером 2 * s.length() и не имеющую «s» в качестве подстроки.
Все, что нам нужно сделать, это сгенерировать строку случая I и II и проверить, что тот, который не содержит «s», является нашим ответом.
Б. Необычные монеты
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t--> 0) {
int sum = sc.nextInt(); //total amount to pay
int k = sc.nextInt(); //value k
int a1 = sc.nextInt(); //coins of value 1
int ak = sc.nextInt(); //coins of value k
int fancyk = 0;
int fancy1 = 0;
int ans = 0;
//use ak coins
int akcoinsused = Math.min(ak, sum / k);
sum -= k * akcoinsused;
//use a1 coins
sum = Math.max(0, sum - a1);
if (sum > 0) { //still need to pay more time to use fancy coins
//use fancy coins worth ak
fancyk = sum / k; //we utilise fancyk to fullest and if sum<k; the division simply returns 0 fancyk used
fancy1 = sum % k;
ans = fancyk + fancy1;
if (a1 >= k - fancy1) { //let's compromise with a1, k-fancy1 is a way of saying by how much can we compromise to reach next k
fancyk = 1 + sum / k;
fancy1 = 0;
int ans2 = fancyk + fancy1;
ans = Math.min(ans, ans2);
}
}
System.out.println(ans);
}
sc.close();
}
}
ЛОГИКА —
sum = m = общая сумма к выплате
a1 = количество монет стоимостью 1
ak = количество монет стоимостью k
Вопросы хотят, чтобы мы использовали как можно меньше причудливых монет.
Обычные монеты — монеты номиналом 1 (монеты ~a1) и монеты номиналом k (монеты ~ak)
Необычные монеты — бесконечные монеты номиналом 1 и k
Сначала мы начнем с траты монет ak, затем монет a1.
И, наконец, мы попробуем использовать необычные монеты, чтобы покрыть оставшуюся сумму.
Сколько монет ak мы можем использовать, думая, что хотим использовать максимальное количество монет ak?
useak = Math.min(ak, m/k); => m/k = общее количество требуемых монет ak.
Таким образом, либо ak_required превышает данное нам ak, либо в противном случае мы можем использовать все ak.
Мы получим количество ak, которое мы будем использовать.
Итак, оставшаяся сумма => sum = sum — (значение использования)
=> sum -= Math.min(k * ak, (m/k) * k);
=> здесь мы умножаем на k, так как нам нужно найти значения, вычитая фактическую стоимость используемых монет.
sum -= k * (ak_coins_used)
Обратите внимание, что: (m/k) * k = › на самом деле представляет собой нечто эквивалентное Math.floor(m/k) * k
=› поскольку мы рассчитываем количество монет, нам понадобится минимальное значение.
Теперь мы должны использовать монеты a1? Каким будет наилучший способ?
оставшаяся сумма => сумма = сумма — 1 * a1;
=> сумма -= a1
Итак, если сумма ‹= 0 => нам достаточно достаточно, чтобы заплатить сумму самостоятельно, не нуждаясь в модных монетах.
В противном случае, если сумма [sum › 0] еще не покрыта, пришло время использовать модные монеты:
Опять же, чтобы использовать минимально возможное число. из необычных монет мы сначала попытаемся использовать необычные монеты стоимостью k, как мы это делали выше.
Fancyk = (sum/k) * k; снова здесь мы рассматриваем, сколько необычных монет стоимостью k можно использовать.
оставшаяся сумма => sum -= (sum/k) * k;
Теперь пришло время использовать Fancy1 стоимостью 1 монету: т. е., если сумма все еще не стала нулевой и ее осталось покрыть
Fancy1 = оставшаяся сумма = сумма
Итак, наш ответ = минимальное количество использованных модных монет = Fancyk + Fancy1.
ПРИМЕЧАНИЕ.
Мы могли бы сделать это непосредственно в приведенных выше шагах вместо того, чтобы снова уменьшать сумму:
Fancyk = sum/k;
Fancy1 = sum%k;
Но приведенные выше формулы помогают нам осознать, И увидев тестовый пример III и осознав их величину:
Вывод:
sum % k › sum / k + 1
Это означает, что использование еще одной причудливой монеты уменьшает нашу общее использование необычных монет путем компромисса в начале, потратив меньшее количество монет a1, как это было сделано в тестовом примере 3.
Следовательно, чтобы минимизировать использование необычных монет, мы предпочтем:
Fancyk = sum/k + 1, когда a1 › = k — sum % k
a1 ›= k — необычный1 или, a1 ›= k = sum % k => — это способ узнать, что для достижения следующего k, чтобы использовать необычные монеты, достаточно ли монет a1, чтобы компромисс.
Теперь нам также нужно проверить, было ли выполнение компромисса полезным или обременительным.
Итак, просто сравните наконец два ответа для жадного и компромиссного и верните минимальный ответ.
C. Игра на перестановку
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t--> 0) {
int n = sc.nextInt();
int arr[] = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
int count = 0;
int fm = arr[0]; //firsmin
int sm = Integer.MAX_VALUE; //secondmin
for (int i = 0; i < arr.length; i++) {
fm = Math.min(fm, arr[i]);
if (arr[i] > fm && sm > arr[i]) {
sm = arr[i];
count++;
}
}
System.out.println(count);
}
sc.close();
}
}
ЛОГИКА —
Алиса делает первый ход.
Фишка ставится на число, следующий игрок должен переместить фишку на следующее меньшее число.
Тот, кто не сможет сделать ход, побеждает в игре.
Нам нужно найти количество индексов, которые Алисе повезет выиграть в массиве.
Некоторые наблюдения:
Выбор первого элемента никогда не возможен; в противном случае Боб выиграет игру, так как он не сможет сделать ход.
Если Алиса использует второй индекс, она сможет выиграть только в том случае, если первый индекс будет строго меньше второго индекса.
Какова идеальная стратегия победы Алисы?
Как насчет того, чтобы подумать об индексах, по которым, если Боб поставит фишки, он проиграет? Другими словами, места, откуда фишку нельзя переместить дальше влево.
Это условие будет a[j] › a[i] для каждого j ‹ i. И это должно происходить только один раз в любом подмассиве.
Это идеальная выигрышная стратегия для Алисы.
Чтобы это произошло, мы берем две переменные: firstmin (fm) и Secondmin (sm).
Если наш текущий элемент становится чем-то вроде: sm ‹ curr && curr ‹ fm
Если мы обнаружим вышеуказанное условие, тогда curr — выигрышная позиция для Алисы,
и мы обновим curr = sm и двинемся дальше.
Примечание. У вас может возникнуть ошибочная идея, что если количество элементов слева от любого индекса (i) меньше и нечетно по частоте, мы можем гарантировать, что Алиса выиграет.
Нет, вы не можете этого гарантировать, потому что что, если Боб переместит фишку прямо на предпоследнюю фигуру? Ему ничто не мешает это сделать, да.
ССЫЛКА НА КОДЫ
Все коды доступны в моем репозитории на GitHub — ссылка на репозиторий.
СДЕЛАЙТЕ ЭТО, ИЛИ МНЕ БУДУ ГРУСТНО 🥺
Было бы здорово, если бы вы также могли поделиться с нами своим объяснением, если вы сделали что-то другое и сочли бы, что этим стоит поделиться, в противном случае желаю удачи в решении этих проблем.
Надеюсь, вам понравилось читать эту статью. Вы можете подписаться на меня, чтобы получать последние новости, когда я выложу еще больше таких замечательных статей.
Кто я?
Просто человек, который с энтузиазмом пишет то, что ему нравится. Технические блоги, последние технические новости, учебные пособия, решения вопросов по кодированию, редакционные статьи, советы по собеседованиям и многое другое, что вам обязательно понравится.
Кроме того, я пишу статьи для фрилансеров, поэтому вы можете связаться со мной по ссылке ниже.
Если вам понравилась эта статья, поддержите меня в этом начинании, подписавшись на меня на Medium и получайте последние обновления моих замечательных и полезных статей.
Вы можете побудить меня написать больше: https://ko-fi.com/medusaverse
Буду рад связаться с вами: https://linktr.ee/harshit_raj_14
Мои статьи вас поразили? Почему бы не подписаться на мою рассылку, чтобы получать первые обновления всякий раз, когда я загружаю новую:
