Thread: SPOJ problem.

    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    2
    Rep Power
    0

    SPOJ problem.


    I have been trying to solve this problem for a while.

    http://www.spoj.com/problems/NDIGITS/

    It is very simple yet the judge doesnt seem to approve my solution. Here is the code.


    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    void contador(short t[], int n)
    {
    int i;

    t[0]=9;

    for (i=0; i<n;i++)
    t[i+1]=0;

    }


    int main()
    {
    int n , i , d , m;
    short t[9999];

    scanf("%d",&n);

    for(i=0;i<n;i++)
    {
    scanf("%d",&d);

    if(d==1)
    printf ("%d", 10);

    else
    {
    contador(t, d);
    for (m = 0; m < d; m++)
    printf("%d", t[m]);
    }


    }

    printf("\n");

    system("PAUSE");

    return 0;
    }



    Code:
    #include <stdio.h> #include <stdlib.h> #include <string.h> void contador(short t[], int n) { int i; t[0]=9; for (i=0; i<n;i++) t[i+1]=0; } int main() { int n , i , d , m; short t[9999]; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&d); if(d==1) printf ("%d", 10); else { contador(t, d); for (m = 0; m < d; m++) printf("%d", t[m]); } } printf("\n"); system("PAUSE"); return 0; }
    Hopefully you will know better than i do because im really getting desperate.

    Thanks for your help in advance.

    Edited for easy code presentation. First time making a thread and i got really impatiencie so im not sure how are the codes supposed to be presented.
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,379
    Rep Power
    1871
    You should edit (and then preview) your post so the code isn't all on one line.

    Then others might be more inclined towards reading it.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  4. #3
  5. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,379
    Rep Power
    1871
    You were on the right track the first time.
    All you needed to do was fix the newline issue.

    However, perhaps you could explain why filling an array with 9 and then a whole bunch of zeros goes towards solving the problem at hand.

    I hope you didn't leave the system("pause") in there when you uploaded it, because that's an instant fail for any automated tests.

    Speaking of tests, what tests did you do (or did you just upload and hope).

    The first line of input consists of an integer t denotes the number of testcases. Then for the next t lines each line consists of an integer n.
    Output
    For each n output the number of n-digit whole numbers.
    So for example, did you prepare a text file containing say

    5
    1
    2
    3
    4
    5

    Do you even know what the answers are supposed to be?
    Why did you make the example (on the webpage) a special case?

    For example, if the input were two, then the answer would be 90.
    That is, if you count from 0 to 100, then only 10 to 99 satisfy the input criteria of having only two digits.

    Input Specification:
    1<=t<=100
    1<=n<=1000
    You need to think smarter than just trying to fill an array.
    A 1000 digit number will NOT fit in any standard data type, and simply counting them is a non-starter. Even the fastest machines on earth cannot even count to 1E10 within a second, so 1E1000 is well into the lifespan of the universe territory.

    Study the pattern and work out the algorithmic solution (or algebraic solution).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    2
    Rep Power
    0
    Originally Posted by salem
    You were on the right track the first time.
    All you needed to do was fix the newline issue.

    However, perhaps you could explain why filling an array with 9 and then a whole bunch of zeros goes towards solving the problem at hand.

    I hope you didn't leave the system("pause") in there when you uploaded it, because that's an instant fail for any automated tests.

    Speaking of tests, what tests did you do (or did you just upload and hope).


    So for example, did you prepare a text file containing say

    5
    1
    2
    3
    4
    5

    Do you even know what the answers are supposed to be?
    Why did you make the example (on the webpage) a special case?

    For example, if the input were two, then the answer would be 90.
    That is, if you count from 0 to 100, then only 10 to 99 satisfy the input criteria of having only two digits.


    You need to think smarter than just trying to fill an array.
    A 1000 digit number will NOT fit in any standard data type, and simply counting them is a non-starter. Even the fastest machines on earth cannot even count to 1E10 within a second, so 1E1000 is well into the lifespan of the universe territory.

    Study the pattern and work out the algorithmic solution (or algebraic solution).
    Simple. The only way you cna make sure that there are n-digit number is by counting, the problems comes when you cannot count number that have above 50 digits(a lot more) or even less.

    The problems itselfs tells you that the amount of digit can go from 1 to 10000 and there isnt any way to store such a large number but with an array, ergo the array of 10000 spaces.

    So by simple logic you make a conclusion to make things easier. from 10 to 99 there are 90 numbers (89 if you exclude 10) so for obvious reason from 100 to 999 (3 didigits number) there will be 900 numbers. This will go on for pretty much the same every single amount of digits, yet the only amount that differs is from 0 to 9 (which is 10).

    I made an array that will be filled for an x amount of 0s depending on how many digits and will print.

    I didnt leave the system ¨pause¨, just in case.

    I made different test, including the example one. Specially i was running my program along with another one that ¨passed¨the judge. Both, mine and the other, did the same thing but differently.

    Mines output is number by number, while the other one is the full array.

    i made a mistake with the maximun limit of digits, it is supposed to be 999 not 9999.

    Two last thing, im not sure what you meant newline issue. Probably i know what it is but in the language i was taught (spanish), and i appreaciate the help but the way you replied made it look like i had no idea of what i was doing(Cant say im totally sure after all it was just recently since i started programming).

    Nevermind the newline issue, looked it up and as you said that is the problem (And the difference from my program to the other), yet i cant seem to just fix it. tried forcing it with the last print but it didnt work. Im currently trying to just print the whole array instead of just ¨space by space¨ but im having difficulties.

    Edit:

    I modified it a little so it matches with the input and output.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    void contador(short t[], int n)
    {
    int i;

    if(n==1)
    t[0]=10;
    else
    {
    t[0]=9;

    for (i=0; i<n;i++)
    t[i+1]=0;
    }
    }


    int main()
    {
    int n , i , d , m;
    short t[999];

    scanf("%d",&n);

    for(i=0;i<n;i++)
    {
    scanf("%d",&d);

    contador(t, d);

    for (m = 0; m < d; m++)
    printf("%d", t[m]);


    printf("\n");



    }


    return 0;
    }



    Like this there musnt be a ny troubles with the new lines yet the judge still doesnt approve. I believe it might have to do with the way the output works.
  8. #5
  9. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,379
    Rep Power
    1871
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper

IMN logo majestic logo threadwatch logo seochat tools logo