Let's sequence S(n) = {s[1], s[2], ..., s[n]} is optimal sequence for the first n steps. L[i] is max number when we can get one space using S(n) for any number in range [1..L[i]]: firstly, we apply s[n], then s[n-1] and etc. Now let's get next s[n+1]. Suppose we found s[n+1] and want get L[n+1]. Always L[n+1] + 1 = q*s[n+1] + r, 0<=r<s[n+1]. L[n+1] is max number => for L[n+1] + 1 we need at least n+2 steps => q + r >= L[n] + 1. But L[n+1] + 1 is min number when using S(n+1) we can't get one space => r->max, q->min => r = s[n+1] - 1, q = L[n] + 1 - r => L[n+1] + 1 = q * s[n+1] + r => L[n+1] = (L[n] - s[n+1] + 2) * s[n+1] + s[n+1] - 2 -> max (where arg is s[n+1]) => s[n+1] = (L[n] + 1) / 2 But using symmetry we can give s[n+1] = floor(L[n] / 2) + 1 (we choice bigger number because s[2] > 1). => L[n+1] = q * s[n+1] + r - 1, q = L[n] + 1 - r, r = s[n+1] - 1.
Edited by author 26.02.2022 01:27 Edited by author 26.02.2022 01:27 I'd like to thank authors for this problem - it became one of my favorite on Timus! Thanks again for very interesting problem! :-) what is that can you tell me what problem it is It's the one that is in the caption of this message :-) It's 1324. Yeah.. But limits could be higher... What about 10^20? :) Or even 10^33. 64-bit integer is still enough (for answer, not for input, but we can just ignore too long input). Or even 10^{10^4}. Works for naive long multiplication. Or even 10^{10^5}. Works in 0.3 in python (only 8 lines!). Or even 10^{10^6}. Hello, FFT! For problem can be solved in T(n), where n = length of input, T(n) is time of multiplication. Nice problem. Playing out with small numbers and sample could help in sequence instantiation. My solution is only 30 lines of c++ code O(L) though. Hint: imagine we have sequence which can replace up to L spaces afterall. Then to enlarge our sequence we insert L/2 + 1 in the beginning. Maximum L could be computed via straightforward iteration starting from lax max_L Example: seq: 2 max_L: 2 seq: 2, 2/2 + 1 = 2, 2 max_L: 2, 4 seq: 2, 2, 4/2 + 1 = 2, 2, 3 max_L: 2, 4, 10 seq: 2, 2, 3, 10/2 + 1 = 2, 2, 3, 6 max_L: 2, 4, 10, 40 Etc. GL. In the statement it is said, that "If there are many such schemes, then you should choose an optimal scheme among them, i.e., a scheme that also reduces sequences of up to K spaces (K ≥ L) for a maximal possible K." So for the sample right answer would be 4 11 5 3 2 and maximum possible k = 110 Where I was wrong, people? :) Oh, now I see.. Admins, please correct russian statement. Look at this: English: If there are many such schemes, then you should choose an optimal scheme among them, i.e., a scheme that also reduces sequences of up to K spaces (K ≥ L) for a maximal possible K. If there are several optimal schemes, you may give any one of them. Russian: Если таких планов несколько, то вы должны выбрать среди них оптимальный — такой, который позволяет заменить последовательности пробелов длины K (K ≥ L) для максимально возможного K. These conditions are not equal! An example you can see in my previous post. Good Luck! Hi Experts, Can you suggest how to approach solving such problems. I am getting no clues at all. Moreover we know nothing about total number of spaces in the text. regards Anupam If you have a group with N spaces and apply to it the operation, that changes K spaces to one, then the number of spaces will be N/K + N%K. You should output such numbers K[1], K[2], ... , K[m], that for every number N in range [1..L] a sequence of operations N := (N/K[i] + N%K[i]) for each i = 1..m will make the value N equals 1. And then you should maximize the range for N. I guess it is a school problem :) Edited by author 25.01.2011 20:42 Edited by author 25.01.2011 20:43 I think that checker is not correct. Admins, please, check test7. too got wa7 P.S. in test 7 L=11 my program out 4 5 4 3 2 Admins why it wrong???????????? if n== 3 , your answer doesnt correct!!! the answer must correct for all the i between 1 to n. sorry for my poor english. Here is my program:program Space; var L, R, I, J, K : longint; s : array [1.. 1000] of longint; begin readln (L); if L < 2 then R := 0; for I := 1 to 1000 do s [I] := 0; if L > 1 then begin I := 2; J := 2; s [1] := 2; R := 1; repeat if L > J then begin inc (R); s [R] := I; if R > 3 then inc (s [R]); I := J + 1; J := (I + 2 - s [R]) * s [R] - 2; end; until L <= J; end; writeln (R); for I := R downto 1 do writeln (s [I]); end. As for me - I don't try to create solution by "jumps". I go from 2 to N and some times add i/2+1 to answer. Petrov should use F7 instead of ctrl+F7 :) In Far file manager replacement is Ctrl+F7, F7 is search. А тут еще жюри подсунуло текст отформатированный какой-то противным DOSовским текстовым редактором -> А тут ещё жюри подсунуло текст, отформатированный каким-то противным DOSовским текстовым редактором 370 371 199999 For 370 and 371: 5 21 6 3 2 2 For 199999: 7 26796 231 21 6 3 2 2 Edited by author 21.08.2005 21:06 11 370 and 371 5 22 8 4 3 2 for 199999 7 463 32 10 5 4 3 2 Why I got wa 7?????? for 1999999 what answer 7 26?96 231 21 6 3 2 2 Edited by author 14.03.2009 02:17 Edited by author 14.03.2009 02:20 I haven't found equivalent of this in it: If there are many such schemes, then you should choose an optimal scheme among them, i.e., a scheme that also reduces sequences of up to K spaces (K >= L) for a maximal possible K. If there are several optimal schemes, you may give any one of them. From the beginning I too have not understood a condition What answer for n=1999999 if L=11 Why it WRONG? 4 5 4 3 2 the answer is: 4 11 5 3 2 Is it right?who can help me? Read the statement carefully about 'optimal'. Your solution doesn't work for 23, while the sample output does. No. If there's 23 spaces. After the first round there's 3. And in the third round they become one. Edited by author 01.11.2004 16:22 For 23: After the first round there are 12 spaces instead of 3. Because 23 means there are 1 space, 2 spaces, 3 spaces... up to 23 spaces, not only 23 spaces. After the first round, 23 becomes 3, but 21 leaves 12. 这条题目可以简化为:一篇电子文档有,里面有一些的多余的连在一起的空格。求找出一种解决方案能用最少的次数处理来使得那些多个空格连在一起的变成一个。例如:假如这篇文章里最多的连在一起的空格数为22,那么其中之一的解决方案为6,3,2,2。也就是说:你第一次你是把每6个连在一起的格子变成一个,第二次你是把每3个格子连在一起的变成一个。。。。。。。、其中,假如有一个是7个格子连在一起的,则经过第一次处理(把6个连在一起的变成一个),那么它便变成了2个格子。。。。。。。。。。。。 Edited by author 06.08.2004 20:57 I also want to know. Can We just replace the spaces once and get the optimal ans ? If We can't , What is the spaces num limit we should assume? Why?? I think it remains only 1 space... Consider example: text[21 spaces]text text[22 spaces]text text[23 spaces]text after replacing 22 spaces with one, we get: text[21 spaces]text text[1 space]text text[2 spaces]text So, 21 spaces can remain in some place. |
|