Connection Status:
Competition Arena > ProgrammingDevice

ProgrammingDevice

SRM 367 · 2007-09-26 · by gevak

SRM 367 · 2007-09-26 · by gevak · Greedy
Class Name: ProgrammingDevice
Return Type: int
Method Name: minPackets
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

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.

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)
{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.

1)
{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.

2)
{15, 95}
{1, 20}
100
Returns: 1
3)
{77, 7777, 777}
{700, 70000, 7000}
1
Returns: 77700
4)
{50,10}
{100, 35}
7
Returns: 20

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

Coding Area

Language: C++17 · define a public class ProgrammingDevice with a public method int minPackets(vector<int> offset, vector<int> size, int maxData) · 108 test cases · 2 s / 256 MB per case

Submitting as anonymous