Statistics

Problem Statement for "TheCoffeeTimeDivTwo"

Problem Statement

John and Brus are flying on an airplane and now it's coffee time.

There are n seats in the plane numbered from 1 to n, one seat in each row. All seats are occupied, thus there are n passengers overall (including John and Brus). A stewardess will serve a cup of coffee or tea to each passenger. She needs to serve tea to all passengers whose seat numbers are listed in int[] tea, and she needs to serve coffee to all other passengers.

A coffee and tea machine is located just before the first seat of the plane. The stewardess has a flask that can contain enough coffee or tea to serve at most 7 passengers. Initially, the stewardess is located near the coffee and tea machine and the flask is empty.

The stewardess can perform the following kinds of actions:
  • Move from the coffee and tea machine to seat 1 or move from seat 1 to the coffee and tea machine. Each of these two actions takes 1 second.
  • Move from seat i, i > 1, to seat i-1. It takes 1 second.
  • Move from seat i, i < n, to seat i+1. It takes 1 second.
  • If she is near seat i, the passenger at this seat has not yet been served and the current type of drink in the flask is the same as the drink this passenger wants, she can serve this passenger with a cup of drink he/she wants. It takes 4 seconds.
  • If she is near the coffee and tea machine and the flask is empty, she can fill the flask with either tea or coffee (but not both simultaneously). It takes 47 seconds. Note that she can fill the flask partially (to serve less than 7 passengers), but it still takes 47 seconds.

Given int n and int[] tea, return the minimal time needed for the stewardess to serve all passengers with proper drinks and return to the coffee and tea machine.

Definition

Class:
TheCoffeeTimeDivTwo
Method:
find
Parameters:
int, int[]
Returns:
int
Method signature:
int find(int n, int[] tea)
(be sure your method is public)

Constraints

  • n will be between 2 and 1000, inclusive.
  • tea will contain between 1 and 47 elements, inclusive.
  • Each element of tea will be between 1 and n, inclusive.
  • All elements of tea will be distinct.

Examples

  1. 2

    {1}

    Returns: 108

    The stewardess will serve coffee in 47+2+4+2=55 seconds and tea in 47+1+4+1=53 seconds.

  2. 2

    {2, 1}

    Returns: 59

    Here she only needs to serve tea.

  3. 15

    {1, 2, 3, 4, 5, 6, 7}

    Returns: 261

    The stewardess will fill the flask three times overall: once with tea and two times with coffee.

  4. 47

    {1, 10, 6, 2, 4}

    Returns: 891

  5. 9

    {3, 1}

    Returns: 154

  6. 7

    {3, 2}

    Returns: 142

  7. 5

    {4, 2, 1, 5}

    Returns: 130

  8. 49

    {10, 16, 40, 41, 27, 47, 26, 43, 21, 34, 22, 13, 31, 17, 4, 23, 7, 9, 36, 28, 20, 18, 8, 49, 11, 45, 15, 38, 25, 35, 48, 6, 32, 1, 3, 39, 24, 42, 2, 37, 29, 5}

    Returns: 953

  9. 44

    {19, 29, 7, 41, 26, 39}

    Returns: 863

  10. 39

    {27, 29, 16, 18, 28, 4, 7, 39, 1, 25, 37, 33, 26, 9, 19, 14, 38, 10, 35, 24, 3, 22, 12, 15, 17, 2, 20, 34, 36, 30, 5, 6, 13, 21}

    Returns: 726

  11. 22

    {4, 5, 10, 11, 9, 12, 15, 19, 13, 3, 6, 1, 22, 17, 14}

    Returns: 386

  12. 43

    {19, 28, 34, 11, 4, 35, 10, 13, 12, 31, 30, 18, 5, 39, 33, 2, 32, 27, 43, 1, 36, 42, 8, 15, 26, 16, 14, 41, 17, 29, 37, 25, 38, 23, 22, 3, 24, 9, 40, 20, 7, 6}

    Returns: 845

  13. 24

    {9, 21, 7, 19, 13, 10, 18, 15, 22, 1, 20, 12, 23, 4, 5, 16, 11, 17}

    Returns: 424

  14. 54

    {21, 10, 48}

    Returns: 1183

  15. 18

    {7, 1}

    Returns: 338

  16. 86

    {53, 42, 17, 71, 35, 39, 59, 52, 5, 41}

    Returns: 2193

  17. 37

    {4, 1, 25, 31, 3, 36, 34, 32, 6, 29, 24, 23, 7, 27, 33, 19}

    Returns: 696

  18. 82

    {81, 69, 15, 27, 63, 38, 79, 49}

    Returns: 2057

  19. 94

    {7, 33, 31, 58, 45, 65, 38, 6, 3, 53, 63, 39, 43, 91, 89, 73, 24, 47, 67, 55, 1, 71, 57, 56, 37, 80, 51, 10, 77, 21, 59, 44, 82, 87, 70, 28, 19, 52, 85, 49, 11, 81, 83}

    Returns: 2515

  20. 80

    {43}

    Returns: 2001

  21. 35

    {31, 4, 12, 19, 9, 25, 18, 16, 33, 10, 30, 2, 17, 6, 13, 23, 8, 35, 34, 20, 7, 27, 29, 21, 11, 5, 32, 28, 1, 22, 15, 24, 26, 14, 3}

    Returns: 585

  22. 28

    {23, 15, 28, 6, 25, 7, 24, 1, 18, 21, 27, 20, 17, 22, 26, 11, 4, 14, 5, 12, 13, 19, 2, 16, 10, 9, 8, 3}

    Returns: 440

  23. 30

    {9, 29, 30, 16, 4, 26, 21, 5, 10, 2, 19, 1, 20, 6, 25, 8, 3, 14, 18, 11, 23, 13, 15, 12, 27, 28, 22, 17, 7, 24}

    Returns: 515

  24. 5

    {1, 4, 3, 2, 5}

    Returns: 77

  25. 43

    {9, 16, 12, 15, 5, 4, 29, 21, 38, 28, 31, 1, 8, 20, 11, 27, 37, 2, 10, 42, 43, 33, 22, 25, 6, 40, 18, 39, 35, 26, 34, 7, 14, 23, 24, 3, 17, 30, 32, 36, 13, 19, 41}

    Returns: 809

  26. 906

    {219, 163, 364, 709, 129, 611, 205, 867, 859, 549, 628, 715, 431, 605, 256, 745, 97, 255, 733, 424, 145, 673, 471, 139, 643, 169, 629, 228, 470, 805, 1, 157, 598, 747, 671, 475, 409, 109, 264, 562, 697, 543}

    Returns: 128570

  27. 154

    {127, 71, 85, 103, 39, 14, 111, 72, 19, 40, 113, 151, 147, 7, 137, 83, 65, 78, 148, 93, 58, 121, 75, 135, 55, 128, 25, 144, 99, 131, 50, 57, 37, 53, 36, 115, 26, 51, 97, 88}

    Returns: 5365

  28. 902

    {861, 452}

    Returns: 128198

  29. 641

    {392, 96, 631, 125, 409}

    Returns: 67018

  30. 960

    {629, 681, 265, 661, 950, 475, 193, 111, 425}

    Returns: 143976

  31. 222

    {104}

    Returns: 9881

  32. 467

    {240, 332, 16, 208, 382, 130, 394, 354, 162, 403, 219, 89, 50, 356, 134, 363, 214, 237, 229, 138, 352, 440, 30, 20, 85, 119, 203, 206, 183, 150, 284, 76, 391, 390, 235, 11, 451, 236, 288, 380, 326, 370, 438, 287, 142}

    Returns: 37128

  33. 632

    {599, 99, 225, 402, 289, 48, 425, 89, 307, 333, 115, 352, 497, 9, 93, 241, 1, 412, 21, 103, 73, 493, 300, 137, 627, 610, 521, 45, 227, 384, 575, 184, 205}

    Returns: 64987

  34. 519

    {57, 69, 340, 264, 248, 83, 265, 437, 147, 325, 406, 271, 104, 112, 470, 438, 349, 212, 241, 448, 425, 66, 443, 139, 343, 436, 312, 344, 58, 238, 49, 490, 166, 214, 65}

    Returns: 45055

  35. 526

    {409, 213, 137, 321}

    Returns: 46240

  36. 906

    {1, 12, 40, 5, 6, 29, 31, 36, 23, 18, 26, 30, 19, 38, 35, 37, 25, 8, 4, 15, 7, 39, 11, 27, 14, 13, 21, 10, 2, 16, 22, 34, 32, 42, 41, 3, 28, 33, 24, 20, 9, 17}

    Returns: 127952

  37. 314

    {4, 10, 16, 8, 3, 15, 6, 11, 5, 1, 18, 14, 2, 7, 13, 19, 17, 12, 9}

    Returns: 17852

  38. 121

    {5, 4, 6, 9, 1, 11, 3, 7, 13, 2, 8, 12, 10}

    Returns: 3560

  39. 857

    {7, 1, 9, 15, 5, 2, 12, 14, 10, 3, 13, 16, 18, 6, 11, 17, 4, 8}

    Returns: 114995

  40. 398

    {5, 4, 6, 2, 7, 1, 8, 3}

    Returns: 27352

  41. 1000

    {444, 455, 483, 448, 449, 487, 490, 479, 466, 489, 469, 473, 462, 481, 478, 480, 488, 451, 447, 458, 486, 482, 454, 470, 457, 456, 464, 453, 445, 459, 465, 477, 475, 485, 484, 446, 471, 476, 467, 463, 452, 460, 450, 472, 468, 461, 474}

    Returns: 154894

  42. 1000

    {607, 227, 545, 365, 226, 369, 269, 125, 437, 590, 811, 135, 523, 31, 573, 799, 611, 217, 252, 852, 199, 744, 563, 291, 165, 529, 501, 41, 749, 796, 134, 7, 357, 417, 388, 73, 868, 873, 61, 981, 784, 137, 681, 434, 677, 605, 907}

    Returns: 155600

  43. 1000

    {681, 105, 576, 313, 414, 943, 89, 585, 279, 181, 310, 253, 201, 883, 85, 239, 481, 997, 401, 191, 701, 686, 901, 23, 2, 803, 97, 748, 396, 385, 979, 255, 685, 271, 345, 793, 601, 900, 795, 985, 831, 565, 111, 517, 45, 948, 277}

    Returns: 155542

  44. 1000

    {897, 737, 25, 579, 37, 116, 719, 73, 553, 189, 876, 479, 885, 997, 513, 373, 655, 657, 541, 119, 914, 971, 219, 806, 793, 506, 701, 770, 798, 619, 835, 236, 241, 31, 915, 251, 629, 617, 267, 27, 270, 105, 636, 429, 751, 265, 424}

    Returns: 155580

  45. 1000

    {595, 887, 885, 961, 601, 641, 482, 232, 876, 361, 517, 561, 753, 401, 281, 799, 433, 877, 681, 717, 556, 851, 713, 376, 745, 853, 633, 161, 701, 463, 353, 551, 751, 156, 881, 781, 445, 89, 358, 499, 309, 725, 818, 571, 941, 669, 55}

    Returns: 155524

  46. 1000

    {109, 848, 271, 580, 846, 741, 26, 843, 785, 605, 521, 301, 841, 463, 748, 845, 667, 209, 201, 551, 516, 1, 440, 125, 648, 663, 177, 278, 353, 651, 161, 981, 961, 685, 295, 988, 137, 159, 817, 81, 676, 486, 245, 151, 734, 266, 473}

    Returns: 155500

  47. 1000

    {922, 761, 257, 31, 869, 356, 601, 461, 117, 661, 218, 521, 689, 911, 519, 553, 479, 804, 8, 225, 124, 863, 821, 101, 276, 476, 368, 481, 313, 833, 741, 189, 401, 153, 216, 305, 692, 537, 876, 538, 358, 370, 157, 817, 341, 205, 97}

    Returns: 155468

  48. 47

    {1, 10, 6, 2, 4 }

    Returns: 891

  49. 15

    {1, 2, 3, 4, 5, 6, 7 }

    Returns: 261

  50. 2

    {1 }

    Returns: 108

  51. 47

    {1, 10, 6, 2, 4, 8 }

    Returns: 891

  52. 995

    {1, 2, 3, 4, 5, 6, 7, 8, 9 }

    Returns: 153133

  53. 100

    {1, 2, 3, 4, 88, 99, 33 }

    Returns: 2771

  54. 1000

    {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 87, 88, 90, 96, 105 }

    Returns: 154724

  55. 47

    {1, 5, 32, 23, 2, 34, 35, 21 }

    Returns: 956

  56. 1000

    {1, 10, 6, 2, 4, 800, 325, 453, 564 }

    Returns: 155612

  57. 20

    {1, 3, 6, 8, 10, 12, 13, 14, 15, 17 }

    Returns: 364

  58. 1000

    {500, 90, 1000, 1 }

    Returns: 156172

  59. 15

    {1, 2, 3, 4, 5, 6, 7, 9, 14, 11 }

    Returns: 265

  60. 15

    {1, 2, 3, 4, 5, 6, 7, 15 }

    Returns: 261

  61. 1000

    {21, 42, 63, 84, 105, 126, 147, 168, 189, 210, 231, 252, 273, 294, 315, 336, 357, 378, 399, 420, 441, 462, 483, 504, 525, 546, 567, 588, 609, 630, 651, 672, 693, 714, 735, 756, 777, 798, 819, 840, 861, 882, 903, 924, 945, 966, 987 }

    Returns: 155502

  62. 50

    {1, 2, 3, 4, 5, 6, 7 }

    Returns: 996

  63. 15

    {8, 9, 10, 11, 14, 12, 15, 13 }

    Returns: 261

  64. 1000

    {50, 90, 1000, 1 }

    Returns: 156300

  65. 50

    {1, 2, 9, 7, 5, 6, 8, 12, 15, 18, 43, 50 }

    Returns: 1052

  66. 207

    {1, 2, 3, 4, 200, 201, 202, 203, 204, 205, 206 }

    Returns: 8580

  67. 9

    {1, 2, 3, 4, 5, 6, 7, 8, 9 }

    Returns: 152

  68. 15

    {1, 2, 3, 4, 5, 6, 7, 13 }

    Returns: 259

  69. 15

    {1, 2, 3, 4, 5, 6, 7, 14, 9, 12, 11 }

    Returns: 267

  70. 17

    {2, 3, 7, 9, 13, 1, 5 }

    Returns: 285

  71. 19

    {2, 4, 6, 8, 10, 12, 14, 16, 18 }

    Returns: 356

  72. 990

    {1, 2, 3, 4, 10, 13, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 100, 101, 105, 112, 550, 551, 900, 901, 120, 121, 122, 129, 130, 888 }

    Returns: 152324

  73. 20

    {20, 19, 18, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 }

    Returns: 299

  74. 47

    {29, 46, 39, 5, 33, 35, 41, 22, 20, 31, 34, 6, 4, 24, 30, 28, 36, 11, 9, 8, 2, 43, 19, 27 }

    Returns: 972

  75. 12

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }

    Returns: 176

  76. 1000

    {11, 12, 13, 7, 8, 9, 23, 53, 64, 65, 66, 67, 68, 32, 33, 37, 35, 343, 234, 235, 236, 238, 240, 242, 244, 873, 897, 674, 888, 889, 893, 833, 787, 973, 999, 1000 }

    Returns: 155544

  77. 16

    {5 }

    Returns: 314

  78. 10

    {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

    Returns: 160

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.
This problem was used for: