Page 4 of 6

Posted: Mon Apr 16, 2007 10:12 am
by animeshnayan
I got AC finally..

10037 - The Bridge (to Hell)

Posted: Wed May 30, 2007 3:13 am
by Schultz
Hello,

I found this problem very interesting at first, but when I tried to solve it, it became a nightmare.

The judge always either return WA or RE. The code below is WA.

Could anyone PLEASE a (the) bug in the code below. It is clear to understand.

Thanks in advance.

Code: Select all

/*	-------------
	ACM UVA 10037
	Schultz
	
	Bridge
	-------------
*/

/*	imports	*/
#include<stdio.h>

#include<vector>
#include<algorithm>
using namespace std;

/*	(int int) pair	*/
typedef		pair<int, int>		iipair;

/*	main	*/
int	main() {

	/*	treating test cases	*/
	int	tests;
	scanf("%d", &tests);
	while (tests > 0) { --tests;
		/*	reading people	*/
		static int	P[1024];
		int	n;
		scanf("%d", &n);
		for (int i = 0; i < n; i++) scanf("%d", &P[i]);
		
		/*	sorting people	*/
		sort(P, P+n);
		
		/*	trivial cases	*/
		if (n == 0)	puts("0");
		else if (n == 1) printf("%d\n%d\n", P[0], P[0]);
		else {
			/*	strategy calculation	*/
			vector<int>	back;
			vector<iipair>	fwd;
			int	a = P[0], b = P[1];
			int	time = 0;
			while (n > 3) {
				int	A = P[n-2], B = P[n-1];
				if (a + A < 2*b) {
					fwd.push_back(iipair(a, A));
					back.push_back(a);
					fwd.push_back(iipair(a, B));
					back.push_back(a);
					time+= 2*a + A + B;
				}
				else {
					fwd.push_back(iipair(a, b));
					back.push_back(a);
					fwd.push_back(iipair(A, B));
					back.push_back(b);
					time+= 2*b + a + B;
				}
				n-= 2;
			}
			if (n == 2) {
				fwd.push_back(iipair(a, b));
				time+= b;
			}
			else {
				fwd.push_back(iipair(a, P[2]));
				back.push_back(a);
				fwd.push_back(iipair(a, b));
				time+= a + b + P[2];
			}
			
			/*	output	*/
			printf("%d\n", time);
			int	fi = 0, bi = 0;
			while (fi < fwd.size() || bi < back.size()) {
				if (fi < fwd.size()) {
					iipair const& p = fwd[fi++];
					printf("%d %d\n", p.first, p.second);
				}
				if (bi < back.size()) {
					printf("%d\n", back[bi++]);
				}
			}
			
			/*	blank	*/
			if (tests > 0) putchar('\n');
		}
	}
		
	return	0;
}
To admins:
Ah, and please do not ask not to create a new thread. The forum should be open and when a thread is too heavy due to containing lots of pages of posting or when the subject differs much, a new one should be created. Also please do not lock this thread.

Posted: Thu Jul 19, 2007 10:25 am
by lucky16g
then Strategy one: AB+A+YZ+B
Strategy two: AZ+A+AY+A

i have try it
and got ac
the argrithm is right

Posted: Mon Sep 03, 2007 10:37 am
by H_Hima
help!!!!
I consider all of the above.

but my code got WA.

please tell me my wrong.

Code: Select all

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

int data[2000];
vector<int> out;

int fun(int n) {
	out.clear();
	int i,dif,sum=0;;
	bool sw=true;
	if(n==1) {
		out.push_back(data[0]);
		return data[0];
	}
	else {
		sort(data,data+n);
		dif=data[1]-data[0];
		for(i=1;i<n;i+=2) {
			if(sw&&(data[1]+dif-data[n-i-1])>=0)
				sw=false;
			if(sw) {
				out.push_back(data[0]);
				out.push_back(data[1]);
				sum+=data[1];
				if(n-i-1)	{
					out.push_back(data[0]);
					sum+=data[0]+data[n-i];
					if(n-i-2)	{
						out.push_back(data[n-i-1]);
						out.push_back(data[n-i]);
						out.push_back(data[1]);
						sum+=data[1];
					}
					else {
						out.push_back(data[0]);
						out.push_back(data[2]);
					}
				}
			}
			else {
				out.push_back(data[0]);
				out.push_back(data[n-i]);
				sum+=data[n-i];
				if(n-i-1)	{
					out.push_back(data[0]);
					out.push_back(data[0]);
					out.push_back(data[n-i-1]);
					sum+=data[0]+data[n-i-1];
					if(n-i-2)	{
						out.push_back(data[0]);
						sum+=data[0];
					}
				}
			}
		}
	}
	return sum;
}

void print(int sum) {
	int i;
	cout<<sum<<endl;
	for(i=0;i<out.size();i++) {
		cout<<out[i];
		i++;
		if(i<out.size()) {
			cout<<" "<<out[i]<<endl;
			i++;
			if(i<out.size())
				cout<<out[i]<<endl;
		}
	}
}

void main() {
	int t,i,j,n;
	cin>>t;
	while(t) {
		cin>>n;
		for(i=0;i<n;i++)
			cin>>data[i];
		print(fun(n));
		cout<<endl;
		t--;
	}
}

Re: 10037 - Bridge

Posted: Mon Jun 23, 2008 10:01 pm
by amr saqr
Help !!!! :D
5 WAs, 1 RE :D
Heeeeeeeeeeeeeelp !!! :cry:

Code: Select all

Removed After AC :D
Thanx in advance

Re: 10037 - Bridge

Posted: Mon Jun 23, 2008 10:29 pm
by mf
Here's a test where your program doesn't produce an optimal strategy:

Code: Select all

1

6
1 10 10 10 100 100
The best strategy here needs 153 seconds.
amr saqr wrote:5 WAs, 1 RE :D
So what? Keep on trying :)

Re: 10037 - Bridge

Posted: Mon Jun 23, 2008 11:29 pm
by amr saqr
Thanx sooooo much mf for the test case and for ur push also :),
I Got Accepted Finally :)

Re: 10037 - Bridge

Posted: Wed Nov 12, 2008 6:18 pm
by Wabi
Hi,
I cant find my mistake. When I test, It seems to work fine, however I get WA all the time. Cant find it... Thank you a lot in advance.

Code: Select all

import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * ACM - problém spousty lidí, mostu, který unese dv? osoby, a jedné baterky
 * @author J. Dan?k
 *
 */

class Main {
	static String retezec;
	static StringTokenizer vstup;
	
	final static int PRVNI = 0; //prvni prvek v poli - nejrychlejsi
	final static int DRUHY = 1; //druhy prvek
	
	
	/**
	 * Metoda pro ?tení z stdin
	 * @param maxLg maximalni delka nacteneho retezce
	 * @return precteny retezec
	 */
	private static String ReadLn (int maxLg) 
    {
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;

        try
        {
            while (lg < maxLg)
            {
                car = System.in.read();
                if ((car < 0) || (car == '\n')) break;
                lin [lg++] += car;
            }
        }
        catch (IOException e)	//v pripade chybneho vstupu neukonci program, ale vrati null
        {
            return (null);
        }

        if ((car < 0) && (lg == 0)) return (null);  // eof
        return (new String (lin, 0, lg));
    }
	
	/**
	 * Nacte pozadovany pocet vstupnich polozek
	 * @param pocet pocet nacitanych polozek
	 * @return pole prvku
	 */
	private static int[] inputData(int pocet){
		
		int[] pole = new int[pocet];
		for(int i = 0; i < pocet; i++){
			if((retezec = ReadLn(255)) != null){
				vstup = new StringTokenizer(retezec);
				pole[i] = Integer.parseInt(vstup.nextToken());
			}
		}
		return pole;
	}
	
	private static boolean podminka(int[] pole, int index){
		/*
		 * rychlost postupu 1: 2*nejrychlejsi + nejpomalejsi + druhy nejpomalejsi
		 * doba jednoho kroku postup 2: 2* druhy nejrychlejsi + nejpomalejsi + nejrychlejsi
		 * ? 1 > 2
		 * po uprave:
		 * nejrychlejsi + druhy nejpomalejsi > 2* druhy nejrychlejsi
		 * */
		if(pole[PRVNI] + pole[--index] < 2 * pole[DRUHY]){
			return true;
		}
		else{
			return false;
		}
	}
	
	private static int cas(int[] pole, int index){
		int t = 0;
		while(index > 2){
			if(podminka(pole,index) == false){
				t += 2*pole[DRUHY] + pole[PRVNI] + pole[index--];
				index--;
			}
			else {
				t += 2*pole[PRVNI] + pole[index] + pole[--index];
				index--;
			}
		}
		if(index == 2){
			for(int i = 0; i <= index; i++){
				t += pole[i];
			}
		}
		else if(index == 1){
			t += pole[DRUHY];
		}
		else{
			t += pole[PRVNI];
		}
		return t;
	}
	
	private static void vystup(int[] pole){
		int max = pole.length - 1;
		System.out.println("" + cas(pole,max));
		while(max > 2){
			if(podminka(pole,max) == true){
				System.out.print("" + pole[PRVNI] + " " + pole[max-1]);
				System.out.println("\n" + pole[PRVNI]);
				System.out.print("" + pole[PRVNI] + " " + pole[max]);
				max -= 2;
				if(max > 0){
					System.out.println("\n" + pole[PRVNI]);
				}
			}
			else{
				System.out.println("" + pole[PRVNI] + " " + pole[DRUHY]);
				System.out.println("" + pole[PRVNI]);
//				vypise a snizi max o jedna
				System.out.println("" + pole[max-1] + " " + pole[max]);
				max -= 2;
				System.out.println("" + pole[DRUHY]);
			}
		}
		if(max == 2){	
			System.out.println("" + pole[PRVNI] + " " + pole[max]);
			System.out.println("" + pole[PRVNI]);
			System.out.print("" + pole[PRVNI] + " " + pole[DRUHY]);
		}
		else if(max == 1){
			System.out.print("" + pole[PRVNI] + " " + pole[DRUHY]);
		}
		else{
			System.out.println("" + pole[PRVNI]);
		}
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Main myWork = new Main();
		myWork.Begin();
	}
	void Begin(){
		
		//System.out.print("Zadej pocet testovanych pripadu: ");
		int pripad; //pocet testovanych pripadu
		retezec = ReadLn(255);
		vstup = new StringTokenizer(retezec);
		pripad = Integer.parseInt(vstup.nextToken());
		ReadLn(255);		
		int[][] data = new int[pripad][];
		int[] prvky = new int[pripad]; //uchovava pocet prvku v jednotlivych pripadech
		for(int i = 0; i < pripad; i++){
			//System.out.print("Pocet prvku:");
			retezec = ReadLn(255);
			vstup = new StringTokenizer(retezec);
			prvky[i] = Integer.parseInt(vstup.nextToken());
			data[i] = new int[prvky[i]];
			data[i] = inputData(prvky[i]);	//nacteni hodnot jednoho testovaneho pripadu
			Arrays.sort(data[i]); 	//setridi vzestupne vsechny hodnoty
			if((pripad != 1) && (i != pripad -1)){	//odradkovani pozadovane v zadani mezi pripady
				ReadLn(255);	
			}
		}
		for(int i = 0; i < pripad; i++){
			vystup(data[i]);
			if(i < pripad - 1){
				System.out.println();
				System.out.println();
			}
		}
	}
}

Re: 10037 - Bridge

Posted: Fri Nov 21, 2008 11:35 am
by poixp
I think it's more convenient for many people to read program in English. It's just a good practice to name variables, functions in English. It's possible to make comment on another language when
1. code will never be read except of author
2. code will be read only by people who understand this language.
I was going to look at your code, but It's enciphered for me ...
Wabi wrote:Hi,
I cant find my mistake. When I test, It seems to work fine, however I get WA all the time. Cant find it... Thank you a lot in advance.

Code: Select all

import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * ACM - problém spousty lidí, mostu, který unese dv? osoby, a jedné baterky
 * @author J. Dan?k
 *
 */

class Main {
	static String retezec;
	static StringTokenizer vstup;
	
	final static int PRVNI = 0; //prvni prvek v poli - nejrychlejsi
	final static int DRUHY = 1; //druhy prvek
	
	
	/**
	 * Metoda pro ?tení z stdin
	 * @param maxLg maximalni delka nacteneho retezce
	 * @return precteny retezec
	 */
	private static String ReadLn (int maxLg) 
    {
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;

        try
        {
            while (lg < maxLg)
            {
                car = System.in.read();
                if ((car < 0) || (car == '\n')) break;
                lin [lg++] += car;
            }
        }
        catch (IOException e)	//v pripade chybneho vstupu neukonci program, ale vrati null
        {
            return (null);
        }

        if ((car < 0) && (lg == 0)) return (null);  // eof
        return (new String (lin, 0, lg));
    }
	
	/**
	 * Nacte pozadovany pocet vstupnich polozek
	 * @param pocet pocet nacitanych polozek
	 * @return pole prvku
	 */
	private static int[] inputData(int pocet){
		
		int[] pole = new int[pocet];
		for(int i = 0; i < pocet; i++){
			if((retezec = ReadLn(255)) != null){
				vstup = new StringTokenizer(retezec);
				pole[i] = Integer.parseInt(vstup.nextToken());
			}
		}
		return pole;
	}
	
	private static boolean podminka(int[] pole, int index){
		/*
		 * rychlost postupu 1: 2*nejrychlejsi + nejpomalejsi + druhy nejpomalejsi
		 * doba jednoho kroku postup 2: 2* druhy nejrychlejsi + nejpomalejsi + nejrychlejsi
		 * ? 1 > 2
		 * po uprave:
		 * nejrychlejsi + druhy nejpomalejsi > 2* druhy nejrychlejsi
		 * */
		if(pole[PRVNI] + pole[--index] < 2 * pole[DRUHY]){
			return true;
		}
		else{
			return false;
		}
	}
	
	private static int cas(int[] pole, int index){
		int t = 0;
		while(index > 2){
			if(podminka(pole,index) == false){
				t += 2*pole[DRUHY] + pole[PRVNI] + pole[index--];
				index--;
			}
			else {
				t += 2*pole[PRVNI] + pole[index] + pole[--index];
				index--;
			}
		}
		if(index == 2){
			for(int i = 0; i <= index; i++){
				t += pole[i];
			}
		}
		else if(index == 1){
			t += pole[DRUHY];
		}
		else{
			t += pole[PRVNI];
		}
		return t;
	}
	
	private static void vystup(int[] pole){
		int max = pole.length - 1;
		System.out.println("" + cas(pole,max));
		while(max > 2){
			if(podminka(pole,max) == true){
				System.out.print("" + pole[PRVNI] + " " + pole[max-1]);
				System.out.println("\n" + pole[PRVNI]);
				System.out.print("" + pole[PRVNI] + " " + pole[max]);
				max -= 2;
				if(max > 0){
					System.out.println("\n" + pole[PRVNI]);
				}
			}
			else{
				System.out.println("" + pole[PRVNI] + " " + pole[DRUHY]);
				System.out.println("" + pole[PRVNI]);
//				vypise a snizi max o jedna
				System.out.println("" + pole[max-1] + " " + pole[max]);
				max -= 2;
				System.out.println("" + pole[DRUHY]);
			}
		}
		if(max == 2){	
			System.out.println("" + pole[PRVNI] + " " + pole[max]);
			System.out.println("" + pole[PRVNI]);
			System.out.print("" + pole[PRVNI] + " " + pole[DRUHY]);
		}
		else if(max == 1){
			System.out.print("" + pole[PRVNI] + " " + pole[DRUHY]);
		}
		else{
			System.out.println("" + pole[PRVNI]);
		}
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Main myWork = new Main();
		myWork.Begin();
	}
	void Begin(){
		
		//System.out.print("Zadej pocet testovanych pripadu: ");
		int pripad; //pocet testovanych pripadu
		retezec = ReadLn(255);
		vstup = new StringTokenizer(retezec);
		pripad = Integer.parseInt(vstup.nextToken());
		ReadLn(255);		
		int[][] data = new int[pripad][];
		int[] prvky = new int[pripad]; //uchovava pocet prvku v jednotlivych pripadech
		for(int i = 0; i < pripad; i++){
			//System.out.print("Pocet prvku:");
			retezec = ReadLn(255);
			vstup = new StringTokenizer(retezec);
			prvky[i] = Integer.parseInt(vstup.nextToken());
			data[i] = new int[prvky[i]];
			data[i] = inputData(prvky[i]);	//nacteni hodnot jednoho testovaneho pripadu
			Arrays.sort(data[i]); 	//setridi vzestupne vsechny hodnoty
			if((pripad != 1) && (i != pripad -1)){	//odradkovani pozadovane v zadani mezi pripady
				ReadLn(255);	
			}
		}
		for(int i = 0; i < pripad; i++){
			vystup(data[i]);
			if(i < pripad - 1){
				System.out.println();
				System.out.println();
			}
		}
	}
}

Re: 10037 - Bridge

Posted: Tue May 19, 2009 8:32 pm
by Slava_Edelev
Hi! Can't find a bug... I used the correct algorithm, described here, I have a special output for 0,1,2,3 people and in addition I've compared my output with the correct output for many times with random values but it didn't help me - outputs are the same...)

Please, point the cases my program works incorrectly or find a bug))

THANK YOU!

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int compare(const unsigned int *a, const unsigned int *b)
{
return (int) (*a - *b);
}
void Vivod (int * mas, int n)
{
    int i;
    for (i=0;i<n;i++) printf ("%i\n",mas[i]);
}

int S1(int *mas,int j)
{
    int S;
    S=mas[j]+mas[j-1]+2*mas[0];
    return S;
}

int S2(int *mas,int j)
{
    int S;
    S=mas[j]+mas[0]+2*mas[1];
    return S;
}

int main(void)
{
    unsigned int i,j,k,n,t,z,a[1001];
    unsigned long long int S;


scanf("%i",&n);
    for (i=0;i<n;i++)
    {


        scanf("%i",&k); z=k;
        if (k==0) {printf("0\n\n"); continue;}
        S=0;
        for (j=0;j<k;j++) scanf("%i",&a[j]);

        qsort(a,k,sizeof(int),compare);

            for (j=k-1;j>2;j-=2)
            {
                if (S1(a,j)<S2(a,j))
                    S+=S1(a,j);
                else
                   S+=S2(a,j);

            }
            if (j<3) k=j+1;
            if (k==1) S=a[0];
            if (k==2) S+=a[1];
            if (k==3) S+=a[0]+a[1]+a[2];

        printf("%i\n",S);
k=z;
         for (j=k-1;j>2;j-=2)
            {
                if (S1(a,j)<S2(a,j))
                    printf("%i %i\n%i\n%i %i\n%i\n",a[0],a[j-1],a[0],a[0],a[j],a[0]);
                else
                    printf("%i %i\n%i\n%i %i\n%i\n",a[0],a[1],a[0],a[j-1],a[j],a[1]);

            }
            if (j<3) k=j+1;
            if (k==1) printf("%i",a[0]);
            if (k==2) printf("%i %i",a[0],a[1]);
            if (k==3) printf("%i %i\n%i\n%i %i",a[0],a[1],a[0],a[0],a[2]);


        if (i+1<n)
        printf("\n\n");
    }

    return 0;
}
and my code with files and random input))

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int compare(const unsigned int *a, const unsigned int *b)
{
return (int) (*a - *b);
}
void Vivod (int * mas, int n)
{
    int i;
    for (i=0;i<n;i++) printf ("%i\n",mas[i]);
}

int S1(int *mas,int j)
{
    int S;
    S=mas[j]+mas[j-1]+2*mas[0];
    return S;
}

int S2(int *mas,int j)
{
    int S;
    S=mas[j]+mas[0]+2*mas[1];
    return S;
}

int main(void)
{
    unsigned int i,j,k,n,t,z,a[1001];
    unsigned long long int S;

FILE *fin,*fout;
//fin=fopen("in.txt","w");
fout=fopen("out.txt","w");
/*
srand(1510);
fprintf(fin,"%i\n\n",1+(int) (1000.0*rand()/(RAND_MAX+1.0)));
fclose(fin);
fin=fopen("in.txt","r");
fscanf(fin,"%i",&n);
fclose(fin);
fin=fopen("in.txt","a+");


for (i=0;i<n;i++)
{

    j=0+(int) (1000.0*rand()/(RAND_MAX+1.0));

fprintf(fin,"%i\n",j);

    for (t=0;t<j;t++)    fprintf (fin,"%i\n",0+(int) (100.0*rand()/(RAND_MAX+1.0)));
    fprintf(fin,"\n");
}
fclose(fin);
*/

fin=fopen("in.txt","r");
fscanf(fin,"%i",&n);
    for (i=0;i<n;i++)
    {


        fscanf(fin,"%i",&k); z=k;
        if (k==0) {fprintf(fout,"0\n\n"); continue;}
        S=0;
        for (j=0;j<k;j++) fscanf(fin,"%i",&a[j]);

        qsort(a,k,sizeof(int),compare);

            for (j=k-1;j>2;j-=2)
            {
                if (S1(a,j)<S2(a,j))
                    S+=S1(a,j);
                else
                   S+=S2(a,j);

            }
            if (j<3) k=j+1;
            if (k==1) S=a[0];
            if (k==2) S+=a[1];
            if (k==3) S+=a[0]+a[1]+a[2];

        fprintf(fout,"%i\n",S);
k=z;
         for (j=k-1;j>2;j-=2)
            {
                if (S1(a,j)<S2(a,j))
                    fprintf(fout,"%i %i\n%i\n%i %i\n%i\n",a[0],a[j-1],a[0],a[0],a[j],a[0]);
                else
                    fprintf(fout,"%i %i\n%i\n%i %i\n%i\n",a[0],a[1],a[0],a[j-1],a[j],a[1]);

            }
            if (j<3) k=j+1;
            if (k==1) fprintf(fout,"%i",a[0]);
            if (k==2) fprintf(fout,"%i %i",a[0],a[1]);
            if (k==3) fprintf(fout,"%i %i\n%i\n%i %i",a[0],a[1],a[0],a[0],a[2]);


        if (i+1<n)
        fprintf(fout,"\n\n");
    }
    fclose (fin);fclose(fout);
    return 0;
}


Re: 10037 - Bridge

Posted: Sat Sep 19, 2009 4:11 am
by blittman
Here is some test data with correct output for those in need (strategies may vary). Don't forget about cases with 1, 2, or 3 people :)

Input:

Code: Select all

5

6
1
5
10
10
100
100

6
1
10
10
10
100
100

6
4
2
3
3
5
10

6
2
20
22
24
26
28

6
20
15
10
5
2
1
Output:

Code: Select all

137
1 5
1
100 100
5
1 5
1
10 10
5
1 5

153
1 10
1
100 100
10
1 10
1
1 10
1
1 10

32
2 3
2
5 10
3
2 4
2
2 3
2
2 3

128
2 28
2
2 26
2
2 24
2
2 22
2
2 20

42
1 2
1
15 20
2
1 2
1
5 10
2
1 2

Re: 10037 - Bridge

Posted: Wed Jul 28, 2010 5:48 pm
by valkov
My code pass correctly all cases posted here but still I get WA.
Please take a look at it:

Code: Select all

#include <fcntl.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
using namespace std;

vector<int> p;

// tc - test cases count
unsigned tc = 0;

void ReadInput() {
    unsigned n;
    cin >> n;
    unsigned t;
    for(unsigned i = 0; i < n; i++) {
        cin >> t;
        p.push_back(t);
    }
}

unsigned FastestBack() {
    stack<int> people;
    int moves = 0;
    int fastest = p[0];
    for(unsigned i = 1; i < p.size(); i++) {
        people.push(p[i]);
    }
    while(!people.empty()) {
        moves += people.top();
        people.pop();
        moves += fastest;
    }
    moves -= fastest;
    return moves;
}

void PrintFastestBack() {
    stack<int> people;
    int fastest = p[0];
    for(unsigned i = 1; i < p.size(); i++) {
        people.push(p[i]);
    }
    while(!people.empty()) {
        cout << fastest << " " << people.top() << endl;
        people.pop();
        if(!people.empty()) {
            cout << fastest << endl;
        }
    }
}

unsigned TwoFastBack() {
    int moves = 0;
    int f1 = p[0];
    int f2 = p[1];
    int endAt = 2;
    while(true) {
        if(p[endAt] != f2) {
            break;
        }
        moves += f1 + f2;
        endAt++;
    }
    if(endAt % 2 != 0) {
        moves += f1 + p[endAt];
        endAt++;
    }
    for(int i = p.size() - 1; i > endAt; i -= 2) {
        moves += f1 + f2;
        moves += p[i] + f2;
    }
    moves += f2;
    return moves;
}

void PrintTwoFastBack() {
    int f1 = p[0];
    int f2 = p[1];

    int endAt = 2;
    while(true) {
        if(p[endAt] != f2) {
            break;
        }
        cout << f1 << " " << f2 << endl;
        cout << f1 << endl;
        endAt++;
    }
    if(endAt % 2 != 0) {
        cout << f1 << " " << p[endAt] << endl;
        cout << f1 << endl;
    }

    for(int i = p.size() - 1; i > endAt; i -= 2) {
        cout << f1 << " " << f2 << endl;
        cout << f1 << endl;

        cout << p[i - 1] << " " << p[i] << endl;
        cout << f2 << endl;
    }
    cout << f1 << " " << f2 << endl;
}

void Compute() {
    if(p.empty()) {
        return;
    }
    sort(p.begin(), p.end());
    if(p.size() == 1) {
        cout << p[0] << endl;
        cout << p[0] << endl;
    } else if(p.size() == 2) {
        cout << p[1] << endl;
        cout << p[0] << " " << p[1] << endl;
    } else if(p.size() == 3) {
        // all of them summed together
        cout << p[0] + p[1] + p[2] << endl;
        // strategy
        cout << p[0] << " " << p[1] << endl;
        cout << p[0] << endl;
        cout << p[0] << " " << p[2] << endl;
    } else {
        unsigned fastestBack = FastestBack();
        unsigned twoFastBack = TwoFastBack();
        if(fastestBack < twoFastBack) {
            cout << fastestBack << endl;
            PrintFastestBack();
        } else {
            cout << twoFastBack << endl;
            PrintTwoFastBack();
        }
    }
}

int main()
{

//    #define ONLINE_JUDGE
    #ifndef ONLINE_JUDGE
      close (0); open ("in.txt", O_RDONLY);
      close (1); open ("out.txt", O_WRONLY | O_CREAT, 0600);
    #endif

    cin >> tc;
    for(unsigned i = 0; i < tc; i++) {
        if(i > 0)
            cout << endl;
        ReadInput();
        Compute();
        p.clear();
    }

    return 0;
}


Re: 10037 - Bridge

Posted: Sun Apr 03, 2011 12:49 am
by leonardoferrari
Keep geeting WA, but every test has worked properly.

Any help would be appreciated !

Code: Select all

done, silly mistake...
BTW, i tried to take the cout << endl; out after the cin >> casos, but no luck :(

Thanks guys !

Re: 10037 - Bridge

Posted: Mon Apr 04, 2011 1:51 am
by nexodg
Any tip? I use http://uvatoolkit.com/problemssolve.php to generate solution, and my own generated large case of test. Compare = Files Match. Should I focus on out format, is so much important?

Re: 10037 - Bridge

Posted: Thu May 19, 2011 6:22 pm
by Leo66
Why W.A? My program is correct :(

All test data is correct

Code: Select all

AC