Page 3 of 6

10037: Bridge

Posted: Sun Oct 12, 2003 2:16 am
by reiners
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;
}
}

return totalTime;
}

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]

Posted: Mon Oct 13, 2003 1:30 am
by gvcormac
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.

Posted: Mon Oct 13, 2003 9:54 am
by Adrian Kuegel
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.

Posted: Fri Oct 24, 2003 12:30 am
by BiK
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?

Posted: Fri Oct 24, 2003 6:48 pm
by BiK
Can somebody post some test input data?

Posted: Fri Oct 24, 2003 11:06 pm
by reiners
Test input data, with matching correct output data, would be especially nice.

10037 : Bridge

Posted: Sat Apr 24, 2004 8:28 pm
by jcosta
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]

Posted: Sun Aug 29, 2004 9:20 pm
by Solaris
I think you should have special check for (n == 0) and (n ==1)

10037:Please Help me,Please look at my code

Posted: Wed Feb 09, 2005 8:13 am
by logic
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;
}

Posted: Fri Aug 19, 2005 12:26 am
by minskcity
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;
}

Posted: Sat Sep 02, 2006 5:58 am
by mohsincsedu
Check your code....
There is no Compile Error

I submit ur code and got WA



avoid posting code.....
ok

10037 Bridge & Indiana Jones Problem

Posted: Tue Jan 23, 2007 9:19 pm
by snar
Can anyone tell me what is Indiana Jones Problem and do it have any relation to this problem?
Thanks

Possible reason for WA

Posted: Tue Mar 13, 2007 7:54 am
by rmpowell77
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.

Posted: Tue Mar 20, 2007 7:57 am
by animeshnayan
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:))

Posted: Tue Mar 20, 2007 4:05 pm
by sumantbhardvaj
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..