10037 - Bridge

[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]

[gvcormac]

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.

[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.

[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?

[BiK]

Can somebody post some test input data?

[reiners]

Test input data, with matching correct output data, would be especially nice.

[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]

[Solaris]

I think you should have special check for (n == 0) and (n ==1)

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

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

[mohsincsedu]

Check your code....
There is no Compile Error

I submit ur code and got WA



avoid posting code.....
ok

[snar]

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

[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.

[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:))

[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..