Show all threads Hide all threads Show all messages Hide all messages | Idea | __Andrewy__ | 1324. Extra Spaces | 26 Feb 2022 01:26 | 1 | Idea __Andrewy__ 26 Feb 2022 01:26 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 | Great Problem! :-) | Ostap Korkuna (Lviv NU) | 1324. Extra Spaces | 18 Jan 2018 07:16 | 5 | 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. | Bit of help | jk_qq | 1324. Extra Spaces | 13 Oct 2017 20:57 | 1 | 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. | Strange statetment | Aleksander | 1324. Extra Spaces | 28 Jan 2011 03:03 | 3 | 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! | What algorithm is applicable for such problems? | Anupam Ghosh,Bengal Engg and Sc Uni,MtechIT,2006-09,India | 1324. Extra Spaces | 25 Jan 2011 20:42 | 2 | 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 | Test7 is correct??? | Pio | 1324. Extra Spaces | 22 Dec 2010 23:14 | 3 | 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. | Why I got WA?Help me! | Z H Pascal | 1324. Extra Spaces | 19 Jul 2010 01:42 | 2 | 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. | Statement is incorrect :) | Гладких Максим | 1324. Extra Spaces | 24 Mar 2009 23:26 | 2 | Petrov should use F7 instead of ctrl+F7 :) In Far file manager replacement is Ctrl+F7, F7 is search. | Mistake in statement | Fyodor Menshikov | 1324. Extra Spaces | 24 Mar 2009 23:24 | 1 | А тут еще жюри подсунуло текст отформатированный какой-то противным DOSовским текстовым редактором -> А тут ещё жюри подсунуло текст, отформатированный каким-то противным DOSовским текстовым редактором | what answer for | +FAMAS+ | 1324. Extra Spaces | 14 Mar 2009 02:16 | 6 | 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 and for. Anatoliy 'Tolyan_NO' Tolstobroff 21 Aug 2005 21:24 My output. Anatoliy 'Tolyan_NO' Tolstobroff 21 Aug 2005 21:29 370 and 371 5 22 8 4 3 2 for 199999 7 463 32 10 5 4 3 2 Why I got wa 7?????? 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 | Maybe russian version of the problem statement is incomplete | CD | 1324. Extra Spaces | 26 Aug 2005 09:35 | 3 | 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 | Why WRONG? | Нищий Наглец | 1324. Extra Spaces | 31 Jul 2005 20:47 | 1 | if L=11 Why it WRONG? 4 5 4 3 2 | Is this answer right for test 1,i.e. the sample? | HybridTheory | 1324. Extra Spaces | 3 Nov 2004 05:22 | 5 | the answer is: 4 11 5 3 2 Is it right?who can help me? No. Maigo Akisame (maigoakisame@yahoo.com.cn) 1 Nov 2004 13:08 Read the statement carefully about 'optimal'. Your solution doesn't work for 23, while the sample output does. Re: No. HybridTheory 1 Nov 2004 16:21 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 You're wrong. Maigo Akisame (maigoakisame@yahoo.com.cn) 2 Nov 2004 03:53 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. | What does it mean? | tbtbtb | 1324. Extra Spaces | 11 Aug 2004 15:23 | 8 | 这条题目可以简化为:一篇电子文档有,里面有一些的多余的连在一起的空格。求找出一种解决方案能用最少的次数处理来使得那些多个空格连在一起的变成一个。例如:假如这篇文章里最多的连在一起的空格数为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... See in Vladimir Yakovlev (USU) 11 Aug 2004 15:23 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. | I think the 4 5 3 2 2 is better than 4 6 3 2 2 when L=22 | Ted | 1324. Extra Spaces | 16 May 2004 09:55 | 1 | |
|
|