2011年6月21日火曜日

CodeForces Beta Round #75 Div2

懲りずに参加

A Chips
Passed System Test


n人が円形に並んでおり、m人のチップを順番に与えていく。
i番目の人間にi枚のチップを与え、最後まで与え終わったら初めに戻る。
与えるチップ数が足りない場合は、動作を中止し、余ったチップを回収。
回収できるチップの枚数を求める。



#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <algorithm>
#include <time.h>
#include <cmath>
#include <queue>
using namespace std;


int main(){
    int n,m;
    cin >> n >> m;
    while(1){
        for(int i = 1;i <= n;i++){
            if(i <= m) m -= i;
            else{
                cout << m << endl;
                return 0;
            }
        }
    }
}



B Binary Number
Passed System Test


100001010のような2進数が与えられる。
与えられた数が偶数ならば、2で割り、奇数ならば、1を足す。
この操作を繰り返して、最終的に1にしたい。
何回の操作が必要になるか?




#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <algorithm>
#include <time.h>
#include <cmath>
#include <queue>


#define REP(i,s,e) for(int i = s;i<e;i++)
#define rep(i,e) REP(i,0,e)


using namespace std;
int main(){
    string arg;
    cin>>arg;
    int len = (int)arg.length()-1;
    int ans = len;
    bool flag = false;
    rep(i,len+1){
        if(arg[len-i] == '1' && !flag && len != i){
            flag = true;
            ans+=2;
        }
        if(arg[len-i] == '0' && flag) ans++;
    }
    cout << ans << endl;
}

C Newspaper Headline
Compilation Error

文字列が二つ(s1,s2)与えられる。
s1を幾つか繋げた後、繋げた文字列から幾つかの文字を消去し、s2を作りたい。
s2を作成するために、必要とするs1の最小個数を出力せよ。
なお、作成出来ない場合は-1を出力せよ。


abcd
dabc
の場合
abcd+abcd→abcdabcdとし
abcdabcdから初めのabc、最後のdを消去すれば
dabcとなるため、出力は2である。

1≦s1≦10^4 かつ 1≦s2≦10^6
であるため、ナイーヴな実装だと確実にTLEになる。

s1における文字の出現箇所をインデックスとして保持してやり、二部探索でやろうとするも、upper_boundではうまくいかず。
aaabbb
aaabbbのような時に、
upper_boundのため最初の文字が認識されず、出力が2となってしまう。
lower_bound + 1でやろうとするも、何故かバグる。
もうちょい修行してきます。

Rating 1338→1367(+29)

以前出来なかったことが少しずつ出来るようになってきた。
ただ、コンテストに出場するよりも、今までやってきた問題の復習をした方が良い気はする。

0 件のコメント:

コメントを投稿

注: コメントを投稿できるのは、このブログのメンバーだけです。