Connection Status:
Competition Arena > SpeedTyper

SpeedTyper

SRM 290 · 2006-02-16 · by hauser

SRM 290 · 2006-02-16 · by hauser · Simple Search, Iteration
Class Name: SpeedTyper
Return Type: String
Method Name: lettersToPractice
Arg Types: (string, vector<int>)
Problem Statement

Problem Statement

Johnny wants to become a great programmer, so he practices to improve his programming skills all the time. He thinks he can save a lot of time if he can learn to type faster. It's said that the key to speed typing is keeping the rhythm, which means pressing each key after a constant interval of time. Johnny, like many programmers, loves all kinds of statistics, so he created a program for measuring his typing progress. The program receives a String letters and a int[] times, representing the keys he pressed and the time of each press in milliseconds respectively. The ith element of times is the time at which he typed the ith character in letters. No key is pressed more than once, and all the times are relative to the start of his practice session.

For this problem you may assume that the average time of one key press will be an integer.

Your task is to calculate which letters take Johnny more than average time to type, so he can practice those letters more. Return a String containing all such letters in the order that they occur in the input.

Notes

  • The time needed to press the first key is given by times[0], and the time needed to press the key corresponding to times[i] for all i > 0 is times[i]-times[i-1].

Constraints

  • letters will contain only lowercase letters ('a'-'z').
  • letters will contain between 1 and 26 characters, inclusive.
  • times will contain the same number of elements as the number of characters in letters.
  • No letter will occur more than once in letters.
  • Each element of times will be between 1 and 100000.
  • Elements of times will be in strict ascending order.
  • The average time of one key press will be an integer.
Examples
0)
"dcab"
{250, 300, 400, 800}
Returns: "db"

It took Johnny 250 ms to type 'd', 50 ms to type 'c', 100 ms to type 'a' and 400 ms for 'b'. The average time to type a letter is 200 ms so he needs to practice 'd' and 'b' more.

1)
"keyboard"
{100,200,300,500,600,800,900,1200}
Returns: "bad"

It took 200 ms each to type 'b', 'a', 300 ms to type 'd', while it only took 100 ms to type each of the other letters. The average time is 150 ms.

2)
"rewq"
{500, 1000, 1500, 4000}
Returns: "q"

'q' seems to be a difficult letter to type.

3)
"abc"
{2000, 4000, 6000}
Returns: ""

Though the speed is not too impressive, the rhythm is perfect.

4)
"a"
{1}
Returns: ""

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

Coding Area

Language: C++17 · define a public class SpeedTyper with a public method string lettersToPractice(string letters, vector<int> times) · 120 test cases · 2 s / 256 MB per case

Submitting as anonymous