CS1020 Josephine Lab3 Ex2

Link to the question – Josephine Lab 3 Ex 2

import java.util.*;

// use ListNode to represent a person in the circle
class ListNode {
	ListNode  next;
	int data;
}

class Result {
	
    // declare the member field
	
    // declare the constructor
	public ListNode create(int N)
	{
		ListNode last = new ListNode();
		ListNode first = last;
		last.data = N;
		for(int i = N-1; i>=1; i--)
		{
			ListNode x = new ListNode();
			x.data = i;
			x.next = first;
			first = x;
		}
		last.next = first;
		return last;
	}
	/**
	 *		remove			: removing K-th person and update the state
	 * 		Pre-condition  	:
	 * 		Post-condition 	:
	 */
	private void remove(int K) {
		// implementation
		return;
	}

	/**
	 *		solve			: keep removing K-th person from the circle to find the Chosen One
	 * 		Pre-condition  	:
	 * 		Post-condition	:
	 */
	public void solve(ListNode x, int K) {
		// implementation
		while(x != x.next)
		{
			for(int i = 1; i < K; i++)
			{
				x = x.next;
			}
			System.out.print(x.next.data + " ");
			x.next = x.next.next;
		}
		System.out.println(x.data + " ");
	}
}

public class Josephine {
	
	public static void main(String[] args) {
        
		// declare the necessary variables
		
		// declare a Scanner object to read input
		Scanner sc = new Scanner(System.in);
		// read input and process them accordingly
		int T = sc.nextInt();
		if(T <= 100)
		{
			for(int i = 0; i < T; i++)
			{
				Result r = new Result();
				int N = sc.nextInt();
				int K = sc.nextInt();
				ListNode x = r.create(N);
				r.solve(x, K);
			}
		}
	}
}
Advertisements
This entry was posted in NUS, SoC and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s