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 件のコメント:
コメントを投稿
注: コメントを投稿できるのは、このブログのメンバーだけです。