First of all, I apologize for not posting during the entire last week. I do understand though that noone yet has stumbled across my blog and so I dont owe anyone any apology. C'mmon,get popular already blog. So, I promise I will be posting regularly from now on, atleast 3 questions per day.
My aim now is to come in the top 10 list of top coders of the week in spoj. For that, I have decided to solve every classical problem I face. I won't skip ANY question.
Coming to today's first question, http://www.spoj.com/problems/SBSTR1/
--------------------------------------------------------------------------------------------------------------------------
Allowed languages are Brainf**k,Whitespace and Intercal, so at the moment I am not eligible to solve this but like I mentioned previously, I will solve each of these questions, I won't leave any. So, naturally I will have to learn one of these languages which is a time taking process. Tommorrow is sunday, so I will write a post entirely on learning one of these languages and I will attach the link here. Also, I will solve this question as soon as I am comfortable with the new language.
I'm definitely going to learn brainf**k though because for starters, it sounds cool. Sorry for the lame post. Comment your compliments and complains.
Ok, so our next problem is loosely based on those sort of problems where we had to print all the prime numbers till first N numbers.
Here is the problem link, http://www.spoj.com/problems/PRIME1/
--------------------------------------------------------------------------------------------------------------------------
Lets take the problem bit by bit,one thing at a time.
INPUT:
First of all, we have to input the no. of test cases(t<=10). So, this part is easy.
Next, we have to enter two integers(1 <= m <= n <= 1000000000, n-m<=100000) separated by space for each test case, these two integers will be the extremities between which we have to find out the prime numbers.This input part is easy as well, take a loop while test case turns 0,keep on decrementing test case and input m & n for each test case till the loop ends. You will have to use arrays of m & n to make this work for obvious reasons. Make the array m[15],n[15] even though we need only m[10] & n[10], to avoid running into runtime error.
OUTPUT:
For the output part,we can use nested loops or functions. This will be a bit tricky. You got to try something like,start from m,then check from every integer starting from 1 and going on till?? m?. No, the trick here is that, if a given no. x is not divisible by 2 then if it is not a prime number ,then its factor will be less than x/2(because ofcourse,since 2 isnot a factor,so for no.s greater than or equal to x/2,they will have to be multiplied by a number y,so that x/2*y=x . Clearly, y won't be an integer). Hope you understand this. Lets try writing something by using it.
REMEMBER, using lots of nested loops increases time consumed by your code,using functions increases the size of your code.
TWEAKED FIRST & WORKING SOLUTION:-
#include <stdio.h>
int prime(int); --->Function prototype
int main()
{
int t,m[15],n[15],a,c=0; //like i mentioned above, arrays of m and n
scanf("%d",&t);
a=t;
while(a>0)
{
scanf("%d %d",&m[c],&n[c]); /*stores value of m and n for each test case*/
c++;
a--;
}
while(a<t)
{
while(m[a]<=n[a])
{
prime(m[a]);
m[a]++;
}
a++;
printf("\n");
}
return 0;
}
int prime(int n){int x=2,y=1,z;
z=n/y;
if(n==1) return n;
else if (n==2)
{printf("%d\n",n);return n;}
else {
while(x<z)
{
if(n%x==0) return n;
x++;
y++;
z=n/y;
}
printf("%d\n",n);
}
return n;
}
The rest of the code is pretty self explanatory. There may be parts which you didn't get. Please leave comments. I always have time for more questions.
Online with my first ever post, dont expect my blog to be all glittery and stuff. It is not gonna look good, for a while. So if the content or the topic interests you, please leave a comment.
Apparently, Im only going to try to solve classical problems in my initial few posts, I dont know why.
So let us start with the first problem http://www.spoj.com/problems/TEST/
--------------------------------------------------------------------------------------------------------------------------
Basic understanding says run a loop for input, stop taking the input when input is 42 and then print the output as it is except 42.
BUT, the sample input shows a user entered 99 after 42, so are we not supposed to stop taking the inputs after getting 42?? Ofcourse the question never says anything about when to stop taking inputs.
The time limit is 10s. We can simply make an array with INT_MAX holding capacity(what is the right term?) and we will stop taking inputs as soon as user enters 42 and to match the input of the Example provided, I will be using do while..so lets see, Honestly, I don't know if a[INT_MAX] will work as an array. But we all are learners here and a mistake never hurts.
First Attempt:-
#include <stdio.h>
#include <stdlib.h> ---->INT_MAX is part of this header
int main()
{
int a[INT_MAX],c=0,d=0;
do
{
scanf("%d",&a[c]); //taking inputs
c++;
}
while(a[c]!=42); //breaking at input=42.
while(d<c)
{
printf("%d\n",a[d]); //printing the remaining values.
d++;
}
return 0;
}
Apparently, putting a[INT_MAX] gives compilation error. But even after declaring a[100] or a[1000], compiler was giving me a runtime error. What is wrong with the above program??
A very small mistake which I made was with the "DO" portion. Suppose, the user inputs value 36 and it is stored in a[3],suppose. We then do c++ ,and the while checks whether a[4]= 42 or not. Which means,practically,this is an infinite loop. To fix this, we can write while(a[c-1]!=42) . There are a lot of different solutions anyways from hereon.
FIXED SOLUTION:-
#include <stdio.h>
int main()
{
int a[1000],c=-1,d=0;
do
{
c++;
scanf("%d",&a[c]);
}
while(a[c]!=42);
while(d<c)
{
printf("%d\n",a[d]);
d++;
}
return 0;
}
I do understand that this was one easy problem but upcoming problems will be a bit tricky, hope so. Please leave comments or complains.
