10705 - The Fun Number System

[htl]

Is there a good algo to solve it? I think brute force would take much time.

[abishek]

yes there is a very good algo.
think like they were just ordinary binary numbers.
just do a small modification for the negative ones.
bye

[htl]

You mean the posibits won't be modified whether we use ordinary or the 'Fun' system? Hmmm.... Let me take some time to figure out

[Observer]

Hint: think of the technique of "excess code".

[abishek]

hi,
i solved this problem. but i don't know what is "excess code". Can you give me some links to that? I'd like to learn that technique too.
bye
abi

[Observer]

Oops.. It's actually NOT a programming technique. It's just a way to store integers in computers......
(Sorry if I've caused confusion )

Check this out: http://library.thinkquest.org/26532/inside/coding/.

[abductor]

can anyone give me some test cases with answers for the problem. thanks

[hiloshi]

hi.
I got ACCEPT, and I'll give you test data.

here is input:

Code: Select all

36
4
ppnn
10
4
nnpp
-10
4
pppp
10
4
ppnn
6
1
p
1
9
pnppnnnnn
332
11
pppnppnnnnn
332
3
ppp
0
2
nn
-2
9
ppppppppn
255
20
pppnnppnnnnpppnpnppp
894632
1
n
0
1
p
0
1
p
1
1
n
-1
3
ppp
4
4
pppp
15
3
pnp
-1
3
pnp
3
50
pnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
1
50
pnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
-1
50
nppppppppppppppppppppppppppppppppppppppppppppppppp
-1
64
ppppnnnpnppnpnnnppppppppppnnnpnpppppnnnpnppnpnnnppppppppppnnnpnp
3254335264364654723
64
ppppnnnpnppnpnnnppppppppppnnnpnpppppnnnpnppnpnnnppppppppppnnnpnp
-980195823579238788
64
ppppnnnpnppnpnnnppppppppppnnnpnpppppnnnpnppnpnnnppppppppppnnnpnp
4363049762604363426
64
ppppnnnpnppnpnnnppppppppppnnnpnpppppnnnpnppnpnnnppppppppppnnnpnp
-1351135325723452455
4
pppp
16
4
ppnn
-10
3
pnp 
6 
4
nnnn
10
1
n
1
8
nppnnnnn
332
2
nn
2
4
pppn
15
2
pp
4
1
n
1

And my output

Code: Select all

1110
1110
1010
1010
1
101110100
00101110100
000
10
100000001
11101101101011111000
0
0
1
1
100
1111
011
111
11111111111111111111111111111111111111111111111111
00000000000000000000000000000000000000000000000001
11111111111111111111111111111111111111111111111111
0011010101010111101110001101001001011101100001010111000010000111
0000111001101011101001010110101110000101010001001110111010001100
0100010110110100101010101110010010011101011011101010111011100110
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible

Good luck!

[abductor]

thanks a lot

[krijger]

Do you guys all handle this correctly?

Code: Select all

Input:
2
64
nppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
-9223372036854775808
64
nppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
9223372036854775807

Code: Select all

Output:
1000000000000000000000000000000000000000000000000000000000000000
0111111111111111111111111111111111111111111111111111111111111111

It gave me some problems because (n+1)/2 or (n-1)/2 could give overflows. I used 'n/2+(n%2-1)/2' and 'n/2+(n%2+1)/2'.
Anybody else had problems with this? And is there a nicer way to do those calculations?

[Eduard]

I solve this problem without using such things.
I just use my proof that if we have K and some string of 'p'-s and 'n'-s than the maximum number(max) which we can give minus minimum number(min) =2^k-1.And all numbers between min and max we can give.

[abishek]

hi kriger,
i also first thought of those problems.
i handle them like this
n>>1; if the bit is a posibit
n>>1; n++; if the bit is a negabit
this will avoid all overflows
bye
abi

[anupam]

I didn't understand the algorithm or discussions. Excess code can help here. how? Please describe the algorithm you used to solve the problem.

[kisow]

hi hiloshi

one test data is not correct.

Code: Select all

64
ppppnnnpnppnpnnnppppppppppnnnpnpppppnnnpnppnpnnnppppppppppnnnpnp
-1351135325723452455
4

Code: Select all

1111010101000001110011011111010010001111110010111001110000101001

The weight of most significant negabit (1ULL << 59)
is 576460752303423488. So, it's "Impossible".

hi.
I got ACCEPT, and I'll give you test data.

here is input:

Code: Select all

36
4
ppnn
10
4
nnpp
-10
4
pppp
10
4
ppnn
6
1
p
1
9
pnppnnnnn
332
11
pppnppnnnnn
332
3
ppp
0
2
nn
-2
9
ppppppppn
255
20
pppnnppnnnnpppnpnppp
894632
1
n
0
1
p
0
1
p
1
1
n
-1
3
ppp
4
4
pppp
15
3
pnp
-1
3
pnp
3
50
pnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
1
50
pnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
-1
50
nppppppppppppppppppppppppppppppppppppppppppppppppp
-1
64
ppppnnnpnppnpnnnppppppppppnnnpnpppppnnnpnppnpnnnppppppppppnnnpnp
3254335264364654723
64
ppppnnnpnppnpnnnppppppppppnnnpnpppppnnnpnppnpnnnppppppppppnnnpnp
-980195823579238788
64
ppppnnnpnppnpnnnppppppppppnnnpnpppppnnnpnppnpnnnppppppppppnnnpnp
4363049762604363426
64
ppppnnnpnppnpnnnppppppppppnnnpnpppppnnnpnppnpnnnppppppppppnnnpnp
-1351135325723452455
4
pppp
16
4
ppnn
-10
3
pnp 
6 
4
nnnn
10
1
n
1
8
nppnnnnn
332
2
nn
2
4
pppn
15
2
pp
4
1
n
1

And my output

Code: Select all

1110
1110
1010
1010
1
101110100
00101110100
000
10
100000001
11101101101011111000
0
0
1
1
100
1111
011
111
11111111111111111111111111111111111111111111111111
00000000000000000000000000000000000000000000000001
11111111111111111111111111111111111111111111111111
0011010101010111101110001101001001011101100001010111000010000111
0000111001101011101001010110101110000101010001001110111010001100
0100010110110100101010101110010010011101011011101010111011100110
1111010101000001110011011111010010001111110010111001110000101001
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible

Good luck!

[/code]

[hiloshi]

hi kisow.

I edit my replay and fix my mistake.
Thanks for your sharp shooting.