HDu 3363 Ice-sugar Gourd(変換+尺取)
3386 ワード
Ice-sugar Gourd
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1754 Accepted Submission(s): 579
Problem Description
Ice-sugar gourd, “bing tang hu lu”, is a popular snack in Beijing of China. It is made of some fruits threaded by a stick. The complicated feeling will be like a both sour and sweet ice when you taste it. You are making your mouth water, aren’t you? I have made a huge ice-sugar gourd by two kinds of fruit, hawthorn and tangerine, in no particular order. Since I want to share it with two of my friends, Felicia and his girl friend, I need to get an equal cut of the hawthorns and tangerines. How many times will I have to cut the stick so that each of my friends gets half the hawthorns and half the tangerines? Please notice that you can only cut the stick between two adjacent fruits, that you cannot cut a fruit in half as this fruit would be no good to eat.
Input
The input consists of multiply test cases. The first line of each test case contains an integer, n(1 <= n <= 100000), indicating the number of the fruits on the stick. The next line consists of a string with length n, which contains only ‘H’ (means hawthorn) and ‘T’ (means tangerine). The last test case is followed by a single line containing one zero.
Output
Output the minimum number of times that you need to cut the stick or “-1” if you cannot get an equal cut. If there is a solution, please output that cuts on the next line, separated by one space. If you cut the stick after the i-th (indexed from 1) fruit, then you should output number i to indicate this cut. If there are more than one solution, please take the minimum number of the leftist cut. If there is still a tie, then take the second, and so on.
Sample Input
4 HHTT 4 HTHT 4 HHHT 0
Sample Output
2 1 3 1 2 -1
Source
「光庭杯」第5回華中北区プログラム設計招待試合及びWHU第8回プログラム設計コンテスト
标题:一連の氷砂糖ひょうたん、HとTから構成して、あなたの任務はHとTをそれぞれ均等に分けて、最も少ない切る刀の数と切る位置を求めます
分析:
特殊な場合は両側を均等に分けることができますが、中間を一刀で切ることができます.もし一刀で均等に分けることができなければ、せいぜい2刀で、しかも2つの位置はn/2に違いありません.少なくとも一刀は理解しやすいが、なぜ最大2刀なのか.の
証明:
私たちはその首位を円につなぎ、一線は円を半分に分けることができます(つまり2刀).
整円をs,一方の半円をs 1,他方の半円をs 2とする.
仮定 sにはx個のH,y個のTがあり,総和はx+yである.では、s 1のHとTの合計は(x+y)/2であるべきである.
仮定 s 1にはx 1個のH,y 1個のTがあり,x 1=x/2であればx 1+y 1=(x+y)/2であるためy 1=y/2がある.
言い換えれば、1つの半円のHの個数が全体の円Hの個数の半分に等しい限り、必然的にこの半円Tの個数も全体の円Tの半分に等しいなら、この半円は私たちが望んでいる区間であり、その端点は私たちが探している2つの位置である.では、x 1を移動するにつれて必ずx/2に等しいのだろうか.それは一定である.欲しい区間(半円)必ず存在します.以下はx 1が必ずx/2に等しい機会があることを証明します.
sにx個のHがあると仮定し、s 1にx 1個のHがあり、s 2にx 2個のHがある.x 1>x/2である.線の回転によってs 1は必ずs 2に移動するので、x 1は元のx 2に等しくなり、x 1は移動に伴ってx/2より小さいからx/2より大きいまで必ずx/2を通過する.したがってx 1は必ずx/2に等しい機会がある.
以上のように、HとTを最大2刀に分けなければならない.その半円区間は必ず見つかるからだ.
(L,L+n/2-1)のH個数が区間全体のH個数の半分に等しいことを求めて、初めて見つけた区間の両端が答えです.
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1754 Accepted Submission(s): 579
Problem Description
Ice-sugar gourd, “bing tang hu lu”, is a popular snack in Beijing of China. It is made of some fruits threaded by a stick. The complicated feeling will be like a both sour and sweet ice when you taste it. You are making your mouth water, aren’t you? I have made a huge ice-sugar gourd by two kinds of fruit, hawthorn and tangerine, in no particular order. Since I want to share it with two of my friends, Felicia and his girl friend, I need to get an equal cut of the hawthorns and tangerines. How many times will I have to cut the stick so that each of my friends gets half the hawthorns and half the tangerines? Please notice that you can only cut the stick between two adjacent fruits, that you cannot cut a fruit in half as this fruit would be no good to eat.
Input
The input consists of multiply test cases. The first line of each test case contains an integer, n(1 <= n <= 100000), indicating the number of the fruits on the stick. The next line consists of a string with length n, which contains only ‘H’ (means hawthorn) and ‘T’ (means tangerine). The last test case is followed by a single line containing one zero.
Output
Output the minimum number of times that you need to cut the stick or “-1” if you cannot get an equal cut. If there is a solution, please output that cuts on the next line, separated by one space. If you cut the stick after the i-th (indexed from 1) fruit, then you should output number i to indicate this cut. If there are more than one solution, please take the minimum number of the leftist cut. If there is still a tie, then take the second, and so on.
Sample Input
4 HHTT 4 HTHT 4 HHHT 0
Sample Output
2 1 3 1 2 -1
Source
「光庭杯」第5回華中北区プログラム設計招待試合及びWHU第8回プログラム設計コンテスト
标题:一連の氷砂糖ひょうたん、HとTから構成して、あなたの任務はHとTをそれぞれ均等に分けて、最も少ない切る刀の数と切る位置を求めます
分析:
特殊な場合は両側を均等に分けることができますが、中間を一刀で切ることができます.もし一刀で均等に分けることができなければ、せいぜい2刀で、しかも2つの位置はn/2に違いありません.少なくとも一刀は理解しやすいが、なぜ最大2刀なのか.の
証明:
私たちはその首位を円につなぎ、一線は円を半分に分けることができます(つまり2刀).
整円をs,一方の半円をs 1,他方の半円をs 2とする.
仮定 sにはx個のH,y個のTがあり,総和はx+yである.では、s 1のHとTの合計は(x+y)/2であるべきである.
仮定 s 1にはx 1個のH,y 1個のTがあり,x 1=x/2であればx 1+y 1=(x+y)/2であるためy 1=y/2がある.
言い換えれば、1つの半円のHの個数が全体の円Hの個数の半分に等しい限り、必然的にこの半円Tの個数も全体の円Tの半分に等しいなら、この半円は私たちが望んでいる区間であり、その端点は私たちが探している2つの位置である.では、x 1を移動するにつれて必ずx/2に等しいのだろうか.それは一定である.欲しい区間(半円)必ず存在します.以下はx 1が必ずx/2に等しい機会があることを証明します.
sにx個のHがあると仮定し、s 1にx 1個のHがあり、s 2にx 2個のHがある.x 1>x/2である.線の回転によってs 1は必ずs 2に移動するので、x 1は元のx 2に等しくなり、x 1は移動に伴ってx/2より小さいからx/2より大きいまで必ずx/2を通過する.したがってx 1は必ずx/2に等しい機会がある.
以上のように、HとTを最大2刀に分けなければならない.その半円区間は必ず見つかるからだ.
(L,L+n/2-1)のH個数が区間全体のH個数の半分に等しいことを求めて、初めて見つけた区間の両端が答えです.
#include
#include
#include
using namespace std;
int main()
{
int n;
string str;
while(cin>>n&&n)
{
cin>>str;
str+=str;
int h=0,t=0,x=0,y=0;
for (int i=0; i