Сокращение строки - Конкурс по программированию. Требуется решение

Question

У меня есть вопрос, который просит нас сократить строку следующим образом.

Вводом является строка, имеющая только A, B или C. Выход должен быть длиной сокращенная строка

Строка может быть уменьшена по следующим правилам

Если любые две разные буквы соседствуют, эти две буквы могут быть заменяется третьей буквой.

Например, ABA -> CA -> B. Таким образом, окончательный ответ равен 1 (длина сокращенной строки)

Например ABCCCCCCC

Это не становится CCCCCCCC, так как может быть уменьшено альтернативно на

ABCCCCCCC -> AACCCCCC -> ABCCCCC -> AACCCC -> ABCCC -> AACC -> ABC -> AA

как здесь длина 2 <(длина <code>CCCCCCCC)

Как вы решаете эту проблему?

Большое спасибо!

Чтобы прояснить ситуацию: в вопросе говорится, что ему нужна минимальная длина сокращенной строки. Таким образом, во втором примере выше возможны 2 решения, одно CCCCCCCC, а другое AA. Таким образом, 2 является ответом, поскольку длина AA равна 2, что меньше, чем длина CCCCCCCC = 8.

Answer 1

Не лучше ли было бы посчитать, какая буква у вас больше всего, и найти способы ее удаления?Продолжайте, пока у нас не будет только одного письма.Мы могли бы иметь это много раз, но пока это то же самое, нам все равно, мы закончили.

Чтобы избежать превращения чего-то вроде ABCCCCCCC в CCCCCCCC.

Мы удаляем самое популярное письмо:

-ABCCCCCCC
-AACCCCCC
-ABCCCCC
-AACCCC
-ABCCC
-AACC
-ABC
-AA

Я не согласен с предыдущим постером, который заявляет, что мы должны иметь длину 1 или 2 - что произойдет, если я войдуначальная строка AAA?

Answer 2

//C# Coding

using System;

using System.Collections.Generic;


namespace ConsoleApplication1
{

class Program
    {

static void Main(string[] args)

{

/*
         Keep all the rules in Dictionary object 'rules'; 
         key - find string, value - replace with value 
         eg: find "AB" , replace with "AA" 
        */

        Dictionary<string, string> rules = new Dictionary<string, string>();
        rules.Add("AB", "AA");
        rules.Add("BA", "AA");
        rules.Add("CB", "CC");
        rules.Add("BC", "CC");
        rules.Add("AA", "A");
        rules.Add("CC", "C");

        // example string
        string str = "AABBCCCA";

        //output
        Console.WriteLine(fnRecurence(rules, str));
        Console.Read();
    }

    //funcation for applying all the rules to the input string value recursivily
    static string fnRecurence(Dictionary<string, string> rules,string str)
    {
        foreach (var rule in rules)
        {
            if (str.LastIndexOf(rule.Key) >= 0)
            {
                str = str.Replace(rule.Key, rule.Value);
            }
        }

        if(str.Length >1)
        {
            int find = 0;
            foreach (var rule in rules)
            {
                if (str.LastIndexOf(rule.Key) >= 0)
                {
                    find = 1;
                }
            }

            if(find == 1)
            {
                str = fnRecurence(rules, str);
            }
            else
            {
                //if not find any exit 
                find = 0;
                str = str;
                return str;
            }
        }

        return str;

    }


}

}

Answer 3

        int previous = a.charAt(0);
        boolean same = true;
        int c = 0;
        for(int i = 0; i < a.length();++i){
            c ^= a.charAt(i)-'a'+1;
            if(a.charAt(i) != previous) same = false;
        } 
        if(same) return a.length();
        if(c==0) return 2;
        else return 1;

Answer 4

Вы можете решить это, используя 2 прохода.

На первом проходе вы применяете

len = strlen (str) ;
index = 0 ;
flag = 0 ;

/* 1st pass */
for ( i = len-1 ; i > 0 ; i -- ) {
  if ( str[i] != str[i-1] ) {
    str[i-1] = getChar (str[i], str[i-1]) ;
    if (i == 1) {
      output1[index++] = str[i-1] ;
      flag = 1 ;
      break ;
    }
  }
  else output1[index++] = str[i] ;

}

if ( flag == 0 ) 
  output1[index++] = str[i] ;
output1[index] = '\0';

И на втором проходе вы применяете то же самое к 'output1', чтобы получить результат.Итак, один - проход вперед, другой - проход назад.

Answer 5

Сравните два символа за раз и замените, если оба соседних символа не совпадают. Чтобы получить оптимальное решение, запустите один раз от начала строки и один раз от конца строки. Вернуть минимальное значение.

Rav решение: -

int same(char* s){
    int i=0;
    for(i=0;i<strlen(s)-1;i++){
            if(*(s+i) == *(s+i+1))
                    continue;
            else
                    return 0;
    }
    return 1;
}


int reduceb(char* s){
    int ret = 0,a_sum=0,i=0;
    int len = strlen(s);
    while(1){
            i=len-1;
            while(i>0){
                    if ((*(s+i)) == (*(s+i-1))){
                                    i--;
                                    continue;
                    } else {
                            a_sum = (*(s+i)) + (*(s+i-1));
                            *(s+i-1) = SUM - a_sum;
                            *(s+i) = '\0';
                            len--;
                    }
                    i--;
            }
            if(same(s) == 1){
                    return strlen(s);
                    }
}
}


int reducef(char* s){
    int ret = 0,a_sum=0,i=0;
    int len = strlen(s);
    while(1){
            i=0;
            while(i<len-1){
                    if ((*(s+i)) == (*(s+i+1))){
                                    i++;               
                                    continue;
                    } else {
                            a_sum = (*(s+i)) + (*(s+i+1));
                            *(s+i) = SUM - a_sum;
                            int j=i+1;
                            for(j=i+1;j<len;j++)
                                    *(s+j) = *(s+j+1);
                            len--;
                    }
                    i++;
            }
            if(same(s) == 1){
                    return strlen(s);
                    }
}
}

int main(){
    int n,i=0,f=0,b=0;
    scanf("%d",&n);
    int a[n];

    while(i<n){
            char* str = (char*)malloc(101);
            scanf("%s",str);
            char* strd = strdup(str);
            f = reducef(str);
            b = reduceb(strd);

            if( f > b)
                    a[i] = b;
            else
                    a[i] = f;
            free(str);
            free(strd);
            i++;
    }

    for(i=0;i<n;i++)
            printf("%d\n",a[i]);

}

@ Rav

этот код не будет введен для ввода "abccaccba". решение должно быть только "б" но этот код не даст этого. Так как я не получаю правильное место для комментариев (из-за низких баллов или по любой другой причине), поэтому я сделал это здесь.

Answer 6

import java.util.Scanner;

public class StringReduction {

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String str = sc.nextLine();
    int length = str.length(); 
    String result = stringReduction(str);
    System.out.println(result); 
}

private static String stringReduction(String str) {
    String result = str.substring(0);
    if(str.length()<2){
        return str;
    }
    if(str.length() == 2){
        return combine(str.charAt(0),str.charAt(1));
    }
    for(int i =1;i<str.length();i++){
        if(str.charAt(i-1) != str.charAt(i)){ 
            String temp = str.substring(0, i-1) + combine(str.charAt(i-1),str.charAt(i)) + str.substring(i+1, str.length()); 
            String sub = stringReduction(temp);
            if(sub.length() < result.length()){
                result = sub;
            }
        }
    }
    return result;
}

private static String combine(char c1, char c2) { 
    if(c1 == c2){
        return "" + c1 + c2;
    }
    else{
        if(c1 == 'a'){
            if(c2 == 'b'){
                return "" + 'c';
            }
            if(c2 == 'c') {
                return "" + 'b';
            }
        }
        if(c1 == 'b'){
            if(c2 == 'a'){
                return "" + 'c';
            }
            if(c2 == 'c') {
                return "" + 'a';
            }
        }
        if(c1 == 'c'){
            if(c2 == 'a'){
                return "" + 'b';
            }
            if(c2 == 'b') {
                return "" + 'a';
            }
        }
        return null;
    } 
}

}

Answer 7

Эту проблему можно решить с помощью жадного подхода.Постарайтесь найти наилучшую позицию для применения преобразования, пока преобразования не существует.Наилучшая позиция - это позиция с максимальным количеством различных соседей преобразованного символа.