SRM 616, D2, 250-Pointer (WakingUpEasy)

James S. Plank

Sat Sep 3 16:07:18 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: April, 2014
Competitors who opened the problem: 1114
Competitors who submitted a solution: 1078
Number of correct solutions: 1027
Accuracy (percentage correct vs those who opened): 92.19%.
Average Correct Time: 8 minutes, 21 seconds.

If you look at the constraints, the maximum number of alarms is 10,000, which, for Topcoder, is a blink of an eye. So, you simply simulate, by subtracting from S the value of each successive alarm. Use an index i, which will start at zero, and which you'll increment on each iteration. Use the mod operation to convert i to an index for the alarms array.

I won't include the code for this one, but I will show the output of testing and subtracting each alarm in examples 0, 1 and 3.

Example 1:

i = 0.  S before = 3.  volume[0] = 5.  S after = -2
1

Example 0:

i = 0.  S before = 13.  volume[0] = 5.  S after = 8
i = 1.  S before = 8.  volume[1] = 2.  S after = 6
i = 2.  S before = 6.  volume[2] = 4.  S after = 2
i = 3.  S before = 2.  volume[0] = 5.  S after = -3
4

Example 1:

i = 0.  S before = 3.  volume[0] = 5.  S after = -2
1

Example 3:

i = 0.  S before = 9999.  volume[0] = 42.  S after = 9957
i = 1.  S before = 9957.  volume[1] = 68.  S after = 9889
i = 2.  S before = 9889.  volume[2] = 35.  S after = 9854
i = 3.  S before = 9854.  volume[3] = 1.  S after = 9853
i = 4.  S before = 9853.  volume[4] = 70.  S after = 9783
i = 5.  S before = 9783.  volume[5] = 25.  S after = 9758
i = 6.  S before = 9758.  volume[6] = 79.  S after = 9679
i = 7.  S before = 9679.  volume[7] = 59.  S after = 9620
i = 8.  S before = 9620.  volume[8] = 63.  S after = 9557
i = 9.  S before = 9557.  volume[9] = 65.  S after = 9492
i = 10.  S before = 9492.  volume[10] = 6.  S after = 9486
i = 11.  S before = 9486.  volume[11] = 46.  S after = 9440
i = 12.  S before = 9440.  volume[12] = 82.  S after = 9358
i = 13.  S before = 9358.  volume[13] = 28.  S after = 9330
i = 14.  S before = 9330.  volume[14] = 62.  S after = 9268
i = 15.  S before = 9268.  volume[15] = 92.  S after = 9176
i = 16.  S before = 9176.  volume[16] = 96.  S after = 9080
i = 17.  S before = 9080.  volume[17] = 43.  S after = 9037
i = 18.  S before = 9037.  volume[18] = 28.  S after = 9009
i = 19.  S before = 9009.  volume[19] = 37.  S after = 8972
i = 20.  S before = 8972.  volume[20] = 92.  S after = 8880
i = 21.  S before = 8880.  volume[21] = 5.  S after = 8875
i = 22.  S before = 8875.  volume[22] = 3.  S after = 8872
i = 23.  S before = 8872.  volume[23] = 54.  S after = 8818
i = 24.  S before = 8818.  volume[24] = 93.  S after = 8725
i = 25.  S before = 8725.  volume[25] = 83.  S after = 8642
i = 26.  S before = 8642.  volume[26] = 22.  S after = 8620
i = 27.  S before = 8620.  volume[27] = 17.  S after = 8603
i = 28.  S before = 8603.  volume[28] = 19.  S after = 8584
i = 29.  S before = 8584.  volume[29] = 96.  S after = 8488
i = 30.  S before = 8488.  volume[30] = 48.  S after = 8440
i = 31.  S before = 8440.  volume[31] = 27.  S after = 8413
i = 32.  S before = 8413.  volume[32] = 72.  S after = 8341
i = 33.  S before = 8341.  volume[33] = 39.  S after = 8302
i = 34.  S before = 8302.  volume[34] = 70.  S after = 8232
i = 35.  S before = 8232.  volume[35] = 13.  S after = 8219
i = 36.  S before = 8219.  volume[36] = 68.  S after = 8151
i = 37.  S before = 8151.  volume[37] = 100.  S after = 8051
i = 38.  S before = 8051.  volume[38] = 36.  S after = 8015
i = 39.  S before = 8015.  volume[39] = 95.  S after = 7920
i = 40.  S before = 7920.  volume[40] = 4.  S after = 7916
i = 41.  S before = 7916.  volume[41] = 12.  S after = 7904
i = 42.  S before = 7904.  volume[42] = 23.  S after = 7881
i = 43.  S before = 7881.  volume[43] = 34.  S after = 7847
i = 44.  S before = 7847.  volume[44] = 74.  S after = 7773
i = 45.  S before = 7773.  volume[45] = 65.  S after = 7708
i = 46.  S before = 7708.  volume[46] = 42.  S after = 7666
i = 47.  S before = 7666.  volume[47] = 12.  S after = 7654
i = 48.  S before = 7654.  volume[48] = 54.  S after = 7600
i = 49.  S before = 7600.  volume[49] = 69.  S after = 7531
i = 50.  S before = 7531.  volume[0] = 42.  S after = 7489
i = 51.  S before = 7489.  volume[1] = 68.  S after = 7421
i = 52.  S before = 7421.  volume[2] = 35.  S after = 7386
i = 53.  S before = 7386.  volume[3] = 1.  S after = 7385
i = 54.  S before = 7385.  volume[4] = 70.  S after = 7315
i = 55.  S before = 7315.  volume[5] = 25.  S after = 7290
i = 56.  S before = 7290.  volume[6] = 79.  S after = 7211
i = 57.  S before = 7211.  volume[7] = 59.  S after = 7152
i = 58.  S before = 7152.  volume[8] = 63.  S after = 7089
i = 59.  S before = 7089.  volume[9] = 65.  S after = 7024
i = 60.  S before = 7024.  volume[10] = 6.  S after = 7018
i = 61.  S before = 7018.  volume[11] = 46.  S after = 6972
i = 62.  S before = 6972.  volume[12] = 82.  S after = 6890
i = 63.  S before = 6890.  volume[13] = 28.  S after = 6862
i = 64.  S before = 6862.  volume[14] = 62.  S after = 6800
i = 65.  S before = 6800.  volume[15] = 92.  S after = 6708
i = 66.  S before = 6708.  volume[16] = 96.  S after = 6612
i = 67.  S before = 6612.  volume[17] = 43.  S after = 6569
i = 68.  S before = 6569.  volume[18] = 28.  S after = 6541
i = 69.  S before = 6541.  volume[19] = 37.  S after = 6504
i = 70.  S before = 6504.  volume[20] = 92.  S after = 6412
i = 71.  S before = 6412.  volume[21] = 5.  S after = 6407
i = 72.  S before = 6407.  volume[22] = 3.  S after = 6404
i = 73.  S before = 6404.  volume[23] = 54.  S after = 6350
i = 74.  S before = 6350.  volume[24] = 93.  S after = 6257
i = 75.  S before = 6257.  volume[25] = 83.  S after = 6174
i = 76.  S before = 6174.  volume[26] = 22.  S after = 6152
i = 77.  S before = 6152.  volume[27] = 17.  S after = 6135
i = 78.  S before = 6135.  volume[28] = 19.  S after = 6116
i = 79.  S before = 6116.  volume[29] = 96.  S after = 6020
i = 80.  S before = 6020.  volume[30] = 48.  S after = 5972
i = 81.  S before = 5972.  volume[31] = 27.  S after = 5945
i = 82.  S before = 5945.  volume[32] = 72.  S after = 5873
i = 83.  S before = 5873.  volume[33] = 39.  S after = 5834
i = 84.  S before = 5834.  volume[34] = 70.  S after = 5764
i = 85.  S before = 5764.  volume[35] = 13.  S after = 5751
i = 86.  S before = 5751.  volume[36] = 68.  S after = 5683
i = 87.  S before = 5683.  volume[37] = 100.  S after = 5583
i = 88.  S before = 5583.  volume[38] = 36.  S after = 5547
i = 89.  S before = 5547.  volume[39] = 95.  S after = 5452
i = 90.  S before = 5452.  volume[40] = 4.  S after = 5448
i = 91.  S before = 5448.  volume[41] = 12.  S after = 5436
i = 92.  S before = 5436.  volume[42] = 23.  S after = 5413
i = 93.  S before = 5413.  volume[43] = 34.  S after = 5379
i = 94.  S before = 5379.  volume[44] = 74.  S after = 5305
i = 95.  S before = 5305.  volume[45] = 65.  S after = 5240
i = 96.  S before = 5240.  volume[46] = 42.  S after = 5198
i = 97.  S before = 5198.  volume[47] = 12.  S after = 5186
i = 98.  S before = 5186.  volume[48] = 54.  S after = 5132
i = 99.  S before = 5132.  volume[49] = 69.  S after = 5063
i = 100.  S before = 5063.  volume[0] = 42.  S after = 5021
i = 101.  S before = 5021.  volume[1] = 68.  S after = 4953
i = 102.  S before = 4953.  volume[2] = 35.  S after = 4918
i = 103.  S before = 4918.  volume[3] = 1.  S after = 4917
i = 104.  S before = 4917.  volume[4] = 70.  S after = 4847
i = 105.  S before = 4847.  volume[5] = 25.  S after = 4822
i = 106.  S before = 4822.  volume[6] = 79.  S after = 4743
i = 107.  S before = 4743.  volume[7] = 59.  S after = 4684
i = 108.  S before = 4684.  volume[8] = 63.  S after = 4621
i = 109.  S before = 4621.  volume[9] = 65.  S after = 4556
i = 110.  S before = 4556.  volume[10] = 6.  S after = 4550
i = 111.  S before = 4550.  volume[11] = 46.  S after = 4504
i = 112.  S before = 4504.  volume[12] = 82.  S after = 4422
i = 113.  S before = 4422.  volume[13] = 28.  S after = 4394
i = 114.  S before = 4394.  volume[14] = 62.  S after = 4332
i = 115.  S before = 4332.  volume[15] = 92.  S after = 4240
i = 116.  S before = 4240.  volume[16] = 96.  S after = 4144
i = 117.  S before = 4144.  volume[17] = 43.  S after = 4101
i = 118.  S before = 4101.  volume[18] = 28.  S after = 4073
i = 119.  S before = 4073.  volume[19] = 37.  S after = 4036
i = 120.  S before = 4036.  volume[20] = 92.  S after = 3944
i = 121.  S before = 3944.  volume[21] = 5.  S after = 3939
i = 122.  S before = 3939.  volume[22] = 3.  S after = 3936
i = 123.  S before = 3936.  volume[23] = 54.  S after = 3882
i = 124.  S before = 3882.  volume[24] = 93.  S after = 3789
i = 125.  S before = 3789.  volume[25] = 83.  S after = 3706
i = 126.  S before = 3706.  volume[26] = 22.  S after = 3684
i = 127.  S before = 3684.  volume[27] = 17.  S after = 3667
i = 128.  S before = 3667.  volume[28] = 19.  S after = 3648
i = 129.  S before = 3648.  volume[29] = 96.  S after = 3552
i = 130.  S before = 3552.  volume[30] = 48.  S after = 3504
i = 131.  S before = 3504.  volume[31] = 27.  S after = 3477
i = 132.  S before = 3477.  volume[32] = 72.  S after = 3405
i = 133.  S before = 3405.  volume[33] = 39.  S after = 3366
i = 134.  S before = 3366.  volume[34] = 70.  S after = 3296
i = 135.  S before = 3296.  volume[35] = 13.  S after = 3283
i = 136.  S before = 3283.  volume[36] = 68.  S after = 3215
i = 137.  S before = 3215.  volume[37] = 100.  S after = 3115
i = 138.  S before = 3115.  volume[38] = 36.  S after = 3079
i = 139.  S before = 3079.  volume[39] = 95.  S after = 2984
i = 140.  S before = 2984.  volume[40] = 4.  S after = 2980
i = 141.  S before = 2980.  volume[41] = 12.  S after = 2968
i = 142.  S before = 2968.  volume[42] = 23.  S after = 2945
i = 143.  S before = 2945.  volume[43] = 34.  S after = 2911
i = 144.  S before = 2911.  volume[44] = 74.  S after = 2837
i = 145.  S before = 2837.  volume[45] = 65.  S after = 2772
i = 146.  S before = 2772.  volume[46] = 42.  S after = 2730
i = 147.  S before = 2730.  volume[47] = 12.  S after = 2718
i = 148.  S before = 2718.  volume[48] = 54.  S after = 2664
i = 149.  S before = 2664.  volume[49] = 69.  S after = 2595
i = 150.  S before = 2595.  volume[0] = 42.  S after = 2553
i = 151.  S before = 2553.  volume[1] = 68.  S after = 2485
i = 152.  S before = 2485.  volume[2] = 35.  S after = 2450
i = 153.  S before = 2450.  volume[3] = 1.  S after = 2449
i = 154.  S before = 2449.  volume[4] = 70.  S after = 2379
i = 155.  S before = 2379.  volume[5] = 25.  S after = 2354
i = 156.  S before = 2354.  volume[6] = 79.  S after = 2275
i = 157.  S before = 2275.  volume[7] = 59.  S after = 2216
i = 158.  S before = 2216.  volume[8] = 63.  S after = 2153
i = 159.  S before = 2153.  volume[9] = 65.  S after = 2088
i = 160.  S before = 2088.  volume[10] = 6.  S after = 2082
i = 161.  S before = 2082.  volume[11] = 46.  S after = 2036
i = 162.  S before = 2036.  volume[12] = 82.  S after = 1954
i = 163.  S before = 1954.  volume[13] = 28.  S after = 1926
i = 164.  S before = 1926.  volume[14] = 62.  S after = 1864
i = 165.  S before = 1864.  volume[15] = 92.  S after = 1772
i = 166.  S before = 1772.  volume[16] = 96.  S after = 1676
i = 167.  S before = 1676.  volume[17] = 43.  S after = 1633
i = 168.  S before = 1633.  volume[18] = 28.  S after = 1605
i = 169.  S before = 1605.  volume[19] = 37.  S after = 1568
i = 170.  S before = 1568.  volume[20] = 92.  S after = 1476
i = 171.  S before = 1476.  volume[21] = 5.  S after = 1471
i = 172.  S before = 1471.  volume[22] = 3.  S after = 1468
i = 173.  S before = 1468.  volume[23] = 54.  S after = 1414
i = 174.  S before = 1414.  volume[24] = 93.  S after = 1321
i = 175.  S before = 1321.  volume[25] = 83.  S after = 1238
i = 176.  S before = 1238.  volume[26] = 22.  S after = 1216
i = 177.  S before = 1216.  volume[27] = 17.  S after = 1199
i = 178.  S before = 1199.  volume[28] = 19.  S after = 1180
i = 179.  S before = 1180.  volume[29] = 96.  S after = 1084
i = 180.  S before = 1084.  volume[30] = 48.  S after = 1036
i = 181.  S before = 1036.  volume[31] = 27.  S after = 1009
i = 182.  S before = 1009.  volume[32] = 72.  S after = 937
i = 183.  S before = 937.  volume[33] = 39.  S after = 898
i = 184.  S before = 898.  volume[34] = 70.  S after = 828
i = 185.  S before = 828.  volume[35] = 13.  S after = 815
i = 186.  S before = 815.  volume[36] = 68.  S after = 747
i = 187.  S before = 747.  volume[37] = 100.  S after = 647
i = 188.  S before = 647.  volume[38] = 36.  S after = 611
i = 189.  S before = 611.  volume[39] = 95.  S after = 516
i = 190.  S before = 516.  volume[40] = 4.  S after = 512
i = 191.  S before = 512.  volume[41] = 12.  S after = 500
i = 192.  S before = 500.  volume[42] = 23.  S after = 477
i = 193.  S before = 477.  volume[43] = 34.  S after = 443
i = 194.  S before = 443.  volume[44] = 74.  S after = 369
i = 195.  S before = 369.  volume[45] = 65.  S after = 304
i = 196.  S before = 304.  volume[46] = 42.  S after = 262
i = 197.  S before = 262.  volume[47] = 12.  S after = 250
i = 198.  S before = 250.  volume[48] = 54.  S after = 196
i = 199.  S before = 196.  volume[49] = 69.  S after = 127
i = 200.  S before = 127.  volume[0] = 42.  S after = 85
i = 201.  S before = 85.  volume[1] = 68.  S after = 17
i = 202.  S before = 17.  volume[2] = 35.  S after = -18
203

Solution.cpp

#include <string>
#include <vector>
#include <list>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class WakingUpEasy {
  public:
    int countAlarms(vector <int> volume, int S);
};

int WakingUpEasy::countAlarms(vector <int> volume, int S)
{
  int i;
  
  for (i = 0; S > 0; i++) {
    printf("i = %d.  S before = %d.  volume[%d] = %d.  S after = %d\n", 
            i, S, (int) (i%volume.size()), volume[i%volume.size()], S-volume[i%volume.size()]);
    S -= volume[i%volume.size()];
  }
  return i;
}