Connection Status:
Competition Arena > DeviceProgramming

DeviceProgramming

SRM 367 · 2007-09-26 · by gevak

SRM 367 · 2007-09-26 · by gevak · Dynamic Programming, Simple Math
Class Name: DeviceProgramming
Return Type: long
Method Name: minBytes
Arg Types: (vector<int>, vector<int>, 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 contains a consecutive piece of data that will be written to a specified memory address. Each packet must also include overhead bytes of various overhead information (like a packet header, the destination address, checksum, etc.). The size of one packet (including the overhead information) can not be more than maxPacketSize bytes. Return the minimum possible total number of bytes 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.
  • overhead will be between 1 and 999, inclusive.
  • maxPacketSize will be between overhead + 1 and 1000, inclusive.
Examples
0)
{0, 42, 60}
{40, 15, 2}
26
6
Returns: 78

Send 40 bytes starting from offset 0 in 2 packets (26 * 2 = 52 bytes). Then, send 20 bytes starting from offset 42 in 1 packet (26 bytes). Only 17 of those 20 bytes are meaningful. There are 3 dummy bytes starting from offset 57. A total of 78 bytes are sent.

1)
{0, 42, 60}
{40, 15, 13}
26
6
Returns: 92

Send 40 bytes starting from offset 0 in 2 packets (26 * 2 = 52 bytes). Then, send 15 bytes starting from offset 42 in 1 packet (6 + 15 = 21 bytes). Finally, send 13 bytes starting from offset 60 in 1 packet (6 + 13 = 19 bytes). A total of 92 bytes are sent.

2)
{0, 2, 13}
{1, 7, 2}
10
5
Returns: 26
3)
{10264, 111, 357, 100066, 714}
{117, 134, 235, 2395, 23}
100
10
Returns: 3254
4)
{1, 100000000, 450000000}
{99999999, 315000000, 500000000}
1000
30
Returns: 943298999

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

Coding Area

Language: C++17 · define a public class DeviceProgramming with a public method long long minBytes(vector<int> offset, vector<int> size, int maxPacketSize, int overhead) · 126 test cases · 2 s / 256 MB per case

Submitting as anonymous