Handshaking lemma

In graph theory, a branch of mathematics, the handshaking lemma is the statement that every finite undirected graph has an even number of vertices with odd degree (the number of edges touching the vertex).

- From Wikipedia, the free encyclopedia

Railroad is one of the challenges that can be solved using this lemma.

Solution is if 4X +3Y ≡ 0 mod 2, then possible. Otherwise, it is impossible.

	import java.util.Scanner;
	public class Main {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int x = sc.nextInt();
	int y = sc.nextInt();
	int res = 4 * x + 3 * y;
	if (res % 2 != 0) {
	System.out.println("impossible");
	} else {
	System.out.println("possible");
	}
	sc.close();
	}
	}

view raw Railroad.java hosted with ❤ by GitHub

And it can be reduced to just checking whether Y is even or odd.

	import java.util.Scanner;
	public class Main {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int x = sc.nextInt();
	int y = sc.nextInt();
	if (y % 2 != 0) {
	System.out.println("impossible");
	} else {
	System.out.println("possible");
	}
	sc.close();
	}
	}

view raw Railroad.java hosted with ❤ by GitHub