akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    
    for(int i = 1;i <= n; i++){
        int x = i;
        if(x%3 == 0) {
            cout << " " << i;
        
        }else{
            while(x){
                if(x%10 == 3){
                    cout << " " << i;
                    break;
                
                }
                x /= 10;
            }
        }
    }
    
    cout << endl;
    
    return 0;
}


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

#define lli long long
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define rep0(i,j) for(lli i=0;i<j;i++)
#define rep1(i,j) for(lli i=1;i<=j;i++)
#define rep0d(i,j) for(lli i=j-1;i>=0;i--)
#define MAX 1000000007

using namespace std;


bool cmpf(pair<lli, lli> left, pair<lli, lli> right) {
	return left.first < right.first;
}


int main() {
	lli n;
	string s;
	cin >> n ;
	cin >> s;
	if (n >= 3200)cout << s;
	else cout << "red";
}


Measured memory_bytes: 256
import sys
A =[list(map(int, input().split())) for _ in range(3)]
N = int(input())
b = [int(input()) for _ in range(N)]

for n in b:
    for i in range(3):
        for j in range(3):
            if n == A[i][j]:
                A[i][j] = 0

if A[0][0] == 0:
    if A[0][1] == 0 and A[0][2] == 0:
        print('Yes')
        sys.exit()
    if A[1][0] == 0 and A[2][0] == 0:
        print('Yes')
        sys.exit()
    if A[1][1] == 0 and A[2][2] == 0:
        print('Yes')
        sys.exit()
if A[0][1] == 0:
    if A[1][1] == 0 and A[2][1] == 0:
        print('Yes')
        sys.exit()
if A[0][2] == 0:
    if A[1][2] == 0 and A[2][2] == 0:
        print('Yes')
        sys.exit()
    if A[1][1] == 0 and A[2][0] == 0:
        print('Yes')
        sys.exit()
if A[1][0] == 0:
    if A[1][1] == 0 and A[1][2] == 0:
        print('Yes')
        sys.exit()
if A[2][0] == 0:
    if A[2][1] == 0 and A[2][2] == 0:
        print('Yes')
        sys.exit()
print('No')

Measured memory_bytes: 3188
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class disjointset
{
public:
	vector<int> rank;
	vector<int> p;
	
	void makeset(int x)
	{
		p[x]=x;
		rank[x]=0;
		return;
	}
	disjointset(int s)
	{
		rank.resize(s);
		p.resize(s);
		for(int i=0;i<s;i++)makeset(i);
		return;
	}
	int findset(int x)
	{
		if(x!=p[x])p[x]=findset(p[x]);
		return p[x];
	}
	void link(int x,int y)
	{
		if(rank[x]>rank[y])p[y]=x;
		else
		{
			p[x]=y;
			if(rank[x]==rank[y])rank[y]++;
		}
		return;
	}
	bool same(int x,int y)
	{
		return findset(x)==findset(y);
	}
	void unite(int x,int y)
	{
		link(findset(x),findset(y));
		return;
	}
};

class buin
{
public:
	int a,b,c;
	bool d;
};

int main()
{
	int aa,bb,cc;
	while(cin>>aa>>bb>>cc,aa){
	disjointset d=disjointset(aa+bb+cc+2);
	int s=0,t=aa+bb+cc+1;
	buin f[1000];
	int n;cin>>n;
	int dd;
	for(int i=0;i<n;i++)
	{
		cin>>f[i].a>>f[i].b>>f[i].c>>dd;
		if(dd==1)f[i].d=true;
		else f[i].d=false;
	}
	for(int i=0;i<n;i++)
	{
		if(f[i].d)
		{
			d.unite(s,f[i].a);
			d.unite(s,f[i].b);
			d.unite(s,f[i].c);
		}
	}
	for(int i=0;i<n;i++)
	{
		if(!f[i].d)
		{
			if(d.same(s,f[i].a)&&d.same(s,f[i].b))d.unite(t,f[i].c);
			if(d.same(s,f[i].a)&&d.same(s,f[i].c))d.unite(t,f[i].b);
			if(d.same(s,f[i].b)&&d.same(s,f[i].c))d.unite(t,f[i].a);
		}
	}
	for(int i=s+1;i<t;i++)
	{
		if(d.same(s,i))cout<<1<<endl;
		else if(d.same(t,i))cout<<0<<endl;
		else cout<<2<<endl;
	}}
	return 0;
}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	uint64_t n; cin>>n;
	uint64_t ans=1e9;
	for(uint64_t i=1;i*i<=n;++i){
		if(n%i==0){
			string a=to_string(i),b=to_string(n/i);
			ans=min(ans,max(a.size(),b.size()));
		}
	}
	cout<<ans<<"\n"s;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

static const int MAX = 100;
static const int INFTY = (1<<21);
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[MAX][MAX];

void dijkstra(){
    int minv;
    int d[MAX], color[MAX];

    for(int i=0; i<n; i++){
        d[i] = INFTY;
        color[i] = WHITE;
    }

    d[0] = 0;
    color[0] = GRAY;

    while(1){
        minv = INFTY;
        int u = -1;
        for(int i=0; i<n; i++){
            if(minv > d[i] && color[i] != BLACK){
                u = i;
                minv = d[i];
            }
        }

        if(u == -1) break;
        
        color[u] = BLACK;

        for(int v=0; v<n; v++){
            if(color[v] != BLACK && M[u][v] != INFTY){
                if(d[v] > d[u] + M[u][v]){
                    d[v] = d[u] + M[u][v];
                    color[v] = GRAY;
                }
            }
        }
    }
    for(int i=0; i<n; i++){
        cout << i << " " << ((d[i] == INFTY) ? -1 : d[i]) << endl;
    }
}

int main(){
    cin >> n;

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            M[i][j] = INFTY;
        }
    }

    int k, c, u, v;
    for(int i=0; i<n; i++){
        cin >> u >> k;
        for(int j=0; j<k; j++){
            cin >> v >> c;
            M[u][v] = c;
        }
    }

    dijkstra();

    return 0;
}





Measured memory_bytes: 3148
#include "bits/stdc++.h"
#define MOD 1000000007
#define INF 11234567890
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int W, H, N, x[112], y[112], a[112];
int field[112][112], ans;

int main()
{
	in >> W >> H >> N;
	rep(i, N) { in >> x[i] >> y[i] >> a[i]; }

	rep(i, N)
	{
		if (a[i] == 1)
		{
			rep(k, H)
			{
				rep(l, x[i])
				{
					field[k][l] = 1;
				}
			}
		}
		if (a[i] == 2)
		{
			rep(k, H)
			{
				for (int l = x[i]; l < W; ++l)
				{
					field[k][l] = 1;
				}
			}
		}
		if (a[i] == 3)
		{
			rep(k, y[i])
			{
				rep(l, W)
				{
					field[k][l] = 1;
				}
			}
		}
		if (a[i] == 4)
		{
			for (int k = y[i]; k < W; ++k)
			{
				rep(l, W)
				{
					field[k][l] = 1;
				}
			}
		}
	}

	rep(i, H)
	{
		rep(j, W)
		{
			if (field[i][j] == 0) { ++ans; }
		}
	}

	out << ans << std::endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define REP(X, Y, Z) for (ll(X) = (Y); (X) < (Z); (X)++)
#define REV(X, Y, Z) for (ll(X) = (Y); (X) > (Z); (X)--)

using namespace std;
using ll = long long;
using dll = deque<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using usll = unordered_set<ll>;
using umll = unordered_map<ll, ll>;
using sll = stack<int>;
using vll = vector<ll>;
using vvll = vector<vll>;

constexpr ll kMod = 1e9 + 7;

ll gcd(ll a, ll b) {
  if (a < b) {
    return gcd(b, a);
  }
  ll c = a % b;
  while (c != 0) {
    a = b;
    b = c;
    c = a % b;
  }
  return b;
}

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

void init() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

int main() {
  init();

  ll H, W;
  cin >> H >> W;
  vector<vector<char>> A;
  REP(i, 0, H) {
    string s;
    cin >> s;
    vector<char> c(W);
    bool all_dot = true;
    REP(j, 0, s.size()) {
      c[j] = s[j];
      if (c[j] == '#') {
        all_dot = false;
      }
    }
    if (!all_dot) {
      A.emplace_back(c);
    }
  }

  vll h_ok(A.size(), 0);
  vll w_ok(A[0].size(), 0);
  REP(i, 0, A.size()) {
    REP(j, 0, A[0].size()) {
      if (A[i][j] == '#') {
        h_ok[i] = 1;
        w_ok[j] = 1;
      }
    }
  }

  REP(i, 0, A.size()) {
    if (!h_ok[i]) { continue; }
    REP(j, 0, A[i].size()) {
      if (!w_ok[j]) { continue; }
      cout << A[i][j];
    }
    cout << endl;
  }

  return 0;
}


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



int main(){
     string s;
     cin >> s;
     sort(s.begin(),s.end());
     if(s=="abc") cout <<"Yes" <<endl;
     else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define endl '\n'
#define INF (1 << 21)
const int MOD = 1000000007;
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int s[4] = {6000, 4000, 3000, 2000};
  int t, n;
  
  for(int i = 0;i < 4;i++){
    cin >> t >> n;
    cout << s[t - 1] * n << endl;
  }
  return 0;
}




Measured memory_bytes: 3132
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<numeric>
#include<math.h>
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    ll ans = 1;
    map<char, int> mp;
    rep(i, n) {
        ++mp[s[i]];
    }
    for ( auto tmp_mp : mp ) {
        ans = ans * ( tmp_mp.second + 1 ) % mod;
    }
//    rep(i, n) {
//        map<char, int> mp;
//        for ( int j = i; j < n; ++j ) {
//            if ( s[j] == s[i] ) continue;
//            ++mp[s[j]];
//        }
//        int cnt1 = 0;
//        int cnt2 = 1;
//        for ( auto tmp_mp : mp ) {
//            if ( tmp_mp.second == 1 ) {
//                ++cnt1;
//            }
//            else if ( tmp_mp.second >= 2 ) {
//                cnt2 = ( cnt2 * ( tmp_mp.second + 1 ) ) % mod;
//            }
//        }
//        ll tmp_num = 1;
//        rep(j, cnt1) {
//            tmp_num = ( tmp_num * 2 ) % mod;
//        }
//        ans = ( ans + ( tmp_num * cnt2 ) % mod ) % mod;
//    }
    cout << ans - 1 << endl;
    return 0;
}


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

using namespace std;

const int N = 2e5 + 7 ; 
int n , m, K ; 
int sol = N ;
int a[11][1111];


int solve(vector<int> v)
{

    vector<int> par(v.size() , 0) ; 

    v.push_back(n);

    int ret = 0 ; 

    for(int i = 0 ; i < m ; i++){
        int k = 0 ; 
        bool ok = 0;
        vector<int> npar(v.size() , 0 );
        for(int j =0 ; j < n ; j++){
            if(j==v[k+1]){
                k++;
            }
            npar[ k ]+=a[j][i];
        }
        for(int j = 0 ; j< v.size()-1;j++){
            if( npar[j] > K )
                return N ; 
            if(npar[j] + par[j] > K){
                ok = 1;
            }
        }
        for(int j = 0 ; j < v.size() -1 ; j++){
            if(ok)par[j] = npar[j] ; 
            else par[j] +=npar[j] ; 
        }
        if(ok)ret++;
    }
    return ret ; 
}

int main(){
  // freopen("in.in" , "r" , stdin); 
   cin>>n>>m>>K ; 
   for(int i = 0 ; i < n ;i ++){
       string s ; 
       cin>>s ; 
       for(int j = 0 ; j < m ;j++)
       {
           a[i][j] = s[j] -'0' ; 
       }
   }
    for(int i= 1 ; i< (1<< n ) ; i++){
        int l = 0;
        int now = 0 ; 
        vector<int> v = {0} ; 
        for(int j =1 ; j < n ;j++){
            if( i&(1<<j)  ){
                v.push_back(j);
            }   
        }
        now =solve(v) ;
        sol = min(sol , now + (int)v.size() -1 ) ;

    }

    cout<<sol; 
    return 0 ;
}

Measured memory_bytes: 256
### main

loop do
  n, s, w, q = gets.split.map(&:to_i)
  break if (n | s | w | q) == 0

  ais = n.times.map{0}
  g = s
  for i in (0...n)
    ais[i] = (g / 7) % 10
    g = (g % 2 == 0) ? g / 2 : (g / 2) ^ w
  end  

  if q == 2 || q == 5
    nzs = 0
    count = 0
    for i in (0...n)
      nzs += 1 if ais[i] != 0
      count += nzs if ais[i] % q == 0
    end

    puts count
    next
  end
  
  mds = (n + 1).times.map{0}
  tmd = 1

  (n - 1).downto(0) do |i|
    mds[i] = (ais[i] * tmd + mds[i + 1]) % q
    tmd = (tmd * 10) % q
  end

  chash = Hash.new{0}
  chash[0] = 1
  count = 0
  
  (n - 1).downto(0) do |i|
    mdi = mds[i]
    if ais[i] != 0 && chash.include?(mdi)
      count += chash[mdi]
    end
    chash[mdi] += 1
  end
  
  puts count
end

Measured memory_bytes: 22084
from collections import deque
N = int(input())
A = [list(map(int,input().split())) for _ in range(2)]
Q = deque([(0,0,A[0][0])])
ans = 0
while Q:
    x,y,d = Q.popleft()
    if x == 1 and y == N-1:
        ans = max(ans,d)
        continue
    for dx,dy in [(0,1),(1,0)]:
        if x+dx <= 1 and y+dy <= N-1:
            Q.append((x+dx,y+dy,d+A[x+dx][y+dy]))
print(ans)


Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,a[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x;scanf("%d",&x);a[x]=i;
    }
    int ans=0,t=1;
    for(int i=2;i<=n;i++)
        if(a[i]>a[i-1]) t++;
    else
        ans=max(ans,t),t=1;
    ans=max(ans,t);
    printf("%d\n",n-ans);
}


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

int n,cnt=0;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin>>n;
	while(n>0){
		if(n%10==2)
			cnt++;
		n/=10;
	}
	cout<<cnt;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <typeinfo>
#define _USE_MATH_DEFINES
#include <cmath>

using namespace std;

int Min(int a, int b) {
    if (a < b) {
        return a;
    }
    return b;
}

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

    int v1, v2;
    cin >> v1 >> v2;
    int cost = v2 - v1;
    int min = Min(v1, v2);

    for (int i = 2; i < n; i++) {
        int tmp;
        cin >> tmp;
        if (tmp < min) {
            min = tmp;
        } else {
            if (cost < tmp - min) {
                cost = tmp - min;
            }
        }
    }
    cout << cost << endl;
}



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

int main() {
    int n;
    cin>>n;
    vector<int> a(n);
    rep(i,n) cin>>a[i];
    vector<size_t> indices(a.size());
    iota(indices.begin(),indices.end(),0);

    sort(indices.begin(),indices.end(),[&a](size_t i1,size_t i2) {
        return a[i1] < a[i2];
    });

    for (auto v: indices)
        cout<<v+1<<" ";
    cout<<endl;
}

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

int main() {
	string S;
	int ans = 0, count = 0;
	cin >> S;
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == 'A' || S[i] == 'C' || S[i] == 'G' || S[i] == 'T') count++;
		else count = 0;
		ans = max(ans, count);
	}
	cout << ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18
#define PI 3.14159265358979

using namespace std;

int main(void){
  int n, k;
  cin >> n >> k;

  int ret = 0;

  while (n > 0){
    n /= k;

    ret++;
  }


  cout << ret << endl;
  

  return 0;
}


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

int main()
{
	int n, t, a; cin >> n >> t >> a;

	vector<int> h(n);

	double tmp;
	double minimum = 1.797693e+308;
	int ans;
	for (int i = 0; i < n; i++) {
		cin >> h[i];
		double tmp = t - h[i] * 0.006;
		if (abs(a - tmp) < minimum ) {
			minimum = abs(a - tmp);
			ans = i + 1;
		}
	}
	
	cout << ans << endl;
		
	return 0;
}

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

#define INF 0x7fffffff
#define REP(i,j,k) for(int i = j;i <= k;i++)
#define squr(x) (x) * (x)
#define lowbit(x) (x&(-x))
typedef long long LL;

using namespace std;

const int MAXN = 100000 + 10;
const LL MO = 1e9 + 7;

int n;
int a[MAXN], b[MAXN];
LL ans = 1;
int numa, numb;

int main(int argc, const char * argv[]) {
    cin >> n;
    REP(i, 1, n) {
        cin >> a[i];
    }
    REP(i, 1, n) {
        cin >> b[i];
    }
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);
    
    
    int j = 1, k = 1;
    while (j <= n || k <= n) {
        if (k > n || (j <= n && a[j] < b[k])) {
            j++;
            if (numb == 0) {
                numa++;
            } else {
                ans = ans * (LL)numb % MO;
                numb--;
            }
        } else {
            k++;
            if (numa == 0) {
                numb++;
            } else {
                ans = ans * (LL)numa % MO;
                numa--;
            }
        }
        //cout << numa << " " << numb << endl;
    }
    cout << ans << endl;
    return 0;
}










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

const long long INF = 1LL << 60;
const int MOD = (int)1e9 + 7;
typedef long long ll;
//約数列挙
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    //sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}
vector<int> dx={1,0,-1,0};vector<int> dy={0,-1,0,1};

signed main () {
    int m;scanf("%d",&m);
    vector<vector<int>> cost(m+1,vector<int>(m+1));
    vector<int> p(m+1);
    FOR(i,1,m+1){
        int a,b;scanf("%d %d",&a,&b);
        p[i-1] = a;p[i]=b;
    }
    REP(i,m)cost[i][i] = 0;
    int min_cost;
    for (int l = 2; l <= m; l++) {  // 行列の個数
        for (int i = 1; i <= m - l + 1; i++) {
            int j = i + l - 1;
            for (int k = i; k < j; k++) {
                if (k == i) min_cost = cost[i][k] + cost[k+1][j] + p[i-1] * p[k] * p[j];
                else min_cost = min(min_cost, cost[i][k] + cost[k+1][j] + p[i-1] * p[k] * p[j]);
            }
            cost[i][j] = min_cost;
        }
    }
    cout << cost[1][m] << endl;
}


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

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

  if (a == b) {
    cout << c << endl;
  } else if (b == c) {
    cout << a << endl;
  } else {
    cout << b << endl;
  }
}

Measured memory_bytes: 256
/*
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
//#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl
#define debug false

ll pow_mod(ll a,ll b){
  if(b==0){
    return 1;
  }
  else if(b%2==1){
    return (a*pow_mod(a,b-1))%MOD;
  }
  else{
    return (pow_mod(a,b/2)*pow_mod(a,b/2))%MOD;
  }
}

signed main(void){
    int N;
    cin >> N;
    REP(i,N){
        int t = pow_mod(2,MOD-2);
    }
    cout << pow_mod(2,MOD-2);
    return 0;
}
*/


#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

ll pow_mod(ll a,ll b){
  if(b==0){
    return 1;
  }
  else if(b%2==1){
    return (a*pow_mod(a,b-1))%MOD;
  }
  else{
    ll t=pow_mod(a,b/2);
    return t*t%MOD;
  }
}

vector<ll> memo(200000,-1);
ll cnt_gcd(ll a,ll k,ll n){

  if(memo[a]!=-1){
    return memo[a];
  }
  ll b=pow_mod((k/a),n);
  ll i=1;
  while(a+a*i<=k){
    b =(b-cnt_gcd(a+a*i,k,n))%MOD;
    i++;
  }
  memo[a]=b%MOD;
  return b%MOD;
}
  
int main() {
  ll n,k;
  cin >> n >> k;
  ll ans=0;
  for(ll i=k;i>=1;i--){
    ans=(ans+i*(cnt_gcd(i,k,n)))%MOD;
  }
  cout << (ans+MOD)%MOD << endl;
}




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

public class Main {

  void solve(InputReader in, PrintWriter out) {
    out.println((1 + in.nextInt()) / 2);
  }

  public static void main(String[] args) throws Exception {
    InputReader in = new InputReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    Main solver = new Main();
    solver.solve(in, out);
    out.close();
  }

  static class InputReader {
    BufferedReader in;
    StringTokenizer st;

    public InputReader(InputStream is) {
      in = new BufferedReader(new InputStreamReader(is));
    }

    public String next() {
      try {
        while (st == null || !st.hasMoreTokens()) {
          st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }

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

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


Measured memory_bytes: 21076
use proconio::input;
use proconio::marker::{Chars, Usize1};
use std::iter::Iterator;
use std::collections::*;
use std::cmp::*;
use itertools::Itertools;

#[allow(unused_macros)]
macro_rules! max {
    ($x:expr) => {
      $x
    };
    ($x:expr, $($xs:tt)+) => {
      max($x,max!($($xs)+))
    };
  }
  
  #[allow(unused_macros)]
  macro_rules! min {
    ($x:expr) => {
      $x
    };
    ($x:expr, $($xs:tt)+) => {
      min($x,min!($($xs)+))
    };
  }

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    input! {
    b: char,
    }

    if b == 'A' {
      println!("T");
    }else if b == 'T' {
      println!("A");
    }else if b == 'C'{
      println!("G");
    }else {
      println!("C");
    }
    
}


Measured memory_bytes: 2076
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

int main(){
    int N;

    cin >> N;

    vector<int> v(N);

    for(int i = 0; i < N; i ++){
        cin >> v[i];
    }
    sort(v.begin(), v.end());

    double new_guzai = 0.5 * (v[0] + v[1]);

    for(int i = 2; i < N; i ++){
        new_guzai = 0.5 * (new_guzai + v[i]);
    }

    cout << fixed;
    cout << setprecision(6) << new_guzai << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<string.h>
#include<math.h>
#include<stdio.h>
#include<queue>
#include<utility>
#include<cstdio>
#include<cstring>
#include<new>
#include<float.h>
#include"ctype.h"
#include<cfloat>
#include<cmath>
#include<cctype>
#include<errno.h>
#include<cerrno>
#include<memory>
#include<memory.h>
#include<assert.h>
#include<cassert>
#include<deque>
#include<sstream>
#define fo(i,w,n) for(int i=(int) w;i<(int) n;i++)
#define qui queue<int>
#define vi vector<int>
#define ll long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define mp make_pair
#define sz size()
#define em empty()
#define ct continue
#define ms multiset
#define all(a) (a).begin(),(a).end()
#define pf push_front
#define ppf pop_front()
#define fi first
#define se second
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,a[101010],b[101010],c[101010];
int main()
{
	cin>>n;
	mem(b,0);
	mem(c,0);
	fo(i,0,n)cin>>a[i];
	for(int i=0;i<n;i+=2)b[a[i]]++;
	for(int i=1;i<n;i+=2)c[a[i]]++;
	int u=0,v=0,y=0,z=0;
	vi l,m;
	fo(i,0,101010)
	if(b[i]>u){
		u=b[i];
		l.clear();
		l.pb(i);
		y=0;
	}
	else if(b[i]==u){
		l.pb(i);
		y=1;
	}
	else y=0;
	fo(i,0,101010)
	if(c[i]>v){
		v=c[i];
		m.clear();
		m.pb(i);
		z=0;
	}
	else if(c[i]==v){
		m.pb(i);
		z=1;
	}
	else z=0;
	if(y||z||l[0]!=m[0]){
		cout<<n-u-v<<endl;
		return 0;
	}
	int ans=0,ans2=0;
	fo(i,0,101010)if(i!=l[0]){
		ans=max(ans,b[i]);
		ans2=max(ans2,c[i]);
	}
	cout<<min(n-u-ans2,n-v-ans)<<endl;
	return 0;
}


Measured memory_bytes: 2168
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <tuple>
//#include <bits/stdc++.h>
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define FORR(i,i0,n) for(int (i)=(n)-1; (i)>=(i0);(i)--)
#define SORT(x) sort(x.begin(),x.end())
#define rn return
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
typedef std::pair<int,int> P;
using namespace std;
using ll = long long;



int main(){
    int h,w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i,h) cin >> s[i];
    vector<vector<int>> dp(h,vector<int>(w,0));
    
    if (s[0][0] == '#') dp[0][0] = 1;
    else dp[0][0] = 0;
    
    FOR(i,1,w){
        if (s[0][i-1] == '#' && s[0][i] == '#'){
            dp[0][i] = dp[0][i-1];
        }
        else if (s[0][i-1] == '.' && s[0][i] == '#'){
            dp[0][i] = dp[0][i-1] + 1;
        }
        else if (s[0][i] == '.' ){
            dp[0][i] = dp[0][i-1];
        }
    }
    
    FOR(i,1,h){
        if (s[i-1][0] == '#' && s[i][0] == '#'){
            dp[i][0] = dp[i-1][0];
        }
        else if (s[i-1][0] == '.' && s[i][0] == '#'){
            dp[i][0] = dp[i-1][0] + 1;
        }
        else if (s[i][0] == '.' ){
            dp[i][0] = dp[i-1][0];
        }
    }
    
    FOR(i,0,h) {
        //FOR(j,0,w) cout << dp[i][j] << " ";
        //cout << endl;
    }
    
    
    FOR(i,1,h) FOR(j,1,w){
        if (s[i][j] == '.'){
            dp[i][j] = min(dp[i-1][j],dp[i][j-1]);
        }
        else{
            int cand1 = 0;
            int cand2 = 0;
            
            if (s[i-1][j] == '#') cand1 = dp[i-1][j];
            else cand1 = dp[i-1][j] + 1;
            
            if (s[i][j-1] == '#') cand2 = dp[i][j-1];
            else cand2 = dp[i][j-1] + 1;
            
            //cout << i << j << " " << cand1 << " "  << cand2 << endl;
            dp[i][j] = min(cand2,cand1);
        }
    }
    
    cout << dp[h-1][w-1];
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int w,h,x,y,r;
  cin >> w >> h >> x >> y >> r;
  if(x<r||x>w-r||y<r||y>h-r){
    cout << "No" <<endl;
  }else{
    cout << "Yes" <<endl;
  }
}



Measured memory_bytes: 3112
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,K = map(int,input().split())
A = list(map(int,input().split()))

# B[i] : i桁目が 1 になっているAの要素数
B = [0] * 40
for a in A:
    for i in range(40):
        if a&(1<<i):
            B[i] += 1

# K以下の条件を無視した場合の, 最適な X
# これは桁ごとに最適値を調べれば良い
X = [0]*40
for i in range(40):
    if B[i] <= N/2:
        X[i] = 1

# K を X に合わせた表現にする
bitK = list(map(int, list(bin(K)[2:].zfill(40)[::-1])))

# 初期値はKと一致した場合にしておく
ans = 0
for i in range(40):
    if bitK[i]==1:
        ans += (N-B[i])<<i
    else:
        ans += B[i]<<i

# Kと不一致になる最上位の桁
for k in range(40):
    # 0の桁で不一致になることはあり得ない
    if bitK[k]==0:
        continue

    total = 0
    leqK = False 
    for i in range(39,-1,-1):
        # K以下が確定しているなら, 貪欲に最適値をとる
        if leqK:
            if X[i]==1:
                total += (N-B[i])<<i
            else:
                total += B[i]<<i
        # そうでないなら
        else:
            # Kと不一致になる最上位の桁 であるなら, X の該当桁を 0 として不一致にする
            if i==k:
                total += B[i]<<i
                leqK = True
            # Kと一致している
            else:
                if bitK[i]==1:
                    total += (N-B[i])<<i
                else:
                    total += B[i]<<i
    ans = max(total,ans)

print(ans)

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

#define MAXN (100010)
#define ll long long

int n, root, minsz;
std::vector<std::pair<int, int> > vec[MAXN];
int sz[MAXN];
ll ans;
bool two_cen;

void dfs(int u, int fa){
	sz[u] = 1;
	int nowsz = 0;
	for(auto p : vec[u]){
		int v = p.first, w = p.second;
		if(v == fa) continue;
		dfs(v, u);
		sz[u] += sz[v];
		nowsz = std::max(nowsz, sz[v]);
		
		int k = std::min(sz[v], n - sz[v]);
		ans += 2ll * k * w;
		
		if(k == n - k){
			two_cen = true;
			ans -= w;
		}
	}
	nowsz = std::max(nowsz, n - sz[u]);
	if(minsz > nowsz){
		minsz = nowsz;
		root = u;
	}
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i < n; ++ i){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		vec[a].push_back({b, c});
		vec[b].push_back({a, c});
	}
	minsz = INT_MAX;
	dfs(1, 0);
	
	if(!two_cen){
		int minw = INT_MAX;
		for(auto p : vec[root]){
			minw = std::min(minw, p.second);
		}
		ans -= minw;
	}
			
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 12800
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define mk make_pair
#define fi first
#define se second
using namespace std;
struct B{
  int size;
  vector<int> dat;
  void init(int n){
    size=n;
    dat.clear();
    dat.resize(n+1);
  }
  void Add(int i,int x){
    while(0<i&&i<=size)
      dat[i]+=x,i+=(i&-i);
  }
  int Sum(int i){
    int res=0;
    while(0<i)
      res+=dat[i],i-=(i&-i);
    return res;
  }
};
int main(){
  int n;
  while(cin>>n,n){
    int ans=0;
    vector<int>v[1001];
    for(int i=0;i<n;i++){
      int pp=0,m,d,h,ss,t;
      scanf("%d/%d %d:%d",&m,&d,&h,&ss);
      pp=m*40*24*60+d*24*60+h*60+ss;
      string s1,s2;
      cin>>s1>>t;
      v[t].push_back(pp);
    }
    for(int o=1;o<1001;o++)if(v[o].size()){
      B A,B;
      A.init(900000);
      B.init(900000);
      for(int i=0;i<v[o].size();i+=2){
	int ss=v[o][i],tt=v[o][i+1];ss+=11,tt+=10;
	A.Add(ss,1);
        A.Add(tt,-1);
        B.Add(ss,(-1)*(ss-1));
        B.Add(tt,(ss-1) + (tt-ss+1) );
      }
      int sum=0;
      for(int i=0;i<v[0].size();i+=2){
	int ss=v[0][i],tt=v[0][i+1];ss+=10;tt+=10;
	sum+=A.Sum(tt)*tt+B.Sum(tt) - A.Sum(ss)*ss-B.Sum(ss);
      }
      ans=max(sum,ans);
    }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 10168
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Edge = [[] for _ in range(N)]
    EdgeK = [[] for _ in range(M)]
    for i in range(N):
        L = [int(j) for j in input().split()]
        for j in L[1:]:
            Edge[i].append(j - 1)
            EdgeK[j - 1].append(i)

    Visited = [False] * N
    VK = [False] * M
    q = deque()
    q.append((0, 0)) #node, person (0) or lang (1)

    while q:
        nN, nT = q.pop()
        if nT == 0: #person
            if not Visited[nN]:
                Visited[nN] = True
                for ne in Edge[nN]:
                    if not VK[ne]: q.append((ne, 1))
        else:
            if not VK[nN]:
                VK[nN] = True
                for ne in EdgeK[nN]:
                    if not Visited[ne]: q.append((ne, 0))
    if False in Visited: print("NO")
    else: print("YES")


    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 38124
// C.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <map>

using namespace std;

int main(int argc, char* argv[]) {
	int n;
	cin >> n;
	map<string, int> m;
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		m[s] += 1;
		cnt = max(cnt, m[s]);
	}
	for (auto kv : m) {
		if (kv.second == cnt) {
			cout << kv.first << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 25216
N, K = map(int, input().split())
L = []
for _ in range(K):
  a, b = map(int, input().split())
  L.append((a,b))
L.sort()
DP_1 = [0]*N
DP_2 = [0]*(N+1)
DP_1[0], DP_2[1] = 1, 1
mod = 998244353
for i in range(1, N):
  for l in L:
    if l[0]>i:
      break
    elif l[1]>i:
      DP_1[i] += DP_2[i-l[0]+1]
      DP_1[i] %= mod
    elif l[1]<=i:
      DP_1[i] += DP_2[i-l[0]+1]-DP_2[i-l[1]]
      DP_1[i] %= mod
  DP_2[i+1] = DP_2[i] + DP_1[i]
  DP_2[i+1] %= mod
print(DP_1[-1]%mod)

Measured memory_bytes: 24640
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <complex>
#include <ctime>
#include <cstdlib>

using namespace std;

inline int to_int(string s) {int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string to_str(T x) {ostringstream sout; sout << x; return sout.str();}

typedef long long ll;

int main()
{
	int L[16];
	int sum;
	int v1, v2;
	double crush;
	int ans;
	while(scanf("%d",&L[0]) != EOF)
	{
		sum = L[0];
		for(int i = 1; i < 10; i++)
		{
			scanf(",%d",&L[i]);
			sum += L[i];
		}
		scanf(",%d,%d", &v1, &v2);

		crush = sum * (v1 * 1.0/(v1+v2) );

		for(int i = 0; i < 10; i++)
		{
			crush -= L[i];
			if(crush <= 0)
			{
				ans = i+1;
				break;
			}
		}
		cout << ans << endl;
	} 
}

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

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

char ma[30][30];

int W,H;
int dfs(int nx,int ny){
	if(ma[ny][nx]=='#')return 0;
	ma[ny][nx]='#';
	int re=1;
	for(int i=0;i<4;i++){
		int nex=nx+dx[i],ney=ny+dy[i];
		if(nex>=0 && ney>=0 && nex<W && ney<H)re+=dfs(nex,ney);
	}
	return re;
}


int main(){
	int sx,sy;
	while(cin>>W>>H && W+H){
		for(int i=0;i<H;i++)for(int j=0;j<W;j++){
			cin>>ma[i][j];
			if(ma[i][j]=='@'){sx=j,sy=i;}
		}
		cout<<dfs(sx,sy)<<endl;
	}
	
}

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

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

    vector<vector<int>> connectedRoomsVec(n + 1);

    connectedRoomsVec.at(0).push_back(1);

    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;

        connectedRoomsVec.at(a).push_back(b);
        connectedRoomsVec.at(b).push_back(a);
    }

    deque<pair<int, int>> roomsDeque = {make_pair(0, 1)};
    map<int, int> signInRoomMap;

    bool isPossible = true;

    while (1)
    {
        pair<int, int> nowRoom = roomsDeque.front();
        roomsDeque.pop_front();

        if (!signInRoomMap.count(nowRoom.second))
        {
            // もしまだ参照してなかったら、

            // この部屋の前に来たところを看板に書く
            signInRoomMap.insert(make_pair(nowRoom.second, nowRoom.first));

            // 次に行く部屋は今いる部屋からつながっている部屋
            for (const int &singleNextRoom : connectedRoomsVec.at(nowRoom.second))
            {
                roomsDeque.push_back(make_pair(nowRoom.second, singleNextRoom));
            }
        }
        else
        {
            // もしもう来てたらスルー
            continue;
        }

        // もし全ての部屋に看板書いたらおしまい
        if (signInRoomMap.size() == n)
        {
            break;
        }
        else if (roomsDeque.size() == 0)
        {
            isPossible = false;
            break;
        }
    }

    if (isPossible)
    {
        cout << "Yes" << endl;

        for (int roomNum = 2; roomNum <= n; ++roomNum)
        {
            cout << signInRoomMap.at(roomNum) << endl;
        }
    }
    else
    {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 16356
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  map<int, int> cnt;
  int ans = n;
  for(int i = 0; i < n; i++){
    int d;
    cin >> d;
    if(cnt[d] == 0)
      cnt[d]++;
    else
      ans--;
  }
  cout << ans << endl;
  return 0;
}

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

int main(){
    ll N; cin >> N;
    int cnt = 0;
    vector<int> P(N);
    rep(i, N) cin >> P[i];
    int mi = INF;
    for(int j=0; j<N; ++j){
        mi = min(mi, P[j]);
        if(mi==P[j]) cnt++;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;


void solve(long long N){
	cout << N*(N-1)/2-N/2 << endl;
	repn(i, N) {
		repn(j, N) {
			if (i >= j) continue;
			if (i+j != N+(N+1)%2) cout << i << " " << j << endl;
		}
	}
}

int main(){	
	long long N;
	scanf("%lld",&N);
	solve(N);
	return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAX_SIZE = 128;


using namespace std;

class Z
{
private:
  int size;
  char d[MAX_SIZE];
public:
  Z(char *s)
  {
    size = strlen(s);
    for(int i=0;i<MAX_SIZE - size;i++)
      d[i] = 0;
    for(int i=0,j=MAX_SIZE - size;j < MAX_SIZE; i++, j++)
      d[j] = s[i];
  }

  void add(Z r)
  {
    int tmp = max(this->size, r.size);
    int updigit = 0;
    for(int i=MAX_SIZE-1;i>=0;i--){
      int a = 0, b = 0;
      if(this->d[i] == 0 && r.d[i] == 0){
	if(updigit){
	  this->d[i] = '1';
	  tmp++;
	}
	goto end;
      }else{
	if(this->d[i])
	  a = this->d[i] - '0';
	if(r.d[i])
	  b = r.d[i] - '0';
	int n = a + b + updigit;
	updigit = n / 10;
	this->d[i] = (n % 10)+'0';
      }
    }
  end:
    this->size = tmp;
    return;
  }

  void print()
  {
    if(this->size > 80){
      puts("overflow");
      return;
    }
    for(int i=MAX_SIZE - this->size;i<MAX_SIZE;i++)
	putchar(d[i]);
    puts("");
  }

  int sz()
  {
    return this->size;
  }
};

int main()
{
  int x;
  scanf("%d", &x);
  char s1[1000], s2[1000];  
  for(int i=0;i<x;i++){
    scanf("%s %s",s1, s2);
    if(strlen(s1) > 80 || strlen(s2) > 80){
      puts("overflow");
      continue;
    }
    Z z1(s1);
    Z z2(s2);
    z1.add(z2);
    z1.print();
  }
  return 0;
}

Measured memory_bytes: 1012
from collections import deque
S=input()
queue=deque()
lst=[]
lst.append([0,0])
for i in range(0,len(S)):
    l=len(lst)
    for _ in range(l):
        x,y=lst.pop(0)
        lst.append([x,y*10+int(S[i])])#plus
        lst.append([x+y*10+int(S[i]),0])
l=len(lst)
for _ in range(l):
    x,y=lst.pop(0)
    lst.append(x+y)
print(int(sum(lst)/2))


Measured memory_bytes: 3444
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author tatsumack
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>

#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

using namespace std;

typedef pair<int, int> P;

class BBalance {
public:
    static constexpr int kStressIterations = 0;

    static void generateTest(std::ostream& test) {
    }

    void solve(std::istream& cin, std::ostream& cout) {
        int N;
        cin >> N;
        vector<int> w(N);
        REP(i, N) cin >> w[i];


        int res = INF;
        REP(t, N) {
            int s1 = 0;
            FOR(i, 0, t) {
                s1 += w[i];
            }
            int s2 = 0;
            FOR(i, t + 1, N - 1) {
                s2 += w[i];
            }
            res = min(res, abs(s1 - s2));
        }
        cout << res << endl;

    }
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);

    BBalance solver;
    solver.solve(in, out);
    return 0;
}


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

using ll = long long;

bool isPrime(int n) {
    if (n == 1) return false;
    for (int i=2; i*i<=n; ++i){
        if (n % i == 0) return false;
    }
    return true;
}

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

    int x;
    cin >> x;
    int ans=0;
    for (int i=x; i<=100010;++i) {
        if (isPrime(i) == true) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;
#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e16;
const ll MOD = 1e9 + 7;
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define rep(i,N) FOR(i, 0, N)
#define ALL(s) (s).begin(), (s).end()
#define EQ(a, b) (abs((a) - (b)) < EPS)
#define EQV(a, b) (EQ((a).reeal(), (b).real) && EQ((a).imag(), (b).imag()))
#define NIL -1

ll g;
ll w;
ll d[100000];
char table[] = {'r','g','b'};

string myitos(ll num){
    string res = "";
    rep(i,w){
        res += table[num % 3];
        num /= 3;
    }
    reverse(ALL(res));
    return res;
}

ll mystoi(string s){
    ll res = 0;
    rep(i,s.size()){
        res *= 3;
        if(s[i] == 'g')res++;
        else if(s[i] == 'b')res += 2;
    }
    return res;
}

void dijkstra(ll start){
    fill(d,d+100000,INF);
    d[start] = 0;

    priority_queue<P,vector<P>,greater<P>> que;
    que.push(P(0,start));

    while(!que.empty()){
        P p = que.top();
        que.pop();
        ll v = p.second;
        ll cost = p.first;
        if(d[v] < cost)continue;
        // d[v] = cost;
        if(v == 0 || v == g || v == 2*g)continue;

        string now = myitos(v);

        rep(i,now.size() - 1){
            char c1 = now[i];
            char c2 = now[i+1];
            string t = now;
            if((c1 == 'r' && c2 == 'g') || (c1 == 'g' && c2 == 'r')){
                t[i] = 'b';
                t[i+1] = 'b';
            }
            if((c1 == 'g' && c2 == 'b') || (c1 == 'b' && c2 == 'g')){
                t[i] = 'r';
                t[i+1] = 'r';
            }
            if((c1 == 'b' && c2 == 'r') || (c1 == 'r' && c2 == 'b')){
                t[i] = 'g';
                t[i+1] = 'g';
            }
            ll to = mystoi(t);
            // cout << t << endl;
            if(d[to] > cost+1){
                d[to] = cost + 1;
                que.push(P(cost+1,to));
            }
        }

    }
}

string s;

int main(){
    while(cin >> s && s != "0"){
        int start = 0;
        w = s.size();
        g = 0;
        rep(i,s.size()){
            g *= 3;
            g++;
            int num = 0;
            if(s[i] == 'g')num++;
            if(s[i] == 'b')num += 2;
            start = 3*start + num;
        }
        // string t = myitos(start);
        // cout << t << endl;
        // cout << mystoi(t) << endl;
        // continue;
        dijkstra(start);
        ll ans = min(d[0],min(d[g],d[2*g]));
        if(ans == INF)cout << "NA" << endl;
        else cout << ans << endl;
    }
}


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

void addzero(int x){
  int cnt = 0,y=x;
  while(y>0){
    cnt ++;
    y /= 10;
  }
  for(int i=0;i<6-cnt;i++){
    cout << '0';
  }
  cout << x;
}

int main(){
  int N,M;cin >> N >> M;
  vector<int> P(M);
  vector<int> Y(M);
  vector<vector<pair<int,int>>> V(N);
  for(int i=0;i<M;i++){
    cin >> P[i] >> Y[i];
    pair<int,int> U = make_pair(Y[i],i);
    V[P[i]-1].push_back(U);
  }
  for(int i=0;i<N;i++){
    sort(V[i].begin(),V[i].end());
    for(int j=0;j<V[i].size();j++){
      Y[V[i][j].second] = j + 1;
    }
  }
  for(int i=0;i<M;i++){
    addzero(P[i]);
    addzero(Y[i]);
    cout << endl;
  }
}

Measured memory_bytes: 9400
#include<iostream>
#include<vector>
using namespace std;
int main(){
int M,N,i;
long long int P,X,sum[110],total=0;
cin>>N;
vector<int> T(N);
for(i=0;i<N;i++){
 cin>>T[i];
 total += T[i];
 }
cin>>M;
for(i=0;i<M;i++){
cin>>P>>X;
sum[i] = total -T[P-1] + X;
 }
for(i=0;i<M;i++){
cout<<sum[i]<<endl;
}
return 0;
}

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

struct Edge
{
  i64 cost, to;
};

int main()
{
  i64 n;
  cin >> n;
  vector<Edge> edge[n];
  for (i64 i = 0; i < n - 1; i++)
  {
    i64 a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    edge[a].push_back({c, b});
    edge[b].push_back({c, a});
  }
  i64 q, k;
  cin >> q >> k;
  k--;
  vector<i64> cost(n, 1e18);
  priority_queue<pair<i64, i64>> que;
  cost[k] = 0;
  que.push({0, k});
  while (que.size())
  {
    pair<i64, i64> p = que.top();
    que.pop();
    for (Edge i : edge[p.second])
      if (cost[p.second] + i.cost < cost[i.to])
      {
        cost[i.to] = cost[p.second] + i.cost;
        que.push({cost[i.to], i.to});
      }
  }
  for (i64 i = 0; i < q; i++)
  {
    i64 x, y;
    cin >> x >> y;
    x--;
    y--;
    cout << cost[x] + cost[y] << endl;
  }
  return 0;
}


Measured memory_bytes: 11136
//_nebula_
#include<bits/stdc++.h>
using namespace std;
#define int long  long
#define double long double
int t;
const int M=1e9+7;
const int inf=INT64_MAX;
int dp[100005][3];
int factt(int n)
{
    int ans=1;
    for(int i=1;i<=n;i++)
    {
        ans*=i;
        ans=ans%M;
    }
    return ans;
}
int max(int a,int b,int c)
{
    return max(a,max(b,c));
}
int min(int a,int b,int c)
{
    return min(a,min(b,c));
}
int fspow(int x,int y)
{
    int ans;
    if(y==0) return 1;
    ans=fspow(x, y/2);
    if(y%2==0)
    {
        if((double)ans>=sqrt((double)inf)) return 0;
        return (ans*ans);
    }
    if((double)ans>=sqrt((double)(inf/x))) return 0;
    return x*ans*ans;
}
int gcd(int x,int y)
{
    if(x<y) swap(x,y);
    if(y==0) return x;
    return gcd(x%y,y);
}
int p2(int x)
{
    int ans=0;
    while(x>=1)
    {
        ans++;
        x/=2;
    }
    return ans;
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    t=1;
    // freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    // cin>>t;
    // int tmp=t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        int h[n];
        for(int i=0;i<n;i++) cin>>h[i];
        int ans[100005]={0};
        for(int i=1;i<n;i++)
        {
            int cnt=1;
            int mn=inf;
            while(cnt<=k && i>=cnt)
            {
                int val=ans[i-cnt]+abs(h[i]-h[i-cnt]);
                mn=min(mn,val);
                cnt++;
            }
            ans[i]=mn;
        }
        cout<<ans[n-1]<<"\n";
    }
}


Measured memory_bytes: 5276
package main

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

func main() {
	S := ReadString()
	for i := 0; i < len(S); i++ {
		for j := i; j <= len(S); j++ {
			s := S[:i] + S[j:]
			if s == "keyence" {
				fmt.Println("YES")
				return
			}
		}
	}
	fmt.Println("NO")
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 2096