akhauriyash/Code-Regression huggingface dataset:
import sys
input = sys.stdin.readline

n = int(input())
s = list(str(input()))
s = [{ord(c)-ord('a')} for c in s]

def segfunc(x, y):
    return x | y

def init(init_val):
    # set_val
    for i in range(n):
        seg[i+num-1] = init_val[i]
    # built
    for i in range(num-2, -1, -1):
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

def update(k, x):
    k += num - 1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

def query(p, q):
    if q <= p:
        return ide_ele
    p += num - 1
    q += num - 2
    res = ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res, seg[p])
        if q&1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res

# identity element
ide_ele = set()

# num: n以上の最小の2のべき乗
num = 2**(n-1).bit_length()
seg = [ide_ele]*2*num

init(s)

q = int(input())
for _ in range(q):
    t, x, y = map(str, input().split())
    if t == '1':
        i = int(x)-1
        c = {ord(y)-ord('a')}
        update(i, c)
    else:
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))


Measured memory_bytes: 476372
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,k,c;cin>>n>>k>>c;
	string s;cin>>s;

	int a[k]={},b[k]={};
	for(int i=0,j=0;i<n&&j<k;i++){
		if(s[i]=='o')
			a[j++]=i+1,i+=c;
	}
	for(int i=n-1,j=k-1;i>=0&&j>=0;i--){
		if(s[i]=='o')
			b[j--]=i+1,i-=c;
	}
	for(int i=0;i<k;i++)
		if(a[i]&&b[i]&&a[i]==b[i])
			cout<<a[i]<<"\n";
	return 0;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> s(n);
    for(int i =0;i < n;i++){
        cin >> s[i];
    }
    sort(s.begin(),s.end());
    int ans = 0;
    for(int i =0;i < n;i++){
        ans += s[i];
    }
    int count =0;
    if(ans%10 == 0){
        if(s[0] % 10 == 0){
          while(s[count] % 10 == 0){
            count++;
            if(count == n){
                ans = 0;
                break;
            }
          }
        }
          
        if(count != n){
            ans -= s[count];
        }        
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
    using namespace std;
 
    int main(){
      int n;
      cin >> n;
      int p[n];
      rep(i,n)cin >> p[i];
      int ans=0;
      sort(p,p+n);
      rep(i,n){
       if(i<=n-2){
        ans+=p[i]; 
       }
        else ans+=p[i]/2;
      }
      cout << ans << endl;
      return 0;}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;


int main(void){
  int a,b,k,i,r;
  cin>>a>>b>>k;
  if(a<b){
    swap(a,b);
  }
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }

  for(i=b;;i--){
    if(b%i==0)k--;
    if(!k)break;
  }
  cout<<i<<endl;

}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
#define all(x) (x).begin(),(x).end()
#define rep(i,m,n) for(int i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(int i = m;i >= n;--i)
#define INF INT_MAX/2
using namespace std;
using ll = long long;
using R = double;
const ll MOD = 1e9 + 7;
const ll inf = 1LL << 50;
struct edge { ll from; ll to; ll cost; };


int main() {
	ll n;
	cin >> n;
	vector<ll>a(5);
	rep(i, 0, 5)cin >> a[i];
	sort(all(a));

	ll temp;
	if (n % a[0] == 0)temp = n / a[0] - 1;
	else temp = n / a[0];

	cout << 5 + temp << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

long long N, P;
const int MAX_N = 52;
int A[MAX_N];
long long dp[MAX_N + 2][MAX_N + 2];

void calc_dp() {
	for (int i = 1; i <= N + 1; ++i) {
		for (int j = 1; j <= N + 1; ++j) {
			if (j == 1) {
				dp[i][j] = 1;
			}
			else if (j == i) {
				dp[i][j] = 1;
				break;
			}
			else {
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
			}
		}
	}
}

void solve() {
	long long oans = 0, eans = 0, ans = 0;
	long long odd = 0, even = 0;
	calc_dp();
	for (long long i = 0; i < N; i++) {
		if (A[i] % 2 == 0) {
			++even;
		}
		else {
			++odd;
		}
	}
	//偶数の組み合わせ
	for (int i = 0; i <= even; ++i) {
		eans += dp[even + 1][i + 1];
	}
	//奇数の組み合わせ
	for (int i = 0; i <= odd; ++i) {
		if (P == 0) {
			if (i % 2 == 0) {
				oans += dp[odd + 1][i + 1];
			}
		}
		else {
			if (i % 2 != 0) {
				oans += dp[odd + 1][i + 1];
			}
		}
	}
	ans = eans * oans;
	cout << ans << endl;
}

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

	return 0;
}

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

int main(){
  int x,y;cin >> x >> y;
  int a[7] = {1,3,5,7,8,10,12};
  int b[4] = {4,6,9,11};
  int c = 2;
  if(x == c && y == c){
    cout << "Yes" << endl;
    return 0;
  } else {
    int flag = 0;
    for(int i=0;i<7;++i){
      if(a[i] == x||a[i] == y)flag += 1;
    }
    if(flag == 2){
      cout << "Yes" << endl;
      return 0;
    }
    flag = 0;
    for(int i=0;i<4;++i){
      if(b[i] == x||b[i] == y)flag += 1;
    }
    if(flag == 2){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}


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

using namespace std;
typedef long long ll;

#define INF (long long)(1e9+7)
#define REP(i,n) for(ll i = 0; i < n; i++)
#define REP1(i,n) for(ll i = 1; i <= n; i++)

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



int main(void)
{
  ll n;
  cin >> n;
  ll ans = 0;
  REP1(i, n) {
    if(i % 3 == 0 || i % 5 == 0) {
    } else {
      ans += i;
    }
  }
  cout << ans << endl;

}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
#define repitr(itr,a) for(auto itr=a.begin();itr!=a.end();++itr)
#define P pair<int,ll>
const ll MOD=998244353;
const int INF=1e9;
const double PI=acos(-1);

ll get_part_mas(vector<ll> c, vector<ll> s, ll k) {
    int m=s.size();
    ll right=1,sum=c[s[0]];
    ll tres=-1e9;
    rep(left,2*m) {
        while (right<2*m && right-left<k) {
            if (c[s[right%m]]<0) break;
            sum+=c[s[right%m]];
            ++right;
        }
        tres=(tres>sum)?tres:sum;
        if (left+1==right && right<2*m) {
            sum+=c[s[right%m]];
            ++right;
        }
        sum-=c[s[left%m]];
    }
    return tres;
}


ll get_maxval(vector<ll> c, vector<ll> s, ll k) {
    ll m=s.size();
    ll k1=(k<m-1)?k:m-1,k2=k%m;
    if (k2==0) k2=m;
    ll tmp=0;
    rep(i,m) tmp+=c[s[i]];
    ll res1=-1e9;
    if (k1>0) res1=get_part_mas(c,s,k1);
    ll res2=get_part_mas(c,s,k2);
    if (tmp>0) {
        ll num1=(k-k1)/m,num2=(k-k2)/m;
        res1+=tmp*num1;
        res2+=tmp*num2;
    }
    ll res=(res1>res2)?res1:res2;
    return res;
}


int main() {
    ios_base::sync_with_stdio(false);

    ll n,k;
    cin >> n >> k;
    vector<ll> p(n),c(n);
    rep(i,n) {
        cin >> p[i]; 
        --p[i];
    }
    rep(i,n) cin >> c[i];
    ll ans=-1e12;
    rep(i,n) {
        ll next=i;
        ll scnt=0;
        vector<ll> cnt;
        while (1) {
            scnt+=c[next];
            cnt.push_back(scnt);
            next=p[next];
            if (next==i) break;
        }
        ll m=cnt.size();
        rep(j,m) {
            if (j+1>k) break;
            ll tans=cnt[j];
            if (scnt>0) tans+=scnt*ll((k-j-1)/m);
            ans=(ans>tans)?ans:tans;
        }
    }
    cout << ans << endl;

    return 0; 
}


Measured memory_bytes: 3768
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <functional>
#include <climits>
#include <cstring>

using namespace std;

#define int long long
#define rep(i, n) for (int i=0;i<(int)n;++i)
#define rep1(i, n) for (int i=1;i<=(int)n;++i)
#define unless(a) if(!(a))
#define all(a) begin(a),end(a)
#define fst first
#define scd second
#define PB emplace_back
#define PPB pop_back

using vi=vector<int>;
using pii=pair<int, int>;

bool chmin(int&a,int b){return a>b?(a=b,true):false;}
bool chmax(int&a,int b){return a<b?(a=b,true):false;}
int read(){int a;scanf("%lld",&a);return a;}

int N, K;

signed main()
{
	cin >> N >> K;

	vector<int> x(N);

	rep(i, N) cin >> x[i];

	if (K == 1) {
		int mn = LLONG_MAX;
		rep(i, N) chmin(mn, abs(x[i]));
		cout << mn << endl;
		return 0;
	}

	int mn = LLONG_MAX / 3;

	rep(i, N - K + 1) {
		int cost = 0;

		if (x[i] <= 0 and 0 <= x[i + K - 1]) {
			if (0 - x[i] > x[i + K - 1] - 0) {
				cost += x[i + K - 1] * 2;
				cost -= x[i];
			} else {
				cost -= x[i] * 2;
				cost += x[i + K - 1];
			}
		} else if (x[i + K - 1] <= 0) {
			cost += -x[i];
		} else if (x[i] >= 0) {
			cost += x[i + K - 1];
		}

		chmin(mn, cost);
	}

	cout << mn << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include <ext/numeric>
using namespace std;
using namespace __gnu_cxx;
#define     __        ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define     pi        acos(-1)
#define     ll        long long int
#define     f0(n)     for(int i=0;i<n;i++)
#define     mem(a)    memset(a,0,sizeof(a))
#define     mems(a)   memset(a,-1,sizeof(a))

int a;
int main()
{
   /* #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif  */
     __

    int n,h,w,ans=0;
    cin>>n>>h>>w;
    int a[n+5],b[n+5];
    f0(n) cin>>a[i]>>b[i],ans+=min(a[i]/h,b[i]/w);
    cout<<ans;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define PI 2*acos(0)
#define INF 1e17
#define mx 2*1000000+5
using namespace std;
const ll int p=1e9+7;
int h,w,k;
vector<string>grid;
bool check(int r,int c)
{
    int cnt=0;
    for(int i=0;i<h ;i++){
        for(int j=0;j< w ; j++){
            if((r & (1<<i)) || (c & (1<<j))) continue;
            if(grid[i][j]=='#') cnt++;
        }
    }
    return (cnt==k);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>h>>w>>k;
    grid.resize(h);
    for(int i=0;i<h;i++){
        cin>>grid[i];
    }
    int ans=0;
    for(int r=0;r< (1<<h) ;r++){
        for(int c=0; c< (1<<w);c++){
            if(check(r,c)) ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3572
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <bitset>
#include <iomanip>
#include <deque>
#include <tuple>
#include <algorithm>

using namespace std;

int main()
{
    int n;

    cin >> n;

    if (n < 1200) {
        cout << "ABC" << endl;
    }
    else {
        cout << "ARC" << endl;
    }
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
const long double PI = acos(-1.0L);
const long long MOD = 1000000007LL;
// const long long MOD = 998244353LL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true;} return false; }
template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true;} return false; }
///////////////////////////////////////////////////////////////////////////////////////////////////

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N,K; cin >> N >> K;
    vector<ll> x(N);
    rep(i,N) cin >> x[i];

    ll ans = 1e18;
    for (int i = 0; i < N-K+1; i++) {
        ll L;
        if (x[i] <= 0 && x[i+K-1] <= 0) L = abs(x[i]);
        else if (x[i] >= 0 && x[i+K-1] >= 0) L = x[i+K-1];
        else {
            L = abs(x[i]) + abs(x[i+K-1]) + min(abs(x[i]),abs(x[i+K-1]));
        }
        chmin(ans,L);
    }

    cout << ans << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> t(n,0);
  for(int i=0;i<n-1;i++){
    int c,s,f;
    cin >> c >> s >> f;
    for(int j=0;j<=i;j++){
      t[j]=max(s,((t[j]+f-1)/f)*f);
      t[j]+=c;
    }
  }
  for(int i=0;i<n;i++){
    cout << t[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
    if(a>=b){
      if(b == 0) return a;
      return gcd(b, a % b);
    }
    else{
      if(a==0)return b;
      return gcd(a, b%a);
    }
}

vector<int> divisors(int n) {
    vector<int> res;
    for(int i = 1; i*i <= n; ++i) {
        if(n % i != 0) continue;
        res.push_back(i);
        if(n/i == i) continue; 
        res.push_back(n/i);
    }
    return res;
}
int main(){
  int a,b,k,g;cin>>a>>b>>k;vector<int> v;
  g=gcd(a,b);
  v=divisors(g);
  sort(v.rbegin(),v.rend());
  cout<<v[k-1]<<endl;
}

Measured memory_bytes: 256
//When I wrote this only God and I knew what it is
//Now, only The_Blitz knows...
#pragma GCC optimize ("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
#define pb push_back
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ff first
#define ss second
typedef long long ll;
typedef pair<int, int> ii;

int main(){
	fastio;
	ll n; cin >> n;
	ll even = n / 2;
	ll odd = n - even;
	cout << fixed << setprecision(8) << odd * 1.0 / (even + odd) << endl;
	return 0;
}



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

int main(){
  long long  n;
  cin >>n;
  map<string, int>dict;
  for(long long  i=0;i<n;i++){
    string x; 
    cin >> x;
    dict.emplace(x, 0);
  }
  cout << dict.size() <<endl;
  return 0;
}

Measured memory_bytes: 19228
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define endl '\n'
const int inf = 1000000007;
const ll INF = 1e18;
// int mod = 998244353;
int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
template<typename T, typename U> T pow_(T a, U b) { return b ? pow_(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { rep(i, sz(vec)) { if (i) os << " "; os << vec[i]; } return os; }
template<typename T> inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T, class T2> inline void add(T &a, T2 b) { a += b; if (a >= mod) a -= mod; }


void solve();

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(11);
  int T;
  T = 1;
  while (T--) solve();
}

void solve() {
  vector<int> a(3);
  cin >> a;
  sort(all(a));

  cout << (a[0] + a[1] != a[2] ? "No" : "Yes") << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int A, B;
  cin >> A >> B;
  int ans=-1;
  for (int i=1; i<=(25*50); i++){
    int ans1 = i*8/100;
    int ans2 = i*1/10;
    if (ans1 == A){
      if (ans2 == B){
        ans = i;
        break;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
/********************************************//**
 ****** Handle: techno_phyle    *****************
 ***********************************************/

#include<bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
typedef long long ll;
#define mod 1000000007
#define N 100010
#define M 200010
#define db(a) cout << a << endl
#define db2(a,b) cout << a << " " << b << endl
#define dbp(a) cout << a.first << " " << a.second << endl
#define adb(a) for(auto it:a) cout << it << " "; cout << endl
#define adbp(a) for(auto it:a) cout << it.first << " " << it.second << endl
#define pb push_back
#define mp make_pair
//fix the sqrt (int) (sqrt(n) + 1e-9)
#define endline "\n"
const ll INF = 1e18L + 5;
const int inf = 1e9 + 5;
typedef pair<double, long> key;
struct comp {
	bool operator()(pair<int, int> p1, pair<int, int> p2) {
		if (p1.first < p2.first) return false;
		if (p2.first < p1.first) return true;
		return p1.second < p2.second;
	};
};
//greater<pair<int,int> , greater<int>>

// vector<int> graph[N];
// vector<int> weight(N);
// void dfs(int node, int parent)
// {
// 	for (int to : graph[node]) {
// 		if (to == parent)
// 			continue;
// 		dfs(to, node);
// 		weight[node] += weight[to];
// 	}
// }
// bool prime(int n) {
// 	if (n <= 1)
// 		return false;
// 	for (int i = 2; i < n; i++)
// 		if (n % i == 0)
// 			return false;
// 	return true;
// }


int main() {
	int n , m;
		cin  >> n >> m;
		vector<int> graph[n + 1];
		for (int i = 0; i < m; i++) {
			int x , y;
			cin >> x >> y;
			graph[x].pb(y);
			graph[y].pb(x);
		}
		int ans = 0;
		bool visited[n + 1];
		for (int i = 0; i <= n; i++) visited[i] = false;
		for (int i = 1; i <= n ; i++) {
			if (visited[i] == false) {
				int count = 0;
				queue<int> q;
				q.push(i);
				count++;
				visited[i] = true;
				while (q.empty() == false) {
					int c = q.front();
					q.pop();
					for (int j = 0; j < graph[c].size(); j++) {
						if (visited[graph[c][j]] == false) {
							visited[graph[c][j]] = true;
							q.push(graph[c][j]);
							count++;
						}
					}
				}
				ans = max(ans , count);
			}
		}
		cout << ans << endl;
	return 0;
}

Measured memory_bytes: 15180
#include <stdio.h>
void call(int n);

int main(void) {
	int n;
	
	//値を入力する
	scanf("%d", &n);
	
	//関数callを呼び出す
	call(n);
	return 0;
}

void call(int n) {
	int i = 1;
	
	//iがn以下の間、繰り返す
	do {
		int x = i;
		
		//3で割り切れるとき、出力する
		if(x % 3 == 0) {
			printf(" %d", i);
		}
		else {
			
			//xが0でない間、繰り返す
			do {
				//10で割った余りが3のとき、出力する
				if(x % 10 == 3) {
					printf(" %d", i);
					break;
				}
				else {
					x /= 10;
				}
			} while(x);
		}
	} while (++i <= n);
	printf("\n");
}


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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int mod = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

string tobaseminus2(int n){
  int r = 0;
 string base_2str = "";
  while(n != 0){
   r = n % 2;
    if(r < 0)
      r += 2;
    n = (n - r) / (-2);
    base_2str += to_string(r);
  }

  reverse(base_2str.begin(), base_2str.end());
  return base_2str;
}



int main(){
  ll n;
  cin >> n;
  if(n ==0)
    cout << 0 << "\n";
  else
    cout << tobaseminus2(n) << "\n";
  }




Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<array>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<numeric>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<unordered_map>
#include<queue>
#include<vector>
using namespace std;

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

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) {cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) {cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
const int MOD = 1e9 + 7;

signed main() {
	for (int a[3]; cin >> a[0] >> a[1] >> a[2] && a[0];) {
		int n; cin >> n;
		sort(a, a + 3);
		rep(i, 0, n) {
			int r; cin >> r;
			if (r*r * 4 > a[0] * a[0] + a[1] * a[1])cout << "OK" << endl;
			else cout << "NA" << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3156
N, M=map(int, input().split())
A=[int(input()) for _ in range(M)]
mod=10**9+7
step=[1]*(N+1)
for a in A:
  step[a]=0
for i in range(2, N+1):
  step[i]=(step[i-1]+step[i-2])%mod*step[i]
print(step[-1])

Measured memory_bytes: 7824
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define int ll
using ll = long long;
using pii = pair<int,int>;
const int MOD = 1e9+7, N = 1e5 + 10; 

int32_t main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   int n;
   cin >> n;
   map<int,int> cnt;
   int val = 0;
   vector<int> a(n);
   f(i,0,n){
      cin >> a[i];
      cnt[a[i]]++;
      val = max(val,cnt[a[i]]);
   }
   if(val == 1){
      cout << "YES\n";
   }else{
      cout << "NO\n";
   }
   return 0;
}

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

#define inf (int)(1e9) 

using namespace std;

long func(long a, long b){
	if(a > b){
		return func(b, a);
	}
	if(a == b){
		return a;
	}else{
		if(b%a == 0){
			return 2*a + func(a, b-a);
		}else{
			return 2* floor(b/a) * a + func(a, b%a);
		}
	}
}

int main(){
	long n, x;
	int flag = 1;

	cin >> n >> x;

	long x1  =     x;
	long y1  = n - x;
	long ans =     n;

	while(flag){
		if(x1 > y1){
			long tp = x1;
			x1 = y1;
			y1 = tp;
		}

		if(y1 % x1 == 0){
			ans += x1 * (2* (y1/x1) - 1);
			flag = 0;
		}else{
			ans += x1 * 2 * ( y1 / x1 );
			y1 = y1 % x1;
		}

	}

	cout << ans << endl;
	


	return 0;
}

Measured memory_bytes: 256
from math import *

a, b, x = map(int, input().split())

areatotal = a*a*b

if areatotal / 2 == x: print(45.0)
elif x > areatotal/2:
    left = 0.0
    right = 90.0
    while right-left > 0.00000001:
        current = (right+left)/2
        if a**2 * tan(radians(current)) / 2 * a < (areatotal - x):
            left = current
        else:
            right = current
    print(left)
else:
    left = 0.0
    right = 90.0
    while right-left > 0.00000001:
        current = (right+left)/2
        if b**2 * tan(radians(90-current))/2*a > x:
            left = current
        else:
            right = current
    print(left)



Measured memory_bytes: 9464
# coding: utf-8
# Your code here!
moj = str(input())
kai = int(input())
han = 0
omo = ''
ura = ''
for i in range(kai):
    kyu = []
    kyu = list(input().split(" "))
    if kyu[0] == "1":
        if han == 0:
            han = 1
        elif han == 1:
            han = 0
    elif kyu[0] == "2":
        if han == 0:
            if kyu[1] == "1":
                ura += kyu[2]
            elif kyu[1] == "2":
                omo += kyu[2]
        if han == 1:
            if kyu[1] == "1":
                omo += kyu[2]
            elif kyu[1] == "2":
                ura += kyu[2]
if han == 1:
    moj = moj[::-1]
    omo = omo[::-1]
    moj = omo + moj + ura
elif han == 0:
    ura = ura[::-1]
    moj = ura + moj + omo
    
print(moj)

Measured memory_bytes: 4408
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
constexpr int MOD = 1000000007;
constexpr int INF = 2000000000;
using namespace std;

int main() {
	long long a, b, c;
	cin >> a >> b >> c;
	if (a % 2 == 0 || b % 2 == 0 || c % 2 == 0)cout << 0 << endl;
	else cout << min({ a*b,b*c,c*a }) << endl;
}

Measured memory_bytes: 380
import sys
def frog():
    for i in range(n):
        for j in range(i+1,i+k+1):
            if(j<n):
                dp[j]=min(dp[j],dp[i]+abs(l[i]-l[j]))
    return dp[n-1]
if __name__ == "__main__":
        n,k=map(int,sys.stdin.readline().split())
        dp = [sys.maxsize] * n
        dp[0] = 0
        l = list(map(int,sys.stdin.readline().split()))
        sys.stdout.write(str(frog()))

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

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

using ll = long long;
using namespace std;

template <typename T>
auto
power (
    T   base,
    ll  exponent)
{
    decltype(base) result = 1;

    for (; exponent; exponent >>= 1) {
      if ( exponent & 1 ) {
        result *= base;
      }
      base *= base;
    }
    return result;
}

template <long long N>
class Modulo {
 public:
  using Type = decltype(N);
  Modulo (Type n = 0) : number_((N + n) % N) {}
  // unary operator
  auto operator - () const {
    return Modulo(-number_);
  }
  auto operator ~ () const {
    // Only if N is prime, and number_ and N are coprime
    return power(*this, N - 2);
  }
  // compound assign operator
  auto & operator += (const Modulo & m) {
    number_ = (number_ + m.number_) % N;
    return *this;
  }
  auto & operator -= (const Modulo & m) {
    return *this += -m;
  }
  auto & operator *= (const Modulo & m) {
    number_ = (number_ * m.number_) % N;
    return *this;
  }
  auto & operator /= (const Modulo & m) {
    return *this *= ~m;
  }
  // binary operator with type conversion
  friend auto operator + (Modulo lhs, const Modulo & rhs) {
    return lhs += rhs;
  }
  friend auto operator - (Modulo lhs, const Modulo & rhs) {
    return lhs -= rhs;
  }
  friend auto operator * (Modulo lhs, const Modulo & rhs) {
    return lhs *= rhs;
  }
  friend auto operator / (Modulo lhs, const Modulo & rhs) {
    return lhs /= rhs;
  }
  // stream operator
  friend auto & operator << (std::ostream & os, const Modulo & m) {
    return os << m.number_;
  }
  friend auto & operator >> (std::istream & is, Modulo & m) {
    // Note that number_ may be negative
    return is >> m.number_;
  }
 private:
  Type number_;
};

// 2^n - c(n, 0) - c(n, a) - c(n, b)
int
main ()
{
    using Number = Modulo<1'000'000'007ll>;

    ll n, a, b;
    cin >> n >> a >> b;

    auto allsum = power(Number(2), n);

    vector<Number> perm(b+1);
    vector<Number> fact(b+1);
    perm[0] = fact[0] = 1;
    rep(b, i) {
      perm[i + 1] = perm[i] * (n - i);
      fact[i + 1] = fact[i] * (1 + i);
    }
    auto nc0 = perm[0] / fact[0];  // 1
    auto nca = perm[a] / fact[a];
    auto ncb = perm[b] / fact[b];

    auto exclude = nc0 + nca + ncb;
    cout << allsum - exclude << endl;
}


Measured memory_bytes: 3328
#include <iostream>
#include <utility>

int main(void){
 
  int x,y,z=0;
  scanf("%d %d %d\n",&x,&y,&z);
  
  using std::swap;
  swap(x, y);
  swap(x, z);
  
  printf("%d %d %d\n",x,y,z);
  
  return 0;
  
}

Measured memory_bytes: 384
N, Q = map(int, input().split())
S = input()

where_ac = [0] * N

for i in range(N-1):    
  if S[i] == 'A' and S[i+1] == 'C':
    where_ac[i+1] = where_ac[i] + 1
  else:
    where_ac[i+1] = where_ac[i]
        
for q in range(Q):
  l, r = map(int, input().split())
  print(where_ac[r-1] - where_ac[l-1])

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

using namespace std;

int main(){
  int n;

  vector<int> p;
  int temp;

  cin >> n;
  cin.ignore();
  for(int i = 0; i < n; i++){
    cin >> temp;
    p.push_back(temp);
  }
  cin.ignore();

  int cnt = 0;
  for (int i = 0; i < n - 2; i++){
    if(((p[i] < p[i + 1]) && (p[i + 1] < p[i + 2]))
       || ((p[i] > p[i + 1]) && (p[i + 1] > p[i + 2]))){
      ++cnt;
    }
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 256
let _ =
  let n = Scanf.scanf "%d\n" (fun x -> x) in
  let rec debt x n =
    if n = 0 then x
    else let nx = x * 1050 in
         if nx mod 1000 = 0 then debt (nx / 1000) (n - 1)
         else debt (nx / 1000 + 1) (n-1) in
  Printf.printf "%d\n" ((debt 100 n) * 1000)

Measured memory_bytes: 2224
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;
const int maxn=200;
const LL inf=LL(1e10);

struct LINK
{
	int id, next;
	LL flow;
};

int n;
int now;
int h[maxn], a[maxn], nx[maxn];
int level[maxn];
int q[maxn];
LL maxflow;
LL posisum, total;
LINK t[maxn*maxn*2];

void read()
{
	scanf("%d", &n);
	for (int i=1; i<=n; ++i)
		scanf("%d", &a[i]);
}
void join(int u, int v, LL fl)
{
	t[now].id=v; t[now].next=h[u]; t[now].flow=fl; h[u]=now++;
	t[now].id=u; t[now].next=h[v]; t[now].flow=0; h[v]=now++;
}
void build()
{
	for (int i=0; i<=n+1; ++i) h[i]=-1;
	for (int i=1; i<=n; ++i)
	{
		total+=a[i];
		if (a[i]<0)
		{
			posisum+=(-a[i]);
			join(0, i, -a[i]);
		}
		else join(i, n+1, a[i]);

		for (int j=i*2; j<=n; j+=i)
			join(i, j, inf);
	}
}
bool build_level()
{
	int head=1, tail=1;
	q[1]=0;
	for (int i=0; i<=n+1; ++i) level[i]=-1;
	level[0]=0;
	while (head<=tail)
	{
		int cur=q[head++];
		for (int i=h[cur]; i>-1; i=t[i].next)
			if (t[i].flow && level[t[i].id]==-1)
			{
				level[t[i].id]=level[cur]+1;
				q[++tail]=t[i].id;
				if (t[i].id==n+1) return true;
			}
	}
	return false;
}
LL dinic(int cur, LL rest)
{
	if (cur==n+1) return rest;
	LL delta=0;
	for (int i=nx[cur]; i>-1; i=nx[cur]=t[i].next)
		if (t[i].flow && level[cur]+1==level[t[i].id])
		{
			LL tmp=dinic(t[i].id, min(rest ,t[i].flow));
			rest-=tmp;
			delta+=tmp;
			t[i].flow-=tmp;
			t[i^1].flow+=tmp;
			if (rest==0) break;
		}
	return delta;
}
void solve()
{
	build();
	while (build_level())
	{
		for (int i=0; i<=n+1; ++i) nx[i]=h[i];
		maxflow+=dinic(0, inf*n);
	}
	printf("%lld\n", total+(posisum-maxflow));
}
int main()
{
	read();
	solve();
	return 0;
}

Measured memory_bytes: 128
#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <climits>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <algorithm>
#include <functional>
using namespace std;
int hi,wi;
int N,M;
int h[3000];
int w[3000];
long long int hl[1500004]={};
long long int wl[1500004]={};
int main(){
	while(1){
	cin>>N>>M;
	if(N==0 && M==0)break;
	long long int ans=0;
	cin>>hi;
	h[0]=hi;
	for(int i=1;i<N;i++){
		cin>>hi;
		h[i]=h[i-1]+hi;
	}
	cin>>wi;
	w[0]=wi;
	for(int i=1;i<M;i++){
		cin>>wi;
		w[i]=w[i-1]+wi;
	}
	for(int i=0;i<1500000;i++){
		hl[i]=0;
		wl[i]=0;
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<N-i;j++){
			hl[h[i+j]-h[j-1]]++;
		}
	}
	for(int i=0;i<M;i++){
		for(int j=0;j<M-i;j++){
			wl[w[i+j]-w[j-1]]++;
		}
	}
	for(int i=0;i<=1500000;i++){
		ans+=hl[i]*wl[i];
	}
	cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 24616
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner(System.in);
		int n = sc.nextInt(), k = sc.nextInt();
		long[] b = new long[n];
		for(int i = 0; i < n; i++) {
			b[i] = sc.nextLong();
		}
		for(int i = 0; i < n - k; i++) {
			if(b[i] < b[i+k]) {
				System.out.println("Yes");
			}else {
				System.out.println("No");
			}
		}
	}

	static class FastScanner {
		private BufferedReader reader = null;
	    private StringTokenizer tokenizer = null;
	    public FastScanner(InputStream in) {
	        reader = new BufferedReader(new InputStreamReader(in));
	        tokenizer = null;
	    }

	    public String next() {
	        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
	            try {
	                tokenizer = new StringTokenizer(reader.readLine());
	            } catch (IOException e) {
	                throw new RuntimeException(e);
	            }
	        }
	        return tokenizer.nextToken();
	    }

	    public String nextLine() {
	        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
	            try {
	                return reader.readLine();
	            } catch (IOException e) {
	                throw new RuntimeException(e);
	            }
	        }

	        return tokenizer.nextToken("\n");
	    }

	    public long nextLong() {
	        return Long.parseLong(next());
	    }

	    public int nextInt() {
	        return Integer.parseInt(next());
	    }

	    public double nextDouble() {
	         return Double.parseDouble(next());
	     }

	    public int[] nextIntArray(int n) {
	        int[] a = new int[n];
	        for (int i = 0; i < n; i++)
	            a[i] = nextInt();
	        return a;
	    }

	    public long[] nextLongArray(int n) {
	        long[] a = new long[n];
	        for (int i = 0; i < n; i++)
	            a[i] = nextLong();
	        return a;
	    }
	}
}


Measured memory_bytes: 59252
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

H, W = map(int, input().split())
cnt=0
for _ in range(H):
  l = input()
  cnt+=l.count("#")
if cnt==H+W-1:
  print("Possible")
else:
  print("Impossible")

Measured memory_bytes: 3064
#include <iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
typedef pair<int,int> pint;
typedef long long ll;
const int inf   = 1<<30;
const int mod=1000000007;    
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

int h,w,k,sx,sy,ans,dist[1000][1000];
string s[1000];

int mi(int a,int b,int c,int d,int e){
  return min(min(a,b),min(c,min(d,e)));
  }

void bfs(){
  queue<pint> q;
  q.push(pint(sx,sy));
  dist[sx][sy]=0;
  ans=mi(inf,sx,sy,h-1-sx,w-1-sy);
  while(!q.empty()){
    pint p=q.front();q.pop();
    int x=p.first,y=p.second;
    rep(i,4){
      int nx=x+dx[i],ny=y+dy[i];
      if(0<=nx&&nx<h&&0<=ny&&ny<w){
        if(s[nx][ny]=='.'&&dist[nx][ny]==inf){
          dist[nx][ny]=dist[x][y]+1;          ans=mi(ans,nx,ny,h-nx-1,w-ny-1);
          if(dist[nx][ny]<k)q.push(pint(nx,ny));
          }
        }
      }
    }
  }

          

int main(){
  cin>>h>>w>>k;
  rep(i,h){
    cin>>s[i];
    rep(j,w)if(s[i][j]=='S'){sx=i;sy=j;}
    }
  rep(i,h)rep(j,w)dist[i][j]=inf;
  bfs();
  if(ans)cout<<2+(ans-1)/k<<endl;
  else cout<<1<<endl;
  return 0;  
  }


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

char F[102][102];

void DFS(int y, int x, char a){
  if(F[y][x]!=a){
    return;
  }
  F[y][x]='.';

  DFS(y-1,x,a);
  DFS(y,x+1,a);
  DFS(y+1,x,a);
  DFS(y,x-1,a);
}

int main(){
  int n,m;
  int cnt=0;
  while(1){
    cin >> n >> m;
    if(n==0&&m==0){
      return 0;
    }
    for(int y=1; y<=n; y++){
      for(int x=1; x<=m; x++){
        cin >> F[y][x];
      }
    }
    cnt=0;
    for(int y=1; y<=n; y++){
      for(int x=1; x<=m; x++){
        if(F[y][x]=='#'){
          cnt++;
          DFS(y,x,'#');
        }
        if(F[y][x]=='*'){
          cnt++;
          DFS(y,x,'*');
        }
        if(F[y][x]=='@'){
          cnt++;
          DFS(y,x,'@');
        }
      }
    }
    cout << cnt << endl;
  }
}


Measured memory_bytes: 3384
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<climits>
#define ll long long
using namespace std;
int main() {
	string s;
	ll count = 0;
	cin >> s;
	for (ll i = 0; i < s.size(); i++) {
		if (s[i] == '+') {
			count++;
		}
		else {
			count--;
		}
	}
	cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//型に気を付けよう
//a=0x61=97
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long  ll;
typedef long double  ld;
typedef vector<int> veci;
typedef pair<int,int> pairii;
const double pi=3.1415926535;
const ll  mod=1000000007;
//桁数指定　cout << fixed << setprecision(10)
int main() {
  int n,k,temp=0,l=0;
  int mi=INT_MAX;
  cin>>n>>k;
  veci v(n);
  rep(i,n)cin>>v[i];
  rep(j,k){
    rep(h,n){
      l+=min(abs(k-v[h]),v[h]);
    }
    mi=min(l,mi);
  }
  mi*=2;
  cout<<mi;
}

Measured memory_bytes: 256
n,y=list(map(int,input().split()))

for i_1000 in range(n+1):
    for i_5000 in range(n-i_1000+1):
        if (i_1000*1000 + i_5000*5000 + (n-i_1000-i_5000)*10000) == y:
            print(n-i_1000-i_5000,i_5000,i_1000)
            exit()
print(-1,-1,-1)

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;
    if (n < 10)
        cout << n << '\n';
    else if (n < 100)
        cout << 9 << '\n';
    else if (n < 1000)
        cout << 9 + n - 99 << '\n';
    else if (n < 10000)
        cout << 909 << '\n';
    else if (n < 100000) 
        cout << 909 + n - 9999 << '\n';
    else 
        cout << 90909 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

vector<P> ans;
int n;
int main(){
  cin >> n;
  int m = n / 2 * 2 + 1;
  for(int i = 1;i <= n;i++){
    for(int j = i+1;j <= n;j++){
      if((i + j) == m)continue;
      ans.push_back(P(i,j));
    }
  }

  cout << ans.size() << endl;
  for(int i = 0;i < ans.size();i++){
    cout << ans[i].first << " " << ans[i].second << endl;
  }
  return 0;
}

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

int main(){
	ll l, r, ans = 2019;
	cin >> l >> r;
	for(ll i = l; i < r; i++){
		if(i == l + 2019) break;
		for(ll j = i + 1; j <= r; j++){
			if(j == i + 2020) break;
			ans = min(ans, (i * j) % 2019);
		}
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
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 const MOD = 1e9+7;

int main() {
    ll h,w,k;
    ll dp[101][10];
    std::cin >> h>>w>>k;
    Fill(dp,0);
    dp[0][0] = 1;
    ll x[10],y[10],z[10];
    Fill(x,0);
    Fill(y,0);
    Fill(z,0);
    
    for (int i = 0; i < w; i++) {
        for (int j = 0; j < (1<<(w-1)); j++) {
            bool ok = true;
            for (int k = 0; k < w-2; k++) {
                if( j & (1<<k) && j & (1<<(k+1)) ){
                    ok = false;
                    break;
                }
            }
            if(!ok)continue;
            
            if( j & (1<<(i-1)) ){
                x[i]++;
            }else if( j & (1<<i) ){
                z[i]++;
            }else{
                y[i]++;
            }
        }
    }

    for (int i = 1; i <= h; i++) {
        for (int j = 0; j < w; j++) {
            dp[i][j] += y[j]*dp[i-1][j];
            dp[i][j] %= MOD;
            if(j>0){
                dp[i][j-1] += x[j]*dp[i-1][j];
                dp[i][j-1] %= MOD;
            }
            if(j<w-1){
                dp[i][j+1] += z[j]*dp[i-1][j];
                dp[i][j+1] %= MOD;
            }
        }
    }
    // for (int i = 0; i <= h; i++) {
    //     for (int j = 0; j < w; j++) {
    //         std::cout <<  dp[i][j];
    //     }
    //     std::cout << std::endl;
    // }
    std::cout << dp[h][k-1] << std::endl;
    
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  sort(a.rbegin(), a.rend());
  vector<ll> v;
  v.push_back(a[0]);
  for (int i = 1; i < n; ++i) {
    v.push_back(a[i]);
    v.push_back(a[i]);
  }
  ll ans = 0;
  for (int i = 0; i < n - 1; ++i) {
    ans += v[i];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 8212
S=input()

if len(S)%2:
  S=S[:-1]
S=S[:-2]

n=len(S)
for i in range(n//2):
    #print(S[:len(S)//2])
    #print(S[len(S)//2:])
    if S[:len(S)//2]==S[len(S)//2:]:
      break
    S=S[:-2]
    
print(len(S))  

Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int i = 0;i < (n);i++)cerr << v[i] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

ll ma[100100];
ll mc[100100];

int main()
{
	int n;
	cin >> n;
	
	vector<ll> va(n);
	vector<ll> vb(n);
	vector<ll> vc(n);
	
	REP(i,n)cin >> va[i];
	REP(i,n)cin >> vb[i];
	REP(i,n)cin >> vc[i];
	
	sort(ALL(va));
	sort(ALL(vb));
	sort(ALL(vc));
	
//	SHOW1d(va,n);
//	SHOW1d(vb,n);
//	SHOW1d(vc,n);
	
	ll cou = 0;
	REP(i,n)
	{
		if(va[i] <  vb[cou])
		{
			ma[cou]++;
		}
		else
		{
			while(va[i] >= vb[cou] && cou != n)
			{
				cou++;
				ma[cou] = ma[cou-1];
				if(cou == n-1)break;
			}
			if(va[i] < vb[cou])ma[cou]++;
		}
		if(cou >= n)break;
	}
	
	for(int i = cou+1;i < n;i++)
	{
			ma[i] = ma[i-1];
	}
	
	cou = n-1;
	REP(i,n)
	{
		if(vc[n-i-1] > vb[cou])
		{
			mc[cou]++;
		}
		else
		{
			while(vc[n-i-1] <= vb[cou] && cou >= 0)
			{
				mc[cou-1] = mc[cou];
				cou--;
				if(cou == 0)break;
			}
			if(cou!=-1 && vc[n-i-1] > vb[cou])mc[cou]++;
		}
		if(cou < 0)break;
		
	}
	for(int i = cou-1;i >= 0;i--)
	{
		mc[i] = mc[i+1];
	}
	
//	SHOW1d(ma,n);
//	SHOW1d(mc,n);
	
	ll ans = 0;
	
	REP(i,n)ans += ma[i] * mc[i];
	
	cout << ans << endl;
	
	
	
	return 0;
}

Measured memory_bytes: 4224
use std::collections::BTreeMap;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let n: usize = sc.read();
    let a: Vec<String> = sc.vec(n);
    let mut map = BTreeMap::new();
    for a in a.iter() {
        *map.entry(a.as_str()).or_insert(0) += 1;
    }

    println!("AC x {}", *map.get("AC").unwrap_or(&0));
    println!("WA x {}", *map.get("WA").unwrap_or(&0));
    println!("TLE x {}", *map.get("TLE").unwrap_or(&0));
    println!("RE x {}", *map.get("RE").unwrap_or(&0));
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 7572
import sys
input=sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
def cmb(n):
    if n == 1:
        return 0
    else:
        return n * (n-1) /2
mydict = {}
for i in range(N):
    a = A[i]
    if a in mydict.keys():
        mydict[a] += 1
    else:
        mydict[a] = 1
s = 0
for i in mydict.values():
	s += cmb(i)
for i in range(N):
    a = A[i]
    x = mydict[a] - 1
    print(int(s-x))

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

namespace AtCoder_081
{
    class Program
    {
        static void Main(string[] args)
        {
			string s = Console.ReadLine();
			int count = 0;
			for (int i = 0; i < 3; i++)
			{
				if (s[i] == '1') count++;
			}
			Console.WriteLine(count);
		}
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include<math.h>
#define rep(i,a) for(int i=0;i<a;i++)
#define nrep(i,a,b) for(int i=a;i<b;i++)
#define mrep(i,a) for(int i=a;i>=0;i--)
#define ll long long
#define vl vector<ll>
#define INF 1123456789012
using namespace std;



int main(){
	ll n, m; cin >> n >> m;
	vl root(n);
	rep(i, m){
		ll a, b; cin >> a >> b;
		root[a - 1]++;
		root[b - 1]++;
	}rep(i, n) cout << root[i] << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n,x;cin>>n>>x;
    ll a[n];for(ll i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    ll ans = 0;
    for(ll i=0;i<n-1;i++)if(a[i]<=x)x-=a[i],ans++;
    if(a[n-1]==x)ans++;
    cout<<ans;
}




Measured memory_bytes: 256