10037 - Bridge

[mop123]

Do you guys have any additional thoughts about this judge? My program works for all test cases in this thread but I still get WA.

I honestly think, that I've tried everything. BTW can I use this, to skip the empty line?

Code: Select all

String line = new String();
while (line.length() == 0)
    line = in.readLine();

Please help.

[brianfry713]

Read an integer at a time instead of line by line.

[37squared]

Getting wrong answer...dunno y

Code: Select all

#include <stdio.h>
#include <stdlib.h>

int a;
int arr[5000][2];

void empty()
{
     int j;
     for(j=0;j<=a;j++)
     {
                      arr[j][0]=0;
                      arr[j][1]=0;
     }
}


void add()
{

    int j,sum=0;
    for(j=0;j<=a;j++)
    {
        if((j%2)==0)
        {
            sum+=arr[j][1];
        }
        else
        {
            sum+=arr[j][0];
        }
    }
    printf("%d\n",sum);
}

void print()
{

    int j;
    for(j=0;j<=a;j++)
    {
        if((j%2)==0)
        {
            printf("%d %d\n",arr[j][0],arr[j][1]);
        }
        else
        {
            printf("%d\n",arr[j][0]);
        }
    }
}

printleft(int n,int left[])
{
           int i;
           for(i=0;i<=n;i++)
                           printf("%d\n",left[i]);
}

int main()
{
    int n,i,tc,m;

    scanf("%d",&tc);
    printf("\n");
    for(m=1;m<=tc;m++)
    {
                      scanf("%d",&n);
                      for(i=0;i<n;i++)
                      {
                      int flag=0,cnt;
                      int left[1200];
                      cnt=n-1;
                      a=0;

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


        int compare(int *p,int *q)
        {

            if(*p>*q)
            return(1);
            if(*p<*q)
            return(-1);

            return(0);
        }

        qsort(left,n,sizeof(int),*compare);

        while(cnt>2)
        {
            flag=(left[0]+(2*left[1])+left[cnt])<((2*left[0])+left[cnt]+left[cnt-1])?1:0;

                if(flag==1)
                {
                    arr[a][0]=left[0];
                    arr[a][1]=left[1];
                    arr[a+1][0]=left[0];
                    arr[a+2][0]=left[cnt-1];
                    arr[a+2][1]=left[cnt];
                    arr[a+3][0]=left[1];
                }

                else
                {
                    arr[a][0]=left[0];
                    arr[a][1]=left[cnt];
                    arr[a+1][0]=left[0];
                    arr[a+2][0]=left[0];
                    arr[a+2][1]=left[cnt-1];
                    arr[a+3][0]=left[0];
                }

                a=a+4;
                cnt=cnt-2;
                /*printleft(cnt,left);
                printf("cnt=%d\n",cnt);*/
        }
         /*printf("a=%d\n",a);*/
         if(n==1)
                 printf("%d\n",left[0]);

        else if(n%2==0)
            {
                arr[a][0]=left[0];
                arr[a][1]=left[1];
            }
        else
            {
                arr[a][0]=left[0];
                arr[a][1]=left[2];
                arr[a+1][0]=left[0];
                arr[a+2][0]=left[0];
                arr[a+2][1]=left[1];
                a+=2;
            }
        }
        if(n!=1)
        {
                add();
                print();
        }
        empty();
        printf("\n");
        }
    return 0;
}

[brianfry713]

The outputs of two consecutive cases will be separated by a blank line. Correct output:

Code: Select all

17
1 2
1
5 10
2
1 2

Your output:

Code: Select all

17
1 2
1
5 10
2
1 2

[37squared]

The outputs of two consecutive cases will be separated by a blank line. Correct output:

Code: Select all

17
1 2
1
5 10
2
1 2

Your output:

Code: Select all

17
1 2
1
5 10
2
1 2

well,.. i corrected that ... but still its WA? Here's my corrected code:

Code: Select all

#include <stdio.h>
#include <stdlib.h>

int a;
int arr[5000][2];

void empty()
{
     int j;
     for(j=0;j<=a;j++)
     {
                      arr[j][0]=0;
                      arr[j][1]=0;
     }
}


void add()
{

    int j,sum=0;
    for(j=0;j<=a;j++)
    {
        if((j%2)==0)
        {
            sum+=arr[j][1];
        }
        else
        {
            sum+=arr[j][0];
        }
    }
    printf("%d\n",sum);
}

void print()
{

    int j;
    for(j=0;j<=a;j++)
    {
        if((j%2)==0)
        {
            printf("%d %d\n",arr[j][0],arr[j][1]);
        }
        else
        {
            printf("%d\n",arr[j][0]);
        }
    }
}

printleft(int n,int left[])
{
           int i;
           for(i=0;i<=n;i++)
                           printf("%d\n",left[i]);
}

int main()
{
    int n,i,tc,m;

    scanf("%d",&tc);
    for(m=1;m<=tc;m++)
    {
                      scanf("%d",&n);
                      for(i=0;i<n;i++)
                      {
                      int flag=0,cnt;
                      int left[1200];
                      cnt=n-1;
                      a=0;

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


        int compare(int *p,int *q)
        {

            if(*p>*q)
            return(1);
            if(*p<*q)
            return(-1);

            return(0);
        }

        qsort(left,n,sizeof(int),(void *)compare);

        while(cnt>2)
        {
            flag=(left[0]+(2*left[1])+left[cnt])<((2*left[0])+left[cnt]+left[cnt-1])?1:0;

                if(flag==1)
                {
                    arr[a][0]=left[0];
                    arr[a][1]=left[1];
                    arr[a+1][0]=left[0];
                    arr[a+2][0]=left[cnt-1];
                    arr[a+2][1]=left[cnt];
                    arr[a+3][0]=left[1];
                }

                else
                {
                    arr[a][0]=left[0];
                    arr[a][1]=left[cnt];
                    arr[a+1][0]=left[0];
                    arr[a+2][0]=left[0];
                    arr[a+2][1]=left[cnt-1];
                    arr[a+3][0]=left[0];
                }

                a=a+4;
                cnt=cnt-2;
                /*printleft(cnt,left);
                printf("cnt=%d\n",cnt);*/
        }
         /*printf("a=%d\n",a);*/
         if(n==1)
                 printf("%d\n",left[0]);

        else if(n%2==0)
            {
                arr[a][0]=left[0];
                arr[a][1]=left[1];
            }
        else
            {
                arr[a][0]=left[0];
                arr[a][1]=left[2];
                arr[a+1][0]=left[0];
                arr[a+2][0]=left[0];
                arr[a+2][1]=left[1];
                a+=2;
            }
        }
        if(n!=1)
        {
                add();
                print();
        }
        empty();
       if(m<tc)
       printf("\n");
        }
    return 0;
}

[brianfry713]

Try a case where n=1.

[37squared]

Thx a lot brianfry... i had been struggling for months to get it submitted...

[ajeet.singh82]

The two strategy posted in the beginning, looks not enough -

The one I/p set posted here correctly points out - 1 10 10 10 100 100 the same.
My take -

While running into strategy -1 compute Total1
if we were crossing like
AB A YZ B AB A WX B ....
if you find out Y == B or Z == B then you got to execute strategy -2 there on wards AY A AX A AW ....

Finally compute - Total2 = A*(N-1) + Sum(2...N)

if (total1 > total2)
print total2
print AZ A AY A ....
else
print total1
print AB A YZ B..

[laberle]

Hi,

I'm having problems getting a correct answer as well. I'm following the previously posted algorithm and all of my output for the 5 inputs given by blittman matches the outputs posted. And I checked cases of 1, 2, and 3 people. Can someone help me find the problem please?

Code: Select all

#include <stdio.h>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, char* argv[])
{
	int n, numPeople;
	cin >> n;

	string s;

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

		cin >> numPeople;
		int cost = 0;
		vector<int> orderOfCrossing;
		vector<int> uncrossedSide;
		vector<int> crossedSide;

		int cost2 = 0;
		vector<int> orderOfCrossing2;
		vector<int> uncrossedSide2;
		vector<int> crossedSide2;

		cin.ignore();

		while (getline(cin, s)) {
			if (s.size() == 0) {
				break;
			}
			int x = atoi(s.c_str());
			uncrossedSide.push_back(x);
			uncrossedSide2.push_back(x);
		}


		bool low = true;
		bool newStrategy = false;
		int person1, person2;

		//Option 1  AB A YZ B...
		while (uncrossedSide.size() > 1) {
			std::sort(uncrossedSide.begin(), uncrossedSide.end());

			if (low) {
				person1 = uncrossedSide.front();
				uncrossedSide.erase(uncrossedSide.begin());
				person2 = uncrossedSide.front();
				uncrossedSide.erase(uncrossedSide.begin());
				low = false;
				cost += person2;
			}
			else {
				person1 = uncrossedSide.back(); //Z
				uncrossedSide.erase(uncrossedSide.end() - 1);
				person2 = uncrossedSide.back(); //Y
				if (person1 <= crossedSide.front() || person2 <= crossedSide.front()) {
					uncrossedSide.push_back(person1);
					newStrategy = true;
					break;
				}


				uncrossedSide.erase(uncrossedSide.end() - 1);
				low = true;
				cost += person1;
			}

			orderOfCrossing.push_back(person1);
			orderOfCrossing.push_back(person2);
			crossedSide.push_back(person1);
			crossedSide.push_back(person2);

			if (uncrossedSide.size() > 0) {
				std::sort(crossedSide.begin(), crossedSide.end());
				person1 = crossedSide.front();
				cost += person1;
				orderOfCrossing.push_back(person1);
				uncrossedSide.push_back(person1);
				crossedSide.erase(crossedSide.begin());
			}
		}

		
		if (newStrategy) { //Need to do AZ A AZ A...
			std::sort(uncrossedSide.begin(), uncrossedSide.end());

			person1 = uncrossedSide.front();
			uncrossedSide.erase(uncrossedSide.begin());
			person2 = uncrossedSide.back();
			uncrossedSide.erase(uncrossedSide.end() - 1);
			cost += person2;

			orderOfCrossing.push_back(person1);
			orderOfCrossing.push_back(person2);
			crossedSide.push_back(person1);
			crossedSide.push_back(person2);

			if (uncrossedSide.size() > 0) {
				std::sort(crossedSide.begin(), crossedSide.end());
				person1 = crossedSide.front();
				cost += person1;
				orderOfCrossing.push_back(person1);
				uncrossedSide.push_back(person1);
				crossedSide.erase(crossedSide.begin());
			}
		}

		if (uncrossedSide.size() > 0) {
			orderOfCrossing.push_back(uncrossedSide.front());
			cost += uncrossedSide.front();
			crossedSide.push_back(uncrossedSide.front());
			uncrossedSide.erase(uncrossedSide.begin());		
		}

		//Option 2 AZ A AY A ...
		while (uncrossedSide2.size() > 1) {

			std::sort(uncrossedSide2.begin(), uncrossedSide2.end());

			person1 = uncrossedSide2.front();
			uncrossedSide2.erase(uncrossedSide2.begin());
			person2 = uncrossedSide2.back();
			uncrossedSide2.erase(uncrossedSide2.end() - 1);
			cost2 += person2;

			orderOfCrossing2.push_back(person1);
			orderOfCrossing2.push_back(person2);
			crossedSide2.push_back(person1);
			crossedSide2.push_back(person2);

			if (uncrossedSide2.size() > 0) {
				std::sort(crossedSide2.begin(), crossedSide2.end());
				person1 = crossedSide2.front();
				cost2 += person1;
				orderOfCrossing2.push_back(person1);
				uncrossedSide2.push_back(person1);
				crossedSide2.erase(crossedSide2.begin());
			}
		}

		if (uncrossedSide2.size() > 0) {
			orderOfCrossing2.push_back(uncrossedSide2.front());
			cost2 += uncrossedSide2.front();
			crossedSide2.push_back(uncrossedSide2.front());
			uncrossedSide2.erase(uncrossedSide2.begin());		
		}

		int twoPerLine = 2;
		//Print results (1st option better)
		if (cost <= cost2) {
			cout << cost << endl;

			for (std::vector<int>::size_type i = 0; i < orderOfCrossing.size(); i++) {
				cout << orderOfCrossing[i];
				if (twoPerLine == 2) {
					cout << " ";
					twoPerLine = 0;
					if (i == orderOfCrossing.size() - 1) {
						cout << endl;
					}
				}
				else {
					cout << endl;
					twoPerLine++;
				}
			}
		}
		else {
			cout << cost2 << endl;
			for (std::vector<int>::size_type i = 0; i < orderOfCrossing2.size(); i++) {
				cout << orderOfCrossing2[i];
				if (twoPerLine == 2) {
					cout << " ";
					twoPerLine = 0;
					if (i == orderOfCrossing2.size() - 1) {
						cout << endl;
					}
				}
				else {
					cout << endl;
					twoPerLine++;
				}
			}
		}
		if ( (i+1) != n ) { //If not last iteration, print line
			cout << endl;
		}
	}

	return 0;
}

[brianfry713]

Try reading an integer at a time instead of line by line.

[laberle]

Still no luck...

Here's my new code (I found a different bug, but that didn't fix the wrong answer problem).

Code: Select all

// main.cpp : Defines the entry point for the console application.
//


#include <stdio.h>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;


int main(int argc, char* argv[])
{


	int n, numPeople;
	cin >> n;

	int x;

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

		cin >> numPeople;
		int cost = 0;
		vector<int> orderOfCrossing;
		vector<int> uncrossedSide;
		vector<int> crossedSide;

		int cost2 = 0;
		vector<int> orderOfCrossing2;
		vector<int> uncrossedSide2;
		vector<int> crossedSide2;

		cin.ignore();

		for (int j=0; j < numPeople; j++){
			cin >> x;
			uncrossedSide.push_back(x);
			uncrossedSide2.push_back(x);
		}


		bool low = true;
		bool newStrategy = false;
		int person1, person2;

		//Option 1
		while (uncrossedSide.size() > 1) {
			std::sort(uncrossedSide.begin(), uncrossedSide.end());

			if (!newStrategy) {

				if (low) {
					person1 = uncrossedSide.front();
					uncrossedSide.erase(uncrossedSide.begin());
					person2 = uncrossedSide.front();
					uncrossedSide.erase(uncrossedSide.begin());
					low = false;
					cost += person2;
					orderOfCrossing.push_back(person1);
					orderOfCrossing.push_back(person2);
				}
				else {
					person1 = uncrossedSide.back(); //Z
					uncrossedSide.erase(uncrossedSide.end() - 1);
					person2 = uncrossedSide.back(); //Y

					if (person1 <= crossedSide.front() || person2 <= crossedSide.front()) {
						uncrossedSide.push_back(person1);
						newStrategy = true;
						continue;
					}

					uncrossedSide.erase(uncrossedSide.end() - 1);
					low = true;
					cost += person1;

					orderOfCrossing.push_back(person2);
					orderOfCrossing.push_back(person1);
				}


				crossedSide.push_back(person1);
				crossedSide.push_back(person2);

				if (uncrossedSide.size() > 0) {
					std::sort(crossedSide.begin(), crossedSide.end());
					person1 = crossedSide.front();
					cost += person1;
					orderOfCrossing.push_back(person1);
					uncrossedSide.push_back(person1);
					crossedSide.erase(crossedSide.begin());
				}
			}

			if (newStrategy) { //Need to do AZ A AZ A...
				std::sort(uncrossedSide.begin(), uncrossedSide.end());

				person1 = uncrossedSide.front();
				uncrossedSide.erase(uncrossedSide.begin());
				person2 = uncrossedSide.back();
				uncrossedSide.erase(uncrossedSide.end() - 1);
				cost += person2;

				orderOfCrossing.push_back(person1);
				orderOfCrossing.push_back(person2);
				crossedSide.push_back(person1);
				crossedSide.push_back(person2);

				if (uncrossedSide.size() > 0) {
					std::sort(crossedSide.begin(), crossedSide.end());
					person1 = crossedSide.front();
					cost += person1;
					orderOfCrossing.push_back(person1);
					uncrossedSide.push_back(person1);
					crossedSide.erase(crossedSide.begin());
				}
			}
		}

		if (uncrossedSide.size() > 0) {
			orderOfCrossing.push_back(uncrossedSide.front());
			cost += uncrossedSide.front();
			crossedSide.push_back(uncrossedSide.front());
			uncrossedSide.erase(uncrossedSide.begin());		
		}

		//Option 2
		while (uncrossedSide2.size() > 1) {

			std::sort(uncrossedSide2.begin(), uncrossedSide2.end());

			person1 = uncrossedSide2.front();
			uncrossedSide2.erase(uncrossedSide2.begin());
			person2 = uncrossedSide2.back();
			uncrossedSide2.erase(uncrossedSide2.end() - 1);
			cost2 += person2;

			orderOfCrossing2.push_back(person1);
			orderOfCrossing2.push_back(person2);
			crossedSide2.push_back(person1);
			crossedSide2.push_back(person2);

			if (uncrossedSide2.size() > 0) {
				std::sort(crossedSide2.begin(), crossedSide2.end());
				person1 = crossedSide2.front();
				cost2 += person1;
				orderOfCrossing2.push_back(person1);
				uncrossedSide2.push_back(person1);
				crossedSide2.erase(crossedSide2.begin());
			}
		}

		if (uncrossedSide2.size() > 0) {
			orderOfCrossing2.push_back(uncrossedSide2.front());
			cost2 += uncrossedSide2.front();
			crossedSide2.push_back(uncrossedSide2.front());
			uncrossedSide2.erase(uncrossedSide2.begin());		
		}

		int twoPerLine = 2;
		//Print results (1st option better)
		if (cost <= cost2) {
			cout << cost << endl;

			for (std::vector<int>::size_type i = 0; i < orderOfCrossing.size(); i++) {
				cout << orderOfCrossing[i];
				if (twoPerLine == 2) {
					cout << " ";
					twoPerLine = 0;
					if (i == orderOfCrossing.size() - 1) {
						cout << endl;
					}
				}
				else {
					cout << endl;
					twoPerLine++;
				}
			}
		}
		else {
			cout << cost2 << endl;
			for (std::vector<int>::size_type i = 0; i < orderOfCrossing2.size(); i++) {
				cout << orderOfCrossing2[i];
				if (twoPerLine == 2) {
					cout << " ";
					twoPerLine = 0;
					if (i == orderOfCrossing2.size() - 1) {
						cout << endl;
					}
				}
				else {
					cout << endl;
					twoPerLine++;
				}
			}
		}
		if ( (i+1) != n ) { //If not last iteration, print line
			cout << endl;
		}
	}


	return 0;
}

[brianfry713]

Input:

Code: Select all

1

1
1

AC output:

Code: Select all

1
1

Don't print a space at the end of a line.

[laberle]

Input:

Code: Select all

1

1
1

AC output:

Code: Select all

1
1

Don't print a space at the end of a line.

Shouldn't that just be a presentation error? Regardless, I changed my code to not print a space at the end of a line, and I'm still getting WA.

[brianfry713]

Don't count on getting PE. Try input:

Code: Select all

1

20
95
95
88
89
62
70
51
53
45
47
32
38
28
31
27
28
24
23
5
15

AC output:

Code: Select all

803
5 15
5
95 95
15
5 15
5
88 89
15
5 15
5
62 70
15
5 15
5
51 53
15
5 15
5
45 47
15
5 15
5
32 38
15
5 15
5
28 31
15
5 15
5
27 28
15
5 24
5
5 23
5
5 15

Post your updated code if you're still having trouble.

[laberle]

Got it. Thanks for that last test case!