Connection Status:
Competition Arena > OddsandEvens

OddsandEvens

SRM 194 · 2004-05-15 · by dimkadimon

SRM 194 · 2004-05-15 · by dimkadimon · Math
Class Name: OddsAndEvens
Return Type: String
Method Name: find
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

Any integer is either odd or even. An even number is a number which divides by 2 without leaving any remainder. All other numbers are odd. We can create an arithmetic that deals with addition and multiplication of odd and even numbers. For example, the sum of two even numbers will also be an even number, but the sum of an odd and an even number must be an odd number. Here is the list of all possible sums and products in this arithmetic:

EVEN + EVEN = EVEN
EVEN + ODD = ODD
ODD + ODD = EVEN

EVEN * EVEN = EVEN
EVEN * ODD = EVEN
ODD * ODD = ODD

A list of integers is chosen. For each unique pair of numbers in the list we record their sum and product. Given the final contents of String[] sums and String[] products, where each element is either "ODD" or "EVEN", return the number of odd and even numbers in the original list. The corresponding elements in sums and products are NOT necessarily calculated from the same pair of numbers. Your return must be formatted as "EVEN <x> ODD <y>" where <x> is the number of evens and <y> is the number of odds. If the original list cannot be constructed then return "IMPOSSIBLE".

Constraints

  • sums will contain N(N-1)/2 elements where N is an integer between 2 and 10 inclusive.
  • products will contain the same number of elements as sums.
  • each element in sums will be either "ODD" or "EVEN".
  • each element in products will be either "ODD" or "EVEN".
Examples
0)
{"EVEN"}
{"ODD"}
Returns: "EVEN 0 ODD 2"

The only sum is even. Thus the two numbers are either both even or both odd. If the two numbers are both even then their product will also be even. This contradicts what we have in products. If the two numbers are both odd then their product will also be odd. This agrees with products. Thus there are two odd numbers.

1)
{"ODD"}
{"ODD"}
Returns: "IMPOSSIBLE"

If the sum is odd then one number is odd and the other is even. The product of an odd and even number is even. This contradicts products. Thus this is IMPOSSIBLE.

2)
{"EVEN","EVEN","EVEN"}
{"EVEN","EVEN","EVEN"}
Returns: "EVEN 3 ODD 0"

The sum and product of any two even numbers are always even. Here there are 3 even numbers.

3)
{"EVEN","ODD","ODD"}
{"ODD","EVEN","EVEN"}
Returns: "EVEN 1 ODD 2"

Two numbers are odd and one number is even. The two odd numbers give us one even sum and one odd product. The even number combined with the other two odd numbers gives two odd sums and two even products.

4)
{"EVEN","ODD","ODD","EVEN","ODD","ODD","EVEN","ODD","ODD","EVEN"}
{"ODD","EVEN","EVEN","ODD","EVEN","EVEN","ODD","EVEN","EVEN","EVEN"}
Returns: "EVEN 2 ODD 3"
20)
{"EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN"}
{"EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN"}
Returns: "EVEN 10 ODD 0"

10 even

21)
{"EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN"}
{"ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD"}
Returns: "EVEN 0 ODD 10"

10 odd

22)
{"ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN"}
{"ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","ODD","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN","EVEN"}
Returns: "EVEN 5 ODD 5"

5 odd 5 even

Submissions are judged against all 35 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class OddsAndEvens with a public method string find(vector<string> sums, vector<string> products) · 35 test cases · 2 s / 256 MB per case

Submitting as anonymous