Coffee Room

Discuss anything here - everything that you wish to discuss with fellow engineers.

12940 Members

Join this group to post and comment.

# 11th C++ problem

The Chef is planning a buffet for the Inauguration Party and everyone is invited. On their

way in, each guest picks up a sheet of paper containing a random number (this number may

be repeated). The guests then sit down on a round table with their friends.

The Chef now decides that he would like to play a game. He asks you to pick a random

person from your table and have them read their number out loud. Then, moving clockwise

around the table, each person will read out their number. The goal is to find that set of

numbers which forms an increasing subsequence. All people owning these numbers will be

eligible for a lucky draw! One of the software developers is very excited about this prospect,

and wants to maximize the number of people who are eligible for the lucky draw. So, he

decides to write a program that decides who should read their number first so as to

maximize the number of people that are eligible for the lucky draw. Can you beat him to it?

Input

The first line contains t, the number of test cases (about 15). Then t test cases follow. Each

test case consists of two lines:

The first line contains a number N, the number of guests invited to the party.

The second line contains N numbers a1, a2, ..., an separated by spaces, which are the

numbers written on the sheets of paper in clockwise order.

Output

For each test case, print a line containing a single number which is the maximum number of

guests that can be eligible for participating the the lucky draw.

Constraints

1 N 10000

You may assume that each number on the sheet of paper; ai is randomly generated,

i.e. can be with equal probability any number from an interval [0,U], where U is

some upper bound (1 U 106).

Example

Input:

32

0 0

3

3 2 1

6

4 8 6 1 5 2

Output:

1

2

4

Output details

Case 1: No matter where who reads there number first, just one person is eligible for the

lucky draw.

Case 2: The person in the last position could read their number first to obtain the sequence

1 3 2. We could then pick 2 sheets with numbers 1 and 2.

Case 3: The person in the fourth position could read their number first to obtain the

sequence 1 5 2 4 8 6. We could then pick 4 sheets with numbers 1 2 4 6

way in, each guest picks up a sheet of paper containing a random number (this number may

be repeated). The guests then sit down on a round table with their friends.

The Chef now decides that he would like to play a game. He asks you to pick a random

person from your table and have them read their number out loud. Then, moving clockwise

around the table, each person will read out their number. The goal is to find that set of

numbers which forms an increasing subsequence. All people owning these numbers will be

eligible for a lucky draw! One of the software developers is very excited about this prospect,

and wants to maximize the number of people who are eligible for the lucky draw. So, he

decides to write a program that decides who should read their number first so as to

maximize the number of people that are eligible for the lucky draw. Can you beat him to it?

Input

The first line contains t, the number of test cases (about 15). Then t test cases follow. Each

test case consists of two lines:

The first line contains a number N, the number of guests invited to the party.

The second line contains N numbers a1, a2, ..., an separated by spaces, which are the

numbers written on the sheets of paper in clockwise order.

Output

For each test case, print a line containing a single number which is the maximum number of

guests that can be eligible for participating the the lucky draw.

Constraints

1 N 10000

You may assume that each number on the sheet of paper; ai is randomly generated,

i.e. can be with equal probability any number from an interval [0,U], where U is

some upper bound (1 U 106).

Example

Input:

32

0 0

3

3 2 1

6

4 8 6 1 5 2

Output:

1

2

4

Output details

Case 1: No matter where who reads there number first, just one person is eligible for the

lucky draw.

Case 2: The person in the last position could read their number first to obtain the sequence

1 3 2. We could then pick 2 sheets with numbers 1 and 2.

Case 3: The person in the fourth position could read their number first to obtain the

sequence 1 5 2 4 8 6. We could then pick 4 sheets with numbers 1 2 4 6

69 views but not even single reply.

Come on Guys this is not that much tough as compared to 10th

or you guys are not interested to solve these

Come on Guys this is not that much tough as compared to 10th

or you guys are not interested to solve these

The sample input seems to be wrong.goyal420Example

Input:

32

0 0

3

3 2 1

6

4 8 6 1 5 2

Output:

1

2

4

Output details

Case 1: No matter where who reads there number first, just one person is eligible for the

lucky draw.

Case 2: The person in the last position could read their number first to obtain the sequence

1 3 2. We could then pick 2 sheets with numbers 1 and 2.

Case 3: The person in the fourth position could read their number first to obtain the

sequence 1 5 2 4 8 6. We could then pick 4 sheets with numbers 1 2 4 6

The first line should be 2, right? It is given as 32.

Also, please explain the output details. I couldn't get what you mean by the cases 1,2 and 3.

Thanks for giving attention ss

yes you are right it is

3

2

00

..

In all the cases the person with smallest no will read it's no first and then the next person in clock wise direction

so here The First case implies since there are two persons hence it is quite obvious that only one person is eligible for lucky draw

2 case:-here is it given 3 2 1 hence person at 3rd position will read its no first

and the sequence becomes 1 3 2 Now among these only those persons are valid which forms increasing sequence ie 1 2 .hence only two persons are valid for luck draw

3:-case same for this 4 8 6 1 5 2

the sequence will be 1 5 2 4 8 6

thus here persons for draw are 1 2 4 6 ie 4 hence output should be 4

yes you are right it is

3

2

00

..

In all the cases the person with smallest no will read it's no first and then the next person in clock wise direction

so here The First case implies since there are two persons hence it is quite obvious that only one person is eligible for lucky draw

2 case:-here is it given 3 2 1 hence person at 3rd position will read its no first

and the sequence becomes 1 3 2 Now among these only those persons are valid which forms increasing sequence ie 1 2 .hence only two persons are valid for luck draw

3:-case same for this 4 8 6 1 5 2

the sequence will be 1 5 2 4 8 6

thus here persons for draw are 1 2 4 6 ie 4 hence output should be 4

I get it now. I'll try to program it today..

so here is the solution for this

#include#include int getvalue(int a[],int b[],int ); int small(int a[],int); void main() { clrscr(); int n,i,j,count=1; int *store; cin>>n; store=new int[n]; int c[100],d[100]; for(i=0;i >b; c=new int[b]; d=new int[b]; store[i]=getvalue(c,d,b); delete []c; delete []d; } for(i=0;i >c[j]; } sm=small(c,b); for(i=0;i 0;i--) { if(d[i]>d[i-1]) { count++; } } for(i=0;i