AtCoder Beginner Contest 029

[TakefumiYamamura]

http://abc029.contest.atcoder.jp/

[TakefumiYamamura]

C - Brute-force Attack

時間制限 : 2sec / メモリ制限 : 256MB

問題文

あなたはスーパーハッカーです。高橋君を攻撃対象に定めたあなたは、 高橋君のパソコンのパスワードに関して次の事実を突き止めました。

長さは N 文字である。 a, b, c 以外の文字は含まれない。 高橋君のパソコンのパスワードの候補として考えられる文字列をすべて列挙してしまいましょう。

Note

ただrecursionさせるだけなのに結構手こずったお

#include <iostream>
#include <string>

using namespace std;

void rec(int n, string s){
    string abc = "abc";
    if(n == 1){
        for (int i = 0; i < 3; ++i)
        {
            cout << s + abc[i] << endl;
        }
        return;
    }

    for (int i = 0; i < 3; ++i)
    {
        rec(n-1, s + abc[i]); 
    }

}

int main(){
    int n;
    cin >> n;
    rec(n, "");
}

[TakefumiYamamura]

D - 1

時間制限 : 2sec / メモリ制限 : 256MB

問題文

高橋君は 1 以上 N 以下のすべての整数を十進表記で一回ずつ紙に書きました。 この作業で、高橋君は 1 という数字を何個書いたでしょうか。

note

全探索数え上げはできないからn桁目に1が何回でるかを数える。

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long

using namespace std;

int main(){
    ll n;
    cin >> n;
    ll ten[10];
    ten[0] = 1;
    for (int i = 1; i < 10; ++i)
    {
        ten[i] = 10 * ten[i-1]; 

    }
    ll ans = 0;

    for (int i = 0; i < 9; ++i)
    {
        ans += ten[i] * (n / ten[i+1]);
        ll tmp = n % ten[i+1];
        if(tmp < ten[i]) continue;
        if(ten[i] <= tmp && tmp < 2*ten[i] ){
            ans += tmp - ten[i]+1;
            continue;
        }
        if(tmp > ten[i]){
            ans += ten[i];
            continue;
        }
    }
    cout << ans << endl;

}