10720 - Graph Construction

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Post by mf » Mon Jul 23, 2007 5:47 am

Can someone show me a graph for the case below?

10 3 3 3 3 3 3 3 3 3 3
(the first number is the number of vertices)
This graph realizes it, for example:

Code: Select all

    *---*---*
   / \  |  / \
  *---* | *---*
   \ /  |  \ /
    *---*---*


raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Re: 10720 - Graph Construction

Post by raj » Thu Sep 26, 2013 12:37 am

Need Help I am getting "Wrong Answer"..... :cry: :cry:

I applied Erdos-Gallis Theorem..

Code: Select all

import java.io.*;
import java.util.*;
class IntegerPair implements Comparable {
    Integer _first;
    
    public IntegerPair(Integer f) {
        _first = f;
    }   
	public int compareTo(Object o) {
           return ((IntegerPair )o).first() - this.first();
    }	    
    Integer first() { return _first; }
}
public class Main{
	public static void main(String[] args)throws IOException {
		BufferedReader kk = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter z = new PrintWriter(System.out);
		ArrayList<IntegerPair> q;
		String line;
		while(!(line = kk.readLine()).equals("0")){
			StringTokenizer s = new StringTokenizer(line);
			int n = Integer.valueOf(s.nextToken());
			q = new ArrayList<IntegerPair>();
			q.add(new IntegerPair(Integer.MAX_VALUE));
			//int [] d = new int[s.countTokens()+1];
			while(s.hasMoreTokens()){
				q.add(new IntegerPair(Integer.valueOf(s.nextToken())));
			}
				Collections.sort(q);
				int k = n;
				int sum = 0;
				boolean first = true;
				int sumA = 0;
				boolean aso = true;
				for(int i = 1;i<=k;i++){
					sumA = sumA + Integer.valueOf(q.get(i).first()+"");
					int sumB = 0;
					for(int ii = k+1;ii<=n;ii++){
						if(aso){
							sumA = sumA + Integer.valueOf(q.get(ii).first()+"");
							aso = false;
						}
						sumB = sumB + Math.min(Integer.valueOf(q.get(ii).first()+""), k);
					}
					sumB = sumB + (k*(k-1));
					int cheq = Integer.valueOf(q.get(i).first()+"");
					if(cheq>sumB){
						first = false;
						break;
					}
				}
				if(first && sumA%2==0) z.println("Possible");
				else z.println("Not possible");
		}
		z.flush();
	}
}
Last edited by raj on Wed Oct 30, 2013 1:42 am, edited 1 time in total.

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

Re: 10720 - Graph Construction

Post by brianfry713 » Sat Sep 28, 2013 12:35 am

It should be "Not possible" instead of "Not Possible".
Check input and AC output for thousands of problems on uDebug!

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Wrong Answer: 10720 - Graph Construction

Post by raj » Wed Oct 30, 2013 1:43 am

Thanks sir for finding the mistake :) but still i am getting Wrong Answer :cry:

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

Re: 10720 - Graph Construction

Post by brianfry713 » Thu Oct 31, 2013 11:16 pm

Try the I/O in this thread.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 107 (10700-10799)”