Threaded Mode | Linear Mode

***drdebcol*** · (This post was last modified: 04-03-2010 08:52 PM by drdebcol.)

A long string is composed by concatenating N times the string S. From the resulting string all the characters at odd positions are removed.Then from the string that remains, again all the characters at odd positions are removed.The process continues until there is only one character left.

Your task is to write a program that finds the last character.
Example: The string PROFILE is written 2 times
--------------------
PROFILEPROFILE
----------------------
-R-F-L-P-O-I-E
-------------------
RFLPOIE
---------------
-F-P-I-
-----------
FPI
---------
-P-
----------
P
------------
So the last character is "P" .

Input
In the first line will be the string S, (5<=length(S)<=250), containing only capital letters. The second line will contain N, (1<=N<=1000000000) , number of times the string S is concatenated.

Output
The output should contain a string, of length 1, which contains only the last remaining character. Don't forget to output the END LINE character after it!

Sample Input
PROFILE
2

Sample Output
P

Sample Input
ABC
10

Sample Output
A

Solution
On first look this is an easy task. You just concatenate string, erase odd characters until you get length of string equals one and write it on the screen. To concatenate string means to add one string to another, like here :

Code:

s='ab';

d='cd';

k=concat(s,d); // k is 'abcd'

So in Pascal you have concat() function, but you can do basic addition of strings like here :

Code:

s='ab';

d='cd';

k=s+d; //k is 'abcd'

That solution should look like this in TPW :

Code:

program concatenated_string_problem;

uses wincrt;

var

i,n:longint;

s,d:string;

begin

  readln(s);

  readln(n);

for i:=1 to n do

  s:=s+s;

while (length(s)>1) do

  begin

  d:='';

    for i:=1 to length(s) do

      if i mod 2 = 1 then

        d:=d+s[i];

        s:=d;

  end;

writeln(s);

end.

And in C++ :

Code:

# include <iostream>

# include <cstdio>

using namespace std;

int main()

{

    int i,n;

    string d,s;

    cin>>s;

    cin>>n;

    for (i=1;i<n;i++)

      s=s+s;

    while (s.length()>1)

    {

       d="";

       for (i=0;i<s.length();i+=2)

         d=d+s[i];

         s=d; 

    }

    cout<<s<<endl;

    system("pause");

}

But there is one problem. Length of string is 256 characters. As you can see in the task, you can get as input 255 character string and when you concatenate that n times and make string length :

Code:

start_length*number_of_concat_operations

So you need to combine number theory with this task and you have fast solution. First let's look at this example :
[Image: 25079_concaticate1.jpg]

As you can see word "PRO9RAMMING" has length 11 and at the end solution is "M". Now when we convert that in numbers you have numbers from one to eleven, like on this picture :
[Image: 25080_concaticate2.jpg]

As you can see solution is 8 and that is like letter "M" which we got in the first case. So solution is 8 and now goes the main part. Solution is the biggest exponent of 2 that is smaller or equal to length of that string.

So solution would be exponent of 2 or 2^k, and it is from this row :
[Image: 25081_concaticate3.jpg]

Mathematically you can write this row like this :
[Image: 25082_concaticate4.jpg]

So if you find the biggest exponent of 2 that is in Natural Numbers that is not bigger than length of string, you have the solution.
More about Natural Numbers you have here :
http://en.wikipedia.org/wiki/Natural_number
Now let's see what happens when we connect everything together :
[Image: 25083_concaticate5.jpg]

And now you have question what if you have string concatenate more than once. Well that is simple you just need to find module of that solution with length of string.
So let's see this example :
[Image: 25096_concaticate6.jpg]

You have string "ABC" and number of concat() functions is n in this case 2.
So main string is "ABCABC" and when we do this operation we have "A" as a solution. And "A" is on position 4. You just need to find module of 4 with length of string :

Code:

4 mod 3 = 1

So length of string "ABC" is 3 and when we find module it is one and we just need to write that on the screen like this :

Code:

s[number mod length] // This is s[1] which is "A" and that is solution

That would be everything about theory of this task. If you don't understand some part, just ask. Now here is the solution n TPW:

Code:

program concatenated_string_problem;

uses wincrt;

var

i,n:longint;

k:integer;

s:string;

begin

  readln(s);

  readln(n);

  k:=length(s);   

  i:=1;

while (i<=n*k) do

  begin

    i:=i*2;

  end;

  i:= i div 2;

writeln(s[i mod k]);

end.

And in C++ :

Code:

# include <iostream>

# include <cstdio>

using namespace std;

int main()

{

    int i,n,k;

    string d,s;

    cin>>s;

    cin>>n;

    k=s.length();

      i=1;

    while (i<=n*k)

    {

        i*=2;

    }

    i=i/2;

    cout<<s[(i % k) - 1]<<endl;

    system("pause");

    return 0;

}

There are small differences in C++ and Pascal. That is because array in C++ starts from zero and first character in C++ is not s[1] but s[0].
You can test second algorithm. It is much faster and it does operations from bigger cases. Simplicity rulez !

OFFTOPIC :
I had a small spelling mistake.
String is not concaticated, it is concatenated, so i had to edit the post to fix that. Sorry !

codecaine · (This post was last modified: 12-12-2009 07:40 AM by codecaine.)

done this in python the name[1::2] returns a string starting at the second character and step by 2

Code:

mystring = raw_input("Enter in a string: ");

while len(name) != 1:

     name = name[1::2]

print("result: " + name);

***drdebcol*** · 12-12-2009, 07:43 AM

Python really rocks !
Great code !

codecaine · 12-12-2009, 07:44 AM

hehe thanks. python don't have a limit on how long as string is either. So thats a bonus Smile

***drdebcol*** · 12-12-2009, 07:46 AM

Yeah and i had to think about that in Pascal and C++.

codecaine · (This post was last modified: 12-12-2009 07:52 AM by codecaine.)

What I would of done in pascal or c++ is used pchar for a array for characters then you would have no limit. same thing with c++ char *mystring;

well the limitation would be that amount of memory on your computer Tongue

codecaine · 12-12-2009, 10:04 AM

Almost forgot c++ string size not limit to 255 either.

***drdebcol*** · 12-12-2009, 09:44 PM

Yeah you are right. C++ does not have limit. But i decided to post faster solution.
In second algorithm you have exponential grow 2^k and it raises rapidly so if you have string length for example 65536 long you will have 16 operations of multiplication with 2 and one module at the end.
In case of cutting strings you will have to do much more operations, you understand what i mean.
If you have string length of 65536 you will have to erase odd position characters 32768 and then 16384 . . . . etc.
So this second algorithm is much faster, but the first one will do the job too !