akhauriyash/Code-Regression huggingface dataset:
n = int(input())
p = list(map(int,input().split()))
p2 = p[0]
p1 = p[1]
pm2 = 1 if p1>p2 else -1
count = 0
for i in range(2,n):
  p2 = p[i-2]
  p1 = p[i-1]
  pm2 = (p2-p1)//abs(p2-p1)
  pm1 = (p1-p[i])//abs(p1-p[i])
  if pm1 == pm2:
    count += 1
print(count)

Measured memory_bytes: 3064
#include <cstdio>
#include <algorithm>
#include <vector>

class UnionFind {
  std::vector<int> vertex;
 
public:
  UnionFind(size_t V): vertex(V, -1) {}
 
  bool unite(size_t u, size_t v) {
    if (u >= 0) u = find(u);
    if (v >= 0) v = find(v);
    if (u == v) return false;
    if (vertex[u] > vertex[v]) std::swap(u, v);
 
    vertex[u] += vertex[v];
    vertex[v] = u;
    return true;
  }
 
  int find(size_t v) const {
    while (vertex[v] >= 0)
      v = vertex[v];
 
    return v;
  }
 
  bool connected(size_t u, size_t v) const {
    return find(u) == find(v);
  }

  int rank(size_t u) {
    return -vertex[find(u)];
  }
};

bool is_hashi(const std::vector<int> &a, const std::vector<int> &b,
              int N, size_t m) {

  UnionFind uf(N);

  for (size_t i=0; i<a.size(); ++i) {
    if (i == m) continue;

    uf.unite(a[i], b[i]);
  }

  return uf.rank(0) != N;
}

int main() {
  int N, M;
  scanf("%d %d", &N, &M);

  std::vector<int> a(M), b(M);
  for (int i=0; i<M; ++i) {
    scanf("%d %d", &a[i], &b[i]);
    --a[i];
    --b[i];
  }

  int res=0;
  for (int i=0; i<M; ++i)
    if (is_hashi(a, b, N, i))
      ++res;
  
  printf("%d\n", res);  
  return 0;
}


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

int main() {
	int h, n, a;
	cin >> h >> n;
	int total = 0;
	for (int i = 0; i < n; i++) {
		cin >> a;
		total += a;
	}
	if (total >= h) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
d = {}
ans = 0
for i in range(n):
    if i-a[i] in d:
        ans += d[i-a[i]]
    if i+a[i] in d:
        d[i+a[i]] += 1
    else:
        d[i+a[i]] = 1
print(ans)

Measured memory_bytes: 40648
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long x,k,d;
    cin>>x>>k>>d;
    long long num=abs(x)/d;
    if(x>0)
        if(num<k)
            if((k-num)%2)   ///奇数
                cout<<abs(x-d*(num+1));
            else
                cout<<abs(x-d*num);
        else
            cout<<abs(x-d*k);
    else if(x<0)
        if(num<k)
            if((k-num)%2)
                cout<<abs(x+d*(num+1));
            else
                cout<<abs(x+d*num);
        else
            cout<<abs(x+d*k);
    else
        if(k%2==0)
        cout<<0;
        else
        cout<<d;
    return 0;
}


Measured memory_bytes: 3584
from bisect import bisect_left

def main():
    N = int(input())
    L = list(map(int, input().split()))
    
    L.sort()
    ans = 0
    for i in range(N-2):
        a = L[i]
        for j in range(i+1, N-1):
            k = bisect_left(L, a + L[j])
            ans += (k - (j + 1))

    print(ans)

    
if __name__ == "__main__":
    main()

Measured memory_bytes: 3188
#include <bits/stdc++.h>
const int N=3050,mo=1e9+7;
using namespace std;
inline int gi(){
  char ch=getchar();int x=0,q=0;
  while(ch<'0' || ch>'9') ch=='-'?q=1:0,ch=getchar();
  while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
  return q?(-x):x;
}
int f[N][N][2];
void dp(int &x,int y){
  x+=y; if (x>=mo) x-=mo;
  return;
}
int main(){
  int n=gi(),m=gi();
  for (int i=0; i<=m; ++i)
    f[0][i][i==0]=1;
  for (int i=0; i<m; ++i)
    for (int j=0; j<=n; ++j)
      for (int k=0; k<=1; ++k)
      if (f[i][j][k]){
	if (j) dp(f[i+1][j-1][k|(j==1)],f[i][j][k]);
	if (j) dp(f[i+1][j][k|(j==1)],f[i][j][k]);
	if (j<n) dp(f[i+1][j+1][k],f[i][j][k]);
	if (j<n) dp(f[i+1][j][k],f[i][j][k]);
      }
  int ans=0;
  for (int i=0; i<=n; ++i)
    dp(ans,f[m][i][1]);
  cout<<ans;
  return 0;
}


Measured memory_bytes: 71936
import sys
import collections
import math
import fractions

def lcm(a,b):
	return a*b/fractions.gcd(int(a),int(b))

def main():
	count = int(input())
	i = 0
	tmp = 1
	while(i < count):
		i += 1
		num = int(input())
		tmp = lcm(tmp,num)
	print(int(tmp))
if __name__ == '__main__':
	main()

Measured memory_bytes: 4776
from collections import deque

n, q = list(map(int, input().split()))
que = deque([])
for _ in range(n):
    name, time = input().split()
    que.append([name, int(time)])
    
elapsed_time = 0
while que:
    name, time = que.popleft()
    dt = min(q, time)
    time -= dt
    elapsed_time += dt
    if time > 0:
        que.append([name, time])
    else:
        print (name, elapsed_time)

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

using namespace std;

int main() {
 int n,a,b,count=0;
 bool flag = false;
 int index = 0;
  cin>>n;
 vector<int> v(n,0);

 while(n--)
 {
     cin>>a>>b;
     if(a == b)
     {
       v[index] = 1;
        
     }
     index++; 
 }

//  for(auto i : v)
//     cout<<i<<' ';

// cout<<endl;
 
 for(int i=0;i<(int)v.size();i++)
 {
     
  // cout<<"value of i is "<<i<<endl;
    count=0;
     for(int j=i;j<(int )v.size();j++)
     {
        
         if(v[j] == 1)
         {  
             count++;
           // cout<<"count val is : " <<count<<endl;
             if(count >=3)
             {
                 flag=true;
                 break;
             }
         }
         else
            break;
     }
 }
 

 
 //cout<<'f'<<flag<<endl;
 
 if(flag == true)
    puts("Yes");
else
    puts("No");
 
 return 0;
}

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

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int MOD=1e9+7;
ll INF=1e18;

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

int par[100010];
int ranks[100010];

void init(int n){
    for(int i=0; i<n; i++){
        par[i]=i;
        ranks[i]=0;
    }
}

int find(int x){
    if(par[x] == x){
        return x;
    }
    else{
        return par[x]=find(par[x]);
    }
}

bool same(int x, int y){
    return find(x) == find(y);
}

void unite(int x, int y){
    x=find(x);
    y=find(y);
    if(x == y) return;

    if(ranks[x] < ranks[y]){
        par[x]=y;
    }
    else{
        par[y]=x;
    }
    
    if(ranks[x] == ranks[y]){
        ranks[x]++;
    }
}

int kruskal(int n, vector<T>& edge){
    sort(edge.begin(), edge.end());
    init(n);
    int res=0;
    for(int i=0; i<2*n-2; i++){
        int cost, cv, nv;
        tie(cost, cv, nv)=edge[i];
        if(!same(cv, nv)){
            unite(cv, nv);
            res+=cost;
        }
    }
    return res;
}

int main(){
    int n; cin>>n;
    vector<P> xsort(n), ysort(n);
    vector<T> edge(2*n-2);
    for(int i=0; i<n; i++){
        int x, y; cin>>x>>y;
        xsort[i]=P(x, i);
        ysort[i]=P(y, i);
    }

    sort(xsort.begin(), xsort.end());
    sort(ysort.begin(), ysort.end());

    for(int i=0; i<n-1; i++){
        int cx, cv, nx, nv;
        tie(cx, cv)=xsort[i];
        tie(nx, nv)=xsort[i+1];
        int cost=abs(nx-cx);
        edge[i]=T(cost, cv, nv);
    }
    for(int i=0; i<n-1; i++){
        int cy, cv, ny, nv;
        tie(cy, cv)=ysort[i];
        tie(ny, nv)=ysort[i+1];
        int cost=abs(ny-cy);
        edge[i+n-1]=T(cost, cv, nv);
    }

    cout << kruskal(n, edge) << endl;
}

Measured memory_bytes: 4992
extension String: CollectionType{}
let a : Int = Int(readLine()!)!
let x: [Int] = readLine()!.split(" ").map { Int($0)! }
let sum = x.reduce(0,combine: +)
switch sum%2 {
case 1:
    print("NO")
case 0:
    print("YES")
default:
    break
}

Measured memory_bytes: 7740
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
namespace Fast_Read {
	inline void read(int &res) {
		res = 0;int tmp = 1;
		char ch = getchar();
		while (ch < '0' || ch > '9') {if (ch == '-')tmp = -1;ch = getchar();}
		while (ch >= '0' && ch <= '9')res = (res<<1)+(res<<3)+(ch^48),ch = getchar();
		res *= tmp;
	}
	inline void read(long long &res) {
		res = 0;long long tmp = 1;
		char ch = getchar();
		while (ch < '0' || ch > '9') {if (ch == '-')tmp = -1;ch = getchar();}
		while (ch >= '0' && ch <= '9')res = (res<<1)+(res<<3)+(ch^48),ch = getchar();
		res *= tmp;
	}
}
using namespace Fast_Read;
#define ll long long
ll H;
inline ll f(ll x) {
	if (x == 1)return 1;
	return (f(x>>1)<<1)+1;
}
int main() {
	read(H);
	cout<<f(H)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define N_MAX 100

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

int main()
{
  static int score[N_MAX];
  int n, i, sum;
  for (;;) {
    scanf("%d", &n);
    if (n == 0) break;
    for (i = 0; i < n; i++) {
      scanf("%d", &score[i]);
    }
    qsort(score, n, sizeof(int), cmpint);
    sum = 0;
    for (i = 1; i <= n - 2; i++) {
      sum += score[i];
    }
    printf("%d\n", sum / (n - 2));
  }
  return 0;
}

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

#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (a); i >= (int)(b); i--)
#define all(x) (x).begin(), (x).end()
using i32 = int32_t;
using i64 = int64_t;
using f32 = float;
using f64 = double;
using P   = pair<int, int>;

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

template <class T>
void dump_vec(const vector<T> &v) {
    auto len = v.size();
    rep(i, 0, len) {
        cout << v[i] << (i == (int)len - 1 ? "\n" : " ");
    }
}

struct Setup {
    Setup() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} SETUP;

//---------------------------------------------------------------------------------------------------

//---------------------------------------------------------------------------------------------------

bool dp[1 << 21];

void init(vector<int> as) {
    const int len = as.size();
    rep(bit, 0, 1 << len) {
        int sum = 0;
        rep(i, 0, len) {
            if (bit & (1 << i)) sum += as[i];
        }
        dp[sum] = true;
    }
}

signed main() {
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];
    init(A);
    int Q;
    cin >> Q;
    rep(i, 0, Q) {
        int m;
        cin >> m;
        cout << (dp[m] ? "yes" : "no") << "\n";
    }
}



Measured memory_bytes: 3136
n = int(input())
t,a = map(int,input().split())
temp = list(map(int,input().split()))
tmp = 10**9
index= 1

for i in temp:
  if abs(a- (tmp)) > abs(a- (t - i * 0.006)):
    tmp = t - i * 0.006
    index = temp.index(i)+1


print(index)


Measured memory_bytes: 3060
package main
import "fmt"
func main() {
  var n,t,t0,t1 int
  var sum int64
  fmt.Scan(&n,&t)
  fmt.Scan(&t0)
  sum = int64(t)
  for i:=1;i<n;i++ {
    fmt.Scan(&t1)
    if t1-t0 < t {
      sum += int64(t1-t0)
    } else {
      sum += int64(t)
    }
    t0 = t1
  }
  fmt.Println(sum)
}

Measured memory_bytes: 5504
#include<iostream>
#include<cmath>
#include<string>
#include<map>
#include<queue>
using namespace std;
#define N 3
#define N2 9

 struct Puzzle {
  int f[N2];
  int space;
  string path;

  bool operator < (const Puzzle &p) const {
    for(int i=0;i<N2;i++) {
      if(f[i]==p.f[i])continue;
      return f[i] > p.f[i];
    }
    return false;
  }
};

static const char dir[4] = {'u','l','d','r'};
static const int dx[4] = {-1,0,1,0};
static const int dy[4] = {0,-1,0,1};

bool isTarget(Puzzle p) {
  for(int i=0;i<N2;i++)
  if(p.f[i] != (i+1)) return false;
  return true;
}

string bfs(Puzzle s ) {
queue<Puzzle> Q;
map<Puzzle,bool> V;
Puzzle u,v;
s.path = "";
Q.push(s);
V[s] = true;

while(!Q.empty()) {
  u = Q.front();Q.pop();
  if(isTarget(u)) return u.path;
  int sx = u.space / N;
  int sy = u.space % N;
  for(int r = 0;r<4 ; r++) {
    int tx = sx + dx[r];
    int ty = sy + dy[r];
    if(tx < 0 || ty < 0|| tx>=N || ty >= N) continue;
    v = u;
    swap(v.f[u.space], v.f[tx *N+ty]);
    v.space = tx * N + ty;
    if(!V[v]) {
      V[v] = true;
      v.path  += dir[r];
      Q.push(v);
    }
  }
}
return "unsolvable";
}

int main() {
  Puzzle in;

  for(int i=0;i<N2;i++) {
    cin >> in.f[i];
    if(in.f[i]==0) {
      in.f[i]=N2;
      in.space = i;
    }
  }

  string ans = bfs(in);
  cout << ans.size()<<endl;

  return 0;
}

Measured memory_bytes: 30672
#include <iostream>
using namespace std;
int main(){
  int N,a=0,b=0,c=0,ans=0;
  cin>>N;
  int A[N];
  for(int i=0;i<N;i++){
    cin>>A[i];
    if(A[i]%4==0) a++;
    else if(A[i]%4==2) b++;
    else c++;
  }
  if(b>0){
    if(a>=c) ans=1;
  }else if(a-c+1>=0) ans=1;
  cout<<(ans?"Yes":"No")<<endl;
}

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

const int mxN = 1e5 + 5, mxM = 105;
int dp[mxN], a[mxN];

int main() {
	int n;
	scanf("%d", &n);
	int k;
	scanf("%d", &k);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	for(int i = k; i >= 0; --i) {
		bool can = false;
		for(int j = 1; j <= n; ++j) {
			if(a[j] + i <= k)
				can |= dp[i + a[j]] == false;
		}
		dp[i] = can;
	}
	if(dp[0])
		puts("First");
	else
		puts("Second");
}


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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repp(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perr(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)

typedef long long LL;
typedef long double LD;

int main(){
  while(1){
    int t,p,r;
    cin >> t >> p >> r;
    if(t==0) return 0;
    vector<int> ac(t,0);
    vector<int> pn(t,0);
    vector<vector<int>> wa(t,vector<int>(p,0));
    int tid,pid,time;
    string ms;
    rep(i,r){
      cin >> tid >> pid >> time >> ms;
      tid--,pid--;
      if(wa[tid][pid]==-1) continue;
      if(ms=="CORRECT"){
        ac[tid]++;
        pn[tid]+=time+wa[tid][pid]*1200;
        wa[tid][pid]=-1;
      }else{
        wa[tid][pid]++;
      }
    }
    vector<int> jun(t,0);
    iota(all(jun),0);
    sort(all(jun),[&](const int &l, const int &r){
      return ac[l]==ac[r]?(pn[l]==pn[r]?l<r:pn[l]<pn[r]):ac[l]>ac[r];
    });
    rep(i,t){
      cout << jun[i]+1 SP ac[jun[i]] SP pn[jun[i]] << endl;
    }
  }
  return 0;
}



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

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

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;

int main(){
    long long a,b,v,w,t;
    cin >> a >> v >> b >> w >> t;
    
    if(t*abs(v-w) >= abs(a-b) && v >= w){
        cout << "YES" << endl;
    } else {
      cout << "NO" << endl;
    }

    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define int long long

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef pair<ll,pll> plpll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const int INF = 1<<30;
const ll mod = 1000000000 + 7;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

#define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod

int n, k;
int a[100000 + 5], b[100000 + 5];

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> k;
    rep(i, n) {
        cin >> a[i] >> b[i];
    }
    int ans = 0;
    int mask = (1 << 31) - 1LL;
    rep(i, 33) {
        if (!((k>>i) & 1) && i != 0) continue;
        int tmp = k;
        if (i == 0) {
            tmp = k;
        }
        else {
            tmp ^= (1<<i); tmp |= (1<<i) - 1LL; tmp &= mask;
        }
        int v = 0;
        rep(l, n) {
            if (a[l] > tmp) continue;
            bool ok = true;
            rep(j, 33) {
                if ((a[l]>>j) & 1) {
                    if (!((tmp>>j) & 1)) {
                        //cout << j << endl;
                        ok = false;
                        break;
                    }
                }
            }
            if (ok) {
                v += b[l];
            }
        }
        ans = max(ans, v);
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long ,long long>pll;

ll gcd(ll a, ll b) {return (!b ? a : gcd(b, a % b));}
ll lcm(ll a, ll b) {return ((a*b)/gcd(a,b));}
bool cmp(int a,int b){return a>b;}

const ll mod = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;
const ld pi = 3.141592653589793;

unsigned long long modpow(unsigned long long n, unsigned long long k, unsigned long long mod)
{
if (k == 0) return 1;
long long r = modpow(n * n % mod, k >> 1, mod);
if (k & 1) r = r * n % mod;
return r;
}

void solve(){
     int n,k;cin >> n >> k;
     vector<int>a(n);
     vector<int>dp(k+1,0);
     for(int i = 0;i<n;i++) cin >> a[i];
     for(int j = 0;j<=k;j++){
        for(int i = 0;i<n;i++){
            if(j>=a[i]&&dp[j-a[i]]==0)
                dp[j] = 1;
        }
     }
     if(dp[k]==1) cout << "First";
     else cout <<"Second";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    solve();
    return 0;
}

Measured memory_bytes: 3732
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
#define mod 1000000007
#define all(x) (x).begin(),(x).end()
 
#define REP(i, n) for(int i = 0; i < (n); i++)
#define NREP(i, n) for(int i = 1; i <= (n); i++)
#define SREP(i, s) for(int i = 0; i < (s.size()); i++)
#define SORT(v, n) sort(v, v+n);
#define GSORT(v, n) sort(v, v+n, greater<int>());
#define VSORT(v) sort(v.begin(),v.end());
#define VGSORT(v) sort(v.begin(),v.end(),greater<int>());
#define REV(a) reverse(begin(a),end(a));

int nums(int n){
	return to_string(n).length();
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cout << fixed << setprecision(7);
////////////////////////////////////////////
	int n;
	cin >> n;
	double x[n];
	double count=0;
	REP(i,n){
		cin >> x[i];
		count+=x[i];
	}
	count/=(double)n;
	if(count-int(count)>0.49999999999) count+=1;

	int ans=0;
	REP(i,n){
		ans+=pow(int(count)-int(x[i]),2);
		
	}
	
	cout << ans << endl;
	
///////////////////////////////////////////
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair<double,double> P;

int main(){

	double x,y;
	vector<P> v;
	while(~scanf("%lf,%lf",&x,&y)){
		v.push_back(P(x,y));
	}
	
	double cx = (v[0].first + v[1].first + v[2].first) / 3.0;
	double cy = (v[0].second + v[1].second + v[2].second) / 3.0;
	
	double S=0;
	for(int i=0;i<v.size();i++){
		int idx1 = i;
		int idx2 = (i+1) % v.size();
		double a = sqrt(pow(v[idx1].first - v[idx2].first,2.0) + pow(v[idx1].second - v[idx2].second,2.0));
		double b = sqrt(pow(v[idx1].first - cx,2.0) + pow(v[idx1].second - cy,2.0));
		double c = sqrt(pow(v[idx2].first - cx,2.0) + pow(v[idx2].second - cy,2.0));

		double z = (a+b+c)/2.0;
		double tmp_s = sqrt(z*(z-a)*(z-b)*(z-c));
		S+=tmp_s;
	}

	printf("%.7f\n",S);

}

Measured memory_bytes: 0
/*
 * author :Sadik Hassan
 *
*/
#include "bits/stdc++.h"
using namespace std;
#define ll            long long
#define nl            "\n"
#define PB            push_back
#define fi            first
#define se            second
#define _SAD()        ios::sync_with_stdio(0),cin.tie(0), cout.tie(0);
#define rep(i,n)      for(int i=0;i<n;i++)
#define repn(i,n)     for(int i=1;i<=n;i++)
#define rrep(i,n)     for(int i=n-1;i>=0;i--)
#define SZ(s)         s.size()
#define SRT(x,y)      sort(x,x+y)
#define REV(a,b)      reverse(a,a+b)
#define VSRT(x)       sort(x.begin(),x.end())
#define VREV(x)       reverse(x.begin(),x.end())
#define TSFL(s)       transform(s.begin(),s.end(),s.begin(),::toupper);
#define TSFH(s)       transform(s.begin(),s.end(),s.begin(),::tolower);
/*---------------------------------------------------------------------*/
const int N = 2e5+10;
const int INF = (int)1e9+5;

int main()
{
    _SAD()
    string s;
    cin>>s;
    bool a=0,b=0;
    rep(i,3)
    {
        if(s[i]=='A')
        {
            a=1;
        }
        else{
            b=1;
        }
    }
    if(!a||!b)
    {
        cout<<"No"<<nl;
    }
    else
    {
        cout<<"Yes"<<nl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(void)
{
	char s[10];
	int N;
	int ans=0;
	int put;
	scanf("%s",s);
	N=strlen(s);
	
	if(s[0]!='A')
	{
		puts("WA");return 0;
	}
	
	for(int i=2;i<N-1;i++)
	{
		if(s[i]=='C')
		{
			put=i;
			ans++;
		}
	}
	if(ans!=1)
	{
		puts("WA");
		return 0;
	}
	for(int i=1;i<N;i++)
	{
		if(i==put)continue;
		if(s[i]<s[0]+26)
		{
			puts("WA");
			return 0;
		}
	}
	puts("AC");
	return 0;
}


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

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

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;

int main()
{
	int A, B;
	cin >> A >> B;

	if (A % 3 == 0 || B % 3 == 0 || (A + B) % 3 == 0)
	{
		cout << "Possible" << endl;
	}
	else
	{
		cout << "Impossible" << endl;
	}

	return 0;
}

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

int main(void){
  int a[3];
  cin >> a[0] >> a[1] >> a[2];
  sort(a, a + 3);
  if(a[0] == a[1] && a[1] == 5 && a[2] == 7) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}


Measured memory_bytes: 256
def dfs(i, V, E):
    S = [i]
    while(len(S) > 0):
        vi = S.pop()
        d = V[vi]
        for j, value in E[vi].items():
            if V[j] > value + d:
                V[j] = value + d
                S.append(j)
    return V

INF = 10 ** 14
n = int(input())
V = [INF for _ in range(n + 1)]
E = [{} for _ in range(n + 1)]
for i in range(n - 1):
    ai, bi, ci = map(int, input().split())
    E[ai][bi] = ci
    E[bi][ai] = ci

q, k = map(int, input().split())
z = [list(map(int, input().split())) for _ in range(q)]
V[k] = 0

V = dfs(k, V, E)
for i in range(q):
    x, y = z[i]
    print(V[x] + V[y])


Measured memory_bytes: 76308
N,M = list(map(int,input().split()))
"""
N=1 0~9
N=2 10~99
N=3 100~999
N   10**(N-1)~10**N-1
"""
S = []
C = []
for i in range(M):
    s,c = list(map(int,input().split()))
    S.append(s)
    C.append(c)

# print(S)
# print(C)

y = 10**N

if N == 1:
    L,R = 0,10
elif N == 2:
    L,R = 10,100
elif N == 3:
    L,R = 100,1000
    
for i in range(L,R):
    f = True
    # print(i)
    for j in range(M):
        if str(i)[S[j]-1] != str(C[j]):
            f = False
            # print("False")
            break
    if f:
        y = min(y,i)
        
if y == 10**N:
    y = -1

print(y)

Measured memory_bytes: 3064
#include <cstdio>
#include <cstring>
#include <bitset>
#include <vector>
using namespace std;

const int MAX_W = 10;
const int MAX = MAX_W * MAX_W;

typedef bitset<MAX> bit;

bit mask;
int W, H;
int board[MAX_W][MAX_W];
int accum[MAX_W + 1][MAX_W + 1];
int best;

bool included(const bit& a, const bit& b){
	return (a&b) == a;
}

bool init(){
	scanf("%d%d", &W, &H);
	for(int i=0; i<H; ++i){
		for(int j=0; j<W; ++j){
			scanf("%d", board[i]+j);
		}
	}
	return H > 0;
}

void dfs(int score, bit brd, vector<bit> bs){
	for(int i=0; i<H*W; ++i)if(!brd[i]){
		int cnt = 0, key = -1;
		for(int j=0; j<(int)bs.size(); ++j){
			if(bs[j][i]){
				++cnt;
				key = j;
			}
		}
		if(cnt == 1){
			++score;
			brd |= bs[key];
		}
	}

	if(brd == mask){
		best = min(best, score);
		return ;
	}

	if(score >= best - 1){
		return ;
	}

	for(int i=0; i<(int)bs.size(); ++i){
		bs[i] &= mask & (~brd);
	}

	vector<bit> ts;
	for(int i=0; i<(int)bs.size(); ++i)if(bs[i].any()){
		for(int j=i+1; j<(int)bs.size(); ++j){
			if(bs[i]==bs[j]){
				bs[j].reset();
			}
		}
	}

	for(int i=0; i<(int)bs.size(); ++i){
		bool ok = true;
		for(int j=0; j<(int)bs.size(); ++j)if(i!=j){
			if(included(bs[i], bs[j])){
				ok = false;
				break;
			}
		}
		if(ok){
			ts.push_back(bs[i]);
		}
	}

	for(int i=0; i<(int)ts.size(); ++i){
		bit t = ts[i];
		ts[i].reset();
		dfs(score+1, brd | t, ts);
		ts[i] = t;
	}
}

int solve(){
	mask.reset();
	for(int i=0; i<W*H; ++i){
		mask.set(i, true);
	}
	for(int i=0; i<H; ++i){
		for(int j=0; j<W; ++j){
			accum[i+1][j+1] = accum[i+1][j] + accum[i][j+1] - accum[i][j] + (1 - board[i][j]);
		}
	}

	bit brd;
	vector<bit> bs;
	for(int i=0; i<H; ++i){
		for(int j=0; j<W; ++j){
			if(board[i][j] == 0){
				brd.set(i*W+j);
			}
			else{
				int sz = 0;
				for(int k=1; i+k<=H && j+k<=W; ++k){
					if(accum[i+k][j+k] - (accum[i+k][j] + accum[i][j+k]) + accum[i][j] == 0){
						sz = k;
					}
				}
				bit bt;
				for(int a=0; a<sz; ++a){
					for(int b=0; b<sz; ++b){
						bt.set((i+a)*W+(j+b), true);
					}
				}
				bs.push_back(bt);
			}
		}
	}

	vector<bit> ts;
	for(int i=0; i<(int)bs.size(); ++i){
		bool ok = true;
		for(int j=0; j<(int)bs.size(); ++j)if(i!=j){
			ok &= !included(bs[i], bs[j]);
		}
		if(ok){
			ts.push_back(bs[i]);
		}
	}

	best = MAX;
	dfs(0, brd, ts);

	return best;
}

int main(){
	for(;init();){
		printf("%d\n", solve());
	}

	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	vector <long long> v;
	long long move=0;
	long long s;
	for (int i=0;i<n;i++) {
		cin>>s;
		v.push_back(s);
	}
	sort(v.begin(),v.end());
	for (int i=0;i<n-m;i++)
		move+=v[i];
	cout<<move<<endl;
	return 0;
}

Measured memory_bytes: 2420
#include<stdio.h>
int main(void)
{
	int n,y,b,r,t,c,j,i,max1;
	double max,a,a1,rr;
	while(1){
		max=0;
		scanf("%d",&n);
		if(n==0){
			break;
		}
		scanf("%d",&y);
		for(i=0;i<n;i++){
			scanf("%d %d %d",&b,&r,&t);
			rr=(double)r/100;
			if(t==2){
				a=1+rr;
				a1=a;
				for(j=2;j<=y;j++){
					a=a1*a;
				}
			}
			if(t==1){
				a=(double)1+y*rr;
			}
			if(a>max){
				max=a;
				max1=b;
			}
		}
		printf("%d\n",max1);
	}
	return 0;
}


Measured memory_bytes: 2032
from collections import Counter
N = int(input())
As = list(map(int, input().split()))

ct = Counter(As)
L = 10**6+1
flags = [True] * L
ans = 0
for k in sorted(ct.keys()):
    c = ct[k]
    if not flags[k]:
        continue
    flags[2*k::k] = [False] * ((L-k-1) // k)
    if ct[k] == 1:
        ans += 1
print(ans)


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

int main() {
  string S;
  cin >> S;
  if(S.at(0)==S.at(1)||S.at(1)==S.at(2)||S.at(2)==S.at(0)){
    cout << "No" << endl;
  }
  else{
    cout << "Yes" <<endl;
  }
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int i,j,n,divis,ans=0;
    cin>>n;
    for(i=1; i<=n; i++){
        divis=0;
        for(j=1; j<=i; j++){
            if(i%j==0)    divis++;
        }
        if(i%2==1 && divis==8){
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
CD = [list(map(int,input().split())) for _ in range(M)]

for i in range(N):
  ans = 10**18
  for j in range(M-1,-1,-1):
    abs_num = abs(AB[i][0]-CD[j][0])+abs(AB[i][1]-CD[j][1])
    ans = min(ans, abs_num)
    if ans == abs_num:
      count = j+1
  print(count)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <unordered_map>

const int MOD = pow(10,9)+7;
typedef long long ll;

using namespace std;
int in(){
    int temp;
    scanf("%d",&temp);
    return temp;
}

ll lin(){
    ll temp;
    scanf("%lld",&temp);
    return temp;
}


int main() {

    int N  = in();
    
    string S[N+1];
    
    for(auto i = 0; i<N; i++){
        cin >> S[i];
        sort(S[i].begin(), S[i].end());
    }
    
    string out;
    
    char maxim = '!';
    
    while(1){
        
        for(auto i = 0; i<N; i++){
            if (S[i].size()==0){
                cout << out << endl;
                return 0;
            }
        }
        
        for(auto j = 0; j <N; j++){  ///頭揃えする。
            while(S[j].front() < maxim){  //// 辞書順最大のものに揃うまで先頭から消していく。
                
                S[j].erase(S[j].begin());
                
                if(S[j].size() == 0){   ///どれかが空になったら終了。
                    cout << out << endl;
                    return 0;
                }
            }
            
            /// この段階で、Sはbcccのような形。bを削除したい。
            /// cが現れた時点で最大値をそれに更新する。
            
            if (S[j].front() > maxim){
                maxim = S[j].front();
            }
        }
        
        int count = 0;
        for(auto i = 0; i <N; i++){
            count += (maxim == S[i].front());
        }
        
        if (count == N){
            for(auto i = 0; i <N; i++){
                
                if (S[i].size() == 0){
                    cout << out << endl;
                    return 0;
                }
                S[i].erase(S[i].begin());
            }
            out.push_back(maxim);
        }
        
    }
    

    
    return 0;
    
}




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

using namespace std;

int main() {
  ios::sync_with_stdio(false); cin.tie(NULL);
  int n;
  cin >> n;
  vector<int> p(n), q(n);
  for (int i = 0; i < n; i++) {
    cin >> p[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> q[i];
  }
  vector<int> a = p;
  sort(a.begin(), a.end());
  int i = -1, j = -1, idx = 0;
  do {
    if (p == a) {
      i = idx;
    }
    if (q == a) {
      j = idx;
    }
    ++idx;
  } while (next_permutation(a.begin(), a.end()));
  cout << abs(i - j) << endl;
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int N;

void input(){
  cin>>N;
}

int main(){
  input();
  vector<int >a(N);
  //int *a;
  //a=new int[N];
  /*int sum=0;
  double K;
  for(int i=0;i<N;i++){
    cin>>a[i];
    sum+=a[i];
  }
  K=sum/N;
  int cn=0,cn_2=0,ans=0;
  for(int i=0;i<N;i++){

    if(K<=a[i])cn++;
    else cn_2++;

    if(cn==cn_2)ans++;
  }

  cout<<ans<<endl;

  */


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

    cin>>a[i];
  }

  sort(a.begin(),a.end());
  int ans;
  ans=a[N/2]-a[N/2-1];
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}// break continue pop_back 998244353
#define int ll
#define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sz(a)((int)(a).size())
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);iostream::sync_with_stdio(0);cout<<fixed<<setprecision(10);cerr<<fixed<<setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N=202020,OO=1e18;
vector<pii> g[N];
vector<pii> onx[N],ony[N];
int valval[N];
int val[N];
int u[N];
int minrowvgruppe[N],mincolvgruppe[N];
int cur=0;
void no(){
	cout<<"No\n";
	exit(0);
}
int h,w,n;
void dfs(int v,int sum){
	u[v]=cur;
	val[v]=sum;
	if(v<=h)upn(minrowvgruppe[cur],sum);
	else upn(mincolvgruppe[cur],sum);
	for(pii p:g[v]){
		int to=p.f,len=p.s;
		if(!u[to]){
			dfs(to,sum+len);
		}
		if(val[to]!=sum+len)no();
	}
}
int32_t main(){
	cin>>h>>w>>n;
	int fx,fy,a;
	cin>>fx>>fy>>a;
	onx[fx].pb(fy,a);
	ony[fy].pb(fx,a);
	g[fx].pb(fy+h,0);
	g[fy+h].pb(fx,0);
	forn(i,n-1){
		int x,y,c;
		cin>>x>>y>>c;
		onx[x].pb(y,c);
		ony[y].pb(x,c);
	}
	for(int i=1;i<=h+w;++i)minrowvgruppe[i]=mincolvgruppe[i]=OO;
	for(int i=1;i<=h;++i){
		sort(onx[i].begin(),onx[i].end());
		for(int j=1;j<sz(onx[i]);++j){
			int pvar=onx[i][j-1].f+h;
			int cvar=onx[i][j].f+h;
			int del=onx[i][j].s-onx[i][j-1].s;
			g[pvar].pb(cvar,del);
			g[cvar].pb(pvar,-del);
		}
	}
	for(int i=1;i<=w;++i){
		sort(ony[i].begin(),ony[i].end());
		for(int j=1;j<sz(ony[i]);++j){
			int pvar=ony[i][j-1].f;
			int cvar=ony[i][j].f;
			int del=ony[i][j].s-ony[i][j-1].s;
			g[pvar].pb(cvar,del);
			g[cvar].pb(pvar,-del);
		}
	}
	cur=1;
	dfs(fx,a);
	for(int i=1;i<=h+w;++i){
		if(!u[i]){
			cur++;
			dfs(i,0);
		}
	}
	if(minrowvgruppe[fx]+mincolvgruppe[fx]-a<0)no();
	for(int i=1;i<=h+w;++i)dbg(i,u[i],val[i]);
	for(int i=1;i<=h;++i){
		if(!onx[i].empty()){
			int x=minrowvgruppe[u[i]];
			int last=onx[i].back().f+h;
			int value=onx[i].back().s;
			int y=mincolvgruppe[u[last]];
			int minvalue=value-(val[i]-x)-(val[last]-y);
			if(minvalue<0){
			dbg(x,last,value,y);
				dbg(minvalue);
				no();
			}
		}
	}
	cout<<"Yes\n";
	return 0;
}


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

long long int dp[200010][5],i,j,n,a[200010],ans;

signed main()
{
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	for (i=1;i<n+1;i++) cin>>a[i];
	if (n==2)
	{
		cout<<max(a[1],a[2]);return 0;
	}
	if (n==3)
	{
		cout<<max(max(a[1],a[2]),a[3]);return 0;
	}
	if (n%2==0)
	{
		ans=0;
		for (i=1;i<n/2+1;i++) ans=ans+a[2*i];
		dp[1][1]=a[1];dp[1][0]=-1e16;
		dp[2][1]=-1e16;dp[2][0]=-1e16;
		for (i=3;i<n+1;i++) for (j=0;j<2;j++)
		{
			dp[i][j]=dp[i-2][j];
			if (j<1 && i>3) if (dp[i-3][j+1]!=-1e16) dp[i][j]=max(dp[i][j],dp[i-3][j+1]);
			if (dp[i][j]!=-1) dp[i][j]=dp[i][j]+a[i];
		}
		
		if (dp[n][0]!=-1e16) ans=max(ans,dp[n][0]);
		if (n>3)
		{
			if (dp[n-1][1]!=-1e16) ans=max(ans,dp[n-1][1]);
		}
		cout<<ans;
		return 0;
	}
	for (i=3;i<n+1;i=i+2) ans=ans+a[i];
	
	
	dp[2][1]=a[2];dp[2][0]=-1e16;
	dp[3][1]=-1e16;dp[3][0]=-1e16;
	for (i=4;i<n+1;i++) for (j=0;j<2;j++)
	{
		dp[i][j]=dp[i-2][j];
		if (j<1) if (dp[i-3][j+1]!=-1e16) dp[i][j]=max(dp[i][j],dp[i-3][j+1]);
		if (dp[i][j]!=-1e16) dp[i][j]=dp[i][j]+a[i];
	}
	
	if (dp[n][0]!=-1e16) ans=max(ans,dp[n][0]);
	if (n>3)
	{
		if (dp[n-1][1]!=-1e16) ans=max(ans,dp[n-1][1]);
	}


	dp[1][2]=a[1];dp[1][1]=-1e16;dp[1][0]=-1e16;
	dp[2][2]=-1e16;dp[2][1]=-1e16;dp[2][0]=-1e16;
	for (i=3;i<n+1;i++) for (j=0;j<3;j++)
	{
		dp[i][j]=dp[i-2][j];
		if (j<2 && i-3>0) if (dp[i-3][j+1]!=-1e16) dp[i][j]=max(dp[i][j],dp[i-3][j+1]);
		if (j<1 && i-4>0) if (dp[i-4][j+2]!=-1e16) dp[i][j]=max(dp[i][j],dp[i-4][j+2]);
		if (dp[i][j]!=-1e16) dp[i][j]=dp[i][j]+a[i];
	}
	
	
	if (dp[n][0]!=-1e16) ans=max(ans,dp[n][0]);
	if (n>3)
	{
		if (dp[n-1][1]!=-1e16) ans=max(ans,dp[n-1][1]);
	}
	if (n>4)
	{
		if (dp[n-2][2]!=-1e16) ans=max(ans,dp[n-2][2]);
	}
	cout<<ans;
}


Measured memory_bytes: 12992
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <bitset>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){freopen("concatenation.in","r",stdin);freopen("concatenation.out","w",stdout);}
void tempwj(){freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){a %= mod;ll ans = 1;while(b){if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{bool operator()(const pii & a, const pii & b){return a.second > b.second;}};
int lb(int x){return  x & -x;}

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 2147483648;
const int maxn = 2e3 + 5;
vector<int> vv;
int ans[20004];
int main()
{
    int n;
    scanf("%d",&n);
    int x = sqrt(1.0 *2 * n);
    for (int  i= 1; i <= x; i ++ )
    {
        for (int  j= 1; j <= x; j ++ )
        {
            for (int k = 1; k <= x; k ++ )
            {
                int x = i +j;
                int y = i + k;
                int z = j +k;
                int s = x  *x + y * y +z * z;
                if(s % 2 == 0 && s / 2 <= n)
                {
                    ans[s/2] ++ ;
                }
            }
        }
    }
    for(int i = 1; i <= n; i ++ )
    {
        printf("%d\n",ans[i]);
    }
}


Measured memory_bytes: 3228
import math
N, M = map(int, input().split())
Mod = 10 ** 9 + 7

if abs(N-M) >= 2:
  print (0)
else:
  ans = (math.factorial(N) % Mod) * (math.factorial(M) % Mod)
  if N == M: ans*=2
  print (ans % Mod)

Measured memory_bytes: 4096
#include <atcoder/lazysegtree>
#include <iostream>
#include <vector>
using namespace std;
using namespace atcoder;
typedef long long ll;
ll mod = 998244353,pw1[200010],pw2[200010];
struct S{ll a,len,dig;};
struct F{ll x;};
S op(S l,S r){
    if(l.len>=r.len) return S{(l.a *pw1[l.len - r.len]+ r.a)%mod,r.len,l.dig + r.dig};
    return S{(r.a*pw1[r.len - l.len] + l.a)%mod,l.len,l.dig + r.dig};
}
S e(){return S{0,0,0};}
S mapping(F l,S r){
    if(l.x==-1) return r;
    return S{l.x*pw2[r.dig - 1]%mod,r.len,r.dig};
}
F composition(F l,F r){
    if(l.x==-1) return r;
    return l;
}
F id(){return F{-1};};
int main(){
    int i,n,q; cin >> n >> q;
    pw1[0] = 1;
    for(i=1;i<=n;i++) pw1[i] = pw1[i - 1]*10%mod;
    pw2[0] = 1;
    for(i=1;i<=n;i++) pw2[i] = (pw2[i - 1]*10 + 1)%mod;
    vector<S> v(n);
    for(i=0;i<n;i++) v[i] = {1,n - 1 - i,1};
    lazy_segtree<S,op,e,F,mapping,composition,id> seg(v);
    for(i=0;i<q;i++){
        int l,r,d; cin >> l >> r >> d; l--;
        seg.apply(l,r,F{d});
        cout << seg.prod(0,n).a << endl;
    }
}

Measured memory_bytes: 25436
N = int(input())
W = list(int(i) for i in input().split())  
sumW = sum(W)
W1 = 0
for w in W:
  W1 += w
  if W1 > sumW//2:
    if abs(W1 - w - sumW//2) > W1 - sumW//2:
      print(abs(sumW - (2*W1)))
      break
    else:
      print(abs(sumW - (2*W1) + (2*w)))
      break

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

int main(void) {
	int n;
	cin >> n;
	int maxH = 0;
	int cnt = 0;
	rep(i, n) {
		int h;
		cin >> h;
		if (h >= maxH) {
			cnt++;
			maxH = h;
		}
	}
	if (cnt == 0) cout << 1 << endl;
	else cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long n,a[6],ans=5,k=1;
	cin>>n;
	for(int i=1;i<6;i++)	
		cin>>a[i];
	for(int i=1;i<6;i++){
		long long t;
		if(n%a[i]!=0) t=n/a[i]+1;
		else t=n/a[i]; 
		if(t>k){
			ans+=t-k;
			k=t;
		}
	}
	cout<<ans;
	return 0;
}

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

template<class T> T read() {
	T t;
	cin >> t;
	return t;
}

inline void write() {
}

template<class T> void write(T const& t) {
	cout << t;
}

template<class T, class... Args> void write(T const& t, Args const&... args) {
	cout << t << ' ';
	write(args...);
}

template<class... Args> void writeln(Args const&... args) {
	write(args...);
	cout << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin .exceptions(ios_base::badbit | ios_base::failbit);
	cout.exceptions(ios_base::badbit | ios_base::failbit);
	cin .tie(nullptr);
	cout.tie(nullptr);
	cout.precision(16);
	void run();
	run();
	return 0;
}

void run() {
	auto s = read<string>();
	string weathers[] = {
		"Sunny", "Cloudy", "Rainy",
	};

	for (sint i = 0; i < 3; ++i) {
		if (s == weathers[i]) {
			writeln(weathers[(i + 1) % 3]);
		}
	}
}

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

int main() {
   string s;
   cin >> s;
   int a=0,b=0,c=0;
   for(int i=0;i<3;i++){
      if(s[i]=='a')a++;
      if(s[i]=='b')b++;
      if(s[i]=='c')c++;
   }
   if(a==1 && b==1 && c==1)cout<<"Yes"<<endl;
   else cout<< "No" <<endl;
   return 0;
}


Measured memory_bytes: 764
def resolve():
    '''
    code here
    '''
    S = input()

    memo = 1
    new_list = []
    prev = S[0]

    for i in range(len(S)-1):
        if S[i+1] == prev:
            memo += 1
        else:
            new_list.append(memo)
            memo = 1
        prev = S[i+1]
    else:
        new_list.append(memo)

    # print(new_list)

    res = []
    for i in range(len(new_list)//2):

        a = new_list[i*2]
        b = new_list[i*2 +1]

        res += [0 for _ in range(a)]
        res[-1] = (a+1)//2 + b//2
        res += [a//2 + (b+1)//2]
        res += [0 for _ in range(b-1)]

    print(*res)


if __name__ == "__main__":
    resolve()


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

using ll=long long;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#define REACH cerr<<"reached line "<<__LINE__<<endl
#define DBG(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"[";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"]";
	return os;
}

int read(){
	int i;
	scanf("%lld",&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(int x,int suc=1){
	printf("%lld",x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341919];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341919];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

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

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

template<class T>
T Sq(const T& t){
	return t*t;
}

signed main(){
	int i=read(),a=i;
	int o=read();
	int t=read();
	int j=read(),b=j;
	int l=read(),c=l;
	int s=read();
	int z=read();
	int ans=o;
	ans+=i/2*2;
	i=i&1;
	ans+=j/2*2;
	j=j&1;
	ans+=l/2*2;
	l=l&1;
	if(i&&j&&l)
		ans+=3;
	if(i+j+l==2&&a&&b&&c)
		ans++;
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
	while (1) {
		string s, t, ans;
		vector<string> sl, tl;
		cin >> s;
		if (s == ".")break;
		cin >> t;
		if (s.size() < t.size()) {
			string a;
			a = s;
			s = t;
			t = a;
		}
		string a="";
		for (int i = 0; i < s.size(); i++) {
			if (s[i] != '"')a.push_back(s[i]);
			else {
				sl.push_back(a);
				a = "";
				i++;
				while (s[i] != '"') {
					a.push_back(s[i]);
					i++;
				}
				sl.push_back(a);
				a = "";
			}
		}
		if (a.size() > 0)sl.push_back(a);
		a = "";
		for (int i = 0; i < t.size(); i++) {
			if (t[i] != '"')a.push_back(t[i]);
			else {
				tl.push_back(a);
				a = "";
				i++;
				while (t[i] != '"') {
					a.push_back(t[i]);
					i++;
				}
				tl.push_back(a);
				a = "";
			}
		}
		if (a.size() > 0)tl.push_back(a);
		if (sl.size() != tl.size())ans = "DIFFERENT";
		else {
			int cnt = 0;
			for (int i = 0; i < sl.size(); i++) {
				if (i % 2 == 0 && sl[i] != tl[i]) {
					cnt = 2;
					break;
				}
				else if (i % 2 == 1 && sl[i] != tl[i]) {
					cnt++;
				}
			}
			if (cnt > 1)ans = "DIFFERENT";
			else if (cnt == 1) ans = "CLOSE";
			else ans = "IDENTICAL";
		}
		cout << ans << endl;
	}
	return 0;
}


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

int main() {
  int N;
  cin>>N;
  int B[N-1];
  for (int i = 0; i < N-1;i++) {
    cin>>B[i];
  }

  int val = 0;
  for (int i = 0; i < N;i++) {
    if (i==0) val += B[0];
    else if (i == N-1) val += B[N-2];
    else val += min(B[i-1],B[i]);
  }


  cout<<val<<endl;
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.ComponentModel.Design;
using System.Globalization;
using System.Linq;
using System.Numerics;
using System.Runtime.InteropServices;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading;
using System.Threading.Tasks;
using System.Xml.Schema;
using static System.Console;

namespace ConsoleApp2
{
    class Program
    {
        static public int[] Sarray() { return ReadLine().Split().Select(int.Parse).ToArray(); }
        static public List<int> Slist() {
            var t = ReadLine();
            if (t.Trim().Length == 0) return new List<int>();
            return new List<int>(t.Split().Select(int.Parse)); }
        static void Main(string[] args)
        {
            var N = Sarray()[0];
            WriteLine(Enumerable.Range(1, N).Count(x => x % 2 == 1) / (double)N);
        }
    }
}


Measured memory_bytes: 19676
n,k=map(lambda x: int(x), input().split())
p = list(map(lambda x: int(x), input().split()))

for i in range(len(p)):
	p[i] = .5 * (p[i] + 1)

tsum = sum(p[:k])
msum=tsum
for i in range(k, len(p)):
	tsum += p[i] - p[i-k]
	msum = max(msum, tsum)

print(msum)

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

using namespace std;

int main(){
    string s;
    cin>>s;
    if(s== "Sunny")
     cout<< "Cloudy";
    else if(s== "Cloudy")
     cout<< "Rainy";
    else
     cout << "Sunny";
     return 0;
}


Measured memory_bytes: 256
def main():
	H, W = map(int, input().split())
	S = [""]*H
	for i in range(H):
		S[i] = input()

	for i in range(H):
		for j in range(W):
			if S[i][j] == ".":
				continue
			if (
				(i > 0 and S[i-1][j] == "#")
				or (j > 0 and S[i][j-1] == "#")
				or (i < H-1 and S[i+1][j] == "#")
				or (j < W-1 and S[i][j+1] == "#")
				):
				continue
			print("No")
			return

	print("Yes")


if __name__ == '__main__':
    main()

Measured memory_bytes: 3064