Codeforces: 300A. Array

It looks like it has been a while since last time I submitted code to codeforces. I almost forgot the fun of solving problems. Again, I choose solving easy problems, that reminds me of the fun of  coding in Python.

The problem is tagged ‘brute-force’, but in my opinion, it is not necessary. algorithm is enough. First, you do need to categorize the numbers by negatives, zero and positives. The problem specifies that at least one solution exists, therefore, there must be at least one zero; there must be at least one negative. If there is non-zero, the multiplication will never be zero; if there is non-negatives, the multiplication result will again never be zero.

If there is non-positive, you need to move two negatives to the list of positives, because the product of two negatives is positive. If there is odd number of negatives, then simply print the three lists, otherwise, move one negative to the zero-list, because the zero times any number still yield zero.

#!/usr/bin/env python

n = int(raw_input())
a = map(int, raw_input().split())

s1 = [i for i in a if i < 0] 
s2 = [i for i in a if i > 0]
s3 = [i for i in a if i == 0]

def pr(x):
    print len(x), " ".join(map(str, x))

if len(s2) == 0:
    s2.append(s1.pop())
    s2.append(s1.pop())

if len(s1) % 2 == 0:
    s3.append(s1.pop())

pr(s1)
pr(s2)
pr(s3)

We here use the list comprehension to group the numbers, of course, it is the same as the below, but this python method looks more elegant.

for x in a:
  if x < 0:      
    s1.append(x)   
  elif x > 0:
    s2.append(x)
  else:
    s3.append(x)

The output string is connected by the join operation, the push and pop methods are done via append and pop in Python respectively.

The other solution is to sort the input, which results array from negatives to positives.

input()
a=map(int,raw_input().split())
a.sort()
a1=[a.pop(0)]
a2=a[-1]>0 and [a.pop()] or [a.pop(0),a.pop(0)]
for x in a1,a2,a:
    print len(x),' '.join(map(str,x))

–EOF (The Ultimate Computing & Technology Blog) —