Connection Status:
Competition Arena > TheCoins

TheCoins

TCO11 Semifinal 2 · 2011-05-07 · by Vasyl[alphacom]

TCO11 Semifinal 2 · 2011-05-07 · by Vasyl[alphacom] · Math, Simple Search, Iteration
Class Name: TheCoins
Return Type: long
Method Name: find
Arg Types: (int, int, int, int, vector<int>, vector<int>)
Problem Statement

Problem Statement

John and Brus have n by m chessboard with rows numbered from 1 to n and columns numbered from 1 to m. Some cells may initially contain coins and some may be empty. In a single operation John choses an empty cell (r, c) such that cell (r+dr, c+dc) exists and is also empty, then John will place one coin on the cell (r, c) and Brus will place another one on the cell (r+dr, c+dc). They may perform this operation any number of times.

You are given ints n, m, dr and dc and int[]s row and column. The chessboard initially contains k coins, where k is the number of elements in row. The i-th coin is placed on the cell (row[i], column[i]). Return the maximal number of coins John and Brus can place on the chessboard (excluding those that are initially on the board). For example, if we have an empty 3 by 3 chessboard and dr=dc=1, then John and Brus can first place two coins at (1, 1) and (2, 2), another pair at (1, 2) and (2, 3) and then two more at (2, 1) and (3, 2) for a result of 6.

Constraints

  • n will be between 1 and 1,000,000,000, inclusive.
  • m will be between 1 and 1,000,000,000, inclusive.
  • dr will be between 1 and 1,000,000,000, inclusive.
  • dc will be between 1 and 1,000,000,000, inclusive.
  • row will contain between 0 and 50 elements, inclusive.
  • column will contain the same number of elements as row.
  • Each element of row will be between 1 and n, inclusive.
  • Each element of column will be between 1 and m, inclusive.
  • All pairs (row[i], column[i]) will be distinct.
Examples
0)
3
3
1
1
{}
{}
Returns: 6

The example from the problem statement.

1)
5
4
2
1
{3, 3}
{2, 3}
Returns: 10
2)
100
100
4
7
{}
{}
Returns: 9520
3)
2
2
1
1
{1, 2}
{2, 1}
Returns: 2
4)
7
8
6
7
{}
{}
Returns: 2

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

Coding Area

Language: C++17 · define a public class TheCoins with a public method long long find(int n, int m, int dr, int dc, vector<int> row, vector<int> column) · 172 test cases · 2 s / 256 MB per case

Submitting as anonymous