Page 5 of 6
Re: 10037 - Bridge
Posted: Sun Sep 23, 2012 9:06 am
by mop123
Do you guys have any additional thoughts about this judge? My program works for all test cases in this thread but I still get WA.
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)
line = in.readLine();
Please help.
Re: 10037 - Bridge
Posted: Tue Sep 25, 2012 1:38 am
by brianfry713
Read an integer at a time instead of line by line.
Re: 10037 - Bridge
Posted: Sun Oct 07, 2012 7:42 pm
by 37squared
Getting wrong answer...dunno y
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;
}
}
void add()
{
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)
{
add();
print();
}
empty();
printf("\n");
}
return 0;
}
Re: 10037 - Bridge
Posted: Sun Oct 07, 2012 8:17 pm
by brianfry713
The outputs of two consecutive cases will be separated by a blank line. Correct output:
Your output:
Re: 10037 - Bridge
Posted: Tue Oct 16, 2012 10:34 pm
by 37squared
brianfry713 wrote:The outputs of two consecutive cases will be separated by a blank line. Correct output:
Your output:
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;
}
}
void add()
{
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)
{
add();
print();
}
empty();
if(m<tc)
printf("\n");
}
return 0;
}
Re: 10037 - Bridge
Posted: Wed Oct 17, 2012 11:52 pm
by brianfry713
Try a case where n=1.
Re: 10037 - Bridge
Posted: Thu Oct 18, 2012 1:57 am
by 37squared
Thx a lot brianfry... i had been struggling for months to get it submitted...
Re: 10037 - Bridge
Posted: Mon Oct 29, 2012 10:09 am
by ajeet.singh82
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..
Re: 10037 - Bridge
Posted: Mon Mar 25, 2013 1:25 am
by laberle
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;
}
Re: 10037 - Bridge
Posted: Wed Mar 27, 2013 12:17 am
by brianfry713
Try reading an integer at a time instead of line by line.
Re: 10037 - Bridge
Posted: Sat Mar 30, 2013 6:09 am
by laberle
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;
}
Re: 10037 - Bridge
Posted: Fri Apr 05, 2013 12:23 am
by brianfry713
Input:
AC output:
Don't print a space at the end of a line.
Re: 10037 - Bridge
Posted: Fri Apr 05, 2013 10:07 pm
by laberle
brianfry713 wrote:Input:
AC output:
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.
Re: 10037 - Bridge
Posted: Wed Apr 10, 2013 12:10 am
by brianfry713
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.
Re: 10037 - Bridge
Posted: Fri Apr 12, 2013 7:18 pm
by laberle
Got it. Thanks for that last test case!