ProgrammingDevice | Topcoder Archive

Problem Statement

You work in a company that produces measuring devices. The software for each device is stored in reprogrammable memory. To program a device, you must connect it to a personal computer and transmit data to the device's reprogrammable memory through a serial interface. Your task is to make this process as efficient as possible.

You are given two int[]s offset and size. Each corresponding pair of elements in offset and size describes a piece of data that must be transmitted to the device. The i-th piece of data consists of size[i] consecutive bytes that must be written starting at the address in offset[i]. To successfully program a device, you must write every piece of the given data. Memory addresses that are not referenced in this data are not important - so you can write anything to those addresses, or write nothing at all to them.

Data is transmitted from the computer to the device through packets. Each packet can contain a maximum of maxData bytes of consecutive data that will be written to a specified memory address. Return the minimum possible total number of packets required to transmit all of the given data to the device.

Definition

Class:: ProgrammingDevice
Method:: minPackets
Parameters:: int[], int[], int
Returns:: int
Method signature:: int minPackets(int[] offset, int[] size, int maxData)
(be sure your method is public)

Notes

Assume that the reprogrammable memory of the measuring device is infinitely large.

Constraints

offset will contain between 1 and 50 elements, inclusive.
offset and size will contain the same number of elements.
Each element of offset will be between 0 and 1,000,000,000, inclusive.
Each element of size will be between 1 and 1,000,000,000, inclusive.
None of the pieces of data described by offset and size will overlap.
maxData will be between 1 and 2,000,000,000, inclusive.

Examples

```
{0, 10, 20, 30}
```
```
{8, 5, 3, 11}
```
```
6
```
```
Returns: 6
```
Send 15 bytes starting from offset 0 in 3 packets. Only 13 of those 15 bytes are meaningful. There are 2 dummy bytes starting from offset 8. Then, send 3 bytes starting from offset 20 in 1 packet. Finally, send 11 bytes starting from offset 30 in 2 packets. A total of 6 packets are sent.
```
{0, 10, 20, 30}
```
```
{8, 2, 3, 11}
```
```
6
```
```
Returns: 5
```
Send 12 bytes starting from offset 0 in 2 packets. Then, send 3 bytes starting from offset 20 in 1 packet. Finally, send 11 bytes starting from offset 30 in 2 packets. A total of 5 packets are sent.
```
{15, 95}
```
```
{1, 20}
```
```
100
```
```
Returns: 1
```

{77, 7777, 777}

{700, 70000, 7000}

Returns: 77700

{0,1000000000}

{1000000000,1000000000}

2000000000

Returns: 1

{0,1000000000}

{1000000000,1000000000}

Returns: 2000000000

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.