Discussion of Problem 1427. SMSHello. 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. Easy problem. Let dp[i] - answer for string S1..Si. Then dp[i]=min(dp[i],dp[i-n]+1). (Maximum possible N-characters message). If last_idx - index of last "bad" character, then dp[i]=min(dp[i],dp[max(last,i-m)]+1). If current character is "bad" - update last_idx. It's O(|S|) solution. A pure greedy problem. You don't need to use any array, the algorithm is very simple: For each characters, just check if you can add it to the current message, if not you will create a new message and then add it to this message. What is the BAD character in string??? 4 100 aaaaaaaaaaaaaaaaaaaa11aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa111 ans : 4 I still get this one right and get WA on test 8. Is this test real? I use dp,but W4.Who can give me some hints or tests. Thanks a lot. Though I don't know why I wa4 that time , I AC now without any change... may be it's time's power... Try 1 10 a1aaaa1aaaa1 Try 1 2 [space] [space] = " " Trick was with I\O. I held half of contest myselt trying to pass it. If you use C\C++, you may have the same bug. Reading scanf("%d%d\n",&n,&m); gets(a); got WA#7, but this code scanf("%d%d",&n,&m); gets(a); gets(a); got AC. Why? I don't know! But it would be better to learn more about this bug. What do you think about it? Safe Bird can you explain why his first code is wrong? scanf("%d%d\n",&n,&m) reads not only new line character but leading spaces in second line. If you use C++, you must know it! Don't mix up 'scanf' and 'gets' or you will have unpredictable am-I-before-or-after-EOL situations. If you have to use 'gets' in the problem, use ONLY 'gets', and use 'sscanf' to extract row elements from the string fetched via 'gets', or use 'strtok' if you don't know amount of elements beforehand. For this particular problem I wrote: gets(s); sscanf(s, "%d %d", &n, &m); gets(s); >> scanf("%d%d\n",&n,&m) reads not only new line character but leading spaces in second line. >> If you use C++, you must know it! Thank you for explain! :) Edited by author 12.08.2008 22:09 Thank you for your useful tip! I didn't find any document about this behavior. Your experience is really great. 2Igor E. Tuphanov Thank you! You are very helpful! 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/9831623In 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 I have the same problem. :( 1 1 a?a (my first program failed on this case) thank you. it helps me very much. Now i get AC answer is 3 ? My Answer is 3, but i have WA on 19th test. Where is the problem? I'v just got AC, try those tests 1 1 a?a ANS = 3 1 2 a?a? ANS = 4 1 2 ?a?aaaa 5 My answer is 5 ,but i get WA on 17th test 10 15 The first line contains the integer numbers N and M . The second line contains an advertisement. The advertisement consists of from 1 to 100000 characters. Each character is either a latin letter, a space, a digit or a punctuation mark "." full stop, "," comma, ";" semicolon, ":" colon, "!" exclamation mark, "?" question mark, "-" hyphen or """ double quotes. The advertisement is terminated by the end of line. My answer is 36 on this test, but i don't know it is right or wrong,who can tell me the answer? Edited by author 09.05.2012 19:05 Edited by author 09.05.2012 19:05 Edited by author 09.05.2012 19:06 Yeah, it’s real answer))) My AC program say this Try test 1 4 abcd&abcd ANS: 3 I don’t know real test, but try this))) Edited by author 18.06.2012 01:46 Edited by author 18.06.2012 01:47 AC Edited by author 22.06.2008 04:48 Why did you wa 5? I got a wa 5,too. Please help me. 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? Example is correct: On the 11-<1>th of February<2>, 2006 the <3>contest "T<4>imus Top Coders<5>: First Ch<6>allenge" i<7>s held!<8> you are very very very bad man, the correct answer to example is: On the 11-<1-10>th of February<2-14>, 2006 the<3-10> contest "<4-10>Timus Top Coder<5-15>s: First C<6-10>hallenge" <7-10>is held!<8> in your example ", 2006 the " 11 simbols!!! after your explain I think that spaces in begin of sms must delete and I always have WA4! 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 had this problem. Change result from Word to LongWord. Result may be up to 100000 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. The length of 2nd line cannot be 15, because it'll include ',', which will force you to send only 10 chars. So it's better to send only 14 chars in 2nd message. Your message don't have to be exactly of length of 10 or 15. Edited by author 24.08.2006 17:55 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! This exemple is wrong,isn't it? Problem №1427 Surely DP :) but dont use SeekEoln it makes WA4. Just Eoln!!! That tests were no terminated by the end of lines indeed because of force majeure... Now the new rules for tests are being developed to prevent such things in the future. Anyway we must apologize for it. If you got WA(17), you may run your program again. Edited by author 12.02.2006 17:11 I started to code G at the beginning of the contest... and I soon found it wa on 18...... my teammate starts to help me find the bug.... it was until 4hours after the beginning, my teammate uses Pascal and ACed......... :'( if i have aced G at the beginning, things would possibly change:( 17-th test was the first test that had not eoln, but your program passed it. If the problem appeared because of eoln, it could fail on 17-th test. Could you explain it? Edited by author 12.02.2006 17:25 have you read the other post of mine? if i use: for (;;) { if (feof(Fin)) break; char ch=fgetc(Fin); if (ch=='\n') break; ... } i will pass 17, but if i use: char ch=fgetc(Fin); if (ch=='\n') break; i will TLE on 17. i don't know why my program passes 17, but failed on 18. you could see my submission, the original program will get AC. It is beyond my rights to look at your submission and it is beyond my power to rejudge the contest. Vladimir Yakovlev will make a decision about this problem. I do not use ICQ :( But one day I will. Edited by author 12.02.2006 17:51 these statements are not useful: if (feof(Fin)) break; char ch=fgetc(Fin); if (ch=='\n') break; use should use these: char ch=fgetc(Fin); if (ch=='\n' || ch==EOF) break; BECAUSE feof(FILE*) returns true iff the end-of-file was already read. So you terminate input string with character 255. Tests were correct, but with no eoln before oef. You considered such situation but made a mistake. "char ch=fgetc(Fin); if (ch=='\n' || ch==EOF) break;" is against the problem description! i think this problem should be rejudged, since you have said: "The advertisement is terminated by the end of line." in the description! Edited by author 12.02.2006 21:13 I don't know much difference between feof and ch==EOF, BUT the problem has said that input is terminated by '\n'! I thought there will be no difference between using that line or not!!! you could contact "Dmitry 'Diman_YES' Kovalioff", the test cases 17,18,... are indeed wrong during the contest. (now they are okay) |
|