anon10020
01-07-2012, 09:25 PM
Hello Sir,
This is the question:
"The aliens living in outer space are very advanced in technology, intelligence and everything, except one, and that is Cooking. Each year they spend millions of dollars in research, to crack famous recipes prepared by humans.
Recently they came to know about Khana-Academy, a non-profit organization streaming free cooking lesson videos on earth. There are N recipes, numbered 1 to N, and the video of the ith recipe is live in the time interval [Si, Ei]. An alien can visit earth but can not survive for more than just a small moment (earth is so advanced in pollution). An alien visits the earth at an integer time t and instantly downloads the complete video of all the lessons that are live at that moment of time t and leaves earth immediately. You are given the visiting times of a small group of K aliens. Find the number of different recipes aliens can learn by watching the downloaded videos. Not just one group of aliens, there are Q such groups, so you have to find the answer for each of these Q groups.
Input
The first line has an integer N. Each of the following N lines has two integers Si Ei. The next line has an integer Q, the number of groups. Each of the following Q lines has information of a group of aliens. The first integer is K, the number of aliens in that group, followed by K integers in the same line, the integer visiting times t of the aliens.
1 ≤ N ≤ 100000 (105)
1 ≤ Q ≤ 5000 (5 ·103)
1 ≤ K ≤ 20
1 ≤ Si, Ei, t ≤ 1000000000 (109)
Si < Ei
Output
For each of the Q groups, output the number of different recipes that group of aliens can learn by watching the downloaded videos.
Example
Input:
4
1 4
3 10
2 6
5 8
3
1 5
2 2 6
3 1 10 9
Output:
3
4
2
Explanation:
Given videos of 4 recipes in the following closed intervals.
1. [ 1 , 4 ]
2. [ 3 , 10 ]
3. [ 2 , 6 ]
4. [ 5 , 8 ]
In the first query, only one alien arrives at t = 5 and can download 3 recipes 2, 3, 4.
In the second query, two aliens arrive at t = 2 and 6. They can learn all the 4 recipes.
In the third query, three aliens arrive at t = 1, 10 and 9. They can learn only two recipes, 1 and 2."
I am pasting my code. It is compiled on gcc on my home CentOs 5.5 .
#include<stdio.h>
#include<stdlib.h>
int main()
{
int N, Q, K[20], i, j, k ,count[100000];
long long S[100000], E[100000], t[5000][20];
// printf("Enter the no. of recipies N (b/w 1 and 100000)\n");
scanf("%d", &N);
if(N<1 || N>100000)
exit(0);
for(i=1; i<=N; i++)
{
// printf("Enter the value of S%d and E%d for %d recipe\n", i ,i ,i);
scanf("%lld %lld", &S[i], &E[i]);
if(S[i]<1 || E[i]<1 || S[i]>1000000000 || E[i]>1000000000)
exit(0);
}
// printf("Enter Number of Groups Q of Aliens coming (b/w 1 and 5000)\n");
scanf("%d", &Q);
if(Q<1 || Q>5000)
exit(0);
for(i=1 ; i<=Q; i++)
{
// printf("Enter number of members K(b/w 1 and 20) in %dth group", i);
scanf("%d", &K[i]);
if(K[i]<1 || K[i]>20)
exit(0);
for(j=1;j<=K[i]; j++)
{
// printf("Enter time to live t of %d th member of %dth group\n", j, i);
scanf("%lld", &t[i][j]);
if(t[i][j]<1 || t[i][j]>1000000000)
exit(0);
}
}
for(i=1; i<=Q; i++)
{
printf("%d Group can download ", i);
for(j=1; j<=K[i]; j++)
{
for(k=1; k<=N; k++)
{
if(t[i][j] < S[k] || t[i][j] > E[k])
continue;
printf("%d, ", k);
count[k]=k;
}
/* for(k=1; k<=N; k++)
{
for(l=1; l<=N; l++)
{
if(count[k]==count[l] && k!=l)
{
if(k <l)
count[l]
}
*/
}
printf("recipies\n\n");
}
return(0);
}
I am get redundancies in my result. I tried but unable to get proper logic, to how to implement it.
Please show some light on it!
Thank You,
Anon10020
This is the question:
"The aliens living in outer space are very advanced in technology, intelligence and everything, except one, and that is Cooking. Each year they spend millions of dollars in research, to crack famous recipes prepared by humans.
Recently they came to know about Khana-Academy, a non-profit organization streaming free cooking lesson videos on earth. There are N recipes, numbered 1 to N, and the video of the ith recipe is live in the time interval [Si, Ei]. An alien can visit earth but can not survive for more than just a small moment (earth is so advanced in pollution). An alien visits the earth at an integer time t and instantly downloads the complete video of all the lessons that are live at that moment of time t and leaves earth immediately. You are given the visiting times of a small group of K aliens. Find the number of different recipes aliens can learn by watching the downloaded videos. Not just one group of aliens, there are Q such groups, so you have to find the answer for each of these Q groups.
Input
The first line has an integer N. Each of the following N lines has two integers Si Ei. The next line has an integer Q, the number of groups. Each of the following Q lines has information of a group of aliens. The first integer is K, the number of aliens in that group, followed by K integers in the same line, the integer visiting times t of the aliens.
1 ≤ N ≤ 100000 (105)
1 ≤ Q ≤ 5000 (5 ·103)
1 ≤ K ≤ 20
1 ≤ Si, Ei, t ≤ 1000000000 (109)
Si < Ei
Output
For each of the Q groups, output the number of different recipes that group of aliens can learn by watching the downloaded videos.
Example
Input:
4
1 4
3 10
2 6
5 8
3
1 5
2 2 6
3 1 10 9
Output:
3
4
2
Explanation:
Given videos of 4 recipes in the following closed intervals.
1. [ 1 , 4 ]
2. [ 3 , 10 ]
3. [ 2 , 6 ]
4. [ 5 , 8 ]
In the first query, only one alien arrives at t = 5 and can download 3 recipes 2, 3, 4.
In the second query, two aliens arrive at t = 2 and 6. They can learn all the 4 recipes.
In the third query, three aliens arrive at t = 1, 10 and 9. They can learn only two recipes, 1 and 2."
I am pasting my code. It is compiled on gcc on my home CentOs 5.5 .
#include<stdio.h>
#include<stdlib.h>
int main()
{
int N, Q, K[20], i, j, k ,count[100000];
long long S[100000], E[100000], t[5000][20];
// printf("Enter the no. of recipies N (b/w 1 and 100000)\n");
scanf("%d", &N);
if(N<1 || N>100000)
exit(0);
for(i=1; i<=N; i++)
{
// printf("Enter the value of S%d and E%d for %d recipe\n", i ,i ,i);
scanf("%lld %lld", &S[i], &E[i]);
if(S[i]<1 || E[i]<1 || S[i]>1000000000 || E[i]>1000000000)
exit(0);
}
// printf("Enter Number of Groups Q of Aliens coming (b/w 1 and 5000)\n");
scanf("%d", &Q);
if(Q<1 || Q>5000)
exit(0);
for(i=1 ; i<=Q; i++)
{
// printf("Enter number of members K(b/w 1 and 20) in %dth group", i);
scanf("%d", &K[i]);
if(K[i]<1 || K[i]>20)
exit(0);
for(j=1;j<=K[i]; j++)
{
// printf("Enter time to live t of %d th member of %dth group\n", j, i);
scanf("%lld", &t[i][j]);
if(t[i][j]<1 || t[i][j]>1000000000)
exit(0);
}
}
for(i=1; i<=Q; i++)
{
printf("%d Group can download ", i);
for(j=1; j<=K[i]; j++)
{
for(k=1; k<=N; k++)
{
if(t[i][j] < S[k] || t[i][j] > E[k])
continue;
printf("%d, ", k);
count[k]=k;
}
/* for(k=1; k<=N; k++)
{
for(l=1; l<=N; l++)
{
if(count[k]==count[l] && k!=l)
{
if(k <l)
count[l]
}
*/
}
printf("recipies\n\n");
}
return(0);
}
I am get redundancies in my result. I tried but unable to get proper logic, to how to implement it.
Please show some light on it!
Thank You,
Anon10020