akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0; (i)<(n); (i)++)

typedef long long ll;

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

int main(){
	const int MOD=1e9+7;
	int n,a,b;
	cin >> n >> a >> b;

	ll x = 1;
	for(int i=n; i>n-a; i--){x = x * i % MOD;}
	ll t = 1;
	for(int i=a; i>0; i--){t = t * i % MOD; }
	ll y = power(t,MOD-2,MOD);
	ll A = x*y % MOD;

	x = 1;
	for(int i=n; i>n-b; i--){x = x * i % MOD;}
	t = 1;
	for(int i=b; i>0; i--){t = t * i % MOD;}
	y = power(t,MOD-2,MOD);
	ll B = x*y % MOD;

	ll C = (power(2,n,MOD) -1)%MOD;
	if(C<0)C=MOD+C;

	ll remove = (B+A) %MOD;
	ll ans = (C -remove) % MOD;
	if(ans<0)ans = MOD + ans; 
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
	int q=0;char ch=' ';
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
	return q;
}
typedef long long LL;
const int N=100005;
LL sum,nowadd,nows,a[N],orz[N],m;int n;
int work() {
	int js=0;
	for(RI i=0;i<n;++i) {
		int b=a[i]-a[(i-1+n)%n];
		if((m-b)%n||m-b<0) return 0;
		orz[i]=(m-b)/n,js+=orz[i];
	}
	if(js!=m) return 0;
	for(RI i=0;i<n;++i) {
		nows+=orz[i],nowadd+=nows;
		if(a[i]<nowadd) return 0;
		a[i]-=nowadd;
	}
	for(RI i=0;i<n;++i) {
		nows-=orz[i],nowadd-=1LL*n*orz[i],nowadd+=nows;
		if(a[i]!=nowadd) return 0;
	}
	return 1;
}
int main()
{
	n=read();
	for(RI i=0;i<n;++i) a[i]=read(),sum+=a[i];
	m=sum/(1LL*(n+1)*n/2);
	if(work()) puts("YES");
	else puts("NO");
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define VI vector<int>
#define VPII vector<PII>
#define LL long long
#define LD long double
#define f first
#define s second
#define MP make_pair
#define PB push_back
#define endl '\n'
#define ALL(c) (c).begin(), (c).end()
#define SIZ(c) (int)(c).size()
#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 FORD(i, b, e) for(int i = (b); i >= (int)(e); --i)

#define sim template<class n
sim, class s> ostream & operator << (ostream &p, pair<n, s> x)
{return p << "<" << x.f << ", " << x.s << ">";}
sim> auto operator << (ostream &p, n y) ->
typename enable_if<!is_same<n, string>::value, decltype(y.begin(), p)>::type 
{int o = 0; p << "{"; for(auto c: y) {if(o++) p << ", "; p << c;} return p << "}";}
void dor() {cerr << endl;}
sim, class...s> void dor(n p, s...y) {cerr << p << " "; dor(y...);}
sim, class s> void mini(n &p, s y) {if(p>y) p = y;}
sim, class s> void maxi(n &p, s y) {if(p<y) p = y;}
#ifdef DEB
#define debug(...) dor(__FUNCTION__, ":", __LINE__, ": ", __VA_ARGS__)
#else
#define debug(...)
#endif 

#define I(x) #x " =", (x), " "
#define A(a, i) #a "[" #i " =", i, "] =", a[i], " "
const int MXN = 104;

bool pal(string s)
  {
  string s2 = s;
  reverse(ALL(s2));
  return s == s2;
  }

int main()
{
  string s;
  cin >> s;
  int n = s.size();

  string s2 = s;
  reverse(ALL(s2));
  if(pal(s) == 0){puts("No"); return 0;}

  while(s.size() > (n-1)/2)s.pop_back();
  debug(s);
  if(pal(s) == 0){puts("No"); return 0;}
  puts("Yes");
}


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

#include <bits/stdc++.h>

using namespace std;

void solve(istream &in, ostream &out) {
    int n;
    in >> n;

    int mod = 1000'000'007;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        in >> a[i];
    }

    int res = 1;
    int cnt = 3;
    vector<int> m(n);
    for (int i = 0; i < n; ++i) {
        if (a[i] > 0) {
            res = ((long long) res * m[a[i] - 1]) % mod;
            --m[a[i] - 1];
            ++m[a[i]];
        } else {
            res = ((long long) res * cnt) % mod;
            --cnt;
            ++m[a[i]];
        }
    }

    out << res << '\n';
}


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


Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define all(v) begin(v), end(v)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 2000000000
#define int long long int

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};
int const MOD = 1000000007;
ll mod_pow(ll x, ll n) {return (!n)?1:(mod_pow((x*x)%MOD,n/2)*((n&1)?x:1))%MOD;}
int madd(int a, int b) {return (a + b) % MOD;}
int msub(int a, int b) {return (a - b + MOD) % MOD;}
int mmul(int a, int b) {return (a * b) % MOD;}
int minv(int a) {return mod_pow(a, MOD-2);}
int mdiv(int a, int b) {return mmul(a, minv(b));}

namespace std {
    bool operator<(const P& a, const P& b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

int w, h;
const int SIZE = 60;
char board[SIZE][SIZE];
int  paint[SIZE][SIZE];

void dfs(int x, int y, int color) {
    rep(i,0,4) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
        int &p = paint[nx][ny];
        if(board[nx][ny] != '.') continue;
        if(p == color || p == INF) continue;
        if(p == -1) p = color;
        else p = INF;
        dfs(nx, ny, color);
    }
}

signed main() {
    while(cin >> w >> h, w||h) {
        memset(paint, -1, sizeof(paint));
        rep(i,0,h) rep(j,0,w) cin >> board[i][j];
        rep(i,0,h) rep(j,0,w) {
            if(board[i][j] == 'W') dfs(i, j, 0);
            if(board[i][j] == 'B') dfs(i, j, 1);
        }

        int cntw = 0, cntb = 0;
        rep(i,0,h) rep(j,0,w) {
            if(paint[i][j] == 0) cntw++;
            else if(paint[i][j] == 1) cntb++;
        }
        printf("%lld %lld\n", cntb, cntw);
    }
    return 0;
}

Measured memory_bytes: 3208
#!/usr/bin/env python3
# atcoder 
# Türkçe konuşyorum
# Türkler var mı?
# memnün oldum
import sys
import math


sys.setrecursionlimit(10 ** 8)

#def divmin
#for i in range(d, 1, -1):
#    if(d % i == 0):
#        print(i)
def pgcd(a, b):
    while b!=0:
        a,b=b,a%b
    return a

def msum(a, b, c):
    if (a <= b) and (a <= c): 
        return math.gcd(a, math.gcd(b,c))
        #while(a >= 1):
        #    if (b % a == 0) and (c % a == 0):
        #        return a
            
    elif (b <= a) and (b <= c):
        return(math.gcd(b, math.gcd(a,c)))
    elif (c <= a) and (c <= b):
        return math.gcd(c, math.gcd(a,b))
    else:
        print("Grande érreur dans ta tête!!!")

def çözmek(num):
    csum = 0
    for i in range(1, num+1):
        for j in range(1, num+1):
            for l in range(1, num+1):
                #print(i,j,l)
                #csum += msum(i,j,l)
                csum += math.gcd(i, math.gcd(j,l))

    return csum


if __name__ == "__main__":
    K = int(input())
    print(çözmek(K))


Measured memory_bytes: 9300
(let ((n (read))
    (ans 0)
    (a 0)
    (b 0))
    (loop for i from 1 while (<= (* i i) n) do
        (if (zerop (rem n i))
        (progn
            (setq a i)
            (setq b (/ n i))
            (if (= ans 0)
                (setq ans (max (length (princ-to-string a)) (length (princ-to-string b))))
                (if (> ans (max (length (princ-to-string a)) (length (princ-to-string b))))
                    (setq ans (max (length (princ-to-string a)) (length (princ-to-string b))))
                )
            )
            (if (not (= (* i i) n))
                (progn
                    (setq a i)
                    (setq b (/ n i))
                    (if (> ans (max (length (princ-to-string a)) (length (princ-to-string b))))
                    (setq ans (max (length (princ-to-string a)) (length (princ-to-string b))))
                )
                )
            )
        )
        )
    )
    (princ ans)
)

Measured memory_bytes: 24628
//wrong answer
#include<iostream>
#include<algorithm>

using namespace std;

int abs(int m, int n)
{
	return m - n > 0 ? m - n : n - m;
}

struct data {
	int x;
	int y;
	int h;
}d[105];

int main()
{
	int N, node = -1;
	cin >> N;
	for (int i = 0;i < N;i++)
	{
		cin >> d[i].x >> d[i].y >> d[i].h;
		if (node == -1 && d[i].h != 0) node = i;
	}
	for (int i = 0;i < 101;i++)
		for (int j = 0;j < 101;j++)
		{
			int H = d[node].h + abs(d[node].x, i) + abs(d[node].y, j);
			int l = 0;
			for (int k = 0;k < N;k++)
			{
				if (max(0, H - abs(d[k].x, i) - abs(d[k].y, j)) == d[k].h) l++;
			}
			//		cout<<i<<" "<<j<<" "<<H;
			//	cout<<"  *  "<<l<<"   &  "<<N<<endl;
			if (l == N) {
				cout << i << " " << j << " " << H << endl;
				return 0;
			}
		}
	return 0;
}

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

long long n;
map<string, int> mp;

int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    ++mp[s];
  }
  cout << mp.size() << endl;
  return 0;
}

Measured memory_bytes: 19224
def main():
    import os
    import sys
    from io import BytesIO, IOBase
    
    BUFSIZE = 8192
    
    
    class FastIO(IOBase):
        newlines = 0
    
        def __init__(self, file):
            self._fd = file.fileno()
            self.buffer = BytesIO()
            self.writable = "x" in file.mode or "r" not in file.mode
            self.write = self.buffer.write if self.writable else None
    
        def read(self):
            while True:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                if not b:
                    break
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines = 0
            return self.buffer.read()
    
        def readline(self):
            while self.newlines == 0:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                self.newlines = b.count(b"\n") + (not b)
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines -= 1
            return self.buffer.readline()
    
        def flush(self):
            if self.writable:
                os.write(self._fd, self.buffer.getvalue())
                self.buffer.truncate(0), self.buffer.seek(0)
    
    
    class IOWrapper(IOBase):
        def __init__(self, file):
            self.buffer = FastIO(file)
            self.flush = self.buffer.flush
            self.writable = self.buffer.writable
            self.write = lambda s: self.buffer.write(s.encode("ascii"))
            self.read = lambda: self.buffer.read().decode("ascii")
            self.readline = lambda: self.buffer.readline().decode("ascii")
    
    
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
    input = lambda: sys.stdin.readline().rstrip("\r\n")
    mod = 10**9 + 7

    n, q = map(int, input().split())
    stx = []
    for _ in range(n):
        s, t, x = map(int, input().split())
        stx.append([x, s - x, t - x])
    stx.sort(reverse=True)
    d = [int(input()) for _ in range(q)]

    N = q
    N0 = 2**(N-1).bit_length()
    data = [None]*(2*N0)
    INF = (-1, 10**9 + 1)
    def update(l, r, v):
        L = l + N0; R = r + N0
        while L < R:
            if R & 1:
                R -= 1
                data[R-1] = v

            if L & 1:
                data[L-1] = v
                L += 1
            L >>= 1; R >>= 1
    def _query(k):
        k += N0-1
        s = INF
        while k >= 0:
            if data[k]:
                s = max(s, data[k])
            k = (k - 1) // 2
        return s
    def query(k):
        return _query(k)[1]



    import bisect

    for i, (x, start, last) in enumerate(stx):
        l = bisect.bisect_left(d, start)
        r = bisect.bisect_left(d, last)
        update(l, r, (i, x))

    for i in range(q):
        res = query(i)
        if res == 10**9 + 1:
            print(-1)
        else:
            print(res)

main()


Measured memory_bytes: 118700
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;
ll MOD = 1e9 + 7;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    int sum = 0, sum_max = 0;
    for (int i = 0; i < k; i++) {
        sum += p[i];
    }
    sum_max = sum;
    for (int i = 0; i < n - k; i++) {
        sum = sum - p[i] + p[i + k];
        if (sum > sum_max) sum_max = sum;
    }
    cout << setprecision(15) << (sum_max + k) / 2.0 << endl;
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  LL A[N+1];
  for (int i = 0; i < N+1; i++) {
    cin >> A[i];
  }
  LL B[N];
  for (int i = 0; i < N; i++) {
    cin >> B[i];
  }
  
  LL ans = 0;
  for (int i = 0; i < N; i++) {
    LL m = min(B[i], A[i]);
    B[i] = B[i] - m;
    A[i] = A[i] - m;
    ans = ans + m;
    m = min(B[i], A[i+1]);
    B[i] = B[i] - m;
    A[i+1] = A[i+1] - m;
    ans = ans + m;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int m = 1e9+7;
int main(){
    int n, k; 
    cin >> n >> k;
    int a[n];
    int f[n];
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if(i == 0){
            f[i] = a[0];
        }
        else{
            f[i] = f[i - 1] + a[i];
        }
    }
    int dp[n][k+1];
    int cum[n][k+1];
    memset(dp, 0, sizeof(dp));
    memset(cum, 0, sizeof(cum));
    //cum[i][j] should give sum of all dp[i][k] where 0 <= k <= j;
    for(int i = 0; i < n; i++){
        long long sum = 0;
        for(int j = 0; j <= k; j++){
            if(j == 0){
                dp[i][j] = 1;
            }
            else if(i == 0 && j <= a[i]){
                dp[i][j] = 1;
            }
            else{
                //dp[i][j] will be dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j-a[i]];
                if(j > f[i]) {
                    dp[i][j] = 0;
                }
                else{
                    dp[i][j] = cum[i-1][j];
                    if(j-a[i]-1 >= 0){
                        dp[i][j] -= cum[i-1][j-a[i]-1];
                    }
                }
            }
            dp[i][j] = (dp[i][j] + m)%m;
            sum = (sum + dp[i][j]) % m;
            cum[i][j] = sum;
        }
    }
    cout << dp[n-1][k] << endl;
    
    return 0;
}


Measured memory_bytes: 78336
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;


class Program {

	static int testN = 3;
	static long mod = 1000000007;
	//static long mod =998244353; 
	static System.IO.StringReader sr;
		static void Main(string[] args) {
			char[] cs = new char[] { ' ' };
			//char[] cs = new char[] { ' ', ',' };

			//int n = int.Parse(Console.ReadLine());
			//int val = int.Parse(Console.ReadLine());
			//int[] vals = parseAry(Console.ReadLine().Split(cs));
			//string str = Console.ReadLine();
			//string[] strs = Console.ReadLine().Split(cs);

			//string res = "";

			string res = "No";

		string str = Console.ReadLine();
		if(str[2] == str[3] && str[4] == str[5]) {
			res = "Yes";
		}



			Console.WriteLine(res);
			return;

		
	}


	//	文字列strをindex番目からdで上書き
	static string strOverWrite(string str, int i, string s) {
		return str.Remove(i, s.Length).Insert(i, s);
	}

	//　String[]  ----->  int[]
	static int[] parseAry(string[] str) {
		int[] nums = new int[str.Length];
		for ( int i = 0; i < str.Length; i++ ) { nums[i] = int.Parse(str[i]); }
		return nums;
	}
	//　String[]  ----->  long[]
	static long[] parseAryL(string[] str) {
		long[] nums = new long[str.Length];
		for ( int i = 0; i < str.Length; i++ ) { nums[i] = long.Parse(str[i]); }
		return nums;
	}

	//文字列を1文字ずつString[]に入れる
	static string[] strAry(String str) {
		string[] re = new string[str.Length];
		for ( int i = 0; i < str.Length; i++ ) { re[i] = str[i].ToString(); }
		return re;
	}



}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
const int INF=1e9,MOD=1e9+7;
const long long LINF=1e18;
using namespace std;
#define int long long
//template
std::vector<int> w(1234567,0);
int val(int l,int r){
  return w[r+1]^w[l];
}
std::vector<int> dpa(1234567,0),dpb(1234567,1),memo(1234567,0);
int pw(int n,int k){
  int res=1;
  while(k){
    if(k&1)res*=n;res%=MOD;
    n*=n;n%=MOD;
    k>>=1;
  }
  return res;
}
//main
signed main(){
  int N;cin>>N;
  std::vector<int> v(N);
  for(int i=0;i<N;i++)cin>>v[i];
  for(int i=0;i<N;i++)w[i+1]=w[i]^v[i];
  int sum=val(0,N-1);
  int now=0;int zco=0;
  for(int i=0;i<N;i++){
    now^=v[i];
    if(now==0)zco++;
    else{
      dpb[now]+=dpa[now]*(zco-memo[now]);
      dpa[now]+=dpb[now];
      memo[now]=zco;
      dpa[now]%=MOD;
      dpb[now]%=MOD;
    }
  }
  if(sum)cout<<dpb[sum]<<endl;
  else{
    int ans=0;
    for(int i=0;i<1234567;i++)ans+=dpa[i];
    cout<<(ans+pw(2,zco-1))%MOD<<endl;
  }
}


Measured memory_bytes: 42752
s=input()
a=int(s[:2])
b=int(s[2:])
if 1<=a<=12 and 1<=b<=12:
	print("AMBIGUOUS")
elif 1<=a<=12 and (12<b or b==0):
	print("MMYY")
elif (12<a or a==0) and 1<=b<=12:
	print("YYMM")
else:
	print("NA")

Measured memory_bytes: 3060
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

template<class T> inline void chmax(T& a, T b) { if(b > a) a = b; }
template<class T> inline void chmin(T& a, T b) { if(b < a) a = b; }

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

	const int INF = 0xfffffff;

	for(int n; cin >> n, n;) {
		vector<vector<int> > dist(10, vector<int>(10, INF));
		for(int i = 0; i < dist.size(); ++i)
			dist[i][i] = 0;

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

			chmax(m, max(a, b));

			dist[a][b] = dist[b][a] = c;
		}

		++m;
		for(int k = 0; k < m; ++k)
			for(int i = 0; i < m; ++i)
				for(int j = 0; j < m; ++j)
					chmin(dist[i][j], dist[i][k] + dist[k][j]);

		int city = INT_MAX, ans = INT_MAX;
		for(int i = 0; i < m; ++i) {
			int sum = 0;
			for(int j = 0; j < m; ++j)
				sum += dist[i][j];

			if(ans > sum) {
				ans = sum;
				city = i;
			}
		}

		cout << city << " " << ans << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1220
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <bitset>
#include <cmath>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define FI first
#define SE second
#define MA(i,j) make_pair(i,j)
#define PA pair<int,int>
#define PB push_back
#define PQ priority_queue<int>
#define PGQ priority_queue<int,vector<int>,greater<int> >
#define VE vector<int>
#define VP vector<PA>
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define MOD 1000000007
#define INF 1000000007
#define PI 3.141592653589793238462643383279
using namespace std;
//
int GCD(int a,int b){
    if(b==0) return a;
    return GCD(b,a%b);
}
int main(){
  int N,K;
  int A[100000];
  cin>>N>>K;
  int G,M;
  cin>>G;
  M=G;
  FOR(i,1,N){
    int C;
    cin>>C;
    G=GCD(max(G,C),min(G,C));
    M=max(M,C);
  }
  if(K>M||K%G!=0){
    cout<<"IMPOSSIBLE"<<endl;
  }else{
    cout<<"POSSIBLE"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
import math

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

#a = list(map(int, input().split()))

#####################################


#0:49
n = int(input())
nlist = [[]for i in range(n+1)]
for i in range(n-1):
    temp = list(map(int, input().split()))
    nlist[temp[0]].append([temp[1],temp[2]])
    nlist[temp[1]].append([temp[0],temp[2]])


queue = []    
for i in range(n+1):
    if(len(nlist[i])==1):
        queue.append([-1,i])
        break
        

searched = 0
color=[-1 for i in range(n+1)]
nowcol=0


color[queue[0][1]]=nowcol
queue.append([queue[0][1],nlist[queue[0][1]][0][0]])
if(nlist[queue[0][1]][0][1]%2==0):
    color[nlist[queue[0][1]][0][0]]=nowcol
else:
    nowcol=1-nowcol
    color[nlist[queue[0][1]][0][0]]=nowcol
searched+=1
    
while(True):
    nowpos = queue[searched][1]
    #print(queue[searched:])
    #print(nowpos)
    for k in nlist[nowpos]:
        if(k[0]!=queue[searched][0]):
            queue.append([nowpos,k[0]])
            #print("k",k[1])
            if(k[1]%2==0):
                color[k[0]]=color[nowpos]
                #print("a")
            else:
                color[k[0]]=1-color[nowpos]
                #print("b")
    searched+=1
    if(len(queue)==searched):
        break
print()
for i in range(n):
    print(color[i+1])

Measured memory_bytes: 92064
#include<bits/stdc++.h>
#include<string>
using namespace std;
int main()
{
    long long int n,i,j,k,l,sum,sum1,cnt,cnt1,flag,flag1,m,x,y,a,b,c,d,mid;
    string s;
    string t;
    cin>>s;
    cin>>t;
    string t1="";
    l=t.size();
    for(i=0;i<l-1;i++)
    {
       t1+=t[i];
    }
    if(s==t1)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
                cout<<"No"<<endl;

    }
    return 0;

}





Measured memory_bytes: 3596
import java.util.*;

public class Main {

    public static void main(String arg[]) {
        try {
            Scanner scan = new Scanner(System.in);
            int a = scan.nextInt();
            int b = scan.nextInt();
            int c = scan.nextInt();
            if ( 0<= a && a<101 && 0<= b && b<101 && 0<= c && c<101) {
                if (a < b && b < c) {
                    System.out.println("Yes");
                }else {
                    System.out.println("No");
                }
            } else {
                System.out.println("1??????100?????§???????????§???");
            }

        } catch (InputMismatchException ex) {
            System.out.println("1??????100?????§????????¶??°?????\?????????????????????");
        }
    }
}

Measured memory_bytes: 26268
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(void) {

	int A,B,C,X;int ans=0;
	cin >> A >> B >> C >> X;
	
	for(int i=0;i<=A;i++){
	    for(int j=0;j<=B;j++){
	        for(int k=0;k<=C;k++){
	            if(500*i+100*j+50*k==X)ans++;
	        }
	    }
	}

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

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

//#pragma GCC optimize("O3")
//#pragma GCC target("sse4")

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int)((a).size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = (LL)INF * INF;

const int MAX = 1 << 9;

int a[MAX][MAX];

void solve(int l, int r, int c)
{
	if(l == r)
		return;
	int m = (l + r) >> 1;
	FOR(i, l, m + 1)
		FOR(j, m + 1, r + 1)
			a[i][j] = c;
	solve(l, m, c + 1);
	solve(m + 1, r, c + 1);
}

int main()
{
	//ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	solve(0, n - 1, 1);
	FOR(i, 0, n - 1)
	{
		FOR(j, i + 1, n)
			cout << a[i][j] << " ";
		cout << "\n";
	}
	return 0;
}


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

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

	int count=0;
	for (int i=0;i<s.size();++i)
	{
		if (s[i]!=t[i])
		{
			++count;
		}
	}
	cout << count << endl;
}







Measured memory_bytes: 3916
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

const int MAXC=1000;
ll comb[MAXC][MAXC];
void comb_init(){
    comb[0][0]=1;
    for(int i=1;i<MAXC;i++){
        comb[i][0]=1;
        for(int j=1;j<MAXC;j++) comb[i][j]=comb[i-1][j-1]+comb[i-1][j];
    }
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    comb_init();
    ll n,p;cin>>n>>p;
    ll e=0,o=0;
    rep(i,n){
        ll t;cin>>t;
        if(t%2==0)  e++;
        else        o++;
    }
    ll a=1;rep(i,e)a*=2;
    ll b=0;for(ll i=p;i<=o;i+=2)b+=comb[o][i];
    cout<<a*b<<endl;
    return 0;
}


Measured memory_bytes: 8064
// #pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define N 1000000007
#define N2 998244353
#define Nmax 1000005
#define INF (ll)1e18
#define pll pair<ll,ll>
#define mp make_pair
#define fi first
#define se second
#define vv vector
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(ll i=m;i<(n);i++)
#define repr(i,n) repr2(i,n,0)
#define repr2(i,m,n) for(ll i=m;i>=(n);i--)
#define get(n) ll (n); scanf("%lld",&(n));
#define get2(n,k) ll (n),(k); scanf("%lld%lld",&(n),&(k));
#define get3(n,m,k) ll (n),(m),(k); scanf("%lld%lld%lld",&(n),&(m),&(k));
#define gets(s) string (s); cin >> (s);
#define ALL(c) (c).begin(),(c).end()
#define fill_nums(A,n) vector<ll> A((n)); for(ll i=0;i<n;i++) scanf("%lld",&A[i]);
#define fill_edges(adj,m) for(ll i=0;i<m;i++) {ll a, b; scanf("%lld %lld",&a,&b); adj[a-1].pb(b-1); adj[b-1].pb(a-1);}
#define fill_direct(adj,m) for(ll i=0;i<m;i++) {ll a, b; scanf("%lld %lld",&a,&b); adj[a-1].pb(b-1);}
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); //cout.tie(0);
#define pi 3.1415926535897
#define db double
#define noop
#define flu fflush(stdout)
#define imp {cout<<"NO\n"; return 0;}
#define debug_vec(vec,n) {rep(idxi,n) cout<<vec[idxi]<<" "; cout<<"\n";}
#define debug_pvec(vec,n) {rep(idxi,n) cout<<vec[idxi].fi<<"-"<<vec[idxi].se<<"  "; cout<<"\n";}
#define debug_set(seta) {cout<<seta.size()<<"\n"; for(auto idxi:seta) cout<<idxi<<" "; cout<<"\n";}
#define debug_map(mappa) {cout<<mappa.size()<<"\n";for(auto idxi:mappa) cout<<idxi.fi<<"-"<<idxi.se<<"  "; cout<<"\n";}


int main() {

    get3(h,w,n);
    ll a = max(h,w);
    cout<<(ll)ceil(n/(double)a)<<endl;

    
    return 0;  
}

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

//??¨??????????????????????????§?´???°??¨?????????
//?´???°??¨??¨?´???????????????£?????????????????§??¨????????????

const int MAX_V = 999999;
int prime[MAX_V + 1]; //?´???°??¨
int sum[MAX_V + 1]; //?´???°?????°???????¨?

int main()
{
	int i, k, v;
	prime[0] = prime[1] = 0;
	for (i = 2; i <= MAX_V; i++)
	{
		prime[i] = 1;
	}
	for (i = 2; i*i <= MAX_V; i++)
	{
		if (prime[i])
		{
			for (k = 2 * i; k <= MAX_V; k += i)
			{
				prime[k] = 0;
			}
		}
	}

	sum[0] = 0;
	for (i = 0; i < MAX_V + 1; i++)
	{
		sum[i+1] = sum[i] + prime[i+1];
	}

	int input;
	while (cin >> input)
	{
		cout << sum[input] << endl;
	}

	return 0;
}

Measured memory_bytes: 10876
///*
#include<iostream>
#include<string>
using namespace std;

int main() {

	string a, b, c;
	cin >> a >> b >> c;

	if ('a' <= a[0] && a[0] <= 'z')a[0] -= 32;
	if ('a' <= b[0] && b[0] <= 'z')b[0] -= 32;
	if ('a' <= c[0] && c[0] <= 'z')c[0] -= 32;

	cout << char(a[0]) << char(b[0]) << char(c[0]);

	return 0;
}

//*/

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define N ((ll)5020)

ll n,k,ans,a[N];
bitset <N> dp[N],dpr[N];

int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>k;
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		dp[i]=dp[i-1];
		if(a[i]<N)dp[i]|=(dp[i]<<a[i]);
	}
	dpr[n+1][0]=1;
	for(int i=n;i>=1;i--)
	{
		dpr[i]=dpr[i+1];
		if(a[i]<N)dpr[i]|=(dpr[i]<<a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		bool flg=0;
		for(int j=0,j2=N-1;j<N;j++)
			if(dp[i-1][j])
			{
				while(j2>=0 && (dpr[i+1][j2]==0 || j2+j>=k))j2--;
				if(j2>=0 && j2+j>=k-a[i]){flg=1;break;}
			}
		//cout<<flg<<"||||| \n";
		ans+=flg;
	}
	cout<<n-ans<<endl;
	return 0;
}

Measured memory_bytes: 6528
import java.util.*

/**
 * Created by niyaz on 07.06.17.
 */

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val k = sc.nextInt()
    val edges = Array(n, { mutableListOf<Int>() })

    fun dfs(v: Int, pv: Int, d: Int): Int {
        var ans = if (2 * d > k) 1 else 0
        for (to in edges[v]) {
            if (to == pv) continue
            ans += dfs(to, v, d + 1)
        }
        return ans
    }

    for (i in 1..n - 1) {
        val v = sc.nextInt() - 1
        val u = sc.nextInt() - 1
        edges[v].add(u)
        edges[u].add(v)
    }
    if (k % 2 == 0) {
        println((0..n - 1).map { dfs(it, -1, 0) }.min())
    } else {
        println(
        (0..n - 1).map { v ->
            edges[v].filter { v < it }.map { dfs(v, it, 0) + dfs(it, v, 0) }.min() ?: Int.MAX_VALUE
        }.min()
        )
    }
}


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

int main(){
  int N;
  cin >> N;
  int x = 0;
  for(int i = 1; i < 10; i++){
    for(int j = i; j < 10; j++){
      if(i*j == N) x++;
    }
  }
  if(x > 0)cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3600
N,M = map(int,input().split())
s = []
for i in range(M):
    dp = [0]*(N)
    k,*tmp = list(map(int,input().split()))
    for j in tmp:dp[j-1]=1
    s.append(dp)
p = list(map(int,input().split()))
ans = 0
for i in range(1<<N):
    tmp = 0
    dp = [0]*M
    for I in range(M):
        for j in range(N):
            t = i>>j&1
            dp[I] += s[I][j] * t
    for e,i in enumerate(dp):
        dp[e] = i%2
    if dp == p:
        ans+=1
print(ans)





Measured memory_bytes: 3188
#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long int_;
inline int readint(){
	int x; scanf("%d",&x); return x;
}

const int MaxN = 200005;
int_ a[MaxN]; set<int_> vis;

int main(){
	for(int i=0; i<MaxN; ++i){
		a[i] = 1ll*i*i*i*i*i;
		vis.insert(a[i]);
	}
	int x = readint();
	bool ok = false;
	int one, two = MaxN+1;
	for(int i=0; !ok; ++i){
		if(a[i] > x) break;
		if(vis.count(x-a[i])){
			ok = true;
			one = i;
			for(int j=1; two>MaxN; ++j)
				if(a[j] == x-a[i])
					two = -j;
		}
	}
	for(int i=0; !ok; ++i){
		if(i and a[i]-a[i-1] > x) break;
		if(vis.count(a[i]-x)){
			ok = true;
			one = i;
			for(int j=1; two>MaxN; ++j)
				if(a[j] == a[i]-x)
					two = j;
		}
	}
	if(ok) printf("%d %d\n",one,two);

	return 0;
}

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

int main() {
	int n,c,count=0;
  	cin >> n;
  	for(int i = 0; i< n; i++) {
		cin >> c;
      	while((c&1)==0)	{
        	count++;
          	c>>=1;
        }
    }
  	cout << count << endl;
}


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

int main() {
  int n;
  cin >> n;
  vector<long long> a(n);
  for(int i = 0; i < n; i++) cin >> a.at(i);
  
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  long long ans = a.at(0), now = 1;
  n -= 2;
  while(n > 0){
    if(n > 1){
      n -= 2;
      ans += a.at(now) * 2;
      now++;
    }
    else n--, ans += a.at(now);
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 4844
n = int(input())
t = list(map(int, input().split()))
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

if max(t) != max(a):
    print(0)
    exit()


def f(li, rev):
    if rev:
        li = li[::-1]

    cnts = [0] * n
    cands = [0] * n
    mx = 0
    cnt = 0
    for i, e in enumerate(li):
        if e > mx:
            cnts[i] = 1
            cands[i] = e
            cnt = e
            mx = e
        else:
            cnts[i] = cnt

    if rev:
        cnts = cnts[::-1]
        cands = cands[::-1]

    return cnts, cands


t_cnt, t_cand = f(t, False)
a_cnt, a_cand = f(a, True)

for e1, e2 in zip(t, a_cand):
    if e2 > e1:
        print(0)
        exit()

ans = 1
for e1, e2 in zip(t_cnt, a_cnt):
    ans *= min(e1, e2)
    ans %= mod

print(ans)


Measured memory_bytes: 19136
#define SUBMIT

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=jp
// Combinatorial - Coin Changing Problem

//Combinatorial - 0-1 Knapsack Problem
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;
using ui64 = unsigned long long;
using i64 = long long;

int main() {
#ifdef SUBMIT
    int N, W;
    cin >> N >> W;
    vector<int> v(N);
    vector<int> w(N);
    for (int i = 0; i < N; ++i) {
        cin >> v[i] >> w[i];
    }
#else
    int N = 4, W = 5;
    vector<int> v { 4, 5, 2, 8};
    vector<int> w {2, 2, 1, 3};
#endif

    // dp[i][j]: i番目の品物の中から重さがjを超えないように選んだときの価値の総和の最大値
    int dp[N + 1][W + 1];
    for (int j = 0; j < W + 1; ++j) {
        dp[0][j] = 0;
    }

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < W + 1; ++j) {
            if (j >= w[i]) {
                dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j]);
            } else {
                dp[i + 1][j] = dp[i][j];
            }
        }
    }

    cout << dp[N][W] << endl;
    return 0;
}


Measured memory_bytes: 7040
#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
#define np basic_string::npos
int main(void){
    int n,in,ans=0;
    vector<int> a;
    cin>>n;
    for(int i=0;i<2*n;i++){
        cin>>in;
        a.push_back(in);
    }
    sort(a.begin(),a.end());
    for(int i=0;i<n;i++){
        ans+=a[2*i];
    }
    cout<<ans<<endl;
}

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

int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  vector<int> Alice(101,2);
  vector<int> Bob(101,0);
  for (int i=a ; i<b; i++){
    Alice[i]=1;
  }
  for (int i=c; i<d; i++){
    Bob[i]=1;
  }
  int ans = 0;
  for(int j=0; j<101; j++){
    if(Alice[j]==Bob[j]) ans+=1;
  }
  cout << ans << endl;
}

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

int main()
{
    int n;
    int a[5]={5,7,5,7,7};
    while(cin >>n,n)
    {
        vector<int> w(n);
        rep(i,n)
        {
            string s;
            cin >>s;
            w[i]=s.size();
        }

        int ans=-1;
        rep(i,n)
        {
            int ct=0;

            bool valid=false;
            int idx=0;
            for(int j=i; j<n; ++j)
            {
                ct+=w[j];
                if(ct==a[idx])
                {
                    ++idx;
                    ct=0;
                }
                else if(ct>a[idx]) break;


                if(idx==5)
                {
                    valid=true;
                    break;
                }
            }

            if(valid)
            {
                ans=i+1;
                break;
            }
        }

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

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


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

    for (int i = 0; i < n.length(); ++i) {
        if(n[i]=='1') cout << 9;
        if(n[i]=='9') cout << 1;
    }
    return 0;
}

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

ll a[3][3],b[1010];
ll n;
bool f[3][3];
bool check(){
	if(f[0][0]&&f[0][1]&&f[0][2])return 1;
	if(f[1][0]&&f[1][1]&&f[1][2])return 1;
	if(f[2][0]&&f[2][1]&&f[2][2])return 1;
	if(f[0][0]&&f[1][0]&&f[2][0])return 1;
	if(f[0][1]&&f[1][1]&&f[2][1])return 1;
	if(f[0][2]&&f[1][2]&&f[2][2])return 1;
	if(f[0][0]&&f[1][1]&&f[2][2])return 1;
	if(f[2][0]&&f[1][1]&&f[0][2])return 1;
	return 0;
}
int main(){
	for(int i=0;i<3;i++)for(int j=0;j<3;j++)cin>>a[i][j];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>b[i];
		for(int j=0;j<3;j++)for(int k=0;k<3;k++)if(b[i]==a[j][k])f[j][k]=1;
	}
	cout<<(check()?"Yes":"No");
	return 0;
}


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

int main(){
  int n;
  double t, a;
  cin >> n >> t >> a;
  vector<int> h(n);
  for(int i = 0; i < n; i++) cin >> h[i];
  double min = 1e9, ans = 0;
  int min_index = 0;
  for(int i = 0; i < n; i++){
    ans = abs((t - h[i] * 0.006) - a);
    if(ans < min){
      min = ans;
      min_index = i + 1;
    }
  }
  cout << min_index << endl;
  return 0;
}

Measured memory_bytes: 3740
#include <iostream>
using namespace std;
int main(){
  int i = 1,n;
  cin>>n;
 while( ++i <= n ){
  int x = i;
  if ( x % 3 == 0 ){
    cout << " " << i;
    continue;
  }
while( x ){
  if ( x % 10 == 3 ){
    cout << " " << i;
    break;
  }
  x /= 10;
}
  
 }

  cout << endl;
  return 0;
}



Measured memory_bytes: 3072
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int n,m;
signed main(){
	scanf("%lld%lld",&n,&m);
	printf("%lld",n*(n-1)/2+m*(m-1)/2);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int main() {
    int m, n, sum = 0, total = 0, cnt = 0;
    while (scanf("%d,%d", &m, &n) != EOF) {
        sum += m * n;
        total += n;
        cnt++;
    }
    cout << sum << endl;
    cout << round((double)total / cnt) << endl;
    
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  int p[N];
  for (int i = 0; i < N; i++) cin >> p[i];

  bool flag[N];
  fill(flag, flag + N, true);
  for (int i = 0; i < N; i++) {
    if (p[i] == i + 1) flag[i] = false;
  }

  int ans = 0;
  for (int i = 1; i < N; i++) {
    if (!flag[i-1] && !flag[i]) {
      ans++;
      flag[i-1] = flag[i] = true;
      i++;
    }
  }

  for (int i = 0; i < N; i++) {
    if (!flag[i]) ans++;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define rep(i, n) FOR(i, 0, n - 1)
using namespace std;
typedef long long ll;
template <class T> inline bool dpmin(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <class T> inline bool dpmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips:
// You use the default template now. You can remove this line by using your
// custom template)
int main()
{
    long long N;
    cin >> N;

    ll ans = 0;
    for (int i = 1; i <= N; i+=2) {
        int n_div = 0;
        for (int j = 1; j <= i; j+=2) {
            if (i%j == 0) { n_div++; }
        }

        if (n_div == 8) { ans++; }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3548
import itertools
n,m = list(map(int,input().split()))
A = [list(map(int,input().split())) for _ in range(m)]
a = [0]*n
for x,y in A:
  a[x-1] |= 1<<(y-1)
  a[y-1] |= 1<<(x-1)

def bitdp(n, a):
  dp = [[0]*n for _ in range(1<<n)]
  dp[1][0] = 1
  
  for bit in range(1<<n):
    for v in range(n):
      if bit & 1<<v:
        sub = bit ^ (1<<v)
        
        for u in range(n):
          if (sub & 1<<u) and (a[v] & 1<<u):
            dp[bit][v] += dp[sub][u]
  ans = sum(dp[(1<<n)-1][u] for u in range(1,n))
  return ans

ans = bitdp(n,a)
print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
using namespace std;
#define INF ( 1 << 30 )
int main(){
  int L,A,B,C,D;
  cin >> L >> A >> B >> C >> D;
  cout << L - max(A%C?A/C+1:A/C,B%D?B/D+1:B/D) << endl;
}

Measured memory_bytes: 1160
const input = require("fs").readFileSync("/dev/stdin", "utf8")

;(input => {

    const lines = input.split('\n')
    const X = lines[0] - 0

    const s = Math.floor(X / 500)
    const mod = Math.floor(X % 500)
    const f = Math.floor(mod / 5)

    console.log(s * 1000 + f * 5)

})(input)

Measured memory_bytes: 29600
from collections import deque

n, m = map(int, input().split())
e = {i:[] for i in range(1, n+1)}
for _ in range(m):
    p, q = map(int, input().split())
    e[p].append(q)
    e[q].append(p)

def bfs():
    visited = [0] + [None] * n
    queue = deque([1])
    visited[1] = 0
    while queue:
        current = queue.pop()
        for x in e[current]:
            if visited[x] == None:
                visited[x] = current
                queue.appendleft(x)
    return visited

print('Yes')
print(*bfs()[2:], sep='\n')

Measured memory_bytes: 42340
#include <bits/stdc++.h>
using namespace std;
using ll = long long ;
int main(){

ll n,sum=0 ;
cin >> n ;
int a[n] ;
for(int i=0 ;i<n ; i++)
{
    cin >>a[i] ;
}
for(int i=0 ;i<n ;i++)
{
    for(int j=i+1 ;j<n ;j++)
    {
        sum+=(a[i]*a[j]) ;
    }

}

cout << sum <<endl ;
    return 0 ;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(){
int H,W,i,j;
while(1){
   scanf("%d %d",&H,&W);
   if(H==0&&W==0) break;
   for(i=1;i<=H;i++){
      for(j=1;j<=W;j++){
         if((i+j)%2==0){
            printf("#");
         }else{
            printf(".");
         }
      }
      printf("\n");
   }
   printf("\n");
}
return 0;
}

Measured memory_bytes: 572
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
#define pb push_back
#define INF 1e15 + 7

int main(int argc, char **argv) {
	int n;
	cin >> n;
	VL a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	ll sum = 0;
	for (int i = 0; i < n; ++i) {
		sum += a[i];
	}
	sum /= 2;
	for (int i = 2; i < n; i += 2) {
		sum -= a[i];
	}
	VL b(n);
	b[0] = sum;
	for (int i = 1; i < n; ++i) {
		b[i] = a[i] - b[i - 1];
	}
	for (int i = 0; i < n; ++i) {
		cout << b[(i + n - 1) % n] * 2 << " ";
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 2944
#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>
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 Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
int main() {
	int n; cin >> n;
	vector<int>v;
	v.push_back(1);
	int k = 1;
	while (k * 6 < 100000) {
		k *= 6;
		v.push_back(k);
	}
	k = 1;
	while (k * 9 < 100000) {
		k *= 9;
		v.push_back(k);
	}
	int len = v.size();
	int dp[100001];
	fill(dp, dp + n + 1, (int)MOD);
	dp[0] = 0;
	rep(i, len) {
		rep(j, n + 1) {
			if (j + v[i] <= n) {
				dp[j + v[i]] = min(dp[j + v[i]], dp[j] + 1);
			}
		}
	}
	cout << dp[n] << endl;
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
 int a[9];
int b[105];
int main()
{
   
    for(int i=0;i<8;i++)a[i]=0;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>b[i];
    int x=0;
    for(int i=0;i<n;i++)
    {
        if(b[i]<=399)a[0]=1;
        else if(b[i]>=400&&b[i]<=799)a[1]++;
          else if(b[i]>=800&&b[i]<=1199)a[2]++;
            else if(b[i]>=1200&&b[i]<=1599)a[3]++;
              else if(b[i]>=1600&&b[i]<=1999)a[4]++;
                else if(b[i]>=2000&&b[i]<=2399)a[5]++;
                  else if(b[i]>=2400&&b[i]<=2799)a[6]++;
                    else if(b[i]>=2800&&b[i]<=3199)a[7]++;
                    else if(b[i]>=3200)x++;

    }
    int y=0;
    for(int i=0;i<8;i++)
    {
        if(a[i]!=0)y++;
    }
  if(y==0) cout<<"1"<<" "<<x<<'\n';

   else  cout<<y<<" "<<x+y<<'\n';

return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		long[] aArray = new long[n];
		long[] bArray = new long[n];

		for (int i=0;i<n;i++) {
			aArray[i]=sc.nextLong();
		}
		for (int i=0;i<n;i++) {
			bArray[i]=sc.nextLong();
		}

		long [] bitSum = new long [32];
		for (int i=0;i<n;i++) {
			for (int j=0;j<32;j++) {
				bitSum[j] += ((aArray[i] >> j) % 2)*n;
				bitSum[j] += ((bArray[i] >> j) % 2)*n;
			}
		}

		long [] aModArray = new long[n];
		long [] bModArray = new long[n];

		for (int i=0;i<32;i++) {

			final int k = i;
			for (int j=0;j<n;j++) {
				aModArray[j]=aArray[j] % (1L << i);
				bModArray[j]=bArray[j] % (1L << i);
			}

			Arrays.sort(bModArray);

			for (long a : aModArray) {
				bitSum[i] += (n - firstBinarySearch(bModArray, (1L << (i)) - a));
			}
		}
		long ans = 0;

		for (int i=0;i<32;i++) {
			if (bitSum[i]%2 == 1) {
				ans += (1L<<i);
			}
		}

		System.out.println(ans);
	}

	static  int firstBinarySearch (long[] array, long v) {
		//return the index of the first object larger than or equal to v
		//n if doesn't exist
		int n =array.length;
		int min = 0;
		int max = n-1;

		if (array[n-1] < v) {
			return n;
		}

		if (array[0] >= v) {
			return 0;
		}

		while (max > min + 1) {
			int mid = min+(max-min)/2;
			if (array[mid] >= v) {
				max = mid;
			} else {
				min = mid;
			}
		}

		return max;
	}

}



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

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

	int a_max = -10000;
	int a_min = 10000;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a_max = max(a_max, a[i]);
		a_min = min(a_min, a[i]);
	}
	
	int ans = 2147483647;
	for (int j = a_min; j <= a_max; j++) {

		int tmp = 0;
		for (int i = 0; i < n; i++) {
			tmp += (j - a[i]) * (j - a[i]);
		}

		ans = min(ans, tmp);

	}

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

Measured memory_bytes: 256
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#pragma GCC optimize("Os")
#pragma GCC target("avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("Os")
*/

#include <bits/stdc++.h>
//#include <windows.h>

#define ll long long
#define X first
#define Y second
#define MP make_pair

using namespace std;

    /*
const int MAX_MEM = 1e8;
int mpos=0;
char mem[MAX_MEM];
inline void * operator new(size_t n){
	char *res = mem + mpos;
	mpos += n;
	assert(mpos <= MAX_MEM);
	return (void *)res;
}

inline void operator delete(void *){}
    */
const int N = 2e3 + 1;

int n, k, ans[N], t, was, uwas;
vector<int> g[N];

void dfs(int v, int pr=0, int d=0){
	if(k % 2 == 0){
		if(d > k / 2){
			ans[t] += 1;
		}
	}
	else{
		if(d > (k + 1) / 2){
			ans[t] += 1;
		}
		if(d == (k + 1) / 2){
			was += 1;
		}
	}   

	for(int u: g[v]){
		if(pr == u)
			continue;
		dfs(u, v, d + 1);
		if(v == t){
			ans[t] += was;
			if(uwas < was){
				ans[t] += uwas;
				ans[t] -= was;
				uwas = was;	
			}
			was = 0;
		}
	}		
}

int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> k;
	for(int i = 1;i < n;i++){
		int x, y;
		cin >> x >> y;
		g[x].push_back(y), g[y].push_back(x);
	}

	for(int i = 1;i <= n;i++){
		t = i, was = 0, uwas = 0;
		dfs(i);
	}

	int res = n;
	for(int i = 1;i <= n;i++)
		res = min(res, ans[i]);//, cout << ans[i] << endl;
	cout << res;
}    


Measured memory_bytes: 512