10720 - Graph Construction

[mf]

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]

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

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

[brianfry713]

It should be "Not possible" instead of "Not Possible".

[raj]

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

[brianfry713]

Try the I/O in this thread.