Your best friend has just opened a Twitter account and, to help make himself known, he has begun to follow random people.
You don’t have a Twitter account but you want to help him by making sure every person he follows then also follows him back.
Initially, the account has 0 followers and every twitter account has a confidence level. An account with a Ci confidence level will wait until at least Ci other accounts are following your friend’s twitter account before also following your friend.
For example, if Ci = 0, the account will immediately follow your friend back whereas a twitter account with Ci = 2 will only follow your friend once it has 2 followers.You know the confidence level of every account your friend has begun to follow and you're prepared to ask some friends that have Twitter accounts to help. Each of these friends have different confidence levels but all can be Ci = 0, it does not matter. What is the minimum number of friends that you need to ask for help to guarantee that all the accounts will follow your friend’s account back?
The input of this problem will have the following format:
The string of digits represents the number of people of each confidence level that your friend begins to follow, so the kth digit of this string (counting starting from 0) represents how many twitter accounts with confidence level k your friend has begun to follow.
For example, the string “513” would mean that your friend began to follow 5 accounts with Ci = 0, 1 account with Ci = 1, and 3
accounts with Ci = 2, and the string “107” would mean that your
friend began to follow 1 account with Ci = 0 and 7 accounts with
Ci = 2 (and none with Ci = 1).
Maximum Confidence Level:
1000
C(max) String:
9050000000500000100000000000000000000000080000000000000600500320
0000900000000000000000000050006000000500000000000050500200000080
0800028000000000100001000009040020810000000000000000006000000400
0960000000220000005000600000000700000000000000000000406000060000
0000001704004023000000000050800000000000040000095000100004000000
0000200000030500009060800000000000000000590000000000600000000509
0000000005040000007600900070039000000000040000000009007077000020
2700004090800000300000000004005000000800700000000100004005000000
0050000100000730600000870001010007900002034000400107000100000000
0006080000207000000000000000000070000400007000300000600000070000
0900001000070050500009004000800080007800000040000000000008020400
5000009000700600005000000000006000000007000000076000000007000000
0230000000000000000000010000090000080000001000000000000000000000
0000800000030100000000070000200080000003003000070000000002100000
9000000100000060807000210053000000020000000000100050305054000000
00300050000007000400600000011000030000301
Maximum Confidence Level:
1000
C(max) String:
0007003000000000000530000000000000000000303700000090000009090102
0050000610006020000050000060004000000050004000000001000090000000
0000090010000000007000070200100000000700000001000000000000000003
9000800000060070000040043000000900000500000771000000000000700000
0950070004600020000700000000060030000000000000000400000000079050
2050009000000030739000904900094000000780160000001080998000000000
0000700005000100000200000000000800000008010108007018000000000050
0300050000090100000000007000080000000040000009030000700700000000
0830000000080000000000005600000908000000200400000038026000031201
0000001000020000000000050000000000005000000300000000000800000300
3000300000090000000400000200060000000000060100000000000000007004
5200090001000000207000000002002000000097012093000040006090000000
5000040700000000800600701079000300000000000099000000040004020360
7000002000040901030200000000000009900000800020404000060000005000
0063000000072000000000000000000000050000000000000076300090106000
000000500000600200000000000406050050001
I don't need to ask friends for help if the current number of followers is bigger or equals the confidence level (ci) of the currently looked at Twitter accounts. In that case the twitter users will follow my friend by themselves so I add the number of Twitter accounts at index i of the C(max) String to the total amount of followers.
In case the number is lower the accounts will not follow my friend so I need to determine how many friends to ask to reach the currently needed confidence level of the accounts. To calculate the number of missing followers take current number of followers and the confidence level of the accounts at the current ci index. Subtract ci from the actual number of followers to calculate the needed amount of friends to reach the next confidence level.
Ask the calculated temporary number of friends to follow the account of my friend and add this number to the total of friends I had to ask, to keep count of how many friends helped in total. Now when the number of current followers equals the confindence level of the accounts at index ci they will start following my friend, so add this number to the counter of followers in total.
Start all over again and repeat the process until the maximum confidence level given is reached.
followers = 0;
neededFriendsTotal = 0;
for (var i = 0; i <= cmax; i++) {
ci = i;
if (followers >= ci) {
followers += twitterAccounts[i];
} else {
var tempNeededFriends = 0;
tempNeededFriends = ci - followers;
neededFriendsTotal += tempNeededFriends;
followers += tempNeededFriends;
if(followers == ci) {
followers += twitterAccounts[i];
}
};
};
Press Button to calculate how many friends you need to ask.