[ACM]プログラミング珠玉
赤、白、青のビーズをランダムに並べたN個のネックレスがあります(3<=N<=350).次の例では、N=29のネックレスを2つ示します.
図Aはまた、bおよびrからなる文字列で直接表すことができ、bは青色を表し、rは赤色を表し、以下に示す:brbrrrbbbbrrrrrrbrrbbbbbrrrrb.
ネックレスのどこかから切断してまっすぐにしたいとします.次に、同じ色のビーズを一端から他端に数え、異なる色のビーズにぶつかるまで集める.そして反対側から同じ操作をします.△一端に集められたビーズの色は、他端と異なるものであってもよい.
ネックレスを切る位置を見つけて、できるだけ同じ色のビーズを集めることができます.
例
図Aのネックレスのように、9番目と10番目または24番目と25番目のビーズの間から切断すると、8つのビーズを集めることができます.
図Bのネックレスには白いビーズがあり、白いビーズに出会ったとき、青いビーズとしても、赤いビーズとしても、ビーズを集めるときのニーズによって決まります.白いビーズを含むネックレスは、r、b、w文字の文字列で表されます.
あるネックレスから何個のビーズが収集できるかを計算するプログラムを作成してください.
入力フォーマット
1行目:N、ネックレスのビーズの個数
2行目:長さNの文字列で、r、b、w文字からなる
入力サンプル
出力フォーマット
計算された結果を含む1行の文字を出力します.
出力サンプル
テスト入力
期待出力
時間の制限
メモリ制限
追加プロセス
試験例1
テキスト表示
29↵
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb↵
テキスト表示
11↵
1秒
1024KB
0
くだらないことは言わないで、プログラムに行きます.
いくつかのテスト例を示します.
入力:
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
77
rwrwrwrwrwrwrwrwrwrwrwrwbwrwbwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwrwr
50
bbrrrbrrrrrrrrbrbbbrbrrbrrrrbbbrbrbbbbbrbrrrbbrbbb
17
wwwwwwwwwwwwwwwww
3
rrr
出力:
11
74
9
17
3
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