even position

John3682 (85)
the original assignment :

One of the members of the delegation came forward on behalf of the others and, without any explanation, selected the people who were in the even position and formed a new line with them. Then, in the new queue, as before, he selected the people who were in the even position and continued this process until only one person remained.


The first line is a natural number (n) that determines the number of rows . In the next (n) line, each line contains a natural number (m) that specifies the number of people in the corresponding row.

1 <= n <= 1000
1 <= m <= 100000000

The output of your program should include (n) lines, in each line, the last person's position number is printed.


io examples :

i :

1
5

o :

4

------------
i :

5
11
10
19
1
7

o :

8
8
16
1
4

---------------------

i think it should be solved like this

1 = numbers that theyre going to enter / row
5 = entered number / people in the row

1
2 --- 1
3
4 --- 2 ---- last person that stands in even position
5

cout << 4 ; cuz he was the 4th person in the original line

or if the input was :

1
10


1
2 --- 1
3
4 --- 2 --- 1
5
6 --- 3
7
8 --- 4 --- 2 <== it should cout << 8 ;
9
10 --- 5

ty in advance

***UPDATE :

so i tried somethings but i cant make it show the origin of the narrowed number i dont know how to trace it back to its origin

(it says that i should use recursive function in order to show trace the number and print it but im really bad at recursion)
Last edited on
lastchance (6980)
Well, in your two examples the originals were 4, 8, ... and if you'd tried something a little bigger you would get 16. Notice anything?
John3682 (85)
hey , thank you for answering

i dont know the specific numbers i just know that

1 <= n <= 1000
1 <= m <= 100000000

so the input could be 19 - 15 - 11 or any other odd number ,
lastchance (6980)
The answers would be one of 1, 2, 4, 8, 16, 32, ...
So, do you not notice something?
thmm (703)
@lastchance
Not so easy to put in words.
Maybe the next lower power of two?
Solution would be sth. like
while not power_of_two(m)
m--
lastchance (6980)
C'est ça!

1
2
3
4
5
6
 
nextLowerPowerOf2( int m )
{
   int ans = 1;
   while ( m /= 2 ) ans *= 2;
   return ans;
}
John3682 (85)
@LASTCHANCE ty for helping ure a life saver; )

it worked with this :


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
#include <iostream>
#include <cmath>

using namespace std;
#define A 1000
int main()
{
	int n,m,c,h;
	int Y[A];
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> m;

		for (int j = 1; j <= m; j++)
		{
			h =pow(2,j);

			if (h <= m)
			{
				c = h;
			}
			else
			{
				Y[i] = c;
				c = 1;
				break;
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		cout << Y[i] << endl;

	}
}



i just have one last question , is there a more sufficient/shorter way to write this that could reduce execution time ?
Last edited on
lastchance (6980)
Err, why don't you use the function I wrote for each value of m?
John3682 (85)
hahaha , i just saw ur code , i send mine before refreshing and didnt look up


is it the way it suppose to be written :?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
#include <iostream>
#include <cmath>

using namespace std;
#define A 1000
int nextLowerPowerOf2(int);

int main()
{
	int n,m,c,h;
	int Y[A];
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> m;
		Y[i] = nextLowerPowerOf2(m);
	}

	for (int i = 1; i <= n; i++)
	{
		cout << Y[i] << endl;

	}
}
int nextLowerPowerOf2(int m)
{
	int ans = 1;
	while (m /= 2) ans *= 2;
	return ans;
}
lastchance (6980)
You don't need Y[], or two separate for loops.

Just output the result as soon as you calculate it. (i.e. you could put it within the cout statement).

You can also make the program run fractionally faster by replacing endl by '\n', so avoiding flushing the output buffer at every single output.
John3682 (85)
i cant cout every m after taking it , i need to take all the m`s and then cout them all after taking all the m inputs

if the input is :

5

11
10
19
1
7

i cant cout :

11
8

10
8

19
16

1
1

7
4
lastchance (6980)
I can't really see you sitting at the keyboard and entering n=1000 lines of data either. It's probably re-directed from a file.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
#include <iostream>
#include <sstream>
using namespace std;

int nextLowerPowerOf2( int m )
{
   int ans = 1;
   while ( m /= 2 ) ans *= 2;
   return ans;
}

int main()
{
   stringstream in( "5 \n"
                    "11\n"
                    "10\n"
                    "19\n"
                    "1 \n"
                    "7 \n" );
   int m, n;
   in >> n;
   while( n-- )
   {
      in >> m;
      cout << nextLowerPowerOf2(m) << '\n';
   }
}
 
8
8
16
1
4
Topic archived. No new replies allowed.