102 - Ecological Bin Packing

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Aurango
New poster
Posts: 4
Joined: Sun Mar 23, 2014 2:07 pm

why runtime error !!!! uva 102

Post by Aurango » Sun Mar 23, 2014 2:16 pm

Code: Select all

import java.io.IOException;
import java.util.*;

/**
 *
 * @author AURANGO SABBIR
 */
class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        // TODO code application logic here
        Scanner sc=new Scanner(System.in);
	int[] bin1 =new int[10];
        int[] bin2 =new int[10];
        int[] bin3 =new int[10];
        int[] ans=new int[10];
        while(true){
        for(int i=1;i<=3;i++)
        {
            bin1[i]=sc.nextInt();
        }
        for(int i=1;i<=3;i++)
        {
            bin2[i]=sc.nextInt();
        }
        for(int i=1;i<=3;i++)
        {
            bin3[i]=sc.nextInt();
        }
        int min=0;
        int code=0;
        ans[0]=bin2[1]+bin3[1]+bin1[2]+bin3[2]+bin1[3]+bin2[3];
        min=ans[0];
        ans[1]=bin2[1]+bin3[1]+bin1[3]+bin3[3]+bin1[2]+bin2[2];
        if(min>ans[1])
        {
            min=ans[1];
            code=1;
        }
        ans[2]=bin2[2]+bin3[2]+bin1[1]+bin3[1]+bin1[3]+bin2[3];
        if(min>ans[2])
        {
            min=ans[2];
            code=2;
        }
        ans[3]=bin2[2]+bin3[2]+bin1[3]+bin3[3]+bin1[1]+bin2[1];
        if(min>ans[3])
        {
            min=ans[3];
            code=3;
        }
        ans[4]=bin2[3]+bin3[3]+bin1[1]+bin3[1]+bin1[2]+bin2[2];
        if(min>ans[4])
        {
            min=ans[4];
            code=4;
        }
        ans[5]=bin2[3]+bin3[3]+bin1[2]+bin3[2]+bin1[1]+bin2[1];
        if(min>ans[5])
        {
            min=ans[5];
            code=5;
        }
        if(code==0)
        {
            System.out.println("BGC " +ans[code]);
        }
        else if(code==1)
        {
            System.out.println("BCG " +ans[code]);
        }
        else if(code==2)
        {
            System.out.println("GBC " +ans[code]);
        }
        else if(code==3)
        {
            System.out.println("GCB " +ans[code]);
        }
        else if(code==4)
        {
            System.out.println("CBG " +ans[code]);
        }
        else if(code==5)
        {
            System.out.println("CGB " +ans[code]);
        }
        }
    }
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: why runtime error !!!! uva 102

Post by brianfry713 » Tue Mar 25, 2014 12:21 am

You need to stop reading the input at EOF.
You could try checking for Scanner.hasNextInt()
Check input and AC output for thousands of problems on uDebug!

Aurango
New poster
Posts: 4
Joined: Sun Mar 23, 2014 2:07 pm

Re: why runtime error !!!! uva 102

Post by Aurango » Fri Mar 28, 2014 1:07 pm

brianfry713 wrote:You need to stop reading the input at EOF.
You could try checking for Scanner.hasNextInt()
Tnx,it works for me :D

Pooria
New poster
Posts: 4
Joined: Thu May 29, 2014 9:56 pm

Why WA in Problem 102

Post by Pooria » Sat May 31, 2014 3:28 pm

Code: Select all

#include <iostream>
#include <cstdio>
using namespace std;

void check(int b,int g,int c);

long long int boxes[3][3];
char bin[3];
long long int Min,sum;

int main()
{
    bool flag = false;
    while(!flag)
    {
        Min = 999999999999999999;
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
               if(scanf("%lld",&boxes[i][j]) == EOF)
               {
                   flag = true;
                   i = 10;
                   break;
               }
            }

        }
        if(flag)
            break;
        check(0, 2, 1);
        check(0, 1, 2);
        check(2, 0, 1);
        check(2, 1, 0);
        check(1, 0, 2);
        check(1, 2, 0);
        cout<<bin[0]<<bin[1]<<bin[2]<<" "<<Min<<endl;
    }
    return 0;
}

void check(int b,int g,int c)
{
    for(int i=0;i<3;i++)
    {
        sum = boxes[(b+1)%3][0] + boxes[(b+2)%3][0] + boxes[(g+1)%3][1] + boxes[(g+2)%3][1] + boxes[(c+1)%3][2] + boxes[(c+2)%3][2];
        if(sum < Min)
        {
            Min = sum;
            bin[b] = 'B';bin[g] = 'G';bin[c] = 'C';
        }
    }
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Why WA in Problem 102

Post by brianfry713 » Wed Jun 11, 2014 10:05 pm

Input:

Code: Select all

495 685 249 891 887 451 775 685 182
AC output:

Code: Select all

CGB 3389
Check input and AC output for thousands of problems on uDebug!

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

UVA problem no. 102

Post by richatibrewal » Wed Jun 18, 2014 6:31 pm

I m getting wrong answer for uva problem no. 102. Plz help me out:

Code: Select all


#include<cstdio>
#include<climits>
using namespace std;
int main()
{
    int a[9],s[6],min,i;
    while(scanf("%d%d%d%d%d%d%d%d%d",&a[0],&a[1],&a[2],&a[3],&a[4],&a[5],&a[6],&a[7],&a[8])!=EOF)
    {
        min=INT_MAX;
        s[0]=a[3]+a[6]+a[2]+a[8]+a[1]+a[4];
        s[1]=a[3]+a[6]+a[1]+a[7]+a[2]+a[5];
        s[2]=a[5]+a[8]+a[1]+a[7]+a[0]+a[3];
        s[3]=a[5]+a[8]+a[0]+a[6]+a[1]+a[4];
        s[4]=a[4]+a[7]+a[2]+a[8]+a[0]+a[3];
        s[5]=a[4]+a[7]+a[0]+a[6]+a[2]+a[5];
        for(i=0;i<6;i++)
        {
            if(s[i]<min)
             {
                 min=s[i];
             }
        }
        if(min==s[0])
            printf("BCG %d",min);
        else if(min==s[1])
            printf("BGC %d",min);
        else if(min==s[2])
            printf("CGB %d",min);
        else if(min==s[3])
            printf("CBG %d",min);
        else if(min==s[4])
            printf("GCB %d",min);
        else if(min==s[5])
            printf("GBC %d",min);
        printf("\n");
    }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: UVA problem no. 102

Post by brianfry713 » Wed Jun 18, 2014 10:58 pm

Input:

Code: Select all

69 804 872 531 431 698 692 480 859
AC output:

Code: Select all

GBC 3242
Check input and AC output for thousands of problems on uDebug!

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

Re: UVA problem no. 102

Post by richatibrewal » Thu Jun 19, 2014 8:03 am

I m getting the required output

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: UVA problem no. 102

Post by brianfry713 » Thu Jun 19, 2014 10:04 pm

Check input and AC output for thousands of problems on uDebug!

bupjae
New poster
Posts: 2
Joined: Sun Aug 03, 2014 7:49 am

Problem 102 - Same algorithm, TLE in Java, AC in C++11

Post by bupjae » Sun Aug 03, 2014 7:53 am

Java version: http://ideone.com/Nnr2GT
C++11 version: http://ideone.com/85ldcr

Both are almost same program (except code related to read from stdin)
However, Java version got TLE; while C++11 version got AC by 0.042sec.

Is there any reason about this?

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: Problem 102 - Same algorithm, TLE in Java, AC in C++11

Post by lbv » Sun Aug 03, 2014 6:11 pm

bupjae wrote:(..) Java version got TLE; while C++11 version got AC by 0.042sec.
Is there any reason about this?
I think it is a combination of two things:

1) The judge may have a relatively large input for this problem. Many problems have small input and in those cases (where the input is just a few bytes or kB of data) any reading method usually works, regardless of the language. When the data gets bigger (in the order of hundreds or thousands of kB), it becomes more important to be careful how to read the data.

2) Java's Scanner is infamous for its performance issues. In competitive programming different alternatives are typically used, and you can find many relevant information doing a web search. One good starting point is this article, for example, but I do encourage you to spend a little time doing some research on this if you plan to use Java for solving this type of problems.

bupjae
New poster
Posts: 2
Joined: Sun Aug 03, 2014 7:49 am

Re: Problem 102 - Same algorithm, TLE in Java, AC in C++11

Post by bupjae » Mon Aug 04, 2014 8:58 am

It seems that using regex heavily in java.util.Scanner causes this issue.

I ran benchmark suggested by the article on my machine, and java.util.Scanner was ~6.5x slower than java.io.BufferedReader + parseInt

Thanks for the good article; it could help me a lot.

Dimpl
New poster
Posts: 3
Joined: Mon Dec 22, 2014 6:53 am

Re: 102 - Ecological Bin Packing

Post by Dimpl » Sun Jan 04, 2015 4:47 am

I don't understand why I received a time out error... the algorithm seems to run fine on my machine.

http://pastebin.com/WxZy9WN8

Thanks!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 102 - Ecological Bin Packing

Post by brianfry713 » Tue Jan 06, 2015 5:23 am

Try using BufferedReader
Check input and AC output for thousands of problems on uDebug!

Zin_tas
New poster
Posts: 3
Joined: Mon Feb 09, 2015 11:05 pm

problem with cin.eof()???

Post by Zin_tas » Mon Feb 09, 2015 11:11 pm

when I tried

while(!cin.eof()){...}
I got WA

and for

while(cin>>A[0][0]>>A[0][1]>>A[0][2]>>A[1][0]>>A[1][1]>>A[1][2]>>A[2][0]>>A[2][1]>>A[2][2]){...}

it got accepted....

can anyone please tell me why? Thanking in advance.... :)

Post Reply

Return to “Volume 1 (100-199)”