TEMA

PROBLEM 1288 - URI Fórum 1.0

URI Online Judge preguntado 8 years ago

URI Online Judge Fórum 1.0

MOD

Este tema fue resuelto y no puede recibir nuevas respuestas.

  • Cristhian Bonilha respondido 7 years ago

    O fato de você escolher as balas conformem elas ainda caibam, e segundo a sua ordenação, é uma escolha gulosa. Ou seja, parece uma boa escolha agora, mas nem sempre é a melhor escolha olhando-se como um todo.

    Esse caso de teste faz seu algoritmo falhar:

    1
    4
    10 21
    4 10
    4 10
    4 10
    30 12

    Ve, o fato de escolher a primeira bala que pesa 21, impede que você possa escolher as outras, enquanto que se você ignorasse a primeira bala e escolhesse as três outras, seu poder seria maior.

    Um dos algoritmos recomendados para lidar com esse tipo de problema é o Algoritmo da Mochila. Pesquise algo a respeito.

  • Allyson Dias de Lima respondido 5 years ago

    Agora quero saber uma forma para otimizá-lo.

    Alguém pode me ajudar?

  • Allyson Dias de Lima respondido 5 years ago

    Realmente, o erro era esse mesmo da matriz só caber 50, mas não percebi antes e também não entendi por que os testes com capacidade 100 funcionavam com a matriz em 50. o.O

  • 🧙The Install Wizard 🧙 respondido 5 years ago

    Nao deveria dar certo =D... sua matriz não tem tamanho suficiente para capacidades > 50

  • Allyson Dias de Lima respondido 5 years ago

    Tentei com vários testes, com capacidade 100, 99... todos bateram com o Toolkit.

    Nem aumentando as variáveis (já que o problema não especifica o tamanho) passou. 20% WA ainda.

  • 🧙The Install Wizard 🧙 respondido 5 years ago

    acho que seu código falha nos casos com capacidade alta (teste com capacidade 100)

  • Allyson Dias de Lima respondido 5 years ago

    20% de WA neste código. Alguém sabe onde está o erro?

    #include <iostream>
    #include <cstdio>
    #include <memory.h>
    
    #define FOR(a) for(int i = 0; i < a; i++)
    #define max(a, b) a>b? a:b
    
    using namespace std;
    
    int N, resistencia, capacidade;
    int poder[50], peso[50];
    int tab[50][51];
    
    int dp(int id, int cabe) {
    
        if(tab[id][cabe] != -1) return tab[id][cabe];
    
        if(id >= N || cabe <= 0) return tab[id][cabe] = 0;
    
        int naocoloca = dp(id+1, cabe);
    
        if(peso[id] <= cabe) {
            int coloca = poder[id] + dp(id+1, cabe - peso[id]);
            return tab[id][cabe] = max(coloca, naocoloca);
        }
    
        return tab[id][cabe] = naocoloca;
    
    }
    
    int main() {
    
        int casos;
        int res;
    
        scanf("%d", &casos);
    
        while(casos--) {
    
            memset(tab, -1, sizeof(int) * 50 * 51);
    
            scanf("%d", &N);
    
            FOR(N) scanf("%d %d", &poder[i], &peso[i]);
    
            scanf("%d %d", &capacidade, &resistencia);
    
            res = dp(0, capacidade);
    
            if(res >= resistencia) printf("Missao completada com sucesso\n");
            else printf("Falha na missao\n");
    
        }
    
        return 0;
    }

    Obrigado.

  • Jairo S. respondido 5 years ago

    Sim, é isso mesmo.

    Posta o seu código. Fica mais fácil de encontrar um caso de teste que faz sua solução falhar.

    Nesse meio tempo, assista esses vídeos sobre "0/1 Knapsack Problem": https://www.youtube.com/watch?v=EH6h7WA7sDw https://www.youtube.com/watch?v=8LusJS5-AGo

    Os vídeos me ajudaram bastante a entender e encontrar onde eu estava errando. Uma imagem vale mais que mil palavras :)

  • Ahmed ali Abotaleb respondido 6 years ago

    Quando utilizando o Algoritmo da Mochila, o último valor da matriz (o mais a direita no canto inferior) não é o resultado desejado? Fiz dessa maneira, apenas pegando-o na tabela, e recebo WA(20%). Alguém pode me ajudar com alguns casos de teste ou alguma indicação de falha na minha lógica?

    Obrigado!

  • Christian Alban respondido 6 years ago

    #include <iostream>
    #include <string>
    #include <cstring>
    #include <cctype>
    #include <stdio.h>
    #include <stdlib.h>
    #include <sstream>
    
    using namespace std;
    
    int main()
    {
        int n=0;
        cin >> n;
        if(n==0) cout << "Falha na missao" << endl;
        string teste;
        while(n>0)
        {
            bool w=false;
            register int x,y,k=0,p,r;
            cin >> teste;
            istringstream buffer(teste);
            buffer >> p;
            int aux=0,total=0;
            int vecx[p],vecy[p],melhor=0,my=0,totaly=0,g=0,h=0,indi=0;
            int testeu[p];
            for(int i=0; i<p; i++)
            {
                cin >> x >> y;
                vecx[i]=x;
                vecy[i]=y;
                testeu[i]=0;
            }
            cin >> k;
            cin >> r;
            for(g=0; g<p; g++)
            {
                for(int s=1; s<p; s++)
                {
                    melhor = vecx[s-1]/vecy[s-1];
                    for(h=0; h<p; h++)
                    {
                        if(vecx[h]/vecy[h]>=melhor && vecy[h]<=k && testeu[h]==0)
                        {
                            indi = h;
                            w=true;
                        }
                    }
                }
                if(w==true)
                {
                    testeu[indi]=1;
                    if(vecy[indi]+totaly<=k)
                    {
                        total+=vecx[indi];
                        totaly+=vecy[indi];
                      //  cout << " usado: " << vecx[indi]<<endl;
                    }
                }
                w=false;
                melhor=0;
                my=0;
            }
    
            if(total>=r)
            {
                cout << "Missao completada com sucesso" << endl;
            }
            else
            {
                cout << "Falha na missao" <<endl;
            }
            n--;
    
        }
    }

    Estou faz uma semana tentando e sempre recebo Wrong answer (20%), fiz muitos testes, sempre funciona! O toolkit não esta mais disponível e isso dificulta ainda mais para mim encontrar o erro!

  • Jean Marcos da Rosa respondido 7 years ago

    Opa, entendi, não estava muito familiarizado com PD, li alguns tópicos e entendi o problema, obrigado pela dica, já consegui resolver

  • Jean Marcos da Rosa respondido 7 years ago

    Olá, alguém sabe me dizer qual foi meu erro no código? Estou levando WA 10% não consegui imaginar um caso de teste que reproduza o problema, se tiverem mais casos de teste também ajuda :D

    #include <cstdio>
    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    typedef struct{
        int p;
        int b;
    } obj;
    
    bool compare(const obj &a, const obj &b){
        if(a.b==0&&b.b==0) return (b.p<a.p);
        if(b.b==0) return true;
        if(a.b==0) return false;
        if((double)(b.p/b.b)<(double)(a.p/a.b)){
            return true;
        }
        return false;
    }
    
    int main(){
        int casos, n, k, r;
        vector<obj>::iterator it;
        scanf("%d", &casos);
        while(casos--){
            scanf("%d", &n);
            vector<obj> bag(n);
            for(int i=0;i<n;i++){
                scanf("%d", &bag[i].p);
                scanf("%d", &bag[i].b);
            }
            scanf("%d", &k);
            scanf("%d", &r);
            sort(bag.begin(), bag.end(), compare);
            it = bag.begin();
            int power = 0;
            while(k&&it!=bag.end()){
                if(it->b<=k){
                    k-=it->b;
                    power+=it->p;
                }
                ++it;
            }
            (power>=r)?printf("Missao completada com sucesso\n"): printf("Falha na missao\n");
        }
        return 0;
    }
  • Jean Bez respondido 8 years ago

    Muito obrigado pelo feedback! Já corrigimos a descrição do problema.

  • Marcelo Cysneiros respondido 8 years ago

    Sobre a saída, é dito: "Se o dano total das cargas carregadas for maior que a resistência do castelo então deverá ser impressa a mensagem “Missao completada com sucesso”, caso contrário, deverá ser impressa a mensagem “Falha na missao”."

    Porém, na terceira entrada do exemplo, o maior dano causado pelo canhão é 1020, a resistência é 1020, e a saída é "Missao completada com sucesso". Então, creio que no enunciado deveria estar escrito "maior ou igual".