akhauriyash/Code-Regression huggingface dataset:
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
typedef long long int ll;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define MOD 1000000007
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);  
//*s.find_by_order(p)   returns the value of pth largest starting from 0 
//s.order_of_key(p)   returns no. of items that are strictly < p 
//string bin = bitset<64>(m).to_string();     convert decimal m to binary 
ll power(ll a, ll b) 
{
    ll res = 1;
    while (b > 0) {
        if (b & 1){res = res * a;res=res%MOD;}
        a = a * a;a=a%MOD;
        b >>= 1;
    }
    return res;
}
int main()
{
      fast;ll t;t=1;
      while(t--)
      { 
            ll n,p;
            cin>>n;
            if(n==1){cout<<0;}
            else if(n==2){cout<<2;}
            else 
            {     
                  p=power(10,n);
                  p%=MOD;
                  p=p+power(8,n);
                  p%=MOD;
                  p=p-2*power(9,n)+2*MOD;
                  p%=MOD;
                  cout<<p;
            }
            cout<<"\n";
      }
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
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; }
typedef long long ll;
typedef pair<int,int> P;

ll dp[105][100005];
int w[105],v[105];

int main(){
    int n,W;
    cin >> n >> W;
    rep(i,n)cin >> w[i+1] >> v[i+1];
    rep(i,100005)dp[0][i]=LINF;
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j = 0;j<100005;j++){
            dp[i][j]= dp[i-1][j];
            if(j-v[i]>=0)chmin(dp[i][j],dp[i-1][j-v[i]]+w[i]);
        }
    }
    int ans = 0;
    rep(i,100005){
        //cout << dp[n][i] << endl;
        if(dp[n][i]<=W)chmax(ans,i);
    }
    cout << ans << endl;
}

Measured memory_bytes: 80128
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD 1000000007

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

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

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

signed main() {
    string S;
    cin >> S;

    rep(i, S.size()) {
        if (S[i] != '?') continue;
        if (i + 1 == S.size())
            S[i] = 'D';
        else if (i > 0 && S[i - 1] == 'P')
            S[i] = 'D';
        else if (i + 1 < S.size() && S[i + 1] == 'P')
            S[i] = 'D';
        else
            S[i] = 'P';
    }

    cout << S << endl;

    return 0;
}


Measured memory_bytes: 3720
#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define debuge cerr<<"isok"<<endl
#define debug(x) cerr<<#x<<"="<<x<<endl
#define SS second
#define FF first
#define ls (k<<1)
#define rs (k<<1|1)
#define inf 0x3f3f3f3f
#define clr(a,x) memset(a,x,sizeof(a))
#define cpy(a,x) memcpy(a,x,sizeof(a))
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout);
using namespace std;

const int N=2005,M=100005,mod=1e9+7;
template<class T> inline void gmin(T &x,const T &y){if(x>y) x=y;}
template<class T> inline void gmax(T &x,const T &y){if(x<y) x=y;}
inline void ch(int &x,int y){x=(x+y)%mod;}
inline void read(int &x){
	x=0;char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}

int n,m,Q;
int f[N][N],g[N][N],h[N][N];
char s[N][N];

int main(){
#ifdef rqgao2014
	freopen("input.txt","r",stdin);
	srand(time(0));
	time_tester(0);
#endif
	scanf("%d%d%d",&n,&m,&Q);
	for(int i=1;i<=n;i++)
		scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(s[i][j]=='1');
	for(int i=1;i<n;i++)
		for(int j=1;j<=m;j++)
			g[i][j]=g[i-1][j]+g[i][j-1]-g[i-1][j-1]+(s[i][j]=='1'&&s[i+1][j]=='1');
	for(int i=1;i<=n;i++)
		for(int j=1;j<m;j++)
			h[i][j]=h[i-1][j]+h[i][j-1]-h[i-1][j-1]+(s[i][j]=='1'&&s[i][j+1]=='1');
	for(int i=1;i<=Q;i++){
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		int ans=f[x2][y2]-f[x1-1][y2]-f[x2][y1-1]+f[x1-1][y1-1];
		ans-=g[x2-1][y2]-g[x1-1][y2]-g[x2-1][y1-1]+g[x1-1][y1-1];
		ans-=h[x2][y2-1]-h[x1-1][y2-1]-h[x2][y1-1]+h[x1-1][y1-1];
		printf("%d\n",ans);
	}
#ifdef rqgao2014
	time_tester(1);
#endif
	return 0;
}


Measured memory_bytes: 52864
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
 int n,m;
  cin >> n >> m;
  vector<int> high(n);
  vector<vector<int>> bri(m, vector<int>(2));
  set<int> s;
  for(int i=0;i<n;i++){
    cin >> high.at(i);
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < 2; j++) {
      cin >> bri.at(i).at(j);
      } 
    }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < 2; j++) {
      int x=bri.at(i).at(0)-1;
      int y=bri.at(i).at(1)-1;
      if (high.at(x)<high.at(y))
        s.insert(x);
      else if (high.at(x)>high.at(y))
        s.insert(y);
      else if (high.at(x)==high.at(y)){
        s.insert(x);
        s.insert(y);
      }
    }
  }
    cout << n-(s.size()) << endl;
}






Measured memory_bytes: 11708
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define REP(X, Y, Z) for (ll(X) = (Y); (X) < (Z); (X)++)
#define REV(X, Y, Z) for (ll(X) = (Y); (X) > (Z); (X)--)

using namespace std;
using ll = long long;
using dll = deque<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using usll = unordered_set<ll>;
using umll = unordered_map<ll, ll>;
using sll = stack<int>;
using vll = vector<ll>;
using vvll = vector<vll>;

constexpr ll kMod = 1e9 + 7;

ll gcd(ll a, ll b) {
  if (a < b) {
    return gcd(b, a);
  }
  ll c = a % b;
  while (c != 0) {
    a = b;
    b = c;
    c = a % b;
  }
  return b;
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

void init() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

int main() {
  init();

  ll N;
  cin >> N;
  vll H(N);
  REP(i, 0, N) {
    ll h;
    cin >> h;
    H[i] = h;
  }

  REV(i, N - 2, -1) {
    if (H[i] > H[i + 1]) {
      H[i]--;
    }
    if (H[i] > H[i + 1]) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <climits>
#include <complex>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

// using
using namespace std;

// typedef
typedef long long ll;

// define
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REVERSE(c) reverse(ALL(c))
#define UNIQ(c) unique(ALL(c))
#define FOR(i, a, b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))
#define REP(i, n) FOR(i, 0, n, 1)
#define RFOR(i, a, b, c) for (int i = (int)(a); i >= (int)(b); i -= (int)(c))
#define RREP(i, n) RFOR(i, n, 0, 1)

// functions
template <class T> T ceil(T a, T b) {
    return (a + b - 1) / b;
}
template <class T> T round(T a, T b) {
    return (a + b / 2) / b;
}
template <class T> T gcd(T a, T b) {
    return b ? gcd(b, a % b) : a;
}
template <class T> T lcm(T a, T b) {
    return a * b / gcd(a, b);
}
template <class T> bool amax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// main
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<vector<int>> X(N, vector<int>(3));
    REP(i, N) {
        REP(j, 3) {
            cin >> X[i][j];
        }
    }
    int pt = 0, px = 0, py = 0;
    REP(i, N) {
        int dt = X[i][0] - pt;
        int d = abs(X[i][1] - px) + abs(X[i][2] - py);
        if (dt < d) {
            cout << "No" << endl;
            return 0;
        } else if (dt > d && dt % 2 != d % 2) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 5760
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        String S = sc.next();

        if (S.length() <= K) {
            System.out.println(S);
        } else {
            System.out.println(S.substring(0, K) + "...");
        }
    }
}

Measured memory_bytes: 38660
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
using namespace std;
using ll = long long;
const ll INF = 10e9;
ll MOD=1000000007;

int main(){
  int n,m,x; cin>>n>>m>>x;
  int C[n];
  int A[n][m];
  ll algo[m];
  ll money = INF;
  bool jud = false;
  rep(i,n){
    cin>> C[i];
    rep(j,m) cin>>A[i][j];
  }
  rep(bit, 1<<n){
    rep(k,m) algo[k]=0;
    ll tmp = 0;
    rep(i,n){
      if (bit & (1<<i)){
        rep(j,m) algo[j] += A[i][j];
        tmp += C[i];
      }
    }
    bool ok = true;
    rep(k,m){
      if (algo[k]<x) ok = false;
    }
    if (ok){
      jud = true;
      money = min(money, tmp);
    }
  }
  if (jud) cout << money << endl;
  else cout << -1 << endl;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define MAX(a,b) a=a>b?a:b
#define MIN(a,b) a=a>b?a:b
#define REP(i,x,n) for(int i=x;i<n;i++)
#define REPR(i,x,n) for(int i=n-1;i>=x;i--)
#define F first
#define S second
using namespace std;
typedef long long ll;
const ll mod =1e9 + 7;
int n;
double c=0;
int x[10],y[10];

void aa(ll nn,double d,int l){
	rep(i,n){
		if((1<<i)&nn)continue;
		int a=0,b=0;
		if(l!=-1){
			a=x[i]-x[l];
		b=y[i]-y[l];
		}
		
		aa(nn+(1<<i),d+sqrt((a*a)+(b*b)),i);

	}

	if(nn+1==(1<<n)){
		c+=d;
	}
}


int main(){
	string s;
	cin>>n;
	ll cn=1;
	rep(i,n){
		cin>>x[i]>>y[i];
		cn*=(i+1);
	}
	aa(0,0,-1);
	printf("%.10f\n",c/cn);
	
}

Measured memory_bytes: 256
N = int(input())
A = [int(i) for i in input().split()]

A.sort(reverse=True)


score = A[0]
N -= 1

for i in A[1:]:
  N -= 1
  if(N==0):
    break
  score += i
  N -= 1
  if(N==0):
    break
  score += i
print(score)







Measured memory_bytes: 94304
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main()
{
  int a, b, c;
  cin >> a >> b >> c;

  int M = std::max(std::max(a, b), c);
  if ((3 * M) % 2 == (a + b + c) % 2)
  {
    cout << (3 * M - (a + b + c)) / 2 << endl;
  }
  else
  {
    cout << (3 * (M + 1) - (a + b + c)) / 2 << endl;
  }
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=1000000007;
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
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 (a>b) { a=b; return 1; } return 0; }
const ll MAX = 2000010;//設定して

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;//＊１
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}
//階乗
long long factor(ll n,ll k){
  if (n<k) return 0;
  if (n<0 || k<0) return 0;
  return (fac[n]*finv[k])%mod;
}
// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//aの逆元求めるならn=mod-2
long long modpow(long long a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
int main(){
COMinit();
int n;
cin>>n;
vector<ll> a(n);
ll ma=0,tmp=inf;
for(int i=0;i<n;i++)cin>>a[i];
sort(all(a),greater<ll>());
ll l,r;
l=a[0];
for(int i=1;i<n;i++){
    if(tmp>abs((l+1)/2-a[i])){
            r=a[i];
            tmp=abs((l+1)/2-a[i]);
    }
    }
cout<<l<<" "<<r<<endl;
}


Measured memory_bytes: 47872
#include <cstdio>
#include <utility>
using namespace std;

using i64 = long long;

#define REP(i, stop) for (int i = 0, i##_len = stop; i < i##_len; ++i)

i64 D[13];
i64 E[13];
char S[100001];
const i64 M = 1000000007;
signed main() {
	D[0] = 1;
	scanf("%s", S);
	i64 i = 0;
	while(true) {
		char c = S[i];
		if (c == 0) {
			break;
		} else if (c == '?') {
			/*
			REP(r, 13) {
				i64 s = 0;
				REP(j, 10) {
					s += D[(j - r + 13) * 9 % 13];
				}
				E[r] = s % M;
			}
			*/
			i64 s = D[0] + D[1] + D[2] + D[3] + D[4] + D[5] + D[6] + D[7] + D[8] + D[9] + D[10] + D[11] + D[12];
			E[0] = (s - D[4] - D[8] - D[12]) % M;
			E[1] = (s - D[3] - D[8] - D[12]) % M;
			E[2] = (s - D[3] - D[7] - D[12]) % M;
			E[3] = (s - D[3] - D[7] - D[11]) % M;
			E[4] = (s - D[2] - D[7] - D[11]) % M;
			E[5] = (s - D[2] - D[6] - D[11]) % M;
			E[6] = (s - D[2] - D[6] - D[10]) % M;
			E[7] = (s - D[1] - D[6] - D[10]) % M;
			E[8] = (s - D[1] - D[5] - D[10]) % M;
			E[9] = (s - D[1] - D[5] - D[9]) % M;
			E[10] = (s - D[0] - D[5] - D[9]) % M;
			E[11] = (s - D[0] - D[4] - D[9]) % M;
			E[12] = (s - D[0] - D[4] - D[8]) % M;
		} else {
			i64 d = c - '0';
			/*
			REP(r, 13) {
				E[r] = D[(d - r + 13) * 9 % 13];
			}
			*/
			E[d] = D[0];
			E[(d + 10) % 13] = D[1];
			E[(d + 7) % 13] = D[2];
			E[(d + 4) % 13] = D[3];
			E[(d + 1) % 13] = D[4];
			E[(d + 11) % 13] = D[5];
			E[(d + 8) % 13] = D[6];
			E[(d + 5) % 13] = D[7];
			E[(d + 2) % 13] = D[8];
			E[(d + 12) % 13] = D[9];
			E[(d + 9) % 13] = D[10];
			E[(d + 6) % 13] = D[11];
			E[(d + 3) % 13] = D[12];
		}
		swap(D, E);
		++i;
	}
	printf("%d", D[5]);
}


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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};


int main()
{
    int H,W,h,w;
    cin>>H>>W>>h>>w;
    cout<<(H-h)*(W-w)<<endl;
 
    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
 
K,S=map(int,input().split())
 
z = list(range(0,K+1))
ans = []
 
for i in z:
  s_z = S - i
  if s_z < 0:
    pass
  elif K < s_z:
    if (K + 1) > (s_z - K):
      ans.append(K + 1 - (s_z - K))
  else:
    ans.append(s_z + 1)
 
print(sum(ans))

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ll a, b, c, k, ans;
    cin >> a >> b >> c >> k;
    if (a + b + c == 0) ans = 0;
    else if (k - a >= 0) {
        k -= a;
        ans += a;
        if (k - b >= 0) {
            k -= b;
            if (k > 0) {
                ans -= k;
            }
        }
    }
    else ans = k;
    cout << ans << endl;
}

Measured memory_bytes: 3644
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
using namespace std;
int main()
{
  int a,b,k;
  cin>>a>>b>>k;

  if((b-a+1)<=(2*k))
    for(int i=a;i<=b;i++) cout<<i<<endl;

  else
  {
    for(int i=a;i<a+k;i++) cout<<i<<endl;
    for(int i=b-k+1;i<=b;i++) cout<<i<<endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <queue>
using namespace std;

int main() {
    int n;
    while (cin >> n, n) {
        map<string, set<string> > groups;
        set<string> gs;
        string group1;
        for (int i = 0; i < n; i++) {
            string line;
            cin >> line;
            size_t pos = line.find_first_of(':');
            string group = line.substr(0, pos);
            line.erase(0, pos + 1);
            if (i == 0) {
                group1 = group;
            }
            gs.insert(group);
            set<string> members;
            while (pos = line.find_first_of(",."), pos !=string::npos) {
                members.insert(line.substr(0, pos));
                line.erase(0, pos + 1);
            }
            groups[group] = members;
        }
        while (true) {
            set<string> members = groups[group1];
            queue<string> q;
            for (set<string>::iterator it = members.begin(); it != members.end(); it++) {
                set<string>::iterator jt = gs.find(*it);
                if (jt != gs.end()) {
                    q.push(*jt);
                }
            }
            if (q.empty()) {
                break;
            }
            while (!q.empty()) {
                string g = q.front();
                q.pop();
                groups[group1].erase(g);
                set<string> m = groups[g];
                for (set<string>::iterator it = m.begin(); it != m.end(); it++) {
                    groups[group1].insert(*it);
                }
            }
        }
        cout << groups[group1].size() << endl;
    }
}

Measured memory_bytes: 1440
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
int main(){
//	freopen("b.in","r",stdin);
//	freopen("b.out","w",stdout);
	int cas;
	cin>>cas;
	ll x,y;
	while(cas--){
		scanf("%lld%lld",&x,&y);
		ll s=x*y;
		ll ans=0;
		ll m=sqrt(s);
		if(m*m==s){
			ans=m*2-1;
			if(x==y) --ans;
			else ans-=2;
			cout<<ans<<endl;
		}else {
			ans=m*2;
			if(m*(m+1)>=s) --ans;
			cout<<ans-1<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
int main() {
  ios::sync_with_stdio(0); 
  cin.tie(0); 
  
  int n;
  string s;
  cin >> n >> s;


  int curr = 0, res = 0;

  for (int i = 0; i < n; ++i) {
    if (s[i] == 'I') curr++;
    else curr--;
    res = max(res, curr);
  }

  cout << res << "\n";
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
#define LL long long int
#define w(t) while(t--)
#define fo(i,n) for(int i = 0;i < n;i++)
#define vi vector<int>

using namespace std;
/*
100 (101/100)^n = X

n log(101) - (n-1)log(100) = log X
n(log(101) - log(100)) = (logX - 2)
n = lo
*/
int main(){
    LL x;
    cin>> x;
    //int i,t;
    //n = (log10(x) - 2)/(log10(101) - 2);
    
    LL v  = 100,num = 0,interest = 0;
    while(v < x){
        interest = (v/100);
        //if(interest >= 1)
        v = v + interest;
        num++; 
    }
    cout<< num<<endl;
}

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

int main(){
  int N, base=0, bonus=0;
  cin >> N;
  vector<int> A(N);
  vector<int> B(N);
  vector<int> C(N);
  for (int i = 0; i < N; i++) {
  	cin >> A.at(i);
  }
  for (int i = 0; i < N; i++) {
  	cin >> B.at(i);
  }
  for (int i = 0; i < N-1; i++) {
  	cin >> C.at(i);
  }
  
  for (int i = 0; i < N; i++) {
  	base += B.at(i);
  }
  for (int i = 0; i < N-1; i++) {
    if (A.at(i+1) - A.at(i) == 1){
      bonus += C.at(A.at(i)-1);
    }
  }
  cout << base + bonus << endl;
}

Measured memory_bytes: 256
#! /usr/bin/env python3
# -*- coding:utf-8 -*-

def attackSurvival(n, k, q, a):
    ans = []
    import collections
    c = collections.Counter(a)
    for i in range(n):
        if c[i+1] > q - k: ans.append('Yes')
        else: ans.append('No')
    return ans

def main():
    n, k, q = map(int, input().split())
    a = []
    for _ in range(q):
        a.append(int(input()))
    for ans in attackSurvival(n, k, q, a): print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 11920
using System;

public class Program
{
	public static void Main()
	{
        var input = Convert.ToInt32(Console.ReadLine(), 2);

        var count = 0;
        while (input != 0)
        {
            if ((input & 0x01) == 1) count++;
            input >>= 1;
        }

        Console.WriteLine(count);
	}
}


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

#define ALL(v) (v).begin(), (v).end()
#define rep(i, n) for (ll i = 0, __##i##_length = (n); i < __##i##_length; i++)
#define rep_reverse(i, n) for (ll i = (n)-1; 0 < i; i--)
#define FOR(i, from, to)                                                       \
  for (ll i = (from), __##i##_end = (to); i < __##i##_end; i++)
#define FOR_REVERSE(i, from, to)                                               \
  for (ll i = (to)-1, __##i##_end = (from); __##i##_end <= i; i--)
#define foreach(e, v) for (const auto e : (v))
#define vfree(v) std::vector<int>().swap(v)
#define DEBUG(x) cout << #x << " = " << (x) << endl

using namespace std;
typedef int64_t ll;
typedef vector<ll> llv;
typedef vector<llv> llvv;

bool strawberry_is_exist(string s) {
  bool exist = false;
  rep(i, s.size()) if (s[i] == '#') exist = true;

  return exist;
}

int main() {
  ll n;
  cin >> n;
  llv a(n);
  rep(i, n) cin >> a[i];
  sort(ALL(a));
  ll count = 0, s = 0;
  rep(i, n - 1) {
    // cout << 2 * (s + a[i]) << endl;
    if (2 * (s + a[i]) >= a[i + 1])
      count++;
    else
      count = 0;

    s += a[i];
  }
  cout << count + 1 << endl;
}


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

#define fr first
#define sc second
#define pii pair < int, int >

const int N = 1e5;
int dp[2][4], a[4];

#define name "lifeguards"

main()
{
	//freopen(name".in", "r", stdin);
	//freopen(name".out", "w", stdout);
	int n, ans = 0; cin >> n;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= 3; j++)
			cin >> a[j];
		
		dp[1][1] = a[1] + max(dp[0][2], dp[0][3]);
		dp[1][2] = a[2] + max(dp[0][1], dp[0][3]);
		dp[1][3] = a[3] + max(dp[0][1], dp[0][2]);
		
		ans = max(dp[1][1], max(dp[1][2], dp[1][3]));
		
		for(int j = 1; j <= 3; j++)
			dp[0][j] = dp[1][j];
	}
	
	
	cout << ans << endl;
}
/***
***/


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(),(x).end())
#define ALL(x) x.begin(),x.end()
#define db(x) cout<<#x<<"="<<x<<endl
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
#define INF (1e9)
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;


const int MAX = 100010;
ll fac[MAX];
ll FACinit(ll a) { // a! mod
  fac[0]=fac[1] = 1;
  reps(i, 2, MAX){
    fac[i] = fac[i - 1] * i % MOD;
  }
  return fac[a];
}

void Main(){

  int N;
  cin >> N;

  string S;
  cin >> S;

  if(S[0]=='W') {cout << 0 <<"\n"; return;}
  if(S[2*N-1]=='W') {cout << 0 <<"\n"; return;}

  int ct=0;

  int d[2*N];

  d[0]=0;

  reps(i,1,2*N){
    if(S[i]==S[i-1]){
      d[i]=1-d[i-1];
    }
    else{
      d[i]=d[i-1];
    }
  }

  ct=0;
  rep(i,2*N){
    if(d[i]==0) ct++;
  }
  if(ct!=N){cout << 0 <<"\n"; return;}

  ct=0;
  ll ans=1;
  rep(i,2*N){
    if(d[i]==0) ct++;
    else {ans = ans * ct % MOD; ct--;}
  }

  ans = ans * FACinit(N) % MOD;

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


//-----------------------------------
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}
//-----------------------------------


Measured memory_bytes: 2196
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;

int A[20];
int n;
bool rec(int Q, int q, int i){
    if (i == n) {
        return q == Q;
    }
    return rec(Q,q + A[i],i+1)|rec(Q,q,i+1);
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i++) scanf("%d",&A[i]);
    
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int Q;
        scanf("%d",&Q);
        if (rec(Q,0,0)) printf("yes\n");
        else printf("no\n");
    }
    
    return 0;
}

Measured memory_bytes: 1204
#include <iostream>
#include <bits/stdc++.h>
#include <math.h>

using namespace std;

int main(){
    string s;
    cin>>s;
    string ans="Yes";
    for(int i=0;i<s.size();i+=2){
        if(s.size()%2==1){
            ans="No";
            break;
        }
        if(s.at(i)!='h' || s.at(i+1)!='i'){
            ans="No";
            break;
        }
    }
    
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	static long dist[][];
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);		
		int N = sc.nextInt();
		int X = sc.nextInt();
		int Y = sc.nextInt();
		dist = new long[N][N];
		for(int i = 0; i < N; i++) {
			Arrays.fill(dist[i], Integer.MAX_VALUE);
		}
		
		for(int i = 0; i < N - 1; i++) {
			dist[i][i + 1] = 1;
		}
		dist[X - 1][Y - 1] = 1;
		
		int ans[] = new int[N];
		for(int i = 1; i <= N; i++) {
			for(int j = i + 1; j <= N; j++) {
				ans[(int)Math.min(j - i, Math.abs(j - Y) + Math.abs(X - i) + 1)]++;
			}
		}
		for(int i = 1; i < N; i++) {
			System.out.println(ans[i]);
		}
	}
}


Measured memory_bytes: 78932
# -*- coding: utf-8 -*-
"""
Created on Sun Dec  2 18:15:53 2018
ABC084C
@author: maezawa
"""
import math
n = int(input())
c=[]
s=[]
f=[]
for i in range(n-1):
    ci, si, fi = list(map(int, input().split()))
    c.append(ci)
    s.append(si)
    f.append(fi)
for j in range(n-1):
    ti = s[j]+c[j]
    for i in range(j+1,n-1):
        #print(j, i, ti)
        if s[i] >= ti:
            m = 0
        else:
            m = math.ceil((ti-s[i])/f[i])
        ti = s[i]+m*f[i]+c[i]
    print(ti)
print(0)

Measured memory_bytes: 3188
#include<stdio.h>
#define FOR(x,y) for(x=0;x<y;x++)
int main(void)
{
	int x = 0;
	int max = 0;
	char str[101];
	int i,s;
	scanf("%d", &s);
	scanf("%s", str);
	FOR(i, s)
	{
		if (str[i] == 'I') x++;
		else if (str[i] == 'D') x--;

		if (x > max) max = x;
	}
	printf("%d\n", max);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 28;

int m, n;
int arr[300];
int dist[300][300];
bool ok[300];

void dfs(int v)
{
	ok[v] = true;
	for (int i = 1; i <= m; i++){
		int to = max(0, min(v + i, n + 1));
		to += arr[to];
		if (!ok[to]) dfs(to);
	}
}

string solve()
{
	for (int i = 0; i <= n; i++){
		if (!ok[i]) continue;
		if (dist[i][n + 1] == INF) return "NG";
	}
	return "OK";
}

int main()
{
	while (scanf("%d", &m), m){
		fill_n(arr, 300, 0);
		fill_n(*dist, 300 * 300, INF);
		fill_n(ok, 300, false);
		
		scanf("%d", &n);
		for (int i = 1; i <= n; i++){
			scanf("%d", &arr[i]);
		}
		
		dfs(0);
		
		for (int i = 0; i <= n; i++){
			for (int j = 1; j <= m; j++){
				int to = max(0, min(i + j, n + 1));
				to += arr[to];
				dist[i][to] = 1;
			}
		}
		
		for (int k = 0; k <= n + 1; k++){
			for (int i = 0; i <= n + 1; i++){
				for (int j = 0; j <= n + 1; j++){
					dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
				}
			}
		}
		
		cout << solve() << endl;
	}
}

Measured memory_bytes: 1572
#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
 
#define rp(i, k, n) for (int i = k; i < n; i++)
using ll = long long;
using ld = double;

template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF = 1ll << 60;
const ll MOD = 1e9 + 7ll;
const double PI=3.14159265358979323846;

int main() {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << max({a*c, a*d, b*c, b*d}) << endl;
    return 0;
}


Measured memory_bytes: 3648
#include <stdio.h>

int main(void)
{
	int h1, m1, s1, h2, m2, s2;
	int s;
	int i;
	
	for (i = 0; i < 3; i++) {
		scanf("%d %d %d %d %d %d", &h1, &m1, &s1, &h2, &m2, &s2);
		s = (h2 - h1) * 3600 + (m2 - m1) * 60 + s2 - s1;
		printf("%d %d %d\n", s / 3600, (s % 3600) / 60, (s % 3600) % 60);
	}
	return (0);
}

Measured memory_bytes: 600
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String... args) {
		Scanner scan = new Scanner(System.in);
		int[] a = new int[9];
		for (int i = 0; i < 9; i++) {
			a[i] = scan.nextInt();
		}
		int n = scan.nextInt();
		List<Integer> b = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {
			b.add(scan.nextInt());
		}

		System.out.println(bingo(a, b) ? "Yes" : "No");
		scan.close();
	}

	private static boolean bingo(int[] a, List<Integer> b) {
		for (int i = 0; i < 3; i++) {
			if (b.contains(a[i * 3]) && b.contains(a[i * 3 + 1]) && b.contains(a[i * 3 + 2])) {
				return true;
			}
		}

		for (int i = 0; i < 3; i++) {
			if (b.contains(a[i]) && b.contains(a[3 + i]) && b.contains(a[6 + i])) {
				return true;
			}
		}

		if (b.contains(a[0]) && b.contains(a[4]) && b.contains(a[8])) {
			return true;
		}

		if (b.contains(a[2]) && b.contains(a[4]) && b.contains(a[6])) {
			return true;
		}

		return false;
	}
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,k;
  cin>>n>>k;
  vector<int> v(n+1,0);
  for(int i=0;i<k;i++)
  {
    int d,a;
    cin>>d;
    for(int i=0;i<d;i++)
    {
      cin>>a;
      v[a]=1;
    }
  }
  int ans=0;
  for(int i=1;i<n+1;i++)
  {
    if(!v[i])
      ans++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define mod 1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
ll a[20][20];
ll dp[1<<16];
ll dp2[1<<16];
int main(){
    int n;
    cin >> n;
    rep(i,n){
        rep(j,n){
            cin >> a[i][j];
        }
    }
    rep(s,1<<n){
        rep(i,n){
            rep(j,n){
                if(i<j){
                    if((s>>i)&1){
                        if((s>>j)&1){
                            dp2[s] += a[i][j];
                        }
                    }
                }
            }
        }
        //cerr << dp2[s] << endl;
    }
    rep(s,1<<n){
        for(int bit = s;bit!=0; bit = (bit-1)&s){
            dp[s] = max({dp[s],dp[bit]+dp[s-bit],dp2[bit]+dp2[s-bit]});
        }
    }
    cout << dp[(1<<n)-1] << endl;
    return 0;
}

Measured memory_bytes: 1280
//Begin Template
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
// define
const int INF = 1<<24;
#define endl "\n"
#ifdef LOCAL
#define lout cerr
#else
ostream devnull(0);
#define lout devnull
#endif
#define AMULET cin.tie(0);ios::sync_with_stdio(false);
// Inspired by: https://github.com/kurokoji/.cpp-Template/blob/master/template/template2.cpp
#define GET_MACRO(_1, _2, _3, _4, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep4, rep3, rep2, rep1) (__VA_ARGS__)
#define rep1(n) rep2(_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, n) rep4(i, a, n, 1)
#define rep4(i, a, n, d) rep5(i, a, n, d, <)
#define rep5(i, a, n, d, o) for (auto i = decltype(n)(a), _n = (n); i o _n; i += (d))

#define rrep(...) GET_MACRO(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rrep1(a) rrep2(_, a)
#define rrep2(i, a) rrep3(i, a, 0)
#define rrep3(i, a, n) rrep4(i, a, n, -1)
#define rrep4(i, a, n, d) rep5(i, (a) - 1, n, d, >=)

#define repc(...) GET_MACRO(__VA_ARGS__, repc4, repc3, repc2, repc1) (__VA_ARGS__)
#define repc1(n) repc2(_, n)
#define repc2(i, n) repc3(i, 0, n)
#define repc3(i, a, n) repc4(i, a, n, 1)
#define repc4(i, a, n, d) rep5(i, a, n, d, <=)

#define dump(x) lout << #x << " = " << x << endl;
// alias
typedef long long ll;
typedef long long lint;
typedef pair<int,int> pii;
typedef pair<lint,lint> pll;
// func
template <class C> inline void vcin(C &c);
template <class C,class D> inline void vcin(C &c,D &d);
template <class C> inline void vcout(const C &c,const string separate="\n");
template <class T=int> inline T in();
template <class T> inline bool chmin(T &a, T b);
template <class T> inline bool chmax(T &a, T b);
//http://beet-aizu.hatenablog.com/entry/2018/04/08/145516
template<typename T> vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}

void solve()
{
  int x, y, z, K;
  cin >> x >> y >> z >> K;
  vector<lint> a(x), b(y), c(z);
  vcin(a);
  vcin(b);
  vcin(c);

  vector<lint> ab;
  rep(i, x) rep(j, y)
  {
    ab.push_back(a[i] + b[j]);
  }

  sort(ab.rbegin(), ab.rend());
  ab.resize(K);

  vector<lint> abc;

  rep(i, ab.size()) rep(k, z)
  {
    abc.push_back(ab[i] + c[k]);
  }

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

  rep(l, K)
  {
    cout << abc[l] << endl;
  }
}

signed main(){
  AMULET
  solve();
  return 0;
}

template <class C>inline void vcin(C &c){for(auto &a:c){cin>>a;}}
template <class C,class D> inline void vcin(C &c,D &d){for(auto it1=c.begin(),it2=d.begin();it1!=c.end()&&it2!=d.end();it1++,it2++){cin>>*it1>>*it2;}}
template <class C> inline void vcout(const C &c,const string separate){for(auto it=c.begin();it!=c.end();it++){if(it!=c.begin())cout<<separate;cout<<*it;}}
template <class T=int> inline T in(){T x;cin>>x;return (x);}
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;}
//End Template


Measured memory_bytes: 43112
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i)
#define all(a) (a).begin(), (a).end()
template <typename T = int>
class Convolution {
  using C = complex<double>;
  const C ZERO = C(0.0, 0.0);
  vector<T> conv;

  vector<C> dft(const vector<C>& x) {
    int n = x.size();

    if (n == 1) return x;

    assert(n % 2 == 0);

    vector<C> even(n / 2), odd(n / 2);
    for (int i = 0; i < n / 2; ++i) {
      even[i] = x[2 * i];
      odd[i] = x[2 * i + 1];
    }

    vector<C> q = dft(even), r = dft(odd);
    vector<C> y(n);
    for (int i = 0; i < n / 2; ++i) {
      double ith = -2.0 * i * M_PI / n;
      C wi(cos(ith), sin(ith));
      y[i] = q[i] + wi * r[i];
      y[i + n / 2] = q[i] - wi * r[i];
    }

    return y;
  }

  vector<C> inverseDft(const vector<C>& x) {
    int n = x.size();
    vector<C> y(n);
    for (int i = 0; i < n; ++i) {
      y[i] = conj(x[i]);
    }

    y = dft(y);

    for (int i = 0; i < n; ++i) {
      y[i] = conj(y[i]);
      y[i] /= n;
    }

    return y;
  }

 public:
  Convolution(const vector<T>& a, const vector<T>& b) {
    int n = a.size(), m = b.size();
    int l = 1;
    while (n + m >= l) l *= 2;

    vector<C> ca(l, ZERO), cb(l, ZERO);
    for (int i = 0; i < n; ++i) ca[i] = C(a[i], 0.0);
    for (int i = 0; i < m; ++i) cb[i] = C(b[i], 0.0);

    vector<C> fa = dft(ca), fb = dft(cb);
    vector<C> fc(l);
    for (int i = 0; i < l; ++i) {
      fc[i] = fa[i] * fb[i];
    }

    vector<C> c = inverseDft(fc);
    conv.resize(l);
    for (int i = 0; i < l; ++i) {
      conv[i] = round(c[i].real());
    }
  }

  T operator[](int i) { return conv[i]; }

  vector<T> toVector() { return conv; }
};

int N;
ll M;
vector<int> A;
const int SUM_MAX = 2e5;

int main() {
  cin >> N >> M;
  A.resize(N);
  rep(i, N) cin >> A[i];

  vector<ll> freq(SUM_MAX + 1, 0);
  rep(i, N) freq[A[i]] += 1;

  Convolution<ll> conv(freq, freq);
  ll ans = 0;
  for (int i = SUM_MAX; i >= 0; --i) {
    ll c = min(M, conv[i]);
    ans += c * i;
    M -= c;
    if (M == 0) break;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 84216
n = int(input())
ans = 0
d = 2

while d * d <= n:
    if n % d != 0:
        d +=1
    z = d
    while n % z ==0: 
        n = n/z
        z *=d
        ans+=1
        
    while n%d == 0: #残った素因数を消化
        n /= d

if n !=1:
    ans+=1

print(ans)

Measured memory_bytes: 9124
A, B, Q = gets.split.map(&:to_i)
S = A.times.map{ gets.to_i }+[Float::INFINITY,-Float::INFINITY]
T = B.times.map{ gets.to_i }+[Float::INFINITY,-Float::INFINITY]
Q.times{
	x = gets.to_i
	si = S.bsearch_index{|s| x < s }||A
	ti = T.bsearch_index{|t| x < t }||B
	sl,sr,tl,tr = S[si-1],S[si],T[ti-1],T[ti]
	p [
		[sr,tr].max-x,
		x-[sl,tl].min,
		sr-tl+[sr-x,x-tl].min,
		tr-sl+[tr-x,x-sl].min
	].min
}


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

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999

using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

struct edge { int to, cost; };
typedef pair<int, int> P;

int iy[]={0, 0, 1, -1};
int ix[]={1, -1, 0, 0};

int n, m, a, b;
vector<edge> G[101];
int d[101];

int main(){
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> i;
		cin >> m;
		for(int k=0;k<m;k++){
			cin >> a >> b;
			G[i].push_back({a,b});
		}
	}

	priority_queue<P, vector<P>, greater<P> > que;
	fill(d,d+n,INF);
	d[0] = 0;
	que.push(P(0,0));

	while(!que.empty()){
		P p = que.top(); que.pop();
		int u = p.second;
		if(d[u] < p.first) continue;
		for(int i=0;i<G[u].size();i++){
			edge e = G[u][i];
			if(d[e.to] > d[u]+e.cost){
				d[e.to] =d[u]+e.cost;
				que.push(P(d[e.to],e.to));
			}
		}
	}
	for(int i=0;i<n;i++){
		cout << i << " " << d[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 3168
#include <stdio.h>
#include <string.h>

int main(void)
{
	char str[101];
	int  i;
	int  len;
	int  count = 0;
	
	while (scanf("%s", str) != EOF){
		len = strlen(str);
		for (i = 0; i <= len / 2; i++){
			if (str[i] != str[len - i - 1]){
				break;
			}
		}
		if (i == len / 2 + 1){
			count++;
		}
	}
	
	printf("%d\n", count);
	
	return (0);
}

Measured memory_bytes: 540
from math import *
import fractions
import sys
import collections
import itertools
import pprint
from collections import deque
from heapq import *
import copy
input=sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
n = 10**6
d={}
pairflag=1
setflag=0
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)
#print(len(primes))
buf=[0]*(max(A)+10)
seen=[0]*(max(A)+10)
for i in range(N):
    if d.get(A[i])==None:
        d[A[i]]=1
    else:
        d[A[i]]=d[A[i]]+1
#print(d)
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
for i in primes:
    cnt=0
    for j in range(i,10**6+1,i):
        if d.get(j)!=None:
            cnt=cnt+d[j]
    if cnt>1:
        pairflag=0
        break

num=A[0]
for i in range(1,N):
    num=ggcd(num,A[i])
if num==1:
    setflag=1
else:
    setflag=0

if pairflag==1:
    print("pairwise coprime")
elif setflag==1:
    print("setwise coprime")
else:
    print("not coprime")

"""
x=list(set(A))
for i in x:
    for j in range(2*i,10**6+1,i):
        if d.get(j)!=None:
            pairflag=0
            break
    if pairflag==0:
        break
print(pairflag)

"""

Measured memory_bytes: 270416
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n) for(int i=1;i<=n;i++)
const ll MOD = 1000000007;
long long modinv(long long a, long long m=MOD) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
    /*MODの割り算の際に
    a/＝b;
    を
    a *= modinv(b,MOD);
    とする。
        */
}

char c[7][7];
char tmp[7][7];
int H,W,K;
void cpy(){
    rep(i,H)rep(j,W)tmp[i][j]= c[i][j];
}

void showtmp() {
    rep(i,H){
        rep(j,W) {
            cout << tmp[i][j];
        }
        cout << endl;
    }
}

int main(){
    cin >> H >> W >>K;

    rep(i,H)rep(j,W){
        cin >> c[i][j];
    }
    
    int ans = 0;

    for(int i=0;i<(1<<H);i++) {
        for(int j=0;j<(1<<W);j++) {
            cpy();
            for(int bit=0;bit<H;bit++) {
                for(int bin=0;bin<W;bin++) {
                    if(i&(1<<bit)) {
                        for(int k=0;k<W;k++) tmp[bit][k] = 'r';
                    }
                    if(j&(1<<bin)) {
                        for(int k=0;k<H;k++) tmp[k][bin] = 'r';
                    }
                }
            }
            int counter = 0;
            rep(r,H)rep(l,W)if(tmp[r][l]=='#')counter++;
            if(counter==K)ans++;
        }
    }

    cout << ans << endl;
    return 0;
}

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


using namespace std;


using ll = long long;
mt19937 mt(736);


void solve(istream &cin = std::cin, ostream &cout = std::cout)
{
	int n;

	cin >> n;

	vector<int> a(n), b(n);

	for (auto &it : a)
		cin >> it;

	priority_queue<pair<int, int>> pq;

	for (size_t i = 0; i < b.size(); i++)
	{
		cin >> b[i];

		if (b[i] < a[i])
		{
			cout << -1 << endl;

			return;
		}

		pq.emplace(b[i], i);
	}

	ll cnt = 0;

	while (!pq.empty())
	{
		int wh = pq.top().second;

		pq.pop();

		assert(b[wh] >= a[wh]);

		if (b[wh] > a[wh])
		{
			auto sub = b[wh == 0 ? n - 1 : wh - 1] + b[wh + 1 == n ? 0 : wh + 1];

			if (sub > b[wh])
			{
				cout << -1 << endl;

				return;
			}

			if ((b[wh] - a[wh]) % sub == 0)
			{
				cnt += (b[wh] - a[wh]) / sub;
				b[wh] = a[wh];
			}
			else
			{
				cnt += b[wh] / sub;
				b[wh] %= sub;
			}

			if (b[wh] < a[wh])
			{
				cout << -1 << endl;

				return;
			}

			pq.emplace(b[wh], wh);
		}
	}

	cout << cnt << endl;
}


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

	cout << fixed;

#ifdef LOCAL
	ifstream fin("../input.txt");

	solve(fin);

	cout << setprecision(4);
	cout << "clock: " << clock() / (double) CLOCKS_PER_SEC << endl;
#else
	solve();
#endif

	return 0;
}


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

int main()
{
  vector<int> vec(3);
  cin>>vec[0]>>vec[1]>>vec[2];
  sort(vec.begin(),vec.end());
  int ans=vec[2]-vec[1];
  int d=vec[2]-vec[0]-ans;
  ans+=(d%2==0)? d/2:((d+1)/2+1);
  cout<<ans;
  
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int main(){
  int N;cin>>N;
  int AA[N+10],AB[N+10],Ar[N+10],Br[N+10];
  Ar[0]=0;Br[0]=0;
  rep(i,N){
    cin>>AA[i];
    Ar[i+1]=Ar[i]+AA[i];
  }
  rep(i,N){
    cin>>AB[i];
    Br[i+1]=Br[i]+AB[i];
  }
  int ans=0;
  for(int i=1;i<=N;i++){
      ans=max(ans,Ar[i]+(Br[N]-Br[i-1]));
    }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
fn f(n: &i64, k: &i64) -> i64{
    let min: i64 = k*(k-1)/2;
    let max: i64 = k*((n-k+1) + n)/2;

    return max - min + 1;
}

fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    let s: Vec<i64> = s.trim().split(' ').map(|x| x.parse::<i64>().unwrap()).collect();

    let mut cnt = 0;
    for i in s[1]..(s[0]+2){
        cnt += f(&s[0], &i);
    }
    cnt %= i64::pow(10, 9) + 7;

    println!("{}", cnt);
}

Measured memory_bytes: 2120
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  int N = S.size();
  int sum = 0;
  for(int i = 0; i < N / 2; i++) {
    if(S.at(i) != S.at(N-i-1)) sum++;
  } 
  cout << sum << endl;
}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n,ans = 1;cin>>n;
  vector<ll> cvec(n);
  for (ll i = 0; i < n; ++i) cin >> cvec[i];
  for (ll i = 1; i < n; ++i) {
    ll h = cvec[i];
    bool view = true;
    for (ll j = 0; j < i; ++ j) if (cvec[j] > h) view = false;
    if (view) ans += 1;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from functools import lru_cache

A = int(readline())
B = int(readline())

@lru_cache(None)
def can_make(A,B):
    # [A,B] の元のorで、{B} 以外の方法でBを作れるかどうか。たいていTrue
    if A == B:
        return False
    if B%2 == 0:
        return can_make((A+1)//2,B//2)
    # Bが奇数なら、{B-1,B}が満たす
    return True

@lru_cache(None)
def F(A,B):
    if A==B:
        return 1
    # 偶数の作り方
    ev = F((A+1)//2,B//2)
    # 奇数の作り方
    if A%2==0:
        A += 1
    if B%2 == 1:
        od = F(A//2,B//2)
    else:
        # 上位の桁では基本的にはA//2～B//2が使える。
        # ただし、{B} 以外でないといけない
        od = F(A//2,B//2)
        if not can_make(A//2,B//2):
            od -= 1
    return ev + od

answer = F(A,B)
print(answer)

Measured memory_bytes: 3684
#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    int n;
    string s;
    cin >> n;
    cin >> s;
    int l = 0;
    int  r = n-1;
    int cnt = 0;
    
    while(l <= r){
        
        while(l < n && s[l] != 'W')
            l++;
            
        while(r >= 0 && s[r] != 'R')
            r--;
            
        if(l < n && r >= 0 && l < r){
            char tmp = s[r];
            s[r] = s[l];
            s[l] = tmp;
            l++;
            r--;
            cnt++;
        }
            
    }
    
    cout << cnt << endl;;
    return 0;
}

Measured memory_bytes: 3756
import std.stdio, std.string, std.array, std.conv;

bool linearSearch(int n, int key, int[] x) {
    int i = 0;
    x ~= key;
    while (x[i] != key) ++i;
    return i != n;
}

void main() {
    int n = readln.chomp.to!int;
    int[] s = readln.chomp.split.to!(int[]);
    int q = readln.chomp.to!int;
    int[] t = readln.chomp.split.to!(int[]);
    int cnt = 0;
    foreach (x; t) {
        if (linearSearch(n, x, s)) ++cnt;
    }
    cnt.writeln;
}


Measured memory_bytes: 5016
#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<unordered_map>
#include<algorithm>
#include<cmath>
#include<tuple>
#include<iomanip>
#include<climits>
#define ll long long int
#define mod 1000000007
#define pi acos(-1)
using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n ,k;
  cin>>n>>k;
  int digit=0;
  while(n!=0)
  {
    n=n/k;
    digit++;
  }
  cout<<digit;
  return 0;
}

Measured memory_bytes: 256