OJ Board

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

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

Code: Select all

Removed After AC :D

Code: Select all

1

6
1 10 10 10 100 100

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

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

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

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

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

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

Code: Select all

done, silly mistake...

Code: Select all

AC