akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std;
string to_string(string s) {
  return '"' + s + '"';
}
string to_string(const char* s) {
  return to_string((string) s);
}
string to_string(bool b) {
  return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifndef ONLINE_JUDGE
#define show(...) cerr << "[" << #__VA_ARGS__ << "] :", debug_out(__VA_ARGS__)
#else
#define show(...) 42
#endif
#define ff first
#define ss second
#define endl "\n"
#define pb push_back
#define  oo 1e15
#define limit 1000000007
#define two pair<int,int>
#define ll long long int
#define int long long int
#define mod(x,m) ((x%m+m)%m)
#define all(v) v.begin(),v.end()
#define max3(x,y,z) max(x,max(y,z))
#define min3(x,y,z) min(x,min(y,z))
#define fori(x,n) for(int i = x; i < n; i++)
#define forj(y,m) for(int j = y; j < m; j++)
#define fork(z,p) for(int k = z; k < p; k++)
#define speedforces std::ios::sync_with_stdio(false)
#define input_from_file  freopen("input.txt", "r", stdin);
#define output_to_file  freopen("output.txt", "w", stdout);

signed main(){
  //input_from_file;
  speedforces;
  int n,k; cin>>n>>k;
  vector<int> v(n+1);
  fori(1,n+1) cin>>v[i];
  int dp[n+1];
  fori(0,n+1) dp[i] = oo;
  dp[1] = 0; dp[2] = abs(v[2]-v[1]);
  fori(3,n+1) forj(max(0ll,i-k),i)
  dp[i] = min(abs(v[i]-v[j])+dp[j],dp[i]);
  cout<<dp[n]<<endl;
 }


Measured memory_bytes: 1792
# ref: https://atcoder.jp/contests/abc147/submissions/8873191

import sys
input = sys.stdin.buffer.readline

H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
B = [list(map(int,input().split())) for _ in range(H)]

# 負の値を表現するために、下駄を履かせる
# 偏りdが0のとき、X桁目が1になる

X = (H + W) * 80

# dp[i][j]: (i,j)で偏りの状態
dp = [[0] * W for _ in range(H)]

# 初期条件
d = abs(A[0][0] - B[0][0])
dp[0][0] = (1 << (X - d))

# 貰うDP
for i in range(H):
    for j,(a,b) in enumerate(zip(A[i],B[i])):
        if i == j == 0:
            continue

        # (i,j)の偏り
        d = abs(a - b)

        tmp = 0
        # (i-1,j)からの遷移
        if i:
            tmp |= (dp[i-1][j] << d) 
            tmp |= (dp[i-1][j] >> d)
        # (i,j-1)からの遷移
        if j:
            tmp |= (dp[i][j-1] << d) 
            tmp |= (dp[i][j-1] >> d)

        dp[i][j] = tmp

dp = dp[-1][-1]

# 二進数に変換して、先頭の0bを削除する
B = bin(dp)[2:]
can_make = [i - X for i,b in enumerate(B[::-1]) if b == '1']

answer = min(tmp if tmp >= 0 else -tmp for tmp in can_make)
print(answer)

Measured memory_bytes: 59228
#include <bits/stdc++.h> //library
#define rep(i, n) for(int i = 0; i < (int)(n); i++) //for-loop (from 0)
#define reps(i,n) for(int i = 1; i <= (int)(n); i++) //for-loop (from 1)
#define all(x) (x).begin(),(x).end() //start-to-end iteration, mainly in upper_bound, lower_bound
#define SZ(x) ((int)(x).size()) //unsigned to signed

using namespace std;
using ll = long long; //long long
ll M = 1000000000 + 7;
const ll INF = 1LL << 60;

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; } //compare a,b and replace by greater
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; } //compare a,b and replace by smaller
ll qp(int a, ll b) { int ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; } //power
ll qp(int a, ll b, ll Mod = M) { int ans = 1; do { if (b & 1)ans = 1ll * ans*a%Mod; a = 1ll * a*a%Mod; } while (b >>= 1); return ans; } //power(mod)
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } //gcd
int dx[4] = { 1,0,-1,0 }; //path
int dy[4] = { 0,1,0,-1 }; //path
ll RS(ll N, ll P, ll Mod = M) { if (P == 0)return 1; else if (P % 2 == 0) { ll sq = RS(N, P / 2, Mod); return sq*sq%Mod; } else { return N*RS(N, P - 1, Mod) % Mod; } } //power(mod)(repeat-square,fast)
ll nPr(ll n, ll r, ll Mod = M) { ll ans = 1; rep(i, r) { ans = ans * (n - i) % Mod; } return ans; } //permutation
ll nCr(ll n, ll r, ll Mod = M) { ll bunbo = 1; ll bunshi = 1; rep(i, r) { bunbo = bunbo * (i + 1) % Mod; bunshi = bunshi * (n - i) % Mod; } return bunshi * RS(bunbo, Mod - 2, Mod) % Mod; } //combination

int main(void) {
  int H,W; cin >> H >> W;
  char graph[H+2][W+2];
  vector<vector<int>> row_wall(H+2,vector<int>()),column_wall(W+2,vector<int>());
  rep(i,H+2){
    rep(j,W+2){
      if (i == 0 || i == H+2-1){
        graph[i][j] = '#';
        row_wall[i].push_back(j);
        column_wall[j].push_back(i);
        continue;
      }
      if (j == 0 || j == W+2-1){
        graph[i][j] = '#';
        row_wall[i].push_back(j);
        column_wall[j].push_back(i);
        continue;
      }
      cin >> graph[i][j];
      if (graph[i][j]=='#'){
        row_wall[i].push_back(j);
        column_wall[j].push_back(i);
      }
    }
  }
  int ans = 0;
  rep(i,H+2){
    rep(j,W+2){
      if (graph[i][j]=='#') continue;
      int row_where = lower_bound(all(row_wall[i]),j) - row_wall[i].begin();
      int column_where = lower_bound(all(column_wall[j]),i) - column_wall[j].begin();
      int ans_temp = (row_wall[i][row_where]-row_wall[i][row_where-1]-1)+(column_wall[j][column_where]-column_wall[j][column_where-1]-1)-1;
      chmax(ans,ans_temp);
    }
  }
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 40448
#include "bits/stdc++.h"
using namespace std;

//#define int int64_t

#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,x,...) x
#define REP1(i, s, cond, cal) for (signed i = signed(s); i cond; i cal)
#define REP2(i, s, n) REP1(i, s, < signed(n), ++)
#define REP3(i, n) REP2(i, 0, n)
#define rep(...) CHOOSE((__VA_ARGS__,REP1,REP2,REP3))(__VA_ARGS__)

#define all(c) begin(c), end(c)
#define maxup(ans, x) (ans = (ans < x ? x : ans))
#define minup(ans, x) (ans = (ans > x ? x : ans))

#define breakif(cond) if(cond) break; else

template<typename T>
inline void input(vector<T>& v) { for (auto& x : v) cin >> x; }

using VV = vector<vector<int>>;
using V = vector<int>;
using P = pair<int, int>;
using IP = pair<int, P>;

const int INF = 1 << 29;

signed main() {
	V v(3); input(v);
	sort(all(v));
	if (v[0] == 5 && v[1] == 5 && v[2] == 7)cout << "YES" << endl;
	else cout << "NO" << endl;
}

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

int main() {
    int n; cin >> n;
    map<int, int> m;

    for(int i = 0; i < n; ++i) {
        int x; cin >> x;
        m[x] += 1;
    }
    
    long long ans = 0;
    
    vector<int> v;

    for(auto e : m) {
        int x = e.first;
        int f = e.second;
        if(f >= 4) {
            ans = max(ans, 1LL * x * x);
        }
        if(f >= 2) {
            v.push_back(x);
        }
    }

    sort(v.rbegin(), v.rend());

    if(v.size() >= 2) {
        ans = max(ans, 1LL * v[0] * v[1]);
    }

    cout << ans << "\n";
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
  long long H; cin >> H;
  
  long long ans = 0;
  long long i = 1;
 
  while(H>0) {
    H /= 2;
    ans += i;
    i *= 2;
  }
  cout << ans << endl;
}

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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }


int main(){
	cin.tie(0); ios_base::sync_with_stdio(false);
	int h,w,n;
	cin >>h >>w >>n;
	
	VI a(n), b(n);
	rep(i, n){ cin >>a[i] >>b[i]; a[i]--; b[i]--;}
	
	map<pii, ll> mp;
	rep(i, n){
		rep2(y, a[i]-1, a[i]+2) rep2(x, b[i]-1, b[i]+2){
			if(y<1 || y>=h-1 || x<1 || x>=w-1) continue;
			//dbg(y,x,a[i],b[i]);
			mp[pii(y, x)]++;
		}
	}
	vector<ll> ans(10);
	for(auto x: mp) ans[x.second]++;
	ans[0] = (ll)(h-2)*(w-2) - accumulate(all(ans), 0LL);
	
	for(auto x :ans) cout <<x <<"\n";
	return 0;
}

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


int main() {
 

  int64_t n;
  cin>>n;

  vector<int64_t> a(n);
  int64_t sum=0;
  for(int i=0;i<n;i++){
    cin>>a.at(i);
    sum+=a.at(i);
  }

  int64_t sum_sunuke=0;
  int64_t sum_raccoon=sum;
  int64_t min_diff=10000000000;
  for(int i=0;i<n-1;i++){
    sum_sunuke+=a.at(i);
    sum_raccoon-=a.at(i);
    min_diff = min(min_diff,abs(max(sum_raccoon,sum_sunuke)-min(sum_sunuke,sum_raccoon)));
  }

  cout<<min_diff<<endl;

	return 0;
}



Measured memory_bytes: 4832
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <time.h>
using namespace std;
typedef long long lint ;
#define N 150010
vector<int> v[N] ; 
void get_ans(){
    for(lint i = 1 ; i < N ; i++){
        v[i].clear() ;
    }
    for(lint i = 1 ; i < N ; i++){
        for(lint j = 1 ; j < N ; j++){
            if(i*j > N) break ;
            lint tag = i*j ;
            v[tag].push_back(i) ;
        }
    }
}
double f[2][150001];
double a[21];
int main(){
	int n;
	get_ans();
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%lf",&a[i]);
	}
	for (int i=0;i<=1;i++)
		for (int j=1;j<=150000;j++)
			f[i][j]=1000000000;
	for (int i=1;i<=150000;i++){
		f[0][i]=abs(a[1]-i)/a[1];
	}
	int gd=0;
	for (int i=2;i<=n;i++){
		gd=1-gd;
		for (int j=1;j<=150000;j++){
			f[gd][j]=1000000000;
			for (int k=0;k<v[j].size();k++){
				int kk=v[j][k];
				f[gd][j]=min(f[gd][j],max(f[1-gd][kk],abs(a[i]-j)/a[i]));
			}
		}
	}
	double ans=1000000000;
	for (int j=1;j<=150000;j++){
		ans=min(ans,f[gd][j]);
	}
	printf("%0.10lf\n",ans);
}

Measured memory_bytes: 15000
# N = gets.chomp.to_i
# H = gets.chomp.split.map(&:to_i)
S = gets.chomp.chars # array of chars
K = gets.chomp.to_i

cnts = [] # <<chr, cnt>>
i = 0
n = S.size
while (i < n)  # rep(i, N)
  cnt = 1
  while (i < n - 1 && S[i] == S[i+1])
    cnt += 1
    i += 1
  end
  cnts << [S[i], cnt]
  i += 1
end

# p cnts

if cnts.size == 1
  p (cnts[0][1] * K) / 2
else
  if cnts[0][0] == cnts[-1][0] # the char of pre and sub are same
    ans = 0
    ans += cnts[0][1] / 2
    ans += cnts[-1][1] / 2
    ans += (cnts[0][1] + cnts[-1][1]) / 2 * (K-1)  # united
    cnts[1..-2].each do |(chr, cnt)|
      ans += cnt / 2 * K
    end
    p ans
  else
    ans = 0
    cnts.each do |(chr, cnt)|
      if cnt > 1
        ans += cnt / 2
      end
    end
    p ans * K
  end
end

Measured memory_bytes: 1788
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,k=nii()
a=lnii()

for i in range(k,n):
  old=a[i-k]
  new=a[i]
  if old<new:
    print('Yes')
  else:
    print('No')

Measured memory_bytes: 31264
#include <iostream>
#include <cmath>
 
using namespace std;
 
const double EPS = 1e-10;
 
int
main()
{
    int n;
    double x1, y1, x2, y2, x3, y3, x4, y4;
 
    cin >> n;
 
    while (n--) {
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
 
        if (fabs((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1)) < EPS)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
 
    return 0;
}

Measured memory_bytes: 3044
N, K = map(int, input().split())
A = list(map(int, input().split()))

mod = 10**9 + 7
intra, inter = 0, 0
for i in range(N):
    ai = A[i]
    for j in range(i, N):
        aj = A[j]
        if ai > aj:
            intra += 1
    for j in range(i + 1):
        aj = A[j]
        if ai > aj:
            inter += 1

ans = (intra * K * (K + 1) // 2) % mod
ans += (inter * (K - 1) * K // 2) % mod
print(ans % mod)


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

#ifdef DEBUG
#define PRINT(x)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#x<<" = "<<(x)<<endl;
#define PRINTA(a,first,last)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#a<<"["<<(first)<<", "<<(last)<<")"<<endl;\
    for (int _i=(first);_i<(last);++_i){cout<<#a<<"["<<_i<<"] = "<<(a)[_i]<<endl;}
#define PRINTI(a,i)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#a<<"["<<#i<<"] = "<<#a<<"["<<(i)<<"] = "<<(a)[i]<<endl;
#else
#define PRINT(x)
#define PRINTA(a,first,last)
#define PRINTI(a,i)
#endif

#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);--i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define MOD 1000000007
//#define MOD 998244353

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

template <class T, class U> void amax(T& x, U y) {if (x < y) x = y;}
template <class T, class U> void amin(T& x, U y) {if (x > y) x = y;}

template <class T, class U>
std::ostream& operator<<(std::ostream &os, const std::pair<T, U> &p) {
	os << "(" << p.first << ", " << p.second << ")";
	return os;
}
 
template <class T>
std::ostream& operator<<(std::ostream &os, const std::vector<T> &v) {
    os << "[";
	for (int i = 0; i < v.size(); ++i) {
        if (i) {
            if (i % 5 == 0) {
                os << ",\n ";
            } else {
                os << ", ";
            }
        }
		os << v[i];
	}
	os << "]";
	return os;
}

template <class T>
using vec2 = vector<vector<T>>;

template <class T>
using vec3 = vector<vector<vector<T>>>;

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

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

    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    REP(i, N) cin >> A[i];

    REP(i, N - K) {
        // A[i]..A[i+K-1]
        // A[i+1]..A[i+K]
        if (A[i] < A[i + K]) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 3988
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define All(V) V.begin(), V.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main()
{
  int n; cin >> n;
  vector<int> ans(n, 0);
  for(int i = 0; i < n-1; i++){
    int a; cin >> a;
    ans[a-1]++;
  }
  rep(i, n)cout << ans[i] << endl;
  cout << endl;
  system("pause");
}


Measured memory_bytes: 4048
import java.util.*;

public class Main {

    long INF = Long.MAX_VALUE;
    long[][] dp;
    int MAX_M = 100000;
    int MAX_N = 100000;

    public static void main(String[] args) {
        new Main().solve();
    }

    void solve() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] d = new int[N];
        for(int i = 0;i < N;i++){
            d[i] = sc.nextInt();
        }
        Arrays.sort(d);
        System.out.println(d[N/2]-d[N/2-1]);
    }
}

Measured memory_bytes: 50684
#include <bits/stdc++.h>
#include <iterator>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <math.h>

#define v vector
#define ll long long 
#define vpll vector<pair<long long,long long> > 
#define F first
#define S second
#define mp make_pair
#define ld long double
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pci pair<char,int>
#define un unsigned
# define M_PI           3.14159265358979323846  /* pi */
#define mod 1000000007
#define MAXN 200001
using namespace std; 
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)


void solve()
{
    int n,k,c;
    string s;
    cin>>n>>k>>c;
    cin>>s;
    int count = 0;
    v<bool> l(n,false);
    v<bool> r(n,false);
    int prev = -c-1;
    for(int i = 0 ; i < n ; )
    {
        if(s[i] == 'o')
        {
            l[i] = true;
            i += c+1;
            count++;
        }
        else
        {
            i++;
        }
    }
    count = 0;
    for(int i = n-1 ; i >= 0 ; )
    {
        if(s[i] == 'o')
        {
            r[i] = true;
            i -= (c+1);
            count++;
        }
        else
        {
            i--;
        }
    }
    if(count > k)
    return;
    for(int i = 0 ; i < n ; i++)
    {
        if(l[i] && r[i])
        {
            cout<<i+1<<endl;
        }
    }
}

int main()
{
    int t;
    // cin>>t;
    t = 1;
    while(t--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 1796
#ABC156 - Virtual
sel='B'
#B
if sel=='B':
    N,K=map(int,input().split())
    cnt=0
    while N>0:
        N//=K
        cnt+=1
    print(cnt)

#C
if sel=='C':
    def ceilT(a,b): #ceil(a/b)
        return (a+b-1)//b

    N=int(input())
    X=[int(i) for i in input().split()]
    p=ceilT(sum(X),N)
    ans=sum((x-p)**2 for x in X)
    p-=1
    ans=min(ans,sum((x-p)**2 for x in X))
    print(ans)






Measured memory_bytes: 3064
//----------BHAVIK DIWANI(PICT_COMP)---------------
#include<bits/stdc++.h>
#include<stdlib.h>
#include<stdio.h>
#define test ll t; cin>>t; while(t--)
#define FOR(p,n) for(ll i=p;i<(ll)n;i++)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define ll long long
#define int long long
#define ull unsigned long long
#define MAX 1000005
#define pb push_back
#define mkp make_pair
#define vi vector<int>
#define pii pair<int,int>
#define endl '\n'
#define vs vector<string>
#define mii map<int,int>
#define msi map<string,int>
#define vpii vector< pair<int, int > >
#define vpsi vector< pair< string ,int > >
#define forci(p,q) for(int i=p;i<q;i++)
ll gcd(ll a,ll b){ if(b==0) return a;    return gcd(b,a%b);}
ll lcm(ll a,ll b) { return (a/gcd(a,b)*b);}
ull power(ull a, ull b) {a %= mod;  ull res = 1;  while (b > 0) { if (b & 1) res = res * a % mod;  a = a * a % mod;  b >>= 1; }  return res%mod; }
ll modmul(ll x, ll y){return (x*y)%mod;}
ll modadd(ll x, ll y){return (x+y)%mod;}
ll modsub(ll x, ll y){return (x-y+mod)%mod;}
ll fact[1000007]={0};
void facto() {fact[0]=1;fact[1]=1;for(int i=2;i<100007;i++)fact[i]=(fact[i-1]*i)%mod;}
ll ncr(ll n,ll r) {ll res=1; res=fact[n]; res=(res*(power(fact[r],mod-2)))%mod; res=(res*(power(fact[n-r],mod-2)))%mod; return res;}
ll npr(ll n,ll r) {ll res=1; res=fact[n]; res=(res*(power(fact[n-r],mod-2)))%mod; return res;}
inline long long toint(const std::string &s) {std::stringstream ss; ss << s; long long x; ss >> x; return x;}
inline std::string tostring(long long number) {std::stringstream ss; ss << number; return ss.str();}
inline std::string tobin(long long x) {return std::bitset<63>(x).to_string();}
/*bool prime[MAX];
ull sieve(){memset(prime,true,sizeof(prime));for(ull p=2;p*p<MAX;p++){if(prime[p]==true){for(ull i=2*p;i<MAX;i+=p){prime[i]=false;}}}prime[0]=0;prime[1]=0;
}*/
/*int inv[1000001]={0};
void findinverse(){inv[1] = 1;for(int i = 2; i <=1e6 ; ++i)	inv[i] = (mod - (mod/i) * inv[mod%i] % mod) % mod;}
*/
using namespace std;
int solve()
{
	int h,w,k;
	cin>>h>>w>>k;
	string s[h];
	for(int i=0;i<h;i++){
		cin>>s[i];
	}
	int cnt=0;
	for(int i=0;i<(1<<h);i++){
		for(int j=0;j<(1<<w);j++){
			int black=0;
			for(int k=0;k<h;k++){
				for(int l=0;l<w;l++){
					if(i&(1LL<<k) && j&(1LL<<l) && s[k][l]=='#')
						black++;
				}
			}
			if(black==k)
				cnt++;
		}
	}
	cout<<cnt<<endl;
	return 0;
}
signed main()
{
	fastio;
//	test
		solve();
}






Measured memory_bytes: 3616
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    int x[n],y[n];
    for(int i=0;i<n;i++){
        cin>>x[i];
    }
    for(int i=0;i<n;i++){
        cin>>y[i];
    }
    int sum=0;
    for(int i=0;i<n;i++){
        if(x[i]>y[i]){
            sum+=(x[i]-y[i]);
        }
    }
    cout<<sum;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
const int MAXN=1005;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int n,m;
bool a[MAXN][MAXN];
int vis[MAXN][MAXN];

int main()

{
	memset(vis,-1,sizeof(vis));
	queue<pair<int,int> > q;
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			char c;
			cin>>c;
			a[i][j]=c=='#';
			if (a[i][j]){
				q.push(make_pair(i,j));
				vis[i][j]=0;
			}
		}
	}

	while (!q.empty()){
		int x=q.front().first,y=q.front().second;
		q.pop();
		for (int i=0;i<4;i++){
			int gx=x+dx[i],gy=y+dy[i];
			if (gx<=0 || gy<=0 || gx>n || gy>m) continue;
			if (vis[gx][gy]==-1){
				vis[gx][gy]=vis[x][y]+1;
				q.push(make_pair(gx,gy));
			}
		}
	}

	int ans=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			ans=max(ans,vis[i][j]);
			
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 13328
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <string>
#include <string.h>
#include <math.h>
#include <iomanip>
#include <stdio.h>
using namespace std;

#define int64 long long
#define pii pair <int64, int64>
#define fr first
#define sc second
#define heap priority_queue
struct piii{
    int64 fr, sc, th;
    bool operator < (const piii &b){
        if (fr != b.fr) return fr < b.fr;
        if (sc != b.sc) return sc < b.sc;
        return th < b.th;
    }
};
///////////////////////////////////////////////
///////////////////////////////////////////////

int main(){
    cout << setprecision(2) << fixed;
    ios::sync_with_stdio(false), cin.tie(0);
    //freopen("input.txt", "r", stdin);
    int n;
    double d;
    cin >> n >> d;
    int cnt=0;
    double x, y;
    while (n--){
        cin >> x >> y;
        if (sqrt(x * x + y * y) <= d) cnt++;
    }
    cout << cnt;
    return 0;
}


Measured memory_bytes: 3856
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,k;
  cin >>n >> k;
  vector<ll> h(n);
  if(k>=n){
    cout << 0 <<endl;
  }else{
    for(ll i=0 ;i<n ;i++){
      cin >> h[i];
    }
    sort(h.begin(), h.end());
    ll ans=0;
    for(ll i=0; i<n-k; i++){
      ans += h[i];
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<string>
using namespace std;

int main(){
  int N,K;
  cin >> N;
  string S;
  cin >> S;
  cin >> K;

  char a = S[K-1];

  for(int i=0; i<N; i++){
    if(S[i]!=a){
      S[i] = '*';
    }
  }

  cout << S << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;

long long n;
long long a[11111];

int main(){
  ios_base::sync_with_stdio(false);
  
  int ans = 0; 
  
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  
  for(int i=0;i<n;i++){
    while(a[i] > 0 && a[i] % 2ll == 0){
      ans++;
      a[i] /= 2;
    }
  }
  
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
#define vcin(a)                          \
    for (int i = 0; i < (a).size(); i++) \
        cin >> (a)[i];

int main()
{
    double a, b, h;
    cin >> a >> b >> h;
    cout << (a + b) / 2 * h;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <stack>

#define MAXN 100
#define INF ~(1U<<31)
#define MAX (1LL<<50)
#define WHITE 0
#define GRAY 1
#define BLACK 2

typedef long long ll;

using namespace std;

struct NODE { int no; ll d; } typedef NODE;

bool operator> ( const NODE& x, const NODE& y ) { return x.d > y.d; };

int E[MAXN][MAXN];
bool EB[MAXN][MAXN];
int color[MAXN], p[MAXN];
ll d[MAXN];

void dicstra( int n, int sno )
{
  for ( int i = 0; i < n; ++i ) color[i] = WHITE, d[i] = MAX, p[i] = -1;
  priority_queue<NODE, vector<NODE>, greater<NODE>> Q;
  color[sno] = GRAY;
  d[sno] = 0;
  Q.push({sno,d[sno]});

  while ( !Q.empty() ) {
    NODE top = Q.top(); Q.pop();
    if ( d[top.no] != top.d) continue;
    if ( (color[top.no] == GRAY)  ) {
      for ( int i = 0; i < n; ++i ) {
        if ( (color[i] != BLACK) && (E[top.no][i] != INF) ) {
          if ( d[i] > d[top.no]+E[top.no][i] ) {
            d[i] = d[top.no]+E[top.no][i];
            color[i] = GRAY;
            p[i] = top.no;
            Q.push({i,d[i]});
          }
        }
      }
    }
    color[top.no] = BLACK;
  }

}

int caledge ( int n ) {

  int ans = 0;

  for ( int i = 0; i < n; ++i ) {
    dicstra(n,i);
    for ( int j = 0; j < n; ++j ) {
      if ( p[j] == -1 ) continue;
      EB[j][p[j]] = true;
      EB[p[j]][j] = true;
    }
  }

  for ( int i = 0; i < n; ++i ) {
    for ( int j = 0; j < n; ++j )  {
      if ( EB[i][j] ) ++ans;
    }
  }

  return ans/2;
}

void printEB ( int n )
{
  for ( int i = 0; i < n; ++i ) {
    for ( int j = 0; j < n; ++j ) {
      if ( EB[i][j] ) cout << 1 << " ";
      else cout << 0 << " ";
    }
    cout << "\n";
  }
}

int main()
{
  int N,M,tmp;

  cin >> N >> M;
  for ( int i = 0; i < N; ++i ) for ( int j = 0; j < N; ++j ) E[i][j] = INF;
  tmp = M;
  while(tmp--) {
    int a,b,c;
    scanf("%d%d%d", &a, &b, &c);
    --a; --b;
    E[a][b] = E[b][a] = c;
  }

  cout << M-caledge(N) << "\n";
  //printEB(N);
}


Measured memory_bytes: 888
#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

int main()
{
	int N, K, temp;
	double ans = 0;
	cin >> N >> K;
	double test;
	double dice_per = (1.0 / (double)N);

	for (int i = 1; i <= N; i++) {
		if (i < K) {
			for (int j = 1; ; j++) {
				temp = i * (pow(2, j));

				if (K <= temp) {
					test = dice_per * pow(0.5, j);
					ans += test;
					break;
				}
			}
		}

		else if (i == K) {
			double temp = ((double)(N - i + 1) / double(N));
			ans += temp;
			break;
		}
	}

	cout << setprecision(15) << ans << endl;
}

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


int main(){
    int N;
    cin >> N;
    set<int> s;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        if (s.find(a) != s.end()) s.erase(a);
        else s.insert(a);
    }
    cout << s.size() << endl;
}

Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 200000;
vector <int> bi[N];
int dfs(int t, int f = 0)
{
    int x = 0;
    for (int i = 0; i < bi[t].size(); ++ i) if (bi[t][i] != f) x ^= dfs(bi[t][i], t) + 1;
    return x;
}
int main()
{
    cin >> n;
    for (int i = 1; i < n; ++ i)
    {
        int a, b;
        cin >> a >> b;
        bi[a].push_back(b);
        bi[b].push_back(a);
    }
    if (dfs(1)) puts("Alice"); else puts("Bob");
}


Measured memory_bytes: 14336
import math
n,k=map(int,input().split())
if k>n:
    prob = 0
    for i in range(1,n+1):
        prob += (1/n) * (1/2)**math.ceil(math.log(k/i,2))
    print(prob)   
else:
    prob =(n-k+1)/n 
    for i in range(1,k):
        prob += (1/n) * (1/2)**math.ceil(math.log(k/i,2))
    print(prob)  

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define PI 3.14159265359
typedef long long ll;
using namespace std;

int main(){
    int n,k,r,s,p; cin >> n >> k >> r >> s >> p;
    string t; cin >> t;
    int ans=0;
    char te[k]={};

    rep(i,k){
        if(t[i]=='r') ans+=p;
        else if(t[i]=='s') ans+=r;
        else ans+=s;
        te[i] = t[i];
    }

    for(int i=k; i<n; i++){
        int o=i%k;
        if(te[o]==t[i]) te[o]='d';
        else{
            if(t[i]=='r') ans+=p;
            else if(t[i]=='s')ans+=r;
            else if(t[i]=='p')ans+=s;
            te[o] = t[i];
        }
    }
    
    cout << ans << endl;
return 0;
}


Measured memory_bytes: 512
S = int(input())

if 0 <= S <= 86400:
    h = int(S / 3600)
    m = int((S % 3600) / 60)
    s = int((S % 3600) % 60)
    print(str(h) + ":" + str(m) + ":" + str(s))
else:
    print("error")


Measured memory_bytes: 7644
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using Graph = vector<vector<int>>;

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

    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a - 1].push_back(b - 1);
        G[b - 1].push_back(a - 1);
    }

    vector<int> res(N, -1); 
    queue<int> que;

    res[0] = 0;
    que.push(0); 

    
    while (!que.empty()) {
        int v = que.front(); 
        que.pop();

        for (int nv : G[v]) {
            if (res[nv] != -1) continue;

            res[nv] = v + 1;
            que.push(nv);
        }
    }

    cout << "Yes" << endl;
    for (int v = 1; v < res.size(); ++v) cout  << res[v] << endl;
}

Measured memory_bytes: 10100
S=list(input())
a=int("".join(S[0:2]))
b=int("".join(S[2:4]))

if 1<=a<=12 and 1<=b<=12:
    print("AMBIGUOUS")
elif 1<=a<=12:
    print("MMYY")
elif 1<=b<=12:
    print("YYMM")
else:
    print("NA")



Measured memory_bytes: 2940
def main
  delicious_degrees = []

  object_count = gets().to_i

  return_flg = false
  gets.split(" ").each do |value|
    value.to_i >= 0 ? delicious_degrees << value.to_i : return_flg = true
    next if return_flg
  end

  return if object_count < 2 || object_count > 50
  return if return_flg

  total_delicious_value = 0
  delicious_degrees.each_with_index do |degree, index|
    next if index == object_count
    total_delicious_value += total_of_multiplication( degree, delicious_degrees[index+1..object_count] )
    # p "#{index}要素目 値:#{degree} 合計:#{total_delicious_value}"
  end
  
  p total_delicious_value
end

def total_of_multiplication( coefficient, targets )
  total = 0
  targets.each do |v|
    total += coefficient * v
  end
  total
end

main

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
int n,h,w,a[N],b[105][105];
int main(){
	cin>>h>>w>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int id=1,s=0,x=1,y=1,d=1;
	while(s<a[id]&&id<=n){
		b[x][y]=id;
		s++;
		if(s==a[id]) s=0,id++;
		if(d==1&&y==w){
			d=-1,x++;
		}
		else if(d==-1&&y==1){
			d=1,x++;
		}
		else y=y+d;
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			printf("%d ",b[i][j]);
		} 
	puts("");
	}
	return 0;
}

Measured memory_bytes: 3804
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,w;
int a,b;
long long dp[100005];
int main(){
	cin>>n>>w;
	fill(dp,dp+100001,1e15);
	dp[0]=0;
	for(int i=1;n>=i;i++)
	{
		cin>>a>>b;
		for(int j=100000-b;j>=0;j--)
			dp[j+b]=min(dp[j+b],dp[j]+a);
	}
	int res=0;
	for(int i=0;100000>=i;i++)
		if(dp[i]<=w)
			res=i;
	cout<<res;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define int long long

#define TASKNAME ""

using namespace std;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("1.txt", "w", stdout);
    int n;
    cin >> n;
    vector<vector<int> > kek = {{1}, {1}};
    int num = 2;
    n--;
    while (true){
        if (n==0) break;
        int need = kek.size();
        if (n < need){
            cout << "No";
            return 0;
        }
        n -= need;
        kek.push_back({});
        for (int i=0; i < need; i++){
            kek[i].push_back(i+num);
            kek.back().push_back(i+num);
        }
        num += need;
    }
    cout << "Yes" << endl;
    cout << kek.size() << endl;
    for (int i=0;i<kek.size(); i++){
        cout << kek[i].size() << " ";
        for (int j=0; j < kek[i].size(); j++) cout << kek[i][j] << " ";
        cout << endl;
    }

}


Measured memory_bytes: 3200
//be naame khodaa

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <cstdio>
#include <algorithm>
#include <set>
#include <cassert>
#include <iomanip>
#include <cstring>
#define fi first
#define se second
#define rep(i, x, n) for (int i = x; i < n; i++)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> VI;
const int maxn = 100005;
const ll P = 1e9 + 7;

ll f[2*maxn], inv[2*maxn];

ll solve (int a, int b){
	int n = a + b, k = a;
	return f[n]*inv[k]%P*inv[n-k]%P;
}

ll bpow (int a, int b){
	if (b == 0) return 1;
	ll ans = bpow (a, b/2);
	ans = ans*ans%P;
	if (b%2) ans = ans*a%P;
	return ans;
}

int main()
{
	ios::sync_with_stdio(false);
	f[0] = inv[0] = 1;
	for (int i = 1; i < 2*maxn; i++){
		f[i] = f[i-1]*i%P;
		inv[i] = inv[i-1]*bpow(i, P-2)%P;
	}
	int h, w, a, b;
	cin >> h >> w >> a >> b;
	ll ans = 0;
	for (int i = 0; i < h-a; i++)
		ans = (ans + solve(i, b-1)*solve(h-1-i, w-b-1))%P;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
#define ll long long
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rep1(i, n) FOR(i, 1, n+1)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define whole(x) (x).begin(),(x).end()
#define rwhole(x) (x).rbegin(), (x).rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define P pair<int, int>
#define debug(var) cerr << "[" << #var << "] " << var << '\n'
template<typename T1, typename T2>
bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
template<typename T1, typename T2>
bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define pr(s) cout << (s) << '\n'
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
const int INF = 1001001001;
const ll INFll = 1E+18;

int main() {
  int a, b;
  cin >> a >> b;
  string ans = "x";
  if (a+b==15) ans = "+";
  if (a*b==15) ans = "*";
  pr(ans);
}

Measured memory_bytes: 3624
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

const int N = 1e5 + 10;
int f[N];

int find(int x) {
  if (f[x] != f[f[x]]) f[x] = find(f[x]);
  return f[x];
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    f[i] = i;
  }
  int cnt = n;
  for (int k = 0; k < m; ++k) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    --x; --y;
    int rx = find(x), ry = find(y);
    if (rx != ry) {
      f[ry] = rx;
      --cnt;
    }
  }
  printf("%d\n", cnt);
  return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int n, a[100009];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i];
	int cx = 1, cnt = 0;
	while (true) {
		cnt++; cx = a[cx];
		if (cx == 2) { cout << cnt << endl; return 0; }
		if (cnt >= 500000)break;
	}
	cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 640
#!/usr/bin/env python
# coding: utf-8

# In[9]:


N,K = map(int, input().split())


# In[10]:


if K == 0:
    ans = N*N
else:
    ans = 0
    cnt = 1
    for b in range(K+1,N+1):
        mod = N%b
        x = N//b
        ans += x*cnt
        if mod >= K:
            ans += mod-K+1
        cnt += 1
print(ans)


# In[ ]:






Measured memory_bytes: 9108
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin >> n >> m;
  int h[n],ma[n];
  for(int i=1;i<=n;i++){
    cin >> h[i];
    ma[i]=0;
  }
  for(int i=0;i<m;i++){
    int a,b;
    cin >> a >> b;
    ma[a]=max(ma[a],h[b]);
    ma[b]=max(ma[b],h[a]);
  }
  int ans=0;
  for(int i=1;i<=n;i++)ans+=h[i]>ma[i];
  cout << ans << endl;
}


Measured memory_bytes: 4420
#include<iostream>
#include<set>
#include <bitset>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include <cstdio>
#include<algorithm>
#include <sstream>
#include<string>
#include<string.h>
#include <cmath>
#include <iomanip>
#include <string>
#include<list>
#include <limits>
#include <numeric>
#include <type_traits>
#define int long long
#define ll long long
#define mod  1000000007
#define inf 1e17
#define rep(i,j,n) for(int i=j;i<n;i++)
#define P pair<int,int>
#define ps push_back
double pi = 3.141592653589793;
using namespace std;
int z=0;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
//ここから始めよう
signed main(){
    string s;cin>>s;
    int n=s.size();
    if(s[n-1]=='1'||s[0]=='0'){
        cout<<-1<<endl;return 0;
    }
    rep(i,0,n-1){
        if(s[i]!=s[n-2-i]){
            cout<<-1<<endl;return 0;
        }
    }
    int pre=0;
    vector<P> v;
    rep(i,0,n-1){
        if(s[i]=='1'){
            v.ps(P(pre,i+1));pre=i+1;
        }
        else v.ps(P(pre,i+1));
    }
    rep(i,0,v.size())cout<<v[i].first+1<<" "<<v[i].second+1<<endl;return 0;
}

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

int floorUp(int num)
{
  if (num == 0) return 0;
  if (num < 1000) return 1000;

  int q, r;
  q = num / 1000;
  r = num - q * 1000;

  if (r == 0) return q * 1000;

  return (q + 1) * 1000;
}

int main()
{
  int n, i, ans;

  cin >> n;

  ans = 100000;

  for (i = 0; i < n; i++)
  {
    ans = floorUp(ans * 1.05);
  }

  cout << ans << endl;

  return 0;
}



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

typedef long long int ll;


int main()
{
    string s;
    ll a = 0, b = 0, c = 0;
    cin >> s;
    ll le = s.length();
    for(ll i = 0;i < le;i++){
        if(s[i] == 'a'){
            a++;
        }
        else if(s[i] == 'b'){
            b++;
        }
        else{
            c++;
        }
    }

    if(abs(a - b) <= 1 && abs(b - c) <= 1 && abs(c - a) <= 1){
        cout << "YES";
    }
    else{
        cout << "NO";
    }

    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
  ll n,k;
  cin >> n>>k;
  ll d[k];
  for(ll i=0;i<k;i++) cin >>d[i];
  for(ll i=n;;i++){
    ll p=i,fl=0;
      while(1){
        if(p==0) break;
        ll l=p%10;
        for(ll i=0;i<k;i++) {
          if(d[i]==l){
            fl=1;
            break;
          }
        }
        if(fl==1) break;
        p/=10;
      }
      if(fl==0) {
        cout <<i<<endl;
        return 0;
      }
  }
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int n,m,q,c[512][512];
    cin>>n>>m>>q;
    for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)c[i][j]=0;
    for(int i=0;i<m;i++){
        int l,r;
        cin>>l>>r;
        c[l][r]++;
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            c[i][j]+=c[i][j-1];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            c[j][i]+=c[j-1][i];
        }
    }
    for(int i=0;i<q;i++){
        int p,q;
        cin>>p>>q;
        cout<<c[q][q]-c[q][p-1]-c[p-1][q]+c[p-1][p-1]<<endl;
    }
}


Measured memory_bytes: 1920
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long LL;
const int MAX_N = 2e5 +6;
const LL INF = 1e15 + 7;

struct Node {
    Node *lc,*rc;
    LL tag;
    LL mx;
    Node() {
        lc=rc=NULL;
        mx = tag = 0;
    }
    void pull() {
        mx = max(lc->mx,rc->mx);
    }
};

Node* Build(int L,int R) {
    Node* node=  new Node();
    if (L==R) {
        return node;
    }
    int mid=(L+R)>>1;
    node->lc=Build(L,mid);
    node->rc=Build(mid+1,R);
    return node;
}

void push(Node* node,int L,int R) {
    if (L==R) node->tag = 0;
    if (node->tag == 0) return;
    node->lc->tag += node->tag;
    node->rc->tag += node->tag;
    node->lc->mx += node->tag;
    node->rc->mx += node->tag;
    node->tag = 0;
    return ;
}

void modify(Node* node,int L,int R,int l,int r,LL val) {
    if (L>r || l>R) return;
    else if (l<=L && R<=r) {
        node->mx += val;
        node->tag += val;
        return;
    }
    push(node,L,R);
    int mid=(L+R)>>1;
    modify(node->lc,L,mid,l,r,val);
    modify(node->rc,mid+1,R,l,r,val);
    node->pull();
    return;
}

LL query(Node *node,int L,int R,int l,int r) {
    if (l>R || L>r) return -INF;
    else if (l<=L && R<=r) return node->mx;
    push(node,L,R);
    int mid=(L+R)>>1;
    return max(query(node->lc,L,mid,l,r),query(node->rc,mid+1,R,l,r));
}

int L[MAX_N],R[MAX_N];
vector<int> v[MAX_N];

int main () {
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=1;n>=i;i++) {
        scanf("%d %d",&L[i],&R[i]);
        v[L[i] ].push_back(R[i]);
    }
    Node* root=Build(1,m);
    int kirino=m;
    for (int i=1;m>=i;i++) {
        modify(root,1,m,i,i,-kirino);
        kirino--;
    }
    sort(v[m].begin(),v[m].end());
    LL ans = max(0,n-m);
    LL meruru = 0;
    for (int i=0;m>i;i++) {
        if (i==0) {
            for (int j:v[i]) {
                if (j==m+1) meruru++;
                modify(root,1,m,1,j,1);
            }
            ans = max(ans,query(root,1,m,1,m));
            ans = max(ans,meruru);
            continue;
        }
        modify(root,1,m,i,i,-INF);
        modify(root,1,m,i+1,m,-1);   //add one point
        meruru--;
        for (int j:v[i]) {
            modify(root,1,m,i+1,j,1);
            if (j==m+1) meruru++;
        }
        ans = max(ans,query(root,1,m,1,m));
        ans = max(ans,meruru);
    }

    printf("%lld\n",ans);
}



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

#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) (x).erase(unique(all(x)), end(x))
#define bit(n) (1LL << (n))
#define cdiv(a, b) (((a) - 1) / (b) + 1)
#define dump(x) cerr << #x " = " << (x) << endl
using vint = vector<int>;
using vvint = vector<vint>;
using pint = pair<int, int>;
using vpint = vector<pint>;
template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
constexpr long double PI = 3.1415926535897932384626433832795028L;
constexpr int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

signed main() {
    int N;
    cin >> N;
    int c = N % 10;
    if (c == 3) { cout << "bon" << endl; }
    else if (c == 0 || c == 1 || c == 6 || c == 8) { cout << "pon" << endl; }
    else { cout << "hon" << endl; }
}

Measured memory_bytes: 3636
#include<bits/stdc++.h> 
//#define <- プログラムの文字列を置換する
//typedef <- 新しい型に名前を付けるためのキーワード

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> ppiii;

const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int INF_INT = 1e9;

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;
}

template<class TYPE>
struct edge{
    TYPE to,cost; 
    edge(TYPE t,TYPE c){
        to = t;
        cost = c;
    }
};

int main(){
    string s;
    int sum = 0;
    cin >> s;
    vector<int> check(26);
    for(int i = 0; i < s.length(); i++){
        if(check[s[i] - 'a'] == 0){
            check[s[i] - 'a'] = 1;
            sum++;
        }
    }
    if(sum == 1){
        cout << 0 << endl;
        return 0;
    }
    ll cost = INF;
    for(int i = 0; i < 26; i++){
        if(check[i] == 0) continue;
        char C = 'a' + i;
        bool flg = true;
        string now = s;
        ll temp = 0;
        while(!flg || temp == 0){
            temp++;
            flg = true;
            string make = string();
            for(int j = 0; j < now.length() - 1; j++){
                if(now[j] == C || now[j+1] == C) make = make + C;
                else make = make + now[j];
            }
            for(int j = 0; j < make.length(); j++){
                if(make[j] != C) flg = false;
            }
            now = make;
        }
        cost = min(cost,temp);
    }
    cout << cost << endl;
    return 0;
}


Measured memory_bytes: 3580
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC85
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] S = Console.ReadLine().Split('/');
            S[0] = (int.Parse(S[0]) + 1).ToString();
            Console.WriteLine(string.Join("/", S));
        }
    }
}


Measured memory_bytes: 11092
from collections import *
from itertools import *
import copy
from heapq import *

D,G=map(int,input().split())
PC=[list(map(int,input().split())) for i in range(D)]

mincount=10000000
for i in range(2**D):
    b=(D-len(bin(i)[2:]))*"0"+bin(i)[2:]
    value=0
    count=0
    for s in range(D):
        if b[s]=="0":
            pass
        if b[s]=="1":
            p,c=PC[s]
            value+=p*(s+1)*100+c
            count+=p
    for s in range(D-1,-1,-1):
        if value<G:
            if b[s]=="0":
                p,c=PC[s]
                a=min(p-1,(G-value)//((s+1)*100)+((G-value)%((s+1)*100)>=1) * 1)
                count+=a
                value+=a*(s+1)*100
    #print(count,value,"2")
    if value>=G:
        mincount=min(mincount,count)
print(mincount)


Measured memory_bytes: 44016
N, M = map(int, raw_input().split())

ax = []
bx = []
for _ in xrange(M):
    a, b = map(int, raw_input().split())
    if a == 1:
        bx.append(b)
    if b == N:
        ax.append(a)
if len(set(ax) & set(bx)) > 0:
    print "POSSIBLE"
else:
    print "IMPOSSIBLE"


Measured memory_bytes: 19920