This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class ProductOfDigits { | |
public: | |
int smallestNumber(int N) { | |
vector<int> factors; | |
int n = N; | |
for(int i=2;i<=N;++i){ | |
while(n%i==0){ | |
factors.push_back(i); | |
n/=i; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* given p as the probability of this team winning, | |
* what's the probability for this team have a prime number as it's final score | |
*/ | |
double solve(int p){ | |
vector<int> prob(0, 20); | |
prob[0]=1; | |
// 短短七行讓你省去寫C(n, k) 又可以拿到第k項展開後的結果 | |
// generate binomial coefficient (x+y)^n : C(n, k) * (x^n-k) * (x^k) | |
// pascal triangle |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class EquilibriumPoints { | |
public: | |
vector<double> getPoints(vector<int> x, vector<int> m) { | |
vector<double> ret; | |
for(int i = 0;i < x.size() - 1; ++ i){ | |
double lo = x[i], hi = x[i+1]; | |
while(hi - lo > 1e-9){ // bug: why > EPS. because we need to keep search if > EPS | |
double mid = (hi + lo) / 2; | |
double F = 0; // trick: use negative for left force | |
for(int j = 0; j <= i; ++ j){ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class PrimeSoccer { | |
public: | |
using LL = long long; | |
LL C(int n, int m){ | |
LL ans = 1L; | |
for(int i=1;i<=m;++i) | |
ans *= n--; | |
for(int i=1;i<=m;++i) | |
ans /= i; | |
return ans; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// was trying to sum up Pa + Pb_selective {2,3,17} but the probability that both team score a prime should | |
// be calculated this way pA * pB | |
double getProbability(int skillOfTeamA, int skillOfTeamB) { | |
vector<int> aWin = {2,3,5,7,11,13,17}, bWin = {2,3,17}; | |
double ret, pa = skillOfTeamA/100.0, pb = skillOfTeamB/100.0; | |
for(int d : aWin) | |
ret += pow(pa, d)*pow(pb,(18-d))*C(18, d); | |
for(int d: bWin) | |
ret += pow(pb, d)*pow(pa,(18-d))*C(18, d); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public int periodLength(int[] heaps) { | |
ArrayList<Integer> slow = new ArrayList<Integer>(); | |
for (int i=0; i<heaps.length; i++) slow.add(heaps[i]); | |
Collections.sort(slow); | |
ArrayList<Integer> fast = slow; | |
while (true) { | |
slow = step(slow); | |
fast = step(fast); | |
fast = step(fast); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
string getText(vector<string> commands, vector<int> time) { | |
string ret = ""; | |
for(int i=commands.size()-1; i>=0;){ | |
istringstream iss(commands[i]); | |
vector<string> tokens {istream_iterator<string>{iss}, istream_iterator<string>{}}; | |
if(tokens[0]=="undo"){ | |
int ustep = stoi(tokens[1]); | |
int cur_time = time[i]; | |
i-=1; | |
while(i>=0 && cur_time - time[i] <= ustep){ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#define MAX 128 | |
class ArithmeticProgression { | |
public: | |
double minCommonDifference(int a0, vector <int> a) | |
{ | |
int N = SIZE(a); | |
if(N == 0) | |
return 0.0; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// - number theory: r = (r * p10 + number) % k | |
// - 32bit int overflow because of multiplication | |
// - cycle dectection: cyclen length < k, only need to iterate k times | |
public int getSmallest(int number, int k) { | |
long r = number % k, n = number, p10 = 1; | |
while (n > 0) { | |
n /= 10; | |
p10 *= 10; | |
} | |
for (int i = 1; i <= k; ++i) { |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public int getSmallest(int number, int k) { | |
String sn = String.valueOf(number); | |
BigInteger bi = new BigInteger(sn), bk = BigInteger.valueOf(k), z = BigInteger.ZERO; | |
//odd/even = -1 | |
if(number%2!=0 && k%2==0) return -1; | |
int c=1; | |
String s = sn; | |
while(bi.mod(bk)!=z){ | |
//extend | |
s += sn; |
NewerOlder