## 10037 - Bridge

Moderator: Board moderators

mop123
New poster
Posts: 1
Joined: Sun Sep 23, 2012 12:10 am

### Re: 10037 - Bridge

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)

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

### Re: 10037 - Bridge

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

37squared
New poster
Posts: 6
Joined: Sun Sep 16, 2012 4:15 pm

### Re: 10037 - Bridge

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;
}
}

{

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)
{
print();
}
empty();
printf("\n");
}
return 0;
}
``````

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

### Re: 10037 - Bridge

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``````

Code: Select all

``````
17
1 2
1
5 10
2
1 2

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

37squared
New poster
Posts: 6
Joined: Sun Sep 16, 2012 4:15 pm

### Re: 10037 - Bridge

brianfry713 wrote: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``````

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;
}
}

{

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)
{
print();
}
empty();
if(m<tc)
printf("\n");
}
return 0;
}
``````

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

### Re: 10037 - Bridge

Try a case where n=1.
Check input and AC output for thousands of problems on uDebug!

37squared
New poster
Posts: 6
Joined: Sun Sep 16, 2012 4:15 pm

### Re: 10037 - Bridge

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

ajeet.singh82
New poster
Posts: 6
Joined: Wed Oct 10, 2012 7:31 am

### Re: 10037 - Bridge

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
New poster
Posts: 5
Joined: Mon Mar 25, 2013 1:19 am

### Re: 10037 - Bridge

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10037 - Bridge

Try reading an integer at a time instead of line by line.
Check input and AC output for thousands of problems on uDebug!

laberle
New poster
Posts: 5
Joined: Mon Mar 25, 2013 1:19 am

### Re: 10037 - Bridge

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10037 - Bridge

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.
Check input and AC output for thousands of problems on uDebug!

laberle
New poster
Posts: 5
Joined: Mon Mar 25, 2013 1:19 am

### Re: 10037 - Bridge

brianfry713 wrote: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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10037 - Bridge

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.
Check input and AC output for thousands of problems on uDebug!

laberle
New poster
Posts: 5
Joined: Mon Mar 25, 2013 1:19 am

### Re: 10037 - Bridge

Got it. Thanks for that last test case!