akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define fi first
#define se second

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;
}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i];if(i<len-1) s<<" ";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i]<<endl;
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){
	s<<"{ ";
	for(auto itr=v.begin();itr!=v.end();++itr) {
		if (itr!=v.begin()) {s<< ", ";}
		s<<(*itr);
	}
	s<<" }";
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){
	s<<"{"<<endl;
	for(auto itr=m.begin();itr!=m.end();++itr){
		s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;
	}
	s<<"}"<<endl;
	return s;
}

const ll mod=1e9+7;
const ll inf=1e15;
const int INF=1e9;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	vector<bool> cnt(n,false);
	vector<int> wa(n,0);
	int ans1=0,ans2=0;
	rep(i,m){
		int p;
		string s;
		cin>>p>>s;
		p--;
		if(!cnt[p]){//まだACしてない
			if(s=="AC"){
				ans1++;
				cnt[p]=true;
			}else{
				wa[p]++;
			}
		}
	}
	rep(i,n){
		if(cnt[i]) ans2+=wa[i];
	}
	cout<<ans1<<' '<<ans2<<endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define int long long
#define pii pair<int,int>
#define pqi priority_queue<int>
#define pb push_back()
#define INF 1000000000000000000
#define pi acos(-1)
#define deb(x) cout<<#x" = "<<x<<" "
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
const int modu=998244353;//1e9+7;
 
int bigmod(int n,int p){
    if(p==0) return 1;
    int x=bigmod(n,p/2)%modu;
    x=(x*x)%modu;
    if(p%2) return (x*n)%modu;
    return x;
}
 
int modInverse(int a){
    return bigmod(a,modu-2)%modu;
}
 
void defInit(){
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    #ifdef OFFLINE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
}

void endscreen(){
    #ifdef OFFLINE
        cerr<<endl<<1.0*clock()/CLOCKS_PER_SEC<<endl;
    #endif
}


int add(int x,int y){
    int z =(x%modu + y%modu)%modu;
    while(z<0) z=(z+modu)%modu;
    return z;
}
 
int mul(int x,int y){
    int z = (x%modu * y%modu)%modu;
    while(z<0) z=(z+modu)%modu;
    return z;
}

// starts here

const int MAXV = 1e5; 

void min_self(int &a,int b){
    a=min(a,b);
}

int32_t main(){
    defInit();
    //If you hack my code , You are gay;
    string s,t;
    cin>>s>>t;
    s='#'+s;
    t='@'+t;
    int dp[s.size()][t.size()];
    dp[0][0]=0;
    for(int i=0;i<s.size();i++){
        for(int j=0;j<t.size();j++){
            int &now = dp[i][j];
            if(i==0 || j==0){ now = 0;continue; }
            if(s[i]==t[j]) now = dp[i-1][j-1] + 1;
            else now = max( dp[i-1][j] , dp[i][j-1] );
        }
    }
    string ans;
    int i=s.size()-1,j=t.size()-1;
    while(ans.size()<dp[s.size()-1][t.size()-1]){
        if(s[i]==t[j]){
            ans.push_back(s[i]);
            i--;
            j--;
        }else{
            if(dp[i-1][j] == dp[i][j]){
                i--;
            }else{
                j--;
            }
        }
    }
    reverse(ans.begin(), ans.end());
    cout<<ans;
    endscreen();
    return 0;

}

Measured memory_bytes: 70656
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <limits>
using namespace std;

int main(){
    string S;
    cin >> S;
    int n = stoi(S);
    for(int i = n; i < 1000; i++) {
        if(i % 111 == 0) {
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

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

void solve() {
	long long n, k;
	cin >> n >> k;
	long long res = 0;
	res += (n / k) * (n / k) * (n / k);
	if (k % 2 == 0) {
		n += k / 2;
		res += (n / k) * (n / k) * (n / k);
	}
	cout << res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	solve();
}


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

int main() {
  int N, A;
  cin >> N >> A;
  
  if (N % 500 <= A) {
    cout << "Yes" << endl;
  }
  else if (A < N % 500) {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
  int n;
  scanf("%d", &n);
  int a[n]; long int ans[n];
  ans[0] = 0;
  for (size_t i = 0; i < n; i++) {
    scanf("%d", a+i);
    ans[0] = (i%2 == 0) ? ans[0]+a[i] : ans[0]-a[i];
  }
  printf("%ld", ans[0]);
  for (size_t i = 1; i < n; i++) {
    ans[i] = a[i-1]*2-ans[i-1];
    printf(" %ld", ans[i]);
  }
  return 0;
}


Measured memory_bytes: 2432
#include <iostream>
using namespace std;
int t[110],tans[110];

int main() {
	int defans = 0;
	int n;cin >> n;
	for (int i = 0;i < n;i++) {
		cin >> t[i];
		defans += t[i];
	}
	int m;cin >> m;
	int p, x;
	for (int k = 0;k < m;k++) {
		cin >> p >> x;
		tans[k] = defans - t[p-1] + x;
	}
	for (int j = 0;j < m;j++) {
		cout << tans[j] << endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL n,d,x,y,cnt;
int main()
{
	cin>>n>>d;
	for(LL i=1;i<=n;i++)
	  {
	  cin>>x>>y;
	  if(x*x+y*y<=d*d)cnt++;
	  }
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 3592
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <stack> // s.top()
#include <bitset>
#include <queue> // s.front()
using namespace std;

typedef long long Int;
typedef pair<Int,Int> P;
#define print(x) cout<<(x)<<endl

#define INF10 10000000000
#define INF5 100000
#define EPS 1e-10
#define MOD 1000000007


int main() {
	string A, B;
	cin >> A >> B;
	int len = max(A.size(), B.size());
	while (A.size() < len) {
		A = "0" + A;
	}
	while (B.size() < len) {
		B = "0" + B;
	}
	if (A > B)print("GREATER");
	else if (A == B)print("EQUAL");
	else print("LESS");





	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<stdio.h>
using namespace std;

struct point {
	double x;
	double y;
};

void koch(int n, point a, point b) {
	if (n == 0) return;

	point s, t, u;
	double th = 3.1415926 * 60.0 / 180.0;

	s.x = (2.0 * a.x + 1.0 * b.x) / 3.0;
	s.y = (2.0 * a.y + 1.0 * b.y) / 3.0;
	t.x = (1.0 * a.x + 2.0 * b.x) / 3.0;
	t.y = (1.0 * a.y + 2.0 * b.y) / 3.0;
	u.x = (t.x - s.x) * cos(th) - (t.y - s.y) * sin(th) + s.x;
	u.y = (t.x - s.x) * sin(th) + (t.y - s.y) * cos(th) + s.y;

	koch(n - 1, a, s);
	cout<<s.x<<" "<<s.y<<endl;
	koch(n - 1, s, u);
	cout<<u.x<<" "<<u.y<<endl;
	koch(n - 1, u, t);
	cout<<t.x<<" "<<t.y<<endl;
	koch(n - 1, t, b);
}

int main()
{
	point a, b;
	int n;

	cin >> n;

	a.x = 0;
	a.y = 0;
	b.x = 100;
	b.y = 0;

	printf("%.8f %.8f\n", a.x, a.y);
	koch(n, a, b);
	printf("%.8f %.8f\n", b.x, b.y);

	return 0;
}


Measured memory_bytes: 3292
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
typedef long long ll;
int n;
ll ans;
ll presum[maxn], prexor[maxn];
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
	{
		int val;
		scanf("%d", &val);
		presum[i] = presum[i - 1] + val;
		prexor[i] = prexor[i - 1] ^ val;
		int l = 0, r = i - 1;
		while(l <= r)
		{
			int mid = l + r >> 1;
			if(presum[i] - presum[mid] == (prexor[i] ^ prexor[mid]))
				r = mid - 1;
			else
				l = mid + 1;
		}
		ans += i - l; 
	}
	printf("%lld\n", ans);
	return 0;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    rep(i,n) cin >> h[i];

    bool ok = true;
    for (int i = n-1; i >= 0; i--) {
        if (h[i-1] > (h[i]+1)) {
            ok = false;
            break;
        }
        else if (h[i-1] > (h[i])) {
            h[i-1]--;
            continue;
        }
        
    }
    puts(ok?"Yes":"No");
    return 0;
}

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

using namespace std;

using ll = long long;

const int MX = 100 * 1000 + 7;

int a[MX];
ll st[MX];
ll b[MX];

int main() {
#ifdef BZ
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;

    ll sm = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sm += a[i];
    }
    ll bl = 1ll * n * (n + 1) / 2;
    if (sm % bl) {
        cout << "NO\n";
        return 0;
    }
    ll tot = sm / bl;
    ll take = 0;
    for (int i = 0; i < n; i++) {
        int x = a[i], y = a[(i + 1) % n];
        if ((x - y + tot) % n) {
            cout << "NO\n";
            return 0;
        }
        st[(i + 1) % n] = (x - y + tot) / n;
        if (st[(i + 1) % n] < 0) {
            cout << "NO\n";
            return 0;
        }
        take += st[(i + 1) % n];
    }
    ll csm = 0;
    for (int i = 0; i < n; i++) {
        csm += (n - i) * st[i];
    }
    for (int i = 0; i < n; i++) {
        csm += take;
        csm -= n * st[i];
        if (csm != a[i]) {
            cout << "NO\n";
            return 0;
        }
    }
    if (take == tot) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

}


Measured memory_bytes: 1408
import collections
n,k=map(int,input().split())
a=list(map(int,input().split()))
a_counter=collections.Counter(a)
a_count=a_counter.most_common()
answer = 0
# print(a_counter)
for i in range(k, len(a_count)):
    # print(a_count[i])
    answer += a_count[i][1]

print(answer)

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

#define ll long long int
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(A) A.begin(), A.end()
#define SZ(A) (ll)A.size()
typedef vector <int> vi;
typedef vector <ll> vl;
typedef pair <int, int> pii;
const ll mod = 1e9 + 7;
//const ll mod = 998244353;
const int inf = 1e9;
//const ll inf = 1e18;
const int N = 1e6;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string s;
    cin >> s;
    int x = s.length();
    string res;
    while (x--) {
        res += 'x';
    }
    cout << res << "\n";
 	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fab(i,a,b) for(long int i = a ; i < b; i++)
#define testcase ll tt; cin >> tt; while(tt--)
#define vll vector<ll>
#define ll long long int
#define pb push_back
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F first
#define S second
using namespace std;


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

ll helper(string s, int i){
    if(i>=s.size()) return 0;
    if(dp[i] != -1) return dp[i];
    ll ans = 0;
    for(int k = i+1 ; k <= s.size() ; k++){
        ans += stol(s.substr(i,k-i))*(pow(2,max(0,(int)s.size()-k-1))) + helper(s,k);
    }
    return ans;
} 
 
int main(){
    string s;
    cin>>s;
    dp.resize(s.size(),-1);
    cout<<helper(s,0);
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#define MAX_N 100
#define MAX_T 40000

int t[MAX_N];
double v[MAX_N], f[MAX_T];

double min(double a, double b)
{
    return a < b? a: b;
}

int main(void)
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &t[i]);
    for (int i = 0; i < n; i++)
        scanf("%lf", &v[i]);
    for (int i = 0; i < MAX_T; i++)
        f[i] = 1.E8;
    int tot = 0;
    for (int i = 0; i < n; i++) {
        t[i] *= 2;
        for (int j = tot; j <= tot + t[i]; j++)
            f[j] = min(f[j], v[i]);
        tot += t[i];
    }
    f[0] = f[tot] = 0.;
    for (int i = 1; i <= tot; i++)
        f[i] = min(f[i], f[i - 1] + .5);
    for (int i = tot - 1; i >= 0; i--)
        f[i] = min(f[i], f[i + 1] + .5);
    double ans = 0.;
    for (int i = 0; i < tot; i++)
        ans += .25 * (f[i] + f[i + 1]);
    printf("%f\n", ans);
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define FOR(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

int H, W;
string S[3010];
int cntO[3010][3010];
int cntI[3010][3010];

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

    cin >> H >> W;
    REP(i, H) {
        cin >> S[i];
        REP(j, W) {
            if (S[i][j] == 'O') cntO[i][j]++;
            if (S[i][j] == 'I') cntI[i][j]++;
        }
    }
    REP(i, H) for (int j = W - 1; j >= 0; --j) cntO[i][j] += cntO[i][j + 1];
    REP(j, W) for (int i = H - 1; i >= 0; --i) cntI[i][j] += cntI[i + 1][j];
    int ans = 0;
    REP(i, H) REP(j, W) if (S[i][j] == 'J') ans += cntO[i][j] * cntI[i][j];
    cout << ans << endl;

}


Measured memory_bytes: 154616
#include <stdio.h>
#include <cmath>
#include <bits/stdc++.h>



using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;


//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)



int main(void){

	int A,B; scanf("%d %d", &A, &B);
	
	if(B%A == 0) printf("%d\n",A+B);
	else printf("%d\n",B-A);


	return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>

#define MAX 500000
#define SENTI 2000000000

using namespace std;

int L[MAX/2+2], R[MAX/2+2];
int cnt;

void merge(int A[], int n, int left, int mid, int right){
  int n1 = mid - left;
  int n2 = right - mid;
  for(int i=0; i < n1; i++) L[i] = A[left+i];
  for(int i=0; i < n2; i++) R[i] = A[mid+i];
  L[n1] = R[n2] = SENTI;
  int i = 0, j = 0;
  for(int k=left; k<right; k++){
    cnt++;
    if(L[i]<=R[j]){
      A[k] = L[i++];
    }else{
      A[k] = R[j++];
    }
  }
}

void mergeSort(int A[], int n, int left, int right){
  if(left+1 < right){
    int mid = (left+right)/2;
    mergeSort(A, n, left, mid);
    mergeSort(A, n, mid, right);
    merge(A, n, left, mid, right);
  }
}

int main(int argc, const char * argv[]) {
  int A[MAX], n, i;
  cnt = 0;
  
  cin >> n;
  for(i=0; i<n; i++) cin >> A[i];
  mergeSort(A, n, 0, n);
  
  for(i=0; i<n; i++){
    if(i) cout << " ";
    cout << A[i];
  }
  cout << endl;
  
  cout << cnt << endl;
  
  return 0;
}



Measured memory_bytes: 7008
h, w = map(int, input().split())
a = [''] * h
for i in range(h):
	a[i] = input()

row = [False] * h
col = [False] * w
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			row[i] = True
			col[j] = True
for i in range(h):
	if row[i]:
		for j in range(w):
			if col[j]:
				print(a[i][j], end = '')
		print()

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

#define ll long long
using namespace std;

double a,b,x;
void solve() {
	cin>>a>>b;
	x=(a+b)/2+0.99;
	cout<<int(x)<<endl;
}
int main() {
	solve();
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#include <string>
#include <set>
#include <vector>

#define FOR(i, l, r) for (i = (l); i < r; i++ )

using namespace std;
typedef long long ll;

#define MAX_N (2000010)
#define MAX_K (10010)
int A[MAX_N];
int C[MAX_K];			// temporal array
int B[MAX_N];

int counting_sort(int A[], int B[], int k, int n) {
    int i;

    memset(C, 0, k * sizeof(int));
    
    // counts the number.
    FOR(i, 0, n) C[A[i]]++;

    FOR(i, 1, k+1) C[i] += C[i-1];

    for ( i = n-1; i >= 0; i-- ) {
	B[C[A[i]]-1] = A[i];
	C[A[i]]--;
    }
}

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

    counting_sort(A, B, MAX_K-1, n);

    FOR( i, 0, n ) {
	printf("%d%c", B[i], (i==n-1) ? '\n' : ' ');
    }

    return 0;
}

Measured memory_bytes: 18844
def f(a, b):
    if a < b:
        d = a
        a = b
        b = d
    if a % b == 0:
        return b
    else:
        return f(b, a % b)

def main():
    n = int(input())
    A = list(map(int, input().split()))
    ans = int(1e9)
    for i in range(1, n):
        ans = min(ans, f(A[i], A[i - 1]))
    print(ans)

main()

Measured memory_bytes: 14252
import sys
import socket

hostname = socket.gethostname()

if hostname == 'F451C':
    sys.stdin = open('a1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def main():
    N = read_int()
    d = N % 10
    if d == 2 or d == 4 or d == 5 or d == 7 or d == 9:
      res = 'hon'
    elif d == 0 or d == 1 or d == 6 or d == 8:
      res = 'pon'
    else:
      res = 'bon'
    print(res)


main()


Measured memory_bytes: 9804
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dis[200005],ans[200005];
vector <int> e[200005];
queue <int> q;
int main(int argc, char** argv) {
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	q.push(1);
	for(int i=2;i<=n;i++)
		dis[i]=1e9;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(auto v:e[x])
		{
			if(dis[v]>dis[x]+1)
			{
				dis[v]=dis[x]+1;
				q.push(v);
				ans[v]=x; 
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(dis[i]>5e8)
		{
			puts("No");
			return 0;
		}
	}
	puts("Yes");
	for(int i=2;i<=n;i++)
		cout << ans[i] << "\n"; 
	return 0;
}

Measured memory_bytes: 12844
N,A,B = [int(i) for i in input().split()]
v = [int(i) for i in input().split()]
v.sort()
v.reverse()
cum = [v[0]]

def comb(n, k):
    if k>n:
        return 0
    ans = 1
    for i in range(k):
        ans *= n-i
    for j in range(k):
        ans = ans//(j+1)
    return ans

for i in range(1,N):
    cum += [cum[i-1] + v[i]]
print('{:.10f}'.format(cum[A-1]/A))
target = v[A-1]
n = v.count(target)
fromk = (A-1) - v.index(target) + 1
if v[0] == target:
    ans = 0
    for i in range(A, min(B,n)+1):
        ans += comb(n, i)
    print(ans)
else:
    #print((n, fromk))
    ans = comb(n, fromk)
    print(ans)


Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  int N;
  cin >> N;
  int dp[100001];
  REP(i, 100001) dp[i] = 1e9;
  dp[0] = 0;
  REP(i, 100001) {
    for (int j = 1; i + j <= 100000; j *= 6) {
      dp[i + j] = min(dp[i + j], dp[i] + 1);
    }
    for (int j = 1; i + j <= 100000; j *= 9) {
      dp[i + j] = min(dp[i + j], dp[i] + 1);
    }
  }
  cout << dp[N] << endl;
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define br cout << "\n";
using namespace std;
const int INF = 1e9;
const int MOD = 1e9+7;
using Graph = vector<vector<ll>>;
template<class T> inline bool chmin(T &a, T b) { if(a > b){ a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b) { if(a < b){ a = b; return true;} return false;}

// 0 false, 1 true 
// string to int : -48
// a to A : -32
// ceil(a)  1.2->2.0
// c++17	g++ -std=c++17 a.cpp
typedef pair<int,int> pint;
bool cmp(pint a, pint b) { return a.second < b.second; }

int main() {
    std::cout << std::fixed << std::setprecision(15);
    ll n; cin >> n;
    vector<ll> A(n);
    vector<ll> B(n);

    ll med_min = 0;
    ll med_max = 0;
    rep(i, n){
        cin >> A[i] >> B[i];
    }

    sort(all(A));
    sort(all(B));

    if(n % 2 == 0){
        cout << ((B[n/2] + B[n/2 - 1])) - ((A[n/2] + A[n/2 - 1])) + 1 << endl;
    }

    if(n % 2 == 1){
        cout << B[n/2] - A[n/2] + 1 << endl;
    }

    

}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    while (cin>>n, n) {
        map<int, int> m;
        int c=0, res=0, a;
        for (int i=0; i<n; ++i) {
            cin >> a;
            int &ma = m[a];
            ++ma;
            if (c < ma) {
                c = ma; res = a;
            }
        }
        if (n < c*2) {
            cout << res << endl;
        } else {
            cout << "NO COLOR" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 2736
#include<stdio.h>

int main(void){
  char s[4];
  scanf("%s",s);
  if(s[0]=='A'&&s[1]=='A'&&s[2]=='A'){
    printf("No");
  }else if(s[0]=='B'&&s[1]=='B'&&s[2]=='B'){
    printf("No");
  }else{
    printf("Yes");
  }
  return 0;
}

Measured memory_bytes: 128
import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 32768);
    static PrintWriter out = new PrintWriter(System.out);
    static StringTokenizer t;

    static String sn() {
        while (t == null || !t.hasMoreTokens()) {
            try {
                t = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                throw new RuntimeException();
            }
        }
        return t.nextToken();
    }

    static int ni() {
        return Integer.parseInt(sn());
    }

    static long nlo() {
        return Long.parseLong(sn());
    }

    public static void main(String args[]) {
        int t = 1;//ni();
        while (t-- > 0) {
            solve();
        }
        out.close();
    }

    static long mod = (long) 1e9 + 7;

    static long pro(long a, long b) {
        return (a % mod * b % mod) % mod;
    }

    static int maxn = 200005;

    static void solve() {
        int n = ni();
        out.println(n * (n + 1) / 2);
    }
}

Measured memory_bytes: 20564
#include<iostream>
#include<cctype>
#include<cstdio>
#include<string>
using namespace std;

void BubbleSort(char C[1000][2], int N){
    int i,j,v1,v2;
    for (i = 0 ;i < N; i++){
       for(j=N-1;j>i;j--){
           if ((C[j][1]-'0') < (C[j-1][1]-'0')){
               v1=C[j][0];
               v2=C[j][1];
               C[j][0]=C[j-1][0];
               C[j][1]=C[j-1][1];
               C[j-1][0]=v1;
               C[j-1][1]=v2;
           }
       }
    }
}

void SelectionSort(char C[1000][2],int N){
    int i,j,v1,v2,minj;
    for (i=0;i<N;i++){
        minj = i;
        for (j=i;j<N;j++){ 
            if ((C[j][1]-'0') < (C[minj][1]-'0')){
                minj = j;
            }
        }
        v1=C[i][0];
        v2=C[i][1];
        C[i][0]=C[minj][0];
        C[i][1]=C[minj][1];
        C[minj][0]=v1;
        C[minj][1]=v2;
    }
}
int isStable(char Cin[1000][2], char Cout[1000][2],int N){
    int i,j,a,b;
    for (i=0;i<N;i++){
        for(j=i+1;j<N;j++){
            for(a=0;a<N;a++){
               for(b=a+1;b<N;b++){
                    if (Cin[i][1]-'0' == Cin[j][1]-'0'){
                        if((Cin[i][0]==Cout[b][0]) && (Cin[i][1]==Cout[b][1])){
                            if ((Cin[j][0]==Cout[a][0]) && (Cin[j][1] == Cout[a][1])){
                                return 2;
                            } 
                        }   
                    }
               }
            }
        }
   }
   return 1 ;
}
int main(){
    int N,i,k;
    char Cin[1000][2],Cs[1000][2],Cb[1000][2];
    cin>>N;
    for(i=0;i<N;i++){
        scanf("%s",&Cin[i]);
        Cs[i][0]=Cin[i][0];
        Cs[i][1]=Cin[i][1];
        Cb[i][0]=Cin[i][0];
        Cb[i][1]=Cin[i][1];
    }
    BubbleSort(Cb,N);
    for(k=0;k<N-1;k++){
        cout<<Cb[k][0]<<Cb[k][1]<<" ";
    }
    cout<<Cb[N-1][0]<<Cb[N-1][1]<<endl;
    cout<<"Stable"<<endl;

    SelectionSort(Cs,N);
    for(k=0;k<N-1;k++){
        cout<<Cs[k][0]<<Cs[k][1]<<" ";
    }
    cout<<Cs[N-1][0]<<Cs[N-1][1]<<endl;
    if (isStable(Cin,Cs,N) == 1){
        cout<<"Stable"<<endl;
    }else if(isStable(Cin,Cs,N)==2){
        cout<<"Not stable"<<endl;
    }
    return 0;
}




Measured memory_bytes: 3240
// Problem : C - Sequence
// Contest : AtCoder - AtCoder Beginner Contest 059
// URL : https://atcoder.jp/contests/abc059/tasks/arc072_a
// Memory Limit : 256 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define eb emplace_back
#define pb push_back
#define size(s) (int)s.size()
#define int long long
#define vi vector<int>
#define vs vector<string>
#define vv vector<vector<int>>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define f first
#define se second
#define inc(v,n,x) v.assign(n,x)
#define incd(v,n) v.resize(n)
#define iniz(n) memset(n,0,sizeof(n))
#define inin(n) memset(n,-1,sizeof(n))
#define inimi(n) memset(n,0xc0,sizeof(n))
#define inima(n) memset(n,0x3f,sizeof(n))
#define all(v) (v).begin(),(v).end()

using namespace std;

template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

double pi=acos(-1.0);
const int md=1e9+7;
const int INF=1e15;
int dx1[]={0,0,-1,1};
int dy1[]={1,-1,0,0};

template<class T>
T abst(T a)
{return a<0?-a:a;}

template<class T>
T max2(T a,T b){return a>b?a:b;}
template<class T>
T min2(T a,T b){return a<b?a:b;}
int n;vi v;
void solve()
{
cin>>n;
incd(v,n);cin>>v;
int ans=INF;
//case 1 : +-+-...
int sum=0;
int cnt=0;
for(int i=0;i<n;i++)
{
	if(i&1)
	{
		//negative
		if(sum+v[i]<0)
		{
			sum=sum+v[i];
		}
		else
		{
			cnt+=abst(-1-sum-v[i]);
			sum=-1;
		}
	}
	else
	{
		if(sum+v[i]>0)
		{
			sum+=v[i];
		}
		else
		{
			cnt+=abst(1-sum-v[i]);
			sum=1;
		}
	}
}
ans=min2(ans,cnt);
//case 2:-+-+
sum=0,cnt=0;
for(int i=0;i<n;i++)
{
	if(i&1)
	{
		if(sum+v[i]>0)
		{
			sum+=v[i];
		}
		else
		{
			cnt+=abst(1-sum-v[i]);
			sum=1;
		}
	}
	else
	{
		if(sum+v[i]<0)
		{
			sum=sum+v[i];
		}
		else
		{
			cnt+=abst(-1-sum-v[i]);
			sum=-1;
		}
	}
}
ans=min2(ans,cnt);
cout<<ans;
}

int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)
{
    solve();
}
return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <cstdlib>

using namespace std;
typedef long long int ll;

bool debug = false;
#define show(x) if (debug) {cout << "" # x << " = " << x << endl;}
#define rep(x, a, b) for (int x = a; x < b; x++)

int main()
{
  string s;
  cin >> s;

  bool f = false, g = false;

  for (auto c : s) {
    if (!f) {
      if (c == 'C') {
        f = true;
      }
    } else {
      if (c == 'F') {
        g = true;
      }
    }
  }

  cout << (g?"Yes":"No") << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long 
#define FI first 
#define SE second
#define pb push_back 
#define eb emplace_back
#define mod 1000000007
#define all(c) (c).begin(),(c).end()
#define LB  lower_bound
#define UB  upper_bound
#define max3(a,b,c) max(c,max(a,b))
#define min3(a,b,c) min(c,min(a,b))
#define mems(s, n) memset(s, n, sizeof(s))
#define NINF -1e18
#define INF 1e18
#define int ll int
#define double long double
#define OOK order_of_key  //no of elements less than
#define FBO find_by_order //iterator pointing kth element;indexing starts from 0
#define CK3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
#define CK4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl

typedef pair<int,int> PII;
typedef pair<pair<int,int>,int> PPII;
typedef pair<int,pair<int,int>> PIPI;
typedef map<int,int>MII;
typedef vector<int> VI;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

/*int power(int a, int b)
{int x=1,y=a;while(b>0){if(b%2){x =(x*y)%mod;}y =(y*y)%mod;b/=2;}return x%mod;}
*/
int parent[1000000],sz[1000000];
int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}
void make_set(int v) {
    parent[v] = v;
    sz[v] = 1;
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (sz[a] < sz[b])
            swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
    }
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0);
int T=1,T1=0;//cin>>T;
while(T1++<T)
{//cout<<"Case #"<<T1<<": ";
    int n;
    cin>>n;vector<PPII>re,re2,se;
    for(int i=0;i<n;i++)
    {   make_set(i);
        int x,y;
        cin>>x>>y;
        re.pb({{x,y},i});
        re2.pb({{y,x},i});
    }
    sort(all(re));sort(all(re2));
    int x=0;
    while(x<n)
    {
        while(se.size()>0&&((se.back()).FI.SE<re[x].FI.SE))
        {
            union_sets(re[x].SE,se.back().SE);
            se.pop_back();
        }
        se.pb(re[x]);
        x++;
    }
    se.clear();
    x=n-1;
    while(x>=0)
    {
        while(se.size()>0&&((se.back()).FI.SE>re[x].FI.SE))
        {
            union_sets(re[x].SE,se.back().SE);
            se.pop_back();
        }
        se.pb(re[x]);
        x--;
    }
    x=0;se.clear();
    while(x<n)
    {
        while(se.size()>0&&((se.back()).FI.SE<re2[x].FI.SE))
        {
            union_sets(re2[x].SE,se.back().SE);
            se.pop_back();
        }
        se.pb(re2[x]);
        x++;
    }
    se.clear();
    x=n-1;
    while(x>=0)
    {
        while(se.size()>0&&((se.back()).FI.SE>re2[x].FI.SE))
        {
            union_sets(re2[x].SE,se.back().SE);
            se.pop_back();
        }
        se.pb(re2[x]);
        x--;
    }
    for(int i=0;i<n;i++)
    {
        int f=find_set(i);
        cout<<sz[f]<<endl;
    }
    
}


return 0;
}





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

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (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 W = 0;W < (n);W++)cerr << v[W] << ' ';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()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

int main(){
	int n;
	while(cin >> n,n){
		vector<int> hoge(30);
		vector<char> v(n);REP(i,n)cin >> v[i];
		bool flag = false;
		REP(i,n){
			hoge[v[i] - 'A']++;
			vector<int> tmp(30);
			REP(j,30)tmp[j] = hoge[j];
			sort(ALL(tmp),greater<int>());
			if(tmp[0] - tmp[1] > n-i-1){
				REP(j,30){
					if(hoge[j] == tmp[0]){
						flag = true;
						char seica = j + 'A';
						cout << seica << ' ' << i + 1<< endl;
						j = 100;i = n;
						break;
					}
				}
			}
		}
		if(!flag)cout << "TIE" << endl;
		
	}
	return 0;
}


Measured memory_bytes: 3160
line = gets.chomp
#文字列として受け取った
arr = line.split(" ")

newArr = arr.map{
    |s| s.to_i
}
#[2, 900]

k = newArr[0]
#500円の枚数

x = newArr[1]
#900

if k * 500 >= x
  puts "Yes"
elsif k * 500 < x
  puts "No"
end






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


  
int main(){
  int a,b,c,d,e,k;
  cin>>a>>b>>c>>d>>e>>k;
  
  if (e-a>k){
    cout<<":("<<endl;
  }
  
  else {
    cout<<"Yay!"<<endl;
  }
  
  
    
  
}

Measured memory_bytes: 256
# n 夏休み日数
# m 宿題の数
# a1,a2.. それぞれの宿題がかかる日数

n , m = map(int,input().split())
a = list(map(int,input().split()))

total = sum(a)

if(total>n):
  print(-1)
else:
  print(n-total)

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

const int mod = 1e9+7;
const int INF = 2000000;

int main() {
    string s;
    cin >> s;
    ll ans = 0, c = 0;
    for(int i=0;i<s.size();++i) {
        if(s[i]=='W') {
            ans += c;
            continue;
        }
        ++c;
    }
    cout << ans << endl;
}



Measured memory_bytes: 640
import math

A, B, H, M = map(int, input().split())
a = 30*H+0.5*M
b = 6*M
kaku = abs(a-b)
if kaku > 180:
    kaku = 360-kaku
#print(kaku)
#print(math.cos(math.radians(kaku)))
ans = A*A+B*B-2*A*B*math.cos(math.radians(kaku))
print(math.sqrt(ans))


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

#define REP(i,n) for(long long i=0;i<n;++i)
#define REPR(i,n) for(long long i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(long long i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define MOD 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(v) {for(long long sitr=0;sitr<v.size();++sitr){cin>>v[sitr];}}

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

using namespace std;

typedef pair<int,int> pii;

int main(){

  int n;
  cin >> n;
  REP(i,9){
    REP(j,9){
      if((i+1) * (j+1) == n){
        cout << "Yes\n";
        return 0;
      }
    }
  }
  cout << "No\n";
  return 0;
}



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

int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	if (a >= b && a >= c)
	{
		cout << (b + c);
	}
	else if (b >= a &&  b >= c)
	{
		cout << (a + c);
	}
	else
	{
		cout << (a + b);
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int main()
{
    int n;
    string s;
    cin >>n >>s;

    int c=0;
    int m=0;
    rep(i,n)
    {
        if(s[i]=='(') ++c;
        else --c;

        m=min(m,c);
    }

    string ans = string(-m,'(') + s;

    c = 0;
    rep(i,ans.size())
    {
        if(ans[i]=='(') ++c;
        else --c;
    }

    if(c>0) ans = ans + string(c,')');

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


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

int main() {

    int n, k;
    cin >> n >> k;
    if(n<k){
    	for(int i=0; i<k; i++){
    		cout << n;
    	}
    }else if(n>=k){
    	for(int i=0; i<n; i++){
    		cout << k;
    	}
    }
} 

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

int a, b;

int main() {
    cin >> a >> b;
    if(a >= 13)
        cout << b << endl;        
    if(6 <= a && a <= 12)
        cout << b/2 << endl;
    if(a <= 5)
        cout << 0 << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
  
  public static void main (String []args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int a = 0;
    int b = 0;
    
    for (int i = 0; i <= 2; i++){
      if (s.charAt(i) == 'A'){
        a++;
      }else {
        b++;
      }
    }
    if (a == 3 || b ==3 ){
      System.out.println("No");
    }else{
      System.out.println("Yes");
    }
  }
}
        
      
      
      

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;

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

int main()
{
	int n, p;
	cin >> n >> p;
	int a;
	int flag = 0;
	REP(i, n){
		cin >> a;
		if (a % 2) flag = 1; 
	}
	ll ans = 1;
	FOR(i, 1, n){
		ans *= 2;
	}
	if (flag) cout << ans << endl;
	else cout << (p ? 0 : ans*2)  << endl;


}


Measured memory_bytes: 256
/// Bismillah Hir Rahmanir Rahim

/**
    Practice like Cristiano Ronaldo
        Play Like Leo Messi..
**/

#include <bits/stdc++.h>

using namespace std;

#define PI                    acos(-1.0)
#define Pi                    3.141592653589793
#define ff                    first
#define ss                    second
#define pb                    push_back
#define space                 " "
#define all(x)                (x).begin(), (x).end()
#define clr(ar)               memset(ar, 0, sizeof(ar))
#define eprintf(...)          fprintf(stderr, __VA_ARGS__)

/*
template <class T> T gcd(T a,T b){ if(b == 0) return a; return gcd( b,a % b ); }
template <class T> T lcm(T a, T b ){ return ( a * b ) / gcd( a,b ); }
template<class T> string ToString(const T &x){ stringstream s; s << x; return s.str(); }
template<class T> int ToInteger(const T &x){ stringstream s; s << x; int r; s >> r; return r; }
*/

typedef  long long int            ll;
typedef  map<string,int>          msi;
typedef  map<int,int>	          mii;
typedef  map<char,int>            mci;
typedef  map<int,string>	      mis;
typedef  pair<int,int> 	          ii;
typedef  pair<string, int>        psi;
typedef  vector<int> 	          vi;
typedef  vector<string> 	      vs;
typedef  vector< ii >             vii;

template<class T1> void deb(T1 e1)
{
    cout << e1 << endl;
}
template<class T1,class T2> void deb(T1 e1, T2 e2)
{
    cout << e1 << space << e2 << endl;
}
template<class T1,class T2,class T3> void deb(T1 e1, T2 e2, T3 e3)
{
    cout << e1 << space << e2 << space << e3 << endl;
}

#define sf                    scanf
#define pf                    printf

#define sf1(a)                scanf("%d", &a)
#define sf2(a,b)              scanf("%d %d",&a, &b)
#define sf3(a,b,c)            scanf("%d %d %d", &a, &b, &c)
#define sf4(a,b,c,d)          scanf("%d %d %d %d", &a, &b, &c, &d)

#define sf1ll(a)              scanf("%I64d", &a)
#define sf2ll(a,b)            scanf("%I64d %I64d", &a, &b)
#define sf3ll(a,b,c)          scanf("%I64d %I64d %I64d", &a, &b, &c)
#define sf4ll(a,b,c,d)        scanf("%I64d %I64d %I64d %I64d", &a, &b, &c, &d)

#define READ                  freopen("in.txt", "r", stdin);
#define WRITE                 freopen("out.txt", "w", stdout);
/// The End.

void check_time()
{
#ifdef the_badcoder
    eprintf("%.5lf\n", (double)clock() / CLOCKS_PER_SEC);
#endif
}

const int res = 1e5 + 10;
const ll mod = 1e9 + 7;


int main()
{
    int n;
    ll dp[res];

    sf1( n );
    dp[ 0 ] = 2, dp[ 1 ] = 1;

    for( int i = 2; i <= n; i++ )
    {
        dp[ i ] = dp[ i - 1 ] + dp[ i - 2 ];
    }

    printf("%lld\n", dp[ n ] );

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int a, b;
	scanf("%d %d", &a, &b);
	
	if(a == b)
		printf("a == b\n");
	else if(a > b)
		printf("a > b\n");
	else
		printf("a < b\n");
	
	return 0;
}


Measured memory_bytes: 2548
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
S = input()

print(S[:K-1], end="")
print(chr(ord(S[K-1])+32), end="")
print(S[K:])


Measured memory_bytes: 5712
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	int A = sc.nextInt();
       	int B =sc.nextInt();
       	int a =sc.nextInt();
       	int b =sc.nextInt();

       	int ans = (A-a) * (B-b);

       	System.out.println(ans);
}

}


Measured memory_bytes: 23124
#include <iostream>
#include <functional>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <iomanip>
#include <complex>
#include <random>
#include <bitset>
#include <list>
// #include <prettyprint.hpp>
using namespace std;
#define repi(i,n) for(int i=0;i<n;++i)
#define rep(i,n) for(ll i=0;i<n;++i)
#define repinvi(i,n) for(int i=n-1;i>=0;--i)
#define sll(n) scanf("%lld", &n);
#define sii(n) scanf("%d", &n);
#define slf(n) scanf("%lf", &n);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define psi pair<si,si>
typedef long long ll;
typedef double lf;
typedef short int si;

void Main(){
    string S;
    cin >> S;
    ll s = 0;
    for(auto c:S){
        s += c - '0';
    }
    if(s % 9 == 0){
        cout << "Yes" <<endl;
    }else{
        cout << "No" <<endl;
    }

}

int main(){
    Main();
}

Measured memory_bytes: 3320
def solve(N, M, KAs):
    ans = 0
    for m in range(1, M+1):
        if all(m in KAs[n][1:] for n in range(N)):
            ans += 1
    return ans


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    KAs = list(list(map(int, input().split(" "))) for _ in range(N))
    print(solve(N, M, KAs))


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using lint = long;
using ll = long long;
#define rep(i,n) for( lint i = 0; i < (lint)n; i++ )
#define repInRange(i,start,end) for( lint i = start; i < end ; ++i )
using lpair = pair<lint,lint>;
using Vecint = vector<lint>;
using Llist = list<lint>;

#define MAX( x, y ) x >= y ? x : y
#define MIN( x, y ) x <= y ? x : y

ll pow(ll k,ll l) {
	ll ret = 1;
	rep(i,l) {
		ret *= k;
	}
	return ret;
}

void Main() {
	unsigned long n, lmax, sum = 0;
	cin >> n;
	vector<unsigned long> a(n);
	rep ( i, n )
		cin >> a[i];
	
	lmax = a[0];
	repInRange ( i, 1, n ) {
		if ( a[i] <= lmax )
			sum += lmax - a[i];
		else
			lmax = a[i];
	}
	cout << sum << '\n';
}

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

Measured memory_bytes: 4776
#include <bits/stdc++.h>
#include <math.h>
#include <regex>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const int INF = 1001001001;

int main(){
    ll n,m ; cin >> n >> m;
    vector<ll> p(n);
    rep(i,n){
        cin >> p.at(i);
        p.at(i)--;
    }

    vector<vector<ll>> hen(n);
    rep(i,m){
        ll x,y; cin >> x >> y;
        x--; y--;
        hen.at(x).push_back(y);
        hen.at(y).push_back(x); 
    }

    vector<bool> seen(n,0);
    ll ans = 0;

    rep(i,n){
        if(seen.at(i)) continue;
        set<ll> s;
        queue<ll> q;
        q.push(i);
        seen.at(i) = 1;
        while(q.size()){
            ll x = q.front();
            if(s.count(x)) ans++; else s.insert(x);
            q.pop();
            if(s.count(p[x])) ans++; else s.insert(p[x]);
            for(auto a:hen.at(x)){
                if(seen.at(a)) continue;
                q.push(a);
                seen.at(a) = 1;
            }
        }
        //cout << i << " " << ans << endl;
    }
    cout << ans << endl;
}

Measured memory_bytes: 11392
//https://atcoder.jp/contests/keyence2019/tasks/keyence2019_e 
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
#define fst first
#define sed second
#define pb push_back
#define mp make_pair
#define rt register int
#define all(it) it.begin(), it.end()
#define rep(it, f, e) for (rt it = f; it <= e; ++it)
#define per(it, f, e) for (rt it = f; it >= e; --it)
const int MAXN = 2e5 + 10;
struct Dsu {
	int par[MAXN];
	Dsu() {
		rep (i, 1, MAXN - 1) {
			par[i] = i;
		}
	}
	inline int find(int x) {
		return x == par[x] ? x : par[x] = find(par[x]);
	}
	inline void mry(int a, int b) {
		par[find(a)] = find(b);
	}
	inline bool tog(int a, int b) {
		return find(a) == find(b);
	}
}	dsu;
struct Tree {
	#define lson (root << 1)
	#define rson (root << 1 | 1)
	#define mid ((tree[root].stdl + tree[root].stdr) >> 1)
	struct Node {
		int stdl, stdr;
		pair<ll,int> mn;
	}	tree[MAXN << 2];
	inline void buildtree(int root, int l, int r) {
		tree[root].stdl = l;
		tree[root].stdr = r;
		tree[root].mn = mp(1e18, l);
		if (l == r) return;
		buildtree(lson, l, mid);
		buildtree(rson, mid + 1, r);
	}
	inline void update(int root) {
		tree[root].mn = min(tree[lson].mn, tree[rson].mn);
	}
	inline pair<ll,int> query(int root, int l, int r) {
		if (l <= tree[root].stdl && tree[root].stdr <= r) {
			return tree[root].mn;
		}
		pair<ll,int> ret(1e18, 1e9);
		if (l <= mid) ret = min(ret, query(lson, l, r));
		if (r > mid) ret = min(ret, query(rson, l, r));
		return ret;
	}
	inline void change(int root, int x, ll p) {
		if (tree[root].stdl == tree[root].stdr) {
			tree[root].mn = mp(p, tree[root].stdl);
			return;
		} 
		if (x <= mid) change(lson, x, p);
		else change(rson, x, p);
		update(root);
	}
}	T;
ll A[MAXN], n, d;
vector<pair<ll,int> > edge[MAXN];
inline void solve(int l, int r) {
	if (l == r) return;
	int m = (l + r) >> 1;
	ll ml = 1e18, li = 0;
	rep (i, l, m) {
		if (ml > A[i] - i * d) {
			ml = A[i] - i * d;
			li = i;
		}
	}
	ll mr = 1e18, ri = 0;
	rep (i, m + 1, r) {
		if (mr > A[i] + i * d) {
			mr = A[i] + i * d;
			ri = i;
		}
	}
	rep (i, l, m) {
		edge[i].pb(mp(A[i] - i * d + mr, ri));
		edge[ri].pb(mp(A[i] - i * d + mr, i));
	}
	rep (i, m + 1, r) {
		edge[i].pb(mp(A[i] + i * d + ml, li));
		edge[li].pb(mp(A[i] + i * d + ml, i));
	}
	solve(l, m);
	solve(m + 1, r);
}
bool Hash[MAXN];
int main() {
	cin >> n >> d;
	rep (i, 1, n) {
		cin >> A[i];
	}
	solve(1, n);
	ll ans = 0;
	Hash[1] = 1;
	T.buildtree(1, 1, n);
	for (auto p : edge[1]) {
		T.change(1, p.sed, p.fst);
	}
	rep (i, 2, n) {
		pair<ll, int> v = T.query(1, 1, n);
		ans += v.fst;
		Hash[v.sed] = 1;
		T.change(1, v.sed, 1e18);
		for (auto p : edge[v.sed]) {
			if (Hash[p.sed]) continue;
			if (p.fst < T.query(1, p.sed, p.sed).fst) {
				T.change(1, p.sed, p.fst);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 189424
#include<stdio.h>
#include<math.h>
int min(int a,int b){
	if(a>b)a=b;
	return a;
}
int main(){
	int a=1000000,n,k,i,j,x,y,b,m[26][26];
	scanf("%d%d",&n,&k);
	for(i=0;i<n;i++)for(j=0;j<k;j++)scanf("%d",&m[i][j]);
	for(i=0;i<n;i++){
		for(j=0;j<k;j++){
			b=0;
			for(x=0;x<n;x++){
				for(y=0;y<k;y++)b+=m[x][y]*min(abs(i-x),abs(j-y));
			}
			a=min(a,b);
		}
	}
	printf("%d\n",a);
	return 0;
}


Measured memory_bytes: 2044