Connection Status:
Competition Arena > TicketPrinters

TicketPrinters

SRM 481 · 2010-03-12 · by vexorian

SRM 481 · 2010-03-12 · by vexorian · Brute Force, Graph Theory, Search
Class Name: TicketPrinters
Return Type: int
Method Name: minTime
Arg Types: (int, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

After 2 years of hard work, it is finally time to unveil the ultimate plan to win the lottery. This plan involves mostly cartomancy, falsification and programming. The tarot specialist has already predicted the N numbers of the required lottery tickets, and they are given as a int[] wantedValues. The falsification specialist has prepared a set of N ticket printers and he has taken a number of security measures to make it very hard to discover the scheme:

  • The printers are in separate locations. For convenience, they are all hidden inside houses that are all on a single street. The distances between each consecutive pair of printers are given by int[] printerDistance, which contains (n-1) elements. For each i, the time required to travel between printer i and printer i+1 is printerDistance[i] seconds.
  • The way a printer functions is by keeping a hidden integer number in its memory. For security, increasing or decreasing the number by one requires 1 second. At any time, it is possible to order the printer to print the number it has in memory. This procedure also takes 1 second. The starting number for printer i is startingValues[i]
  • Each printer can print at most one ticket.
Your role as the programmer is to go to each printer and print the required lottery tickets given by wantedValues. You are currently in the same location as printer number currentPrinter. Since you do not understand why they even hired a programmer for the scheme, you have decided to use programs to save time in this process. The first program you have developed can, given a wanted number, modify the one in the printer by automatically increasing or decreasing it and finally print the wanted number automatically (increasing/decreasing the numbers and printing them still requires one second). You can install this program to each printer once you are its location. The installation doesn't take any time. Once the program is installed, it can work without any administration from your side, so you can immediately proceed to the next printer.

Now your task is to develop the second program that should determine in which order to visit printers and which printer to use for printing of each of the tickets. Return the outcome of the second program, i.e., the minimum time that is necessary to finish printing all the required numbers.

Constraints

  • wantedValues will contain between 1 and 16 elements, inclusive.
  • startingValues will contain n elements, where n is the number of elements in wantedValues.
  • printerDistance will contain exactly n-1 elements.
  • currentPrinter will be between 0 and n-1, inclusive.
  • Each element of startingValues, printerDistance and wantedValues will be between 1 and 1000000, inclusive.
  • Each element of wantedValues will be unique.
Examples
0)
0
{100, 20, 50}
{66, 78, 99, 5}
{99, 5, 78, 66}
Returns: 171
1)
1
{50, 50}
{100, 200, 300}
{101, 201, 302}
Returns: 152

A possible way to print the tickets is: 0 seconds: Start printing program up at printer 1 to print ticket #201. Begin moving to printer 2's position. 1 second: Printer 1 reaches number 201 in memory. 2 seconds: Printer 1 finishes printing its assigned ticket. 50 seconds: Arrive at printer 2's location. Order it to print ticket #302. Begin moving to printer 0's position. 52 seconds: Printer 2 reaches number 302 in memory. 53 seconds: Printer 2 finishes printing its assigned ticket. 150 seconds: Arrive at printer 0's location. Order it to print ticket #101. 151 seconds: Printer #0 reaches number #101 in memory. 152 seconds: Printer #0 finishes printing ticket #101.

2)
2
{13, 26, 39, 13}
{123, 12, 32, 67, 1015}
{1, 2, 3, 4, 5}
Returns: 1063
3)
8
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
{449787,614796,54968,786527, 9485, 580565, 863481, 75981, 376144, 655003, 614014, 539809, 530316, 933720, 331977, 852299}
{148911, 505520, 471407, 703590, 782713, 363320, 731199, 777341, 60611, 774001, 184862, 12720, 874230, 522316, 477209, 433213}
Returns: 147122
4)
8
{50786, 9196, 512090, 32939, 100741, 474428, 989373, 365848, 206504, 208140, 267419, 131983, 895520, 480880, 967392}
{80756, 615730, 38519, 835172, 587564, 969197, 369071, 339844, 550224, 8133, 295471, 373624, 842247, 329170, 929143, 856805}
{691887, 84678, 281133, 247894, 325949, 391053, 27407, 278613, 882012, 35383, 88651, 735921, 53944, 854962, 552751, 640832}
Returns: 8230484
9)
7
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
{1, 10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000, 100000, 110000, 120000, 130000, 140000, 150000}
{70120, 80119, 120075, 90114, 10042, 20065, 100105, 30084, 140029, 15, 130054, 110092, 50110, 150000, 60117, 40099}
Returns: 121

Longest printer path.

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

Coding Area

Language: C++17 · define a public class TicketPrinters with a public method int minTime(int currentPrinter, vector<int> printerDistance, vector<int> startingValues, vector<int> wantedValues) · 100 test cases · 2 s / 256 MB per case

Submitting as anonymous