Broken Necklace


/*
ID: tausiq11
PROG: beads
LANG: C++
*/

#include <stdio.h>
#include <iostream>
#include <list>
using namespace std;

int length;
list <char> l;

int call ()
{
	int count = 0;
	char temp = 'w';
	bool flag = true;

	do {
		if ( flag && l.front () != 'w' ) {
			temp = l.front ();
			flag = false;
		}
		l.pop_front ();
		count++;
		//cout << l.front ();
	} while ( l.size () && ( l.front () == 'w' || l.front () == temp ));

	temp == 'r' ? temp = 'b' : temp = 'r' ;

	while ( l.size () && ( l.back () == 'w' || l.back () == temp ) ) {
		l.pop_back ();
		count++;
	}

	return count;
}


int main ()
{
	freopen ("beads.in", "r", stdin);
	freopen ("beads.out", "w", stdout);

	scanf ("%d", &length);

	char a [360];
	scanf ("%s", a);

	int i, j, k;
	int max = 0;
	int value;

	for ( i = 0; i < length; i++ ) {
		for ( j = i; j < length; j++ )
			l.push_back ( a [j] );
		for ( k = 0; k < i; k++ )
			l.push_back ( a [k] );
		value = call ();
		if ( max < value )
			max = value;
		l.clear ();

	}

	printf ("%d\n", max);
	return 0;
}
Advertisements

3 thoughts on “Broken Necklace

  1. hi,
    suppose u have a necklace of N beads
    and u have to cut it in a certain point thus u can get maximum number of beads .. right?

    N is at most as 350
    so u can try out every possible points

    at first i made a list/string of beads by break the necklace at point 0
    and then function call () tells me how much beads i can collect from this list / string
    and thus i can determine the highest number of beads

    for example, given
    wrbbrb

    first try out, wrbbrb
    then try, rbbrbw
    then try, bbrbwr
    then try, brbwrb
    then try, rbwrbb
    then try, bwrbbr

    among those possible cuts u will find the highest number of beads

    invoke the function call for every possible cuts
    and function call will return you the number of beads u can collect for that particular cuts
    i hope if you think a bit then you will find a clue about the implementation of function call
    u don’t have to do exactly as i did ..
    let me know if you face any problem .. good luck 🙂

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