TOPIC

PROBLEM 1286 - URI Fórum 1.0

beecrowd asked on Feb 8 2013

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Lucas156 replied 7 years ago

    Não entendo por que a solução gulosa não funciona em um dos casos, já que o problema diz:

    Enquanto a resposta do seguinte caso de teste dá 77, enquanto deveria dar 75 se pegar sempre os pedidos mais demorados.

    5
23
43 9
4 1
17 2
13 5
54 17

  • wbrito replied 9 years ago

    @Matheus Cordeiro

    Sua sua recursão está correta. Para evitar ficar recalculando valores, você pode utilizar uma técnica chamada "Memoization". É bastante simples: Se vc já conhece um resultado, simplesmente olhe na tabela. Se ainda não sabe, continue calculando recursivamente. Você pode ver esse vídeo, ele vai te ajudar bastante: https://www.youtube.com/watch?v=dZ0OS4YUs2A

  • wbrito replied 9 years ago

    Pesquise pelo problema da mochila booleana (programação dinâmica).

    sua solução falha pra esse caso:

    10
17
661 836
586 962
628 486
233 997
247 854
460 798
769 10
994 455
169 265
319 173
0

    a saída deveria ser "769 min."

  • epinheiro1 replied 7 years ago

    Obrigado pela resposta! Tentarei corrigir os erros.

  • epinheiro1 replied 7 years ago

    Olá, gostaria de saber por que o meu código recebe Wrong answer, sendo que aparentemente passa em todos os testes realizados. 

    #include <iostream>
#include <stdio.h>

using namespace std;

int tempo[30], pizzas[30];
int n, p;

int sol(int n, int p) {

    if (n < 0) {
        return 0;
    }
    if (pizzas[n] > p) {
        return sol(n-1, p);
    } else {
        return max(sol(n-1, p), sol(n-1, p - pizzas[n]) + tempo[n]);
    }
}

int main()
{
    scanf("%d", &n);
    scanf("%d", &p);

    for(int i = 1; i <= n; i++){
        scanf("%d %d", &tempo[i], &pizzas[i]);
    }
    printf("%d min.", sol(n, p));

}

  • favenger replied 7 years ago

    i'm always having runtime error i can't figure the error help !!

    #include <iostream>
#include <algorithm>

using namespace std;

int main()
{

    int n,mw,m;
    cin>>n;
    while(true)
    {
        cin>>mw;
        m=mw+1;
        n++;
        int mat[n][m];

        for(int i=0;i<n;i++)
        {
            mat[i][0]=0;
        }
        for(int i=0;i<m;i++)
        {
            mat[0][i]=0;
        }
        int vl[n],wt[n];
        for(int i=0;i<n-1;i++)
            cin>>vl[i]>>wt[i];
        for(int i=1;i<n;i++)
        {
            for(int j=1;j<m;j++)
            {
                if(wt[i]>j)
                    mat[i][j]=mat[i-1][j];
                else
                {
                    mat[i][j]=max((mat[i-1][j]),vl[i]+mat[i-1][j-wt[i]]);
                }
            }
        }
        cout<<mat[n-1][m-1]<<" min.\n";
        cin>>n;
        if(n==0)break;

    }
    return 0;
}

  • Joao40 replied 7 years ago

    O exercício quer que você maximize o tempo total. Nem sempre pegar o maior tempo de cada entrega vai dar o maior tempo final.

  • albertininm replied 8 years ago

    Gostaria de saber porque estou recebendo WA. Aqui vai meu código, funciona para todos os casos de teste, inclusive para o que o wyllian postou aqui...

    #include <stdio.h>
#include <bits/stdc++.h>
//%lld
typedef long long ll;
using namespace std;
//Knapsack
int peso[2005];
int valor[2005];
int matriz[2005][2005];
int main(){
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int s, n;
    while(scanf("%d", &n)==1){
        if(n==0)break;
        else{
            memset(matriz, 0, sizeof(matriz));
            memset(valor, 0, sizeof(valor));
            memset(peso, 0, sizeof(peso));
            scanf("%d", &s);
            for(int i = 0;i<n;i++){
                scanf("%d%d", &valor[i], &peso[i]);
            }
            for(int i = peso[0];i<=s;i++){
                matriz[0][i] = valor[0];
            }
            for(int i = 1;i<=n;i++){
                for(int j = 1;j<=s;j++){
                    if(peso[i]>j){
                        matriz[i][j] = matriz[i-1][j];
                    }else{
                        matriz[i][j] = max((valor[i]+matriz[i-1][j-peso[i]]), matriz[i-1][j]);
                    }
                }
            }
            int saida = 0;
            for(int i = 0;i<=s;i++){
                if(matriz[i][s]>saida)saida = matriz[i][s];
            }
            printf("%d min.\n", saida);
        }
    }
}

  • gvdfarias replied 8 years ago

    Estou levando 10%WA, mas não consigo ver onde está meu erro

    #include <bits/stdc++.h>

using namespace std;

int n,p,pedidos[25][2],pd[25][35];

int pdF(int obj,int pizza){
    if(pd[obj][pizza]!=-1)
        return pd[obj][pizza];

    if(obj>n || pizza<0)
        return pd[obj][pizza]=0;

    int nC=pdF(obj+1, pizza);

    if(pedidos[obj][1]<=pizza){
        int coloca=pedidos[obj][0]+pdF(obj+1,pizza-pedidos[obj][1]);

        if(coloca>nC)
            return pd[obj][pizza]=coloca;
        else
            return pd[obj][pizza]=nC;
    }

    return pd[obj][pizza]=nC;
}

int main(){
    scanf("%d",&n);
    scanf("%d",&p);

    for(int i=0;i<n+2;i++)
        for(int j=0;j<p+2;j++)
            pd[i][j]=-1;

    for(int i=0;i<n;i++)
        scanf("%d %d",&pedidos[i][0],&pedidos[i][1]);

    printf("%d min.\n", pdF(0,p));

    for(int i=0;i<n;i++){
        pedidos[i][1]=p+5;
    }

    scanf("%d",&n);

    while(n!=0){
        scanf("%d",&p);

        for(int i=0;i<n+2;i++)
            for(int j=0;j<p+2;j++)
                pd[i][j]=-1;

        for(int i=0;i<n;i++)
            scanf("%d %d",&pedidos[i][0],&pedidos[i][1]);

        printf("%d min.\n", pdF(0,p));

        for(int i=0;i<n;i++)
            pedidos[i][1]=p+5;

        scanf("%d",&n);
    }

    return 7;
}

  • mgcordeiro replied 9 years ago

    Obrigado pela ajuda, Wyllian. Finalmente consegui. Muito obrigado.

  • mgcordeiro replied 9 years ago

    Olá, Wyllian. Gostaria da sua ajuda novamente. Depois de pesquisar sobre o problema da mochila booleana, consegui fazer um programa que calcula o resultado correto, mas excede o tempo limite de execução ("Time limit exceeded"). O que eu faço agora?

    #include <stdio.h>

#define max(A,B) ((A>B) ? (A):(B))

int f(int pedido, int espaco, int *tempo, int *pizzas)
{
    if (pedido < 0) return 0;
    if (espaco < pizzas[pedido]) return f(pedido - 1, espaco, tempo, pizzas);
    return max (f(pedido - 1, espaco - pizzas[pedido], tempo, pizzas) + tempo[pedido], f(pedido - 1, espaco, tempo, pizzas));
}

int main()
{
    int x, pedido, espaco, tempo[20], pizzas[20];
    scanf ("%d", &pedido);
    while (pedido > 0)
    {
        scanf ("%d", &espaco);
        for (x = 0; x < pedido; x++) scanf ("%d%d", &tempo[x], &pizzas[x]);
        printf ("%d min.\n", f(pedido - 1, espaco, tempo, pizzas));
        scanf ("%d", &pedido);
    }
    return 0;
}

  • mgcordeiro replied 9 years ago

    Olá. Gostaria de uma ajuda para entender o que há de errado no meu código, pois ele, aparentemente, dá as respostas corretas, mas ainda recebo "Wrong answer", obrigado.

    #include <stdio.h>

int main()
{
    int x, y, z, cont, pedidos, max_pizzas, pizzas, tempos[20], pizza[20], max_tempo = 0, tempo = 0;
    scanf ("%d", &pedidos);
    while (pedidos > 0)
    {
        scanf ("%d", &max_pizzas);
        for (x = 0; x < pedidos; x++) scanf ("%d%d", &tempos[x], &pizza[x]);
        for (x = 0; x < pedidos; x++)
        {
            for (y = x, tempo = 0, pizzas = max_pizzas; y < pedidos; y++)
            {
                if (pizzas >= pizza[y])
                    {
                        tempo += tempos[y];
                        pizzas -= pizza[y];
                        if (tempo > max_tempo) max_tempo = tempo;
                        cont = 1;
                    }
                else
                    {
                        if ((cont == 1) && (y > x) && (tempo > tempos[y-1]))
                        {
                            tempo -= tempos[y-1];
                            pizzas += pizza[y-1];
                            cont = 0;
                            y--;
                        }
                    }
            }
        }
        printf("%d min.\n", max_tempo);
        max_tempo = 0;
        scanf("%d", &pedidos);
    }
    return 0;
}

  • crbonilha replied on Oct 20 2013

    A sua solução é gulosa, ou seja, ela escolhe a opção que parece melhor no momento, sem pensar nas consequências futuras. Experimente esse caso de teste:

    4
10
10 9
9 1
8 1
7 1

    Pesquise o algoritmo da mochila, próprio para esse exercício.

  • lblanger replied on Oct 18 2013

    Olá, o meu código passa nos casos de teste porém recebe wrong, o que há de errado?

    #include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef struct {
    int pizzas;
    int tempo;
} Entrega;

bool ordenar(Entrega a, Entrega b){
    return a.tempo > b.tempo;
}

int main(){
    int n, pizzas;

    while(scanf("%d", &n) and n != 0){
        Entrega x[n];

        scanf("%d", &pizzas);

        for(int i=0; i<n; i++){
            scanf("%d%d", &x[i].tempo, &x[i].pizzas);
        }

        sort(x, x+n, ordenar);

        int tempoMax = 0, acumPizzas, acumTempo;

        for(int i=0; i<n; i++){
            acumPizzas = x[i].pizzas;
            acumTempo = x[i].tempo;

            for(int j=0; j<n; j++){

                if( i!=j and acumPizzas+x[j].pizzas <= pizzas){
                    acumTempo += x[j].tempo;
                    acumPizzas += x[j].pizzas;
                }
            }

            if(acumTempo > tempoMax){
                tempoMax = acumTempo;
            }
        }

        printf("%d min.\n", tempoMax);
    }
}