[ACM]プログラミング珠玉


赤、白、青のビーズをランダムに並べたN個のネックレスがあります(3<=N<=350).次の例では、N=29のネックレスを2つ示します.
             1 2                              1 2
           r b b r                           b r r b
          r         b                       b         b
         r           r                     b           r
        r             r                   w             r
       b               r                 w               w
      b                 b               r                 r
      b                 b               b                 b
      b                 b               r                 b
       r               r                 b               r
        b             r                   r             r
         b           r                     r           r
           r       r                         r       b
             r b r                            r r w
          Figure A                     Figure B
                        r red bead
                        b blue bead
                        w white bead

図Aはまた、bおよびrからなる文字列で直接表すことができ、bは青色を表し、rは赤色を表し、以下に示す:brbrrrbbbbrrrrrrbrrbbbbbrrrrb.
ネックレスのどこかから切断してまっすぐにしたいとします.次に、同じ色のビーズを一端から他端に数え、異なる色のビーズにぶつかるまで集める.そして反対側から同じ操作をします.△一端に集められたビーズの色は、他端と異なるものであってもよい.
ネックレスを切る位置を見つけて、できるだけ同じ色のビーズを集めることができます.

図Aのネックレスのように、9番目と10番目または24番目と25番目のビーズの間から切断すると、8つのビーズを集めることができます.
図Bのネックレスには白いビーズがあり、白いビーズに出会ったとき、青いビーズとしても、赤いビーズとしても、ビーズを集めるときのニーズによって決まります.白いビーズを含むネックレスは、r、b、w文字の文字列で表されます.
あるネックレスから何個のビーズが収集できるかを計算するプログラムを作成してください.
入力フォーマット
1行目:N、ネックレスのビーズの個数
2行目:長さNの文字列で、r、b、w文字からなる
入力サンプル
29 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb

出力フォーマット
計算された結果を含む1行の文字を出力します.
出力サンプル
11

 
テスト入力
期待出力
時間の制限
メモリ制限
追加プロセス
試験例1
テキスト表示
29↵
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb↵
テキスト表示
11↵
1秒
1024KB
0
くだらないことは言わないで、プログラムに行きます.
#include <stdio.h>
#include <malloc.h>
char s[200];
int Pearl(int n)
{
	int i ,j ,left , k, max ,f = 1, w = 0, p = 0,m = 0;
	char c;
	i = j = max = left = 0;
	while (m < n)
		if (s[m++] != 'w')
		{
			c = s[m-1];
			break;
		}
	if(m == n)//  w,  "wwwwwwwwwwwwwwwwwwwwwwwww"
		return n;
	while ((c == s[i] || s[i] == 'w') && i < n)
	{
		left++;
		i++;
	}
	if (i == n)//        ,  "bbbbbbbbbbbbbbbbbbbbbb"
	{
		f = 0;
		i = 0;
		return left;
	}
	while (f)
	{
		c = s[i];
		j = 0;
		w = i - 1 == -1 ? n-1 : i - 1;
		while(s[w] == 'w')
		{
			p++;
			w = (w - 1 == -1) ? n-1 : w - 1;
		}
		while (s[i] == c || s[i] == 'w')
		{
			f = (i == n-1) ? 0 : f;  //i == n - 1             ,   f  
			i = (i + 1) % n;
			j++;
		}
		left += j;
		max = left > max ? left : max;
		left = j + p;
		p = 0;
	}
	return max;
}
int main()
{
	int n,i,j;
	//freopen("in.txt", "r", stdin);
	while (scanf("%d",&n) != EOF)
	{
		scanf("%s",s);
		printf("%d
",Pearl(n)); } }

いくつかのテスト例を示します.
入力:
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
77
rwrwrwrwrwrwrwrwrwrwrwrwbwrwbwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwr
50
bbrrrbrrrrrrrrbrbbbrbrrbrrrrbbbrbrbbbbbrbrrrbbrbbb
17
wwwwwwwwwwwwwwwww
3
rrr
出力:
11
74
9
17
3