akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)          (x).begin(), (x).end()
#define rep(i, s, n)    for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define VAR(type, ...)  type __VA_ARGS__; read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U> inline bool chmax(T &a, const U &b) { return b > a && (a = b, true); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return b < a && (a = b, true); }
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> makeV(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeV(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeV<T>(initValue, args...))>(sz, makeV<T>(initValue, args...));
}

template <class T>
inline istream& operator>> (istream &is, vector<T> &vec) {
    for (auto &e : vec) is >> e;
    return is;
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail&... tail) { cin >> head; read(tail...); }

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream& operator<< (ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = { " ", "" };
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}

template <class Container>
struct Rev {
    Container &x_;
    inline Rev(Container &x): x_(x) {}
    inline auto begin() { return rbegin(x_); }
    inline auto end() { return rend(x_); }
};
// }}} End Header

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

    VAR(int, N);
    vector<pii> ps(N);
    rep(i, 0, N) {
        int x, y;
        read(x, y);
        ps[i] = { x, y };
    }

    sort(all(ps));
    long double sum = 0;
    int cnt = 0;
    do {
        rep(i, 1, N) {
            sum += hypot(ps[i].first - ps[i - 1].first, ps[i].second  - ps[i-1].second);
        }
        ++cnt;
    } while (next_permutation(all(ps)));

    cout << fixed << setprecision(12);
    print(sum / cnt);

    return 0;
}


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




int main(){
    int n, a, b;
    cin >> n >> a >> b;
    int d=abs(b-a);
    if(d%2==0)cout << "Alice" << endl;
    else cout << "Borys" << endl;   
}


Measured memory_bytes: 3536
// #include <bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define exf(x)	 for(auto&& tmp : x) { cout << tmp << endl; }	// 拡張for
#define PI 3.14159265358979323846264338327950288
#define testP	 cout << "------------------ test ------------------" << endl;	// 動作確認テスト
#define testX(x) cout << "testout : " << x << endl;	// テストアウト
const int MOD{ int(1e9 + 7) };	// = 1000000007
const int inf{ 2100000000 };	// = 2100000000 (MAX:2147483647)
typedef long long ll;
using namespace std;

// ------------------ ベクター表示 ------------------ //
void printVec(vector<int>& vec) {
	cout << "";
	for (auto it = vec.begin(); it != vec.end(); it++) cout << *it << " ";
	cout << endl;
}

// ------------------ ベクター合計 ------------------ //
int sumVec(vector<int> v) {
	int sum = 0;
	for (size_t i = 0; i < v.size(); i++) sum += v[i];
	return sum;
}

// -------------------------------------------------- //
// ------------------ ここから本編 ------------------ //
// -------------------------------------------------- //

int main(void) {

	ll N, M, K;
	cin >> N >> M >> K;

	vector<ll>A(N + 1, 0), B(M + 1, 0);
	for (int i = 1; i <= N; i++) {
		int a; cin >> a;
		A[i] = A[i - 1] + a;
	}
	for (int i = 1; i <= M; i++) {
		int b; cin >> b;
		B[i] = B[i - 1] + b;
	}

	ll ans = 0, best = M;
	for (ll i = 0; i <= N; i++) {
		if (A[i] > K) break;
		while (B[best] + A[i] > K) best--;
		ans = max(ans, i + best);
	}

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


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

using namespace std;

#define sz(x) ((int) ((x).size()))
typedef long long ll;
typedef long double ld;

int n, a[50][50];
ll dp[50][50][50], cnt[50][50], ddp[50][50][50][50];

ll getNumWays(int al, int ar, int bl, int br) {
  if (ar < al && br < bl)
    return 1;
  if (ar < al || br < bl)
    return 0;
  if ((ar - al + 1) % 2 != (br - bl + 1) % 2)
    return 0;
  if (ddp[al][ar][bl][br])
    return ddp[al][ar][bl][br] - 1;
  for (int aj = al; aj <= ar; aj++)
    for (int ak = al; ak <= aj; ak++)
      if (dp[al][aj][ak])
        for (int bi = br; bi >= bl; bi--)
          for (int bk = br; bk >= bi; bk--)
            if (a[ak][bk] && dp[bi][br][bk])
              ddp[al][ar][bl][br] += getNumWays(aj + 1, ar, bl, bi - 1) * dp[al][aj][ak] * dp[bi][br][bk];
  ddp[al][ar][bl][br]++;
  return ddp[al][ar][bl][br] - 1;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(10);
  cin >> n;
  char c;
  for (int i = 0; i < 2 * n; i++)
    for (int j = 0; j < 2 * n; j++)
      cin >> c, a[i][j] = c == '1';
  for (int l = 0; l < 2 * n; l++)
    for (int i = 0; i + l < 2 * n; i++) {
      int j = i + l;
      for (int k = i; k <= j; k++)
        dp[i][j][k] = getNumWays(i, k - 1, k + 1, j);//, cerr << i << " " << j << " " << k << " " << dp[i][j][k] << "\n";
    }
  ll r = 0;
  for (int i = 1; i < 2 * n; i++)
    r += a[0][i] * getNumWays(1, i - 1, i + 1, 2 * n - 1);
  cout << r << "\n";
}


Measured memory_bytes: 39680
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
const ll mod = 1e9+7;
const ll INF = 2e9;
const double PI = 3.1415926535;


int main(void){
    ll n, m; cin >> n >> m;
    priority_queue <P> can;
    priority_queue<P, vector<P>, greater<P>> day;
    for(int i = 0;i < n;i++){
        ll a, b; scanf("%lld %lld", &a, &b);
        P p; p.first = a; p.second = b;
        day.push(p);
    }
    ll ans = 0;
    ll d = 1;
    while(d <= m){
        //cout << "A" << endl;
        while(!day.empty()){
            P p = day.top();
            if(p.first <= d){
                P q; q.second = p.first; q.first = p.second;
                can.push(q); day.pop();
            }else break;
        }
        //cout << can.size() << endl;
        if(!can.empty()){
            //cout << "B" << endl;
            P p = can.top();
            ans += p.first;
            can.pop();
        }
        d++;
    }
    cout << ans << endl;
	return 0;
}

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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

int main()
{
    lint n,k;cin >> n>>k;
    vector<lint> v(n);
    REP(i, n) { cin >> v[i]; }
    sort(ALL(v));

    lint ans = 200000000000;
    REP(i,n-k+1){
        lint l = v[i], r = v[i + k - 1];
        ans = min(ans, r - l);
    }


    cout << ans <<"\n";

    return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

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

                int X = scan.nextInt();
                int Y = scan.nextInt();

                scan.close();

                boolean isExist = false;


                if (Y%2 == 0 && -X + Y/2 >= 0 && 2*X - Y/2 >= 0) {
                	isExist = true;
                }

                if (isExist) {
                	System.out.println("Yes");
                } else {
                	System.out.println("No");
                }

        }

}

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

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
#define loop(i,a,b) for(int i=(a);i<int(b);i++)
#define rep(i,b) loop(i,0,b)

pair<int,int> find(int n, vvi const& v){
	rep(i,v.size())rep(j,v[i].size()){
		if(v[i][j]==n)return make_pair(i,j);
	}
	return make_pair(-1,-1);
}

int main(){
	int m;
	while(cin>>m && m){
		int a,b;
		vvi ps(m);
		rep(i,m)ps[i]={i+1};
		while(cin>>a>>b && a|b){
			auto ia=find(a,ps), ib=find(b,ps);
			vi &A=ps[ia.first], &B=ps[ib.first];
			if(b==0){
				if(ia.second==0) continue;
				while(1){
					int top=A.back();
					ps.push_back({top});
					A.pop_back();
					if(top==a)break;
				}
			}else if(ia.first==ib.first){
				if(ia.second < ib.second){
					ps.push_back({b,a});
					while(1){
						int top=A.back();
						if(top!=a && top!=b){
							ps.push_back({top});
						}
						A.pop_back();
						if(top==a) break;
					}
				}
			}else{
				while(1){
					int top=A.back();
					A.pop_back();
					if(top==a){
						B.push_back(a);
						break;
					}else{
						ps.push_back({top});
					}
				} 
			}
			ps.erase(remove_if(ps.begin(),ps.end(),[](const vi& v){return v.size()==0; }),ps.end());
		}
		vi ans;
		rep(i,ps.size())if(ps[i].size())ans.push_back(ps[i].size());
		sort(ans.begin(),ans.end());
		rep(i,ans.size())cout<<ans[i]<<endl;
		cout<<"end"<<endl;
	}
}

Measured memory_bytes: 1228
#include<bits/stdc++.h>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;

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

    int n;
    cin>>n;

    vector<int> h(n+1);
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }

    vector<int> c(n+1);
    c[1]=0;
    c[2]=abs(h[1]-h[2]);

    for(int i=3;i<=n;i++){
        c[i]=min(c[i-2]+abs(h[i]-h[i-2]),c[i-1]+abs(h[i]-h[i-1]));
    }

    cout<<c[n]<<"\n";
    return 0;
}


Measured memory_bytes: 3952
#include<iostream>
#include<cassert>
#include<stdexcept>
#include<utility>
#include<functional>
#include<numeric>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<array>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<complex>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<bitset>
#include<memory>
using namespace std;
using ll=long long;

const ll MOD=1e9+7;
int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    ll res=1;
    int cnt=0;
    for(int i=0;i<2*n;i++){
        bool isLef;
        if(s[i]=='W'){
            isLef=(i%2==0);
        }
        else{
            isLef=(i%2==1);
        }
        if(isLef){
            res=res*cnt%MOD;
            cnt--;
        }
        else{
            cnt++;
        }
    }
    if(cnt!=0) res=0;
    for(int i=0;i<n;i++) res=res*(i+1)%MOD;
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<string>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<queue>
#include<functional>
#include<iso646.h>
#include<bitset>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<long long> vll;
typedef pair<long long, long long> pll;

const double INF = 1e16;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;

bool comp_p(const pll& l, const pll& r) {
	return l.second < r.second;
}

int main() {
	ll N;
	cin >> N;
	ll i, j;
	vector<pll> X;
	ll s = 0;
	for (i = 0; i < N; i++) {
		ll a, b;
		cin >> a >> b;
		s += a;
		X.push_back(pll(a, b));
	}
	sort(X.begin(), X.end(), comp_p);

	bool ans = true;
	ll now = X[N - 1].second;
	for (i = N - 1; i >= 0; i--) {
		ll a = X[i].first;
		ll b = X[i].second;
		now = min(now, b);
		ll limit = b;
		if (s > now) {
			ans = false;
			break;
		}
		s -= a;
		now -= a;
	}
	if (ans) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 6556
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = 5;
		int na[] = new int[n];
		for (int i = 0; i < n; i++)
		{
			na[i] = sc.nextInt();
		}
		int k = sc.nextInt();
		if (na[4] - na[0] > k)
		{
			System.out.println(":(");
		}
		else
		{
			System.out.println("Yay!");
		}
	}
}

Measured memory_bytes: 20948
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<list>

using namespace std;
using ll = long long;

const ll MOD = 1e9+7;
const ll MAX_N = 1e5+1;
ll dp[MAX_N] = {};

int main(){
    int n,m;
    cin>>n>>m;
    
    bool broken[n+1];
    for(int i=0;i<=n;i++) broken[i] = false;

    int a[m];
    for(int i=0;i<m;i++){
        cin>>a[i];
        broken[a[i]] = true;
    }

    dp[0] = 1;
    if(broken[1] == true) dp[1] = 0;
    else dp[1] = 1;

    for(int i=2;i<=n;i++){
        dp[i] = (dp[i-1] + dp[i-2]) % MOD;
        if(broken[i] == true) dp[i] = 0;
    }

    ll ans = dp[n] % MOD;
    cout<<ans<<endl;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC target("sse4")

typedef double LD;
typedef long long ll;
typedef pair<ll, ll> PII;
typedef pair<LD, LD> PDD;
typedef vector<ll> VI;
typedef vector<PII> VPII;
typedef vector<VI> VVI;
#define MP make_pair
#define	pb push_back
#define x first
#define y second
#define next fake_next

#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(ll i = (b) - 1; i >= (a); --i)
#define REP(i, t) FOR(i, 0, t)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (ll)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define count jaskdasbj
const LD PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000;

int main()
{
	//freopen("input.txt" , "r" , stdin);
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	int back = -1;
	int cnt = 0;
	int ans = 0;
	while(n--)
	{
		int x;
		cin >> x;
		//cout << ans << endl;
		if(back == -1)
		{
			cnt = 1;
			back = x;
		}
		else if(back == x)
		{
			cnt++;
		}
		else
		{

			ans += cnt / 2;
			back = x;
			cnt = 1;
		}
	}
	ans += cnt / 2;
	cout << ans;


	return 0;
}


Measured memory_bytes: 256
#if 1
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <set>
#include <numeric>
#include <cassert>

using namespace std;
#define int long long
#define uint unsigned long long
constexpr int MOD = 1000000007;
constexpr int INF = 1145141919810;

#define LOADVEC(type,name,N) std::vector<type>name(N); \
for (int nnn = 0; nnn < N; ++nnn) { \
	cin >> name[nnn]; \
}

#define LOADVEC2(type,name0,name1,N) std::vector<type>name0(N),name1(N); \
for (int nnn = 0; nnn < N; ++nnn) { \
	cin >> name0[nnn];cin >> name1[nnn]; \
}

#define LOAD(type,name) type name; \
cin >> name;


void proc();

signed main() {
	ios::sync_with_stdio(false);
	proc();
	return 0;
}

/*
--------------------------------------------------------
--------------------------------------------------------
---------------    template      ----------------------
--------------------------------------------------------
--------------------------------------------------------
*/

void proc() {
	LOAD(int, N);
	LOADVEC(int, a, N - 1);
	std::vector<unordered_set<int>>childs(N);
	std::vector<unordered_set<int>>childs2;
	std::vector<int> depth(N, -1);
	std::vector<int>stack;
	for (int i = 0; i < N - 1; ++i) {
		childs[a[i] - 1].insert(1 + i);
	}
	childs2 = childs;
	//
	stack.reserve(N + 1);
	stack.push_back(0);
	depth[0] = -2;
	while (!stack.empty()) {
		int v = stack.back();
		bool pushed = false;
		for (auto child : childs2[v]) {
			if (depth[child] == -1) {
				depth[child] = -2;
				stack.push_back(child);
				childs2[v].erase(child);
				pushed = true;
				break;
			}
		}
		if (!pushed) {
			std::vector<int>childsDepth;
			childsDepth.reserve(childs[v].size());
			for (auto &child : childs[v]) {
				childsDepth.push_back(depth[child]);
			}
			std::sort(childsDepth.begin(), childsDepth.end(), std::greater<int>());
			//
			int maxDepth = 0;
			for (int i = 0; i < childsDepth.size(); ++i) {
				int oneDepth = childsDepth[i] + i + 1;
				if (maxDepth < oneDepth)maxDepth = oneDepth;
			}
			depth[v] = maxDepth;
			stack.pop_back();
		}
	}
	cout << depth[0];
}

#endif


Measured memory_bytes: 26112
//#include <cmath>
//#include <cstdio>
//#include <vector>
//#include <map>
//#include <iostream>
//#include <algorithm>
//#include <set>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pil = pair<int,ll>;
using vi = vector<int>;
using vb = vector<bool>;
using pli = pair<ll,int>; 		
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
int INF = 1e9+7;
const int N = 100010;

int dp[N][3];

void solve(){
	int n;
	scanf("%d",&n);
	
	//dp[i][j] -> max happiness get if on ithe day j th task is done
	
	for(int i =0; i < n; ++i){
		int arr[3];
		scanf("%d%d%d",&arr[0],&arr[1],&arr[2]);
		if(i == 0){
			dp[i][0] = arr[0];
			dp[i][1] = arr[1];
			dp[i][2] = arr[2];
		}
		else{
			for(int pre: {0,1,2}){
				for(int curr : {0,1,2}){
					if(pre != curr){
						dp[i][curr] = max(dp[i][curr], dp[i-1][pre] + arr[curr]);
					}
				}
			}
		}
	}
	printf("%d\n", max({dp[n-1][0],dp[n-1][1],dp[n-1][2]}));
	
	
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t = 1;
	//cin >> t;
	//scanf("%d",&t);
	while(t--){
		solve();
	}
		
			
}


Measured memory_bytes: 5020
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr double eps = 1e-9;
constexpr ll MOD = 1000000007LL;
template <typename T>
bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T>
bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
};
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for(int i = 0; i < v.size(); i++) {
        os << v[i] << (i + 1 == v.size() ? "\n" : " ");
    }
    return os;
}
template <typename T>
vector<T> make_v(size_t a) {
    return vector<T>(a);
}
template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T& t, const V& v) {
    t = v;
}
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T& t, const V& v) {
    for(auto& e : t) {
        fill_v(e, v);
    }
};
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    if(s[0] == s[1] || s[1] == s[2] || s[2] == s[3]) {
        cout << "Bad" << endl;
    } else {
        cout << "Good" << endl;
    }
}


Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7



def f(ai, ki):
    if ai < ki: return 0
    elif ai % ki == 0 :return ai // ki
    d = ai // ki + 1
    if ai % ki % d:
        return f(ai - (ai % ki // d + 1) * d, ki)
    return f(ai - ai % k, k)


n = I()
ret = 0
for i in range(n):
    a, k = LI()
    ret ^= f(a, k)

print("Takahashi" if ret else "Aoki")


Measured memory_bytes: 114872
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    MAX = 500000
    SENTINEL = 2000000000

    L = [None]*(MAX//2+2)
    R = [None]*(MAX//2+2)
    cnt = 0

    def merge(A, n ,left, mid, right, cnt):
        n1 = mid - left
        n2 = right - mid
        for i in range(n1):
            L[i] = A[left + i]
        for i in range(n2):
            R[i] = A[mid + i]
        L[n1] = R[n2] = SENTINEL
        i, j = 0, 0
        for k in range(left, right):
            cnt += 1
            if L[i] <= R[j]:
                A[k] = L[i]
                i += 1
            else:
                A[k] = R[j]
                j += 1
        return cnt

    def mergeSort(A, n, left, right, cnt):
        if left+1 < right:
            mid = (left + right)//2
            cnt = mergeSort(A, n, left, mid, cnt)
            cnt = mergeSort(A, n, mid, right, cnt)
            cnt = merge(A, n, left, mid, right, cnt)
        return cnt

    n = int(input())

    A = list(map(int, input().split()))

    cnt = mergeSort(A, n, 0, n, cnt)

    print(' '.join(map(str, A)))
    print(cnt)



Measured memory_bytes: 70584
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s, t;
    cin >> s >> t;
    int m = sz(s);
    int n = sz(t);
    vvi dp(m+1, vi(n+1, 0));
    vvi prev(m+1, vi(n+1, 0));
    rep(i, m) rep(j, n) {
        if (chmax(dp[i+1][j+1], dp[i][j+1])) prev[i+1][j+1] = 0;
        if (chmax(dp[i+1][j+1], dp[i+1][j])) prev[i+1][j+1] = 1;
        if (s[i] == t[j]) {
            chmax(dp[i+1][j+1], dp[i][j] + 1);
            prev[i+1][j+1] = 2;
        }
    }
    string ans = "";
    for (int i = m, j = n; i != 0 && j != 0; ) {
        if (prev[i][j] == 0) i--;
        else if (prev[i][j] == 1) j--;
        else {
            i--;
            j--;
            ans += s[i];
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
}

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

#define trace(...) __f( #__VA_ARGS__ , __VA_ARGS__ )
template <typename Arg1>
void __f( const char* name , Arg1&& arg1 ) {
        cerr << name << " : " << arg1 << "\n";
}
template <typename Arg1, typename... Args>
void __f( const char* na , Arg1&& arg1 , Args&&... args ) {
        const char* c = strchr( na + 1 , ',' );
        cerr.write( na , c - na ) << " : " << arg1 << " , ";
        __f( c + 1 , args... );
}
#define endl "\n"
#define all(V) V.begin(),V.end()
#define Unique(V) sort(all(V)),V.erase(unique(all(V)),V.end())
#define IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long int LL;
typedef pair <int,int> pii;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const double EPS = 1e-9;
const double PI = acos(-1.0);
const long long INF = 1e18;
const int N = 1e5 + 5;

int main( ) {
        IO;
        #ifdef LOCAL
            //freopen( "input.txt" , "r" , stdin );
        #endif // LOCAL
        string s;
        cin >> s;
        int ans = 0;
        for( int i = 1; i < s.size(); i++ ) {
                if( s[i] == s[i - 1] ) {
                        if( s[i] == '1' ) s[i] = '0';
                        else s[i] = '1';
                        ans++;
                }
        }
        cout << ans << endl;
        return 0;
}











Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define int long long int
mt19937 rng(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int N=3005;
#define M 998244353
#define double long double
#define BINF 10000000000001
#define init(arr,val) memset(arr,val,sizeof(arr))
#define MAXN 5000004
#define deb(x) cout << #x << " " << x << "\n";
const int LG = 22;

bool f(string s){
    int l = s.length();
    for(int i = 0; i < l / 2; i++){
        if(s[i] != s[l - i - 1])
            return false;
    }
    return true;
}

#undef int 
int main() {
#define int long long int
ios_base::sync_with_stdio(false); 
cin.tie(0); 
cout.tie(0);



    int x, y;
    cin >> x >> y;
    cout << (x * (x - 1)) / 2 + (y * (y - 1)) / 2 << endl;
    
    

return 0;  
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int A,B;
    cin >> A >> B;
    cout << A - B + 1 << endl;
}

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

int main() {
    int H, W; cin >> H >> W;
    vector<vector<char>> A(H+2, vector<char>(W+2, '.'));
    for(int i=1; i<H+1; i++){
        for(int j=1; j<W+1; j++){
            cin >> A.at(i).at(j);
        }
    }
    vector<vector<int>> used(H+2, vector<int>(W+2, -1));

    queue<int> quex;
    queue<int> quey;
    quex.push(1);
    quey.push(1);
    used.at(1).at(1) = 0;

    while(!quex.empty() && !quey.empty()){        
        int x = quex.front();
        int y = quey.front();
        quex.pop();
        quey.pop();

        if(A.at(y).at(x+1) == '#' && A.at(y+1).at(x) == '#'){
            cout << "Impossible" << endl;
            return 0;
        }

        if(A.at(y).at(x-1) == '#' && used.at(y).at(x-1) == -1){
            break;
        }

        if(A.at(y-1).at(x) == '#' && used.at(y-1).at(x) == -1){
            //cout << x << y << endl; 
            break;
        }        

        if(A.at(y).at(x+1) == '#' && used.at(y).at(x+1) == -1){
            quex.push(x+1);
            quey.push(y);
            used.at(y).at(x+1) = used.at(y).at(x) + 1;
        }
        else if(A.at(y+1).at(x) == '#' && used.at(y+1).at(x) == -1){
            quex.push(x);
            quey.push(y+1);
            used.at(y+1).at(x) = used.at(y).at(x) + 1;
        }

        if(x == W && y == H && quex.empty() && quey.empty()){
            cout << "Possible" << endl;
            return 0;
        }

    }

    cout << "Impossible" << endl;

}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using ll = long long int;
using ull = long long unsigned int;
using Int = long long int;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する
class Solve {
public:
    void solve() {
        int N, K;
        cin >> N >> K;
        int B = N / 2 + (N % 2);
        if (B >= K) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }


    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    Solve().solve();


    return 0;
}


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

#define PI 3.14159265358979323846264338327950L

int main() {
  int a, b, h, m;

  cin >> a >> b >> h >> m;
  long double thetaa = 2 * M_PI * ((long double)h * 60 + m) / 720;
  long double thetab = 2 * M_PI * (long double)m / 60;

  long double theta = thetab - thetaa;

  // double theta = thetaa - thetab;
  long double c = a * a + b * b - 2 * a * b * cosl(theta);
  c = sqrtl(c);

  cout << setprecision(20) << c << endl;
  return 0;
}

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

int blocks[1000001], n;


void update()
{
  for(int i = 0; i < n; i++)
    blocks[i]--;
  blocks[n++] = n;
  int m = 0;
  for(int i = 0; i < n; i++)
  {
    if(blocks[i] == 0)
    {
      m++;
    }
    else
      blocks[i - m] = blocks[i];
  }
  n -= m;
}

bool check()
{
  for(int i = 0; i < n; i++)
  {
    if(blocks[i] != i + 1)
      return false;
  }
  return true;
}

int main()
{
  while(true)
  {
    cin >> n;
    if(!n)
      break;
    for(int i = 0; i < n; i++)
      cin >> blocks[i];
    for(int i = 0; i <= 10000; i++)
    {
      if(check())
      {
        cout << i << endl;
        goto success;
      }
      update();
    }
    cout << -1 << endl;
success:;
  }
}

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

typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)

const ll MOD = 1e9+7;

inline void in() {}
template<class T, class... Ts>
inline void in(T& x, Ts&... xs) {
	int c, s=0; x=0;
	while (c=getchar(), c!='-'&&(c<'0'||c>'9'));
	if (c=='-') s=1, c=getchar();
	do x=x*10+(c-'0'); while (c=getchar(), c>='0'&&c<='9');
	if (s) x=-x;
	in(xs...);
}
inline void ins(char *s) {
    char c; while(c=getchar(), c<33); do *s++=c; while(c=getchar(), c>32); *s=0;
}


#define N 10000
int segtree[N * 2];

void modify(int i, int v) {
	for (segtree[i += N] = v; i > 1; i /= 2)
		segtree[i / 2] = min(segtree[i], segtree[i ^ 1]);
}

int query(int l, int r) { // [l, r)
	int ans = INT_MAX;
	for (l += N, r += N+1; l < r; l /= 2, r /= 2) {
		if (l % 2 == 1) ans = min(segtree[l++], ans);
		if (r % 2 == 1) ans = min(ans, segtree[--r]);
	}
	return ans;
}

int a[4000];
int main() {
	int n,x;
	in(n,x);
	rep(i,0,n)in(a[i]),a[i+n]=a[i],modify(i,a[i]),modify(i+n,a[i]);
	ll ans=LLONG_MAX;
	rep(k,0,n) {
		ll t=k;t*=x;
		rep(i,n,2*n) {
			t+=query(i-k,i);
		}
		ans=min(ans,t);
	}
	printf("%lld\n",ans);
}


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

#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define repi(i,a,b) for(int i = (a); i < (b); i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

const int dx[]={0,1,0,-1};
const int dy[]={-1,0,1,0};
//int board[120][120];
int main(){
	int n,m;
	while(cin>>m>>n,n||m){
		int dir =0;
		int posx,posy;
		posx =posy=1;
		//memset(board, 0, sizeof(board));
		int nx,ny;
		nx=ny=1;
		while(true){
			//cout <<dir<<" "<<posx<<" "<<posy<<endl;
			string str;
			cin>>str;
			if(str=="FORWARD"){
				int d;
				cin>>d;
				if(dir==0){
					nx =posx;
					ny =min(posy+d,n); 
				}else if(dir==1){
					nx =min(posx+d,m);
					ny =posy;
				}else if(dir==2){
					nx =posx;
					ny =max(posy-d,1);
				}else if(dir==3){
					nx =max(posx-d,1);
					ny =posy;
				}
			}else if(str=="BACKWARD"){
				int d;
				cin>>d;
				if(dir==0){
					nx =posx;
					ny =max(posy-d,1); 
				}else if(dir==1){
					nx =max(posx-d,1);
					ny =posy;
				}else if(dir==2){
					nx =posx;
					ny =min(posy+d,n);
				}else if(dir==3){
					nx =min(posx+d,m);
					ny =posy;
				}
			}else if(str=="RIGHT"){
				dir =(dir+1)%4;
				nx =posx;
				ny =posy;
			}else if(str=="LEFT"){
				dir =(dir-1);
				if(dir<0){
					dir =3;
				}
				nx =posx;
				ny =posy;
			}else if(str=="STOP"){
				break;
			}
			posx =nx;
			posy =ny;
		}
		cout <<posx<<" "<<posy<<endl;
	}
	return 0;
}

Measured memory_bytes: 1216
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back 
#define mp make_pair
#define fr first
#define sc second
#define Rep(i,n) for(int i=0;i<(n);i++)
#define All(v) v.begin(),v.end()
typedef pair<int, int> Pii; typedef pair<int, Pii> Pip;
const int INF = 1107110711071107;

main()
{
  double R1, R2;
  cin >> R1 >> R2;
  printf("%.7lf\n", R1*R2 / (R1+R2));
  
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
int main()
{
    ll h,n;
    cin>>h>>n;
    ll a[n],sum=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }    
    if(sum>=h)
    cout<<"Yes";
    else
    cout<<"No";
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
const long long MOD = 1000000007LL;
const string alpha = "abcdefghijklmnopqrstuvwxyz";
const long long Mod = 1000003LL;
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
long long poww(long long x,long long n,long long mod){
    long long ans = 1;
    while(n>0){
        if(n%2==1){
            ans*=x;
            ans%=mod;
        }
        n/=2;
        x=x*x;
        x%=mod;
    }
    return ans;
}
int main(){
    vector<long long> kaiz;
    kaiz.push_back(0);
    kaiz.push_back(1);
    for(long i = 2;i<Mod;i++){
        kaiz.push_back((kaiz[i-1]*i)%Mod);
    }
    int q;
    cin >> q;
    long long x,d,n;
    long long k;
    long long ans;
    rep(i,q){
        cin >> x >> d >> n;
        if(d == 0){
            cout << poww(x,n,Mod) << endl;
        }
        else{
            k = (x*modinv(d,Mod))%Mod;
            if(k+n-1>=Mod){
                cout << 0 << endl;
            }
            else{
                ans = kaiz[k+n-1]*modinv(kaiz[k-1],Mod);
                ans%=Mod;
                cout << (ans*poww(d,n,Mod))%Mod << endl;
            }
        }
    }
}

Measured memory_bytes: 10604
#include <iostream>
#include <algorithm>
#include <string> 
#include <vector>
#include <iomanip>
#include <math.h>
#include <map>
using namespace std;

int main()
{
	string S;
	cin >> S;
	bool can = false;
	for (int i = 0; i < S.size() - 1; i++) {
		if (S[i] == 'A' && S[i + 1] == 'C') {
			can = true;
		}
	}
	if (can) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scanner() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, 1000000007)
	sc.Split(bufio.ScanWords)
	n, _ := strconv.Atoi(Scanner())
	m, _ := strconv.Atoi(Scanner())
	graph := make([][]int, n)
	searched := make([]bool, n)
	ans := 0
	for i := 0; i < n; i++ {
		graph[i] = make([]int, 0)
	}
	for i := 0; i < m; i++ {
		x, _ := strconv.Atoi(Scanner())
		y, _ := strconv.Atoi(Scanner())
		_ = Scanner()
		x--
		y--
		graph[x] = append(graph[x], y)
		graph[y] = append(graph[y], x)
	}
	for i := 0; i < n; i++ {
		if !searched[i] {
			ans++
			q := []int{i}
			searched[i] = true
			for len(q) != 0 {
				idx := q[0]
				q = q[1:]
				for _, j := range graph[idx] {
					if !searched[j] {
						q = append(q, j)
						searched[j] = true
					}
				}
			}
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 11392
#include<algorithm>
#include<iostream>
using namespace std;
 
int out[4] = {0};
 
int main() {
int l[3];
while( cin >> l[0] >> l[1] >> l[2] ) {
sort(l, l+3);
if ( l[2] > l[0] + l[1] )
break;
 
out[0]++;
if ( l[2] * l[2] == l[0] * l[0] + l[1] * l[1] )
out[1]++;
if ( l[2] * l[2] < l[0] * l[0] + l[1] * l[1] )
out[2]++;
if ( l[2] * l[2] > l[0] * l[0] + l[1] * l[1] )
out[3]++;
}
 
cout << out[0] << " " << out[1] << " " << out[2] << " " << out[3] << endl;
return 0;
}

Measured memory_bytes: 1180
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main(){
  int a,b,c;
  LL k;
  cin>>a>>b>>c>>k;
  if(a!=b && b!=c && k>1000000000000000000) cout<<"Unfair"<<endl;
  else if(k%2){
    cout<<(b+c)-(a+c)<<endl;
  }else{
    cout<<a-b<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            int N, X;
            string[] str = Console.ReadLine().Split(' ');
            N = int.Parse(str[0]);
            X = int.Parse(str[1]);

            int zanX = X;
            int total = 0;

            int[] m = new int[N];
            for (int i = 0; i < N; i++)
            {
                m[i] = int.Parse(Console.ReadLine());
                zanX -= m[i];
                total++;
            }
            total = total + (zanX / m.Min());
            Console.WriteLine(total);
        }
    }
}


Measured memory_bytes: 13268
N,K=map(int,input().split())
#N=int(input())
A=list(map(int,input().split()))
#p=10**9+7
ma=[]
dp=[False]*(K+1)

for i in range(1,K+1):
    if i in A:
        dp[i]=True
    for j in A:
        if i < j:
            continue
        elif not dp[i-j]:
            dp[i] = True

#print(dp)
if dp[K]:
    print("First")
else:
    print("Second")




Measured memory_bytes: 41580
#include <bits/stdc++.h>
using namespace std;
using ll = long long ;
using P = pair<ll, ll>;
using Vec = vector<ll>;
using VecP = vector<P>;
#define FOR(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define FORN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define FORR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define repr(i, n) FORR(i, n, 0)
#define repnr(i, n) FORR(i, n, 1)
#define co(n) cout << (n) << endl
#define cosp(n) cout << (n) << ' '
#define setp(n) cout << fixed << setprecision(n);
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second

const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const double PI = acos(-1);
const double EPS = 1e-9;

int main(void){
	ll t1, t2, a1, a2, b1, b2;
	cin >> t1 >> t2 >> a1 >> a2 >> b1 >> b2;

	ll x1 = t1*a1, x2 = t2*a2, y1 = t1*b1, y2 = t2*b2;
	if(x1+x2 == y1+y2){
		puts("infinity");
		return 0;
	}

	if(x1 < y1){
		swap(x1, y1);
		swap(x2, y2);
	}

	if(x1+x2 > y1+y2){
		co(0);
		return 0;
	}

	ll diff = y1+y2-x1-x2;
	ll ans = (x1-y1)/diff*2+1;
	if((x1-y1)%diff == 0) ans--;
	co(ans);

	return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // setprecision
#include <complex> // complex
#include <math.h> 
#include <functional>
using namespace std;
using ll = long long;
using P = pair<int,int>;
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const int dx[8] = {1, 0, -1, 0,1,1,-1,-1};
const int dy[8] = {0, 1, 0, -1,1,-1,1,-1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ---------------------------------------------------------------------------


int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string N;
  cin >> N;
  int sum = 0;
  for(int i=0; i<N.size(); i++){
    sum += N[i] - '0';
    sum %= 9;
  }
  if(sum == 0){
    cout << "Yes\n";
  }else{
    cout << "No\n";
  }
  return 0;
}

Measured memory_bytes: 3768
a = int(input())
s = 0
b = 1
while 15*b <= a:
  s += 8*b
  b += 1
while 5*b <= a:
  s -= 7*b
  b += 1
while 3*b <= a:
  s -= 2*b
  b += 1
while b <= a:
  s += b
  b += 1
print(s)

Measured memory_bytes: 9184
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <cassert>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int iINF = 1001001001;
const long long llINF = 1LL << 60;
int main()
{
	// Square869120Contest #4 B, 
	int n, k; cin >> n >> k;
	vector<ll> a(n);
	rep(i, n) cin >> a[i];
	ll ans = llINF;
	rep(i, 1 << n) {
		int c = 0;
		rep(j, n) c += i >> j & 1;
		if (c != k) continue;
		ll tmpMax = -1;
		ll tmpAns = 0;
		rep(j, n) {
			if (i >> j & 1) {
				tmpAns += max(0ll, tmpMax - a[j] + 1);
				tmpMax = max(tmpMax + 1, a[j]);
			}
			else {
				tmpMax = max(tmpMax, a[j]);
			}
		}
		ans = min(ans, tmpAns);
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3624
n = int(input())
w = [input() for i in range(n)]
ans = True
if len(w) != len(set(w)):
    ans = False
for i in range(n-1):
    if w[i][-1] != w[i+1][0]:
        ans = False
if ans:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main()
{
 int n;
 cin>>n;
 vector<int>vec;
 int x;
 for(int i=0;i<n;i++)
 {
   cin>>x;
   vec.push_back(x);
 }

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

 int cnt=0,flag;

 for(int i=0;i<n;i++)
 {
     flag=0;
     for(int j=i+1;j<n;j++)
     {
         for(int k=j+1;k<n;k++)
         {
             if(vec[k]<vec[i]+vec[j])cnt++;
             else {flag=1;break;}
         }
     }
 }

 cout<<cnt;
}


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

int main(){

	int n;
	cin >> n;
	// char S[100][11];
	vector< string > S;
	
	for(int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		S.push_back(s);
	}
	
	for(int i = 0; i < n-1; i++)
	{
		// cout << S[i][0] << "," << S[i-1][S[i-1].size()-1] << "," << S[i][S[i].size()-1] << "," << S[i+1][0] << endl;
		// if(S[i][0] == S[i-1][S[i-1].size()-1] && S[i][S[i].size()-1] == S[i+1][0]){
		if (S[i].back() == S[i+1].front()){
			continue;
		}else{
			cout << "No" << endl;
			return 0;
		}
	}
	
	
	for(int i = 0; i < n-1; i++)
	{
		
		for(int j = i+1; j < n; j++)
		{
			// cout << i << "," << j << endl;
			if(S[i] == S[j] && i!=j){
				cout << "No" << endl;
				return 0;
			}
		}
		
	}
	cout << "Yes" << endl;
	
	return 0;
}

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

int main() {
    vector<vector<int> >grid(3,vector<int>(3,0));
   // vector<vector<int> > vec( n , vector<int> (m, 0));  
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    cin>>grid[i][j];
    // for(auto x:grid)
    // {
    //     for(auto y:x)
    //     cout<<y<<" ";
    //     cout<<"\n";
    // }
    int n;
    cin>>n;
    for(int k=0;k<n;k++)
    {
        int t;
        cin>>t;
        for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
        {
            if(grid[i][j]==t)
            grid[i][j]=0;
        }
    }
         if(grid[0][0]==0 && grid[0][1]==0 && grid[0][2]==0)
    cout<<"Yes";
    else if(grid[1][0]==0 && grid[1][1]==0 && grid[1][2]==0)
    cout<<"Yes";
    else if(grid[2][0]==0 && grid[2][1]==0 && grid[2][2]==0)
    cout<<"Yes";
    else if(grid[0][0]==0 && grid[1][0]==0 && grid[2][0]==0)
    cout<<"Yes";
    else if(grid[0][1]==0 && grid[1][1]==0 && grid[2][1]==0)
    cout<<"Yes";
    else if(grid[0][2]==0 && grid[1][2]==0 && grid[2][2]==0)
    cout<<"Yes";
    else if(grid[0][0]==0 && grid[1][1]==0 && grid[2][2]==0)
    cout<<"Yes";
    else if(grid[2][0]==0 && grid[1][1]==0 && grid[0][2]==0)
    cout<<"Yes";
    else cout<<"No";
	return 0;
}

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

typedef long long ll;

ll a[50],b[50],c[50],d[50];
int N,M,Q;
ll ans;

void dfs(vector<int> cur){
    if(cur.size() == N){
        ll sum = 0;
        for(int i=0; i<Q; i++){
            if(a[i] < cur.size() && b[i] < cur.size()){
                if((cur[b[i]] - cur[a[i]]) == c[i]){
                    sum += d[i];
                }
            }
        }

        ans = max(sum,ans);
        return;
    }

    if(cur.size() == 0){
        for(int i=1; i<=M; i++){
            cur.push_back(i);
            dfs(cur);
            cur.pop_back();
        }
    }

    else{
        for(int i=cur.back(); i<=M; i++){
            cur.push_back(i);
            dfs(cur);
            cur.pop_back();
        }
    }

}

int main(){
    cin>>N>>M>>Q;
    ans = 0;

    for(int i=0; i<Q; i++){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        a[i]--;
        b[i]--;
    }

    vector<int> cur;

    dfs(cur);

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

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

typedef long long int ll;
typedef pair<ll, ll> pii;
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fo(i,a,b) for(ll i = a; i<=b;i+=1)
#define rf(i,a,b)  for(ll i=a;i>=b;i--)
#define vll vector<ll>
#define sz(a) ll(a.size())
#define all(v) v.begin(),v.end()
#define pb push_back
#define pf push_front 
#define MAXN 100010
#define MOD 1000000007
#define mod 998244353
#define deb(x) cout << '>' << #x << ':' << x << endl;
#define debug(x) cout << '>' << #x << ':' << x << " ";
#define nl '\n'
#define INF 1000000000000000000
#define IO                 \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define int long long int

const int N = 2e5+10;
int x[N], y[N];

void solve(){
    int n;
    cin >> n;
    vll diff1, diff2;
    f(i, 0, n){
        cin >> x[i] >> y[i];
        diff1.push_back(x[i]-y[i]);
        diff2.push_back(x[i]+y[i]);
    }
    sort(all(diff1));
    sort(all(diff2));
    cout << max(abs(diff1[n-1] - diff1[0]), abs(diff2[n-1] - diff2[0])) << nl;
}
main()
{
    IO;
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int T = 1;
    // cin >> T;
    fo(c, 1, T){
        solve();
        // cout<<"Case #"<<c<<": ";
    }
    return 0;
}

Measured memory_bytes: 9748