TopCoder Statistics - Problem Statement

Problem Statement

You are very happy because you advanced to the next round of a very important programming contest. You want your best friend to know how happy you are. Therefore, you are going to send him a lot of smile emoticons. You are given an int smiles: the exact number of emoticons you want to send.

You have already typed one emoticon into the chat. Then, you realized that typing is slow. Instead, you will produce the remaining emoticons using copy, paste, and possibly some deleting.

You can only do three different operations:

Copy all the emoticons you currently have into the clipboard.
Paste all emoticons from the clipboard.
Delete one emoticon from the message.

Each operation takes precisely one second. Copying replaces the old content of the clipboard. Pasting does not empty the clipboard. You are not allowed to copy just a part of the emoticons you already have. You are not allowed to delete an emoticon from the clipboard.

Return the smallest number of seconds in which you can turn the one initial emoticon into smiles emoticons.

Definition

Class:: EmoticonsDiv1
Method:: printSmiles
Parameters:: int
Returns:: int
Method signature:: int printSmiles(int smiles)
(be sure your method is public)

Constraints

smiles will be between 2 and 1000, inclusive.

Examples

2

Returns: 2

First use copy, then use paste. The first operation copies one emoticon into the clipboard, the second operation pastes it into the message, so now you have two emoticons and you are done.
4

Returns: 4

One optimal solution is to copy the initial emoticon and then to paste it three times. Another optimal solution is to copy the one emoticon, paste it, copy the two emoticons you currently have, and paste two more.
6

Returns: 5

Copy. This puts one emoticon into the clipboard. Paste. You now have 2 emoticons in the message. Copy. The clipboard now contains 2 emoticons. Paste. You now have 4 emoticons in the message. Paste. You now have 6 emoticons in the message and you are done.
18

Returns: 8
11

Returns: 8

Sometimes we actually do delete an emoticon in the optimal solution.
3

Returns: 3
5

Returns: 5
7

Returns: 7
8

Returns: 6
9

Returns: 6
10

Returns: 7
20

Returns: 9
30

Returns: 10
32

Returns: 10
35

Returns: 11
41

Returns: 13
47

Returns: 12
53

Returns: 12
55

Returns: 13
65

Returns: 14
67

Returns: 14
70

Returns: 13
81

Returns: 12
99

Returns: 14
100

Returns: 14
255

Returns: 17
321

Returns: 17
345

Returns: 18
768

Returns: 19
564

Returns: 19
890

Returns: 21
990

Returns: 21
991

Returns: 22
992

Returns: 21
993

Returns: 23
994

Returns: 22
995

Returns: 22
996

Returns: 22
997

Returns: 23
998

Returns: 22
999

Returns: 22
1000

Returns: 21
977

Returns: 24
901

Returns: 24
961

Returns: 22
508

Returns: 19
959

Returns: 21
968

Returns: 20
22

Returns: 10
512

Returns: 18
123

Returns: 16
513

Returns: 19
817

Returns: 23
729

Returns: 18
111

Returns: 16
833

Returns: 22
847

Returns: 21
33

Returns: 11
509

Returns: 20
34

Returns: 11
506

Returns: 20
124

Returns: 15
501

Returns: 20
510

Returns: 19
26

Returns: 10
127

Returns: 15

Statistics

Problem Statement for "EmoticonsDiv1"

Problem Statement

Definition

Constraints

Examples