Codeforces Round 893 (Div. 2) включваше два интригуващи проблема, „Бутони“ (Проблем A) и „Още един проблем с пермутация“ (Проблем 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 a = sc.nextInt(); //pressed by Anna only
int b = sc.nextInt(); //pressed by Katie only
int c = sc.nextInt(); //can be pressed by either
if (c % 2!=0 && a==b) System.out.println("First");
else if (a > b) System.out.println("First");
else System.out.println("Second");
}
sc.close();
}
}
ЛОГИКА —
Анна прави първия ход.
Играта е оптимална -› всеки играч играе за победа
Момичето, което не може да натисне бутон, губи. -› Този, който не може да направи ход, губи.
За да спечели, Анна би искала да завърши бутоните c и след това може да отдели време, за да завърши своите бутони a.
Същото за Кейти, тя ще иска да завърши първо бутоните c и след това отидете на бутоните b.
Сега общи случаи -› (a,b,c)
Случай I: (0,0,четно) -› в този случай Анна започва и след това Кейти играе. Така например-2 -› тогава Кейти печели, играейки последния ход
Случай II: (0,0,нечетно) -› в този случай Анна започва и след това Кейти играе. И така, например-3 -› Анна печели
И така, какво ще стане, ако a=a и b=b =› (a,b,c)
ПОКЛЮЧИТЕЛНИ 5 СЛУЧАЯ:
Ако c е четно и a›b =› (2,1,even=2) =› бутон c завършва с игра на Кейти. Анна печели, защото може да играе с един допълнителен бутон в собствения си случай.
Ако c е четно и a‹=b =› (1,2,even=2) =› бутон c завършва с игра на Кейти. Katie печели с допълнителни бутони за игра.
Ако c е нечетно и a›b =› (2,1,odd=3) =› бутон c завършва с игра на Анна. Anna печели.
Ако c е нечетно и a‹b =› (1,2,odd=3) =› бутон c завършва с игра на Anna. Katie печели.
Допълнителен случай: Ако c е нечетно и a==b =› (1,1,odd=3) =› бутон c завършва с игра на Anna. Анна печели.
Горното заключение:
Първо проверете специалния случай -› c е нечетно и a==b =› Анна печели
Случай I : a›b =›Анна печели независимо c е нечетно или четно
Случай II: a‹=b( c четно) или a‹b(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 a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
if(c%2==0){
System.out.println(a>b?"First":"Second");
}else{
System.out.println(b>a?"Second":"First");
}
}
}
}
ТРЕТО РЕШЕНИЕ
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 a = sc.nextInt(); //pressed by Anna only
int b = sc.nextInt(); //pressed by Katie only
int c = sc.nextInt(); //can be pressed by either
a+=Math.ceil(c/2.0);
b+=Math.floor(c/2.0);
if(a>b) System.out.println("First");
else System.out.println("Second");
}
sc.close();
}
}
ЛОГИКА — -
Забележка: Няма да използваме a+=Math.ceil(c/2);
Вместо това използваме a+=Math.ceil(c/2.0);
Тъй като искаме да направим деление с плаваща единица и след това да намерим неговия ceil или floor.
Ако направим целочислено деление /2, вече получаваме съкратеното стойностите тогава подът и таванът губят предназначението си.
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];
int index=0;
for(int i=1;i<=n;i+=2){ //since we are taking double of each element in secodn loop the only element left not to be counted will be the odd oens so take a jump of 2 starting from 1 => will land on odd
for(int j=i;j<=n;j*=2){
arr[index]=j;
index++;
}
}
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
}
sc.close();
}
}
ЛОГИКА — -
Пермутацията на n е пермутацията на масив [1,2,3,….,n]
Стъпка 1: Намира ли определена пермутация
di=gcd(ai,a(imodn)+1) = › намиране на gcd от последователни елементи
Стъпка 2: Създаване на друг масив от дадения gcd израз за всяка пермутация
Стъпка 3: Изчисляване на резултата на всяка пермутация чрез преброяване на броя на отделните елементи във формирания gcd масив
Върнете пермутацията с максималния резултат
напр.: n=5 -› 1,2,3,4,5
gcd максимален резултат може да бъде направен чрез пермутация 1,2,4,3,5
gcd(1,2) -› 1
gcd(2,4) -› 2
gcd(4,3) -› 1
gcd(3,5) -› 1
gcd(5,1) - › 1 //a(imodn)+1
Резултат =2 (максимален възможен резултат)
напр.: n=7 -› 1,2,3,4,5,6,7
gcd максимален резултат може да бъде направен чрез пермутация 1,2,4,3,6,5,7
gcd (1,2) -› 1
gcd(2,4) -› 2
gcd(4,3) -› 1
gcd(3,6) -› 3
gcd(6,5) -› 1
gcd(5,7) -› 1
gcd(7,1) -› 1
резултат = 3 (максимален възможен резултат)
Сега, ако се опитаме да намерим максималния брой отделни gcd на съседен елемент на пермутацията, той никога няма да надхвърли n/2.
Запомнете, че може да се провери и чрез наблюдение.
Например пермутацията на n=10 ще има максимум 5 отделни gcds.
отделните gcds са — 1,2,3,4,5
Това идва от 1,2,4, 8,3,6,5,10,7,9
Сега можете да видите, че сме подредили съседните елементи като двойни, за да получим различни gcds
1,2 =› 1
2, 4 =› 2
4,8 =› 4
3,6 =› 3
5,10 =› 5
Сега, тъй като двойно от 6 (т.е. 12) надвишава 10. Ще ни даде само повтарящ се gcd и така нататък за други числа като 7,9
Така че нашата цел трябва да бъде да получим двойника на всяко число едно до друго
Това, което трябва да направим, е да намерим модел, който да направи това да се случи сега. Ето до какво се свежда нашият въпрос.
Да удвоим съседните елементи и да ги представим.
Проблемът изисква от нас да намерим пермутацията, която дава максималния gcd.
ПО-ДОБРО И ЛЕСНО ЕЛЕГАНТНО РЕШЕНИЕ
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();
HashSet<Integer> set = new HashSet<>(); //all elemtn sar egoing to be distinct in permutation
for(int i=1;i<=n;i++){
set.add(i);
}
for(int i=1;i<=n;i++){
if(set.contains(i)){
int j=i;
while(j<=n){
System.out.print(j+" ");
set.remove(j);
j*=2;
}
}
}
System.out.println();
}
sc.close();
}
}
ЛОГИКА — ПО-ДОБРО РЕШЕНИЕ ЗА НАМИРАНЕ НА НЕОБХОДИМИЯ ШАБЛОН
За да генерираме типа шаблон, който искаме
Поставяме всички елементи в хешсет
Започваме с първия елемент и след това продължаваме да поставяме неговия двоен, докато надхвърлим.
В същото време премахваме елементи, използвани от хешсет
И продължете да повтаряте само ако наборът все още съдържа числото.
ВРЪЗКА КЪМ КОДОВЕ
Всички кодове са налични в моето репо в GitHub — репо връзка
НАПРАВИ ТОВА ИЛИ ЩЕ БЪДА ТЪЖЕН 🥺
Би било чудесно, ако можете също да споделите обяснението си с нас, ако сте направили нещо различно и смятате, че си струва да го споделите, в противен случай пожелаваме успех при решаването на тези проблеми.
Надявам се, че ви е харесало да прегледате статията. Можете да ме последвате, за да получите най-новата актуализация, когато кача още такава невероятна статия.
Кой съм аз?
Просто някой, който е ентусиазиран да пише това, което му харесва. Технически блогове, най-нови технически новини, уроци, решения на въпроси за кодиране, редакционни статии, съвети за интервюта и много други неща, които със сигурност ще харесате.
Освен това пиша статии за свободна практика, така че можете да се свържете с мен чрез връзката по-долу.
Ако сте харесали тази статия, подкрепете ме в това начинание, като ме последвате средно и получавате най-новите актуализации на моите невероятни и полезни статии.
Можете да ме насърчите да пиша повече на: https://ko-fi.com/medusaverse
Ще се радвам да се свържа с вас: https://linktr.ee/harshit_raj_14
