akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,b)     for(int i=a;i<(b);i++)
#define lop(n)         for(int i=0;i<n;i++)
#define revlop(n)      for(int i=n-1;i>=0;i--)
#define trav(a,x)      for(auto & a :x)
#define all(x)         begin(x),end(x)
#define pb             push_back
#define pii            pair<int,int>
#define vpii           vector<pii>
#define F              first
#define S              second
#define mod            1000000007
#define inf            1e18
#define ps(x,y)        fixed<<setprecision(y)<<x
#define mk(arr,n,type) type *arr=new type[n];
#define w(x)           int x; cin>>x; 

typedef long long ll;
typedef vector<int> vi;

// functions
ll gcd(ll a, ll b){if(b==0) return a; return gcd(b,a%b);}
ll lcm(ll a, ll b){return (a*b)/gcd(a,b);}
ll power(ll x,ll y,ll p ){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int setbits(ll x)  {  return __builtin_popcount(x);  }
ll factorial(ll n) {  ll f = 1; if (n == 0|| n == 1)  return 1;  for (ll i = 2; i <= n; i++)  f = f * i; return f; }

void solve()
{ 
  int n,d;
  cin>>n>>d;
  ll c=0,x,y;
  for(int i=0;i<n;i++)
  {
    cin>>x;
    cin>>y;
     if(x<0) x=-x;
     if(y<0) y=-y;
    if(sqrt(x*x+y*y)<=d)
      c++;
  }
  cout<<c<<'\n';
}

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

  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif

   int test=1;
   //cin>>test;
   while(test--)
     solve();

  return 0;
}



Measured memory_bytes: 3680
#include <bits/stdc++.h>
#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define PRINT(x) cout << (x) << "\n"
using namespace std;
using ll = long long; using pint = pair<int, int>; using pll = pair<ll, ll>;
const long long MOD = 1000000007;

ll N, A[200010];

signed main(){
    cin >> N;
    REP(i, N) cin >> A[i];
    sort(A, A + N);
    ll ans = 0;
    if(A[0] < 0 &&  A[N - 1] < 0){
        ans = A[N - 1] - accumulate(A, A + N - 1, 0LL);
        PRINT(ans);
    }else if(A[0] > 0 && A[N - 1] > 0){
        ans = accumulate(A + 1, A + N, 0LL) - A[0];
        PRINT(ans);
    }else{ 
        REP(i, N) ans += abs(A[i]);
        PRINT(ans);
    }
    ll l = 0, r = N - 1;
    while(A[r - 1] > 0){
        cout << A[l] << " " << A[r] << endl;
        A[l] = A[l] - A[r];
        r--;
    }
    l = r - 1;
    while(l >= 0){
        cout << A[r] << " " << A[l] << endl;
        A[r] = A[r] - A[l];
        l--;
    }
    return 0;
}

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

int main() {
    uint64_t N;
    cin >> N;
    vector<uint64_t> A(N + 1);
    vector<uint64_t> B(N);
    rep(i, N + 1) cin >> A[i];
    rep(i, N) cin >> B[i];
    uint64_t sum = 0;
    rep(i, N) {
        if (A[i] >= B[i])
            sum += B
                [i];  // B[i]の戦闘力を使い切ってA[i]の一部を倒す.i+1番以降はA[i]の敵には触れられないので関係ない。
        else {
            if (B[i] - A[i] <= A[i + 1]) {  // B[i]の戦闘力をA[i+1]で使い切るとき
                A[i + 1] -=
                    B[i] - A[i];  // A[i+1]の残りの数は次回に関わるので計算
                sum += B[i];
            } else {  // B[i]の戦闘力が使い切らないとき
                sum += A[i] + A[i + 1];
                A[i + 1] = 0;
            }
        }
    }
    cout << sum << endl;
    return 0;
}


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

using namespace std;
int n;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 10;
vector<int> edges[MAXN];
pair<long long int, long long int> dp[MAXN];
pair<long long int, long long int> null = {-1, -1};

// ans.first - Black, ans.second - White
pair<int, int> dfs(int start = 1, int parent = 0){
    if(dp[start] != null){
        return dp[start];
    }else{
        pair<long long int, long long int> ans = {1, 1};
        for(int neigh : edges[start]){
            if(neigh != parent){
               auto temp_ans = dfs(neigh, start);
               // White
               ans.second = ans.second * (temp_ans.first + temp_ans.second) % MOD;
               
               // Black
               ans.first = (ans.first * temp_ans.second) % MOD; 
            }
        }
        dp[start] = ans;
        return ans;
    }
}

int main(){
    cin >> n;
    
    for(int i = 0; i < n - 1; ++i){
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
        dp[i] = null;
    }
    dp[n - 1] = null;
    dp[n] = null;
    auto ans =  dfs();
    long long int final_ans = ans.first + ans.second;
    final_ans %= MOD;
    cout << final_ans << "\n";
    return 0;
}

Measured memory_bytes: 17548
// inputに入力データ全体が入る
function Main(input) {
	var a = input.split("\n")[0];
	var b = input.split("\n")[1];

	var ans = false;
	for(var i=0;i<a.length;i++){
		if(a == b){
			ans = true;
			break;
		}
		a = a.substring(a.length-1,a.length) + a.substring(0,a.length-1);
	}
	console.log(ans?"Yes":"No");
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

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

  string s;
  cin >> s;

  int ans = 0;
  rep(i, 4) {
    if (s[i] == '2') ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
nm = gets.split.map(&:to_i)
mod = 10 ** 9 + 7
fac = [1]
1.upto(nm.max){|i| fac << fac.last * i % mod}

case nm[0] - nm[1]
when 0
    puts fac[nm[0]] * fac[nm[1]] * 2 % mod
when 1, -1
    puts fac[nm[0]] * fac[nm[1]] % mod
else
    puts 0
end

Measured memory_bytes: 2684
from collections import deque

N = int(input())
data = [[] for i in range(N+1)]
for i in range(N-1):
    u,v,w = map(int,input().split())
    data[u].append([v,w])
    data[v].append([u,w])

que = deque([1])
seen = [-1]*(N+1)
seen[1] = 0
cnt = 1
while cnt < N:
    cur = que.popleft()
    for item in data[cur]:
        if seen[item[0]] == -1:
            seen[item[0]] = (seen[cur]+item[1]%2)%2
            cnt += 1
            que.append(item[0])

for i in range(1,N+1):
    print(seen[i])

Measured memory_bytes: 45364
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <ctime>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MaxN = 1e5 + 5;
map <int, int> m;
int dat[MaxN];
LL ans;
int n;
int x;

int main() {
	while(scanf("%d", &n) != EOF) {
		int cnt = 0;
		ans = 0;
		for(int i = 1; i <= n; i++) {
			scanf("%d", &x);
			if(m[x] == 0) dat[cnt++] = x;
			m[x]++;
		}
		for(int i = 0; i < cnt; i++) {
			if(m[dat[i]] < dat[i]) ans+= m[dat[i]];
			else ans += m[dat[i]] - dat[i];
		}
		printf("%lld", ans);
		return 0;
	}
	return 0;
}

Measured memory_bytes: 5120
#include <iostream>
#include <cmath>
using namespace std;
int solve(int N);
int main(){
  int N;
  int six=0;
  int nine=0;
  int i, j;
  int cnt =0;
  cin >> N;
  /*
  while(N != 0){
    if(N==12){
      cnt +=2;
      break;
    }else if(N==13){
      cnt +=3;
      break;
    }else if(N==14){
      cnt +=4;
      break;
    }
    for(i=0;pow(9,i) <= N;i++);
    for(j=0;pow(6,j) <= N;j++);
    nine=pow(9,i-1);
    six=pow(6,j-1);
    //cout << i <<endl;
    //cout << j << endl;
    //cin >> cnt;
    if(nine>=six){
      N -= nine;
    }else{
      N -= six;
    }
    cnt++;
  }*/
  cnt = solve(N);
  cout << cnt << endl;
}
int solve(int N){
  int i, j, nine, six;
  for(i=0;pow(9,i) <= N;i++);
  for(j=0;pow(6,j) <= N;j++);
  nine=pow(9,i-1);
  six=pow(6,j-1);

  if(N-nine != 0 && N-six !=0){
    nine = solve(N-nine);
    six = solve(N-six);
  }else{
    return 1;
  }

  if(nine >= six){
    return six+1;
  }else{
    return nine+1;
  }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

main(){
  int n, a, b, m = 0, d;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> a >> b;
    if(m < b){
      m = b;
      d = a;
    }else if(m == b && d > a) d = a;
  }
  cout << d << ' ' << m << endl;
}

Measured memory_bytes: 1164
N, X = map(int, input().split())

burger_size = [1]
patty_num = [1]
for i in range(50):
    burger_size.append(2 * burger_size[-1] + 3)
    patty_num.append(2 * patty_num[-1] + 1)


# レベルnバーガーの下からx段目までに含まれるパティの数を返す
def dfs(n, x):
    if burger_size[n] == x:
        return patty_num[n]

    if x == 1:
        return 0

    elif 1 < x <= 1 + burger_size[n - 1]:
        return dfs(n - 1, x - 1)

    elif x == 1 + burger_size[n - 1] + 1:
        return patty_num[n - 1] + 1

    elif 1 + burger_size[n - 1] + 1 < x < burger_size[n]:
        return patty_num[n - 1] + 1 + dfs(n - 1, x - burger_size[n - 1] - 2)


print(dfs(N, X))


Measured memory_bytes: 9084
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <functional>
#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int w,h,t;
int p;
int add[51][51][51];
int s[51][51];

int main(void){
	scanf("%d%d%d",&w,&h,&t);
	scanf("%d",&p);
	for(int i=0;i<p;i++){
		int x,y,t;
		scanf("%d%d%d",&x,&y,&t);
		add[t][y][x]=1;
	}
	int all=0;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			scanf("%d",&s[i][j]);
		}
	}
	for(int i=0;i<t;i++){
		for(int j=0;j<h;j++){
			for(int k=0;k<w;k++){
				if(s[j][k] && add[i][j][k]){
					all++;
				}
			}
		}
	}
	printf("%d\n",all);

	return 0;
}

Measured memory_bytes: 1380
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


ll a,b,n;



int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> a >> b >> n;
    ll sta = n%b;
    ll kojen = n;
    if(sta != b-1){
        kojen = (n - n%b) - 1;
    }
    ll res = 0;
    if(kojen >= 0) res = (a*kojen) / b  - a*((kojen)/b);
    //cout << res << endl;
    fb(i,n,n-100){
        if(i < 0)break;

        res = max(res, (a*i)/b - a*((i)/b));
    }
    if(b-1 <= n)res = max(res, (a*(b-1))/b - a*((b-1)/b));
    else{
        res = max(res, (a*n)/b - a*((n)/b));
    }
    cout << res;
    return 0;
    ff(i,0,100){
        if(i > n)break;
        res = max(res, (a*i)/b - a*((i)/b));
    }
    ll last = -1;
    if(a == 1 || b == 1){
        cout << res << endl;
        return 0;
    }
    cout << res << endl;
    return 0;
}


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

using namespace std;
#define X first
#define Y second
#define pb push_back
typedef double db;
typedef long long ll;
const int MAXN=1e3,MOD=1e9+7;
int n,A,B,C,D;
ll fac[MAXN+10],inv[MAXN+10],cur,dp[MAXN+10][MAXN+10];

ll quickpow(ll a,ll b)
{
	ll ret=1;
	for(;b;b>>=1,a=a*a%MOD)
		if(b&1) ret=ret*a%MOD;
	return ret;
}
ll P(ll a,ll b)
{return fac[a]*inv[a-b]%MOD;}

int main()
{
	fac[0]=1;
	for(int i=1;i<=MAXN;i++)
		fac[i]=fac[i-1]*i%MOD;
	inv[MAXN]=quickpow(fac[MAXN],MOD-2);
	for(int i=MAXN-1;i>=0;i--)
		inv[i]=inv[i+1]*(i+1)%MOD;
	
	scanf("%d%d%d%d%d",&n,&A,&B,&C,&D);
	dp[A-1][0]=1;
	for(int i=A;i<=B;i++)
	{
		for(int j=0;j<=n;j++)
			dp[i][j]=dp[i-1][j];
		for(int j=0;j<=n;j++)
			for(int k=C,cur=quickpow(inv[i],C);j+k*i<=n&&k<=D;k++,cur=cur*inv[i]%MOD)
				if(dp[i-1][j]) (dp[i][j+k*i]+=dp[i-1][j]*P(n-j,k*i)%MOD*cur%MOD*inv[k]%MOD)%=MOD;
	}
	printf("%lld",dp[B][n]);
	return 0;
}

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

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

    int n;
    cin >> n;

    set<string> st;
    rep(i, n){
        string s;
        cin >> s;
        st.insert(s);
    }

    cout << (int)st.size() << endl;

    return 0;
}

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

int main() {
    int a,b,c;
    cin >> a >> b >> c;
    if (b-a == c-b) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
} 

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstring>
#include <deque>
#include <functional>
#include <initializer_list>
#include <math.h>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <queue>
#include <vector>

#define FOR(i, a, b) for(int (i) = (a); (i) < (b); ++(i))
#define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); --(i))
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) rFOR(i, 0, (n-1))
#define SORT(A) std::sort((A).begin(), (A).end())
#define ALL(A) (A).begin(), (A).end()
// 座標圧縮 (for vector) : ソートしてから使うのが一般的 ; SORT(A) => COORDINATE_COMPRESSION(A)
#define COORDINATE_COMPRESSION(A) (A).erase(unique((A).begin(),(A).end()),(A).end())

using lli = long long int;
using pii = std::pair<int, int>;

void VintOut(std::vector<int>& A){
    const int n = A.size();
    if(n == 0){putchar('\n'); return;}
    printf("%d", A[0]);
    for(int i = 1; i < n; ++i) printf(" %d", A[i]);
    putchar('\n');
}
void VintOut(std::vector<long long int>& A){
    const int n = A.size();
    if(n == 0){ putchar('\n'); return;}
    printf("%lld", A[0]);
    for(int i = 1; i < n; ++i) printf(" %lld", A[i]);
    putchar('\n');
}

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

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

inline bool bitUP(int state, int k){ return (state >> k) & 1; }
inline bool bitUP(long long int state, int k){ return (state >> k) & 1;}


// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

constexpr int inf = 1e8 + 334;
int  A[500][500];
char S[30][30];
std::array<int, 4> X = {1, -1, 0, 0};
std::array<int, 4> Y = {0, 0, 1, -1};

int main(void){
    int H, W; scanf("%d%d", &H, &W);
    REP(i, H) scanf("%s", S[i]);
    REP(i, H*W) REP(j, H*W) A[i][j] = (i == j) ? 0 : inf;
    REP(i, H) REP(j, W)if(S[i][j] == '.'){
        int V = i * W + j;
        REP(k, 4){
            int nx = i + X[k];
            int ny = j + Y[k];
            if(0 <= nx and nx < H and 0 <= ny and ny < W and S[nx][ny] == '.'){
                int U = nx * W + ny;
                A[V][U] = 1;
            }
        }
    }
    REP(k, H * W) REP(i, H * W) REP(j, H * W){
        chmin(A[i][j], A[i][k] + A[k][j]);
    }
    int d = 0;
    REP(i, H * W) REP(j, H* W) if(A[i][j] != inf) chmax(d, A[i][j]);
    printf("%d\n", d);
   

    




    return 0;
}

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

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

print(count)

Measured memory_bytes: 3060
#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
 
typedef long long ll;

#define MP make_pair
#define F first
#define S second

int main(){
	int n,m;
    cin >> n >>m;
    int all=0;
    bool f=true;
    vector<int> a(n);
    for(int i=0;i<n;i++){
    	cin >> a[i];
        all += a[i];
    }
    sort(a.begin(), a.end());
    for(int i=0;i<m;i++){
    	if(a[n-1-i]<(double)all/(4*m)) f=false;
    }
    if(f){
    	cout << "Yes" << endl;
    }else{
    	cout << "No" << endl;
    }
}

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

int main()
{
	int w, h, x, y, r;
	cin.tie(0);
	cin >> w >> h >> x >> y >> r;
	if (x - r < 0 || x + r > w || y - r < 0 || y + r > h) cout << "No" << "\n";
	else cout << "Yes" << "\n";
}


Measured memory_bytes: 3104
#include <iostream>
#define rep(i, n)for(int i=0; i<n; i++)
using namespace std;

int main(){
    int n, ans=0;
    cin >> n;
    for(int i=1; i<=n; i+=2){
        int count = 0;
        for(int j=1; j<=i; j++){
            if(i%j==0) count++;
        }
        if(count==8)ans++;
    }

    cout << ans << endl;

    return 0;
}


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

using namespace std;

int main()
{
    int N;
    cin >> N;
    string S;
    cin >> S;
    long long int r = 0, g = 0, b = 0;
    for (int i = 0; i < S.size(); i++)
    {
        if (S[i] == 'R')
            r++;
        if (S[i] == 'G')
            g++;
        if (S[i] == 'B')
            b++;
    }

    long long int ans = r * g * b;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; i + j < N; j++)
        {
            if (i - j >= 0)
            {
                if (S[i - j] != S[i] && S[i] != S[i + j] && S[i - j] != S[i + j])
                    ans--;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3636
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int s(ll x) {
    if(!x) return 0;
    return x%10+s(x/10);
}
int main() {
    int K;
    scanf("%d",&K);
    ll n=1,d=1;
    printf("%d\n",1); K--;
    while(K--) {
        if(s(n+10*d)*(n+d)>(n+10*d)*s(n+d)) d*=10;
        printf("%lld\n",n+=d);
    }
}


Measured memory_bytes: 128
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
bool com(pair<int,int> a,pair<int,int> b){
    if(a.first!=b.first){
        return a.first>b.first;
    }
    else{
        return a.second>b.second;
    }
}
int fie[2][3100][3100];
int main(){
    int N,T;
    cin>>N>>T;
    pair<int,int> AB[3000];
    for(int i=0;i<N;i++)cin>>AB[i].first>>AB[i].second;
    sort(AB,AB+N,com);
    //for(int i=0;i<N;i++)printf("[%d][%d]\n",AB[i].first,AB[i].second);
    for(int i=0;i<2;i++){
        for(int j=0;j<3100;j++){
            for(int k=0;k<3100;k++){
                fie[i][j][k]=-1;
            }
        }
    }
    fie[0][0][0]=0;
    for(int i=0;i<2;i++){
        for(int j=0;j<N;j++){
            for(int k=0;k<3100;k++){
                if(fie[i][j][k]!=-1){
                    if(i==0){
                        fie[0][j+1][k]=max(fie[i][j][k],fie[0][j+1][k]);
                        fie[1][j+1][k]=max(fie[i][j][k]+AB[j].second,fie[1][j+1][k]);
                        //fie[1][j+1][k+AB[j].first]
                    }
                    else{
                        fie[1][j+1][k]=max(fie[i][j][k],fie[1][j+1][k]);
                        if(k+AB[j].first<3100){
                            fie[1][j+1][k+AB[j].first]=max(fie[i][j][k]+AB[j].second,fie[1][j+1][k+AB[j].first]);
                        }
                    }
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<2;i++){
        for(int k=0;k<T;k++){
            ans=max(ans,fie[i][N][k]);
        }
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 75392
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  ll N;
  cin>>N;
  vector<ll>a(N);
  for(ll i=0;i<N;i++)cin>>a[i];

  vector<ll>s(N+1,0);
  map<ll,ll>mp;
  for(ll i=0;i<N;i++){
    s[i+1]=s[i]+a[i];
  }
  for(int i=0;i<N+1;i++){
    mp[s[i]]++;
  }
  ll ans=0;
  for(auto t:mp){
    ll x=t.second;
    ans+=x*(x-1)/2;
  }
  cout<<ans<<endl;
}


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

namespace ConsoleApp2
{
    class Program
    {
        static long Gcd(long a, long b)
        {
            if (a < b)
            {
                long temp = a;
                a = b;
                b = temp;
            }

            while (true)
            {
                long remainer = a % b;
                a = b;
                b = remainer;
                if (b == 0)
                {
                    return a;
                }
            }
        }

        static void Main(string[] args)
        {
            Console.ReadLine();
            long[] M = Console.ReadLine().Split().Select(s => long.Parse(s)).ToArray();

            long gcd = M[0];
            foreach (var item in M)
            {
                gcd = Gcd(gcd, item);
            }

            Console.WriteLine(gcd);
        }
    }
}

Measured memory_bytes: 20832
import bisect

n=int(input())
L=[int(i) for i in input().split()]

L.sort()

s=0
for i in range(n-1):
      for j in range(i+1,n):
            index=bisect.bisect_left(L,L[i]+L[j])
            s+=index-(j+1)
print(s)            


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

int n,t,ans;
int a[100005];

int main() {
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>t;
    while (n--) {
        int l,r; cin>>l>>r;
        ++a[l], --a[r];
    }
    for (int i=1;i<=t;i++) a[i]+=a[i-1];
    for (int i=0;i<=t;i++) ans=max(ans,a[i]);
    cout<<ans<<'\n';
}


Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
#define AC ios::sync_with_stdio(0),cin.tie(0);
bool dp[100001];
int main(){
	AC
	int n;
	cin>>n;
	int k;
	cin>>k;
	int a[n];
	for(int i=0;i<n;i++){
		cin>>a[i];
		dp[a[i]]=1;
	}
	dp[0]=0;
	for(int i=1;i<=k;i++){
		for(int j=0;j<n;j++){
			if(i-a[j]<0)dp[i]=0;
			else{
				dp[i]=!dp[i-a[j]];
				if(dp[i])break;
			}
		}
	}
	if(dp[k])cout<<"First"<<endl;
	else cout<<"Second"<<endl;
}


Measured memory_bytes: 3688
s = str(input())
t = str(input())
ls = [[0] for i in range(26)]
lt = [[0] for i in range(26)]
for i in range(len(s)):
    ls[ord(s[i])-97].append(i)
    lt[ord(t[i])-97].append(i)
for i in ls:
    for j in lt:
        if i==j:
            break
    else:
        print("No")
        exit()
print("Yes")

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

int t[100005]={0}, a[100005]={0};
long long int mountain[100005]={0};
bool flags[100005]={0};

int main(){
    int n;
    cin >> n;
    for(int i=0;i<n;++i)cin >> t[i];
    for(int i=0;i<n;++i)cin >> a[i];
    int maxi = 0;
    for(int i=0;i<n;++i){
        if(t[i] > maxi){
            maxi = t[i];
            flags[i] = true;
        }
        mountain[i] = t[i];
    }
    maxi = 0;
    for(int i=n-1;i>=0;--i){
        if(a[i] > maxi){
            if(!flags[i] && mountain[i] >= a[i] || flags[i] && mountain[i] == a[i])flags[i] = true;
            else{
                cout << 0 << endl;
                return 0;
            }
            maxi = a[i];
        }
        mountain[i] = min(mountain[i], (long long)a[i]);
    }

    long long int ans = 1;
    for(int i=0;i<n;++i){
        if(flags[i])continue;
        ans = ans * mountain[i] % 1000000007;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1920
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <sstream>
#include <cassert>
#include <list>
using namespace std;
static const double EPS = 1e-10;
typedef long long ll;
typedef pair<int,int> PI;
typedef vector<int> vi;
#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define F first
#define S second

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

int ck[7][7]={{0,300,500,600,700,1350,1650},
	      {6,0,350,450,600,1150,1500},
	      {13,7,0,250,400,1000,1350},
	      {18,12,5,0,250,850,1300},
	      {23,17,10,5,0,600,1150},
	      {43,37,30,25,20,0,500},
	      {58,52,45,40,35,15,0},
};

main(){
  int eic;
  while(cin>>eic,eic){
    int eh,em,tic,th,tm;
    cin>>eh>>em>>tic>>th>>tm;
    if(eic>tic)swap(eic,tic);

    --eic,--tic;
    int kyori=ck[tic][eic];
    if(((60*eh+em>=17*60+30 && 60*eh+em<=19*60+30) ||
	(60*th+tm>=17*60+30 && 60*th+tm<=19*60+30)) &&
       kyori<=40)cout<<(ck[eic][tic]/2+49)/50*50;
       else cout<<ck[eic][tic];
       cout<<endl;
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pint = pair<int,int>;
ll mod = 1000000007,mod2 = 998244353;

void chmin(long long &a, long long b) { if (a > b) a = b; }
void chmax(long long &a, long long b) { if (a < b) a = b; }
const long long INF = 1LL<<60;
ll gcd(ll a,ll b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}


map<int,int> mp;
int main() {
    int n;
    cin >> n;
    int ans = 0,niko = 0,mx = 0;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        mx = max(mx,a);
        mp[a]++;
    }
    for(int i = 1;i <= mx;i++){
        if(mp[i] %2 == 0 && mp[i] >= 4){
            ans += (mp[i]-2);
            mp[i] = 2;
            niko++;
        }else if(mp[i] == 2) {
            niko++;
        }else if(mp[i] %2 == 1 && mp[i] >= 3){
            ans += (mp[i]-1);
            mp[i] = 1;
        }
    }
    if(niko %2 == 0) ans += niko;
    else ans += (niko+1);
    cout << n-ans << endl;
    return 0;
}

Measured memory_bytes: 4992
import java.util.Scanner;                                                                                                   
public class Main {                                                                                                         
                                                                                                                            
	public static void main(String[] args) {                                                                                
		Scanner scan = new Scanner(System.in);                                                                              
		double r = scan.nextDouble();                                                                                       
		double area = r * r * Math.PI;                                                                                      
		double cf = r * 2 * Math.PI;                                                                                        
		                                                                                                                    
		System.out.print(String.format("%.6f ",area));                                                                      
		System.out.println(String.format("%.6f",cf));                                                                       
	}                                                                                                                       
}                                                                                                                           


Measured memory_bytes: 28200
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
using vl = vector<ll>;
using Map = map<ll,ll>;
using Tup = tuple<ll,ll,ll>;
using vvl = vector<vector<ll>>;
#define all(v) v.begin(), v.end()
#define prt(v) cout<<(v)<<"\n";
#define fl cout<<flush;
#define fi(v) get<0>(v)
#define se(v) get<1>(v)
#define th(v) get<2>(v)
#define endl '\n'
template <typename T> inline bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> inline bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld pi=3.141592653589793238;

signed main(void){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll A;
    cin >> A;
    prt(N-A+1)

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
template<class T> inline bool chmax(T &a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, T b){ if(a>b){ a=b; return 1; } return 0; }

const long long INF=1LL<<60;

int main(){
    int n;
    cin>>n;
    int a[100010][3];
    for(int i=0;i<n;++i){
        for(int j=0;j<3;++j){
            cin>>a[i][j];
        }
    } 
    int dp[100010][3];
    for(int i=0;i<n;++i){
        for(int j=0;j<3;++j){
            dp[i][j]=0;
        }
    }
    for(int i=0;i<n;++i){
        for(int j=0;j<3;++j){
            for(int k=0;k<3;++k){
                if(j==k) continue;
                chmax(dp[i+1][j],dp[i][k]+a[i][j]);
            }
        }
    }

    int ans=0;
    for(int j=0;j<3;++j) chmax(ans,dp[n][j]);
    cout<<ans<<endl;
}

Measured memory_bytes: 2560
H, W, K = map(int, input().split())
S = [list(map(int, input())) for i in range(H)]

ret = W - 1 + H - 1

for i in range(1 << (H - 1)):
    sep = bin(i)[2:].rjust(H - 1, '0')[::-1]

    tile_idx = [0] * H
    cut = 0

    for j in range(H):
        tile_idx[j] = cut

        if j == H - 1:
            break

        if sep[j] == '1':
            cut += 1

    cnt_lst = [0] * (cut + 1)
    num_cnt = 0

    for w in range(W):
        col_new = [0] * (cut + 1)

        flag = False
        flag1 = False
        for h in range(H):
            if S[h][w] == 1:
                idx = tile_idx[h]
                col_new[idx] += 1

        for a in col_new:
            if a > K:
                flag1 = True
                break

        if flag1:
            break

        for k in range(cut + 1):
            if cnt_lst[k] + col_new[k] > K:
                num_cnt += 1
                for l in range(cut + 1):
                    cnt_lst[l] = col_new[l]

                flag = True
                break

        if not flag:
            for k in range(cut + 1):
                cnt_lst[k] += col_new[k]

    if not flag1:
        ret = min(ret, num_cnt + cut)


print(ret)


Measured memory_bytes: 48348
#include<bits/stdc++.h>
#define cs const
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
cs int N = 505;
int n; char S[N][N];
int sm[N][N], dn[N][N]; 
int mn[2][N][N], mx[2][N][N];
int main(){
	#ifdef FSYolanda
	freopen("1.in","r",stdin);
	#endif
	scanf("%d",&n);
	for(int i=1; i<=n; i++) scanf("%s",S[i]+1);
 	int now=0, nxt=1; ll Ans=0;
 	for(int i=n,x; i; i--){
		for(int j=n; j; j--)
	 	if(S[i][j]!='#'){ 
	 		x=S[i][j]-'0';
	 		sm[i][j]=sm[i+1][j]+sm[i][j+1]+x;
	 		dn[i][j]=max(max(dn[i+1][j],dn[i][j+1]),i);
	 		mn[nxt][j][i]=j;
	 		for(int k=i+1; k<=dn[i+1][j]; k++) mn[nxt][j][k]=mn[now][j][k];
	 		for(int k=max(dn[i+1][j],i)+1; k<=dn[i][j+1]; k++) mn[nxt][j][k]=mn[nxt][j+1][k];
	 		mx[nxt][j][i]=j;
	 		for(int k=i; k<=dn[i][j+1]; k++) mx[nxt][j][k]=mx[nxt][j+1][k];
	 		for(int k=max(dn[i][j+1],i)+1; k<=dn[i+1][j]; k++) mx[nxt][j][k]=mx[now][j][k];
	 		int u=i+1, lm=min(dn[i][j+1],dn[i+1][j]);
	 		while(u<=lm){
	 			if(mn[nxt][j+1][u]<=mx[now][j][u]){
	 				sm[i][j]-=sm[u][mn[nxt][j+1][u]];
	 				u=dn[u][mn[nxt][j+1][u]];
	 			} ++u;
	 		} Ans+=(ll)x*(sm[i][j]-x);
		} swap(now,nxt);
	} cout<<Ans; return 0;
}

Measured memory_bytes: 6528
#include<iostream>
#include<stdio.h>
#include<string>
#include<algorithm>
#include<array>
using namespace std;
int main(){
	int A[3];
	for(int i=0;i<3;i++)
	{
		cin>>A[i];
	}
	sort(A,A+3);
	int b=A[2]*2-(A[1]+A[0]);
	if(b%2==0)
	b/=2;
	else
	b=b/2+2;
	cout<<b;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws IOException {
    
    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      int n = Integer.parseInt(br.readLine());
      int[] seq = new int[n];
      for(int i=0; i!=n; i++)
        seq[i] = Integer.parseInt(br.readLine());

      System.out.println( shellSort(seq, n) );

      StringBuilder str = new StringBuilder(n*6);
      for (int i : seq)
        str.append(i).append("\n");

      str.setLength(str.length()-1);
      System.out.println(str);
    }
  }

  public static int shellSort(int a[], int n) {
    int cnt=0;
    int m = 0;
    int[] aG = new int[100];
    for (int g=1,max=n+1; g < max; g=(g*3+1)) {
      aG[m++] = g;
    }
    StringBuilder str = new StringBuilder(m*5);
    str.append(m).append("\n");

    for(int i=(m-1); i!=-1; i--){
      cnt += insertionSort(a, n,aG[i]);
      str.append(aG[i]).append(" ");
    }

    str.setLength(str.length()-1);
    System.out.println(str);

    return cnt;
  }
  
  public static int insertionSort(int a[], final int max, final int g) {
    int cnt=0;

    for (int i=g,j=0,v=0; i < max; i++) {
      for( j=(i-g), v=a[i]; j>=0 && a[j]>v; j-=g ) {
        a[j+g] = a[j];
        cnt++;
      }
      a[j+g] = v;
    }

    return cnt;
  }
}


Measured memory_bytes: 93872
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
const int maxn = 50 + 5;
const int mod = 1e9 + 7;
int a[maxn];
ll dp[maxn][maxn][maxn * maxn];
int main()
{
    ios::sync_with_stdio(false);
    int n , A; cin >> n >> A;
    for (int i = 1 ; i <= n ; i++) cin >> a[i];
    dp[0][0][0] = 1;
    int now = 0;
    for (int i = 1 ; i <= n ; i++){
         now += a[i];
        for (int j = 0; j <= i ; j++){
            for (int k = 0; k <= now ; k++){
                dp[i][j][k] = dp[i - 1][j][k];
                if (j >= 1 && k >= a[i])
                    dp[i][j][k] += dp[i - 1][j - 1][k - a[i]];
            }
        }
    }
    ll ans = 0;
    for (int i = 1 ; i <= n ; i++) ans += dp[n][i][A * i];
    cout << ans << endl;
    return 0;
}


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

using namespace std;

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

    int n, m;
    cin >> n >> m;
    int c[n];
    for (int i = 0; i < m; ++i) {
        cin >> c[i];
    }

    int dp[m + 1][n + 1];
    for (int i = 0; i <= n; ++i) {
            dp[0][i] = i;
    }

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (j < c[i]) {
                dp[i + 1][j] = dp[i][j];
            } else {
                dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - c[i]] + 1);
            }
        }
    }

    cout << dp[m][n] << '\n';

    return 0;
}



Measured memory_bytes: 7224
class Dice
	attr_accessor :t, :b, :n, :e, :s, :w
	def initialize(*labels)
		@t = labels[0]
		@s = labels[1]
		@e = labels[2]
		@w = labels[3]
		@n = labels[4]
		@b = labels[5]
	end
	def roll(dir)
		case dir
		when 'N'
			@t, @s, @b, @n = @s, @b, @n, @t
		when 'S'
			@s, @b, @n, @t = @t, @s, @b, @n
		when 'W'
			@t, @e, @b, @w = @e, @b, @w, @t
		when 'E'
			@e, @b, @w, @t = @t, @e, @b, @w
		end
	end
	def ==(other)
		dice1 = dup
		dice2 = other.dup
		dirs = "EEEENEEEENEEEENEEENEEEENNEEEE"
		found = false
		dirs.chars{|d|
			if dice1.t == dice2.t && dice1.s == dice2.s && dice1.e == dice2.e && dice1.w == dice2.w && dice1.n == dice2.n && dice1.b == dice2.b
				found = true
				break
			else
				dice2.roll d
			end
		}
		found
	end
end

dice1 = Dice.new(*gets.split)
dice2 = Dice.new(*gets.split)
puts dice1 == dice2 ? "Yes" : "No"

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

typedef unsigned long long LL;

int main() {
    LL N, M, dog_p = 1, monkey_p = 1, comb;
    cin >> N >> M;
    if (max(N, M) - min(N, M) > 1) {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 1; i <= N; i++) {
        dog_p *= i;
        dog_p %= 1000000007;
    }
    for (int i = 1; i <= M; i++) {
        monkey_p *= i;
        monkey_p %= 1000000007;
    }
    if (N == M) comb = 2;
    else comb = 1;
    cout << (comb * dog_p * monkey_p) % 1000000007 << endl;
    return 0; 
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <typeinfo>
#include <math.h>

using namespace std;
using ll = long long;

int main() {
	ll n, r;
	cin >> n >> r;
	if (n < 10)
		cout << r + 100 * (10 - n) << endl;
	else
		cout << r << endl;
}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,k,ans=0;cin>>n>>k;
  lvector v(n); rep(i,n) cin>>v[i];
  const ll mn=min(n,k);
  for(ll a=0;a<=mn;++a) {
    for(ll b=0;a+b<=mn;++b) {
      ll ans_=0;
      priority_queue<ll,lvector,greater<ll>> q;
      rep(i,a) {
        ans_+=v[i];
        if(v[i]<0) q.push(v[i]);
      }
      rep(i,b) {
        ans_+=v[n-1-i];
        if(v[n-1-i]<0) q.push(v[n-1-i]);
      }
      ll rm = k-(a+b),cnt=1;
      while(q.size()&&cnt<=rm) {
        ans_-=q.top();
        q.pop();
        cnt++;
      }
      ans=max(ans,ans_);
    }
  }
  print(ans);
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstring>
#include <chrono>
#include <complex>
#define endl "\n"
#define int long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define f first
#define s second

using namespace std;
void lala()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
int powr(int x,int y,int z)
{
	int	ans=1;
	int square=x;
	if(y==0)
	    return 1;
	while(y!=0)
	{
	    if(y%2)
	        ans=ans*square;
	    square=(square*square)%z;
	    y=y/2;
	    if(ans>z)
	        ans=ans%z;
	}
	return ans;
}

int32_t main()
{
std::ios::sync_with_stdio(false);


int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
cin >> a[i];

int res = 0;
int sum = 0;
for (int i = 0; i < n; i++)
sum = (sum + a[i] + mod) % mod;

for (int i = n - 1; i >= 0; i--)
{
sum = (sum - a[i]) % mod;
res = (res + (a[i] * sum) % mod + mod) % mod;

}
cout << (res + mod) % mod << endl;
return 0;
}




Measured memory_bytes: 5124
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Linq.Enumerable;
using static System.Math;

class Program
{
    static void Main()
    {
        var N = int.Parse(ReadLine());
        var (D, X) = ReadLine().Split(' ').Select(int.Parse).ToArray();
        var A = Range(0, N).Select(i => int.Parse(ReadLine())).ToArray();

        var ans = X;
        foreach (var a in A)
        {
            var i = 0;
            int GetD() => i * a + 1;
            while (GetD() <= D)
            {
                ans++;
                i++;
            }
        }

        WriteLine(ans);
    }
}

static class ArrayDeconstructExtensions
{
    public static void Deconstruct<T>(this T[] a, out T i1, out T i2) => (i1, i2) = (a[0], a[1]);
    public static void Deconstruct<T>(this T[] a, out T i1, out T i2, out T i3) => (i1, i2, i3) = (a[0], a[1], a[2]);
    public static void Deconstruct<T>(this T[] a, out T i1, out T i2, out T i3, out T i4) => (i1, i2, i3, i4) = (a[0], a[1], a[2], a[3]);
    public static void Deconstruct<T>(this T[] a, out T i1, out T i2, out T i3, out T i4, out T i5) => (i1, i2, i3, i4, i5) = (a[0], a[1], a[2], a[3], a[4]);
}


Measured memory_bytes: 28332
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define ll long long
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB push_back
#define PF push_front
#define FILL(a,b) memset(a,b,sizeof(a))
#define lwb lower_bound
#define upb upper_bound
using namespace std;
int co[200005],n,sum[2];
V<int> v[200005];
void dfs(int p,int fa,int color){
	co[p]=color;
	sum[co[p]]++;
	int u;
	rep(i,0,v[p].size()){
		u=v[p][i];
		if(u==fa)continue;
		dfs(u,p,color^1);
	}
}
int ans[200005];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	int x,y;
	rep(i,1,n){
		cin>>x>>y;
		v[x].PB(y);
		v[y].PB(x);
	}
	dfs(1,-1,0);
	int l[4];
	l[1]=n/3+(n%3>0);
	l[2]=n/3+(n%3>1);
	l[3]=n/3;
	int t[2]={};
	if(l[1]<=sum[0]&&l[2]<=sum[1]){
		t[0]=1;t[1]=2;
	}else if(l[1]<=sum[1]&&l[2]<=sum[0]){
		t[1]=1;t[0]=2;
	}
	if(t[0]){
		FOR(i,1,n)ans[i]=t[co[i]],l[t[co[i]]]--;
		FOR(i,1,n){
			if(co[i]){
				if(l[t[1]]<0){
					l[t[1]]++;
					ans[i]=3;
				}
			}else{
				if(l[t[0]]<0){
					l[t[0]]++;
					ans[i]=3;
				}
			}
		}
	}else{
		int lc;
		if(l[3]>=sum[0]){
			lc=0;
		}else lc=1;
		FOR(i,1,n){
			if(co[i]==lc)ans[i]=3;
			else if(l[1]){
				l[1]--;ans[i]=1;
			}else if(l[2]){
				l[2]--;ans[i]=2;
			}else ans[i]=3; 
		}
	}
	int st[4]={};
	FOR(i,1,n){
		cout<<st[ans[i]]*3+ans[i]<<' ';
		st[ans[i]]++;
	}
	RE 0;
}




Measured memory_bytes: 15872
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(a,b) for(int a=0;a<b;a++)
#define Sort(a) sort(a.begin(),a.end())
#define rev(a) reverse(a.begin(),a.end())
 int wari(int a,int b) {
   if(a%b==0)
     return a/b;
   else
     return a/b+1;
 }
 int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
 }
 int souwa(int a){
  return a*(a+1)/2;
 }
 int lcm(int a,int b){
  int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return d*e/f;
    }
  int gcm(int a,int b){
      int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return f;
  }
signed main(){
  int a,b,d=0;
  cin>>a>>b;
  vector<int> c(a);
  fo(i,a)
    cin>>c[i];
  fo(i,a-1){
    if(c[i]+c[i+1]>b){
      if(c[i+1]>c[i]+c[i+1]-b){
        d+=c[i]+c[i+1]-b;
        c[i+1]=b-c[i];
      }
      else{
        d+=c[i]+c[i+1]-b;
        c[i]=b;
        c[i+1]=0;
      }
    }
  }
  cout<<d<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 
#define U_MAP unordered_map<ll,ll>

ll n,cnt,ans,a[ohara],b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

//------ 自分を天才だと信じる ------

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

    cin>>n;
    rep(i,n)cin>>a[i];
    sort(a,a+n);
    if(n%2==1){
        if(a[0]!=0){
            Cout(0);
            return 0;
        }
        ll want=2;
        rrep(i,1,n){
            if(a[i]!=want){
                Cout(0);
                return 0;
            }
            i++;
            if(a[i]!=want){
                Cout(0);
                return 0;
            }
            want+=2;
        }
    }
    else{
        ll want=1;
        rep(i,n){
            if(a[i]!=want){
                Cout(0);
                return 0;
            }
            i++;
            if(a[i]!=want){
                Cout(0);
                return 0;
            }
            want+=2;
        }
    }
    n/=2;
    ans=1;
    rep(i,n){
        ans*=2;
        ans%=MOD;
    }
    Cout(ans);
    return 0;
}


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

int main(){
	double a,b;
	while(cin>>a>>b){
		if(a*b==0) break;
		double ans = 1e100;
		for(double i=0;i<=a/2;i+=1.0){
			ans = min(ans, abs(sqrt(i*i+(a-i)*(a-i))-b));
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 3212
def foo(n):
    ret = ""
    cnt = 1
    for i in range(1, len(n)):
        if n[i - 1] == n[i]:
            cnt += 1
            continue
        else:
            ret += str(cnt) + n[i - 1]
            cnt = 1

    ret += str(cnt) + n[-1]

    return ret


while 1:
    n = input()
    if n == 0:
        break
    m = raw_input().strip()
    for i in range(n):
        m = foo(m)
    print m

Measured memory_bytes: 5080
N=int(input())
A=list(map(int,input().split()))

stock=0
money=1000

for i in range(1,N):
    #上がってたら前日の価格との差分を毎日もらう
    if A[i-1] < A[i]:
        money=money+ (A[i]-A[i-1]) * (money//A[i-1]) 
print(money)

Measured memory_bytes: 61636
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<iostream>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x.begin(), _x.end(), std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define R(_x, _y) (0 <= _x && _x <= M - 1 && 0 <= _y && _y <= N - 1)
#define A(a) (!(R(x + dx[a], y + dy[a]) && b[y + dy[a]][x + dx[a]]))
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
int main() {
	int S, W;
	cin >> S >> W;
	puts(W >= S ? "unsafe" : "safe");
	return 0;
}

Measured memory_bytes: 3632