SRM 612 Div2 Medium || Topcoder || C++ ||日本語訳

topcoder srm Div2 全探索 再帰関数 プログラミング

問題文 :

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 and paste.

You can only do two different operations:

1.Copy all the emoticons you currently have into the clipboard.
2.Paste all emoticons from the clipboard.

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

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

日本語訳 :

あなたはとても重要なプログラミングコンテストのnext round に進めてとても嬉しいです。あなたは一番の友達にあなたがどれだけ嬉しいか知ってほしいです。それゆえに、あなたは彼にたくさんの笑っている顔文字を贈ろうとしている。あなたにはint型整数smile(顔文字の数)が与えられる。

あなたはすでにチャットにひとつ顔文字を打っている。そして、あなたは自分がタイピングが遅いことに気がついた。顔文字を打つ代わりに、あなたはチャットにある顔文字をコピー&ペーストして目的の数の顔文字をつくろうとする。

あなたは二つの操作のみできる :

1.クリップボードにチャットにある顔文字を全てコピーする
2.クリップボードにある顔文字を貼り付ける。

それぞれの操作は正確に一秒かかる。コピーするとクリップボード内のものは更新される。貼り付けることでクリップボードが空になることはない。※注意 コピーする際今ある顔文字の中の幾つかの文字だけをコピーしてはいけない(10個の顔文字がある時コピーするなら10個全てコピーしなければいけない)

最初の顔文字(一文字)からsmile個の顔文字にするのに掛かる最小の時間を返し(求め)なさい。

2≦smile≦1000


解法 :

再帰関数で全探索。

#include<algorithm>

using namespace std;

class EmoticonsDiv2{

	int searchE(int base, int now, int clip , int count){  

	if (now > base)return 1100;
	if (now == base)return count;

	return min(searchE(base, now + clip, clip, count + 1), //クリップボードの中身を貼り付ける
                   searchE(base, now + now, now, count + 2));  //nowをコピーし貼り付ける
	}

public :
	int printSmiles(int smiles){
	
	return searchE(smiles,1,1,1); //顔文字を一つコピーした状態から始める
	}	
};


反省 :

日本語訳初めて書いてみました!

数式の綺麗な書き方(TeX?)が分からなかった...


おまけ

実際にやると...

smile=100
日本 :
(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)
(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)
(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)
(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)
(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)
(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)
(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)
(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)
(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)
(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)(≧▽≦)

欧米 :
XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD
XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD
XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD
XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD
XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD XD

(欧米の顔文字は基本90°反時計回りに傾いているようです)

こんな感じ