Problem Statement | |||||||||||||
On most modern PC systems, there is a 2-wire bus called the System Management Bus, or SMBus, which is based on the I2C protocol. This bus is used to talk to multiple devices on the system such as temperature sensors, or batteries. The most significant achievement of the I2C protocol is that it requires no more than 2 wires, and is not susceptible to collisions (unlike other hardware protocols, like ethernet). Collisions occur when two masters (devices which transmit messages) try to transmit at the same time and the resulting data is invalid. For I2C, the first bit transmitted by one master which is different than the bit transmitted by another master causes an "arbitration" to occur. The data being transmitted on the bus is the logic and-ed value of all the data being transmitted by the masters. Therefore, if one master is transmitting a '1' and another is transmitting a '0', the '0' will be transmitted and the '1' will not. The master transmitting the '1' detects that it is not able to transmit, and stops transmitting. The arbitration is not detected by the master transmitting the '0', or by the slave receiving the '0', so the message can continue without any collisions. Since '0' bits that occur earlier in messages always win, the master transmitting the lowest byte always wins arbitration. For example, if one master was transmitting "01234", and another master was transmitting "01245", both masters would transmit the first three bytes, but the first master would win arbitration on the fourth data byte, since '3' is less than '4'. Multiple masters can start transmissions at the same time, but if a transmission has already started, another master cannot start one in the middle of the transmission. Therefore, if one master is transmitting "01234", and has already transmitted the '0', another master wanting to transmit "1234" cannot start its transmission until the first master is finished. The speed of transmission of each master is also allowed to vary. The speed at which each byte is transferred is determined by the slowest transmitting master. If a master loses arbitration of the bus, it continues to drive the clock signal (which determines the speed) for the remainder of the current byte, but then stops driving the clock for the rest of the transmission. In other words, the speed that each byte is transmitted at is determined by the slowest master attempting to transmit during that byte, even if the master loses arbitration during that byte. Given the description of the I2C protocol above, you are to simulate multiple masters transmitting messages on the bus, and return how long it takes to transmit them. You will be given a String[] messages, where each element is a message to be transmitted by a master device, and the messages consist of numeric digits '0'-'9'. You will also be given a int[] times, where each element is the number of milliseconds it takes for the corresponding master to transmit a byte. The master transmitting element i of messages is described by element i of times. Each master that loses arbitration will retry transmitting its message after the current message is finished. Note that all masters try transmitting their messages at the very beginning of the simulation. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Constraints | |||||||||||||
- | messages will contain between 1 and 50 elements, inclusive. | ||||||||||||
- | Each element of messages will contain between 1 and 50 characters, inclusive. | ||||||||||||
- | Each element of messages will consist only of numeric digits '0'-'9', inclusive. | ||||||||||||
- | No element of messages will be a prefix of, or be exactly the same as, any other element of messages. | ||||||||||||
- | times will contain the same number of elements as messages. | ||||||||||||
- | Each element of times will be between 1 and 100, inclusive. | ||||||||||||
Examples | |||||||||||||
0) | |||||||||||||
| |||||||||||||
1) | |||||||||||||
| |||||||||||||
2) | |||||||||||||
|