akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
 
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
constexpr int MOD = 1000000007;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int dy[] = {0, -1, 0, 1, 1, -1, -1, 1};
 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os; }
 
struct rule {
  int l, x;
};
 
void solve() {
  int N, M;
  cin >> N >> M;
  vector<vector<rule>> R(N + 1);
  for (int i = 0; i < M; i++) {
    int l, r, x;
    cin >> l >> r >> x;
    R[r].push_back({l, x});
  }
  
  const int mod = 1e9 + 7;
  vector<vector<vector<ll>>> dp(N + 1, vector<vector<ll>>(N + 1, vector<ll>(N + 1, 0)));
  dp[0][0][0] = 1;
  for(int i = 0; i <= N; i++) {
    for(int j = 0; j <= N; j++) {
      for(int k = 0; k <= N; k++) {
        int m = max({i, j, k});
        vector<int> c{i, j, k};
        sort(all(c));
        auto f = [&c](int l) {
          if (l > c[1]) return 1;
          if (l > c[0]) return 2;
          return 3;
        };
        bool flag = true;
        for(int p = 0; p < R[m].size(); p++) {
          int l = R[m][p].l;
          int x = R[m][p].x;
          if (f(l) != x) {
            flag = false;
            break;
          }
        }
        if (!flag) {
          dp[i][j][k] = 0;
          continue;
        }
 
        int m_ = m + 1;
        if (m_ > N) continue;
        dp[m_][j][k] += dp[i][j][k]; dp[m_][j][k] %= mod;
        dp[i][m_][k] += dp[i][j][k]; dp[i][m_][k] %= mod;
        dp[i][j][m_] += dp[i][j][k]; dp[i][j][m_] %= mod;
      }
    }
  }
  ll ans = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      ans += dp[N][i][j]; ans %= mod;
      ans += dp[i][N][j]; ans %= mod;
      ans += dp[i][j][N]; ans %= mod;
    }
  }
  cout << ans << endl;
 
}
 
int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  cout.setf(ios::fixed);
  cout.precision(16);
  solve();
  return 0;
}


Measured memory_bytes: 218880
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int k = in.nextInt();
		int[] a = new int[n];
		int sum = 0;
		for(int i=0;i<n;i++) {
			a[i] = in.nextInt();
			sum += a[i];
		}
		List<Integer> list = new ArrayList<>();
		for(int i=1;i*i<=sum;i++) {
			if(sum%i==0) {
				if(i*i==sum) list.add(i);
				else {
					list.add(i);
					list.add(sum/i);
				}	
			}
		}
		list.sort((e1,e2)->-e1+e2);
		int ans = 0;
		for(int num : list) {
			if(num==1) ans = 1;
			else {
				int[] b = new int[n];
				int sum2 = 0;
				for(int i=0;i<n;i++) {
					b[i] = a[i]%num;
					sum2 += num-b[i];
				}
				Arrays.sort(b);
				int sum3 = 0;
				int idx = 0;
				while(sum2!=sum3) {
					sum2 -= num-b[idx];
					sum3 += b[idx];
					idx++;
				}
				if(sum2<=k) {
					ans = num;
					break;
				}
			}
		}
		System.out.println(ans);
		
		
		in.close();

	}

}


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

const int M = (int)1e9 + 7;
const int N = (int)2e6 + 5;

ll f[N], rf[N];

ll powmod(ll a, ll b) {
  if(b == 0) return 1;
  ll ans = powmod(a, b / 2);
  ans = ans * ans % M;
  if(b % 2) ans = ans * a % M;
  return ans;
}
ll C(ll a, ll b) {
  if(a < b) return 0;
  return f[a] * rf[b] % M * rf[a - b] % M;
}

ll x, y;

void build() {
  f[0] = 1;
  for(int i = 1 ; i < N ; ++i) f[i] = f[i - 1] * i % M;
  rf[N - 1] = powmod(f[N - 1], M - 2);
  for(int i = N - 2 ; i >= 0 ; --i) rf[i] = rf[i + 1] * (i + 1) % M;
}
void init() {
  cin >> x >> y;
}
void solve() {
  if((x + y) % 3 != 0) { cout << "0\n"; return; }
  ll xy = (x + y) / 3, xx = 2 * xy - y, yy = 2 * xy - x;
  if(xx < 0 || yy < 0) { cout << "0\n"; return; }
  cout << C(xx + yy, xx) << '\n';
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  build();
  init();
  solve();
}


Measured memory_bytes: 31488
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
#define SortAsc(c) std::sort(c.begin(), c.end())
#define SortDesc(c) std::sort(c.rbegin(), c.rend())
int dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int dy[8] = {1, 0, -1, 0, 1, -1, 1, -1};

int main() {
  int N, M;
  cin >> N >> M;
  int c = 0;
  for (int i = 0; i < M; i++) {
    int a;
    cin >> a;
    c += a;
  }
  if (c <= N) {
    cout << N - c << endl;
  } else {
    cout << -1 << endl;
  }
}

Measured memory_bytes: 3636
#include <iostream>
using namespace std;
#define MAX 500001

int heap[MAX];
int sizeOfHeap;

int getLeft(int node) {
	return node * 2;
}

int getRight(int node) {
	return node * 2 + 1;
}

void swapValue(int a, int b){
	int tmp = heap[a];
	heap[a] = heap[b];
	heap[b] = tmp;
}

void maxHeapify(int currNode) {
	int left = getLeft(currNode);
	int right = getRight(currNode);
	int largest;
	// pick out the largest one among currNode and its child nodes
	if (left <= sizeOfHeap && heap[left] > heap[currNode])
		largest = left;
	else
		largest = currNode;
	if (right <= sizeOfHeap && heap[right] > heap[largest])
		largest = right;

	if (largest != currNode){
		swapValue(currNode, largest);
		maxHeapify(largest);
	}
}

void buildMaxHeap() {
	for (int i = sizeOfHeap / 2; i >= 1 ; i-- ) {
		maxHeapify(i);
	}
}

int main(){

	cin >> sizeOfHeap;

	for( int i = 1; i <= sizeOfHeap ; i++) {
		cin >> heap[i];
	}

	buildMaxHeap();

	for( int i = 1; i <= sizeOfHeap ; i++) {
		cout << " " << heap[i];
	}
	cout << endl;

	return 0;
}

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

int main(){
    int n;  cin>>n;
    long min=1000000000;
    long max=0;

    for(int i=0;i<n;i++){
        int x;  cin>>x;
        if(x>max)max=x;

        if(x<min)min=x;
    }

    cout<<max-min<<endl;

    return 0;
}


Measured memory_bytes: 256
/**
 * ?????§?????????
 * FX????????§????????°?????????????????¨????????????????????¨??§????????????????????????????????¨?????§????????????????????°????????????100???????????? 1000???????????????????????????????????? 1?????? 108???????????£??????????£??????¨???(108??? ?????? 100???) ???? 1000?????? == 8000??????????????????????????¨?????§????????????
 * <p>
 * ???????????¨?????????????????????t?????????????????? Rt(t=0,1,2,,,n???1)?????\?????¨??????????????????????????§??????????????? Rj???Ri (?????????,j>i??¨??????) ????????§???????±??????????????????????
 * <p>
 * ??\???
 * ?????????????????´??°n?????????????????????????¶????n????????´??° Rt(t=0,1,2,,,n???1) ?????????????????????????????????
 * <p>
 * ??????
 * ?????§??????????????????????????????????????????
 * <p>
 * ??¶?´?
 * 2???n???200,000
 * 1???Rt???10e9
 */

import java.util.*;

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

		int t = stdIn.nextInt();
		int[] profitT = new int[t];

		for (int i = 0; i < t; i++) {
			profitT[i] = stdIn.nextInt();
		}

		int maxProfit = profitT[1] - profitT[0];

		int min = profitT[0];
		for (int i = 1; i < t; i++) {
			if (maxProfit < profitT[i] - min) {
				maxProfit = profitT[i] - min;
			}
			if (min > profitT[i]) {
				min = profitT[i];
			}
		}
		System.out.println(maxProfit);
	}
}

Measured memory_bytes: 101888
#include "bits/stdc++.h"
#define REP(i, n) for(int i = 0; i < int(n); i++)
#define FOR(i,n,m) for(int i = int(n); i < int(m); i++)
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 6;
const ll LLINF = 1e18 + 1;
 
int main() {
    int n; cin >> n;
    string s; cin >> s;
    int ans = 0;
    REP(i, 1000) {
        int a = i / 100, b = (i - a * 100) / 10, c = i % 10;
        int f = 0;
        REP(j, s.size()) {
            if (f == 0 && s[j] - '0' == a) f = 1;
            else if (f == 1 && s[j] - '0' == b) f = 2;
            else if (f == 2 && s[j] - '0' == c) f = 3;
        }
        if (f == 3) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string.h>

using namespace std;

int main()
{
  int N;
  int RedSum = 0;
  int Sum = 0;
  string str;
  cin >> N;
  cin >> str;
  for(int i = 0;i < N;i++)
  {
    if(str[i] == 'R')
    {
      RedSum++;
    }
  }
  for(int j = 0; j < RedSum; j++)
      {
    if(str[j] == 'R')
    {
      Sum++;
    }
  }
  cout << RedSum-Sum << endl;
  return 0;
}

Measured memory_bytes: 3484
#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()
typedef long long ll;
const int INF = 100000000;
const long INF64 = 1000000000000000ll;
const int MOD = 1000000007;
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};
int main(){
  int n,m;
  int counter=0;
  std::cin >> n>>m;
  std::vector<int> a(m),b(m);
  rep(i,m)std::cin >> a[i]>>b[i];
  for (int i = 0; i < m; i++) {
    /* code */
    int bo=1;
    UnionFind tree(n);
    rep(j,m){
      if(i!=j)tree.unite(a[j]-1,b[j]-1);
    }
    for (int j = 1; j < n; j++) {
      /* code */
      if(!tree.same(0,j))bo=0;
    }
    counter+=bo;
  }
  std::cout << m-counter << std::endl;
}

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

using namespace std;

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

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

int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  vector<int64> L(n), R(n), sum(n + 1);
  L[0] = max(0, a[0]);
  for (int i = 1; i < n; ++i) L[i] = L[i - 1] + max(0, a[i]);
  R[n - 1] = max(0, a[n - 1]);
  for (int i = n - 2; i >= 0; --i) R[i] = R[i + 1] + max(0, a[i]);
  for (int i = 0; i < n; ++i) sum[i + 1] = sum[i] + a[i];
  int64 ret = 0;
  for (int i = 0; i + k <= n; ++i) {
    int64 cur = max(0LL, sum[i + k] - sum[i]);
    if (i - 1 >= 0) cur += L[i - 1];
    if (i + k < n) cur += R[i + k];
    ret = max(ret, cur);
  }
  printf("%lld\n", ret);
  return 0;
}


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

int main(){
	vector<P> p;
	int N;
	cin >> N;
	rep(i,N){
		P t;
		cin >> t.first >> t.second;
		p.push_back(t);
	}
	sort(p.begin(),p.end());
	double sum=0; int c=0;
	do{
		c++;
		float a;
		rep(i,N-1){
			//cout << "(" << p[i].first <<","<<p[i].second <<")"<< " ";
			int x = p[i+1].first-p[i].first;
			int y = p[i+1].second - p[i].second; 
			a = sqrt(x*x + y*y);
			sum += a;
		}
		//cout << "(" << p[N-1].first <<","<<p[N-1].second <<")"<< " ";
		//cout << "c: "<<c<< endl;

	}while(next_permutation(p.begin(),p.end()));

	printf("%.6lf\n",sum /c);
}


Measured memory_bytes: 256
/***** author :  C0d1ngPhenomena *****/

#include <bits/stdc++.h>
#define endl "\n"
#define ll long long int
#define TestCases int T; cin>>T; while(T--)
#define rep(i,a,b) for(ll i = a; i < b; i++)
#define revrep(i,a,b) for(ll i = b-1; i >= a; i--)
#define vll vector<ll>
#define vvll vector < vll >
#define pll pair<ll, ll>
#define vpll vector <pll>
#define mp(x,y) make_pair(x,y)
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define alld(c) c.begin(),c.end(),greater<int>()
#define mem(a,val) memset(a,val,sizeof(a))
#define f first
#define s second
#define pb push_back
using namespace std;

bool sortbysec(const pair<int, int> &a, const pair<int, int> &b)
{
	return (a.second < b.second);
}


int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll n;
	cin >> n;
	if (n >= 400 and n < 600) cout << 8;
	else if (n >= 600 and n < 800) cout << 7;
	else if (n >= 800 and n < 1000)cout << 6;
	else if (n >= 1000 and n < 1200)cout << 5;
	else if (n >= 1200 and n < 1400)cout << 4;
	else if (n >= 1400 and n < 1600)cout << 3;
	else if (n >= 1600 and n < 1800)cout << 2;
	else cout << 1;


	return 0;
}







Measured memory_bytes: 3592
// -_-
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define rz resize
#define fori(i, a, b) for(int i = a; i <= b; i++)
#define ford(i, a, b) for(int i = a; i >= b; i--)
#define mod 1000000007
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int, int> pii;
typedef pair<long long , long long> pll;
 
int main() 
{

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

    ll n, h, x, y;
    cin >> n >> h;
    vector < pair <ll, ll> > vec;
    vi b(n);
    fori(i, 0, n-1)
    {
    	cin >> x >> y;
    	vec.pb({x, y});
    	b[i] = y;
    }

    sort(vec.begin(), vec.end());
    sort(b.begin(), b.end());

    ll ct = 0;
    ford(i, n-1, 0)
    {
    	if(b[i] < vec[n-1].fi) break;

    	else
    	{
    		h -= b[i];
    		ct++;
    		if(h <= 0) {cout << ct; return 0;}
    	}
    }

    if(h % (vec[n-1].fi) == 0) ct += h/(vec[n-1].fi);
    else ct += (h/vec[n-1].fi + 1);

    cout << ct;

	return 0;
}

Measured memory_bytes: 2804
s = list(input())[::-1]

c = 0

r = "YES"

while c < len(s):
    try:
        if s[c:c + 6] == list('eraser')[::-1]:
            c += 6
        elif s[c:c + 7] == list('dreamer')[::-1]:
            c += 7
        elif s[c:c + 5] == list('dream')[::-1] or s[c:c + 5] == list('erase')[::-1]:
            c += 5
        else:
            r = "NO"
            break
    except IndexError:
        r = "NO"
        break

print(r)


Measured memory_bytes: 4652
#include <iostream>
#include <string>
#include <vector>
#include <algorithm> 
#include <utility> 
#include <tuple> 
#include <cstdint> 
#include <cstdio> 
#include <map> 
#include <queue> 
#include <set> 
#include <stack> 
#include <deque> 
#include <unordered_map> 
#include <unordered_set> 
#include <bitset> 
#include <cctype> 
#include <cmath>
#include <iomanip>
#include <ctype.h>

using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi >;
using vl = vector<ll>;
using vvl = vector<vl >;
using pairi = pair<int, int>;
using pairl = pair<ll, ll>;

#define TR ","
#define TS " "
#define rep(i,N) for(ll i=0;i<(ll)N;++i)
#define rpt(i,a,b) for(ll i=a;i<(ll)b;++i)
#define all(v) v.begin(), v.end()
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

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

ll lcm(ll x, ll y) {
    return x / gcd(x, y) * y;
}

void printVector(const vector<ll>& vec) {
    for (ll value : vec) {
        cout << value << " ";
    }
    cout << endl;
}

vector<int> IntegerToVector(int bit, int N) {
    vector<int> S;
    for (int i = 0; i < N; ++i) {
        if (bit & (1 << i)) {
            S.push_back(i);
        }
    }
    return S;
}

const int MAX = 510000;
const int MOD = 1000000007;

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

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll COM(ll n, ll k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main()
{
    
   string S; cin>>S;
   int n=S.size();
   if (S[n-1]=='s'){cout<<S+"es"<<endl;}
   else {cout<<S+'s'<<endl;}

}

Measured memory_bytes: 3632
# coding: utf-8
# Your code here!
n=int(input())
h=list(map(int,input().split()))
dp=[10000000000]*n
dp[0]=0
for i in range(n):
    if i==0:
        continue
    dp[i]=min(dp[i],abs(h[i]-h[i-1])+dp[i-1])        
    if i>1:
        dp[i]=min(dp[i],abs(h[i]-h[i-1])+dp[i-1],abs(h[i]-h[i-2])+dp[i-2])
    #print(dp)
print(dp[n-1])
#print(dp)

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

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
#define ALL(x) x.begin(),x.end()
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int N,C,K;

int main()
{
	scanf("%d%d%d",&N,&C,&K);
	vector<int> A(N);
	FOR(i,0,N){
		scanf("%d",&A [i]);
	}
	sort(ALL(A));

	int ans = 0;
	for(int i = 0;i < N;){
		int j = i;
		while(j - i < C && j < N && A [i] + K >= A [j]){
			j++;
		}
		ans++;
		i = j;
	}

	printf("%d\n",ans);

	return 0;
}


Measured memory_bytes: 764
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>

using namespace std;

#define REP(i,n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++)
#define pb push_back
#define INF 1000000007LL
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int,int> p;

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

int N;
int main(){
    ios::sync_with_stdio(false);
    cin >> N;
    vector<int> a(N);
    int cnt = 0;
    REP(i, N) {
        cin >> a[i];
        a[i]--;
    }
    int cur = 0;
    ll ans = 0;
    while(cur < N) {
        if (a[cur] == cur) {
            ans += 1;
            if (cur+1 < N && a[cur+1] == cur+1) {
                cur++;
            }
        }
        cur++;
    }
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;
int main(){
    map<int,int>mp;
    rep(i,3){
        int a,b; cin>>a>>b;
        mp[a]++; mp[b]++;
    }
    int mx=0;
    for(auto&p:mp){
        mx=max(mx,p.second);
    }
    if(mp.size()==4&&mx<=2)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <functional>
#include <limits.h>
#include <set>
#include <map>
#include <tuple>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rep(i,N) for (ll i=0;i<N;i++)
#define loop(i,N,M) for(ll i=N;i<M;i++)
#define MAX(v) *max_element(v.begin(),v.end())
#define MIN(v) *min_element(v.begin(),v.end())
#define SORTL2S(type,v) sort(v.begin(),v.end(),greater<type>())
#define SORTS2L(type,v) sort(v.begin(),v.end())
#define SORTMF(v,func) sort(v.begin(),v.end(),func)

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

void solve() {

	set<pair<ll, ll>> ans;

	if (N % 2 == 0) {

		cout << (N - 2)*N / 2 << endl;

		for (int i = 1; i < N + 1; i++) {
			for (int j = 1; j < N + 1; j++) {
				if (j != i && i + j != N + 1) ans.insert(make_pair(min(i, j), max(i, j)));
			}
		}

	}
	else {

		cout << (N - 3)*(N - 1) / 2 + N - 1 << endl;

		for (int i = 1; i < N; i++) {
			for (int j = 1; j < N; j++) {
				if (j != i && i + j != N) ans.insert(make_pair(min(i, j), max(i, j)));
			}
		}

		for (int i = 1; i < N; i++) {
			ans.insert(make_pair(i, N));
		}

	}

	for (pair<ll, ll> p : ans) {
		cout << p.first << " " << p.second << endl;;
	}

	return;
}

int main() {

	cin >> N;

	solve();
	cout << endl;
	return 0;
}

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

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

  map<ll, ll> C;
  C[0]++;
  ll tmp=0;
  rep(i, n) {
    tmp+=A[i];
    C[tmp%m]++;
  }
  ll ans=0;
  for (auto i : C) {
    ll x=i.second;
    ans+=x*(x-1)/2;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 4992
#include <stdio.h>
#define N 101
int main()
{
  int a, b, c, d, e;
  int m[N][N], p[N];
  
  scanf("%d", &a);
  
  for(b = 0; b < a; b++)scanf("%d%d", &p[b], &p[b+1]);
    for (b = 1; b <= a; b++) m[b][b] = 0;
    for (e = 2; e <= a; e++) {
      for (b = 1; b <= a - e + 1; b++) {
        c = b + e - 1;
        m[b][c] = 100000000;
        for (d = b; d <= c - 1; d++) {
          if (m[b][c] > m[b][d] + m[d + 1][c] + p[b - 1] * p[d] * p[c]) {
            m[b][c] = m[b][d] + m[d + 1][c] + p[b - 1] * p[d] * p[c];
          }
        }
      }
    }
  
  printf("%d\n", m[1][a]);
  
  return 0;
}



Measured memory_bytes: 2112
n = int(input())
an = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]

# an -> dict
dic = {}
for a in an:
    dic[a] = 1 if a not in dic else dic[a] + 1
sm = sum(k*dic[k] for k in dic)

for i in range(q):
    b, c = bc[i]
    if b in dic:
        sm -= b * dic[b]
        sm += c * dic[b]
        if c in dic:
            dic[c] += dic[b]
        else:
            dic[c] = dic[b]
        del dic[b]
    print(sm)


Measured memory_bytes: 37376
#include <iostream>
#include <vector>
#include <string>

using namespace std;
using ll = long long;

int main()
{

    string s;
    int k;
    cin >> s >> k;
    int n = 1;
    for (int i = 0; i < k; i++)
    {
        if (s[i] != '1')
        {
            n = s[i] - '0';
            break;
        }
    }

    cout << n << endl;

    return 0;
}

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

#define ll long long
#define mx  100005
#define mod 1000000009
#define lim 10000000
#define inf 1e9
#define N 18
using namespace std;
int a[mx];

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

	int n,need=1,k,kk;cin>>n>>k;
	kk=k;

	for(int i=0;i<n;i++)
		{
			if(!kk)
				need++,kk=k-1;
			kk--;
			cin>>a[i];
		}
	cout<<need<<"\n";


	return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long int ll;
typedef vector<pair<ll,ll> > Q;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(int)(n);i++)

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

  if(b>a) swap(a,b);

  if(c<=a && b<=c) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


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

int main() {
  int N, K;
  cin >> N >> K;
  /*cout << M << endl;*/

  /*int N = 3;*/
  vector<int> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }

  sort(vec.begin(), vec.end()); // vector

  int ans=0;

  for (int i = 0; i < K; i++){
    ans += vec.at(i);
  }

  cout << ans << endl;

  /*for (int i = 0; i < vec.size(); i ++){
    cout << vec.at(i) << endl;
  }

  for (int i = 0; i < vec.size()-1; i ++){
    cout << vec.at(i) << " ";
  }
  cout << vec.at(vec.size() - 1) << endl;*/
}


Measured memory_bytes: 3628
#include<set> 
#include<map> 
#include<ctime> 
#include<cmath> 
#include<cstdio> 
#include<queue> 
#include<vector> 
#include<cstring> 
#include<climits> 
#include<iostream> 
#include<algorithm> 
using namespace std; 
int read(){ 
    int f=1,x=0; 
    char c=getchar(); 
    while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();} 
    while('0'<=c&&c<='9') x=x*10+c-'0',c=getchar(); 
    return f*x; 
} 
#define MOD 100003 
#define MAXN 100000 
#define LL long long
#define INF 0x3f3f3f3f
int main(){
	bool flag=0;
	LL a,b,n=read(),s1=0,s2=INF;
	for(int i=1;i<=n;i++)
	{
		a=read(),b=read(),s1+=a;
		if(a>b&&s2>b) s2=b;
		if(a!=b) flag=1;
	}
	printf("%lld\n",flag?(s1-s2):0);
    return 0; 
}

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

using namespace std;

#define rep(i,n) for(int i=0;i<int(n);i++)
#define reps(i,n) for(int i=1;i<=int(n);i++)
#define sint(i) scanf("%d",&i);
#define sintt(i,j) scanf("%d%d",&i,&j);
#define sinttt(i,j,k) scanf("%d%d%d",&i,&j,&k);

#define INF 1010000000
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

int main(){
	while(1){
		int n,m;
		sintt(m,n);
		if(n==0)break;
		int hon[101];
		rep(i,n){
			sint(hon[i]);
		}
		
		int left=0;
		int right=1500000;
		
		while(1){
			double harf=(right+left)/2.0;
			
			int flg=0;
			
			int now=0;
			int cont=0;
			rep(i,n){
				if(now+hon[i]<=harf){
					now+=hon[i];
				}else{
					now=0;
					i--;
					cont++;
				}
				if(cont>=m){
					break;
				}
			}
			
			if(cont>=m){
				flg=1;
			}
			
			if(flg==1){
				left=harf+0.5;
			}else{
				right=harf;
			}
			
			if(left==right){
				printf("%d\n",left);
				break;
			}
		}
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}
 
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=std::sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}
 
long long gcd_(long long a, long long b){
  if(a<b){
    std::swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}
 
//using namespace std;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;

int main(){
  using namespace std;
  long long n;
  long long k;
  cin>>n>>k;
  int a[n];
  REP(i, n) cin>>a[i];
  
  vector<int> prev(20'0010, -1);
  long long g[n][61];
  REP(i, 2 * n){
    int ni = i % n;
    if(prev[a[ni]] < 0){
      prev[a[ni]] = i;
      continue;
    }
    
    int start = prev[a[ni]];
    if(start >= n) continue;
    g[start][0] = i - start + 1;
    prev[a[ni]] = i;
  }
  
  //REP(i, n) cout << g[i][0] << ' '; cout << endl;
  
  
  REPP(j, 60){
    REP(i, n){
      g[i][j] = g[i][j - 1];
      long long mid = i + g[i][j - 1];
      if(mid >= n * k){
        g[i][j] = n * k;
        continue;
      }
      long temp = g[(int)(mid % n)][j - 1];
      if(temp >= n * k){
        g[i][j] = n * k;
        continue;
      }
      g[i][j] += temp;
      g[i][j] = min(g[i][j], n * k);
    }
  }
  
  //REP(i, n) cout << g[i][60] << ' '; cout << endl;
  
  
  //ここでプログラムが止まらなっているっぽい
  //型をcpp_intにして解決...と思いきやメモリ確保に失敗
  //g[i][j] の取る値を制限する
  long long now = 0;
  while(now < n * k){
    long long i = now % n;
    int nj = -1;
    for(int j = 0; j <= 60; j++){
      if(now + g[i][j] < n * k){
        nj = j;
      }
    }
    if(nj < 0) break;
    now = now + g[i][nj];
  }
  
  //cout << now << endl;
  
  
  vector<bool> exist(200'010, false);
  stack<int> st;
  for(int i = (int)(now % n); i < n; i++){
    if(!exist[a[i]]){
      st.push(a[i]);
      exist[a[i]] = true;
      continue;
    }
    while(!st.empty()){
      if(st.top() == a[i]){
        st.pop();
        exist[a[i]] = false;
        break;
      }else{
        exist[st.top()] = false;
        st.pop();
      }
    }
  }
  vector<int> ans;
  while(!st.empty()){
    ans.push_back(st.top());
    st.pop();
  }
  reverse(ALL(ans));
  for(int& x: ans) cout << x << ' ';
  cout << endl; 
  
  return 0;
}


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

int main () {
  int X;
  cin >> X;
  int ans = 1;
  for(int i = 2; i <= sqrt(1000); i++) {
    for(int j = i*i; j <= X; j *= i) {
      ans = max(ans, j);
    }
  }
  cout << ans << endl;

  return 0;
}


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

using namespace std;

#define SWAP(x,y,z) {if ( y > z ) swap(y,z); if ( x > y ) swap(x,y); if (y > z) swap(y,z);}
typedef long long ll;
typedef unsigned long long ull;

double const eps = 1e-6;
double const pi = 3.1415926535;
ll const mod = 1e9+7;

ll a[100005];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    ll k;
    cin >> n >> k;
    for ( int i = 1; i <= n; i++ )
    {
        int x,y;
        cin >> x >> y;
        a[x] += y;
    }

    for ( int i = 1; i <= 100000; i++ )
    {
        if ( k-a[i] <= 0 )
        {
            cout << i << '\n';
            break;
        }
         k -= a[i];
    }
 
    return 0;
}


Measured memory_bytes: 1024
/// Bismillahir Rahmanir Rahim
/* Mohammad Morsalin
   Dept of ICE, NSTU
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define pb push_back
#define mp make_pair
#define endl "\n"
#define int long long
#define f0(n) for(int i=0;i<n;i++)
#define ms(x) memset(x,0,sizeof(x))
#define ms2d(x,m,n) memset(x, 0, sizeof(x[0][0]) * m * n)
#define uniq(vec) vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end())))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pi pair<int,int>
#define tc(t) int t;cin>>t;while(t--)
#define bits(n) __builtin_popcount(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define ins insert
#define ALL(v) v.begin(),v.end()
#define highest(x) numeric_limits<x>::max()
#define lowest(x) numeric_limits<x>::min()
#define Inf INFINITY
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define fi first
#define se second
#define PI acos(-1)
#define sz(a) (int)a.size();
#define IOS ios::sync_with_stdio(false);
using namespace std;
int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
typedef tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
const long long MOD = 1000000007;
double sq(double x) {return x*x;}
template<typename T>inline T Bigmod(T base, T power, T MOD){
    T ret=1;
    while(power)
    {
        if(power & 1)ret=(ret*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return ret;
}

bool sortinrev(const pair<int,int> &a,
               const pair<int,int> &b)
{
       return (a.first > b.first);
}
signed main()
{
    IOS
    int n;
    while(cin>>n){
        int x=n/1000;
        if(x*1000 !=n)x++;
        cout << (x*1000)-n << endl;
    }
    return 0;
}
///Alhamdulillah


Measured memory_bytes: 3640
import java.util.*;

public class Main {
		public static void main(String args[]) {
		Scanner input = new Scanner(System.in);
			int x = input.nextInt();
			int a = input.nextInt();
			int b = input.nextInt();
			if(Math.abs(x-a) < Math.abs(x-b)){
				System.out.println("A");
			}
			else{
				System.out.println("B");
			}
		}
}

Measured memory_bytes: 21716
Y = input().strip()
X = input()
X_len = len(X)
ss = 100000
for i in range(len(Y) - X_len + 1):
    s = 0
    for j in range(X_len):
        if Y[i + j] != X[j]:
            s += 1
    ss = min(ss, s)
print(ss)

Measured memory_bytes: 9048
#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 M1, D1, M2, D2;
  cin >> M1 >> D1 >> M2 >> D2;
  cout << (M1 != M2 ? "1" : "0") << endl;
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+20;
const int M=2e2+20;
ll v[N];
ll C[M][M];
//题意:n件物品,可以选a~b件,求平均值最大是多少和方法数? n<=50,vi<=1e15
//固定的k=a~b ave=sum/k ave要大 sum要最大 选最大的k个 
// 1/k*segma(vi) i=0~k-1 - 1/(k+1) segma(vi) i=0~k >=0
//所以选A个时的平均值最大;

//e.g a=2,b=4 a[i]={20,20,20,20,10} 方法数为11  
//sum/k=(sum+x)/(k+1)  x=sum/k=ave, kx=sum=segma(a[i]) 因为从大->小排序,i<A,a[i]>=x a[i]只能都等于x
//增加个数,平均值不变:只有当前A个相同 && 后面还有x=ave 
//[x,x,y,y,z..z], x>y>z,无法增加个数,则方法数为 最小数z,共有ni个,在A中有ki个,则ans=C(ni,ki) 
void init()
{
	memset(C,0,sizeof(C));
	C[0][0]=1;
	for(int i=1;i<=50;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++)
			C[i][j]=C[i-1][j-1]+C[i-1][j];
	}
}
int main()
{
	int n,A,B;
	init();
	while(cin>>n>>A>>B)
	{
		double ave=0;
		for(int i=0;i<n;i++)
			cin>>v[i];
		sort(v,v+n);
		reverse(v,v+n);//大->小
		for(int i=0;i<A;i++) 
			ave+=v[i];
		ave/=A;
		int num=0,k=0;
		for(int i=0;i<n;i++)
		{
			if(v[i]==v[A-1])
			{
				num++;
				if(i<A)
					k++;
			}
		}	
		ll ans=0; 
		if(k==A)//前A个相同,可能增加个数 
		{
			for(int i=A;i<=B;i++)
				ans+=C[num][i];
		}
		else
			ans+=C[num][k];

 		cout.precision(20);
 		cout<<fixed<<ave<<endl;
 		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 640
#include<iostream>
using namespace std;
int main(){
   long long int i,sum=0;
string s;
cin>>s;
for(i=0;i<s.size();i++){
    sum=sum+s[i]-'0';

}
if(sum%9==0)cout<<"Yes"<<endl;
else cout<<"No"<<endl;

}


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

int main(){
    ll t,n,q=1,m,k,x,y,ss=0,aa=0,b=0,c=0,d=0;
    cin>>n>>k;
    ll a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(a[i]>0)
            d=1;
        if(a[i]==0)
            b=1;
        if(a[i]<0)
            c=1;
    }

    sort(a,a+n);

    if(d==1&&c==0){
        ll i=n-1;
        while(k--){
            q*=a[i];
            q%=mod;
            i--;
        }
        if(q<0)
            q+=mod;
        cout<<q<<endl;
        return 0;
    }
    if(d==0&&c==1){
        if(k%2==1 && b==1){
            cout<<0<<endl;
            return 0;
        }
        if(k%2==1 && b==0){
            ll i=n-1;
            while(k>1){
                ll w = a[i]*a[i-1];
                w %= mod;
                q*=w;
                q%=mod;
                i-=2;
                k-=2;
            }
            if(k){
                q*=a[i];
                q%=mod;
            }
            if(q<0)
                q+=mod;
            cout<<q<<endl;
            return 0;
        }
        ll i=0;
        while(k){
            ll w = a[i]*a[i+1];
            w %= mod;
            q*=w;
            q%=mod;
            i+=2;
            k-=2;
        }
        if(q<0)
            q+=mod;
        cout<<q<<endl;
        return 0;
    }

    if(b==1&&c==0&&d==0){
        cout<<0<<endl;
        return 0;
    }

    ll i=0,j=n-1;
    while(k>1){
        ll m1 = a[i]*a[i+1];
        ll m2 = a[j]*a[j-1];
        if(m2>m1){
            m2%=mod;
            q*=m2;
            j-=2;
        }else{
            m1 %= mod;
            q*=m1;
            i+=2;
        }
        q %= mod;
        k-=2;
    }
    if(k){
        q*=a[j];
        q%=mod;
    }
    if(q<0)
        q+=mod;
    cout<<q<<endl;
    return 0;
}







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

void solve()
{
  int r,g,b;
  cin >> r >> g >> b;

  if((r*100 + g*10 + b) % 4 == 0) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}

int main(){cin.tie(0);ios_base::sync_with_stdio(false);solve();return 0;}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
	public static void main(String[] args) throws IOException {
		MScanner sc = new MScanner(System.in);
		PrintWriter pw=new PrintWriter(System.out);
		int n=sc.nextInt();int q=sc.nextInt();
		int[]pref=new int[n];
		char[]in=sc.nextLine().toCharArray();
		pref[0]=0;
		for(int i=1;i<n;i++) {
			if(in[i]=='C' && in[i-1]=='A')
				pref[i]=pref[i-1]+1;
			else {
				pref[i]=pref[i-1];
			}
		}
		while(q-->0) {
			int l=sc.nextInt()-1;int r=sc.nextInt()-1;
			pw.println(pref[r]-pref[l]);
		}
		pw.flush();
 
	}
    static class MScanner {
		StringTokenizer st;
		BufferedReader br;
 
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
 
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
 
		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}

Measured memory_bytes: 40696
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i=0;i < (int)(n);i++)


int main(){
   int n;
   cin >> n;
   int ans=1;
   if (n == 1) {
      cout << 1 << endl;
      return 0;
   }
   for (int i=2;i < 100;i++){
      int tmp = i*i;
      while (tmp <= 1000){
         if (tmp <= n){
            ans=max(ans,tmp);
         }
         tmp*=i;
      }
   }
   cout << ans << endl;
   return 0;
}

Measured memory_bytes: 256
from math import sqrt
l = [-1]+[0]*10**4
n = int(input())
for i in range(1,int(sqrt(n))+2):
    for j in range(1,int(sqrt(n))+2):
        for k in range(1,int(sqrt(n))+2):
            ans = i**2+j**2+k**2+i*j+j*k+k*i
            if ans <= 10**4:
                l[ans] += 1
for i in range(1,n+1):
    print(l[i])

Measured memory_bytes: 69292
#[allow(unused_imports)]
use std::io;
use std::io::stdin;

fn read_line_as_vec() -> Vec<String> {
    let mut s = String::new();
    stdin().read_line(&mut s).expect("");
    s.split(' ').map(|x| x.to_string()).collect::<Vec<String>>()
}

fn main() {
    let nm = read_line_as_vec();
    let n: i32 = nm[0].trim().parse().expect("n");
    let m: i32 = nm[1].trim().parse().expect("m");
    let mut students = Vec::<(i32,i32)>::new();
    for _ in 0..n {
        let ab = read_line_as_vec();
        let a: i32 = ab[0].trim().parse().expect("");
        let b: i32 = ab[1].trim().parse().expect("");
        students.push((a, b));
    }
    let students = students;
    let mut points = Vec::<(i32,i32)>::new();
    for _ in 0..m {
        let cd = read_line_as_vec();
        let c: i32 = cd[0].trim().parse().expect("");
        let d: i32 = cd[1].trim().parse().expect("");
        points.push((c, d));
    }
    let points = points;
    for (a,b) in students {
        let mut argmin_cp = 0;
        let mut min_dist: i32 = 1_000_000_000;
        for (i,&(c,d)) in points.iter().enumerate() {
            let dist: i32 = (c-a).abs() + (d-b).abs();
            if dist < min_dist {
                min_dist = dist;
                argmin_cp = i + 1;
            }
        }
        println!("{}", argmin_cp);
    }
}


Measured memory_bytes: 4352
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <numeric>
#include <functional>
#include <map>
#include <set>
#define Rep(i, n) for(int i=0;i<n;++i)
#define rep(i, n) for(int i=1;i<=n;++i)
#define ll long long
#define INF 100000000
#define MOD 1000000007
#define PI 3.14159265359
#define All(a) (a).begin(), (a).end()

using namespace std;
using P = pair<ll int, ll int>;
 
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

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 N;
vector<int> d;

int main () {
  cin >> N;

  Rep(i, N) {
    int tmp;
    cin >> tmp;
    d.push_back(tmp);
  }

  sort(All(d));

  int min_num = d[N/2-1] + 1;
  int max_num = d[N/2];

  cout << max_num - min_num + 1 << "\n";
}


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

using namespace std;

int main() {
    int h, w;
    cin >> h >> w;
    int field[h][w];
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> field[i][j];
        }
    }
    int ans = 1000000000;
    for (int north = 0; north < h; ++north) {
        for (int west = 0; west < w; ++west) {
            int res = 0;
            for (int i = 0; i < h; ++i) {
                for (int j = 0; j < w; ++j) {
                    res += min(abs(north - i), abs(west - j)) * field[i][j];
                }
            }
            ans = min(ans, res);
        }
    }
    cout << ans << '\n';
}


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

const int MAX_N = 110000;

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

  vector<int> dp(MAX_N, n);  // INF の気持ち
  dp[0] = 0;

  // 貰う DP --- dp[i] に遷移を集める
  for (int i = 1; i <= n; i++) {
    // 1, 6, 6^2, ..., を試す (i を超えない範囲で)
    for (int pow6 = 1; pow6 <= i; pow6 *= 6)
      dp[i] = min(dp[i], dp[i - pow6] + 1);

    // 1, 9, 9^2, ..., を試す (i を超えない範囲で)
    for (int pow9 = 1; pow9 <= i; pow9 *= 9)
      dp[i] = min(dp[i], dp[i - pow9] + 1);
  }

  cout << dp[n] << endl;
}


Measured memory_bytes: 640
n=int(input())
word=[]
for i in range(n):
    word.append(input())
 
 
cnt=0
for i in range (n-1):
    if word[i][len(word[i]) - 1] != word[i + 1][0]:
        cnt += 1
        print("No")
        break
    for j in range (i):
     if word[i+1]==word[j]:
        cnt+=1
        print ("No")
        break
 
if cnt==0:
    print("Yes")

Measured memory_bytes: 3064
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int n,p,q=0;
        n=scan.nextInt();
        int[] sort=new int[n];
        for(int i=0; i<n; i++){
            sort[i]=scan.nextInt();
        }
        
        for(int i=0; i<n-1; i++){
            for(int j=0; j<n-1; j++){
                if(sort[j]>sort[j+1]){
                    sort[j]^=sort[j+1];
                    sort[j+1]^=sort[j];
                    sort[j]^=sort[j+1];
                    q++;
                }
            }
        }
        //System.out.println(Arrays.toString(sort));
        for(int i=0; i<n; i++){
            System.out.print(sort[i]);
            if(i!=n-1)
                System.out.print(" ");
        }
        System.out.println();
        System.out.println(q);
    }
}


Measured memory_bytes: 26268
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0, max_i = (n); i < max_i; i++)
#define REPI(i, a, b) for (int i = (a), max_i = (b); i < max_i; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define fi first
#define se second
#define int long long
using namespace std;
using ll = long long;
using II = pair<int, int>; using VII = vector<II>; using VVII = vector<VII>;
using VI = vector<int>; using VVI = vector<VI>; using VVVI = vector<VVI>;
template <class T = int> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template <class T = int> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
template <class T> ostream& operator<<(ostream &s, const vector<T>& d) { REP (i, d.size()) s << d[i] << (i == d.size() - 1 ? "" : " "); return s; }
template <class T> ostream& operator<<(ostream &s, const vector<vector<T>>& d) { REP (i, d.size()) s << d[i] << (i == d.size() - 1 ? "" : "\n"); return s; }
template <class T, class S> ostream& operator<<(ostream &s, const pair<T, S>& p) { s << "{" << p.first << ", " << p.second << "}"; return s; }
template <class T, class S> ostream& operator<<(ostream& s, const map<T, S> m) { for (auto it = m.begin(); it != m.end(); it++) { s << *it << (next(it) == m.end() ? "" : "\n"); } return s; }
#ifdef _MY_DEBUG
  #define dump(...) cerr << "/* " << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << endl, dump_func(__VA_ARGS__), cerr << "*/\n\n";
#else
  #define dump(...)
#endif
void dump_func() { cerr << endl; }
template <class Head, class... Tail> void dump_func(Head&& h, Tail&&... t) { cerr << h << (sizeof...(Tail) == 0 ? "" : ", "), dump_func(forward<Tail>(t)...); }
struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); } } fast;
constexpr int MOD = 1e9 + 7;

signed main() {
  int n, K; cin >> n >> K;
  VI a(n);
  REP (i, n) cin >> a[i];
  VI dp(K + 1);
  REP (i, K + 1) {
    REP (j, n) {
      if (i - a[j] >= 0 && dp[i - a[j]] == 0) dp[i] = true;
    }
  }
  cout << (dp[K] ? "First" : "Second") << endl;
}


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

int main() {
  int64_t n,k;
  cin >> n >> k;
  
    if( n % k == 0 )
      cout << 0 << endl;
    else if(n < k)
      cout << min( abs(n-k),n ) << endl;
    else {
      n %= k;
      cout << min( abs(n-k),n ) << endl; 
    }
}

Measured memory_bytes: 3556