Codeforces #181 Div2 A "Array"
問題
http://codeforces.com/contest/300/problem/A
訳
ヴィタリーは互いに異なるn個の整数の配列を持っている。
ヴィタリーはこの配列を下記の決まりを守って、
3つの空でない配列に分割したいと思っている。
1. 1番目の配列の数値を全て掛け合わせたときに、負の数となること( < 0 ) 2. 2番目の配列の数値を全て掛け合わせたときに、正の数となること( > 0 ) 3. 3番目の配列の数値を全て掛け合わせたときに、0になること。 4 元の配列の各数値は、必ず3つの配列のどれか1つに含めること。
与えられた配列を3つの配列に分割し、出力せよ。
制約
3 <= 元の配列の要素数 <= 100
0 <= 元の配列の数値の絶対値 <= 1000
正しい答えは必ず存在する
考えた事
ルールを守った上で3つの配列に必ずわけられるということは、
与えられる元の配列は、
1. 必ず 0 を含む
2. 正の要素が必ず1つ以上あるか、負の要素が必ず3つ以上ある
という性質がある。
正の要素があった場合、
1... 負の数1つ
2... 正の数全部
3... その他
と分割し、
正の要素がなかった場合、
1... 負の数1つ
2... 負の数2つ
3... その他
と分割すればよい。
ソースコード
int N; int A[ 100 ]; int main() { cin >> N; bool existPos = false; // 正の数があったか? for( int i = 0; i < N; i++ ){ cin >> A[i]; if( A[i] > 0 ) existPos = true; } vector<int> a1; vector<int> a2; vector<int> a3; for( int i = 0; i < N; i++ ){ if( A[i] > 0 ){ a2.push_back( A[i] ); }else if( A[i] < 0 ){ if( !existPos && a2.size() < 2 ){ a2.push_back( A[i] ); }else if( a1.size() == 0 ){ a1.push_back( A[i] ); }else{ a3.push_back( A[i] ); } }else{ a3.push_back( A[i] ); } } printf( "%d ", a1.size() ); for( int i = 0; i < a1.size(); i++ ){ printf( "%d%c", a1[i], (i + 1 == a1.size() ? '\n' : ' ' ) ); } printf( "%d ", a2.size() ); for( int i = 0; i < a2.size(); i++ ){ printf( "%d%c", a2[i], (i + 1 == a2.size() ? '\n' : ' ' ) ); } printf( "%d ", a3.size() ); for( int i = 0; i < a3.size(); i++ ){ printf( "%d%c", a3[i], (i + 1 == a3.size() ? '\n' : ' ' ) ); } }