akhauriyash/Code-Regression huggingface dataset:
N = int(input())
a = list(map(int, input().split()))

x = sum(a)

a.sort(reverse = True)

D = [0] * N

ans = 0
flag = True
while flag:
  k = 0
  for i in range(N):
    k += a[i] // N
  for i in range(N):
    D[i] = a[i] % N + (k - a[i] // N)
  flag = False
  ans += k
  for i in range(N):
    a[i] = D[i]
    if D[i] >= N:
      flag = True

print(ans)



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

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

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)

#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))

#define DEBUG(x) cout<<#x<<": "<<(x)<<endl

int n,r;
int a[352521];

int dat[352521];
int root(int x){
	return dat[x]<0 ? x : dat[x]=root(dat[x]);
}
void unite(int a,int b){
	a=root(a); b=root(b);
	if(a==b)return;
	if(dat[a]>dat[b])swap(a,b);
	dat[a] += dat[b];
	dat[b] = a;
}

bool dp[352521];

int main(){
	scanf("%d%d",&n,&r);
	REP(i,n)scanf("%d",a+i);
	REP(i,n)a[i]--;
	fill(dat,dat+n,-1);
	REP(i,n)unite(i,a[i]);
	map<int,int> sizes;
	REP(i,n)if(root(i)==i)sizes[-dat[i]]++;
	dp[0] = true;
	auto f = [&](int w){
		FORR(i,0,n)if(dp[i] && i+w<=n){
			dp[i+w] = true;
		}
	};
	for(pii P : sizes){
		int w = P.first;
		int c = P.second;
		int b = 1;
		while(b<=c){
			c -= b;
			f(w*b);
			b *= 2;
		}
		if(c>0){
			f(w*c);
		}
	}
	puts(dp[r] ? "Yes" : "No");
	return 0;
}


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    string S;
    cin >> S;
    ll N = S.size();
    vector<int> A(N + 1, 0);
    rep(i, N) {
        if (S[i] == '<') {
            A[i + 1] += A[i] + 1;
        }
    }
    rrep(i, N - 1, 0) {
        if (S[i] == '>') {
            A[i] = max(A[i + 1] + 1, A[i]);
        }
    }
    ll ans = accumulate(A.begin(), A.end(), 0LL);
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 2844
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
//using ll=long long;

int main(){
    int a, b;
    cin >> a >> b;
    int diff = b - a;
    int total = 0;
    for(int i = 1; i < diff; i++){
        total += i;
    }
    cout << total - a << endl;
    
    return 0;
}

Measured memory_bytes: 256
/*Remember: The Struggle is Important*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

#include<bits/stdc++.h>
using namespace std;

#define     int          long long int
#define     ld           long double
#define     fast()       ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)       x.begin(),x.end()
#define     mem(a,b)     memset(a,b,sizeof(a))
#define     gcd(a,b)     (__gcd((a),(b)))
#define     lcm(a,b)     (((a)*(b))/gcd((a),(b)))
#define     pb           push_back
#define     ins          insert
#define     pii          pair<int,int>
#define     F            first
#define     S            second
#define     makep        make_pair
#define     maket        make_tuple
#define     show(x)      for(auto c:x)cout<<c<<" ";cout<<"\n";
#define     show2(x)     for(auto c:x)cout<<c.F<<" "<<c.S<<"\n";

const int inf=1e18,M=1e9+7;
const int N=1;

void solve()
{
    string s;
    cin>>s;

    int n=s.length();

    if(n==2)
    {
        if(s[0]==s[1])
            cout<<"1 2";
        else
            cout<<"-1 -1";
        return;
    }

    for(int i=0;i+2<n;++i)
    {
        if(s[i]==s[i+1] || s[i+1]==s[i+2] || s[i]==s[i+2])
        {
            cout<<i+1<<" "<<i+3;
            return;
        }
    }

    cout<<"-1 -1";
}

int32_t main()
{
    fast();

    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
        //cout<<"\n";
    }

    return 0;
}




Measured memory_bytes: 512
module IO = struct

  (* @since 4.04.0 *)
  let split_on_char sep s =
    let open String in
    let r = ref [] in
    let j = ref (length s) in
    for i = length s - 1 downto 0 do
      if get s i = sep then begin
        r := sub s (i + 1) (!j - i - 1) :: !r;
        j := i
      end
    done;
    sub s 0 !j :: !r

  let read_ns () = read_line () |> split_on_char ' ' |> List.map int_of_string

end

let solve h w c =
  let s = Array.make w 0 in
  let t = Array.make w 0 in
  let r = ref 0 in
  for i = 0 to h - 1 do
    if c.(i).(0) then r := 1
  done;
  for j = 0 to w - 1 do
    if c.(0).(j) then begin
      s.(j) <- 1;
      r := 1
    end
  done;
  for i = 1 to h - 1 do
    if c.(i).(0) then t.(0) <- 1;
    for j = 1 to w - 1 do
      if not c.(i).(j) then t.(j) <- 0
      else begin
        let d = if s.(j) < t.(j-1) then s.(j) else t.(j-1) in
        t.(j) <- 1 + if s.(j-1) < d then s.(j-1) else d;
        if t.(j) > !r then r := t.(j)
      end
    done;
    Array.iteri (fun i e -> s.(i) <- e) t
  done;
  !r * !r

let () =
  match IO.read_ns () with
  | [h; w] ->
    let c = Array.make_matrix h w false in
    for i = 0 to h - 1 do
      IO.read_ns () |> List.iteri (fun j e -> c.(i).(j) <- e = 0);
    done;
    solve h w c |> Printf.printf "%d\n"
  | _ -> assert false

Measured memory_bytes: 25408
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

k = int(input())

g = [[] for _ in range(k)]
for i in range(k):
    g[i].append(((i+1)%k,1))
    if i: g[i].append((10*i%k,0))
#print(g)

from collections import deque
q = deque([1])
res = [float("inf")]*k
res[1] = 1
while q:
    v = q.popleft()
    if v==0: break
    for c,d in g[v]:
        if res[c] <= res[v] + d: continue
        res[c] = res[v] + d
        if d: q.append(c)
        else: q.appendleft(c)

print(res[0])




Measured memory_bytes: 37148
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int n; cin>>n;
	cout<<(n+n*n+n*n*n)<<endl;
	return 0;
}


Measured memory_bytes: 3648
R, G, B, N = map(int, input().split())
R, G, B = sorted([R, G, B], reverse=True)
if B == 1:
  c = 0
  for r in range(0, N+1):
    if r*R > N:
      break
    n = N-r*R
    c += 1+n//G
  print(c)
  exit()
c = 0
for r in range(0, N+1):
  if r*R > N:
    break
  for g in range(0, N+1):
    if r*R+g*G > N:
      break
    n = N-r*R-g*G
    if n%B == 0:
      c += 1
print(c)


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

int main(void){
	double num;
	while(cin >> num){
		double ans=num;
		for(int i=2;i<=10;i++){
			if(i%2==0)num=(double)num*2;
			else num=(double)num/3;
			ans+=num;
		}
		printf("%0.10f\n",ans);
	}
    return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <iomanip>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<long double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

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

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }
#define INF 1LL<<60

int main() {
    ll mod = 1e9 + 7;
    int N, M;
    cin >> N >> M;
    vector<ll> a(M), dp(N+2);
    REP(i, M) cin >> a[i];
    dp[0] = 0;
    dp[1] = 1;
    int cur_a_idx = 0;
    for(int i=2; i<=N+1; i++) {
        if( cur_a_idx < M && i-1 == a[cur_a_idx]) {
            cur_a_idx++;
            dp[i] = 0;
        } else {
            dp[i] = (dp[i-1] + dp[i-2]) % mod;
        }
    }

    cout << dp[N+1] << endl;

    return 0;
}

Measured memory_bytes: 1792
n = int(input())
h = list(map(int,input().split()))
x = float("inf")

dp = [x] * n

dp[0] = 0
for i in range(1,n):
    dp[i] = min(dp[i],dp[i-1]+abs(h[i]-h[i-1]))
    if(i > 1):
        dp[i] = min(dp[i],dp[i-2]+abs(h[i]-h[i-2]))

print(dp[n-1])

Measured memory_bytes: 13980
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <numeric>
#include <random>
#include <algorithm>
#include <functional>
#include <cassert>

using namespace std;
typedef long long ll;

template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

const int INF = (1 << 30) - 1;
const ll INFLL= (1LL << 61) - 1;
const int MOD = 1000000007;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  ll X,a,b;
  cin>>X;
  a=X/500;
  b=(X-a*500)/5;
  cout<<a*1000+b*5<<endl;
}


Measured memory_bytes: 256
import java.util.*;

class Main{
	public static void main(String[] args){
      	int n, k;
      	boolean loop = true;
    	Scanner sc = new Scanner(System.in);
      	n = sc.nextInt();
      	k = sc.nextInt();
      	
      	int i = 1, ans = 0;
      	while(loop){
          	int count = 0;
          	int j = i;
        	while(true){
        		//System.out.print(j);
        	  count++;
              if(j > n){
              	loop = false;
                break;
              }
              if(count == k){
              	ans++;
              	//System.out.println();
                break;
              }
              j++;
            }
          	i++;
        }
      
      	System.out.println(ans);
    }
}


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

int c1_to_c2[26], c2_to_c1[26];

int main(){
    string S, T;
    cin >> S;
    cin >> T;
    for(int i = 0; i < 26; i++){
        c1_to_c2[i] = -1;
        c2_to_c1[i] = -1;
    }
    bool is_ok = true;
    for(int i = 0; i < S.length(); i++){
        char c1 = S[i] - 'a', c2 = T[i] - 'a';
        if(c1_to_c2[c1] == c2 || c1_to_c2[c1] == -1){
            c1_to_c2[c1] = c2;
        }else{
            is_ok = false;
        }
        if(c2_to_c1[c2] == c1 || c2_to_c1[c2] == -1){
            c2_to_c1[c2] = c1;
        }else{
            is_ok = false;
        }
    }
    cout << (is_ok? "Yes" : "No") << endl;
}


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

const ll INF = 1e10;
ll dp[1<<12][12];
int N,M,X;
int C[12],A[12][12];


ll dfs(ll bit,int v){
  if(dp[bit][v] != 0) return dp[bit][v];
  if(bit == (1<<N)-1) return dp[bit][v] = 0;
 ll res = INF;
  rep(u,N){
    if(!(bit & 1<<u)){
      rep(j,M){
        dp[bit][j] = min(res,dfs(bit | 1<<u,j) + A[v][j]);
      }
    }
  }
  return dp[bit][v] = res;
}


int main(){
  cin >> N >> M >> X;
  rep(i,N){
    cin >> C[i];
    rep(j,M){
      cin >> A[i][j];
    }
}

rep(i,1<<N)rep(j,M) dp[i][j] = 0;

  rep(j,M){
    dp[0][j] = 0;
  }

ll cost = INF;

rep(j,M) dp[0][j] = 0;
//dfs(0,0);


for(ll i = 1; i< 1<<N; i++){
  rep(u,N){
    if(i & 1<<u){
      rep(j,M){
        dp[i][j] = dp[i^(1<<u)][j] + A[u][j];
      }
    }
  }
}


for(int i = 1; i <(1<<N); i++){
  bool flg = true;
  rep(j,M){
    if(dp[i][j] < X) flg = false;
  }
  if(flg){
    ll sum = 0;
    rep(j,N){
      if(i & 1<<j) sum += C[j];
    }
    cost = min(cost,sum);
  }
}
//
// rep(i,1<<N){
//    rep(j,M) cout << dp[i][j] << ' ';
//    cout << endl;
// }

if(cost == INF) cout << -1 << endl;
else cout << cost << endl;
}


Measured memory_bytes: 4008
#include <iostream>
#include <string>

using namespace std;

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

    if(x=="Sunny"){
        cout<<"Cloudy"<<endl;
    }
    else if(x=="Cloudy"){
        cout<<"Rainy"<<endl;
    }else{
        cout<<"Sunny"<<endl;
    }
    
}


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

int main() {
  string s;
  cin>>s;
  int a=s.size();
  if(a<4){
    cout<<"No"<<endl;
    return 0;
  }
  
  if(s.at(0)=='Y'&&s.at(1)=='A'&&s.at(2)=='K'&&s.at(3)=='I'){
    cout<<"Yes"<<endl;
    return 0;
  }
  cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
string ss,st="CODEFESTIVAL2016";
int sum=0;
int main(){
	int i,j,k,n;
	cin>>ss;
	for(i=0;i<ss.length();i++)
	if(ss[i]!=st[i])sum++;
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
 
 
int main(void){
    int N;
    cin >>N;
    vector<int>A(N);
    for(int a=0;a<N;a++){
        cin >>A[a];
    }
    long long int ans=1000;
    long long int kabu=0;
    for(int k=0;k<N-1;k++){
        if(A[k]<A[k+1]){
            kabu=ans/A[k];
            ans=ans%A[k]+kabu*A[k+1];
        }else{
            //kabu=0;
        }
        //cout << ans<<" "<<kabu<<endl;
    }
    cout <<ans<<endl;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　 |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/





int W, H, C;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> W >> H >> C;
    int ans = inf;
    rep(l, 1, 1010) if (W % l == 0 and H % l == 0) {
        int cst = (W / l) * (H / l) * C;
        chmin(ans, cst);
    }
    cout << ans << endl;
}


Measured memory_bytes: 3212
A,B,M = map(int,input().split())

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

mi = min(a) + min(b)

for i in range(M):
    x,y,c = map(int,input().split())
    x -= 1
    y -= 1
    mi = min(mi,a[x] + b[y] - c)

print(mi)

Measured memory_bytes: 70596
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const ll P=1000000007;
const int maxn=5010;
int n,m,cnt,rt,mn,sum;
ll ans;
int head[maxn],to[maxn<<1],nxt[maxn<<1],siz[maxn],fa[maxn],v[maxn];
ll jc[maxn],jcc[maxn],ine[maxn],f[maxn],g[maxn],h[maxn];
inline void add(int a,int b)
{
	to[cnt]=b,nxt[cnt]=head[a],head[a]=cnt++;
}
void dfs(int x)
{
	siz[x]=1;
	int i,tmp=0;
	for(i=head[x];i!=-1;i=nxt[i])	if(to[i]!=fa[x])
		fa[to[i]]=x,dfs(to[i]),siz[x]+=siz[to[i]],tmp=max(tmp,siz[to[i]]);
	tmp=max(tmp,n-siz[x]);
	if(tmp<mn)	mn=tmp,rt=x;
}
inline ll c(int a,int b)
{
	if(a<b)	return 0;
	return jc[a]*jcc[b]%P*jcc[a-b]%P;
}
inline int rd()
{
	int ret=0,f=1;	char gc=getchar();
	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}
	while(gc>='0'&&gc<='9')	ret=ret*10+(gc^'0'),gc=getchar();
	return ret*f;
}
int main()
{
	n=rd();
	int i,j,k,a,b;
	memset(head,-1,sizeof(head));
	jc[0]=jcc[0]=ine[0]=jc[1]=jcc[1]=ine[1]=1;
	for(i=2;i<=n;i++)	jc[i]=jc[i-1]*i%P,ine[i]=P-(P/i)*ine[P%i]%P,jcc[i]=jcc[i-1]*ine[i]%P;
	for(i=1;i<n;i++)	a=rd(),b=rd(),add(a,b),add(b,a);
	mn=1<<30,dfs(1);
	if(mn+mn==n)
	{
		printf("%lld",jc[n/2]*jc[n/2]%P);
		return 0;
	}
	for(i=head[rt];i!=-1;i=nxt[i])
	{
		if(to[i]==fa[rt])	v[++m]=n-siz[rt];
		else	v[++m]=siz[to[i]];
	}
	f[0]=1;
	for(i=1;i<=m;i++)
	{
		for(j=0;j<=v[i];j++)	g[j]=c(v[i],j)*c(v[i],j)%P*jc[j]%P;
		memset(h,0,sizeof(h[0])*(sum+v[i]+2));
		for(j=0;j<=sum;j++)	for(k=0;k<=v[i];k++)	h[j+k]=(h[j+k]+f[j]*g[k])%P;
		memcpy(f,h,sizeof(h[0])*(sum+v[i]+2));
		sum+=v[i];
	}
	for(i=n;i>=0;i--)
	{
		f[i]=f[i]*jc[n-i]%P;
		for(j=i+1;j<=n;j++)	f[i]=(f[i]-f[j]*c(j,i))%P;
	}
	printf("%lld",(f[0]+P)%P);
	return 0;
}


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

int main(void) {
  ll N;
  cin >> N;
  vector<ll> A(N + 1);
  vector<ll> B(N);
  REP(i, 0, N + 1) cin >> A[i];
  REP(i, 0, N) cin >> B[i];

  ll ans = 0, t = 0;
  REP(i, 0, N) {
    ans += min(A[i], t);
    A[i] = max(A[i] - t, 0LL);

    ans += min(A[i], B[i]);
    t = max(B[i] - A[i], 0LL);
  }
  ans += min(A[N], t);

  cout << ans << endl;
}

Measured memory_bytes: 1792
N = int(input())
A = list(map(int, input().split()))
x = 1

for i in range(N):
  if A[i] == 0:
    print(0)
    exit()  
 
for i in range(N):
  x = x * A[i]
  if x > 10**18:
    print(-1)
    exit()
  
print(x)

Measured memory_bytes: 21640
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#define rep(i, n) for(int i = 0;i < n;i++)
#define reprb(i, n) for(int i = n;i >= 0;i--)
#define reps(i, m, n) for(int i = m;i < n;i++)
#define repsb(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
int main(int argc,char * argv[])
{
	int n,num,sum=0,dig=0;
	cin>>n;
	num=n;
	if(n%10==0){
		cout<<10<<endl;
		return 0;
	}
	while(num){
		dig=num%10;
		sum=sum+dig;
		num=num/10;
	}

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define dhoom ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);  
typedef long long ll;
typedef long double ld;
const ll inf = 1e18;
const int nax = 2e6 + 7;
const ll mod = 1e9 + 7;
//ll tree[4 * nax];
//9uS-22RSwk7gQqh
ll gcd(ll a , ll b){
	if(b == 0) return a;
	return gcd(b , a % b);	
}
ll lcm(ll a , ll b){
	ll g = gcd(a , b);
	ll lc = (a/g) * b;
	return lc;
}
map< string , int > mp;
int main()
{
	dhoom;
	int n , m;
	cin >> n >> m;
	int x , y;
	cin >> x >> y;
	int a[n + 1] , b[m + 1];
  	a[n] = x;
  	b[m] = y;
	for(int i = 0 ; i < n ;i++)
		cin >> a[i];
	for(int i = 0 ; i < m; i++)
		cin >> b[i];
	sort(a , a + n + 1);
	sort(b , b + m + 1);
	if(b[0] > a[n])
		cout << "No War" << endl;
	else
		cout << "War" << endl;
	return 0;
} 



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

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

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

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

typedef long long int ll;
using ll = long long int;
using ull = long long unsigned int;
using Int = long long int;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//edit
class Solve {
public:
    void solve() {
        Int N;
        vector<Int> tapu(5);
        cin >> N;
        rep(i, 0, 5) cin >> tapu[i];

        Int min_v = N, min_k = -1;

        for (int i = 0; i < 5; ++i) {
            if (min_v > tapu[i]) {
                min_v = tapu[i];
                min_k = i;
            }
        }
        if (min_k == -1) {
            cout << 5 << endl;
            return;
        }


//        Int ans = (N - min_v - 1) / min_v + (4 - min_k);
        Int ans = 4 + (N + min_v - 1) / min_v;
        cout << ans << endl;
    }
};


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

    Solve().solve();


    return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define rep(i, m, n) for (lli i = m; i < (n); i++)
#define repe(i, m, n) for (lli i = m; i <= (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((lli)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define _GLIBCXX_DEBUG
const lli INF = 2147483647;
const lli MINF = -2147483648;
const lli LINF = 9223372036854775807;
const lli MOD = 1000000007; //10^9+7
const double PI = acos(-1);
#define SORT(n) sort(n.begin(), n.end())
#define SORTR(n) sort(n.begin(), n.end(), greater<int>())
#define REV(n) reverse(n.begin(), n.end())
#define pb push_back
#define eb emplace_back
#define mp make_pair
#pragma GCC optimize("Ofast")
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vlli = vector<lli>;
using vs = vector<string>;
using ll = long long;
// vector入力
template <typename T>
istream &operator>>(istream &is, vector<T> &vec)
{
  for (T &x : vec)
    is >> x;
  return is;
}
// vector出力
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec)
{
  // os << '{';
  for (int i = 0; i < vec.size(); i++)
  {
    os << vec[i] << (i + 1 == vec.size() ? "" : "");
  }
  // os << '}';
  return os;
}
// aよりもbが大きいならばaをbで更新する(更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T &b)
{
  if (a < b)
  {
    a = b; // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する(更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T &b)
{
  if (a > b)
  {
    a = b; // aをbで更新
    return true;
  }
  return false;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  lli h1, h2, k, n, w, ans = 0, count = 0;
  double m1, m2, a, b, c;
  string s, t;
  vector<pair<string, pair<lli, lli>>> pr;
  cin >> h1 >> m1 >> h2 >> m2 >> k;
  a = m1 / 60;
  b = m2 / 60;
  c = (b / 60) - (a / 60);
  ans = (h2 - h1 + (b - a)) * 60;
  ans -= k;
  cout << ans << endl;
  // cout << a << endl;
  // cout << b << endl;
  // cout << c << endl;
}

Measured memory_bytes: 3828
N = int(input())
Aij = []
for i in range(N):
    Aij.append([int(i) for i in input().split()])

dp = [[0]*3]*N

dp[0] = Aij[0]

for i in range(1,N):
    a,b,c = dp[i-1]
    dp[i][0] = Aij[i][0] + max(b, c)
    dp[i][1] = Aij[i][1] + max(c, a)
    dp[i][2] = Aij[i][2] + max(a, b)

    ### このやり方はなにかまずい(中身が書き換わっている？)
    # dp[i][0] = Aij[i][0] + max(dp[i-1][1], dp[i-1][2])
    # dp[i][1] = Aij[i][1] + max(dp[i-1][2], dp[i-1][0])
    # dp[i][2] = Aij[i][2] + max(dp[i-1][0], dp[i-1][1])


print(max(dp[-1]))

Measured memory_bytes: 25076
#include <bits/stdc++.h>
#define F(i,j,k) for(int i=(j);i<=(k);++i)
#define D(i,j,k) for(int i=(j);i>=(k);--i)
#define rep(it,s) for(auto it=s.begin();it!=s.end();++it)
#define Rep(a,s) for(auto a:s)
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
template<class Type>inline ll quick_pow(Type x,Type y,Type MOD){
   ll res=1;
   while(y){
      if(y&1)res=res*x%MOD;
      x=x*x%MOD,y>>=1;
   }
   return res;
}
template<class Type>inline ll inv(Type x,Type MOD){return quick_pow(x,MOD-2);}
template<class Type>inline void read(Type &x){
   x=0;static int f=1;char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
   while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
   x*=f;
}
const int N=2005;
const int INF=0x3f3f3f3f;
int n,K,root,dep[N],res,_res,__res,ans=INF;
vector<int>E[N];
inline void add(int x,int y){
    E[x].PB(y),E[y].PB(x);
}
void dfs(int x,int f){
    dep[x]=dep[f]+1;
    if(dep[x]-dep[root]>K/2)++res;
    if(dep[x]-dep[root]==K/2+1)++__res;
    Rep(y,E[x]){
        if(y==f)continue;
        dfs(y,x);
    }
    if(dep[x]==dep[root]+1){
        _res=max(_res,__res);
        __res=0;
    }
}
int main(){
   #ifndef ONLINE_JUDGE
      freopen("in.txt","r",stdin);
      freopen("out.txt","w",stdout);
   #endif
   read(n),read(K);
   int tx,ty;
   F(i,1,n-1){
       read(tx),read(ty);
       add(tx,ty);
   }
   F(i,1,n){
       res=0,_res=0;
       dfs(root=i,0);
       if(K&1)ans=min(ans,res-_res);
       else ans=min(ans,res);
   }
   cout<<ans<<endl;
   return 0;
}


Measured memory_bytes: 3776
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(vec) vec.begin(), vec.end()
#define rALL(vec) vec.rbegin(), vec.rend()
using namespace std;
using ll = long long;
// ------------------------------

int main() {
    string S;
    cin >> S;
    vector<string> vec = {"AKIHABARA", "AKIHBARA", "AKIHABRA", "AKIHABAR", "AKIHBRA", "AKIHBAR", "AKIHBR", "AKIHABR", "KIHBR", "KIHBRA", "KIHBAR", "KIHBARA", "KIHABR", "KIHABRA", "KIHABAR", "KIHABARA"};
    for (string a : vec) {
        if (a == S) {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
    return 0;
}

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

int main() {
  int n = 0;
  int i;
  long long y = 100;
  long long x;
  cin >> x;
  // n = ceil((log10(x) - 2) / log10(1.01));
  // if (x < 1000000000) {
  for (i = 0; y < x; i++) {
    y *= 1.01;
  }
  // } else {
  // y = 1000000000;
  // for (i = 1677; y <  x; i++) {
  // y *= 1.01;
  // }
  // }
  cout << i << endl;
}

Measured memory_bytes: 3644
#include<iostream>
#include<string>
using namespace std;
int main(void){
  int N,A = 0;
  cin >> N;
  int *H=(int*)malloc(N*sizeof(N));
  for (int i=0;i<N;i++){
    cin >> A;
    H[A-1]=i+1;
  }
  for(int i=0;i<N;i++)
   cout << H[i] << " ";
}

Measured memory_bytes: 1152
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (int)(m); i < (int)(n); ++i)

const int MOD = 1e+9 + 7;


template <typename T>
T pow_mod(T n, T p, T m)  // (n^p) % m
{
    if(p == 0) return 1;
    if(p%2 == 1) return pow_mod<T>(n, p-1, m) * n % m;
    else{
        T tmp = pow_mod<T>(n, p/2, m) % m;
        return tmp * tmp % m;
    }
}


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

    vector<long long> nC(n+1, 1), n_1C(n+1, 1);
    FOR(i, 1, n+1){
        n_1C[i] = ((n-i)*n_1C[i-1])%MOD*pow_mod<long long>(i, MOD-2, MOD);
        n_1C[i] %= MOD;
    }
    FOR(i, 1, n+1){
        nC[i] = n_1C[i-1] + n_1C[i];
        nC[i] %= MOD;
    }

    long long ans = 0;
    FOR(i, 0, min(n, k+1)){
        ans += (nC[i]*n_1C[n-i-1]) % MOD;
        ans %= MOD;
    }
    // if(k%2 == 0) cout << (ans+1)%MOD << endl;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3328
a = int(input())
b = int(input())
c = int(input())
x = int(input())

counter = 0
calc_x = 0

ans = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if i * 500 + j * 100 + k * 50 == x:
                ans += 1
print(ans)


Measured memory_bytes: 3060
#[allow(unused_imports)]
use std::cmp;

// Input macro from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
  (source = $s:expr, $($r:tt)*) => {
    let mut iter = $s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
  ($($r:tt)*) => {
    let s = {
      use std::io::Read;
      let mut s = String::new();
      std::io::stdin().read_to_string(&mut s).unwrap();
      s
    };
    let mut iter = s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
}

macro_rules! input_inner {
  ($iter:expr) => {};
  ($iter:expr, ) => {};

  ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
    let $var = read_value!($iter, $t);
    input_inner!{$iter $($r)*}
  };
}

macro_rules! read_value {
  ($iter:expr, ( $($t:tt),* )) => {
    ( $(read_value!($iter, $t)),* )
  };

  ($iter:expr, [ $t:tt ; $len:expr ]) => {
    (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
  };

  ($iter:expr, chars) => {
    read_value!($iter, String).chars().collect::<Vec<char>>()
  };

  ($iter:expr, usize1) => {
    read_value!($iter, usize) - 1
  };

  ($iter:expr, $t:ty) => {
    $iter.next().unwrap().parse::<$t>().expect("Parse error")
  };
}

fn main() {
  input! {
    a: chars,
  }
  let mut pop = vec![0i64; 26];
  for &c in &a {
    pop[(c as u32 - 'a' as u32) as usize] += 1;
  }
  let sum: i64 = pop.into_iter().map(|x| x * (x - 1) / 2).sum();
  let n = a.len() as i64;

  println!("{}", n * (n - 1) / 2 - sum + 1);
}


Measured memory_bytes: 4476
import sys

input = sys.stdin.readline
N = int(input())
Ss = {}
for i in range(N):
    s = ''.join(sorted(list(input().rstrip("\n"))))
    if s in Ss:
        Ss[s] += 1
    else:
        Ss[s] = 1

c = 0
for s in Ss.values():
    c += (s - 1) * s >> 1

print(c)

Measured memory_bytes: 57052
type Scanner() = class
    let mutable hold = [||]
    let mutable index = 0
    member public this.Next() =
        if hold.Length > index
        then 
            index <- index + 1
            hold.[index - 1]
        else
            let mutable st = stdin.ReadLine()
            while st = "" do st <- stdin.ReadLine()
            hold <- st.Split(' ')
            if hold.Length = 0
            then
                this.Next()
            else
                index <- 1
                hold.[index - 1]
            
    member public this.NextI32() =
        this.Next() |> int

    member public this.ArrayI32(n: int) =
        [|for _ in 0 .. n - 1 -> this.NextI32()|]

    member public this.NextI64() =
        this.Next() |> int64
    
    member public this.ArrayI64(n: int) =
        [|for _ in 0 .. n - 1 -> this.NextI64()|]

    member public this.NextF32() =
        this.Next() |> float32
    
    member public this.ArrayF32(n: int) =
        [|for _ in 0 .. n - 1 -> this.NextF32()|]

    member public this.NextF64() =
        this.Next() |> double
    
    member public this.ArrayF64(n: int) =
        [|for _ in 0 .. n - 1 -> this.NextF64()|]

    member public __.Tuple2List n (f : int -> 'a list) =
        [|for _ in 0 .. n - 1 -> f 2 |> fun x -> x.[0], x.[1]|]
    
    member public __.Tuple3List n (f : int -> 'a list) =
        [|for _ in 0 .. n - 1 -> f 3 |> fun x -> x.[0], x.[1], x.[2]|]

end

[<EntryPoint>]
let main _ =
    let scanner = Scanner()
    let n = scanner.NextI32()
    let m = scanner.NextI32()
    let liA = scanner.ArrayI32 m |> Array.sort
    if n >= m then 0
    else
        let a = 
            [|for i in 0..m-2 -> liA.[i + 1] - liA.[i]|]
            |> Array.sortDescending
        let b = Array.skip (n - 1) a |> Array.sum
        b
    |> printfn "%i"

    0


Measured memory_bytes: 30936
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <cmath>
#include <stdio.h>
#include <sstream>
#define int_inf 1000000000 //1e9
#define ll_inf  1000000000000000000 //1e18
using namespace std;
template <typename T> std::string to_string(const T& t){
	std::ostringstream os; os<<t; return os.str();
}

int main(){
	string a, b, c;
	cin>>a>>b>>c;
	
	if(a[a.size()-1]==b[0] && b[b.size()-1]==c[0]) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}




Measured memory_bytes: 256
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    S = input()
    T = input()

    if S==T[:-1]:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

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

using namespace std;
typedef long long  LL;
LL gcd(LL x, LL y)
{
     if (!y) return x;
     return gcd(y, x%y);
}
int main()
{
    LL s=1, a;
    int n;
    scanf("%d", &n);
    for (int i=1; i<=n; i++)
    {
        cin>>a;
        s=a/gcd(a,s)*s;
    }
    cout<<s;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        List<Long> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(Long.parseLong(sc.next()));
        }
        sc.close();

        // 主処理
        long MAX = 1000000000000000000L;
        long num = 1;
        long result = 0;

        for (int i = 0; i < n; i++) {
            if ((double) MAX / list.get(i) < num) {
                result = -1;
                break;
            }
            num *= list.get(i);
        }

        if (result != -1 && num <= MAX) {
            result = num;
        } else {
            result = -1;
        }

        if (list.contains(0L)) {
            result = 0;
        }

        // 出力
        System.out.println(result);
    }
}


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

// 二分搜索
bool BinarySearch(int A[], int n, int key) {
    int left = 0 , right = n, mid;

    while (left < right) {
        mid = (left + right) / 2;
        if (key == A[mid])
            return true;

        if(key > A[mid])
            left = mid + 1;
        if (key < A[mid])
            right = mid;
    }
    return false;

}
int main() {
    int n, q, key;
    int sum = 0;
    int A[100000 + 10];
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &A[i]);
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%d", &key);
        if (BinarySearch(A, n, key))
            sum++;
    }
    printf("%d\n", sum);
}


Measured memory_bytes: 3544
#include <iostream>
#include <vector>
#include<queue>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const long long INF = 1LL << 60;

vector<vector<int>> G;
vector<int> deg;

int dp[100100];

int main() {
	int n, m;
	cin >> n >> m;
	G.assign(n, vector<int>());
	deg.assign(n, 0);
	for (int i = 0;i < m;i++) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		G[x].push_back(y);
		deg[y]++;
	}
	queue<int> que;
	for (int v = 0;v < n;v++)if (deg[v] == 0)que.push(v);

	while (!que.empty()) {
		int v = que.front(); que.pop();
		for (auto nv : G[v]) {
			deg[nv]--;
			if (deg[nv] == 0) {
				que.push(nv);
				chmax(dp[nv], dp[v] + 1);
			}
		}
	}

	int res = 0;
	for (int v = 0;v < n;v++)chmax(res, dp[v]);
	cout << res << endl;

}


Measured memory_bytes: 6528
#include <array>
#include <climits>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }
 
enum FACE {SOUTH, EAST, TOP, BOTTOM, WEST, NORTH};
 
typedef array<int, 6> A;
 
struct dice {
	A value;
 
	dice(const A &value_):value(value_) {}
 
	void roll(FACE a, FACE b, FACE c, FACE d) {
		const int t = value[a];
		value[a] = value[b];
		value[b] = value[c];
		value[c] = value[d];
		value[d] = t;
	}
 
	int operator[](int f) const { return value[f]; }
 
	void north() { roll(TOP, SOUTH, BOTTOM, NORTH); }
	void east()  { roll(TOP, WEST,  BOTTOM, EAST ); }
	void ccw()   { roll(NORTH, EAST, SOUTH, WEST ); }
};
 
int calc(vector<dice> &dies) {
	int res = 0;
	for(int i = 0; i < 6; ++i) {
		unordered_map<int, int> cnt;
		for(const auto &d : dies) {
			++cnt[d[i]];
		}
 
		int mx = 0;
		for(const auto &e : cnt) {
			mx = max(mx, e.second);
		}
 
		res += dies.size() - mx;
	}
 
	return res;
}
 
int dfs(unsigned idx, vector<dice> &dies) {
	if(idx == dies.size()) return calc(dies);

	int res = INT_MAX;
 
	for(int i = 0; i < 4; ++i) {
		for(int j = 0; j < 4; ++j) {
			dies[idx].north();
			chmin(res, dfs(idx + 1, dies));
		}
		dies[idx].ccw();
	}

	dies[idx].east();
	for(int i = 0; i < 2; ++i) {
		for(int j = 0; j < 4; ++j) {
			dies[idx].north();
			chmin(res, dfs(idx + 1, dies));
		}
		dies[idx].ccw();
		dies[idx].ccw();
	}

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

	for(int n; cin >> n && n;) {
		unordered_map<string, int> encoder;
		vector<dice> dies;
		dies.reserve(n);
 
		for(int i = 0; i < n; ++i) {
			A value;
			for(auto &e : value) {
				string s;
				cin >> s;
 
				if(!encoder.count(s)) encoder.insert({s, encoder.size()});
				e = encoder.at(s);
			}
 
			dies.emplace_back(value);
		}
 
		cout << dfs(1, dies) << endl;
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1232
#include <bits/stdc++.h>
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define MP make_pair
#define Mod 998244353
#define MOD 1000000007
using namespace std;
using lint = long long;
using vi = vector<lint>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<lint, lint>;

// cout << fixed << setprecision(12)

lint modpow(lint a, lint n, lint m = MOD){
  lint ans = 1;
  while(n>0){
    if(n%2==1) ans *= a; ans %= m;
    a *= a; a %= m;
    n /= 2;
  }
  return ans;
}

lint inv(lint a, lint m = MOD){
  return modpow(a, m-2, m);
}

///////////////////////////////////

int main(){
  lint N; cin>>N;
  vi ans(10020,0);
  
  for(lint x=1; x<=100; x++){
    for(lint y=1; y<=100; y++){
      for(lint z=1; z<100; z++){
        
        lint r = x*x + y*y + z*z + x*y + y*z + z*x;
        if(r<10010) ans[r]++;
        
      }
    }
  }
  
  for(lint i=1; i<=N; i++){
    cout << ans[i] << endl;
  }
}
    
 

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

using namespace std;
using ll = long long;
#define int ll
using PII = pair<int, int>;
template <typename T> using V = vector<T>;
template <typename T> using VV = vector<V<T>>;
template <typename T> using VVV = vector<VV<T>>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll INF = (1LL<<60);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

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

  int n;
  cin >> n;
  V<int> a(n), b(n);
  REP(i, n) cin >> a[i] >> b[i];

  int ret = 0, tmp = 0;
  REP(i, n) {
    if(a[i] < b[i]) ret += b[i];
    if(a[i] == b[i]) tmp += b[i];
  }
  if(ret != 0) ret += tmp;

  int sum = 0;
  REP(i, n) sum += a[i];
  // cout << sum << endl;

  int ans = ret;
  REP(i, n) {
    if(a[i] > b[i]) {
      // cout << ans << " " << sum - b[i] << endl;
      chmax(ans, sum-b[i]);
    }
  }

  cout << ans << endl;

  return 0;
}


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

bool check(int a){return a%3==0?true:false;}

int main(){
    int a,b;
    cin>>a>>b;
    if(check(a)||check(b)||check(a+b))cout<<"Possible"<<endl;
    else cout<<"Impossible"<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

        String str = stdIn.next();

        char [] cs = str.toCharArray();

        int n = 0;

        int counter = 0;
        boolean flag = false;

        for(int i=0; i<cs.length; i++){
            if((cs[i] == '0' && !flag) || (cs[i] == '1' && flag)){

            }else{
                counter++;
            }
            flag = (flag) ? false : true;
        }

        n = counter;
        counter = 0;
        flag = true;

        for(int i=0; i<cs.length; i++){
            if((cs[i] == '0' && !flag) || (cs[i] == '1' && flag)){

            }else{
                counter++;
            }
            flag = (flag) ? false : true;
        }
      
      if(n>counter){
        n = counter;
      }

        System.out.println(n);
    }
}

Measured memory_bytes: 27092
n = int(input())
a = list(map(int,input().split()))

def gcd(x,y):
    while y != 0:
        x,y = y,x%y
    return x

l,r = [0],[0]
for i in range(n-1):
    l.append(gcd(l[-1],a[i]))
    r.append(gcd(r[-1],a[n-i-1]))

ans = 0
for i in range(n):
    ans = max(ans,gcd(l[i],r[n-i-1]))
print(ans)


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

int main() {
	int n;
	cin >> n;
	vector<int> b(n - 1);
	for (int i = 0; i < n - 1; i++) {
		cin >> b[i];
	}

	vector<int> ans(n);
	ans[0] = b[0];
	ans[n - 1] = b[n - 2];
	for (int i = 1; i < n - 1; i++) {
		ans[i] = min(b[i - 1], b[i]);
	}

	int sum = 0;
	for (int i = 0; i < n; i++) {
		sum += ans[i];
	}

	cout << sum << endl;
}

Measured memory_bytes: 256
#include <math.h>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define PI 3.14159265358979323846264338327950L
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))

int main() {
  int r, g, b;
  cin >> r >> g >> b;
  int num = 100 * r + 10 * g + b;

  if (num % 4 == 0)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}


Measured memory_bytes: 256
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    g = False
    way = [[] for _ in range(n+1)]
    for _ in range(m):
        u,v,s = map(int,ipt().split())
        way[u].append((v,s))
        way[v].append((u,s))
    ans = [10**18]*(n+1)
    par = [0]*(n+1)
    ans[1] = 1
    q = [1]
    par[1] = 1
    while q:
        qi = q.pop()
        pqi = par[qi]
        aqi = ans[qi]
        for i,si in way[qi]:
            if ans[i] == 10**18:
                q.append(i)
                ans[i] = si-aqi
                par[i] = pqi*(-1)
            elif par[i] == pqi:
                g = True
                a = ans[i]+si-aqi
                if a&1:
                    print(0)
                    exit()
                stt = i
                sa = a//2
                if sa <= 0:
                    print(0)
                    exit()
                break
            elif ans[i] != si-aqi:
                print(0)
                exit()
        if g:
            break
    if g:
        ans = [10**18]*(n+1)
        ans[stt] = sa
        q = [stt]
        while q:
            qi = q.pop()
            aqi = ans[qi]
            for i,si in way[qi]:
                if ans[i] == 10**18:
                    if si-aqi <= 0:
                        print(0)
                        exit()
                    q.append(i)
                    ans[i] = si-aqi
                elif ans[i] != si-aqi:
                    print(0)
                    exit()
        print(1)
    else:
        p1 = []
        m1 = []
        for i in range(1,n+1):
            if par[i] == 1:
                p1.append(ans[i])
            else:
                m1.append(ans[i])
        print(max(0,min(m1)+min(p1)-1))



    return None

if __name__ == '__main__':
    main()


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



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


n, m = LI()

fac = [1] * (m + 1)
inv = [1] * (m + 1)
for j in range(1, m + 1):
    fac[j] = fac[j-1] * j % mod


inv[m] = pow(fac[m], mod-2, mod)
for j in range(m-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(m, r):
    if r > m or m < 0 or r < 0:
        return 0
    return fac[m] * inv[m - r] * inv[r] % mod

ret = 0
for i in range(n + 1):
    c = comb(m, i) * comb(n, i) % mod * fac[i] % mod * pow(comb(m - i, (n - i)) * fac[n - i] % mod, 2, mod) % mod
    if i % 2:
        ret -= c
    else:
        ret += c
    ret %= mod

print(ret)







Measured memory_bytes: 96708
def dfs(v):
    visit[v] = True
    for adj_v in [v for v, adj in enumerate(g[v]) if adj and not visit[v]]:
        dfs(adj_v)

N, M = map(int, input().split())
a, b = [0] * M, [0] * M
for i in range(M):
    a[i], b[i] = map(int, input().split())

g = [[False] * N for _ in range(N)]
for _a, _b in zip(a, b):
    g[_a-1][_b-1] = True
    g[_b-1][_a-1] = True

ans = 0
for _a, _b in zip(a, b):
    g[_a-1][_b-1] = False
    g[_b-1][_a-1] = False
    visit = [False] * N
    dfs(0)
    if not all(visit):
        ans += 1
    g[_a-1][_b-1] = True
    g[_b-1][_a-1] = True
print(ans)

Measured memory_bytes: 3064