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

animeshnayan
New poster
Posts: 5
Joined: Tue Mar 20, 2007 7:44 am

Post by animeshnayan » Mon Apr 16, 2007 10:12 am

I got AC finally..
I am striving to write bug free codes :((

Schultz
New poster
Posts: 13
Joined: Wed May 16, 2007 12:39 am

10037 - The Bridge (to Hell)

Post by Schultz » Wed May 30, 2007 3:13 am

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.

lucky16g
New poster
Posts: 8
Joined: Sun Jul 01, 2007 7:25 pm

Post by lucky16g » Thu Jul 19, 2007 10:25 am

then Strategy one: AB+A+YZ+B
Strategy two: AZ+A+AY+A

i have try it
and got ac
the argrithm is right

H_Hima
New poster
Posts: 18
Joined: Mon Sep 25, 2006 10:56 am
Location: Solar System
Contact:

Post by H_Hima » Mon Sep 03, 2007 10:37 am

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

amr saqr
New poster
Posts: 29
Joined: Tue Mar 11, 2008 6:35 pm

Re: 10037 - Bridge

Post by amr saqr » Mon Jun 23, 2008 10:01 pm

Help !!!! :D
5 WAs, 1 RE :D
Heeeeeeeeeeeeeelp !!! :cry:

Code: Select all

Removed After AC :D
Thanx in advance
Last edited by amr saqr on Wed Jul 02, 2008 11:57 pm, edited 1 time in total.
C++ Is The Best.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10037 - Bridge

Post by mf » Mon Jun 23, 2008 10:29 pm

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

amr saqr
New poster
Posts: 29
Joined: Tue Mar 11, 2008 6:35 pm

Re: 10037 - Bridge

Post by amr saqr » Mon Jun 23, 2008 11:29 pm

Thanx sooooo much mf for the test case and for ur push also :),
I Got Accepted Finally :)
C++ Is The Best.

Wabi
New poster
Posts: 1
Joined: Wed Nov 12, 2008 5:59 pm

Re: 10037 - Bridge

Post by Wabi » Wed Nov 12, 2008 6:18 pm

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();
			}
		}
	}
}

poixp
New poster
Posts: 20
Joined: Mon Apr 07, 2008 11:05 am

Re: 10037 - Bridge

Post by poixp » Fri Nov 21, 2008 11:35 am

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();
			}
		}
	}
}

Slava_Edelev
New poster
Posts: 4
Joined: Fri May 15, 2009 2:36 pm

Re: 10037 - Bridge

Post by Slava_Edelev » Tue May 19, 2009 8:32 pm

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


blittman
New poster
Posts: 2
Joined: Mon Aug 31, 2009 1:13 am

Re: 10037 - Bridge

Post by blittman » Sat Sep 19, 2009 4:11 am

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

valkov
New poster
Posts: 20
Joined: Tue Jul 20, 2010 3:11 pm

Re: 10037 - Bridge

Post by valkov » Wed Jul 28, 2010 5:48 pm

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


leonardoferrari
New poster
Posts: 5
Joined: Mon Mar 14, 2011 4:59 am

Re: 10037 - Bridge

Post by leonardoferrari » Sun Apr 03, 2011 12:49 am

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 !
Last edited by leonardoferrari on Sun Apr 03, 2011 8:10 pm, edited 1 time in total.

nexodg
New poster
Posts: 2
Joined: Mon Apr 04, 2011 1:43 am

Re: 10037 - Bridge

Post by nexodg » Mon Apr 04, 2011 1:51 am

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?

Leo66
New poster
Posts: 2
Joined: Sun May 01, 2011 5:11 pm

Re: 10037 - Bridge

Post by Leo66 » Thu May 19, 2011 6:22 pm

Why W.A? My program is correct :(

All test data is correct

Code: Select all

AC

Post Reply

Return to “Volume 100 (10000-10099)”