akhauriyash/Code-Regression huggingface dataset:
def partition(A,p,r):
    x = A[r]
    i = p-1
    for j in xrange(p,r):
        if A[j] <= x:
            i += 1
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp
    tmp = A[i+1]
    A[i+1] = A[r]
    A[r] = tmp
    return i+1

def main():
    n = input()
    A = map(int,raw_input().split())
    pos = partition(A,0,n-1)
    A = map(str,A)
    A[pos] = "["+A[pos]+"]"
    print " ".join(A)

if __name__ == '__main__':
    main()

Measured memory_bytes: 14792
n=int(input())
a=list(map(int,input().split()))

ans=True
for i in range(n):
    if a[i]%2==0:
        if a[i]%3==0 or a[i]%5==0:
            ans = True
        else:
            ans = False
            break
if ans:
    print("APPROVED")
else:
    print("DENIED")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define pb push_back
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

int n, l;
vector <int> v;

void read() {
  cin >> n >> l;
}

int abs(int x) {
  if (x < 0)
    return -x;
  return x;
}

void solve() {
  int apple = 1e9, sum = 0;
  for(int i = 0; i < n; ++i) {
    int nr = l + i;
    sum += nr;
    if (abs(nr) < abs(apple))
      apple = nr;
  }
  cout << sum - apple;
}

int main() {
  ios :: sync_with_stdio(false);
  cin.tie(nullptr);
  read();
  solve();
  return 0;
}


Measured memory_bytes: 256
/***********************
*  Author: xuziyuan    * 
***********************/

#include <bits/stdc++.h>

#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define replet(c) for(char c='a';c<='z';c++) 
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
#define sqr(a) ((a)*(a))

using namespace std;

const LL MOD=1e9+7;

LL n,a[5],b[5],k,ans,dp[25000010];

int main()
{
	cin>>n;
	ans=n;
	rep(i,3) cin>>a[i];
	rep(i,3) cin>>b[i];
	memset(dp,-1,sizeof(dp));
	dp[n]=n;
	for(LL i=n;i>=0;i--)
	{
		rep(j,3)
		{
			if(i-a[j]>=0&&dp[i]!=-1) dp[i-a[j]]=max(dp[i-a[j]],dp[i]-a[j]+b[j]);
		}
	}
	rep(i,n+1) ans=max(ans,dp[i]);
	memset(dp,-1,sizeof(dp));
	dp[ans]=ans;
	//cout<<ans<<endl;
	for(LL i=25000005;i>=0;i--)
	{
		rep(j,3)
		{
			if(i-b[j]>=0) 
			{
				if(i-b[j]>=0&&dp[i]!=-1) dp[i-b[j]]=max(dp[i-b[j]],dp[i]-b[j]+a[j]);
				//if(dp[i]-b[j]+a[j]==92) cout<<i-b[j]<<' '<<i<<' '<<j<<endl;
			}
		}
	}
	LL p=ans;
	rep(i,p+1) ans=max(ans,dp[i]);
	cout<<ans<<endl;
	rt0;
}

Measured memory_bytes: 195584
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
int binsea(vector<int>& v, int k){
    int h = v.size(), l = 0;
    int mid;
    while(l < h){
        mid  = l + (h-l)/2;
        if (v[mid] >= k) 
            h = mid - 1;
        else
            l = mid + 1;
    }
    while(l < v.size() && v[l] < k)
        l++;
    return l;
}



int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> arr[n];
    for(int i = 0; i < m; ++i){
        int u, v;
        scanf("%d%d", &u, &v);
        v--;u--;
        arr[v].push_back(u);
    }
    for (int i = 0; i < n; ++i)
        sort(arr[i].begin(), arr[i].end());
    int dp[n][n];
    for(int i = 0; i < n; ++i){
        int cnt = 0;
        for (int j = i; j < n; ++j){
            //first index in arr[j] which is greater than or equal to i
            cnt += arr[j].size() - binsea(arr[j], i);
            dp[i][j] = cnt;
        }
    }
    while(q--){
        int u, v;
        scanf("%d%d", &u, &v);
        printf("%d\n", dp[u-1][v-1]);
    }
	return 0;
}	



Measured memory_bytes: 3200
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n,m = map(int, input().split())
uf = UnionFind(n)
b = [list(map(int, input().split())) for i in range(m)]
b.reverse()
def kumi(x):
    return x*(x-1)//2
c = kumi(n)
ans = [0 for i in range(m)]
nextans = c
for i,bri in enumerate(b):
    ans[m-1-i] = nextans
    if uf.same(bri[0]-1, bri[1]-1):
        continue
    else:
        a_num = uf.size(bri[0]-1)
        b_num = uf.size(bri[1]-1)
        a_num = kumi(a_num)
        b_num = kumi(b_num)
        uf.union(bri[0]-1, bri[1]-1)
        c_num = uf.size(bri[0]-1)
        c_num = kumi(c_num)
        nextans = nextans - (c_num - a_num - b_num)
for i in range(m):
    print(ans[i])

Measured memory_bytes: 118944
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <numeric>
#include <algorithm>
#include <functional>

#include <vector>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N;
	cin >> N;

	vector<long long> A(N + 1, 0);

	for (int i = 0; i < N + 1; i++)
	{
		cin >> A[i];
	}

	vector<long long> B(N, 0);

	for (int i = 0; i < N; i++)
	{
		cin >> B[i];
	}

	long long result = 0;
	for (int i = 0; i < N; i++)
	{
		if (A[i] <= B[i])
		{
			result += A[i];
			B[i] -= A[i];
			A[i] = 0;
		}
		else
		{
			result += B[i];
			A[i] -= B[i];
			B[i] = 0;
		}

		if (B[i] > 0)
		{
			if (A[i + 1] <= B[i])
			{
				result += A[i + 1];
				B[i] -= A[i + 1];
				A[i + 1] = 0;
			}
			else
			{
				result += B[i];
				A[i + 1] -= B[i];
				B[i] = 0;
			}
		}
	}

	cout << result;

	return 0;
}


Measured memory_bytes: 1792
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[] s = sc.next().toCharArray();
        long ans = Long.MAX_VALUE;
        int[] WL = new int[n];
        int[] EL = new int[n];
        for(int i = 0; i < n; i++){
            if(s[i] == 'E'){
                EL[i]++;
            }else{
                WL[i]++;
            }
            if(i != 0){
                WL[i] += WL[i-1];
                EL[i] += EL[i-1];
            }
        }
        for(int i = 0; i < n; i++){
            if(i == 0){
                ans = Math.min(ans,EL[n-1] - EL[i]);
            }else{
                ans = Math.min(ans,WL[i-1] + EL[n-1] - EL[i]);
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 30820
#include <cstdio>

const int N = 100;

char a[N], b[N], c[N];

int main() {
  int n;
  scanf("%d", &n);
  scanf("%s%s%s", a, b, c);
  int ret = 0;
  for (int i = 0; i < n; ++i) {
    if (a[i] != b[i] && a[i] != c[i] && b[i] != c[i]) ret += 2;
    else if (a[i] == b[i] && a[i] == c[i]) ret += 0;
    else ret += 1;
  }
  printf("%d\n", ret);
  return 0;
}


Measured memory_bytes: 128
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		long X = sc.nextLong();
		
		long ans = X/500*1000 + (X%500/5*5);
		
		System.out.println(ans);

		sc.close();
	}
}


Measured memory_bytes: 22996
#include<iostream>
#include<vector>
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
	if ((x += a.x) >= mod) x -= mod;
	return *this;

    }
    mint& operator-=(const mint a) {
	if ((x += mod-a.x) >= mod) x -= mod;
	return *this;

    }
    mint& operator*=(const mint a) {
	(x *= a.x) %= mod;
	return *this;

    }
    mint operator+(const mint a) const {
	mint res(*this);
	return res+=a;

    }
    mint operator-(const mint a) const {
	mint res(*this);
	return res-=a;

    }
    mint operator*(const mint a) const {
	mint res(*this);
	return res*=a;

    }
    mint pow(ll t) const {
	if (!t) return 1;
	mint a = pow(t>>1);
	a *= a;
	if (t&1) a *= *this;
	return a;

    }

    // for prime mod
    mint inv() const {
	return pow(mod-2);

    }
    mint& operator/=(const mint a) {
	return (*this) *= a.inv();

    }
    mint operator/(const mint a) const {
	mint res(*this);
	return res/=a;

    }

};
// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1),ifact(n+1) {
	assert(n < mod);
	fact[0] = 1;
	for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
	ifact[n] = fact[n].inv();
	for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;

    }
    mint operator()(int n, int k) {
	if (k < 0 || k > n) return 0;
	return fact[n]*ifact[k]*ifact[n-k];

    }

};

int main(void){
    long long n;
    long long k;
    std::cin >> n >> k;
    k = std::min(n-1, k);
    mint ans;
    ans.x = 0;
    combination com = combination(n+1);
    for(int i = 0; i <= k; i++){
	ans += com(n, i) * com((n-1), i);
    }
    std::cout << ans.x << std::endl;
    return 0;
}



Measured memory_bytes: 6372
h, w = map(int, input().split())
field = [input() for i in range(h)]
DXY = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for y in range(h):
	for x in range(w):
		if field[y][x] == '#':
			flag = False
			for dy, dx in DXY:
				ny = y + dy
				nx = x + dx
				if not (0 <= ny < h and 0 <= nx < w):
					continue
				if field[ny][nx] == '#':
					flag = True
					break
			if flag == False:
				print("No")
				exit()
else:
	print("Yes")

Measured memory_bytes: 39664
#pragma GCC optimize("O3") 

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;

#define test(t)		int t; cin >> t; while(t--)
#define f(i, a, b)	for(int (i) = (a); (i) < (b); ++(i))
#define all(a)		(a).begin(), (a).end()
#define endl 		"\n"
#define maxvec(vec)     *max_element(all(vec))
#define minvec(vec)     *min_element(all(vec))
#define maxarr(arr)     *max_element(arr, arr + n)
#define minarr(arr)     *min_element(arr, arr + n)
#define deb(x)		cout << #x << " is " << x << endl;
#define deb2(x,y)	cout << #x << " is " << x << " and " <<  #y << " is " << y << endl;
#define deba(arr)	cout << #arr << " ~ [ "; for(auto n: arr) cout << n << " "; cout << "]" << endl;
#define debap(arr)	cout << #arr << " ~ [ "; for(auto n: arr) cout << n.first << "-" << n.second << " "; cout << "]" << endl;
#define fast 		ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

#define mx9		1000000007
#define mx7		10000007
#define mx6		1000006
#define mx5		200005
#define inf		1<<30                                 
#define eps		1e-9
#define mod		1000000007
#define PI		3.141592653589793238462643383279502884L

void solve()
{
    ll n;
    cin >> n;
    ll a[n], b[mx5] = {0}, sum = 0;
    f(i, 0, n)
    {
        cin >> a[i];
        b[a[i]] += 1;
        sum += a[i];
    }
    
    ll q;
    cin >> q;
    f(i, 0, q)
    {
        ll x, y;
        cin >> x >> y;
        sum = sum - (b[x] * x) + (b[x] * y);
        b[y] += b[x];
        b[x] = 0;
        cout << sum << endl;
    }
}

int main()
{
    fast;
    // test(t)
        solve();
    return 0;
}

Measured memory_bytes: 6008
//#pragma GCC optimize (2)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(v) v.begin(),v.end()
ll quick_pow(ll base, ll n) {
    ll ans = 1;
    while (n ) {
        if (n & 1 )
            ans *= base;
        base *= base;
        n >>= 1;
    }
    return ans;
}
void solve();
int main() {
    int T=1;
    //cin>>T;
    while (T--){
        solve();
    }
    return 0;
}
void solve(){
    int legs ,heads;
    cin>>heads>>legs;
    if (legs&1){
        cout<<"No\n";
        return;
    }
    int  t = legs/2-heads;
    int k = heads-t;
    if (t>= 0 && k>=0 )
        cout<<"Yes\n";
    else
        cout<<"No\n";
}

Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
using namespace std;
#define i64  long long
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()

// int DP[MEM_SIZE][MEM_SIZE] = {0};
// int GMEM[MEM_SIZE][MEM_SIZE] = {0};
template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return;std::cout << e << std::endl;}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T> void DEBUG(string str, T e){if(DEBUG_OUT == false)return;std::cout <<str<<" ";DEBUG(e);};
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }


//CODE
void solve(void)
{  
  int N,M,X,Y;
  cin>>N>>M>>X>>Y;
  int MAX_X = -1*INF, MIN_Y = INF;
  for (int i = 0; i < N; i++)
  {
    int A;
    cin>>A;
    chmax(MAX_X,A);
  }
  for (int i = 0; i < M; i++)
  {
    int A;
    cin>>A;
    chmin(MIN_Y,A);
  }
  bool check = false;
  for (int i = MAX_X+1; i <= MIN_Y; i++)
  {
    if(X < i && i <= Y)
    {
      check = true;
    }
  }

  cout<<(check?"No War":"War")<<endl;
  
  
  
  
  
  
  
  return;
}


int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();
  

 
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <numeric>
using namespace std;
#define MAX_N 200000

template<class T> inline bool chmax(T& a, T b) { if(a < b) {a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if(a > b) {a = b; return true; } return false; }
const long long INF = 1LL << 60;

// Input
int K, N;
int A[MAX_N];

int main() {
  cin >> K >> N;
  for (int i = 0; i < N; i++) cin >> A[i];

  int max_diff = 0;
  int tmp = A[N-1];
  for (int i = N-1; i > 0; i--) {
    A[i] -= A[i-1];
  }
  A[0] = A[0] + K - tmp;
  for (int i = 0; i < N; i++){
    chmax(max_diff, A[i]);
  }
  cout << K - max_diff << endl;
}


Measured memory_bytes: 1024
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = 0
for i in range(N-1):
    a = A[i]-1
    b = B[a]
    ans+=b
    if a+1 == A[i+1]-1:
        c = C[a]
        ans+=c
ans+=B[A[-1]-1]
print(ans)

Measured memory_bytes: 38384
#include<iostream>
using namespace std;

int Merge(int A[], int left, int mid, int right){
	int n1 = mid - left;
	int n2 = right - mid;
	int L[n1+1], R[n2+1];
	int cnt = 0;
	
	for(int i=0; i<n1; i++){
		L[i] = A[left + i];
	}
	for(int i=0; i<n2; i++){
		R[i] = A[mid + i];
	}
	L[n1] = 1000000000;
	R[n2] = 1000000000;
	
	int i=0, j=0;
	
	for(int k=left; k<right; k++){
		if(L[i] <= R[j]){
			A[k] = L[i];
			i++;
			cnt++;
		}else{
			A[k] = R[j];
			j++;
			cnt++;
		}
	}
	
	return cnt;
}

int Merge_Sort(int A[], int left, int right){
	int cnt = 0;
	
	if(left+1 < right){
		int mid = (left + right)/2;
		cnt += Merge_Sort(A, left, mid);
		cnt += Merge_Sort(A, mid, right);
		cnt += Merge(A, left, mid, right);
	}
	
	return cnt;
}


int main(void){
	int A[500000], n, left, right, cnt;
	
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> A[i];
	}
	
	left = 0;
	right = n;
	
	cnt = Merge_Sort(A, left, right);
	
	for(int i=0; i<n-1; i++){
		cout << A[i] << " ";
	}
	cout << A[n-1] << "\n";
	
	cout << cnt << "\n";
	
	return 0;
}


Measured memory_bytes: 6928
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;

  vector<int> cnt(n);

  ll MOD = 998244353;

  int d0;
  cin >> d0;

  int tmp;
  int len_max = 0;
  for(int i = 1; i < n; i++){
    cin >> tmp;
    cnt[tmp]++;
    chmax(len_max, tmp);
  }

  if(d0 > 0 || cnt[0] > 0){
    cout << 0 << endl;
  }else{
    ll ans = 1;

    for(int i = 2; i <= len_max; i++){
      for(int j = 0; j < cnt[i]; j++){
        ans *= cnt[i-1];
        ans = ans % MOD;
      }
    }
    cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define per(i,n) for(int i = n-1; i >= 0; i--)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;

int main() {
  ll n;
  cin >> n;
  map<ll,ll> mp;
  rep(i,n) {
    ll a;
    cin >> a;
    mp[a]++;
  }
  ll ans = 0;
  rep(i,100000) {
    ll cnt = 0;
    rep(j,3) cnt += mp[i+j];
    ans = max(ans,cnt);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 6656
import Control.Applicative ((<$>), (<*>))
import Control.Monad
import Data.List

main :: IO ()
main = do
  x <- getl toInt
  h <- getl toInt
  when (x /= 0 || h /= 0) $ do
    print $ solve x h
    main
    
solve :: Int -> Int -> Double
solve x h = as + at4
  where
    as = (fromIntegral x) ^ 2
    at4 = 2.0 * (fromIntegral x) * l
    l = sqrt $ (fromIntegral h) ^ 2 + (fromIntegral x) ^ 2 / 4.0
    
toInt :: String -> Int
toInt s = read s

getl :: (String -> a) -> IO a
getl f = f <$> getLine

Measured memory_bytes: 3948
#include<stdio.h>
#define N 2000
#define L 2000

int n, A[N], M[L];
int saiki(int, int);


int main(){
  int i, m;

  scanf("%d", &n);
  for(i=0;i<n;i++) scanf("%d", &A[i]);

  scanf("%d",&m);
  for(i=0;i<m;i++) scanf("%d", &M[i]);

  for(i=0;i<m;i++){

    if(saiki(0, M[i]) == 1)printf("yes\n");
  else printf("no\n");

  }

  return 0;

}

int saiki(int j, int m){
  int a;
  a = m - A[j];
  if(j > n) return 0;
  else if(a == 0) return 1;
  else if(saiki(j+1, m)==1)return 1;
  else if(saiki(j+1, a)==1)return 1;
}

Measured memory_bytes: 584
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()

l = []
for i in t:
    if i == "r":
        l.append("p")
    elif i == "s":
        l.append("r")
    else:
        l.append("s")
#print(l)
for i in range(k, n):
    if l[i] == l[i-k]:
        l[i] = "a"
#print(l)
for i in range(len(l)):
    if l[i] == "r":
        l[i] = r
    elif l[i] == "s":
        l[i] = s
    elif l[i] == "a":
        l[i] = 0
    else:
        l[i] = p
#print(l)
print(sum(l))   

Measured memory_bytes: 46516
while 1:
        n = map(int,raw_input().split())
        if n[0] == n[1] == 0:
                break
        m, o = [1 for x in range(n[0])], 0

        for x in range(1,n[1]+1):
                a = raw_input()
                if sum(m) == 1:
                        pass
                elif x % 15 == 0:
                        if a != "FizzBuzz":
                                m[o] = 0
                elif x % 3 == 0:
                        if a != "Fizz":
                                m[o] = 0
                elif x % 5 == 0:
                        if a != "Buzz":
                                m[o] = 0
                else:
                        if a != str(x):
                                m[o] = 0
                while 1:
                        o += 1
                        if sum(m) == 1:
                                break
                        elif o == len(m):
                                o = -1
                        elif m[o] == 1:
                                break

        OutPut = ""
        for x in range(n[0]):
                if m[x] == 1:
                        OutPut += str(x+1) + " "
        print OutPut[:-1]

Measured memory_bytes: 4584
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define SP << " " 
#define LLi long long int

using namespace std;

int imax=2147483647;
long long int llimax=9223372036854775807;

//int型vectorを出力
void PV(vector<int> pvv) {
	rep(i, pvv.size()) cout << pvv[i] SP;
	cout << endl;
}

//LLi型vectorを出力
void PVL(vector<LLi> pvv) {
	rep(i, pvv.size()) cout << pvv[i] SP;
	cout << endl;
}

int main(){

	LLi n, mi=imax, dlt;
	LLi ans=0, ami;
	vector<LLi> v;

	cin>> n;
	v.resize(n);

	rep(i, n){
		cin >> v[i];
		v[i]-=i+1;
		mi=min(mi, v[i]);
	}

	rep(i, n) ans+=v[i]-mi;
	ami=ans;
	sort(v.begin(), v.end());
	//cout<< ans <<endl;//

	for(int i=1;i<n;i++){
		dlt=v[i]-v[i-1];
		ans+=dlt*i;
		ans-=dlt*(n-i);
		ami=min(ami, ans);
		//cout<< ans <<endl;//
	}

	cout<< ami <<endl;
 
	return 0;
}

Measured memory_bytes: 4812
from sys import setrecursionlimit as srl; srl(10**7)
rr = raw_input
rrm = lambda: map(int, raw_input().split())

N =int(rr())
from collections import Counter
count = Counter()
for _ in xrange(N):
    count[rr()] += 1
M = max(count.values())
ans = []
for k in count:
    if count[k] == M:
        ans.append(k)
ans.sort()
for x in ans:
    print x


Measured memory_bytes: 73608
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import Data.List (unfoldr)

main :: IO ()
main = do
  (n : _) <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  mapM_ putStrLn . map (map (toEnum . (fromEnum 'a' +))) . fromTree n . head . toTrees $ 0

data Tree = Node Int [Tree]

toTrees :: Int -> [Tree]
toTrees m = map (Node <$> id <*> (toTrees . max m . succ)) [0..m]

fromTree :: Int -> Tree -> [[Int]]
fromTree 1 (Node k _) = [[k]]
fromTree n (Node k ts) = map (k :) (concatMap (fromTree (pred n)) ts)

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 4732
#include<bits/stdc++.h>
using namespace std;
#define pi acos(-1.0)
//cout << fixed << setprecision(8) << a << endl;
#define Fast_Input ios_base :: sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
#define pb push_back
#define mem(a, b)     memset(a, b, sizeof(a))
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<int,null_type,greater<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
/*sort(v.begin(), v.end(),
     [](const pair<int, int>& x, const pair<int, int>& y)
{
    if (x.first != y.first)
        return x.first < y.first;
    return x.second < y.second;
});
*/
int const fx[]= {+1,+0,-1,+1};
int const fy[]= {-1,+1,+0,+0};
const int inf = numeric_limits<int>::max();
const int mx=1e9;
const int mod=1e9+7;
int main()
{
    int n,i;
    cin >> n;
    vector<int>v(n);
    for(i=0;i<n;i++)cin >> v[i];
    ll prev=v[0],sum=0;
    for(i=1;i<n;i++)
    {
        if(v[i]<prev)
        {
            sum+=(prev-v[i]);
        }
        else
            prev=v[i];
    }
    cout << sum << endl;
    return 0;
}




Measured memory_bytes: 4024
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 111111
typedef unsigned long long ull;
ull MOD=1000000007LL;
vector<int> G[MAX_N];
int n;
map<ull,ull> m;
ull dfs(int p){
  ull res=1LL;
  for(int i=0;i<(int)G[p].size();i++)
    res+=dfs(G[p][i])*MOD;
  m[res]++;
  return res;
}
int main(){
  cin>>n;
  for(int i=0;i<n-1;i++){
    int a,b;
    cin>>a>>b;
    G[a].push_back(b);
  }
  dfs(1);
  ull ans=0;
  for(auto i:m) ans+=i.second*(i.second-1)/2;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 21308
H,W = gets.split.map(&:to_i)
ch = Hash[("a".."z").map{ |a| [a,0] }]
H.times{ gets.chomp.split("").each{ |a| ch[a]+=1 } }
p4 = ch.values.reduce(0){ |t,a| t + a/4 }
p2 = ch.values.reduce(0){ |t,a| t + a/2 }
puts p4 >= (H/2)*(W/2) && p2 >= H*W/2 ? "Yes" : "No"


Measured memory_bytes: 2044
using Base.Collections
using Base.Order

parseInt(x) = parse(Int, x)
parseArray(x::Array{SubString{String}, 1}) = map(parseInt, x)

function main()
  n,m_days = readline() |> split |> parseArray
  a_days=zeros(Int,n)
  b_salary=zeros(Int,n)
  for i in 1:n
    a_days[i],b_salary[i]= readline() |> split |> parseArray
  end

  pq=PriorityQueue(Int[],Int[],Reverse)

  ix=sortperm(a_days)
  a_days=a_days[ix]
  b_salary=b_salary[ix]

  i=1
  days=1
  ans=0
  while days<=m_days
    j=i
    while j<=n && a_days[j]<=days
      enqueue!(pq, j,b_salary[j])
      j+=1
    end
    i=j

    if !isempty(pq)
      j=dequeue!(pq)
      ans+=b_salary[j]
    end
    days+=1
  end

  println(ans)
end

main()


Measured memory_bytes: 166024
R,C,k=map(int,input().split())
rcv = [[0 for _ in range(C+1)] for _ in range(R+1)]
for i in range(k):
  r,c,v = map(int,input().split())
  rcv[r][c] = v
# dp: 各場所までの合計の最大値
dp0=[[0 for _ in range(C+1)] for _ in range(R+1)]
dp1=[[0 for _ in range(C+1)] for _ in range(R+1)]
dp2=[[0 for _ in range(C+1)] for _ in range(R+1)]
dp3=[[0 for _ in range(C+1)] for _ in range(R+1)]
dp1[1][1] = rcv[1][1]
for r in range(1,R+1):
  for c in range(1,C+1):
    dp1[r][c] = max(dp0[r][c]+rcv[r][c],dp0[r][c-1]+rcv[r][c],dp1[r][c-1])
    dp2[r][c] = max(dp1[r][c-1]+rcv[r][c],dp2[r][c-1])
    dp3[r][c] = max(dp2[r][c-1]+rcv[r][c],dp3[r][c-1])
    
    if r < R:
      dp0[r+1][c] = max(dp0[r][c],dp1[r][c],dp2[r][c],dp3[r][c])
print(max(dp0[R][C],dp1[R][C],dp2[R][C],dp3[R][C]))

Measured memory_bytes: 463452
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define debug3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define debugB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

template<typename T>
void printA(vector<T> &printArray, char between = ' ') {
   int paSize = printArray.size();
   for (int i = 0; i < paSize; i++) { cerr << printArray[i] << between;}
   if (between != '\n') {cerr << endl;}
}

// ------------------------------------------------------------------------------------------

int n, W;
int weight[110], value[110];

int dp[110][10010];

int main() {
   cin >> n >> W;
   rep (i, n) cin >> value[i] >> weight[i];

   rep (i, W+1) dp[0][W] = 0;

   for (int i = 0; i < n; i++) {
      for (int w = 0; w <= W; w++) {
         if (w >= weight[i]) {
            dp[i+1][w] = max(dp[i][w-weight[i]] + value[i], dp[i][w]);
         } else {
            dp[i+1][w] = dp[i][w];
         }
      }
   }

   cout << dp[n][W] << endl;

   return 0;
}


Measured memory_bytes: 7012
#include<iostream>
#include<algorithm>
using namespace std;
int a[4], b[2];
int main() {
	for (int i = 0; i < 4; i++)cin >> a[i];
	for (int i = 0; i < 2; i++)cin >> b[i];
	sort(a, a + 4); sort(b, b + 2);
	cout << a[1] + a[2] + a[3] + b[1] << endl;
	return 0;
}

Measured memory_bytes: 1176
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

//-------------------------------------------------
//--ModInt
//-------------------------------------------------
const ::std::uint_fast64_t MOD = 1e9+7;

class mint
{
private:
    using value_type = ::std::uint_fast64_t;
    value_type n;
public:
    mint():n(0){}
    mint(::std::int_fast64_t _n):n(_n<0 ? MOD-(-_n)%MOD : _n%MOD){}
    mint(const mint &m):n(m.n){}

    friend ::std::ostream& operator<<(::std::ostream &os, const mint &a){
		return os << a.n;
	}
    friend ::std::istream& operator>>(::std::istream &is, mint &a){
        value_type temp; is>>temp;
        a = mint(temp);
        return is;
    }

    mint& operator+=(const mint &m){n+=m.n; n=(n<MOD)?n:n-MOD; return *this;}
    mint& operator-=(const mint &m){n+=MOD-m.n; n=(n<MOD)?n:n-MOD; return *this;}
    mint& operator*=(const mint &m){n=n*m.n%MOD; return *this;}
    mint& operator/=(const mint &m){return *this*=m.inv();}
    mint& operator++(){return *this+=1;}
    mint& operator--(){return *this-=1;}

    mint operator+(const mint &m) const {return mint(*this)+=m;}
    mint operator-(const mint &m) const {return mint(*this)-=m;}
    mint operator*(const mint &m) const {return mint(*this)*=m;}
    mint operator/(const mint &m) const {return mint(*this)/=m;}
    mint operator++(int){mint t(*this); *this+=1; return t;}
    mint operator--(int){mint t(*this); *this-=1; return t;}

    mint operator==(const mint &m) const {return n==m.n;}
    mint operator!=(const mint &m) const {return n!=m.n;}
    mint operator-() const {return mint(MOD-n);}

    mint pow(value_type b) const {
        mint ret(1), m(*this);
        while(b){
            if (b & 1) ret*=m;
            m*=m;
            b>>=1;
        }
        return ret;
    }

    mint inv() const {return pow(MOD-2);}
};

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m; cin>>n>>m;
    vi s(n),t(m);
    rep(i,n) cin>>s[i];
    rep(i,m) cin>>t[i];
    vector<vector<mint> > dp(n+1, vector<mint>(m+1));
    rep(i,n+1) dp[i][0] = 1;
    rep(j,m+1) dp[0][j] = 1;
    rep(i,n)rep(j,m){
        if (s[i]==t[j]){
            dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j];
        }else{
            dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]-dp[i][j];
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}


Measured memory_bytes: 31616
#include<bits/stdc++.h>
using namespace std;

typedef long long lint;
typedef long double louble;

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

namespace ae86
{
	const int bufl = 1<<15;

	char buf[bufl],*s=buf,*t=buf;

	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}

	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}
}
using ae86::ty;

const double eps = 1e-11;

inline int dcmp(double x){if(-eps<x && x<eps)return 0;return x>0?1:-1;}

struct points
{
	double x,y;
	points(double _x=0,double _y=0){x=_x,y=_y;}

	inline friend points operator + (points a,points b){return points(a.x+b.x,a.y+b.y);}
	inline friend points operator - (points a,points b){return points(a.x-b.x,a.y-b.y);}
	inline friend points operator * (points a,double b){return points(a.x*b,a.y*b);}
	inline friend points operator / (points a,double b){return points(a.x/b,a.y/b);}

	inline friend int operator == (points a,points b){return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;}

	void takein(){x=ty(),y=ty();}
	void print(char ends='\n'){printf("%.12lf %.12lf",x,y),putchar(ends);}
};

inline double dox(points a,points b){return a.x*b.x+a.y*b.y;}
inline double cox(points a,points b){return a.x*b.y-a.y*b.x;}
inline double length(points a){return sqrt(dox(a,a));}

inline points pervec(points a){if(dcmp(length(a))<=0)return points(0,0);return a/length(a);}

void finder()
{
	points al,ar,bl,br;
	al.takein(),ar.takein(),bl.takein(),br.takein();

	points a=ar-al,b=br-bl;
	double cx=cox(a,b),dx=dox(a,b);
	
	if(dcmp(cx)==0)puts("2");
	else if(dcmp(dx)==0)puts("1");
	else puts("0");
}

int main()
{
	int q=ty();
	while(q--)finder();
	
	return 0;
}



Measured memory_bytes: 3120
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il print(T x){
	if(x/10) print(x/10);
	putchar(x%10+'0');
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(res*bas)%mod;
		bas=(bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 2e3+5,mod = 1e9+7;
int n,k,val[MAXN],sum,ans,T[MAXN],bas;
il updata(int pos,int k){for(;pos<=2000;pos+=lowbit(pos)) T[pos]+=k;}
it query(int pos){ri res=0;for(;pos;pos-=lowbit(pos)) res+=T[pos];return res;}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(k),bas=(1ll*k*(k-1)/2)%mod;
	for(ri i=1;i<=n;++i) read(val[i]),sum+=i-1-query(val[i]),updata(val[i],1);
	for(ri i=1;i<=n;++i) ans+=query(val[i]-1);
	ans=(1ll*bas*ans)%mod;
	print((ans+1ll*k*sum%mod)%mod);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef HIRO
#define d(f_, ...) printf((f_), ##__VA_ARGS__)
#else
#define d(f_, ...)
#endif

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pllll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector< pair<int, int> > vii;
typedef vector< pair<long long, long long> > vllll;
typedef map<int, int> mii;
typedef map<long long, long long> mllll;
typedef queue<int> qi;
typedef queue< pair<int, int> > qp;
#define mp make_pair
#define pi 3.14159265358979323846
#define MAX max_element
#define MIN min_element
#define all(v) v.begin(), v.end()
#define gt(T) greater<T>()
#define sum(v) accumulate(v.begin(), v.end(), 0ll)
#define uni(v) do{ \
  sort(v.begin(), v.end()); \
  decltype(v)::iterator result = unique(v.begin(), v.end()); \
  v.erase(result, v.end()); \
}while(0)
#define fi(init, n) for(int i = init; i < n; ++i)
#define fj(init, n) for(int j = init; j < n; ++j)
#define fk(init, n) for(int k = init; k < n; ++k)
#define zero(x) memset(x, 0, sizeof(x))
#define negative(x) memset(x, ~0, sizeof(x))
#define bitsum(x) __builtin_popcount(x)
const ll MOD = 1e9 + 7;
const int INF = 1e9;
const int di[] = { 0, 1, 0, -1 };
const int dj[] = { 1, 0, -1, 0 };

template<typename T>
T gcd(T a, T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	return a / gcd(a, b) * b;
}
template<typename T>
int finder(vector<T> vec, T number) {
	auto itr = find(vec.begin(), vec.end(), number);
	size_t index = distance(vec.begin(), itr);
	if (index != vec.size()) return 1;
	else return 0;
}
ll frac(ll n){
	if (n == 0) return 1;
	return (n * frac(n - 1)) % MOD;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
int prime[100010];
int res[100010];
int main(int argc, char** argv) {
#ifdef HIRO
  string quiz(argv[1]);
  string id(argv[2]);
  string filename("input/" + quiz + "/" + id + ".txt");
  ifstream fin(filename);
  if (fin.peek() == ifstream::traits_type::eof()) {
    cout << "No input.";
    return 0;
  }
  ifstream cin(filename);
  std::cin.rdbuf(cin.rdbuf());
#endif
  ll ans = 0;
  ll q;
  cin >> q;
  // ll n, m;
  // cin >> n >> m;
  // ll n, m, k;
  // cin >> n >> m >> k;
  negative(prime);
  prime[1] = 0;
  prime[2] = 1;
  fi(3, 100001) {
    if(i % 2 == 0) {
      prime[i] = 0;
      continue;
    }
    prime[i] = 1;
    for(int j = 3; j <= sqrt(i); j += 2)
      if(i % j == 0) {
        prime[i] = 0;
        break;
      }
    // printf("%d: %d\n", i, prime[i]);
  }
  fi(1, 100001) {
    res[i] = res[i - 1];
    if(i % 2 == 0) continue;
    if(prime[i] && prime[(i + 1) / 2])
      res[i]++;
  }
  int l, r;
  fk(0, q) {
    cin >> l >> r;
    // printf("%d: %d, %d: %d\n", r, res[r], l - 1, res[l - 1]);
    cout << res[r] - res[l - 1] << endl;
  }
  // cout << ans << endl;
  return 0;
}



Measured memory_bytes: 1408
#include <iostream>

int main()
{
    int money = 0;
    std::cin >> money;

    long long happiness = 0;
    if (money >= 500)
    {
        auto count = money / 500;
        money -= (count * 500);
        happiness += 1000 * count;
    }

    if (money >= 5)
    {
        auto count = money / 5;
        happiness += 5 * count;
    }

    std::cout << happiness;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

#define rep(i,n) for(int i = 0; i < n; i++)

struct Team {
	int no, time;
	map<int, int> wa;
	set<int> ac;
	Team() : time(0) {}
	bool operator < (const Team &other) {
		if (ac.size() == other.ac.size()) {
			if (time == other.time) {
				return no < other.no;
			}
			return time > other.time;
		}
		return ac.size() < other.ac.size();
	}
	bool operator == (const Team &other) {
		return ac.size() == other.ac.size() && time == other.time;
	}
};

int main() {
	int M, T, P, R;
	while (cin >> M >> T >> P >> R && M) {
		vector<Team> teams(T);
		rep(i, T) {
			teams[i].no = i + 1;
		}
		rep(i, R) {
			int m, t, p, j;
			cin >> m >> t >> p >> j;
			t--;
			if (j == 0) {
				teams[t].time += teams[t].wa[p] * 20 + m;
				teams[t].ac.insert(p);
			}
			else {
				teams[t].wa[p]++;
			}
		}
		sort(teams.begin(), teams.end());
		reverse(teams.begin(), teams.end());
		rep(i, T-1) {
			cout << teams[i].no;
			if (teams[i] == teams[i + 1]) {
				cout << "=";
			}else{
				cout << ",";
			}
		}
		cout << teams.back().no << endl;
	}

	return 0;
}

Measured memory_bytes: 3152
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}

int main() {
	ll x;
	cin >> x;
	ll year = 0;
	ll ans = 100;
	while (ans < x) {
		ans += ans / 100;
		year++;
	}
	cout << year << endl;
	return 0;
}

Measured memory_bytes: 3584
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;

typedef complex<long double> P;

template<typename D=long double,typename P=complex<long double>>
struct Geometry{
    const D EPS=1e-9;
    
    P project(P vec,P x){return vec*(x/vec).real();}
    
    P project(P p1,P p2,P x){return p1+project(p2-p1,x-p1);}
    
    P reflect(P vec,P x){return vec*conj(x/vec);}
    
    P reflect(P p1,P p2,P x){return p1+reflect(p2-p1,x-p1);}
};



int main(){
    Geometry<long double,complex<long double>> G;
    P a[2];
    for(int i=0;i<2;i++){
        long double x,y;
        cin>>x>>y;
        a[i]={x,y};
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        long double x,y;
        cin>>x>>y;
        P K={x,y};
        P ans=G.reflect(a[0],a[1],K);
        cout<<fixed<<setprecision(12)<<ans.real()<<" "<<ans.imag()<<endl;
    }
    
    
    return 0;
}



Measured memory_bytes: 3296
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 29;
 
int main() {
	vector<int> letter(26, 0);
	string s;
	cin >> s;
	rep(i,s.size()) {
		char c = s[i];
		letter[c-'a']++;
	}
	rep(i, 26) {
		if (letter[i] == 0) {
			cout << char('a' + i) << endl;
			return 0;
		}
	}
	cout << "None" << endl;
	return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
int main()
{
  int a, b;
  scanf("%d %d", &a, &b);
  if(a == 1) a=14;
  if(b == 1) b=14;
  if(a > b) printf("Alice");
  else if(a == b) printf("Draw");
  else printf("Bob");
  return 0;
}

Measured memory_bytes: 128
#include "bits/stdc++.h"
#define BUGAVOID(x) x
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define rep(...) BUGAVOID(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define unq(v) v.erase(unique(v.begin(),v.end()),v.end());
#define mp make_pair
#define write(x) cout<<(x)<<endl
#ifdef LOCAL
#define debug(...) debug_vars(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#endif
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; }return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; }return 0; }
const int INF = 1 << 28;
const double EPS = 1e-8;
const int MOD = 1e9 + 7;
const int MAX = 1e5 + 10;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); }; }aaaa;

int pattern[15];
int getPattern(const int n) {
    if (n < 2) return 1;
    if (pattern[n]) return pattern[n];
    ll cnt = 0;
    rep(flen, 1, n + 1) {
        cnt += getPattern(n - flen);
    }
    pattern[n] = cnt;
    return cnt;
}

int num[15];

int main()
{
    string s;
    cin >> s;
    int len = s.size();
    rep(i, len) num[i] = s[i] & 0x0F;
    
    ll sum = 0;
    rep(i, 0, len) {
        rep(l, 1, len - i + 1) {
            ll val = stoll(s.substr(i, l));
            sum += val * getPattern(i) * getPattern(len - i - l);
        }
    }
    write(sum);
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
constexpr int inf=1e9+7;
constexpr ll longinf=1LL<<60 ;
constexpr ll mod=1e9+7 ;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll a,b,c;
    cin>>a>>b>>c;
    if(a+b>c){
        cout<<"No"<<endl;
    }
    else if(4*a*b<(c-a-b)*(c-a-b)){
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(void){
	while( 1 ){
		int s = 0;
		int d;
		int a, b, n;

		
		cin >> a >> b >> n;
		if( cin.eof() )break;
		
		d = a / b; a = (a - d * b) * 10;
		while( n > 0 ){
			int d = a / b;
			a = (a - d * b) * 10;
			n--;
			s += d;
		}

		cout << s << endl;
	}
}

Measured memory_bytes: 0
#include <iostream>
#include <math.h>
#include <limits>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <map>
using namespace std;
#define rep(i, n) for (int i =0; i < (int)(n); i++)
typedef pair<int, string> P;


int main() {
    int N, M;
    cin >> N >> M;

    vector<int>  AC(N), P(N);

    int p;
    string s;
    rep(i, M) {
        cin >> p >> s;
        p = p - 1;
        if (AC[p] > 0)continue;
        if (s == "AC")AC[p] = 1;
        else P[p]++;
    }
    int A = 0, B =0 ;

    rep(i, N) {
        A += AC[i];
        if (AC[i] == 1)B += P[i];
    }
    cout << A << " " << B << endl;
}

Measured memory_bytes: 1024
#include <stdio.h>
 
int main(void) {
    int arr[5];
    int i,j;
    int temp;
    for(i=0;i<5;i++)scanf("%d",&arr[i]);
    for(i=4;i>0;i--) {
        for(j=0;j<i;j++) {
            if(arr[j]<arr[j+1]) {
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
    printf("%d %d %d %d %d\n",arr[0],arr[1],arr[2],arr[3],arr[4]);
    return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
#define f(i,n) for(int i=0;i<n;i++)
#define P pair<int,int>
#define F first
#define S second
#define int long long
#define mod 1000000007
#define mmod 998244353
#define all(v) v.begin(), v.end()
#define INF LLONG_MAX/3
using namespace std;
int mypow(int fa, int fb, int fc) {
	if (fb == 0)return 1;
	if (fb % 2)return mypow(fa, fb - 1, fc)*fa%fc;
	int z = mypow(fa, fb / 2, fc);
	return z * z%fc;
}
int k(int fa) {
	int x = 0;
	while (fa) {
		x++;
		fa /= 10;
	}
	return x;
}
int gcd(int fa, int fb) {
	if (fb == 0)return fa;
	return gcd(fb, fa%fb);
}
int a[50], b[50], c[50], d[50], n, m, q, z[10], ans = 0;
void mutu(int fn, int fm) {
	if (fn == 0) {
		int sum = 0;
		f(i, q) {
			if (z[b[i] - 1] - z[a[i] - 1] == c[i])sum += d[i];
		}
		ans = max(sum, ans);
		return;
	}
	for (int i = fm; i <= m; i++) {
		z[n - fn] = i;
		mutu(fn - 1, i);
	}
	return;
}
signed main() {
	cin >> n >> m >> q;
	f(i, q)cin >> a[i] >> b[i] >> c[i] >> d[i];
	mutu(n, 1);
	cout << ans << endl;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long int n,k;
	cin>>k>>n;
	long long int arr[n],dist[n],minD;
	for(long long int i=0;i<n;i++)
		cin>>arr[i];
	dist[0]=min(arr[n]-arr[0],arr[0]+(k-arr[1]));
	// cout<<dist[0];
	minD=dist[0];
	for(long long int i=1;i<n-1;i++)
	{
		dist[i]=min(arr[n-1]-arr[i] + k-arr[n-1] + arr[i-1],arr[i]+(k-arr[i+1]));
		// cout<<dist[i]<<endl;
		if(dist[i]<minD)
			minD=dist[i];
	}
	dist[n-1]=min(arr[n-1]-arr[0],k-arr[n-1]+arr[n-2]);
	if(dist[n-1]<minD)
			minD=dist[n-1];
	cout<<minD<<endl;
	return 0;
}

Measured memory_bytes: 3328