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

Post by reiners » Sun Oct 12, 2003 2:16 am

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
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Post by gvcormac » Mon Oct 13, 2003 1:30 am

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.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Oct 13, 2003 9:54 am

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

Post by BiK » Fri Oct 24, 2003 12:30 am

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

Post by BiK » Fri Oct 24, 2003 6:48 pm

Can somebody post some test input data?

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

Post by reiners » Fri Oct 24, 2003 11:06 pm

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

Post by jcosta » Sat Apr 24, 2004 8:28 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Sun Aug 29, 2004 9:20 pm

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

10037:Please Help me,Please look at my code

Post by logic » Wed Feb 09, 2005 8:13 am

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

Post by minskcity » Fri Aug 19, 2005 12:26 am

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:

Post by mohsincsedu » Sat Sep 02, 2006 5:58 am

Check your code....
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

Post by snar » Tue Jan 23, 2007 9:19 pm

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

Post by rmpowell77 » Tue Mar 13, 2007 7:54 am

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

Post by animeshnayan » Tue Mar 20, 2007 7:57 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:

Post by sumantbhardvaj » Tue Mar 20, 2007 4:05 pm

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

Post Reply

Return to “Volume 100 (10000-10099)”