Advertisement contains up to 100000 symbols and ends with a newline.

So may need to store 100000 symbols + newline symbol + one '\0' symbol.

I had problems with this using fgets in C++.

Binary search the optimal value when only latin and spaces. You don't have to iterate through all m. Calculate transition for n in O(1) time. Overall complexity should be something like O(|s|log(m)).

add ? to your list

Hello. Could somebody tell me a right DP approach to this problem. I couldn't figure out the solution better than O(|S|*M). |S| - length of the string.

4 100
aaaaaaaaaaaaaaaaaaaa11aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa111
ans : 4

I use dp,but W4.Who can give me some hints or tests.
Thanks a lot.

This is very important:
"SMS message which consists of latin letters and spaces only can be up to M characters long while the length of SMS message which consists of any characters is limited by N characters."
Because non-latin letters are coded by another charset and message header will took 5 extra bytes. Read the problem task about N and M you will understad;
test case:
3    5
aaaa      答案是 1

3 5
aaa!       答案是 2

http://blog.csdn.net/zhangyanxing666/article/details/9831623

In The documentation that the type of string is not limited to 255 characters.

but the program does not pass the second test.

Q: Amount of characters is limited or not?
or how to make a string of unlimited?

Somebody give me a hint about this test or possible mistake. Thanks to all who will answer

AC

Edited by author 22.06.2008 04:48

int main(int argc, char** argv)
{unsigned long long int min = 0, max = 0;
 unsigned long long int len = 0;
 unsigned long long int tt = 0;
 unsigned long long int counter = 0;
 char a[100001];
 int i;

 scanf("%lld %lld",&min,&max);
 gets(a);
 gets(a);
 len = strlen(a);

for(i = 0;i<len;i++)
{
        if((unsigned char)(a[i])==' ' || isalpha((unsigned char)(a[i])))
        {
        tt++;
        if(tt == max)
        {
            tt = 0;
            counter++;
        }
        }
        else
        {
        tt = 0;
        }

}
if((len-(counter*max))%min == 0)
 counter+=(len-(counter*max))/min;
else
 counter+=(len-(counter*max))/min+1;

 printf("%lld",counter);

    return 0;
}

Edited by author 13.02.2011 18:48

Tags: dynamic programming

But most solution of the problem use a greedy algo

On the 11-(10-1)th of Febr(10-2)uary, 2006(10-3) the conte(10-4)st "Timus (10-5)Top Coders(10-6): First Ch(10-7)allenge" i(10-8)s held!
The exemple of this problem is wrong,isn't it?

I submitted this problem in C++ and got WA #2. It used getline and C++ strings.

Then I rewrote it in Pascal and got AC. I really don't understand why. Explain it to me, please.

Do you know what's so special about it? I have WA :(

I saw some explanations, it's rare, but the example is:
10 15
On the 11-th of February, 2006 the contest "Timus Top Coders: First Challenge" is held!

Some explanations have this:
On the 11-         <1>
th of February     <2>
, 2006 the         <3>
 contest "         <4>
Timus Top Coders   <5>
:                  <6>
 First Challenge   <7>
" is held!         <8>
I think the second is wrong, they are 14 caracters and we have M = 15, and N = 10, so we cannot have this. .. please any suggesttion, may be I din't understand something.

Edited by author 24.08.2006 17:55

Surely DP :) but dont use SeekEoln it makes WA4. Just Eoln!!!