akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = (s); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i = (n); i >= 0; i--)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    constexpr int INF = 1 << 30;
    int N; cin >> N;
    vector<pii> m(2,{-INF,INF});
    REP(i,N) {
        int x, y;
        cin >> x >> y;
        m[0].first = max(m[0].first,x+y);
        m[0].second = min(m[0].second,x+y);
        m[1].first = max(m[1].first,x-y);
        m[1].second = min(m[1].second,x-y);
    }
    OUT(max(abs(m[0].first-m[0].second),abs(m[1].first - m[1].second)))

    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <string>

using namespace std;

struct List{
  string str;
  List* next;

  List(){
    str = "";
    next = NULL;
  }
};


struct Dict{
  List list[20000];

  int hash(string str){
    int hash_num = 0;
    for(int i=0;i<str.length();i++){
      int c = (int)str[i];
      hash_num += c*c*c+i*c*c+c*i*i+c;
    }
    return hash_num;
    
  }
  void insert(string str){
    int key = hash(str)%20000;
    List *target;
    List *item = new List();
    item->str = str;
    
    target = &list[key];
    while(target->next != NULL){
      if(target->next->str==str) return;
      target = target->next;
    }
    target->next = item;
  }
  void find(string str){
    int key = hash(str)%20000;
    List *target;
    target = &list[key];
    if(target->next==NULL){
      cout<<"no"<<endl; return;
    }
    target = target->next;
    while(true){
      if(target->str==str){
        cout<<"yes"<<endl;
        return;
      }else if(target->next==NULL){
        cout<<"no"<<endl;
        return;
      }else{
        target = target->next;
      }
    }
  }
};

int main(){
  int n; cin>>n;
  string ope, str;
  Dict dict;
  for(int i=0;i<n;i++){
    cin>>ope>>str;
    if(ope=="insert"){
      dict.insert(str);
    }else if(ope=="find"){
      dict.find(str);
    }
  }
}

Measured memory_bytes: 52876
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
using namespace std;

#define lint long long int
#define Q_MAX 50
#define N_MAX 10
#define M_MAX 10

int n, m, q;
int a[N_MAX];
int max_score = -1;

typedef struct {
    int a, b, c, d;
} SC;
SC sc[Q_MAX];


void get_ar(int *head, int n_ar, int mini)
{
    for (int i = mini; i <= m; i++) {
        *head = i;
        
        if (n_ar != 1) get_ar(&head[1], n_ar-1, i);
        else {
            int sum = 0;
            for (int j = 0; j < q; j++) {
                if (a[sc[j].b-1] - a[sc[j].a-1] == sc[j].c) sum += sc[j].d;
            }
            max_score = max(max_score, sum);
        }
    }
}


int main()
{
    cin >> n >> m >> q;
    for (int i = 0; i < q; i++) cin >> sc[i].a >> sc[i].b >> sc[i].c >> sc[i].d;
    
    get_ar(a, n, 1);
    cout << max_score << endl;
}


Measured memory_bytes: 3636
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<math.h>
#include<map>
using namespace std;
	
int main(){
	long long n,q,cnt=0;
	cin >> n >> q;
	
	string s;
	cin >> s;
	long long c[n];
	c[0]=0;
	for(long long i=1;i<=n;i++){
		c[i]=cnt;
		if(s[i]=='C' && s[i-1]=='A'){
			cnt++;
			c[i]=cnt;
		}
	}
	
	long long a[q][2];
	for(long long i=0;i<q;i++){
		cin >> a[i][0];
		cin >> a[i][1];
	}	
	
	for(long long i=0;i<q;i++){
		cout << c[a[i][1]-1]-c[a[i][0]-1] << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3456
/*
By Tianyi Chen. All rights reserved.
Date: 2016-08-13
*/
#include<bits/stdc++.h>
using namespace std;
char buf[100001];int n;
int cnt[128],prp[100001],pc,qq;
int main() {
 scanf("%s",buf);n=strlen(buf);
 for(int c='a';c<='z';++c) {
  memset(cnt,0,sizeof cnt);pc=0;qq=0;
  for(int i=0;i<n;++i) {
   if (buf[i]==c) {
    for(int j=0;j<pc;++j) {
     if (++qq>50000000)goto nt;
     if (pc-j+1<<1>i-prp[j]+1)return printf("%d %d\n",1+prp[j],++i),0;
    }
    prp[pc++]=i;
   }
  }
 nt:;
 }
 puts("-1 -1");
}

Measured memory_bytes: 512
function Main(input) {
    input = input.split("\n");
    var map = new Map([["A", "T"], ["T", "A"], ["C", "G"], ["G", "C"]]);
    var b = input[0];
    console.log(map.get(b));
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

#define sz(x) int(x.size())
#define pii pair<int, int>
#define Task "abc"
#define For(i, a, b) for(int i = (a), _b = (b); i <= b; ++i)
#define Debug(X) cout << #X << " = " << X << '\n'
#define All(x) (x).begin(), (x).end()
#define mp make_pair

typedef unsigned long long ull;
typedef long long ll;

const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
//  freopen(Task".inp", "r", stdin);
//  freopen(Task".out", "w", stdout);
  ll n, k; cin >> n >> k;
  cout << min(n % k, k - n % k);
}



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

typedef long long ll;
typedef vector <ll> v_ll;
typedef vector <vector <ll> > vv_ll;
typedef vector < pair <ll,ll> > vp_ll;
typedef pair <ll,ll> p_ll;

bool TEST=false;
ll MOD = 1000000007;

void show(){if (TEST){cout << endl;}}
void show(string x){if (TEST){cout << x;}}
void show(string x,bool enter){
  if (TEST){if (enter) cout << "<#> " << x << endl;else cout << x;}
}
void show(ll x){if (TEST){cout << x;}}
void show(ll x,bool enter){
  if (TEST){if (enter) cout << "<#> " << x << endl;else cout << x;}
}
void show(p_ll p){
  if (TEST){cout << "{ ";show(p.first);cout << " ";show(p.second);cout << " }";}
}
void show(v_ll v){
  if (TEST){
    cout << "<begin> ";
    for (ll i=0;i<v.size();i++){show(v[i]); cout << " ";}cout <<"<end>"<< endl;
}}
void show(vv_ll v){
  if (TEST){
    cout << "//////////" << endl;
    for (ll i=0;i<v.size();i++){
      show(v[i]); cout << endl;
}}}
void show(vp_ll v){
  if (TEST){
    cout << "//////////" << endl;
    for (ll i=0;i<v.size();i++){
      show(v[i]); cout << endl;
}}}

ll mod(ll x){
  ll n=MOD;
  ll ret=x%n;
  if (ret<0)ret+=n;
  return ret;
}
void mod_self(ll &x){
  x=mod(x);
}
ll mod_inv(ll x){
  ll n=MOD;
  ll y = x,z = n-2, ret=1;
  y=mod(y);
  while (z>0){
    if(z%2==1) ret=mod(ret*y);
    y=mod(y*y);
    z/=2;
  }
  return ret;
}
ll mod_pow(ll x,ll a){
  ll y = x,z = a,ret=1;
  y=mod(y);
  if (z<0)z=-z;
  while (z>0){
    if(z%2==1) ret=mod(ret*y);
    y=mod(y*y);
    z/=2;
  }
  if (a<0) ret=mod_inv(ret);
  return ret;
}
v_ll mod_nck(ll n){
  v_ll nck(n+1,0);
  nck[0]=1;
  for (ll i=1;i<=n;i++){
    nck[i]=mod(nck[i-1]*(n+1-i));
    nck[i]=mod(nck[i]*mod_inv(i));
  }
  return nck;
}
v_ll mod_factorial(ll n){
  v_ll fct(n+1,0);
  fct[0]=1;
  for (ll i=1;i<=n;i++){
    fct[i]=mod(fct[i-1]*i);
  }
  return fct;
}

ll N,A,B;
int main(){
  cin >> N >> A >> B;
  cout << min(N*A,B) << endl;
}


Measured memory_bytes: 888
#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int dp[1001],N,v[1001],w[1001],W;
signed main(){
    for(int l=1;;l++){
        fill(dp,dp+1001,0);
        /*fill(v,v+100,0);
        fill(w,w+100,0);*/
        cin>>W;
        if(W==0)break;
        cin>>N;
        for(int i=0;i<N;i++){
            scanf("%lld,%lld",&v[i],&w[i]);
        }
        for(int i=0;i<N;i++){
            for(int j=W;j>=w[i];j--){
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        for(int i=W;i>=0;i--){
            if(dp[W]!=dp[i]){
                cout<<"Case "<<l<<":"<<endl<<dp[W]<<endl<<i+1<<endl;
                break;
            }
        }
    }
    return 0;
}

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

const int inf = 1e9;

int n;
int p2[30];
char s[200005];
map<int,int> dp;

int get(int x) {
    if(dp.find(x)==dp.end()) return inf;
    return dp[x];
}

int main() {
    int cur;
    p2[0] = 1;
    for(int i=1;i<=26;i++) p2[i] = p2[i-1]*2;
    scanf(" %s",s);
    n = strlen(s); cur = 0; dp[0] = 0;
    for(int i=0;i<n;i++) {
        cur ^= p2[s[i]-'a'];
        int val = get(cur);
        for(int pos=0;pos<26;pos++) val = min(val,get(cur^p2[pos])+1);
        dp[cur] = val;
    }
    if(cur==0) printf("1");
    else printf("%d",get(cur));
}


Measured memory_bytes: 9856
#include<stdio.h>
int main()
{
	int a,b,c,d,m,n;
	scanf("%d %d",&m,&n);
	a=m;
	b=n;
	c=0;
	d=0;
	while(a!=0)
	{
		a--;
		c=10*c+n;
	}
	while(b!=0)
	{
		b--;
		d=10*d+m;
	}
	if(c>=d)
	printf("%d",c);
	else 
	printf("%d",d);
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <set>
#include <map>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long lint;

struct edge {
    int v;
    lint w;
    edge() {}
    edge(int v, lint w) : v(v), w(w) {};
};

vector<lint> dijkstra(int n, vector<vector<edge> >& G, int s) {
    vector<lint> d(n, 1e18/10); d[s] = 0;
    priority_queue<pair<lint, int> > que;
    que.push(make_pair(0ll, s));
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int u = p.second;
        lint dist = -p.first;
        if (dist > d[u]) continue;
        for (edge e : G[u]) {
            if (d[e.v] > d[u]+e.w) {
                d[e.v] = d[u] + e.w;
                que.push(make_pair(-d[e.v], e.v));
            }
        }
    }
    return d;
}

int main() {
    int K;
    cin >> K;
    vector<vector<edge> > G(K+1);
    for (int i = 0; i < K; i++) {
        // +1
        {
            int next = (i+1)%K;
            if (i != 0 && next == 0) next = K;
            G[i].emplace_back(next, 1);
        }
        // *10
        {
            int next = (i*10)%K;
            if (i != 0 && next == 0) next = K;
            G[i].emplace_back(next, 0);
        }
    }
    auto d = dijkstra(K+1, G, 0);
    cout << d[K] << endl;
    return 0;
}

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

using namespace std;

#define LL long long
#define DD double
#define Pb push_back
#define Bp pop_back
#define Pf push_front
#define Fp pop_front
#define Ub upper_bound
#define Lb lower_bound
#define In insert
#define All(x) x.begin(), x.end()
#define mem(a, b) memset(a, b, sizeof(a))
#define fast ios_base::sync_with_stdio(0);cin.tie(0)
#define X first
#define Y second
#define mx1 10
#define mx2 110
#define mx3 1010
#define mx4 10010
#define mx5 100010
#define mx6 1000010

typedef vector<LL> Vl;
typedef vector<DD> Vd;
typedef vector<bool> Vb;
typedef vector<Vl> VVl;
typedef pair<LL, LL> Pll;
typedef pair<DD, DD> Pdd;
typedef vector<Pll> Vpl;
typedef vector<Pdd> Vpd;
typedef queue<LL> Ql;
typedef stack<LL> Sl;
typedef deque<LL> Dl;

LL _set(LL N, LL pos) {return N = N | (1 << pos);}
LL _reset(LL N, LL pos) {return N = N & ~(1 << pos);}
bool _check(LL N, LL pos) {return (bool)(N & (1 << pos));}
bool _upper(char a) {return a >= 'A' && a <= 'Z';}
bool _lower(char a) {return a >= 'a' && a <= 'z';}
bool _digit(char a) {return a >= '0' && a <= '9';}

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

///**************************DONE****************************///

int main()
{
    LL h, w;
    cin >> h >> w;

    LL ans = 1e18;
    for(int i = 1; i <= h / 2 + h % 2; i++){
        LL a = i * w;
        LL b = w * ((h - i) / 2 + (h - i) % 2);
        LL c = w * ((h - i) / 2);

        LL x = min(a, min(b, c)), y = max(a, max(b, c));
        ans = min(ans, y - x);
    }
    for(int i = 1; i <= h / 2 + h % 2; i++){
        LL a = i * w;
        LL H = h - i;
        LL b = H * (w / 2 + w % 2);
        LL c = H * (w / 2);

        LL x = min(a, min(b, c)), y = max(a, max(b, c));
        ans = min(ans, y - x);
    }
    swap(h, w);
    for(int i = 1; i <= h / 2 + h % 2; i++){
        LL a = i * w;
        LL b = w * ((h - i) / 2 + (h - i) % 2);
        LL c = w * ((h - i) / 2);

        LL x = min(a, min(b, c)), y = max(a, max(b, c));
        ans = min(ans, y - x);
    }
    for(int i = 1; i <= h / 2 + h % 2; i++){
        LL a = i * w;
        LL H = h - i;
        LL b = H * (w / 2 + w % 2);
        LL c = H * (w / 2);

        LL x = min(a, min(b, c)), y = max(a, max(b, c));
        ans = min(ans, y - x);
    }

    cout << ans << '\n';
    return 0;
}


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

int main(){
    string w;
    cin >> w;
    sort(w.begin(),w.end());

    int count = 1;
    for(int i=0; i<w.length(); i++){
        if(i == w.length() - 1 || w[i] != w[i+1]){
            if(count % 2 != 0){
                cout << "No" << endl;
                return 0;
            }
            count = 1;
        }
        if(w[i] == w[i+1]) count += 1;
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{

    int n,k;
    int[] x;
    int[] dist;

    void solve(){
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();
        for(int ii=0; ii<t; ii++){
            n = sc.nextInt();
            k = sc.nextInt();
            x = new int[n];
            for(int i=0; i<n; i++) x[i] = sc.nextInt();

            int ans = 0;
            dist = new int[n-1];
            for(int i=0; i<n-1; i++){
                dist[i] = x[i+1]-x[i];
                ans += dist[i];
            }

            Arrays.sort(dist);
            int idx = dist.length-1;
            for(int i=0; i<k-1; i++){
                if(ans==0 || idx-i<0) break;
                ans -= dist[idx-i];
            }

            System.out.println(ans);
        }
    }

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

Measured memory_bytes: 15000
l,r = map(int, input().split())
mod = 2019
if r-l >= 2018:
  print(0)
  exit()
l %= mod
r %= mod
ans = 2019
for i in range(l,r):
  for j in range(i+1,r+1):
    m = (i*j)%mod
    if ans > m:
      ans = m
    if m == 0:
      break
print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define M_PI 3.14159265358979323846
using namespace std;


int main()
{
    int h1,h2,h,w;
    cin>>h1>>h2>>h>>w;
    long double angle=abs(((long double)h/(long double)12)*(long double)360+((long double)w/(long double)60)*(long double)30-((long double)w/(long double)60)*(long double)360);
    if(angle>(long double)180)
        angle=(long double)360-angle;
    long double ans=sqrt(((long double)(h1*h1+h2*h2)-(long double)(2*h1*h2)*cos(angle*M_PI/(long double)180)));
    cout<<setprecision(10)<<fixed<<ans<<'\n';
    return 0;

}
/***
5 4 1
1000000000 1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000
3 4 730
60 90 120
80 150 80 150
*/


Measured memory_bytes: 4172
#include <algorithm>
#include <climits>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <vector>

#define int long long int
constexpr int INF = std::numeric_limits<int>::max();
constexpr int NINF = std::numeric_limits<int>::min();
using namespace std;

void solve() {
  string s;
  int N;
  cin >> N >> s;
  for (int i = 0; i < s.size(); i++) {
    char roted = (s[i] - 'A' + N) % 26;
    s[i] = 'A' + roted;
  }
  cout << s << endl;
}

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


Measured memory_bytes: 256
//                             In The Name Of Allah                                           
//                             	Mohammad Hosseini
#include <bits/stdc++.h>
#define	ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define pb push_back
#define int long long
#define ld long double
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std; 

const int N = 1e4 + 100, OO = 724249387, T = 4500 + 100, M = 1e9 + 7, P = 6151, SQ = 280, lg = 30;
typedef pair <int, int> pii;
int fac[N], inv[N], dp[T][T], is[T][T], it[T][T];
 
int pw(int x, int y) {
	if(y == 0)
		return 1;
	int cnt = pw(x, y / 2);
	cnt = (cnt * cnt) % M;
	cnt = (cnt * (y % 2 == 1 ? x : 1)) % M;
	return cnt;
}
 
void prepro() {
	fac[0] = 1;
	for(int i = 1; i <= N - lg; i++) 
		fac[i] = (fac[i - 1] * i) % M;
	inv[N - lg] = pw(fac[N - lg], M - 2);
	for(int i = N - lg - 1; i > -1; i--) 
		inv[i] = (inv[i + 1] * (i + 1)) % M;
}
 
int c(int x, int y) {
	return ((fac[x] * inv[y] % M) * inv[x - y]) % M;
}

int32_t main() {
	use_fast;
	prepro();
	int n, cnt = 0;
	cin >> n;
	for(int i =0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		cnt -= c(2 * (x + y), 2 * x);
		cnt = (cnt % M + M) % M;
		is[-x + 2500][-y + 2500]++;
		it[x + 2500][y + 2500]++;
	}
	for(int i = 1; i <= 4550; i++) {
		for(int j = 1; j <= 4550; j++) {
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + is[i][j]) % M;		
			cnt = (cnt + dp[i][j] * it[i][j]) % M;
		}
	}
	cnt = (cnt * pw(2, M - 2)) % M;
	cout << cnt << endl;
	return 0;
}
/*
be carefull :
1- if not solve after 20 min, read again twice
2- after submit read the code again
3- fun with contest
4- uploaded by ubuntu 20.04 
5- ...
*/


Measured memory_bytes: 244676
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int s, s_1, s_2, s_3;
  
  cin >> s;
  
  s_1 = s /100;
  s_2 = s / 10 % 10;
  s_3 = s % 10;
  
  cout << s_1 + s_2 + s_3 << 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; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...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 a, ans =0;
	string s;
	cin >>a >>s;
	
	if(a<3200) puts("red");
	else cout << s <<"\n";
	return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
		public static void main(String[] args) {
			Scanner sc = new Scanner(System.in);

			int[] value = new int[9];
			boolean[] flags = new boolean[9];

			for(int i = 0; i < 9; i++)
			{
				value[i] = sc.nextInt();
			}

			int N = sc.nextInt();

			for(int i = 0; i < N; i++)
			{
				int num = sc.nextInt();
				for(int j = 0; j < 9; j++)
				{
					if(num == value[j])
					{
					   flags[j] = true;
					   break;
				    }
				}
			}

			if((flags[0]== true && flags[1] == true && flags[2] == true)
				|| (flags[3] == true &&  flags[4] == true && flags[5] == true)
				|| (flags[6] == true &&  flags[7] == true && flags[8] == true)
				|| (flags[0] == true &&  flags[3] == true && flags[6] == true)
				|| (flags[1] == true &&  flags[4] == true && flags[7] == true)
				|| (flags[2] == true &&  flags[5] == true && flags[8] == true)
				|| (flags[0] == true &&  flags[4] == true && flags[8] == true)
				|| (flags[2] == true &&  flags[4] == true && flags[6] == true))
			{
				System.out.println("Yes");
			}
			else
			{
				System.out.println("No");
			}
		}
}


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

int main(){
	using ll = long long;
	ll n, a, b;
	cin >> n >> a >> b;
	if(b < a){
		cout << 0 << endl;
		return 0;
	}
	if(n == 1){
		cout << (a == b) << endl;
		return 0;
	}
	if(n == 2){
		cout << 1 << endl;
		return 0;
	}
	cout << (b - a + 1) + (b - a) * (n - 3) << endl;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	static int H;
	static int[][] f;
	static boolean[][] vanish;

	public static void main(String[] args) {
		while (true) {
			H = sc.nextInt();
			if (H == 0) break;
			f = new int[H][5];
			vanish = new boolean[H][5];
			for (int i = 0; i < H; ++i) {
				for (int j = 0; j < 5; ++j) {
					f[i][j] = sc.nextInt();
				}
			}
			int sum = 0;
			while (true) {
				int add = erase();
				if (add == 0) break;
				sum += add;
				fall();
			}
			System.out.println(sum);
		}
	}

	static int erase() {
		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < 3; ++j) {
				if (f[i][j] != 0 && f[i][j] == f[i][j + 1] && f[i][j] == f[i][j + 2]) {
					vanish[i][j] = vanish[i][j + 1] = vanish[i][j + 2] = true;
				}
			}
		}
		int ret = 0;
		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < 5; ++j) {
				if (vanish[i][j]) {
					vanish[i][j] = false;
					ret += f[i][j];
					f[i][j] = 0;
				}
			}
		}
		return ret;
	}

	static void fall() {
		for (int i = 0; i < 5; ++i) {
			int to = H - 1;
			for (int j = H - 1; j >= 0; --j) {
				if (f[j][i] == 0) continue;
				f[to][i] = f[j][i];
				--to;
			}
			while (to >= 0) {
				f[to][i] = 0;
				--to;
			}
		}
	}

}

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

#define int long long
namespace flow{
	const int _ = 1e6 + 7 , __ = 1e7 + 7;
	struct Edge{int end , upEd , f , w;}Ed[__];
	int head[_] , cur[_] , dis[_] , cntEd = 1 , S , T;

	void addEd(int a , int b , int c , int d){Ed[++cntEd] = (Edge){b , head[a] , c , d}; head[a] = cntEd;}
	void addE(int a , int b , int c , int d = 0){addEd(a , b , c , d); addEd(b , a , 0 , -d);}
	
	bool vis[_]; queue < int > q;
	bool SPFA(){
		memset(dis , -0x3f , sizeof(int) * (T + 2));
		dis[S] = 0; q.push(S);
		while(!q.empty()){
			int t = q.front(); q.pop(); vis[t] = 0;
			for(int i = head[t] ; i ; i = Ed[i].upEd)
				if(Ed[i].f && dis[Ed[i].end] < dis[t] + Ed[i].w){
					dis[Ed[i].end] = dis[t] + Ed[i].w;
					if(!vis[Ed[i].end]){q.push(Ed[i].end); vis[Ed[i].end] = 1;}
				}
		}
		return dis[T] != dis[T + 1];
	}
	
	bool ins[_];
	int dfs(int x , int mn){
		if(x == T) return mn;
		int sum = 0; ins[x] = 1;
		for(int &i = cur[x] ; i ; i = Ed[i].upEd)
			if(Ed[i].f && dis[Ed[i].end] == dis[x] + Ed[i].w && !ins[Ed[i].end]){
				int t = dfs(Ed[i].end , min(mn - sum , Ed[i].f));
				sum += t; Ed[i].f -= t; Ed[i ^ 1].f += t;
				if(sum == mn) break;
			}
		ins[x] = 0; return sum;
	}
	
	int Dinic(int s , int t){
		int sum = 0; S = s; T = t;
		while(SPFA()){
			memcpy(cur , head , sizeof(int) * (T + 1));
			sum += dis[T] * dfs(S , 1e9);
		}
		return sum;
	}
}using flow::addE;

int N , cnt;

signed main(){
	cin >> N; cnt += 4;
	for(int i = 1 ; i <= N ; ++i){
		int x , y , c; cin >> x >> y >> c;
		addE(0 , ++cnt , c);
		addE(cnt , 1 , 1e9 , x + y); addE(cnt , 2 , 1e9 , x - y);
		addE(cnt , 3 , 1e9 , -x + y); addE(cnt , 4 , 1e9 , -x - y);
	}
	for(int i = 1 ; i <= N ; ++i){
		int x , y , c; cin >> x >> y >> c;
		addE(++cnt , 2 * N + 5 , c);
		addE(4 , cnt , 1e9 , x + y); addE(3 , cnt , 1e9 , x - y);
		addE(2 , cnt , 1e9 , -x + y); addE(1 , cnt , 1e9 , -x - y);
	}
	cout << flow::Dinic(0 , 2 * N + 5); return 0;
}
	


Measured memory_bytes: 6400
n = int(input())
t = list(map(int, input().split()))
m = int(input())
p = []
x = []
for i in range(m):
    _p, _x = map(int, input().split())
    p.append(_p)
    x.append(_x)
for i in range(m):
    tmp = t[:]
    tmp[p[i]-1] = x[i]
    print(sum(tmp))
    


Measured memory_bytes: 3064
# encoding:utf-8
import copy
import numpy as np
import random

n = int(input())
h = [int(i) for i in input().split()]

count = 0

stack = []
stack.append(h)
while len(stack) != 0:
    group = stack.pop()
    # print(group)

    count += min(group)
    minus = min(group)
    for i in range(len(group)):
        group[i] -= minus

    begin = 0
    # print(group)
    for i in range(len(group)):
        if group[i] == 0:
            if len(group[begin:i])!=0:
                stack.append(group[begin:i])
            begin = i+1
        elif i == len(group)-1:
            if len(group[begin:])!=0:
                stack.append(group[begin:])
    # print(stack)
    # print(count)
print(count)


Measured memory_bytes: 13592
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ios ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
int main() {
  ll n;
  cin >> n;
  vector<ll>a(3*n);
  for(int i = 0; i < 3 * n; i++)
    cin >> a[i];
  sort(a.begin(), a.end());
  ll ans = 0;
  for(int i = 3*n-2;i>=n; i-=2)
    ans +=a[i];
  cout << ans << endl;





}


Measured memory_bytes: 2560
n, k = list(map(int, input().split()))
res = 0
if k == 1:
  print(n ** 3)
  exit()
num_baisuu = n // k
res += num_baisuu ** 3
if k % 2 == 0:
  nn = n + k / 2
  num_baisuu = nn // k
  res += num_baisuu ** 3
print(int(res))

Measured memory_bytes: 3064
// ------------------------------------
// Date:2018/ 2/25
// Problem:AOJ DPL KnapsackProblem 1_a.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl

using ll = long long;

#define MOD 1000000007

// dp[num][weight]
int dp[111][11111];

int main()
{
  int N;
  int W;
  cin >> N >> W;
  // v:value, w:weight
  int v[111];
  int w[111];
  memset(dp,0,sizeof(dp));
  memset(v,0,sizeof(v));
  memset(w,0,sizeof(w));
  REP(i,N) {
    cin >> v[i] >> w[i];
  }
  REP(num,N+1) {
    REP(weight,W+1) {
      if (weight-w[num] >= 0) {
        // max(中に入れる or 中に入れない)
        dp[num+1][weight] = max(dp[num][weight],
                                dp[num+1][weight-w[num]]+v[num]);
      } else {
        // これ以上入らないのでスルー
        dp[num+1][weight] = dp[num][weight];
      }
    }
  }
  cout << dp[N][W] << endl;
  return 0;
}



Measured memory_bytes: 7952
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000007;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N, K;
	cin >> N >> K;

	vector<Int> h(N);
	for (Int i = 0; i < N; i++) {
		cin >> h[i];
	}

	sort(h.begin(), h.end());

	Int ans = INF;
	Int i = 0;
	Int res = 0;
	while (i + K - 1 < N) {
		res = h[i + K - 1] - h[i];
		ans = min(res, ans);
		i++;
	}

	cout << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<pair<int, int>> ans;
  rep2(i, 1, n){
    int x;
    if(n % 2 == 0) x = (n+1)-i;
    else x = n - i;
    rep2(j, i+1, n+1){
      if(j == x) continue;
      ans.push_back({i, j});
    }
  }
  cout << ans.size() << endl;
  for(auto p : ans){
    cout << p.first << " " << p.second << endl;
  }
  return 0;
}

Measured memory_bytes: 3656
#include <iostream>
#include <functional>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>

#define MaxInt 2e9
#define LF '\n';
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

vector<int> xi, ci;

int main(void)
{
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	xi.resize(n);
	ci.resize(n);
	int sum = 0;
	for (int a = 0; a < n; a = a + 1) { cin >> xi[a]; }
	for (int a = 0; a < n; a = a + 1) { 
		cin >> ci[a]; 
		sum += (xi[a] > ci[a]) * (xi[a] - ci[a]);
	}

	cout << sum;
	return 0;
}

//https://codeforces.com/problemset/problem/500/B

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define VI vector<int>
#define VVI vector<vector<int>>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define MOD 1000000007
#define INF 1e9
#define All(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;

int main() {
  int S, W;
  cin >> S >> W;
  if(W>=S){
    cout << "unsafe" << endl;
  }else{
    cout << "safe" << endl;
  }

  return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using tii = tuple<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define INF 1E9
#define LINF 1E18*5
#define EPS 1E-9
#define MOD 1000000007
#define PI 3.1415926535897932384

template<class S, class T>ostream& operator<<(ostream&os, pair<S, T>p) { os << "[" << p.first << ", " << p.second << "]"; return os; };
template<class S>auto&operator<<(ostream&os, vector<S>t) { bool a = 1; for (auto s : t) { os << (a ? "" : " ") << s; a = 0; } return os; }

//int dx[]={1,1,1,0,-1,-1,-1,0},dy[8]={1,0,-1,-1,-1,0,1,1,1};
//
constexpr ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

class compare {
public:
	bool operator()(tuple<int, int> a, tuple<int, int> b) {
		return (get<1>(a) < get<1>(b));
	}
};

int main() {
	ll h, w;
	cin >> h >> w;
	ll ans = INF;
	range(i, w / 3 - 1, w) {
		if ((w-i)*h % 2==0) {
			ll lb = max((ll)i*h, (ll)(w - i) * h / 2) - min((ll)i*h, (ll)(w - i) * h / 2);
			ans = min(ans, lb);
		}
		else {
			if ((w - i) > h) {
				ll a = ((w - i) / 2 + 1)*h;
				ll b = ((w - i) / 2)*h;
				ll c = i*h;
				ll mx = max(a, max(b, c));
				ll mn = min(a, min(b, c));
				ans = min(ans, mx - mn);
			}
			else {
				ll a = (h / 2 + 1)*(w - i);
				ll b = (h / 2)*(w - i);
				ll c = i*h;
				ll mx = max(a, max(b, c));
				ll mn = min(a, min(b, c));
				ans = min(ans, mx - mn);
			}
		}
	}
	swap(h, w);
	range(i, w / 3, w) {
		if ((w - i)*h % 2==0) {
			ll lb = max((ll)i*h, (ll)(w - i) * h / 2) - min((ll)i*h, (ll)(w - i) * h / 2);
			ans = min(ans, lb);
		}
		else {
			if ((w - i) > h) {
				ll a = ((w - i) / 2 + 1)*h;
				ll b = ((w - i) / 2)*h;
				ll c = i*h;
				ll mx = max(a, max(b, c));
				ll mn = min(a, min(b, c));
				ans = min(ans, mx - mn);
			}
			else {
				ll a = (h / 2 + 1)*(w - i);
				ll b = (h / 2)*(w - i);
				ll c = i*h;
				ll mx = max(a, max(b, c));
				ll mn = min(a, min(b, c));
				ans = min(ans, mx - mn);		
			}

		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <math.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> P;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REPR(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define FOR(i, n, m) for (ll i = (n); i < (m); ++i)
#define FORR(i, n, m) for (ll i = (m) - 1; i >= (n); --i) 
#define FORE(x, xs) for (auto &x: (xs))
#define ALL(v) v.begin(), v.end()
#define ZERO(a) memset(a,0,sizeof(a))

const ll INF = 9223372036854775807;
const int MOD = 1000000007;
const double EPS = 1e-14;
const double PI = acos(-1);

const int MAX = 2e5;

int N, X;
int x[MAX];

ll calc(int c) {
  // int c = (hi+lo)/2; /// ゴミを捨てる回数
  int p = N/c + min(1, N%c); /// 一回の往復で拾う最大の量

  ll res = 1l*(c+N)*X; /// ゴミを拾って捨てるのに使うエネルギー

  REP (i, N) {
    int j = N-1-i;
    int y = i/c; /// 拾う前に持っているゴミの数
    if (y == 0) res += x[j]; /// 行き道のエネルギー
    else res += 1l*(y+1)*(y+1)*(x[j+c]-x[j]); /// 一つ前から移動するのに必要なエネルギー

    if (j < c) res += 1l*(y+2)*(y+2)*x[j]; /// そこからゴミ箱に行くのに必要なエネルギー
  }

  return res;
}

int main() {

  cin >> N >> X;
  REP (i, N) cin >> x[i];


  ll ans = INF;
  
  int lo = 0, hi = N;
  while (hi - lo > 1) {
    int mid = (hi+lo)/2;
    ll res1 = calc(mid);
    ll res2 = calc(mid+1);

    if (res1 < res2) {
      if (hi == mid+1) hi = mid;
      else hi = mid+1;
    }
    else if (lo == mid) lo = mid+1;
    else lo = mid;

    ans = min(ans, min(res1, res2));
  }
  

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

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

#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"

#define Debug(x) cout<<(#x)<<" >> "<<(x)<<endl

using namespace std;

ll fastpow(ll angka,ll pangkat,ll MOD){
	ll res=1;
	while(pangkat){
		if(pangkat&1) res=(res*angka)%MOD;
		angka=(angka*angka)%MOD;
		pangkat=pangkat>>1;
	}
	return res;
}

ll fastpow(ll angka,ll pangkat){
	ll res=1;
	while(pangkat){
		if(pangkat&1) res=(res*angka);
		angka=(angka*angka);
		pangkat=pangkat>>1;
	}
	return res;
}

ll gcd(ll angka1,ll angka2){
	while(angka2){
		swap(angka1,angka2);
		angka2=angka2%angka1;
	}
	return angka1;
}

ll lcm(ll angka1,ll angka2){
	return (angka1/gcd(angka1,angka2))*angka2;
}




void solve(){
	int n,k;
	cin>>n>>k;
	
	vector<int>v(n);
	for(int i=0;i<n;i++)cin>>v[i];
	
	for(int i=k;i<n;i++){
		if(v[i]>v[i-k]) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
		
}

int main(){
	
	fastio();

	int t=1;
//	cin>>t;
	
	for(int tt=0;tt<t;tt++){
//		cout<<"Case #"<<tt+1<<": ";solve();
		solve();
	}
	
	return 0;
}

Measured memory_bytes: 3988
#include<iostream>
#include<utility>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
int mark[100005],a[100005];
int main()
{
	int N,i,x=1,cnt=0;
	cin>>N;
	for(i=1;i<=N;i++)
	cin>>a[i];
	while(mark[2]==0&&cnt<=N)
	{
		x=a[x];
		mark[x]++;
		cnt++;
	}
	if(!mark[2])
	cout<<-1<<endl;
	else
	cout<<cnt<<endl; 
	return 0;
}


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

int main(){
  int n;
  cin >> n;
  vector<int> vec(n);
  string ans = "APPROVED";
  for(int i = 0; i < n; i++){
    cin >> vec.at(i);
  }
  
  for(int i = 0; i < n; i++){
    if(vec.at(i) % 2 != 0){
      continue;
    }
    
    if(vec.at(i) % 3 != 0 && vec.at(i) % 5 != 0) {
      ans = "DENIED";
      break;
    }
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int gcd(int a, int b)
{
	if (a > b) {
		a ^= b;
		b ^= a;
		a ^= b;
	}
	if (a == 0) return b;
	else return gcd(b % a, a);
}

long long solve(int W, int H, int K)
{
	long long i, j, k, l[2], r[2], ans = 0;
	for (k = 1; k <= (H - 1) / 2; k++) {
		l[0] = (K * 2 - k * (W + 1)) / (H - k);
		r[0] = ((K + H) * 2 - k + H - k - 1) / (H - k);
		if (l[0] < 1) l[0] = 1;
		else if (l[0] >= W) {
			ans += (long long)(W - 1) * (W - 1);
			continue;
		}
		if (r[0] <= 1) break;
		else if (r[0] > W) r[0] = W;
		ans += (long long)(l[0] - 1) * (W - 1);
		
		for (i = l[0]; i < r[0]; i++) {
			l[1] = (K * 2 - (H - k) * i + k - 1) / k;
			r[1] = ((K + H) * 2 - (H - k) * i + k - 1) / k;
			if (l[1] < 1) l[1] = 1;
			else if (l[1] >= W) {
				ans += W - 1;
				continue;
			}
			if (r[1] <= 1) break;
			else if (r[1] > W) r[1] = W;
			ans += l[1] - 1;
			for (j = l[1]; j < r[1]; j++) if (j * k + i * (H - k) - gcd(i, k) - gcd(j, H - k) - gcd(abs(i - j), H) < K * 2) ans++;
		}
	}
	for (k = 1; k <= (W - 1) / 2; k++) {
		l[0] = (K * 2 - k * (H + 1)) / (W - k);
		r[0] = ((K + W) * 2 - k + W - k - 1) / (W - k);
		if (l[0] < 1) l[0] = 1;
		else if (l[0] >= H) {
			ans += (long long)(H - 1) * (H - 1);
			continue;
		}
		if (r[0] <= 1) break;
		else if (r[0] > H) r[0] = H;
		ans += (long long)(l[0] - 1) * (H - 1);
		
		for (i = l[0]; i < r[0]; i++) {
			l[1] = (K * 2 - (W - k) * i + k - 1) / k;
			r[1] = ((K + W) * 2 - (W - k) * i + k - 1) / k;
			if (l[1] < 1) l[1] = 1;
			else if (l[1] >= H) {
				ans += H - 1;
				continue;
			}
			if (r[1] <= 1) break;
			else if (r[1] > H) r[1] = H;
			ans += l[1] - 1;
			for (j = l[1]; j < r[1]; j++) if (j * k + i * (W - k) - gcd(i, k) - gcd(j, W - k) - gcd(abs(i - j), W) < K * 2) ans++;
		}
	}
	ans *= 2;
	
	if (H % 2 == 0) {
		k = H / 2;
		for (i = 1; i < W; i++) {
			l[1] = (K * 2 - (H - k) * i + k - 1) / k;
			r[1] = ((K + H) * 2 - (H - k) * i + k - 1) / k;
			if (l[1] < 1) l[1] = 1;
			else if (l[1] >= W) {
				ans += W - 1;
				continue;
			}
			if (r[1] <= 1) break;
			else if (r[1] > W) r[1] = W;
			ans += l[1] - 1;
			for (j = l[1]; j < r[1]; j++) if (j * k + i * (H - k) - gcd(i, k) - gcd(j, H - k) - gcd(abs(i - j), H) < K * 2) ans++;
		}
	}
	if (W % 2 == 0) {
		k = W / 2;
		for (i = 1; i < H; i++) {
			l[1] = (K * 2 - (W - k) * i + k - 1) / k;
			r[1] = ((K + W) * 2 - (W - k) * i + k - 1) / k;
			if (l[1] < 1) l[1] = 1;
			else if (l[1] >= H) {
				ans += H - 1;
				continue;
			}
			if (r[1] <= 1) break;
			else if (r[1] > H) r[1] = H;
			ans += l[1] - 1;
			for (j = l[1]; j < r[1]; j++) if (j * k + i * (W - k) - gcd(i, k) - gcd(j, W - k) - gcd(abs(i - j), W) < K * 2) ans++;
		}
	}
	
	return ans * 2;
}

int main()
{
	int W, H, K;
	scanf("%d %d %d", &W, &H, &K);
	printf("%lld\n", solve(W, H, K));
	fflush(stdout);
	return 0;
}

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

int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	
	int n=0;cin>>n;
	double a=100000;
	for(int i=0;i<n;i++){
		a*=1.05;
		a/=1000;a=ceil(a);a*=1000;
	}
	
	cout<<(int)a<<endl;
	return 0;
}

Measured memory_bytes: 3140
s = list(input())
n = len(s)
ok = True
for i in range(n):
    if i % 2 == 0:
        if s[i] == 'L':
            ok = False
    else:
        if s[i] == 'R':
            ok = False

if ok:
    print('Yes')
else:
    print('No')

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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define SORTG(v) sort(v.begin(),v.end(),greater<>())
#define SORT(v) sort(v.begin(),v.end())
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/3

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<string> Vs;

template<class T> void chmax(T& a, T b) {if(a<b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a>b){a=b;}}
void YesNo(int a) {if(a){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}
void YESNO(int a) {if(a){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}
void AorB(int a,string b,string c) {if(a){cout<<b<<endl;}else{cout<<c<<endl;}}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void start(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);}

signed main(){start();
    int n,k;
    string s;
    cin>>n>>k>>s;
    if(s[k-1]=='A') s[k-1]='a';
    if(s[k-1]=='B') s[k-1]='b';
    if(s[k-1]=='C') s[k-1]='c';
    cout<<s<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N=1<<19;
int n,s,a[N];
int id[N][2];
bool cmp(int A,int B){
    return a[A]<a[B];
}
int main(){
    scanf("%d",&n);
    s=1<<n;
    for (int i=0;i<s;i++)
        scanf("%d",&a[i]);
    a[s]=-1;
    id[0][0]=0,id[0][1]=s;
    for (int i=1;i<s;i++){
        id[i][0]=i,id[i][1]=s;
        int x[4];
        for (int j=0;j<n;j++)
            if (i&(1<<j)){
                int _i=i^(1<<j);
                x[0]=id[i][0],x[1]=id[i][1];
                x[2]=id[_i][0],x[3]=id[_i][1];
                sort(x,x+4,cmp);
                id[i][0]=x[3],id[i][1]=x[2]==x[3]?x[1]:x[2];
            }
    }
    int mx=0;
    for (int i=1;i<s;i++){
        mx=max(mx,a[id[i][0]]+a[id[i][1]]);
        printf("%d\n",mx);
    }
    return 0;
}

Measured memory_bytes: 9216
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main(){
    int n,x;
    cin >> n >> x;
    int m[100];
    for (int i=0;i<n;++i) cin >> m[i];
    int sum=0;
    for (int i=0;i<n;++i) sum += m[i];
    
    bool stop = false;
    int min = m[0];
    for (int i=1;i<n;++i){
        if (m[i] < min) min = m[i];
    }
    int count = 0;
    while(!stop){
        if (sum > x) break;
        else {
            sum += min;
            ++count;
        }
    }
    cout << count+n-1 << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
 
int main(){
  char c[1101];
  int i=0,ans=0,b=1;
  do{
    for(i=0; i<1100; i++){
      scanf("%c",&c[i]);
      if(i==0&&c[0]=='0'){
        b=0;
        break;
      }
      if(c[i]=='\n')break;
      ans+=(c[i]-'0');
    }
    if(b)printf("%d\n",ans);
    ans=0;
  }while(b);
  return 0;
}


Measured memory_bytes: 2056
#include <bits/stdc++.h>
using namespace std ;
// int prime[10000005];
int p[10000005] = { 0 };
// int num=0;
void f() {
    for (int i = 2; i < 10000005; i++) {
        if (p[i] == 0) {
            // prime[num++]=i;
            for (int j = i + i; j < 10000005; j += i) {
                p[j] = 1;  //非素数赋值为1
            }
        }
    }
}
int main() {
    f();
    int n ;
    cin >> n ;
    while(1) {
    	if(!p[n]) {
    		cout << n << endl ;
    		break ;
		}
		else n++ ;
	}
    return 0;
}

Measured memory_bytes: 39424
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

const int INF = 1 << 24;
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

typedef unsigned long long ull;
typedef std::pair<int,int> P;

int main(){
    int K;
    while(std::cin >> K, K){
        int sum = 0;
        REP(i, K*(K-1)/2){
            int a;
            std::cin >> a;

            sum += a;
        }

        printf("%d\n", sum / (K-1));
    }
}

Measured memory_bytes: 1144
from itertools import *

n,m,q=map(int,input().split())

aaa=[]
for i in range(m):
    aaa.append(i+1)

l=[]
for i in range(q):
    a=list(map(int,input().split()))
    l.append(a)

a=list(combinations_with_replacement(aaa,n))
ans=0
for i in a:
    aa=0
    for j in l:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            aa+=j[3]
    if aa>ans:
        ans=aa
print(ans)

Measured memory_bytes: 21464
s=input()
ans=0
for i in range(1<<(len(s)-1)):
  st=s[0]
  for j in range(len(s)-1):
    if i & (1<<j):
      st+="+"+s[j+1]
    else:
      st+=s[j+1]
  ans+=eval(st)
print(ans)


Measured memory_bytes: 3060
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>

#define _GLIBCXX_DEBUG
#define rep(i, n) for (int64_t i = 0; i < (int64_t)(n); i++)
using namespace std;
using vi = vector<int64_t>;
using vvi = vector<vi>;

int main(int argc, const char * argv[]) {
    // fasten cin
    cin.tie(0);
    ios::sync_with_stdio(false);
    // implement
    int64_t a,b,c,k;
    cin >> a >> b >> c >> k;
    int64_t max_ = max(a,max(b,c));
    int64_t poweredMax = max_;
    for(int i=0; i<k; i++){
        poweredMax *= 2;
    }
    cout << a+b+c-max_+poweredMax << endl;
}


Measured memory_bytes: 256
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
N = int(input())
A = list(map(int,input().split()))
d = {}
for i in A:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
for i in range(1,N+1):
    if i in d.keys():
        print(d[i])
    else:
        print(0)





Measured memory_bytes: 34808
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            int w = sc.nextInt();
            int[] set = new int[w + 1];
            for (int i = 1; i <= w; i++) {
                set[i] = i;
            }
            int n = sc.nextInt();
            int[] a = new int[n];
            int[] b = new int[n];
            for (int i = 0; i < n; i++) {
                String s = sc.next();
                String[] token = s.split(",");
                a[i] = Integer.parseInt(token[0]);
                b[i] = Integer.parseInt(token[1]);
            }
            for (int i = 0; i < n; i++) {
                swap(a[i], b[i], set);
            }
            for (int i = 1; i <= w; i++) {
                System.out.println(set[i]);
            }
        }
    }

    private static void swap(int a, int b, int[] set) {
        int temp;
        temp = set[a];
        set[a] = set[b];
        set[b] = temp;
    }
}


Measured memory_bytes: 26128
#include <iostream>
#include <cmath>

using namespace std;

int main(){
 int w,h,n;
  cin >> w >> h >> n;
  
  int leftx=0;
  int lefty=0;
  int rightx=w;
  int righty=h;
  
  int x[n],y[n],a[n];
  for(int i=0;i<n;i++){
   cin >> x[i] >> y[i] >> a[i];
    
    if(a[i]==1&&leftx<x[i]) leftx=x[i]; 
    else if(a[i]==2&&rightx>x[i]) rightx=x[i]; 
    else if(a[i]==3&&lefty<y[i]) lefty=y[i];
    else if(a[i]==4&&righty>y[i]) righty=y[i];
  } 
    cout << max(0,(rightx-leftx))*max(0,(righty-lefty)) << endl;
}

Measured memory_bytes: 256
N = int(input())
X = list(input())
es = [0,N,0]

def p(X):
    print(X)

def list_change(X):
    for i in range(N):
        if X[i] == 'W':
            es[0] = i
            for j in reversed(range(es[1])):
                if X[j] == 'R':
                    es[1] = j
                    if i<j :
                        X[i] = 'R'
                        X[j] = 'W'
                        es[2] +=1
                        break
                elif j == 0:
                    es[1] = 1
                


list_change(X)
p(es[2])


Measured memory_bytes: 10776
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store")  
#pragma GCC optimize ("-fno-defer-pop")
#define all(a) a.begin(),a.end()
#define bs binary_search
#define ll long long int
ll power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m); t=(t*t)%m; if(b&1)t=(t*a)%m; return t;}
ll modInverse(ll a, ll m) { return power(a, m-2, m); }
#define ipr pair<ll,ll>
#define ps push_back
#define fs first
#define sc second
#define mkp make_pair
#define mod 1000000007
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll i,j,k,l,n;
	cin>>n;

	ll ar[n]; 
	for(i=0;i<n;i++){
		cin>>ar[i];
	}
	k=ar[0];
	for(i=1;i<n;i++){
		k=__gcd(k,ar[i]);
	}

	cout<<k;
	return 0;
}
//ctrl H replace

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <map>
#include <iomanip>

using namespace std;



int main() 
{
	string a, b;
	cin >> a >> b;
	int size = a.size();
	a += a;
	for (int i = 0; i < size; i++)
	{
		string temp = a.substr(i, size);
		if (temp == b)
		{
			cout << "Yes" <<"\n";
			return 0;
		}
	}
	cout << "No" <<"\n";
	return 0;







}

Measured memory_bytes: 256
a = input()
t = 0
cnt = 0
for i in range(len(a)-1, -1, -1):
    if a[i] == "T":
        t += 1
    elif a[i] == "S" and t != 0:
        t -= 1
        cnt += 1
print(len(a) - cnt * 2)


Measured memory_bytes: 3500
_, M = map(int, input().split())
left_rights = [list(map(int, input().split())) for _ in range(M)]

l_max = 0
r_min = 10 ** 6
for l, r in left_rights:
    l_max = max(l_max, l)
    r_min = min(r_min, r)

ans = r_min - l_max + 1
if ans > 0:
    print(ans)
else:
    print(0)


Measured memory_bytes: 27332