ACM (UVa) : 10935


Use a circular queue to solve this problem

or, if u r able to use STL then this problem can be categorized as a easy one
i have included serial input-output cases, thus it will be made easy for u to debug ur code, if any problem occur
i think it’s a good idea to learn STL documentation, becoz it’s very helpful and provides various features to eliminate hazards

some links:
1. http://www.sgi.com/tech/stl/
2. http://www.cplusplus.com/reference/stl/
3. http://www.java2s.com/Code/Cpp/CatalogCpp.htm

#inlcude <list>

using namespace std;

list <int> var; // declare a list variable named “var”

var.clear (); // clear the list

var.push_front (x); // insert element x at the front

var.size (); // returns the size of the list

var.front (); // access the top element of list, but not removed it

var.pop_front (); // wipe out the top element of the list

var.push_back (x); // insert an element at the back of the list


#include "stdio.h"
#include "list"

using namespace std;

int main ()
{
	list <int> v;
	int n, i, flag, temp;

	while (scanf ("%d", &n)) {

		if (n == 0)
			return 0;
		v.clear ();

		for (i = n; i >= 1; i--)
			v.push_front(i);

		flag = 0;
		printf("Discarded cards:");

		while (v.size () > 1) {
			if (flag == 0) {
				temp = v.front ();
				printf(" %d", temp);
				v.pop_front ();
				flag = 1;
				temp = v.front ();
				v.push_back (temp);
				v.pop_front ();
			}

			else {
				temp = v.front ();
				printf(", %d", temp);
				v.pop_front ();
				temp = v.front ();
				v.push_back (temp);
				v.pop_front ();
			}
			if (v.size () == 1)
				printf("\n");
		}

		if (flag == 0)
			printf("\n");

		printf("Remaining card: %d\n", v.front ());
	}

	return 0;
}








Critical input:
1
2
3
4
5
6
8
9
50

Critical output:
Discarded cards:
Remaining card: 1
Discarded cards: 1
Remaining card: 2
Discarded cards: 1, 3
Remaining card: 2
Discarded cards: 1, 3, 2
Remaining card: 4
Discarded cards: 1, 3, 5, 4
Remaining card: 2
Discarded cards: 1, 3, 5, 2, 6
Remaining card: 4
Discarded cards: 1, 3, 5, 7, 2, 6, 4
Remaining card: 8
Discarded cards: 1, 3, 5, 7, 9, 4, 8, 6
Remaining card: 2
Discarded cards: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 8, 16, 24, 32, 40, 48, 12, 28, 44, 20, 4
Remaining card: 36

Advertisements

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