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

jhuliagraziella
New poster
Posts: 4
Joined: Mon Jun 10, 2013 10:04 pm

Re: 10037 - Bridge

Post by jhuliagraziella » Mon Jul 22, 2013 6:20 pm

Hey guys, could someone help me?? I have no idea of what's wrong with my code and I keep getting WA! :(
I've tried all the inputs in this forum and all of them were ok... If anyone could send me some critical input/output that would really help! ty

Here's my code:

Code: Select all

removed after AC
Last edited by jhuliagraziella on Wed Jul 24, 2013 6:13 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10037 - Bridge

Post by brianfry713 » Tue Jul 23, 2013 2:20 am

Check n = 2.
Check input and AC output for thousands of problems on uDebug!

jhuliagraziella
New poster
Posts: 4
Joined: Mon Jun 10, 2013 10:04 pm

Re: 10037 - Bridge

Post by jhuliagraziella » Wed Jul 24, 2013 6:12 pm

Got it! :T
Tks a lot (again) brianfry! =D

cmpsamurai
New poster
Posts: 1
Joined: Wed Oct 16, 2013 6:32 pm

Re: 10037 - Bridge

Post by cmpsamurai » Wed Oct 16, 2013 6:42 pm

I dont know if anyone will check this post or not , i have just signed up, because this problem is getting me all crazy :(, i have passed all the test cases discussed her on this forum and still WA , can anyone please help me :(

Code: Select all

/*************************************************************************
 * Copyright (C) 2008 by Moustafa Mahmoud (cmpsamurai)                   *
 * moustafa@cmpsamurai.com                                               *
 *************************************************************************/
/*C++ "10037 - Bridge" */

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <iterator>
#include <sstream>

using namespace std;

void cross(deque<int> runners)
{
    deque<int> first,second;
    first=runners;
    int time=0;
    stringstream output;
    
    int temp=-1,last1,last2;
    
    while(second.size()<runners.size())
    {
        sort(first.begin(),first.end());
        sort(second.begin(),second.end());
        
        if(first.size()==1)
        {
            output<<first.front()<<endl;
            time+=first.front();
            second.push_front(first.front());
            first.pop_front();
        }
        else if(first.size()==2)
        {
            output<<first[0]<<" "<<first[1]<<endl;
            time+=first[1];
            second.push_back(first.front());
            first.pop_front();
            second.push_back(first.front());
            first.pop_front();
        }
        else if(first.size()==3)
        {
            output<<first[0]<<" "<<first[2]<<endl;
            time+=first[2];
            second.push_back(first[0]);
            second.push_front(first[2]);
            first.pop_front();
            first.pop_back();
            sort(second.begin(),second.end());
            output<<second[0]<<endl;
            time+=second[0];
            output<<second[0]<<" "<<first[0]<<endl;
            time+=first[0];
            second.push_back(first[0]);
            
        }
        else 
        {
            bool test1=(first[1]+first[0]+first[first.size()-2]+first[1])<(first[0]+first[0]+first[first.size()-1]+first[first.size()-2]);
           if(test1)
           {
                //first 2
                output<<first[0]<<" "<<first[1]<<endl;
                time+=first[1];
                second.push_back(first[0]);
                second.push_back(first[1]);
                first.pop_front();
                first.pop_front();
                sort(second.begin(),second.end());
                first.push_front(second[0]);
                output<<second[0]<<endl;
                time+=second[0];
                second.pop_front();
                
                //last 2
                output<<first[first.size()-2]<<" "<<first[first.size()-1]<<endl;
                time+=first[first.size()-1];
                second.push_back(first[first.size()-2]);
                second.push_back(first[first.size()-1]);
                first.pop_back();
                first.pop_back();
                
                first.push_front(second.front());
                time+=first.front();
                output<<first.front()<<endl;
                second.pop_front();
           }
           
           else
           {
                //first 2
                output<<first[0]<<" "<<first[first.size()-1]<<endl;
                time+=first[first.size()-1];
                second.push_back(first[0]);
                second.push_back(first[first.size()-1]);
                first.pop_front();
                first.pop_back();
                sort(second.begin(),second.end());
                first.push_front(second[0]);
                output<<second[0]<<endl;
                time+=second[0];
                second.pop_front();
                
                
                //last 2
                output<<first[0]<<" "<<first[first.size()-1]<<endl;
                time+=first[first.size()-1];
                second.push_back(first[0]);
                second.push_back(first[first.size()-1]);
                first.pop_back();
                first.pop_front();
                sort(second.begin(),second.end());
                first.push_front(second.front());
                time+=first.front();
                output<<first.front()<<endl;
                second.pop_front();
           }
            
        }
    }
    
    cout<<time<<endl;
    cout<<output.str();
}

int main() {
    
    int num_cases,n,temp;
    string line;
    cin>>num_cases;
    getline(cin,line);
    
    for(int i=0;i<num_cases;i++)
    {
       getline(cin,line);
       cin>>n;
       cin.ignore();
       deque<int> speeds;
       
       for(int j=0;j<n;j++)
       {
           cin>>temp;
           cin.ignore();
           speeds.push_back(temp);
       }
       cross(speeds);
       
       if(i<num_cases-1)
       {
           cout<<endl;
       }
    }
    return 0;
    
}

and this is the ideone link to the code
http://ideone.com/ST8lEr

thanks alot in advance

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10037 - Bridge

Post by brianfry713 » Wed Oct 16, 2013 9:12 pm

Input:

Code: Select all

1

40
35
56
72
18
26
63
26
47
18
81
69
60
84
90
90
74
33
40
45
4
36
10
38
61
84
6
41
100
57
100
91
43
7
62
60
32
76
37
30
46
AC output:

Code: Select all

1349
4 6
4
100 100
6
4 6
4
90 91
6
4 6
4
84 90
6
4 6
4
81 84
6
4 6
4
74 76
6
4 6
4
69 72
6
4 6
4
62 63
6
4 6
4
60 61
6
4 6
4
57 60
6
4 6
4
47 56
6
4 6
4
45 46
6
4 6
4
41 43
6
4 6
4
38 40
6
4 6
4
36 37
6
4 6
4
33 35
6
4 6
4
30 32
6
4 6
4
26 26
6
4 6
4
18 18
6
4 10
4
4 7
4
4 6
Check input and AC output for thousands of problems on uDebug!

ngdik
New poster
Posts: 4
Joined: Mon Jun 23, 2014 1:27 pm

10037 Bridge

Post by ngdik » Tue Jul 01, 2014 8:22 am

hi,
I tried the test case and it was right,but i can not get the Ac,who can help me,pls

Code: Select all

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void check();
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		check();
	}
	
	system("pause");
	
}

void check()
{
	int num;
	
	int tmp;
	vector<int> people;

	string text;

	int count = 0;
	ostringstream os;

	cin >> num;

	for (int i = 0; i < num;i++)
	{
		cin >> tmp;
		people.push_back(tmp);
	}

	int smallest, secondSmallest;


	sort(people.begin(), people.end());
	

	if (num == 1)
	{
		os << people[0] << endl;
		text = os.str();
		count = people[0];
		cout << count << endl << text;
		return;
	}
	else if (num == 2)
	{
		count = people[1];

		os << people[0] << " " << people[1] << endl;
		text = os.str();
		cout << count << endl << text;
		return;
	}
	else if (num == 3)
	{
		count = people[0] + people[1] + people[2];
		os << people[0] << " " << people[2] << endl;
		os << people[0] << endl;
		os << people[0] << " " << people[1] << endl;
		text = os.str();
		cout << count << endl << text;
		return;
	}


	smallest = people[0];
	secondSmallest = people[1];

	if (num %2 ==1)
	{
		for (int i = num - 1; i != 2; i -= 2)
		{
			os << smallest << " " << secondSmallest << endl;
			count = count + secondSmallest;
			os << smallest << endl;
			count = count + smallest;
			os << people[i-1] << " " << people[i ] << endl;
			count = count + people[i];
			os << secondSmallest << endl;
			count = count + secondSmallest;

		}
		count += people[0] + people[1] + people[2];
		os << people[0] << " " << people[2] << endl;
		os << people[0] << endl;
		os << people[0] << " " << people[1] << endl;
		text = os.str();
		cout << count << endl << text;


	}
	else
	{
		for (int i = num - 1; i != 1; i -= 2)
		{
			os << smallest << " " << secondSmallest << endl;
			count = count + secondSmallest;
			os << smallest << endl;
			count = count + smallest;
			os << people[i-1] << " " << people[i  ] << endl;
			count = count + people[i];
			os << secondSmallest << endl;
			count = count + secondSmallest;

		}
		count += people[1];

		os << people[0] << " " << people[1] << endl;
		text = os.str();
		cout << count << endl << text;
		
	}
	
}

ngdik
New poster
Posts: 4
Joined: Mon Jun 23, 2014 1:27 pm

Re: 10037 Bridge

Post by ngdik » Tue Jul 01, 2014 9:03 am

i fix the(A+2*B+Y+Z) > (A*2+Y+Z),
but i can not get the ac

Code: Select all

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void check();
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		check();
	}


	
}

void check()
{
	int num;
	
	int tmp;
	vector<int> people;

	string text;

	int count = 0;
	ostringstream os;

	cin >> num;

	for (int i = 0; i < num;i++)
	{
		cin >> tmp;
		people.push_back(tmp);
	}

	int smallest, secondSmallest;


	sort(people.begin(), people.end());
	

	if (num == 1)
	{
		os << people[0] << endl;
		text = os.str();
		count = people[0];
		cout << count << endl << text;
		return;
	}
	else if (num == 2)
	{
		count = people[1];

		os << people[0] << " " << people[1] << endl;
		text = os.str();
		cout << count << endl << text;
		return;
	}
	else if (num == 3)
	{
		count = people[0] + people[1] + people[2];
		os << people[0] << " " << people[2] << endl;
		os << people[0] << endl;
		os << people[0] << " " << people[1] << endl;
		text = os.str();
		cout << count << endl << text;
		return;
	}


	smallest = people[0];
	secondSmallest = people[1];

	if (num %2 ==1)
	{
		for (int i = num - 1; i != 2; i -= 2)
		{
			if (smallest + 2 * secondSmallest + people[i] < 2 * smallest + people[i] + people[i - 1])
			{
				os << smallest << " " << secondSmallest << endl;
				count = count + secondSmallest;
				os << smallest << endl;
				count = count + smallest;
				os << people[i - 1] << " " << people[i] << endl;
				count = count + people[i];
				os << secondSmallest << endl;
				count = count + secondSmallest;
			}
			else
			{
				os << smallest << " " << people[i] << endl;
				count = count + people[i];
				os << smallest << endl;
				count = count + smallest;
				os << smallest << " " << people[i - 1] << endl;
				count = count + people[i - 1];
				os << smallest << endl;
				count = count + smallest;
			}

		}
		count += people[0] + people[1] + people[2];
		os << people[0] << " " << people[2] << endl;
		os << people[0] << endl;
		os << people[0] << " " << people[1] << endl;
		text = os.str();
		cout << count << endl << text;


	}
	else
	{
		for (int i = num - 1; i != 1; i -= 2)
		{
			if (smallest + 2 * secondSmallest + people[i] < 2 * smallest + people[i] + people[i - 1])
			{
				os << smallest << " " << secondSmallest << endl;
				count = count + secondSmallest;
				os << smallest << endl;
				count = count + smallest;
				os << people[i - 1] << " " << people[i] << endl;
				count = count + people[i];
				os << secondSmallest << endl;
				count = count + secondSmallest;
			}
			else
			{
				os << smallest << " " << people[i] << endl;
				count = count + people[i];
				os << smallest << endl;
				count = count + smallest;
				os << smallest << " " << people[i - 1] << endl;
				count = count + people[i - 1];
				os << smallest << endl;
				count = count + smallest;
			}

		}
		count += people[1];

		os << people[0] << " " << people[1] << endl;
		text = os.str();
		cout << count << endl << text;
		
	}
	
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10037 Bridge

Post by brianfry713 » Tue Jul 08, 2014 1:09 am

The outputs of two consecutive cases will be separated by a blank line.
Check input and AC output for thousands of problems on uDebug!

fresher96
New poster
Posts: 25
Joined: Wed Sep 03, 2014 8:50 am

Re: 10037 - Bridge

Post by fresher96 » Tue Oct 07, 2014 1:27 am

hey guys !
any one who got this problem accepted in "programmingchallenges.com"
can share any tips ??
or post the AC output for

Code: Select all

2

8
1
2
3
4
5
6
7
8

7
1
2
3
4
5
6
7
or know how the order of the output should be

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10037 - Bridge

Post by lighted » Tue Oct 07, 2014 9:59 am

Check your input here. http://www.udebug.com/UVa/10037
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 100 (10000-10099)”