320SC程序代做、代写Java，c/c++编程

日期：2023-09-05 10:06

Computer Science 320SC – (2023)

Programming Assignment 3

Due: Friday Sept 1st or Friday Sept 8th (11:59pm)

Requirements

This assignment tests you understanding of how to apply network flow to a real-world application. We

have taken a recent New Zealand Programming Contest question and repackaged it for your requirements. See the following two pages for specifications.

Submission

There will problem two sets of inputs Easy and Hard worth 3 and 2 marks, respectively, on the computer

science automarker https://www.automarker.cs.auckland.ac.nz/. It is expected that you will need

a network flow solution for the harder test case.

For this assignment you can use any language supported on the automarker and can submit up to

10 times for each problem before occuring a 20% penalty. Then a maximum of 20 times to prevent

overloading of the server.

Also, as a bonus, if you finish both parts of the assignment before the first deadline of Sept 1st, you will

get 10% added to your Assignment 3 score (e.g. 5.5 marks), which will be manually added to Canvas.

You need to have solved both test sets to qualify.

1

NZPC2023 MOLECULES

Organic molecules can be amazingly complex and need a great

variety of shapes and conventions to represent them,

particularly if we wish to depict details of their 3-dimensional

structures. For this problem, we will restrict ourselves to

reasonably simple compounds with only single bonds between

atoms, that can be represented on a simple rectangular grid

with bonds aligned horizontally or vertically. In such molecules,

carbon is bonded to 4 adjacent atoms, nitrogen to 3, oxygen to

2 and hydrogen to 1. These numbers are called the valences of

the atoms.

Of course, not all such grids represent valid molecules. Your task is to write a

program that will determine whether a given grid could represent one or more valid

molecules, satisfying the valences of all the atoms. Note that the molecule(s) in a

valid grid do not need to exist in the real world.

Input

The first line of the input consists of a pair of integers (r and c, 1 ≤ r, c ≤ 20) representing

the number of rows and columns in the rectangle to follow. The next r lines contain c

characters each, where the characters are chosen from the set {‘H’, ‘O’, ‘N’, ‘C’, ‘.’}

representing hydrogen, oxygen, nitrogen, carbon and ‘empty’, respectively.

Output

Output consists of a single line containing a single word:

Valid if it possible to draw horizontal and/or vertical bonds between

neighbouring atoms so as to satisfy the valences of all the atoms in the grid, or

Invalid if no such set of bonds exists.

New Zealand Programming Contest 2023

Sample Input #1

3 4

HOH.

NCOH

OO..

Output for Sample Input #1

Valid

Explanation

A valid bonding is:

H O—H

| |

N—C—O—H

| |

O—O

Sample Input #2

3 4

HOH.

NCOH

OCNH

Output for Sample Input #2

Invalid

Sample Input #3

2 3

HOH

HOH

Output for Sample Input #3

Valid

Explanation

This could represent two water

molecules:

H—O—H

H—O—H

Sample Input #4

4 10

OOOONOOOOO

OOOOHOOOOO

OOOHNHHOOO

OOOOOOOOOO

Output for Sample Input #4

Invalid