Statistics

Problem Statement for "PriorityQueue"

Problem Statement

It's lunchtime! The school canteen is currently empty. N children are going to enter the canteen and form a single queue. The children are numbered 0 through N-1 in the order in which they enter the canteen. Whenever a child enters the canteen, it performs one of two possible actions:

  • either it stands at the current end of the lunch queue,
  • or it skips the entire queue and goes to stand at its current beginning.

You are given the description of the children's behaviour: a String S containing N characters. For each valid i, S[i] is either 'e' or 'b'. Here, 'e' means that child i goes to the end of the queue, and 'b' means it goes to the beginning of the queue.


You are also given a int[] a with N elements. The element a[j] is the annoyance factor of child j (explained below).


At the beginning, the displeasure of each child is zero. The displeasure D[i] of child i grows whenever another child cuts in front of them. More precisely, whenever child i already stands in the queue and child j goes to the beginning of the queue, the displeasure of child i will grow by a[i].


The total displeasure is the sum of all D[i]. Compute and return the total displeasure after all N children have joined the queue.

Definition

Class:
PriorityQueue
Method:
findAnnoyance
Parameters:
String, int[]
Returns:
int
Method signature:
int findAnnoyance(String S, int[] a)
(be sure your method is public)

Constraints

  • N will be between 1 and 100, inclusive.
  • The string S will contain N characters.
  • a will contain N elements.
  • Each element of a will be between 1 and 1,000, inclusive.

Examples

  1. "bbbbb"

    {1,1,1,1,1}

    Returns: 10

    The queue will look as follows: { child 4, child 3, child 2, child 1, child 0 }. The individual displeasures at the end are D[0] = 4, D[1] = 3, D[2] = 2, D[3] = 1, and D[4] = 0. Thus, the total displeasure is 4+3+2+1+0 = 10.

  2. "eeeeee"

    {416,5,41,96,965,7}

    Returns: 0

  3. "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"

    {1,3,5,41,16,1,5,26,51,5,1,6,1,22,1,15,5,15,451,6,1,651,651,851,51,51,511,5,41,85,20,88,11,185,5,77,723,960,620,397,484,692,600,477,222,514,197,131,418,105,130,480,538,727,422,694,224,727,499,810,601,352,33,713,80,217,606,39,676,28,283,207,743,40,688,130,557,793,473,907,332,561,367,890,638,997,461,886,445,47,358,366,371,19,97,412,725,102,153,810}

    Returns: 1239716

  4. "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee"

    {872,272,446,900,294,800,565,428,958,71,478,294,856,925,387,719,760,613,45,980,520,921,448,377,296,191,643,357,207,47,455,442,451,721,16,150,706,191,824,737,772,26,178,451,327,509,897,551,562,627,705,883,796,365,501,141,32,141,910,859,359,959,589,633,472,597,305,57,111,885,674,961,593,873,726,313,568,124,434,877,192,618,271,149,979,91,145,60,861,537,54,307,125,192,362,277,151,55,379,951}

    Returns: 0

  5. "b"

    {1000}

    Returns: 0

  6. "e"

    {1000}

    Returns: 0

  7. "bb"

    {153,87}

    Returns: 153

  8. "ee"

    {12,13}

    Returns: 0

  9. "be"

    {392,687}

    Returns: 0

  10. "eb"

    {687,392}

    Returns: 687

  11. "ebe"

    {1000,999,998}

    Returns: 1000

  12. "beb"

    {1,2,1000}

    Returns: 3

  13. "eeb"

    {2,4,6}

    Returns: 6

  14. "bee"

    {50,40,30}

    Returns: 0

    When the first child joins the queue, there are no other children in the queue yet, so all displeasures remain at zero. The other two children stand at the end of the queue, so they don't change anyone's displeasure either. The total displeasure at the end is therefore 0.

  15. "ebbe"

    {5,2,11,1}

    Returns: 12

  16. "bbe"

    {2,3,1}

    Returns: 2

  17. "ebb"

    {1,1,1}

    Returns: 3

  18. "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeebbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"

    {677,677,543,543,517,517,642,642,583,583,860,860,934,934,475,475,564,564,112,112,952,952,26,26,796,796,536,536,494,494,451,451,742,742,392,392,601,601,30,30,891,891,156,156,993,993,330,330,630,630,901,901,807,807,883,883,145,145,173,173,139,139,261,261,255,255}

    Returns: 927769

  19. "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee"

    {370,601,182,1000,592,95,856,1,476,617,266,357,878,668,649,331,360,800,851,798,89,997,611,37,639,768,869,377,962,903,68,121,946,536,240,7,401,248,172,880,316,326,196,747,923,26,788,979,945,633,268,795,995,206,707,98,538,103,386,740,712,369,350,368,927,386,47,772,19,105}

    Returns: 208451

  20. "eeeeeeeeeeeeeebbbbbbbbbbbbbbbbbbbbbeeeeeeeeeeeee"

    {3,99,109,116,127,174,189,197,225,255,257,286,288,303,306,312,342,360,386,441,455,475,477,478,496,497,550,573,588,605,639,642,682,685,734,789,790,836,859,864,900,910,926,937,938,959,967,996}

    Returns: 146758

  21. "eeeeeeeeeeeeeeeeebbbbbbbbbbeeeeeeeeeeeeeeeeeeeeeeeeeeeeeebb"

    {990,973,966,953,941,936,929,896,871,861,842,823,809,793,791,773,765,764,762,762,756,753,741,728,713,669,663,626,620,613,599,594,590,585,574,551,492,481,466,454,406,385,379,366,364,346,338,276,235,214,189,179,176,164,142,139,117,91,5}

    Returns: 250827

  22. "beeeeeeeebbbbbbbbbbbeeeeeeeeeeeeeeeeeeee"

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

    Returns: 1210

  23. "ebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebebeb"

    {152,122,154,167,148,145,128,139,135,147,162,123,182,198,106,184,144,192,171,156,117,199,183,145,170,190,200,183,187,131,162,185,174,132,137,159,118,172,190,125,195,166,200,109,197,193,135,104,151,148,173,192,200,128,105,156,180,127,156,200,143,160,118,128,154,125,100,141,108,123,180,134,171,131,120,184,155,166,148,163,196,159,192,163,110,145,132,129,148,162,111,170,120,191,108,172,165,112}

    Returns: 374395

  24. "bbeebeebeeeebbb"

    {58,517,301,524,79,375,641,152,810,778,222,342,911,313,336}

    Returns: 20485

  25. "beeebeeeeee"

    {743,522,871,408,717,878,746,587,481,263,701}

    Returns: 2544

    random

  26. "bbbebbbbebbbbebbbbbbeebeeeeebbbbbb"

    {347,697,133,17,258,649,33,229,572,800,229,119,811,311,305,167,534,56,27,167,911,252,71,731,579,255,456,330,36,618,1000,871,156,211}

    Returns: 133603

    random

  27. "bbbbbeebbbbbebbebbbeeebbeebbbbebebbeeebeebbbebbbebbbbebebbeeebbbbeebebebbebbbbebbb"

    {508,14,683,129,155,409,849,183,627,117,532,481,211,959,88,906,996,360,24,198,919,821,354,607,933,196,854,281,913,339,410,983,285,230,221,813,526,229,535,960,373,362,6,572,265,131,843,59,715,421,646,489,584,53,679,727,461,294,242,754,6,954,688,290,600,271,189,691,40,810,65,584,374,458,158,685,834,328,759,136,85,995}

    Returns: 998393

    random

  28. "ebebbebbbeeeebbeeebebbbbbeebbebbbeebbbebbbeebbebebebeebebbeeebbeeeebbbeeebb"

    {219,85,927,420,314,582,307,897,597,384,369,819,682,986,50,593,297,738,102,189,152,659,22,38,449,971,641,412,366,500,342,888,571,555,358,855,186,956,797,483,320,472,254,373,57,102,681,860,239,405,748,560,796,690,529,731,115,594,761,198,63,146,988,610,351,534,714,790,393,531,981,284,144,807,831}

    Returns: 689296

    random

  29. "bbebbeeee"

    {827,583,432,555,659,246,208,24,432}

    Returns: 5066

    random

  30. "bbebbeebbbbebbbbebbbbbbbbbebebbeb"

    {370,636,620,941,880,870,51,343,914,342,181,827,446,58,537,563,978,299,571,148,721,9,76,851,825,181,411,484,673,33,165,562,507}

    Returns: 213671

    random

  31. "bbbeeeebebbbbebbbbbeb"

    {723,134,601,856,471,907,381,386,523,907,269,257,553,400,945,994,749,616,515,323,25}

    Returns: 86323

    random

  32. "ebbbeeeebbebbeebbee"

    {457,379,108,115,930,600,755,136,179,409,778,778,297,198,566,58,154,938,911}

    Returns: 33274

    random

  33. "ebbbeeeeebeeeeebeebeeebbbbebbbbebebbbebbebebebbebebbbebeebebeeebebbbbeeebebebbbbeebbeebbebeeeb"

    {501,290,451,792,978,110,843,104,121,133,952,20,31,224,594,432,255,931,684,914,31,620,480,928,809,857,762,398,301,253,954,72,333,443,371,663,699,382,610,545,677,626,381,801,701,36,126,148,650,669,679,128,628,948,986,680,57,733,569,361,518,766,982,274,73,736,438,204,57,628,876,550,223,747,369,898,956,911,220,580,527,11,817,318,477,988,556,945,773,694,510,7,469,519}

    Returns: 1172856

    random

  34. "bbeebeebeeeebbb"

    {58, 517, 301, 524, 79, 375, 641, 152, 810, 778, 222, 342, 911, 313, 336 }

    Returns: 20485

  35. "bee"

    {50, 40, 30 }

    Returns: 0

  36. "bbeebeebeeeebbbbbbe"

    {58, 517, 301, 524, 79, 375, 641, 152, 810, 778, 222, 342, 911, 313, 336, 23, 432, 213, 444 }

    Returns: 40040

  37. "ebbe"

    {5, 2, 11, 1 }

    Returns: 12

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: