TOPIC

PROBLEM 1580 - URI Fórum 1.0

URI Online Judge asked 5 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • David Carlos replied 5 years ago

    Apenas uma dica: resolvam essa questão em python. Ele tem bignum implementado por padrão, então você conseguirá printar os resultados corretamente.

  • Thiago Magalhaes replied 3 years ago

    No segundo caso do exemplo está dando errado. Alguma dica?

    #include <iostream>
    #include <map>
    #include <string>
    
    using namespace std;
    
    int main() {
    
      long long int vet[1001], i, n, div, r;
      string palavra;
    
      vet[1] = 1;
      for (i = 2; i <= 100; i++)
        if ((vet[i-1] * i) > 1000000007)
          vet[i] = (vet[i-1] * i) % 1000000007;
        else
          vet[i] = (vet[i-1] * i);
    
      while (getline(cin, palavra)) {
        n = palavra.size();
        div = 1;
    
        map<char, int> letras;
        map<char, int>::iterator it;
    
        for (i = 0; i < n; i++)
          letras[palavra[i]]++;
    
        for (it = letras.begin(); it != letras.end(); ++it) {
          //cout << it->first << " = " << it->second << endl;
          if ((div * vet[it->second]) > 1000000007)
            div = (div * vet[it->second]) % 1000000007;
          else
            div = (div * vet[it->second]);
        }
    
        if ((vet[n] / div) > 1000000007)
          r = (vet[n] / div) % 1000000007;
        else
          r = (vet[n] / div);
    
        cout << r << endl;
      }
    }
  • Marcos Bustamante replied 5 years ago

    Alguém poderia me ajudar a encontrar o erro? Ganhei 40%

    # include <iostream>
    # include <string>
    # include <cstring>
    # include <cstdio>
    using namespace std;
    
    int main(){
        string a;
        int k, vet[30], index, tam, mult[1010];
        long long int result;
        while(cin >> a){
            memset(vet, 0, sizeof(vet));
            tam = a.size();
    
            for (int i = 1; i <= tam; ++i) {
                mult[i] = i;
            }
    
            for(int i = 0; i < tam; ++i){
                index = a[i]-'A';
                ++vet[index];
                if(vet[index] > 1){
                    for(int j = vet[index]; ; j+=vet[index]){
                        if(mult[j]%vet[index] == 0){
                            mult[j] /= vet[index];
                            break;
                        }
                    }
                }
            }
    
            result = 1;
            for(int j = tam; j > 1; --j){
                result *= mult[j];
                result %= 1000000007;
            }
    
            printf("%lld\n", result);
    
        }
        return 0;
    }
  • Beatriz Rezener replied 5 years ago

    Poxa, desculpa, então... E muito obrigada!

  • Ahmed ali Abotaleb replied 5 years ago

    Eu submeti seu código e recebi Accepted. Às vezes você enviou uma versão desatualizada dele e por isso recebeu Wrong Answer.

  • Beatriz Rezener replied 5 years ago

    Infelizmente meu código funcionou para o exemplo, mas fiquei com WA 50%, por isso eu gostaria de realizar alguns testes. Segue meu código, caso alguém consiga identificar as inconsistências e/ou puder me indicar algumas entradas:

    AC
  • Ahmed ali Abotaleb replied 5 years ago

    Acho que se seu código der o output certo para o 2º caso de teste proposto no problema, sua abordagem está correta. Isso porque o 2º caso abrange o problema dessa questão, que é justamente encontrar uma maneira de resolver as divisões grandes em aritmética modular.

  • Beatriz Rezener replied 5 years ago

    Olá, alguém poderia, por gentileza, postar mais algumas entradas e saídas significativas? O Toolkit está bugado. :/

  • Ahmed ali Abotaleb replied 5 years ago

    Oi. Alguém pode me ajudar a encontrar o que causa Possible runtime error no meu código?

    Segue:

    import java.util.Locale;
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.math.BigInteger;
    
    public class Main {
        public static void main(String[] args) throws IOException {
            Locale.setDefault(Locale.US);
    
            int[] letras = new int[26];
            int totalLetras = 0;
    
            BigInteger parteCima, parteBaixo, modulo;
    
            InputStreamReader ir = new InputStreamReader(System.in);
            BufferedReader in = new BufferedReader(ir);
    
            String palavra = null;
    
            modulo = new BigInteger("1000000007");
            while(true) {
                for(int i = 0; i < 26; i++)
                    letras[i] = 0;
    
                palavra = null;
    
                palavra = in.readLine();
                if (palavra.equals(null) || palavra == null)
                    break;
    
                totalLetras = palavra.length();
    
                for (int i = 0; i < totalLetras; i++)
                    letras[palavra.charAt(i) - 65]++;
    
                parteCima = new BigInteger("1");
                for (int i = 2; i <= totalLetras; i++) {
                    parteCima = parteCima.multiply(BigInteger.valueOf((long)i));
                }
    
                parteBaixo = new BigInteger("1");
                for(int i = 0; i < 26; i++) {
                    if(letras[i] > 1) {
                        for(int j = 2; j <= letras[i]; j++) {
                            parteBaixo = parteBaixo.multiply(BigInteger.valueOf((long) j));
                        }
                    }
                }
    
                parteCima = parteCima.divide(parteBaixo);
                parteCima = parteCima.mod(modulo);
    
                System.out.println(parteCima);
            }
            in.close();
        }
    }

    Obrigado!

  • Matheus Barroso replied 5 years ago

    Alguém poderia me dar uma luz, o toolkit não esta funcionando então não consigo testar o código com novas entradas.

    #include <iostream>
    #include <algorithm>
    #include <string.h>
    #include <math.h>
    
    using namespace std;
    
    int main()
    {
        int i,j;
        int tamanho,comeco;
        long long int Fat[1001];
        long long int den;
        long long int total;
        int mod = 1000000007;
        char nEntrada [1001];
    
        Fat[0] = 1;
        for (i = 1; i <= 1000; i++)
        {
            Fat[i] = (Fat[i-1] * i)% mod;
        }
    
        while (cin >> nEntrada)
        {
            den = 1;
            comeco = 1;
            j = 0;
            tamanho = strlen (nEntrada);
            cout << tamanho << endl;
            sort (nEntrada,nEntrada+tamanho);
    
            while(nEntrada[j] != '\0')
            {
                if (nEntrada[j]== nEntrada[j+1])
                {
                    comeco = comeco + 1;
                }
                else
                {
                    if (comeco != 1)
                    {
                        den = den * Fat[comeco] % mod;
                        comeco = 1;
                    }
                }
                j++;
            }
    
            if (Fat[tamanho] > mod || den > mod)
            {
                total = (Fat[tamanho] / den) % mod;
                cout << total << endl;
            }
            else
            {
            total = (Fat[tamanho] * pow (den,-1));
            cout << total % mod << endl;    
            }
        }
    }
  • André Esteves Martins Pinto replied 5 years ago

    Creio que resolvi o problema, e minha saída para o "Sample Input" é exatamente igual ao do "Sample Output" oferecido pelo problema. Sei que isso não é garantia alguma de minha solução estar correta, porém como os números envolvidos no segundo input do "Sample Input" são grandes o bastante para serem tratados mesmo com um long double em C, creio que é muito improvável minha resposta para esse input ser apenas coincidência, além do mais porque o número das combinações possíveis é mod 1000000007. Na página do problema há um box "Checking" com a mensagem: "This problem is being checked, i.e., the input can be modified to better suit all test cases. During this period all submissions to this problem may be re-judged.", então alguém da moderação saberia me dizer se é possível minha solução estar correta? Ou apenas as que estão corretas hoje podem ser reavaliadas para "Wrong Answer"?

    E acabei de verificar a página Submissions, e nela está para este submit o seguinte:

    Wrong answer (10%)

    Esse 10% significa que não passou em 10% dos testes? Seria isso?

  • Rodrigo Machado replied 5 years ago

    Eu entendi direito? É pra retornar o resto da divisão por 1000000007 ? Número estranho...