Just another WordPress.com site

ACM UVA 10127 – Ones

This is a very easy but tricky problem. If you want to calculate the sequence of one by increasing ONE, then two thing can be happened.

1) If your data type is even long double (in C it is the highest data type), it can not hold the sequence and because of overflow you will get WA.
2) If your data type is string then you will get “time limit exceeded”. To avoid these problems we need to follow a trick here.

The Algorithm

input (it will be the input of the problem) 
N=1
one=1 (in this variable finally we get how many one will be in the sequence)

loop until we find the desired answer {
  if N < input
    append a ‘1’.  (this the way -> N=N*10+1)
    one = one + 1
  k = N mod input  ( k is a variable )
  do this until k = 0, otherwise N = k and repeat everything
}

Example

Let the input is 3
At first N = 1 and one  = 1

Now,
3 | 1 | but here N < input so, append a ‘1’
one = one + 1 = 2
3 | 11| 3
     9
   —–
     2
Now, k = 2, so, N=k;
again,

3 | 2 | but here N < input so append a ‘1’
one = one + 1 = 3

3 | 21| 7
    21
  —–
     x

So the output is variable ‘one’ which contains the value 3

Basically, this problem is a reverse version of dividing a series of ‘1’s with N. In the example above. The step by step of dividing “111” with “3” is like this:

3 |111| 37
    9   => the same ‘9’ that we see above
  —–
    21
    21  => the same ’21’ that we see above
   —-
     x

So, basically we just simulate this division but without spanning out the actual string of ‘1’s.

 

CODE

 

#include<iostream>
using namespace std;

int calculate(int input)
{
    long int N=1;
    int one=1,k;
    while(1)
    {
        if(N<input)
        {
            N=N*10+1;
            ++one;
        }
        k=N%input;
        if(k==0)
            break;
        else
            N=k;
    }
    return one;
}

int main()
{
    int N;
    while(cin>>N)
        cout<<calculate(N)<<endl;
    return 0;
}

জানি বন্ধু তুমি বড় অভিমানী
          রক্তে তোমার আগুন জ্বলে
এখনি সময় সব কিছুর solution করার
          সাজিয়ে নাও তোমার তড়ে …।

Comments on: "ACM UVA 10127 – Ones" (2)

  1. সাইফ...ঢাবি said:

    সুন্দর…

  2. Thanks Saif for your comment . Be prepared for next ACM contest

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: