Codechef Easy Problem - Nuclear Reactors

[prakhs]

http://www.codechef.com/problems/NUKES
I'm getting time limit exceeded in my code... Please some one help me out with this code. My algorithm is when A - ((N+1) ^ (p+1)) < 0 then pth chamber will have 1 particle and the new value of A in my recursive function is A - ((N+1) ^ p). This process will continue till A < N+1, then k[0] will be A.

#include <stdio.h>
#include <math.h>

int k;
int N;

/* if [A - (N + 1) ^ (p + 1) < 0], then pth chamber will have one particle and new value of A i.e. A' will be [A - (N + 1) ^ p] and the same procedure will be applied to get the new value of p. This process will continue till A* will be less than N + 1 */
void recurse(int a[], int A)
{
    if (A < N + 1) {
        a[0] = A;
        return;
    }
    int p = 0;
    int A2 = 0;
    while (A - pow(N + 1, p + 1) >= 0)
        ++p;
    if (p < k)   /* there are only k chambers, rest will go to waste */
        ++a[p];
    A2 = A - pow(N + 1, p);
    recurse(a, A2);
}
main()
{
    unsigned long int A;
    scanf("%lu %d %d", &A, &N, &k);
    int a[k];
    int j;
    for (j = 0; j < k; ++j)
        a[j] = 0;

    recurse(a, A);

    for (j = 0; j < k; ++j)
        if (j == k - 1)
            printf("%d\n", a[j]);
        else
            printf("%d ", a[j]);

    return 0;
}

I'm getting this error :
http://www.codechef.com/submit/complete/52434-4579--506325bda1ce2

[L7Sqr]

I believe you are over-thinking this. Try to abstract the problem into something you already understand. Here is a hint: ones, tens, hundreds, thousands, ...

[prakhs]

not getting it can u tell me in which test case it exceeds time-limit.
I have made a non-recursive solution also, this also is getting time limit exceeded in "test 8; Approx_N_value 100" and it is running well for "test 1 to 7; Approx_N_value 10 to 1000000000".
here's a non-recursive code

#include <stdio.h>
#include <math.h>

main()
{
    unsigned long int A;
    int N, k;
    scanf("%lu %d %d", &A, &N, &k);
    int a[k];   /* stores no. of particles in a chamber */
    int j;
    unsigned long int power;
    for (j = 0; j < k; ++j)
        a[j] = 0;

    while (A != 0) {
        j = 0;
        while (A - pow(N+1, j) >= 0)
            ++j;
        power = (unsigned long)pow(N+1, j-1);
        a[j-1] = A/power;
        A = A % power;
    }

    for (j = 0; j < k; ++j)
        if (j == k - 1)
            printf("%d\n", a[j]);
        else
            printf("%d ", a[j]);

    return 0;
}

[prakhs]

A more better version

#include <stdio.h>
#include <math.h>

main()
{
    long int A;
    int N, k;
    scanf("%lu %d %d", &A, &N, &k);
    int a[k];   /* stores no. of particles in a chamber */
    int j;
    long int power[101];
    for (j = 0; j < k; ++j)
        a[j] = 0;

    for (j = 0; A - (power[j] = (long)pow(N+1, j)) >= 0 && j < 101; ++j)
        ;
    while (A != 0) {
        j = 0;
        while (A - power[j] >= 0)
            ++j;
        a[j-1] = A/power[j-1];
        A = A % power[j-1];
    }

    for (j = 0; j < k; ++j)
        if (j == k - 1)
            printf("%d\n", a[j]);
        else
            printf("%d ", a[j]);

    return 0;
}

[L7Sqr]

This is essentially a base-N problem. You are given a set of items, a base to convert them into and a maximum precision (how big the number can be).
To do this you simply calculate the modulus and remainder as long as you have particles left. You do not need to calculate a powers lookup table or any other trickery for this one. Here is an example:

#include <stdio.h>

int main () {

    unsigned int particles = 0, capacity = 0, chambers = 0, i = 0;

    if (3 != scanf ("%d %d %d", &particles, &capacity, &chambers))
        return fprintf (stderr, "Invalid input. Expect A N K\n");

    /* 
       For each chamber find the remainder with current capacity That
       is how many will be left. Divide remaining capacity and move to 
       next chamber. Stop when there are no more particles.
     */
    for (; i < chambers; ++i) {
        printf ("%d ", particles % (capacity + 1));
        particles /= (capacity + 1);
        if (! particles)
            break;
    }
    /* Remember to print all chambers not filled */
    while (++i < chambers) printf ("0 ");
    printf ("\n");

    return 0;
}

Often times with these challenges it is important to consider the real problem being asked (base-N in this case) and determine the easiest way to solve that. More often than not there is a simple solution that is hidden in the statement of the problem that makes the time limit trivial to avoid.

[nitin1]

it is the most easy problem i have seen in my coding carrier. here goes the solution ;'

#include<stdio.h>

int main()
{
    int a,k,n;

    scanf("%d%d%d",&a,&n,&k);

    while(k--)
    {
           printf("%d ",a%(n+1));
           a/=(n+1);
    }

    return 0;
}

feel free to ask doubts! thanks

[L7Sqr]

@nitin1:
I doubt that prakhs was looking for the solution outright. Explanation of how to derive the solution and, in general, how to approach these problems is a more meaningful response than what you provided. Certainly, if all that was required was a solution the site already provides that outright.

[nitin1]

okay! sory for that ! will not do this type of mistake in future!

@ L7Sqr Can you tell me what exactly that base-N problem you mean by ? please explain a little bit. I am eager to know a second approch of this question. The code i have provided is done by me just in 3 minutes after reading problem. way which you are telling is different from my approach ?

Secondly, can you tell what is base in this and please specify how you are relating this problem to base-N ? thanks ;)

[L7Sqr]

I was referring to the problem of converting a decimal number (the number of particles in this case) to a number in a different base (octal, hexidecimal, etc.). The base, in this problem, is provided by the number of particles that can be held in an individual chambers.
Here is another desccription of base conversion

[nitin1]

okay! after converting it then ? what is the next step it this ?

[prakhs]

I'm also not getting what do you mean by base-N problem?
Can some 1 please tell me what is the fault in my code ? why it exceeds time limit ?

[prakhs]

i got it how it is base-N problem.
But still i'm unable to find fault in my solution.

[L7Sqr]

I cant answer that; I am not the judge and I do not have the input that is causing the errors. Perhaps you could request the set of test inputs from the host. At that point you could check for yourself.