## 10037 - Bridge

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

Moderator: Board moderators

reiners
New poster
Posts: 9
Joined: Fri May 30, 2003 6:50 pm
Location: San Francisco

### 10037: Bridge

I'm getting WA for my submission below. Could someone please give me an input for which my submission fails, and what the expected output is?

[cpp]
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

int max(int n1, int n2) {
return n1 >= n2 ? n1 : n2;
}

int min(int n1, int n2) {
return n1 <= n2 ? n1 : n2;
}

int solveBridgeProblem(vector<int> times, bool print) {
bool onLeftBank[1000];
bool onRightBank[1000];
int cnt = times.size();
for (int i = 0; i < 1000; i++) {
onLeftBank = (i < cnt);
onRightBank = false;
}
int totalTime = 0;
for (int i = 0; i < cnt - 1; i++) {
int t1;
int t2;
bool t1Found = false;
bool t2Found = false;
int index;
if (i % 2 == 0) {
index = 0;
}
else {
index = cnt - 1;
}
while (!t1Found || !t2Found) {
if (onLeftBank[index]) {
if (!t1Found) {
t1 = index;
t1Found = true;
}
else {
t2 = index;
t2Found = true;
}
}
if (i % 2 == 0) {
index++;
}
else {
index--;
}
}
totalTime += max(times[t1], times[t2]);
if (print) {
cout << min(times[t1], times[t2]) << " "
<< max(times[t1], times[t2]) << endl;
}
onLeftBank[t1] = false;
onLeftBank[t2] = false;
onRightBank[t1] = true;
onRightBank[t2] = true;

if (i < cnt - 2) {
index = 0;
t1Found = false;
while (!t1Found) {
if (onRightBank[index]) {
t1 = index;
t1Found = true;
}
index++;
}
totalTime += times[t1];
if (print) {
cout << times[t1] << endl;
}
onLeftBank[t1] = true;
onRightBank[t1] = false;
}
}

}

int getTotalTime(vector<int> times) {
return solveBridgeProblem(times, false);
}

void printCrossings(vector<int> times) {
solveBridgeProblem(times, true);
}

int main (int argc, const char * argv[]) {
int testCaseCnt;
cin >> testCaseCnt;
for (int i = 0; i < testCaseCnt; i++) {
string s;
getline(cin, s);
int itemCnt;
cin >> itemCnt;
vector<int> times;
for (int j = 0; j < itemCnt; j++) {
int time;
cin >> time;
times.push_back(time);
}
sort(&times[0], &times[itemCnt]);

int totalTime = getTotalTime(times);
cout << totalTime << endl;
printCrossings(times);
cout << endl;
}

return 0;
}
[/cpp]

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
hank wrote:I also got WA many times,but I still can't find any bug in my program!
any idea?
by the way,
How did you know the judge's testdata is wrong?
As I recall, some of the Waterloo input files had extra data at the end. This caused no problems at Waterloo, where there was only one test case per input file (programs simply terminated and ignored the extra input). But when the files were joined for multiple input at acm.uva.es, many programs were tripped up by the extra data.

I believe if, after processing the data for a case, you skip forward to find the blank line that separates input cases, you'll be OK. Or it may be that this problem has been fixed - it was noted a long time ago.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
As LittleJohn wrote, the problem has been rejudged. To Hank:
There is nothing wrong with the judge input now, so if you have wrong answer your program is wrong.

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
Can it be proven that we must always consider both strategies of Little John? I mean is it possible that for big enough n, only one of the strategies is sufficient?

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
Can somebody post some test input data?

reiners
New poster
Posts: 9
Joined: Fri May 30, 2003 6:50 pm
Location: San Francisco
Test input data, with matching correct output data, would be especially nice.

jcosta
New poster
Posts: 1
Joined: Sat Apr 24, 2004 8:25 pm

### 10037 : Bridge

hi
im still getting WA with this one
can sb help me out with some input/output tests?

heres my code[cpp]#include <iostream>
#include <cstdlib>
using namespace std;

int cmp_int(const void *a, const void *b) {

const int *ia = (const int *) a;
const int *ib = (const int *) b;

return (*ia > *ib) - (*ia < *ib);
}

int main () {

int numberOfCases;
cin >> numberOfCases;

for(int cases = 0; cases < numberOfCases; cases++) {

int n;
cin >> n;

int people[n];
// reading the vector
for(int i = 0; i < n ; i++) {
int time;
cin >> time;
people = time;
}

// sorting
qsort(people, n, sizeof(int), cmp_int);

int peopleLeft = n;
int timeSpent = 0;
int moves[3*n];
int pos = 0;
while(peopleLeft > 3) {
int a, b, x, y;
a = people[0];
b = people[1];
x = people[peopleLeft-2];
y = people[peopleLeft-1];

int time1 = b + a + y + b;
int time2 = x + a + y + a;

peopleLeft -=2;
if(time1 < time2) {
moves[pos] = a;
moves[pos+1] = b;

moves[pos+2] = a;

moves[pos+3] = x;
moves[pos+4] = y;

moves[pos+5] = b;
pos += 6;

timeSpent += time1;
}
else {
moves[pos] = a;
moves[pos+1] = x;

moves[pos+2] = a;

moves[pos+3] = a;
moves[pos+4] = y;

moves[pos+5] = a;
pos += 6;

timeSpent += time2;
}
}

if(peopleLeft == 3) {
moves[pos] = people[0];
moves[pos+1] = people[2];

moves[pos+2] = people[0];

moves[pos+3] = people[0];
moves[pos+4] = people[1];

timeSpent += people[2] + people[1] + people[0];
}
else {
moves[pos] = people[0];
moves[pos+1] = people[1];

timeSpent += people[1];
}

if(cases > 0 ) {
cout << endl;
}
cout << timeSpent << endl;

peopleLeft = n;
int i = 0;
while(peopleLeft > 2){
cout << moves << " " << moves[i+1] << endl << moves[i+2] << endl;
i +=3;
peopleLeft--;
}
cout << moves << " " << moves[i+1] << endl;
}
return 1;

}
[/cpp]

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
I think you should have special check for (n == 0) and (n ==1)
Where's the "Any" key?

logic
New poster
Posts: 1
Joined: Tue Feb 08, 2005 3:42 pm

The judge says Compilation error

#include<stdio.h>
int sum=0;
int a[1000];
void find(int i,int j)
{
if(i==j)
{
sum+=a[j];
//printf("%d %d",a[0],a[1]);
return;
}
sum+=2*a[j]+a[j+1];
sum+=a[i-1];
if(i+2<j)
find(i+2,j);
else
{
if(j-i==1)
sum+=a[j];
else
sum+=a[i+1]+a[j]+a[j+1];
}
}
void cal(int i,int j)
{
if(i==j)
{
printf("%d %d\n",a[j+1],a[j]);
return;
}
printf("%d %d\n",a[j+1],a[j]);
printf("%d\n",a[j+1]);
printf("%d %d\n",a,a[i-1]);
printf("%d\n",a[j]);
if(i+2<j)
find(i+2,j);
else
{
if(j-i==1)
{
printf("%d %d\n",a[j+1],a[j]);
}
else
{
printf("%d %d\n",a[i+1],a[j+1]);
printf("%d\n",a[j+1]);
printf("%d %d\n",a[j+1],a[j]);
}
}
}

int main()
{
int num,k=0;
scanf("%d",&num);
while(k<num)
{
int i,j,n;

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

for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(a<a[j])
{
int tmp=a[j];
a[j]=a;
a=tmp;
}
find(1,n-2);
printf("%d\n",sum);
cal(1,n-2);
k++;
}
return 0;
}

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
I'm using the algorithm that was described in the very beginning of this post and keep getting WA... Can anybody see what's wrong with my code or post some critical inputs?

Code: Select all

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){

int n, t, in;
cin >> t;
while(t-- && cin >> n){
vector < int > data, ans;
while(n-- && cin >> in) data.push_back(in);
sort(data.begin(), data.end());

int a = 0;
while(data.size() > 3){
if(data[0]*2 + data[data.size() - 1] + data[data.size() - 2] < data[0] + 2*data[1] + data[data.size() - 1])
a += data[0]*2 + data[data.size() - 1] + data[data.size() - 2],
ans.push_back(data[0]), ans.push_back(data[data.size() - 1]), ans.push_back(data[0]),
ans.push_back(data[0]), ans.push_back(data[data.size() - 2]), ans.push_back(data[0]);
else a += data[0] + 2*data[1] + data[data.size() - 1],
ans.push_back(data[0]), ans.push_back(data[1]), ans.push_back(data[0]);
ans.push_back(data[data.size() - 2]), ans.push_back(data[data.size() - 1]), ans.push_back(data[1]);
data.resize(data.size() - 2);
}

if(data.size() == 3){
cout << a + data[0] + data[1] + data[2] << endl;
for(int i = 0; i < (int)ans.size(); i += 3) cout << ans[i] << " " << ans[i + 1] << endl << ans[i + 2] << endl;
cout << data[0] << " " << data[2] << endl << data[0] << endl << data[0] << " " << data[1] << endl;
}

if(data.size() == 2){
cout << a + data[1] << endl;
for(int i = 0; i < (int)ans.size(); i += 3) cout << ans[i] << " " << ans[i + 1] << endl << ans[i + 2] << endl;
cout << data[0] << " " << data[1] << endl;
}

if(data.size() == 1){
cout << a + data[0] << endl;
for(int i = 0; i < (int)ans.size(); i += 3) cout << ans[i] << " " << ans[i + 1] << endl << ans[i + 2] << endl;
cout << data[0] << endl;
}

if(data.size() == 0) cout << 0 << endl;
if(t) cout << endl;
}

return 0;
}

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:
There is no Compile Error

I submit ur code and got WA

avoid posting code.....
ok
Amra korbo joy akhdin............................

snar
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

### 10037 Bridge & Indiana Jones Problem

Can anyone tell me what is Indiana Jones Problem and do it have any relation to this problem?
Thanks
Narek Saribekyan

rmpowell77
New poster
Posts: 5
Joined: Fri Aug 25, 2006 11:42 pm

### Possible reason for WA

I just tried something that might have lead to WA.

It appears that order may matter on the last 3 to cross. If the last three were 1, 2, 3, and if I printed:

1 2
1
1 3

I get WA. But if I change it to:

1 3
1
1 2

I get AC. Note, I am using the judge for the programmingchallenges.com.

animeshnayan
New poster
Posts: 5
Joined: Tue Mar 20, 2007 7:44 am
I think I am following the algorithm given at the start of this thread...getting WA ... I can't work out the test cases ... Somebody who has got AC help plzzz.

Code: Select all

Got Ac:))
Last edited by animeshnayan on Mon Apr 16, 2007 10:12 am, edited 1 time in total.
I am striving to write bug free codes (

sumantbhardvaj
New poster
Posts: 19
Joined: Sun Jun 18, 2006 4:07 pm
Contact:
well , as u would hv already seen in previous posts that there are two possible strategies...

if A,B,C....Z are time in ascending order ,

then Strategy one: AB+A+YZ+B
Strategy two: AZ+A+AY+A

So u r required to check for both and choose min out of them..