10232 - Bit-wise Sequence

Caesum · Post by **Caesum** » Sat May 18, 2002 9:38 pm

Can someone explain this problem to me please ? It gives the sample input and output:

Sample Input
0
1
2
31
32

Sample Output
0
1
2
1073741824
3

Shouldnt the sequence be 0,1,2,4,8,16,32,3,5,6,9,.....
in which case 32 is 6th and not 3rd as in the sample ? and 31 would not be that far in to the sequence....... Or am I completely misunderstanding this ?

Ivan Golubev · Post by **Ivan Golubev** » Sat May 18, 2002 10:14 pm

Looks like you've exchanged input and output -- the 31th number of sequence is 1073741824, the 32nd number is 3, etc.

ithamar · Post by **ithamar** » Mon Sep 16, 2002 6:03 am

I dont understan the input - output for this problem. Can anybody explain me why the number 1073741824 is the number 31 in the sequence (not 30 as i believe that should be).

I believe that all the numbers in the sequence between 1 and 30 are 1, 2, 4, 8, 16, 32, .... , 1073741824. But in this way 1073741824. is the number 30 not 31. What is wrong about my reasoning.

Thanxs in advance.

Adrian Kuegel · Post by **Adrian Kuegel** » Mon Sep 16, 2002 12:40 pm

If you use this sequence, the 30th number is 536870912, the 31th number is 1073741824. Perhaps generate you a list with a program, you will see it.

solver · Post by **solver** » Mon Oct 28, 2002 7:25 pm

umm... I'm feeling quite clueless attempting this problem.

solver · Post by **solver** » Sat Nov 02, 2002 2:08 am

I've been thinking about 10232 (Bitwise Sequence), and the only way I could think of doing it was to

Taking 2 to be the only prime number with one 1 in its bin. representation,

1. generate all combinations of two 1s (with 1 in the last placeholder, as even numbers are not to be checked), and check them for primality.
2. Do the same for three 1s, four 1s, .. and so on, UNTIL we get the Nth prime number.

This approach is basically trying all combinations (serialwise however), and doesn't seem quite right if the time limit is less.

Is there any obvious number theory trick I'm missing ( a hint will do ). At least someone can confirm if I'm on the right track?

Thanks

solver · Post by **solver** » Wed Nov 13, 2002 3:01 pm

Ulan Degenbayev wrote:How did you attached primes to this problem?
May be you have mixed up some problems?

You are right. I mixed up this problem with another one I saw. And misreading this one, I assumed one has to form a list of prime numbers in ascending order of B(n). That was confusing me a lot.

Now that the question is clear to me, the solution seems straightforward. Thanks.

Shahab · Post by **Shahab** » Sun Sep 28, 2003 8:53 am

Hi everybody,

I have solved the problem #10232, but I got WA for it. It solves the sample input and my samples in the right way and I really can't understand the problem behind it.

Can anyone give me some sample input and output plz?

Thanks in advance,
Shahab Tasharrofi

Larry · Post by **Larry** » Sun Sep 28, 2003 9:49 am

Pretty much random:

Input:

Code: Select all

Output:

Code: Select all

Shahab · Post by **Shahab** » Sun Sep 28, 2003 10:30 am

Thanks for your inputs Larry, but altough it can solve them in the right way, i got WA another time

, I'm really getting disappointed of this problem

Shahab Tasharrofi

Shahab · Post by **Shahab** » Sun Sep 28, 2003 10:35 am

ok, let me put my code here, I'll be graceful if you could have a brief look at it :

[pascal]
program P10232;
type Int=LongInt;
var A:array [-1..31,-1..31] of Int;
Bit:array [0..31] of Byte;
function Solve(n:Int):Int;
var i,b,k:Int;
begin
i:=0;
while n>=0 do
begin
n:=n-A[31,i];
Inc(i);
end;
Dec(i);
n:=n+A[31,i];
b:=31;
repeat
if n>=A[b-1,i] then
begin
n:=n-A[b-1,i];
Bit:=1;
Dec(i);
end
else
begin
Bit:=0;
end;
Dec(b);
until b<=0;
for i:=31 downto 1 do
k:=k shl 1+Bit;
Solve:=k;
end;
var i,j,n,k:Int;
begin
A[-1,0]:=0;
A[-1,-1]:=0;
for i:=0 to 31 do
begin
A[i,-1]:=0;
A[i,0]:=1;
for j:=1 to i-1 do
A[i,j]:=A[i-1,j-1]+A[i-1,j];
A[i,i]:=1;
end;
while not Eof(Input) do
begin
ReadLn(n);
k:=Solve(n);
WriteLn(k);
end;
end.
[/pascal]

daveon · Post by **daveon** » Wed Aug 02, 2006 7:23 pm

Hi,

I do not know pascal but here are some boundary IO's:

input:

Code: Select all

output:

Code: Select all

Bunda001 · Post by **Bunda001** » Sun Jan 06, 2008 11:57 am

Hi, i would need that program - can someone please send here solved program in C++? thank you very much... or can send on Bunda001@seznam.cz

OJ Board

10232 - Bit-wise Sequence

10232 - Bit-wise Sequence

10232 -- is this the method?

10232 - Bit-wise sequence