11166 - Power Signs
Moderator: Board moderators
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
11166 - Power Signs
Is this problem related to BigInteger (because the input can be as large as 2^5000) ?
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
There is a greedy approach also.
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
replace consecutive 1's with +000..000- pattern from right to left except for the leftmost 11
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim
Try creating bruteforce solution for small inputs and test your greedy approach on it. You will find where's your mistake.
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim
Some Cases
Can anyone tells me this samples answer :
11101110111
1101101100
1010110101
11010101011
11111101111110111111
I got WA and my code's answer is :
+000-000-00-
+00-00-0-00
+0++0-0+0+
+00-0-0-0-0-
+000000-000000-00000-
If it's not true what is the true answer? And if it's true can anyone give me some other testcases?
11101110111
1101101100
1010110101
11010101011
11111101111110111111
I got WA and my code's answer is :
+000-000-00-
+00-00-0-00
+0++0-0+0+
+00-0-0-0-0-
+000000-000000-00000-
If it's not true what is the true answer? And if it's true can anyone give me some other testcases?
correct output is
Eventhough, ++0-0-0+0+ and +0++0-0+0+ has same number of zeros but former is
lexicographically smallest.
-pvncad
Code: Select all
+000-000-00-
+00-00-0-00
++0-0-0+0+
+00-0-0-0-0-
+000000-000000-00000-
lexicographically smallest.
-pvncad
-
- New poster
- Posts: 3
- Joined: Wed Apr 19, 2006 11:20 pm
WA aaaaaaah...
anyone can post some input/output?
I ve tried creating a program with brute force aproach test my heuristc, but it returns the same results.
I tried a greedy aproach, and it outputs the correct results for the sample input and for the one pvncad posted.
thx in advance
I ve tried creating a program with brute force aproach test my heuristc, but it returns the same results.
I tried a greedy aproach, and it outputs the correct results for the sample input and for the one pvncad posted.
thx in advance
Re: WA aaaaaaah...
Hello,eduardojmc wrote:anyone can post some input/output?
I ve tried creating a program with brute force aproach test my heuristc, but it returns the same results.
I tried a greedy aproach, and it outputs the correct results for the sample input and for the one pvncad posted.
thx in advance
Here are some testdata ,
Input
Code: Select all
1
10
11
100
111
1001
1111111
10101010000111111
1110101110101001111
11111111111110
1101010101010111111111
1100000001100010000000010110
101010101010101010101010101010
100000000000000000000000
1100000000000110000000000
111110111100111111000111111
110000000000110000000000000
0
Code: Select all
+
+0
++
+00
+00-
+00+
+000000-
+0+0+0+000+00000-
+000-0-00-0+0+0+000-
+000000000000-0
+00-0-0-0-0-0-00000000-
++000000+0-000+0000000+0-0-0
+0+0+0+0+0+0+0+0+0+0+0+0+0+0+0
+00000000000000000000000
++0000000000+0-0000000000
+00000-000-0+00000-00+00000-
++000000000+0-0000000000000
-
- New poster
- Posts: 7
- Joined: Sat Mar 10, 2007 7:03 pm
I think I am using the Greedy approach as described above. However, I got WAs.
Any tricky input or traps I am missing? Thanks.
Any tricky input or traps I am missing? Thanks.
Code: Select all
accepted