akhauriyash/Code-Regression huggingface dataset:
#include  <iostream>
#include  <cstdlib>


int main(void)
{
	int N;
	std::cin >> N;

	int ans;

	if(N % 1000 == 0)
		ans = 0;
	else
		ans = (N/1000 + 1) * 1000 - N;

	std::cout << ans << std::endl;

	return EXIT_SUCCESS;
}


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

bool chk[244140624];
int n;
string ins, s;

int h(string s) {
    int ret = 0;
    for (int i=0; i<(int)s.size(); ++i) {
        ret *= 5;
        if (s[i] == 'A')
            ret += 1;
        else if (s[i] == 'C')
            ret += 2;
        else if (s[i] == 'G')
            ret += 3;
        else if (s[i] == 'T')
            ret += 4;
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    while (n--) {
        cin >> ins >> s;
        if (ins[0] == 'i') {
            chk[h(s)] = true;
        } else {
            cout << (chk[h(s)] ? "yes" : "no") << endl;
        }
    }
    return 0;
}

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




bool check(vector <ll> &init, vector <ll> &tar)
{
    for(ll i=0;i<init.size();i++)
        if(init[i]!=tar[i])
            return false;

    return true;
}
int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll n,i;
    cin>>n;
    vector <ll> a(n);
    vector <ll> b(n);
    vector <ll> init(n);
    for(i=0;i<n;i++)
        init[i] = i+1;
    for(auto &x:a)
        cin>>x;
    for(auto &x:b)
        cin>>x;
    ll count1 = -1;
    ll count2 = -1;
    i = 1;
    do
    {
        if(check(init,a))
            count1 = i;
        if(check(init,b))
            count2 = i;
        if(count1!=-1 && count2!=-1)
            break;

        i++;

    }
    while(next_permutation(init.begin(),init.end()));
    ll res = abs(count1-count2);
    cout<<res<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
    int N, K;
    cin >> N >> K;
    
    double ans = 0;
    for (int i = 1; i <= N; i++)
    {
        double prb = 1;
        int num = i;
        
        while (num < K)
        {
            prb *= 0.5;
            num *= 2;
        }
        
        ans += prb / N;
    }
    
    printf("%.12f\n", ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long N,k,ans,a,b;
  cin >>N>>k;
  
  if(k%2==0){
    a=N/k;
    k=k/2;
    b=N/k-a;
    ans=a*a*a+b*b*b;
  }
  else{
  a=N/k;
  ans=a*a*a;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC push_options
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#include <xmmintrin.h>
#include <immintrin.h>
using namespace::std;
__attribute__((constructor))void init(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// typedef mp::number<mp::cpp_dec_float<0>> cdouble;
// typedef mp::cpp_int cint;
template<typename T>using pbds=__gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T>using pbds_map=__gnu_pbds::tree<T,T,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T,typename E>using hash_map=__gnu_pbds::gp_hash_table<T,E>;
template<typename T>using pqueue =__gnu_pbds::priority_queue<T, greater<T>,__gnu_pbds::rc_binomial_heap_tag>;
typedef long long lint;
#define INF (1LL<<60)
#define IINF (1<<30)
#define EPS (1e-10)
#define endl '\n'
#define MOD 1000000007LL
//#define MOD 998244353LL
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
typedef vector<vector<vector<lint>>> mat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
template<typename T>inline void numout(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i<INF/2?i:"INF";f=1;}cout<<endl;}
template<typename T>inline void numout2(T t){for(auto i:t)numout(i);}
template<typename T>inline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<<i;f=1;}cout<<endl;}
template<typename T>inline void output2(T t){for(auto i:t)output(i);}
template<typename T>inline void _output(T t){bool f=0;for(lint i=0;i<t.size();i++){cout<<f?"":" "<<t[i];f=1;}cout<<endl;}
template<typename T>inline void _output2(T t){for(lint i=0;i<t.size();i++)output(t[i]);}
#define rep(i,n) for(lint i=0;i<lint(n);++i)
#define repi(i,a,b) for(lint i=lint(a);i<(lint)(b);++i)
#define rrep(i,n) for(lint i=lint(n)-1;i>=0;--i)
#define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i)
#define irep(i) for(lint i=0;;++i)
#define all(n) begin(n),end(n)
#define dist(a,b,c,d) sqrt(pow(a-c,2)+pow(b-d,2))
inline lint gcd(lint A,lint B){return B?gcd(B,A%B):A;}
inline lint lcm(lint A,lint B){return A/gcd(A,B)*B;}
// inline cint cgcd(cint A,cint B){return B?cgcd(B,A%B):A;}
// inline cint clcm(cint A,cint B){return A/cgcd(A,B)*B;}
inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;}
inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;}
const vector<lint> dx={1,0,-1,0,1,1,-1,-1};
const vector<lint> dy={0,1,0,-1,1,-1,1,-1};
#define SUM(v) accumulate(all(v),0LL)
auto call=[](auto f,auto... args){return f(f,args...);};


int main(){
	lint a,b;
	cin>>a>>b;
	rep(i,1e6){
		if(floor(i*0.08)==a&&floor(i*0.1)==b){
			cout<<i<<endl;
			return 0;
		}
	}
	cout<<-1<<endl;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/abc162/tasks/abc162_e

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(_i, n) printf("%d%c", a[_i], _i + 1 == n ? '\n' : ' ')
#define DUMP2D(a, n, m) REP(_i, n) REP(_j, m) printf("%d%c", a[_i][_j], _j + 1 == m ? '\n' : ' '); puts("")
#define DUMPLL(a, n) REP(_i, n) printf("%lld%c", a[_i], _i + 1 == n ? '\n' : ' ')


//------------------------------------------------------------------------------
ll mod_pow(ll x, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) {
      res = res * x % mod;
    }
    x = x * x % mod;
    n >>= 1;
  }
  return res;
}

//------------------------------------------------------------------------------
const int N_MAX = 1e5;
const int K_MAX = 1e5;
const int MOD = 1e9+7;

int N, K;

ll phi[K_MAX + 1];

void solve() {
  ll ans = 0;
  for (int i = K; i >= 1; i--) {
    phi[i] = mod_pow(K / i, N, MOD);
    for (int j = 2 * i; j <= K; j += i) {
      phi[i] = (phi[i] + MOD - phi[j]) % MOD;
    }
    ans = (ans + i * phi[i] % MOD) % MOD;
  }
  // DUMPLL(phi, K + 1);
  printf("%lld\n", ans);
}

void input() {
  scanf("%d%d", &N, &K);
}

int main() {
  input();
  solve();
  return 0;
}


Measured memory_bytes: 4552
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < n; i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main() {
    int N; cin >> N;
    vector<int> A(N);
    REP(i, 0, N) cin >> A[i];

    vector<int> B;
    int multiples[N + 1] = {};
    for (int i = N - 1; i >= 0; i--) {
        if (A[i] == multiples[i + 1] % 2) continue;
        B.push_back(i + 1);
        for (int j = 1; j * j <= i + 1; j++) {
            if ((i + 1) % j != 0) continue;
            multiples[j]++;
            if (j * j != i + 1) multiples[(i + 1) / j]++;
        }
    }

    cout << B.size() << endl;
    if (B.size() > 0) {
        for (int i = B.size() - 1; i >= 0; i--) {
            cout << B[i];
            if (i != 0) cout << " ";
        }
        cout << endl;
    }
    return 0;
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//const ull mod = 1e9 + 7;
const ll mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

// conversion number to bit
string num2bit(ll num, ll len){
  string bit = "";
  REP(i, len){
    bit += char('0'+(num>>i & 1));
  }
  return bit;
}

ll powLL(ll a, ll n){
    ll res = 1;
    while(n>0){
        if(n&1){
            res *= a;
            res %= mod;
        }
        a = a*a;
        a %= mod;
        n >>= 1;
    }
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N;
    cin >> N;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];

    vector<ll> S(N+1, 0);
    REP(i, N) S[i+1] = S[i]^A[i];
    cerr << S << endl;

    vector<ll> SZ(N+2, 0);
    REP(i, N+1) SZ[i+1] = SZ[i] + (S[i]==0);

    // compress
    set<ll> st;
    REP(i, N+1){
        st.insert(S[i]);
    }
    map<ll, ll> mp;
    ll cnt = 0;
    for(auto x: st){
        mp[x] = cnt;
        cnt++;
    }

    vector<vector<ll>> kan(cnt);
    vector<ll> prev(cnt, -1);

    REP(i, N+1){
        ll val = mp[S[i]];
        kan[val].push_back(SZ[i] - SZ[prev[val]+1]);
        prev[val] = i;
    }

    REP(i, cnt){
        REP(j, kan[i].size()){
            cerr << kan[i][j] << " ";
        }
        cerr << endl;
    }


    ll res = 0;
    if(S.back()==0){
        REP(i, cnt){
            if(i==0){
                res += powLL(2, (ll)kan[i].size()-2);
                continue;
            }
            ll zz = 1, xx = 1;
            REP(j, kan[i].size()){
                if(j==0)continue;
                zz += (xx*kan[i][j])%mod;
                zz %= mod;
                xx += zz;
                xx %= mod;
            }

            res += xx;
            res %= mod;
        }
    }else{
        REP(i, cnt){
            if(mp[S.back()] != i) continue;
            
            ll zz = 1, xx = 1;
            REP(j, kan[i].size()){
                if(j==0)continue;
                zz += (xx*kan[i][j])%mod;
                zz %= mod;
                xx += zz;
                xx %= mod;
            }

            res += zz;
            res %= mod;
        }
    }
    
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 63292
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define bit(k) (1LL<<(k))
typedef long long ll;

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

const int INF = 1e9;
const ll INFLL = 1e18;
const ll MOD = 1e9+7;
const double PI = acos(-1.0);

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

/*------------------------------------/
for library*/

/*------------------------------------*/

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

    string S;
    cin>>S;
    int cnt  = 0;
    int N = S.size();
    for(int i = 0;i < N/2;i++){
        if(S[i] != S[N-1-i]){
            cnt++;
        }
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 256
using System.Collections.Generic;
using static System.Console;
using static System.Math;

class Program {
	static void Main() {
		var N = NextInt();
		var A1 = NextInt();
		var min = A1;
		var max = A1;

		for (var i = 0; i < N - 1; i++) {
			var A = NextInt();
			min = Min(min, A);
			max = Max(max, A);
		}
		WriteLine(max - min);
	}

	static int NextInt() {
		return int.Parse(NextString());
	}

	static string NextString() {
		var result = new List<char>();
		while (true) {
			int next = Read();
			if (next < 0)
				break;
			var nextChar = (char)next;
			if (!char.IsWhiteSpace(nextChar))
				result.Add(nextChar);
			else if (nextChar != '\r')
				break;
		}
		return string.Join("", result);
	}
}

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

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

	int n;
	cin >> n;
	if(n%2) cout << n/2+1;
	else cout << n/2;

    return 0;
}


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

using namespace std;

#define rep(i, n) for (int i = 0; i < n; ++i)
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
#define stl_repr(itr, x) for (auto itr = x.rbegin(); itr != x.rend(); ++itr)
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()

using llong = long long int;

const static int MOD = 1000000007;
const static int inf = INT_MAX;
const static llong INF = LLONG_MAX;
const static int dx[4] = {1, 0, -1, 0};
const static int dy[4] = {0, 1, 0, -1};

int main (int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int> A(n), B(n), C(n);
    rep(i, n) cin >> A[i];
    rep(i, n) cin >> B[i];
    rep(i, n-1) cin >> C[i];

    int satisfaction = 0;
    rep(i, n) {
        satisfaction += B[A[i]- 1];
        if (i < n - 1) {
            if (A[i + 1] == A[i] + 1) satisfaction += C[A[i] - 1];
        }
    }

    cout << satisfaction << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main() {
	int a, b, c=0;
	scanf("%d %d", &a, &b);
	for (int i = 0; i < 2; i++) {
		if (a < b) {
			c = c + b;
			b = b - 1;
		}
		else {
			c = c + a;
			a = a - 1;
		}
	}
	printf("%d", c);
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>

int main(void){
    int A,B,C,K,ans=0;
    scanf("%d %d %d %d",&A,&B,&C,&K);

    //aとKの枚数を比較する
    //kがa以上だった場合、とりあえず答えにaの値を加算し、kの枚数をaだけ減らす
    //kがaより小さいなら、とりあえずaの値をkだけ増やす。
    if(A<=K){
        ans += A;
    }else{
        ans += K;
    }

    //kからaとbの枚数だけ減らす
    K -= (A + B);

    //もしまだkが1以上あるのなら、その枚数だけ答えから引く
    if(K>0){
        ans -= K;
    }

    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 1720
#include <iostream>
using namespace std;
int main()
{
    int A,B,C;
    
    cin >> A >> B >> C;

    if (A == B && A == C)
    {
        cout << "No" << endl;
    } else if (A == B && A != C) 
    {
        cout << "Yes" << endl;
    }  else if (B == A && B == C) 
    {
        cout << "No" << endl;
    }  else if (B == A && B != C) 
    {
        cout << "Yes" << endl;
    }  else if (C == A && C == B) 
    {
        cout << "No" << endl;
    }  else if (C == A && C != B) 
    {
        cout << "Yes" << endl;
    } else if (B == C && B != A) 
    {
        cout << "Yes" << endl;
    } else
    {
        cout << "No" << endl;
    }
    return 0;
}

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

static const int N = 100;

int min (int a, int b) {
	if (a < b) return a;
	else return b;
	return 0;  
}

int main () {
	int i, j, k, l;
	int n, p[N +1], m[N + 1][N + 1];

	scanf("%d",&n);

	for ( i = 1; i <= n; i++) scanf("%d%d", &p[i -1], &p[i]);

	for ( i = 1; i <= n; i++) m[i][i] = 0;
	for ( l = 2; l <= n; l++) {
		for ( i = 1; i <= n - l + 1; i++) {
			j = i + l - 1;
			m[i][j] = i + l - 1;
			m[i][j] = (1 << 21);
			for (k = i; k <= j - 1; k++) {
				m[i][j] = min(m[i][j],m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j] );
			}
		}
	}

	printf("%d\n",m[1][n]);

	return 0;
}


Measured memory_bytes: 2112
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <sstream>
#include <fstream>
#include <cmath>
#include <stack>
#include <queue>
#include <list>
#include <map>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

#define MAX(x,y) ( (x) > (y) ? (x) : (y) )
#define MIN(x, y) ( (x) < (y) ? (x) : (y) )
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define IVFOR(p,a) for(vector<int>::iterator p = (a).begin(); p!=(a).end(); p++)
#define ILFOR(p,a) for(list<int>::iterator p = (a).begin(); p!=(a).end(); p++)
#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define CHECK(x)  cout << #x << " = " << (x) << endl
#define FINA(y) cout << (y) << endl

int main(){

  int n,k;
  cin >> n >> k;
  if(n == 1)
    FINA(k);
  else{
    int o = 1;
    FOR(i,1,n)
      o *= k - 1;
    cout << o * k << endl;
    //    cout << (k * pow(k-1, n-1)) << endl; 
  }
 return 0;
}


Measured memory_bytes: 256
A, B = map(int,input().split())
base_A = int(A / 0.08) if A / 0.08 - int(A/0.08) < 0.5 else int(A / 0.08)+1
base_Aplus = int((A+1) / 0.08)
count = 0
for i in range(base_A, base_Aplus):
  if (int(i * 0.1) == B):
    ans = i
    count += 1
    break
if count > 0:
  print(ans)
else:
  print(-1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)(n); i++)
#define FOR(i, a, b) for(ll i = a; i <= (ll)(b); i++)

#define ALL(x) (x).begin(), (x).end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

using namespace std;
using ll = long long;
using vel = vector<ll>;
using ves = vector<string>;

int main() {
    ll N, A;
    cin >> N;
    vel S(N);
    REP(i, N) S[i] = 0;
    REP(i, N - 1) {
        cin >> A;
        S[A-1]++;
        }
        REP(i, N) cout << S[i] << endl;
}

Measured memory_bytes: 4840
using System;
using System.Collections.Generic;


public class Contest
{
	public static void Main()
	{
		int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), new Converter<string,int>(s => int.Parse(s)));

//		int[] b = Array.ConvertAll(Console.ReadLine().Split(' '), new Converter<string,int>(s => int.Parse(s)));
//		int[] c = Array.ConvertAll(Console.ReadLine().Split(' '), new Converter<string,int>(s => int.Parse(s)));
//		int[] d = Array.ConvertAll(Console.ReadLine().Split(' '), new Converter<string,int>(s => int.Parse(s)));
/*
		int n = a[0];
		int[][] e = new int[n][];
		for(int i=0; i<n; i++) e[i] = Array.ConvertAll(Console.ReadLine().Split(' '), new Converter<string,int>(s => int.Parse(s)));
*/

		string q = "";
		switch(a[0]){
			case 22: q="Christmas Eve Eve Eve";break;
			case 23: q="Christmas Eve Eve";break;
			case 24: q="Christmas Eve";break;
			case 25: q="Christmas";break;
			default : break;
		}

		string ans = q.ToString();

		Console.WriteLine(ans);
	}
	
	private static int calc_main(int[] a,int[] b,int[] c,int[] d) {



		return 0;
	}




}


Measured memory_bytes: 11220
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

struct Task
{
    int x,y,t;
    bool operator < (const Task &a) const
    {
        return t < a.t;
    }
}tsk[100050];

int N;

int main()
{
    scanf("%d",&N);
    int tmpx = 0,tmpy = 0,tmpt = 0;
    for(int i = 1;i <= N; ++ i)
    {
        scanf("%d%d%d",&tsk[i].t,&tsk[i].x,&tsk[i].y);
        int val = abs(tsk[i].x - tmpx) + abs(tsk[i].y - tmpy);
        if(val > tsk[i].t - tmpt || (val - tsk[i].t + tmpt) % 2 != 0)
        {
            printf("No\n");
            return 0;
        }
        tmpx = tsk[i].x;
        tmpy = tsk[i].y;
        tmpt = tsk[i].t;
    }
    printf("Yes\n");
    return 0;
}


Measured memory_bytes: 1408
import numpy as np
N,A = map(int,input().split())
X = [int(x) for x in input().split()]
dp = np.zeros((N+1,3000),dtype=np.int64) # 枚数、目標数ごとに場合の数
dp[0,0] = 1

for x in X:
  dp[1:,x:] += dp[:-1,:-x].copy()
  
answer = 0
for n in range(1,N+1):
  answer += dp[n,n*A]
  
print(answer)

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

int main() { 
    int n, j = 0, ans = 0;
    string s;
    cin >> n >> s;
    for(int i = 0; i < n; ++i) {
        if(s[i] == 'I') j++;
        else j--;
        ans = max(ans, j);
    }
    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vec;
 
#define vecc vector<vector<ll>>
#define LM LLONG_MAX
 
#define int long long int
#define P pair<ll,ll>
 
#define ff first
#define ss second
 
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
 
#define N 200005
#define MOD (ll)1000000007

signed main()
{
      FAST;
      
      ll n;
      cin>>n;
      
      ll dp[n+5];
      ll a[n+5];
      
      for(int i=1;i<=n;i++)
            cin>>a[i];
            
      dp[1]=0;
      dp[2]=abs(a[2]-a[1]);
      
      for(int i=3;i<=n;i++)
            dp[i]=min(dp[i-2]+abs(a[i-2]-a[i]),dp[i-1]+abs(a[i-1]-a[i]));
      
      cout<<dp[n]<<"\n";
      
}

Measured memory_bytes: 1920
using System;
using System.Collections.Generic;
using System.Linq;

class Procon
{
    public Procon() { }
    static void Main(string[] agrs)
    {
        new Procon().Do();
    }

    Scanner cin;

    public void Do()
    {
        cin = new Scanner();

        int N = cin.nextInt();
        int[] V = cin.arrayInt();
        int[] C = cin.arrayInt();

        int ret = 0;
        for (int i = 0; i < N; i++)
        {
            if (V[i] - C[i] > 0)
            {
                ret += V[i] - C[i];
            }
        }

        Console.WriteLine(ret);
    }
}

class Scanner
{
    string[] s;
    int i;
    int max_i;

    public Scanner()
    {
        s = new string[0];
        max_i = 0;
        i = 0;
    }

    public string nextString()
    {
        if (i >= s.Length)
        {
            s = Console.ReadLine().Split(' ');
            max_i = s.Length;
            i = 0;
            if (max_i == 0)
            {
                return "";
            }
            return s[i++];
        }
        else
        {
            return s[i++];
        }
    }

    public int nextInt()
    {
        return int.Parse(nextString());
    }

    public long nextLong()
    {
        return long.Parse(nextString());
    }

    public double nextDouble()
    {
        return double.Parse(nextString());
    }

    public string[] arrayString()
    {
        return Console.ReadLine().Split(' ');
    }

    public int[] arrayInt()
    {
        string[] str = Console.ReadLine().Split(' ');
        int[] array = new int[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = int.Parse(str[i]);
        }
        return array;
    }

    public long[] arrayLong()
    {
        string[] str = Console.ReadLine().Split(' ');
        long[] array = new long[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = long.Parse(str[i]);
        }
        return array;
    }

    public double[] arrayDouble()
    {
        string[] str = Console.ReadLine().Split(' ');
        double[] array = new double[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = double.Parse(str[i]);
        }
        return array;
    }
}

Measured memory_bytes: 13140
#include<iostream>
#include<vector>
#include<algorithm>
#define F first
#define S second
using namespace std;

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


int solve(int ini, std::vector<p>& v){
	int now = ini;
	sort(v.begin(),v.end());

	for(int i=v.size()-1;i>=0;i--){
		if(v[i].S.F==now){
			now = v[i].S.S;
		}else if(v[i].S.S==now){
			now = v[i].S.F;
		}
		// cout << v[i].F <<" "<<v[i].S.F << " "<<v[i].S.S << endl;
	}
	return now;
}

int main(){
	while(1){
		vector<p> v;
		int n,m,a;
		cin >> n >> m >>a;
		if(n+m+a==0) break;
		int h,p,q;
		for(int i=0;i<m;i++){

			cin >> h >> p >>q;
			v.push_back(make_pair(h,make_pair(p,q)));
		}
		cout << solve(a,v) << endl;
	}
	return 0;
}

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

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

int main()
{
    int N, M;
    cin >> N >> M;

    vector<int> A(N,0), B(M,0), C(M,0);
    rep(i, N)   cin >> A.at(i);
    rep(i, M)   cin >> B.at(i) >> C.at(i);

    priority_queue<pair<int, int>> q;
    rep(i, N)   q.push(make_pair(A.at(i), 1));
    rep(i, M)   q.push(make_pair(C.at(i), B.at(i)));

    long long ans = 0;
    rep(i, N)
    {
        auto P = q.top();
        q.pop();
        ans += P.first;

        if(P.second > 1)
        {
            P.second--;
            q.push(P);
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3700
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <sstream>
#include <string>
#include <map>
#include <set>
using namespace std;

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


int main() {
	int s;
	cin >> s;
	int A[1000000];
	int an = s;
	A[an]++;
	int fn;
	bool flg = true;
	int res = 1;
	while(flg) {
		if (an%2==0) fn = an / 2;
		else fn = 3*an + 1;
		an = fn;
		if (A[an] != 0) flg = false;
		A[an]++;
		res++;
	}
	cout << res << endl;
}

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


int main() {
    int n, d, ans = 0;
    cin >> n >> d;
    REP(i,n){
        int p;
        cin >> p;
        ans += max(0, p-d);
    }
    if(ans > 0){
        cout << ans << endl;
    }
    else {
        cout << "kusoge" << endl;
    }
    return 0;
}


Measured memory_bytes: 3096
/*
********************
Author : MIHIR ARORA
********************
*/
#include <bits/stdc++.h>
using namespace std;
#define fast cin.tie(NULL); cout.tie(NULL); 
#define input int n; scanf("%d",&n); int*arr = new int[n];  for(int i=0;i<n;i++) scanf("%d",&arr[i]);  
#define inputs int n; scanf("%d",&n); char str[n];   cin>>str;   

typedef long long int ll;
const int mod=1e9+7; 
ll add(ll a, ll b)
{
    return (a%mod+b%mod)%mod;
}

ll mul(ll a, ll b)
{
    return ((a%mod)*(b%mod))%mod;
}

ll sub(ll a, ll b)
{
    return ((a%mod) - (b%mod))%mod;
}
inline void solve()
{
 input; 
}
int main()
{ 
    fast; 
   int a,b,c,d; 
    cin>>a>>b>>c>>d; 
    int ctr=1; 
    while(a>0 && c>0)
    {
        if(ctr%2==0)
        {
            a=a-d; 
        
        }
        else
        {
            c=c-b; 
         
        }
        ctr++; 
    }
    
    if(c<=0)
        cout<<"Yes"; 
    else if(a<=0)
        cout<<"No"; 
}

Measured memory_bytes: 3636
// Union-Find木のテスト
//  ランクあり版

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

struct UnionFind {
  vector<int> par;
  vector<int> rank;
  UnionFind( int n ) {
    par.resize(n);
    rank.resize(n);
    init(n);
  }
  void init( int n ) {
    for(int i=0; i<n; ++i )  par[i] = i;
    for(int i=0; i<n; ++i )  rank[i] = 0;
  }
  int root( int a ) {
    int pa = par[a];
    if ( pa == a ) return a;
    rank[a] = 1;
    return par[a] = root(pa);
  }
  bool merge( int a, int b ) {
    int ra = root(a);
    int rb = root(b);
    if ( ra == rb ) return false;
    if ( rank[a] < rank[b] ) swap(a,b);
    par[rb] = ra;
    rank[rb]++;
    return true;
  }
  bool isSame( int a, int b) {
    int ra = root(a);
    int rb = root(b);
    if ( ra == rb ) return true;
    else return false;
  }
  int CountRoot( int n ) {
    int cnt = 0;
    for (int i=0; i<n; ++i )
      if ( i == par[i] ) cnt++;
    return cnt;
  }
};

int main() {
  int N,M;
  cin >> N >> M;
  UnionFind uf(N);
  REP(i,M) {
    int x,y,z;
    cin >> x >> y >> z;
    x--; y--;
    uf.merge(x,y);
  }
  
  cout << uf.CountRoot(N) << endl;
  
}



Measured memory_bytes: 1024
import math

H = int(input())

i = 1
count = 0
monster = [H, 1]
while i > 0:
  count += monster[1]
  new_monster = math.floor(monster[0] / 2)
  monster = [new_monster, monster[1] * 2]
  if new_monster == 0:
    print(count)
    break

Measured memory_bytes: 3064
primes = {
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
    73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
    157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
    239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
    331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
    421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
    509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
    613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
    709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811,
    821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
    919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997}


def split_primes(x: int) -> int:
    """
    x <= 1000 (10^3)
    """
    if x in primes:
        return {x: 1}

    exp_dict = {}
    while x != 1:
        for prime in primes:
            if prime not in exp_dict:
                exp_dict[prime] = 0
            if x % prime == 0:
                exp_dict[prime] = exp_dict[prime] + 1
                x = int(x / prime)
                break
    return exp_dict


def main():
    N = int(input())
    mod_target = 10 ** 9 + 7

    exp_dict = {}
    for i in range(2, N + 1):
        n_exp = split_primes(i)
        for new_exp in n_exp:
            exp_dict[new_exp] = n_exp[new_exp] + (
                exp_dict[new_exp] if (new_exp in exp_dict) else 0
            )
    count = 1
    for key in exp_dict:
        count = (count * (exp_dict[key] + 1)) % mod_target
    print(count)


if __name__ == '__main__':
    main()

Measured memory_bytes: 3192
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);  cin.tie(0) ; cout.tie(0);
#define debug(x) cout << #x << " : " << x << endl;
#define pi 3.14159265359
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
using ll = long long int;
using db = double;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<bool> vb;
const int MOD = 1e9+9;

void solve()
{
    ll n , tot ;
    cin >> n;
    cin >> tot;
    vl a(n);
    a[0] = tot;
    for(ll i = 1 ; i < n ; i++)
    {
        ll x;
        cin >> x;
        a[i] = x;
        tot ^= x;
    }
    for(int i = 0 ; i < n ; i++)
        cout << (a[i]^tot) << " ";
    
}

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

    ll t = 1;
    while(t--)
       solve();
    return 0;
}

Measured memory_bytes: 4776
#include <bits/stdc++.h>
#include <algorithm>
#include <map>
#include <cstdlib>
#include <cmath>
#include <bitset>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<n;i++)
#define inf 1e9+7
using namespace std;
typedef long long ll;
const double pi=acos(-1);

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> P(n);
    vector<int> C(n);
    for(int i=0;i<n;i++) cin >> P[i];
    for(int i=0;i<n;i++) cin >> C[i];
    for(int i=0;i<n;i++) P[i]--;
    ll ans=-1e18;
    for(int i=0;i<n;i++){
        int ind=i;
        vector<ll> cycle_cum;
        while(true){
            ind=P[ind];
            ll num=C[ind];
            if(cycle_cum.size()!=0) num+=cycle_cum.back();
            cycle_cum.push_back(num);
            if(ind==i) break;
        }
        ll cycle_sum=cycle_cum.back();
        int cycle_size=cycle_cum.size();
        if(cycle_sum<=0){
            for(int j=0;j<min(k,cycle_size);j++){
                ans=max(ans,cycle_cum[j]);
            }
        }else{
            ll tmp=cycle_sum;
            for(int j=0;j<k%cycle_size;j++){
                tmp=max(tmp,cycle_sum+cycle_cum[j]);
            }
            sort(cycle_cum.begin(),cycle_cum.end());
            ll sep=max(cycle_cum.back(),tmp);
            sep+=cycle_sum*(k/cycle_size-1);
            ans=max(ans,sep);
        }
    }
    cout << ans << endl;
}

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

typedef ostringstream OSS; typedef istringstream ISS;
typedef long long LL;
typedef pair<int, int> PII;  typedef pair<LL, LL> PLL;
typedef vector<int>    VI;   typedef vector<VI>   VVI;   typedef vector<VVI>   VVVI;
typedef vector<LL>     VLL;  typedef vector<VLL>  VVLL;  typedef vector<VVLL>  VVVLL;
typedef vector<double> VD;   typedef vector<VD>   VVD;   typedef vector<VVD>   VVVD;
typedef vector<string> VS;   typedef vector<VS>   VVS;   typedef vector<VVS>   VVVS;
typedef vector<bool>   VB;   typedef vector<VB>   VVB;   typedef vector<VVB>   VVVB;
typedef vector<PII>    VPII; typedef vector<VPII> VVPII; typedef vector<VVPII> VVVPII;
typedef vector<PLL>    VPLL; typedef vector<VPLL> VVPLL; typedef vector<VVPLL> VVVPLL;

typedef unsigned int  UI;
typedef vector<UI>    VUI;
typedef vector<VUI>   VVUI;

#define fst first
#define snd second
// #define Y first
// #define X second
#define MP make_pair
#define PB push_back
#define EB emplace_back 
#define ALL(x)  (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define RANGEBOX(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
#define RANGE(x, l, r) ((l) <= (x) && (x) <= (r))
#define rep(i, N)  for (int i = 0; i < (int)(N); i++)
#define rrep(i, N) for (int i = N - 1; i >= 0; i--)
#define REP(i, init, N)  for (int i = (init); i < (int)(N); i++)
#define RREP(i, N, last) for (int i = (init - 1); i >= last; i--)
#define MAXUD(orig, target) orig = max(orig, target)
#define MINUD(orig, target) orig = min(orig, target)
#define DUMP(x) cerr << #x << " = " << (x) << endl

template < typename T > inline T fromString(const string &s) { T res; ISS iss(s); iss >> res; return res; };
template < typename T > inline string toString(const T &a)   { OSS oss; oss << a; return oss.str(); };

template<typename T=int> inline void dump(vector<T> vs, bool ent=false) { rep(i, vs.size()) cout << vs[i] << (i+1==vs.size() ? '\n' : ' '); if (ent) cout << endl; }
template<typename T = int> inline void dump(vector<vector<T>> vs, bool ent=false) { rep(i, vs.size()) dump<T>(vs[i]); if (ent) cout << endl; }

const int    INF  = 0x3f3f3f3f;
const LL     INFL = 0x3f3f3f3f3f3f3f3fLL;
const double DINF = 0x3f3f3f3f;
const int    DX[] = {1,  0, -1, 0};
const int    DY[] = {0, -1,  0, 1};
const double EPS  = 1e-12;
// const double PI   = acos(-1.0);

template<typename T = int> inline T in() { T x; cin >> x; return x; }
template<typename T = int> inline vector<T> in(int n) { vector<T> xs(n); rep(i, n) cin >> xs[i]; return xs; }
template<typename T = int> inline vector<vector<T>> in(int n, int m) { vector<vector<T>> xs(n, vector<T>(m)); rep(i, n) rep(j, m) cin >> xs[i][j]; return xs; }

int main(void) {
    int n, k, x, y;
    cin >> n >> k >> x >> y;
    cout << (min(k, n) * x + max(0, n - k) * y) << endl;

    return 0;
}



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

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    int al = 0;
    int bo = 0;
    if(n % 2 == 0) {
        rep(i, n / 2) {
            al += a[2 * i];
            bo += a[2 * i + 1];
        }
    }
    else {
        rep(i, n / 2) {
            al += a[2 * i];
            bo += a[2 * i + 1];
        }
        al += a[n - 1];
    }
    cout << al - bo << endl;
    return 0;
}

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

int main() {
  
  int N; cin >> N; bool ans = true;
  
  vector<int> vec(N);
  
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  
  sort(vec.begin(), vec.end());
  
  for (int i = 0; i < N - 1; i++) {
    if (vec.at(i) == vec.at(i + 1)) {
      ans = false;
    }
  }
  
  if (ans) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
  
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()

using ll = long long;
using P = pair<int,int>;

const int MOD = 1e9 + 7;
const int INF = 1001001001;

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

    char a;
    cin >> a;

    if('A' <= a && a <= 'Z'){
        cout << 'A' << "\n";
    }else{
        cout << 'a' << "\n";
    }


    return 0;
}


Measured memory_bytes: 3608
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

int asc(const void* a, const void* b) {
    return *(char*)b - *(char*)a;
}

int cmp2(const void* p, const void* q) {
    return strcmp((char*)p, (char*)q);
}
int main() {
    char str[100000][15] = { 0 };
    int n;
    long long ans = 0, temp = 1;

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", str[i]);
        qsort(str[i], 10, sizeof(char), asc);
    }
    //for (int i = 0; i < n; i++) printf("%s\n", str[i]);
    qsort(str, n, sizeof(str[0]), cmp2);
    //for (int i = 0; i < n; i++) printf("%s\n", str[i]);
    for (int i = 0; i < n; i++) {
        if (strcmp(str[i],str[i+1])==0)temp++;
        else {
            ans += temp * (temp - 1) / 2;
            temp = 1;
        }
    }
    printf("%lld", ans);
    return 0;
}


Measured memory_bytes: 3068
import numpy as np
input_arr = [int(x) for x in input().split()]

N = input_arr[0]
D = input_arr[1]


point = []

for i in range(N):
    input_num = [int(x) for x in input().split()]
    point.append(input_num)
count = 0

for i in range(N):
    for j in range(i+1,N):
        a = np.array(point[i])
        b = np.array(point[j])
        u = b - a
        distance = (np.linalg.norm(u))
        if distance.is_integer():
            count = count +1
            
print(count)

Measured memory_bytes: 12444
def eat2(lv, to_eat)
  # lv0
  if lv == 0
    return [1, to_eat-1]
  end

  total, pate = burger_info(lv)
  # 食べ尽くせる
  if total <= to_eat
    return [pate, to_eat - total]
  end

  # 残る -> こまぎれに考える
  if to_eat == 1
    return 0, 0
  end

  # 前レベルその1
  pate, rest = eat2(lv-1, to_eat-1)
  return pate, 0 if rest == 0

  # 真ん中
  return pate+1, 0 if rest == 1

  # 前レベルその2
  pate += 1
  rest -= 1
  p, rest = eat2(lv-1, rest)
  pate += p

  return pate, 0 if rest == 0

  # 端
  return pate, 0 if rest == 1

  # このレベルでは食べきれなかった
  [pate, rest-1]
end

# total, pate
def burger_info(lv)
  # lv total pate
  # 0      1    1
  # 1      5    3
  # 2     13    7
  # 3 13*2+3 7*2+1
  #

  return [1, 1] if lv == 0

  total = 1
  pate = 1
  lv.times do |l|
    total = total * 2 + 3
    pate = pate * 2 + 1
  end
  [total, pate]
end

def main
  n, x = gets.split.map(&:to_i)

  pate, _ = eat2(n, x)

  puts pate
end

if __FILE__ == $0
  main
end


Measured memory_bytes: 1788
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
const double EPS = 1e-9;
typedef pair<int, int> P;
typedef unsigned int ui;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
const ld eps=1e-8;
int main() {
	int n;
	while (cin >> n, n) {
		P in[41] = {};
		in[0] = { 0,0 };
		rep1(i, n) {
			int d,t;
			cin >> d >> t; in[i] = { d,t };
		}
		int dp[41][4];
		int out = in[n].first;
		rep(i, 41) {
			rep(j, 4) {
				dp[i][j] = (int)MOD;
			}
		}
		dp[0][0] = 0; int chk;
		bool g = false;
		rep1(i, n) {
			bool f = false;
			rep(j, 4) {
				if (dp[i-1][j] == (int)MOD)continue;
				int cost = j + 1;
				int straitime = abs(in[i].first - in[i - 1].first)*cost;
				if (j<3&&straitime <= in[i].second - in[i - 1].second) {
					f = true;
					dp[i][j + 1] = min(dp[i][j + 1], dp[i - 1][j] + abs(in[i].first - in[i - 1].first));
				}
				int retime = in[i - 1].first*cost + in[i].first;
				if (retime <= in[i].second - in[i - 1].second) {
					f = true;
					dp[i][1] = min(dp[i][1], dp[i - 1][j] + in[i - 1].first + in[i].first);
				}
			}
			if (!f) {
				chk = i; g = true; break;
			}
		}
		if (g) {
			cout << "NG "<< chk << endl;
		}
		else {
			int mi = (int)MOD;
			rep(i, 4) {
				mi = min(mi, dp[n][i]);
			}
			out += mi;
			cout << "OK " << out << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 2992
# chokudaiブログの典型力の話を意識しつつ考えたら思いついた!

# 「ある集合の部分集合の中で、〜〜〜の値が最小になるものを求めよ」のパターン
# 愚直にやると2^Nを調べねばならず無理。
# したがって「一部を調べればよい」に帰着するのが多いだろう。
# 何らかの形でソートしておいて、空集合から1つずつ付け加えるとか。全体集合から1つずつ取り去るとか。

# 今回は全体集合から1つずつ取り去るのを考えるとできる。
# 全体集合である競技m0が最多の人数p0人を集めたとする。
# すると、全ての部分集合のうち「m0を含む集合」を考えると、競技m0は必ずp0人以上集まるので解もp0以上。
# ここで「m0を含む集合」について一気に計算できていることに注意! 一撃で多数の集合について計算が終わる。
# 次に全体集合からm0を取り去ったものを考える。
# ここである競技m1が最多の人数p1人を集めたとする。すると……以下同様。
# なお複数種目の競技が同率1位になった場合は全て一度に取り除いて良い。
# これで空集合までやって、最大が最小のものを出力すればOK! 

n, m = list(map(int, input().split()))
preference = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)] # 1-index → 0-index

ans = n
held_sports = set(range(m))

while held_sports:
    # 各競技に参加する人数を求める
    parti = [0] * m
    for pref in preference:
        for s in pref:
            if s in held_sports:
                parti[s] += 1
                break
    
    temp = max(parti)
    ans = min(ans, temp)
    # 集合から最大人数を取った要素を除外
    indices = [i for i,val in enumerate(parti) if val == temp]
    held_sports = held_sports - set(indices)

print(ans)

Measured memory_bytes: 10252
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

struct node{
  int id;
  int k;
  int pk;
  int lk;
  int rk;
};
typedef struct node *Node;

int parent(i){
  return floor(i/2);
}

int left(i){
  return 2*i;
}

int right(i){
  return (2*i)+1;
}

int main(){
  
  int H, i, K, P;
  Node n;
  scanf("%d",&H);
  
  n = (Node)malloc(sizeof(Node)*H);
  
  for(i=0; i<H; i++){
    n[i].id = i+1;
    scanf("%d", &K);
    n[i].k = K;
    n[i].pk = 0;
    n[i].lk = 0;
    n[i].rk = 0;
  }
  
  for(i=0; i<H; i++){

    if(i != 0){
    n[i].pk = n[parent(n[i].id)-1].k;
    }

    if(n[i].id*2 <= H){
      n[i].lk = n[left(n[i].id)-1].k;
    }

    if(n[i].id*2+1 <= H){
      n[i].rk = n[right(n[i].id)-1].k;
    }
    
    printf("node %d: key = %d, ", n[i].id, n[i].k);
    if(n[i].pk != 0){
      printf("parent key = %d, ",n[i].pk);
    }
    if(n[i].lk != 0){
      printf("left key = %d, ",n[i].lk);
    }
    if(n[i].rk != 0){
      printf("right key = %d, ",n[i].rk);
    }
    printf("\n");
  }
  
  return 0;
}



Measured memory_bytes: 2040
#include<stdio.h>
int main(void){
    int i,n,a,min=1000000,max=-1000000;
    long long int sum=0;
    scanf("%d",&n);
    i=0;
    for(i=0;i<n;i++){
        scanf("%d",&a);
        if(max<a){
            max=a;
        }
        if(min>a){
            min=a;
        }
        sum+=a;
    }
    printf("%d %d %lld\n",min,max,sum);
    return 0;
}


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

signed
main(){
	int N,A,B,C,D;
	string s;
	cin >> N >> A >> B >> C >> D >> s;
	A--,B--,C--,D--;

	bool not_diwa = true;
	for(int i=A;i<=D;i++) {
			if(s[i]=='#' && s[i+1]=='#'){
					not_diwa = false;
					break;
			}
	}

	bool pass = false;
	for(int i=B-1;i<=D-1;i++) {
			if(s[i]=='.' && s[i+1]=='.' && s[i+2]=='.') {
					pass = true;
					break;
			}
	}

	if(C < D) {
			if(not_diwa) cout << "Yes" << endl;
			else cout << "No" << endl;
	}else {
			if(pass && not_diwa) cout << "Yes" << endl;
			else cout << "No" << endl;
	}
}

Measured memory_bytes: 640
#define _USE_MATH_DEFINES
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>
#include<map>
#include<stdbool.h>
#include<math.h>
#include<sstream>
#include<math.h>
#include<vector>
#include<functional>
#include<queue>
#include<utility>
#include<bitset>
typedef long long ll;
#define N (1000000000+7)
#define INF 1e10
using namespace std;
typedef pair<ll, ll> P;

int main(void) {
	ll n;
	cin >> n;
	vector<ll>a(n);
	for (ll i = 0;i < n;i++)cin >> a[i];
	ll ans = 0;
	for (ll i = 0;i < n;i++) {
		while (a[i] % 2 == 0) {
			ans++;
			a[i] = a[i] / 2;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 384
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define reps(i,a,b) for(int i=a;i<b;++i)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U &u,const V... v){for(auto &e:u)fill_v<T>(e,v...);}

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

    string s, t, u;
    cin >> s >> t >> u;
    int now = 0;
    map<char, int> mp;
    mp['a'] = 0;
    mp['b'] = 1;
    mp['c'] = 2;
    while (true) {
        if (now == 0) {
            if (sz(s) == 0) {
                puts("A");
                return 0;
            }
            now = mp[s[0]];
            s = s.substr(1, sz(s)-1);
        } else if (now == 1) {
            if (sz(t) == 0) {
                puts("B");
                return 0;
            }
            now = mp[t[0]];
            t = t.substr(1, sz(t)-1);
        } else {
            if (sz(u) == 0) {
                puts("C");
                return 0;
            }
            now = mp[u[0]];
            u = u.substr(1, sz(u)-1);
        }
    }
}


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

// @@ !! LIM(f:gcd)
// --> f:gcd
// ---- inserted function gcd from util.cc
// g = eGCD(a, b, s, t)  --->  sa + tb = g
ll eGCD(ll a, ll b, ll& s, ll& t) {
  if (a == 0) {
    s = 0;
    t = 1;
    return b;
  }
  ll u = 0;
  ll g = eGCD(b % a, a, t, u);
  s = u - (b / a) * t;
  return g;
}

// gcd(0, x) = x, gcd(-x, y) = gcd(x, y)
ll gcd(ll a, ll b) {
  ll dummy1 = 0;
  ll dummy2 = 0;
  return eGCD(abs(a), abs(b), dummy1, dummy2);
}
// ---- end gcd
// @@ !! LIM  -- end mark --

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N; cin >> N;
  vector<ll> T(N);
  for (ll i = 0; i < N; i++) {
    cin >> T.at(i);
  }
  if (N == 1) {
    cout << T.at(0) << endl;
    return 0;
  }
  ll x = T.at(0);
  for (ll i = 1; i < N; i++) {
    ll g = gcd(x, T.at(i));
    x = x / g * T.at(i);
  }
  cout << x << endl;

  return 0;
}



Measured memory_bytes: 256