akhauriyash/Code-Regression huggingface dataset:
/*
https://drken1215.hatenablog.com/entry/2020/01/22/114900
勉強させていただいた記事
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;


const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse
#define ALL(a) (a).begin(),(a).end()

int main(){
    int N;
    cin>>N;
    ll res=0;
    vector<vector<ll>> num(10,vector<ll>(10,0));
    REP(n,1,N+1){
        vector<int> d;
        int nn=n;
        while(nn){//桁を後ろから配列につめる
            d.push_back(nn%10);
            nn/=10;
        }
        int a=d[0];//nの一番後ろ
        int b=d.back();//nの一番前
        if(!a||!b)continue;//a,bのどちらかが0での場合飛ばす
        ++num[a][b];
    }
    REP(a,1,10){
        REP(b,1,10){
            //Aの末桁がBの先桁と、Bの末桁がAの先桁に一致する物を求めたいため
            //aとbをひっくり返した物をかけて、その通りの数を答えに足す
            res+=num[a][b]*num[b][a];
        }
    }

    cout<<res<<endl;

    return 0;
}

//a=97,z=122

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int main()
{
   int a,b,c,d,e,f;
   while(~scanf("%d%d%d%d",&a,&b,&c,&d))
   {
       e=a*b;
       f=c*d;
       if(e>=f)
       {
           printf("%d\n",e);
       }
       else
       {
           printf("%d\n",f);
       }
   }
    }


Measured memory_bytes: 128
while(1):
    H,W=map(int,input().split())
    if(H==0):
        break
    for i in range(1,H+1):
        for j in range(1,W+1):
            if((i+j)%2==0):
                print("#",end='')
            else:
                print(".",end='')
        print()
    print()


Measured memory_bytes: 7004
#include <iostream>
#include <ccomplex>
#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>
#include <time.h>
#include <stack>
#include <locale>
#include <clocale>
#include <ctype.h>
#include <wchar.h>
#include <random>
#include <vector>
#include <unordered_map>
#include <bitset>

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SP << " " <<

LL mod = 998244353;

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

  LL N;
  cin>>N;
  vector<LL> a(N * 3);
  REP(i,N*3){
    cin >> a[i];
  }

  BACKSORT(a);

  LL sum = 0;
  REP(i, N)
  {
    sum += a[i*2+1];
  }
  cout << sum << endl;
}


Measured memory_bytes: 2560
#include <stdio.h>
//WA
int main() {
  long int a, b, ans = 0, s;
  scanf("%ld%ld", &a, &b);
  if (a%2) {
    s = b-a;
    if (s%2) {
      ans = a ^ b ^ ((s/2)%2);
    } else {
      ans = a ^ ((s/2)%2);
    }
  } else {
    s = b-a+1;
    if (s%2) {
      ans = b ^ ((s/2)%2);
    } else {
      ans = ((s/2)%2);
    }
  }
  printf("%ld\n", ans);
  return 0;
}


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

int main() {
    int i;
    cin >> i;
    if(i){
        cout << 0 << endl;
    } else {
        cout << 1 << endl;
    }
    return 0;
}


Measured memory_bytes: 3628
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
using ll = long long;

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> g(n,vector<int>());
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> ans(n,-1);
    queue<int> q;
    ans[0]=0;
    q.push(0);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int nv : g[v]){
            if(ans[nv]!=-1) continue; 
            ans[nv]=v+1;
            q.push(nv);
        }
    }
    cout<<"Yes"<<endl;
    for(int i=1;i<n;i++) cout<<ans[i]<<endl;
}

Measured memory_bytes: 10252
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<numeric>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<functional>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};


int main()
{
	int t,p,r;
	while((cin >> t >> p >> r )&&t && p && r){
		int wrong[10][50] = {0};
		int tID,pID,time;
		int ansID[50];
		string msg;
		int memo[50] = {0};

		int cnt[50] = {0};
		for(int i=0;i<r;i++){
			cin >> tID >> pID >> time >> msg;
			if(msg == "WRONG"){
				wrong[pID-1][tID-1]++;
			}else if(msg == "CORRECT"){
				memo[tID-1] += wrong[pID-1][tID-1] * 1200 + time;
				cnt[tID-1]++;
       		 	}
	
			for(int i=0;i<t;i++){
				ansID[i] = i+1;
			}
		}

		for(int i=0;i<t;i++){
			for(int j=i+1;j<t;j++){
				if(cnt[i] < cnt[j]){
					swap(ansID[i],ansID[j]);
					swap(cnt[i],cnt[j]);
					swap(memo[i],memo[j]);
				}
				else if(cnt[i] == cnt[j]){
					if(memo[i] > memo[j]){
						swap(ansID[i],ansID[j]);
						swap(cnt[i],cnt[j]);
						swap(memo[i],memo[j]);
					}else if(memo[i] == memo[j] && ansID[i] > ansID[j]){
						swap(ansID[i],ansID[j]);
						swap(cnt[i],cnt[j]);
						swap(memo[i],memo[j]);
					}
				}
			}
		}
		for(int i=0;i<t;i++){
			cout << ansID[i] << " " << cnt[i] << " " << memo[i] << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define all(v) v.begin(),v.end()
using namespace std;

signed main(){
    int n;
    cin>>n;
    int a[n];
    rep(i,n)cin>>a[i];
    int q;
    cin>>q;
    rep(i,q){
        int b,e,k;
        cin>>b>>e>>k;
        cout<<count(a+b,a+e,k)<<endl;
    }
    return 0;
}


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

int main(){
    string s;
    cin >> s;
    int sum=0;
    for(ll i=0;i<s.length();i++){
        sum+=(s.at(i))-'0';
    }
    if(sum%9==0) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 3684
#include<bits/stdc++.h>
using namespace std;
int a[260000],x[600];
int main()
{
    int i,j,n,k,l,cnt;
    cin >> n;
    for(i=1;i<=n;i++)
    {
        cin >> x[i];
        a[x[i]]=i;
    }
    sort(x+1,x+n+1);
    int ind = 1;
    for(i=1;i<=n;i++)
    {
        int pos = x[i];
        j=a[x[i]];
        k = j-1;
        while(k)
        {
            if(a[ind]==0)
            {
                a[ind] = j;
                ind++;
                k--;
            }
            else
            {
                if(ind==x[i])
                    break;
                ind++;
            }
        }
        if(k)
        {
            cout << "No" << endl;
            return 0;
        }
    }

    for(i=1;i<=n;i++)
    {
        j=a[x[i]];

        for(k=j+1;k<=n;k++)
        {
            while(a[ind])
            {
                ind++;
            }
            if(ind<x[i] || ind>(n*n))
            {
                cout << "No" << endl;
                return 0;
            }
            a[ind] = j;
        }

    }


    cout << "Yes" << endl;
    for(i=1;i<=n*n;i++)
    {
        if(i>1) cout << ' ';
        cout << a[i];
    }
    cout << endl;
    return 0;

}


Measured memory_bytes: 2176
N, Y = gets.split.map(&:to_i)

res10000 = -1
res5000  = -1
res1000  = -1

(0..N).each do |a|
  (0..N - a).each do |b|
    c     = N - a - b
    total = (10000 * a) + (5000 * b) + (1000 * c)
    if total == Y
      res10000 = a
      res5000  = b
      res1000  = c
    end
  end
end

puts [res10000, res5000, res1000].join(' ')


Measured memory_bytes: 1788
#include<stdio.h>
#include<stdlib.h>

#define SENTINEL 1000000001

int nibutan(int left,int right,int num,int s[]){
	int nibun=(left+right)/2;
	if(num>s[nibun])
	{
		if(right-left==1)
		{
			return right;
		}
		return nibutan(nibun,right,num,s);
	}else if(num<s[nibun])
	{
		return nibutan(left,nibun,num,s);
	}else
	{
		return nibun;
	}
	
}

int count=0;

void merge(int A[],int left,int mid,int right);

void mergeSort(int A[],int left,int right){
  int i,mid;
  if(left+1<right){
    mid=(left+right)/2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,mid,right);
  }
}



void merge(int A[],int left,int mid,int right){
  int n1,n2,i,j,k;
  int *L,*R;
  n1=mid-left;
  n2=right-mid;
  L=(int *)malloc(sizeof(int)*(n1+1));
  R=(int *)malloc(sizeof(int)*(n2+1));
  for(i=0;i<=n1-1;i++){
    L[i]=A[left+i];
  }
  for(j=0;j<=n2-1;j++){
    R[j]=A[mid+j];
  }
  L[n1]=SENTINEL;
  R[n2]=SENTINEL;
  i=0;
  j=0;
  for(k=left;k<=right-1;k++){
   if(L[i]<=R[j]){
      A[k]=L[i];
      i++;
      count++;
    }
    else{
      A[k]=R[j];
      j++;
      count++;
    }
  }
  free(L);
  free(R);
}


int main(){
  int A[200000];
  int sortA[200000];
  int n,result=0;

  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&A[i]);
    sortA[i]=A[i];
  }
  mergeSort(sortA,0,n);
  
  for(int i=0;i<n;i++)
  {
  	if(i%2!=nibutan(0,n-1,A[i],sortA)%2)
  	{
  		result++;
  	}
  }
  printf("%d",result/2);
  return 0;
}

Measured memory_bytes: 1536
using System;
using System.Collections.Generic;
using System.Text;

namespace AtCoder
{
  class Program
  {
    static void Main(string[] args)
    {
      int N = int.Parse(Console.ReadLine());

      List<int> primes = new List<int>();
      for(int i = 11; i <= 55555; i += 10)
        if(IsPrime(i))
        {
          primes.Add(i);
          if(primes.Count == N)
          {
            string s = "";
            foreach(int p in primes)
              s += " " + p.ToString();
            Console.WriteLine(s.Substring(1));
            Console.ReadLine();
            return;
          }
        }
    }

    static bool IsPrime(int n)
    {
      for(int i = 3; i <= n / 2; i += 2)
      {
        if(n % i == 0)
          return false;
      }
      return true;
    }
    static bool IsOK(List<int>ans,int newAns)
    {
      for(int a = 1; a < ans.Count - 3; a++)
        for(int b = a + 1; b < ans.Count - 2; b++)
          for(int c = b + 1; c < ans.Count - 1; c++)
            for(int d = c + 1; d < ans.Count; d++)
            {
              int sum = ans[a] + ans[b] + ans[c] + ans[d] + newAns;
              if(IsPrime(sum))
                return false;
            }
      return true;
    }
  }
}

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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define endl '\n'

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

const ll mod=1000000007;
//head

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

    ll n;
    cin >> n;

    ll ans = 1 << 30;
    for(ll i = 1; i * i <= n; i++) {
        if(n % i == 0) {
            ll a = log10(i) + 1;
            ll b = log10(n/i) + 1;
            ans = min(max(a,b),ans);
        }
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	vector<vector<pair<int, int>>> arr(n);
	for(int i = 0; i < n; i++) {
		auto& v = arr[i];
		int m;
		cin >> m;
		v.resize(m);
		for(int j = 0; j < m; j++) {
			cin >> v[j].first >> v[j].second;
			v[j].first--;
		}
	}

	int ans = 0;

	for(int s = 0; s < (1<<n); s++) {
		bool ok = true;
		int best = s;
		for(int b = 0; b < n; b++) {
			if(s >> b & 1) {
				// this person is honest
				for(auto p : arr[b]) {
					int v = p.first, honest = p.second;
					if(honest) {
						if(!(best >> v & 1)) {
							ok = false;
						}
					} else if(best >> v & 1) {
						best ^= 1<<v;
					}
				}
			}
		}

		if(ok && best == s) {
			ans = max(ans, __builtin_popcount(s));
		}
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//using ll = long long;
using P = pair<int,int>;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

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

signed main(){
	int n,K,h[310],dp[310][310][310];
	vector<int> hs;
	cin >> n >> K;
	for(int i = 0;i < n;i++){
		cin >> h[i];
		hs.push_back(h[i]);
	}
	hs.push_back(0);
	sort(all(hs));
	hs.erase(unique(all(hs)),hs.end());
	for(int i = 0;i <= n;i++){
		for(int j = 0;j < hs.size();j++){
			for(int k = 0;k <= K;k++) dp[i][j][k] = INF;
		}
	}
	dp[0][0][0] = 0;
	for(int i = 0;i < n;i++){
		for(int k = 0;k <= K;k++){
			int mi = INF;
			for(int j = 0;j < hs.size();j++){
				chmin(mi,dp[i][j][k] - hs[j]);
				chmin(dp[i + 1][j][k + (hs[j] != h[i])],mi + hs[j]);
			}
			mi = INF;
			for(int j = hs.size() - 1;j >= 0;j--){
				chmin(dp[i + 1][j][k + (hs[j] != h[i])],mi);
				chmin(mi,dp[i][j][k]);
			}
		}
	}
	int ans = INF;
	for(int i = 0;i < hs.size();i++){
		for(int j = 0;j <= K;j++) chmin(ans,dp[n][i][j]);
	}
	cout << ans << endl;
}


Measured memory_bytes: 227968
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
/*-------------------Basis Functions----------------------*/
template<class T> inline void dmin(T& x,T y){ y<x?x=y:0; }
template<class T> inline void dmax(T& x,T y){ y>x?x=y:0; }
template<class T> inline void dmin(T& x,vector<T> y){ 
	for(auto t:y) t<x?x=t:0;
}
template<class T> inline void dmax(T& x,vector<T> y){
	for(auto t:y) t>x?x=t:0;
}
const int MOD=1e9+7;
inline void mo(int& x){x>=MOD?x-=MOD:0;}
inline int mo1(int x){ return x>=MOD?x-MOD:x; }
inline int fpow(int x,int n,int ret=1){
	for(;n;n>>=1,x=1ll*x*x%MOD)
		n&1?ret=1ll*ret*x%MOD:0;
	return ret;
}
struct DSF{
	int fa[5005],sz[5005];
	void ms(int x){ fa[x]=x,sz[x]=1; }
	int fs(int x){
		if(fa[x]!=x) fa[x]=fs(fa[x]);
		return fa[x];
	}
	void merge(int x,int y){
		x=fs(x); y=fs(y);
		if(x==y) return;
		sz[x]+=sz[y];
		fa[y]=x;
	}
}dsf;
vector<int> a,b;
int f[5005],p[5005];
int fac_inv[5005],fac[5005],inv[5005];
bool flag[5005];
void init(int n){
	fac_inv[0]=inv[1]=fac[0]=1;
	for(int i=1;i<=n;++i){
		fac[i]=1ll*i*fac[i-1]%MOD;
		if(i>1) inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
		fac_inv[i]=1ll*fac_inv[i-1]*inv[i]%MOD;
	}
}
int main(){
	int n,sum; scanf("%d",&n);
	for(int i=1;i<=n;++i) dsf.ms(i);
	init(n);
	for(int i=1;i<=n;++i){
		scanf("%d",&p[i]);
		if(p[i]!=-1) dsf.merge(p[i],i);
	}
	for(int i=1;i<=n;++i)
		if(p[i]==-1)
			flag[dsf.fs(i)]=1;
	for(int i=1;i<=n;++i)
		if(dsf.fs(i)==i){
			if(flag[dsf.fs(i)]) 
				a.push_back(dsf.sz[i]);
			else
				b.push_back(dsf.sz[i]);
		}
//	for(int i=0;i<a.size();++i) printf("[%d]",a[i]); puts("");
	int ret=1ll*b.size()*fpow(n-1,a.size())%MOD;
	f[0]=1;
	for(int i=1;i<=a.size();++i)
		for(int j=a.size();j>=1;--j)
			f[j]=(f[j]+1ll*f[j-1]*a[i-1])%MOD;
	for(int j=0;j<=a.size();++j){
		if(j==1) f[j]=(f[j]+MOD-a.size())%MOD;
		ret=(ret+1ll*f[j]*fac[j-1]%MOD*fpow(n-1,a.size()-j))%MOD;
	}
	int ans=1ll*fpow(n-1,a.size())*n%MOD;
//	printf("{%d}",ans);
	ret=mo1(ans+MOD-ret);
	printf("%d\n",ret);
	return 0;
}
	

Measured memory_bytes: 3996
N,M=map(int,input().split())
A=[input() for i in range(N)]
B=[input() for j in range(M)]
for i in range(N-M+1):
    for j in range(N-M+1):
        if A[i][j:j+M]==B[0]:
            if all(A[i+k][j:j+M]==B[k] for k in range(1,M)):
                print("Yes")
                exit()
print("No")

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

int main(){
	long long X,c=100;
	cin >> X;
	for(int i=1;;i++){
		c*=1.01;
		if(c>=X){
			cout << i << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 3620
#include<stdio.h>
#include<string.h>
#define MX 200001
typedef long long int ll;
int len;
char A[MX];
ll sm1 = (ll)0, ad = (ll)0;
int main() {
	int i;
	scanf("%s", A);
	len = strlen(A);
	for (i = 0; i < len; i++) {
		if (A[i] == 'W') {
			ad++;
			sm1 += (ll)i;
		}
	}
	sm1 -= ((ad*(ad - (ll)1)) / 2);
	printf("%lld", sm1);
}

Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
	static void Main()
	{
		var t = Array.ConvertAll(Console.ReadLine().Split(new[] { ' ' }), number => int.Parse(number));

		var ave = t.Average();
		Console.WriteLine(ave % 1.0 > 0.1 ? (int)(ave + 1) : (int)ave);

		//デバッグ実行での確認用。そのまま提出しても問題なし
		Console.ReadKey();
	}
}


Measured memory_bytes: 13268
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+4;
const int MOD=998244353;
int n,d[N];
int cnt[N],tot;
int fpow(int a,int b,int m) {
	int ret=1;
	while (b) {
		if (b&1) ret=1ll*ret*a%m;
		b>>=1,a=1ll*a*a%m;
	}
	return ret;
}
int main() {
	scanf("%d",&n);
	for (register int i=1;i<=n;++i) {
		scanf("%d",&d[i]);
		tot=max(tot,d[i]);
		++cnt[d[i]];
	}
	bool f=true;
	for (int i=0;i<=tot;++i)
		if (!cnt[i]) {
			f=false;
			break;
		}
	if (!f||cnt[0]>1||d[1]^0) {
		puts("0");
		return 0;
	}
	int ans=1;
	for (int i=1;i<=tot;++i) {
		int x=cnt[i-1],y=cnt[i];
		ans=1ll*ans*fpow(x,y,MOD)%MOD;
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1024
package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)

	ans := 0
	for i, j := 0, len(s)-1; i < j; {
		if s[i] == s[j] {
			i++
			j--
		} else if s[i] != 'x' && s[j] == 'x' {
			ans++
			j--
		} else if s[i] == 'x' && s[j] != 'x' {
			ans++
			i++
		} else {
			fmt.Println(-1)
			return
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 1280
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-8;

//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;


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

	long long int T1, T2;
	cin >> T1 >> T2;
	long long int A1, A2, B1, B2;
	cin >> A1 >> A2 >> B1 >> B2;
	if (T1*A1 + T2 * A2 == T1 * B1 + T2 * B2) {
		cout << "infinity" << endl;
		return 0;
	}
	if (A1 > B1&&A2 > B2) {
		cout << 0 << endl;
		return 0;
	}
	if (A1 < B1&&A2 < B2) {
		cout << 0 << endl;
		return 0;
	}
	if (A1 < B1) {
		swap(A1, B1);
		swap(A2, B2);
	}
	////A1>B1&&B2>A2
	if (A1*T1 + A2 * T2 > B1*T1 + B2 * T2) {
		cout << 0 << endl;
		return 0;
	}
	////A1*T1 + A2 * T2 < B1*T1 + B2 * T2
	long long int dis = B1 * T1 + B2 * T2 - A1 * T1 - A2 * T2;
	long long int fst = A1 * T1 - B1 * T1;
	//cout << fst << endl;
	//cout << dis << endl;
	long long int ans = 1;
	if (fst%dis) {
		ans += (fst / dis) * 2;
	}
	else {
		ans += (fst / dis) * 2 - 1;
	}
	cout << ans << endl;
}


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

using namespace std;

ll power(ll n, ll k);
ll inv(ll n);
ll genfact(ll n, ll k);
ll fact(ll n);
ll nck(ll n, ll k);

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

  int n = 0;
  for (int i = 0; i <= a; i++){
    for (int j = 0; j <= b; j++){
      for (int k = 0; k <= c; k++){
        if (500*i + 100*j + 50*k == x)
          n++;
      }
    }
  }


  cout << n << endl;

  return 0;
}


ll power(ll n, ll k){
  ll res = 1;
  while(k > 0){
    if (k & 1) 
      res = res * n % MOD;
    n = n * n % MOD;
    k >>= 1;
  }
  return res;
}

ll genfact(ll n, ll k){

  ll res = 1;
  while (k >= 0){
    res = (res * (n - k)) % MOD;
    k--;
  }

  return res;
}

ll inv(ll n){
  return power(n, MOD - 2);
}

ll fact(ll n){
  return genfact(n, n - 1);
}

ll nck(ll n, ll k){
  if (k == 0)
    return 1;
  if (n <= 0)
    return 0;

  return ((genfact(n, k) % MOD) * inv(fact(k))) % MOD;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

const long long INF = 1e18;
const ll mod = 998244353;
ll dp[3005][3005];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a, b, c, d;
    cin >> a>> b >> c >> d;
    dp[a][b] = 1;
    for(ll i = a; i <= c; i++) {
        for(ll j = b; j <= d; j++) {
            //cerr << i << " " << j << endl;
            if(i > a) {
                dp[i][j] += dp[i-1][j] * j;
            }
            if(j > b) {
                dp[i][j] += dp[i][j-1] * i;
            }
            if(i > a and j > b) {
                dp[i][j] += mod - dp[i-1][j-1] * (i-1) * (j-1);
            }
            dp[i][j] %= mod;
            dp[i][j] += mod;
            dp[i][j] %= mod;
        }
    }
    cout << dp[c][d] << endl;
    return 0;
}


Measured memory_bytes: 74012
#include <stdio.h>
#include <string.h>

#pragma warning(disable:4996)

int A[100000];

int main(void) {
	int N;
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d", &A[i]);
	}
	int minusCnt = 0;
	long long sum = 0;
	int min = 1000000000;
	for (int i = 0; i < N; ++i) {
		if (A[i] < 0) {
			++minusCnt;
			A[i] *= -1;
		}
		if (min > A[i]) {
			min = A[i];
		}
		sum += A[i];
	}
	if (minusCnt % 2 == 1) {
		sum -= min * 2;
	}
	printf("%lld", sum);
	return 0;
}

Measured memory_bytes: 512
#include<stdio.h>
#include<stdlib.h>

int main(){
	int N;
	int a[100];
	int right, left, top, bottom;
	int loop;
	int x[100], y[100];
	left = bottom = 0;
	scanf("%d %d", &right, &top);
	scanf("%d", &N);
	for (loop = 0; loop < N; loop++)
		scanf("%d %d %d", &x[loop], &y[loop], &a[loop]);
	
	for (loop = 0; loop < N; loop++){
		if (a[loop] == 1){
			if (left < x[loop])left = x[loop];
		}
		else if (a[loop] == 2){
			if (right > x[loop])right = x[loop]; 
		}
		else if (a[loop] == 3){
			if (bottom < y[loop])bottom = y[loop];
		}
		else{
			if (top > y[loop])top = y[loop];
		}
	}
	if (right - left <= 0)printf("0\n");
	else if (top - bottom <= 0)printf("0\n");
	else printf("%d\n", (top - bottom)*(right - left));
	return 0;
}

Measured memory_bytes: 128
import itertools
K = int(input())
RC = [list(map(int,input().split())) for _ in range(K)]
P = list(itertools.permutations([0,1,2,3,4,5,6,7]))
PP = []
for p in P:
    for rc in RC:
        if p[rc[0]] != rc[1]:
            break
    else:
        PP.append(p)
for pp in PP:
    for i in range(8):
        for j in range(1,8):
            if i+j <= 7 and (pp[i]+j == pp[i+j] or pp[i]-j == pp[i+j]):
                break
            if i-j >= 0 and (pp[i]+j == pp[i-j] or pp[i]-j == pp[i-j]):
                break
        else:
            continue
        break
    else:
        ppp = pp
        break
for p in ppp:
    print('.......'[:p] + 'Q' + '.......'[p:])


Measured memory_bytes: 10544
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder2 {
	class Program {
		static void Main(string[] args) {
     	var inputArray = retreiveLongArray();
			var inputCount = 1;

			// 不正な入力は処理しない
			if (inputArray.Length != inputCount) {
				Console.WriteLine("invalid input");
				return;
			}
			long N = inputArray[0];
			var X = Console.ReadLine();

			//扱いやすいように1の桁から並べる
			var Xrev = X.Reverse().ToArray();

			var popCount = Xrev.Where(x => x == '1').Count();
			
			//popCount の+-1を格納
			var popS = new long[2];
			popS[0] = popCount + 1;
			popS[1] = popCount - 1 <=0 ? 1 : popCount - 1;

			//N...2のN乗  2...pop+-　それぞれの余り
			var TwoMods = new long[N, 2];
			TwoMods[0,0] = 1 % popS[0];
			TwoMods[0,1] = 1 % popS[1];

			for (int p = 0; p < 2; p++) {
				for (int i = 1; i < N; i++) {
					TwoMods[i, p] = (TwoMods[i - 1, p] * 2) % popS[p];
				}
			}

			//Xをpop+-1で割ったあまり
			var Fx = new long[2];

			
			for (int i = 0; i < N; i++) {
				var c = Xrev[i];
				for (int p = 0; p < 2; p++) {
					if (c == '1') {
						Fx[p] += TwoMods[i, p];
						Fx[p] %= popS[p];
					}

				}
			}

			//i番目をひっくり返す　降順になる
			for (var i = N-1; i >= 0; i--) {
				var c = Xrev[i];
				var first = 0L;
				if (c=='1') {

					//1つしかない1を反転させると、操作0回になる
					if (popCount==1) {
						Console.WriteLine(0);
						continue;
					}

					var p = 1;
					first = Fx[p] - TwoMods[i, p];
					if (first < 0) {
						first += popS[p];
					}
				}
				else {
					var p = 0;
					first = Fx[p] + TwoMods[i, p];
					first %= popS[p];
				}

				var ans = 1 + function(first);
				Console.WriteLine(ans);
			}

		}


		/// <summary>
		/// 問題文のfunctionを実装した関数
		/// </summary>
		/// <param name="n"></param>
		/// <returns></returns>
		private static long function(long n) {

			var count = 0;

			while (n >0) {
				//1が何個あるか求める
				var OneCount = 0L;
				for (int i = 0; i < 32; i++) {
					if ((n >> i & 1) == 1) {
						OneCount++;
					}
				}

				//nを割ってあまりを求める
				n %= OneCount;
				count++;
			}
			return count;


		}



		/// <summary>
		/// スペースで区切られた文字列配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static string[] retreiveStringArray() {
			var inputArray = Console.ReadLine().Split(' ');
			return inputArray;
		}

		/// <summary>
		/// スペースで区切られた整数配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static long[] retreiveLongArray() {
			var inputArray = Console.ReadLine().Split(' ');
			var longArray = inputArray.Select(s => long.Parse(s));
			return longArray.ToArray();
		}


		/// <summary>
		/// 2組みずつの入力データ(数値)からTuppleListを作成する
		/// </summary>
		/// <param name="N"></param>
		/// <returns></returns>
		private static List<Tuple<long, long>> createLongTuppleList(long N) {
			var inpList = new List<Tuple<long, long>>();

			for (int i = 0; i < N; i++) {
				var inp = retreiveLongArray();
				var item1 = inp[0];
				var item2 = inp[1];
				inpList.Add(new Tuple<long, long>(item1, item2));
			}
			return inpList;
		}
	}
}



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

using namespace std;

int main (){
    string s ,t;
    cin >> s >> t;
    int x = stoi (s + t);
    for ( int i = 1; i <= 1000; i++){
        if ( i * i == x ){
            puts ("Yes");
            return 0;
        }
    }
    puts ("No");
}



Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int oturi;
  if(N%1000==0){
    oturi=0;
  }else{
    oturi=1000-N%1000;
  }
  
  cout << oturi <<endl;
}

Measured memory_bytes: 3608
S = list(input())
N = len(S)

from itertools import product
LS = list(product([0,1], repeat=N-1))
out = 0
for L in LS:
    T = S[0]
    for i in range(N-1):
        if L[i]==1:
            T += "+"+S[i+1]
        else:
            T += S[i+1]
    A = list(map(int,T.split("+")))
    out += sum(A)
print(out)

Measured memory_bytes: 71928
N = int(input())

l = []
for i in range(N):
    A, B = map(int, input().split())
    l.append((B, A))
l.sort()
    
ans = 0
t = 0
for i in range(N):
    if (t + l[i][1] <= l[i][0]):
        ans += 1
        t += l[i][1]

if ans == N:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 29420
#include <bits/stdc++.h>
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

int main() {
	int h, w; scanf("%d%d", &h, &w);
	std::vector<std::string> s(h);
	for(int i = 0; i < h; i++) cin >> s[i];
	
	i64 ans = 0;
	std::vector<int> dx = {0, 1, 0, -1};
	std::vector<int> dy = {1, 0, -1, 0};
	std::vector<std::vector<bool>> used(h, std::vector<bool>(w, false));
	for(int i = 0; i < h; i++) {
		for(int j = 0; j < w; j++) {
			if(s[i][j] == '.' or used[i][j]) continue;
			std::queue<std::pair<int, int>> qu; used[i][j] = true; qu.push({i, j});
			i64 A = 1, B = 0;
			while(!qu.empty()) {
				auto p = qu.front(); qu.pop();
				
				for(int k = 0; k < 4; k++) {
					int nx = p.first + dx[k], ny = p.second + dy[k];
					if(nx < 0 or ny < 0 or nx >= h or ny >= w or s[nx][ny] == s[p.first][p.second]) continue;
					if(used[nx][ny]) continue; used[nx][ny] = true;
					if(s[nx][ny] == '.') B++;
					if(s[nx][ny] == '#') A++;
					qu.push({nx, ny});
				}
			}
			ans += A * B;
		}
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 512
from itertools import permutations, combinations
from bisect import bisect_left, bisect
n= int(input())
a = tuple(map(int, input().split()))
b = tuple(map(int, input().split()))
lst = [x for x in range(1, n + 1)]
per = list(permutations(lst, n))
a_index = bisect_left(per, a)
b_index = bisect_left(per, b)
print(abs(a_index - b_index))

Measured memory_bytes: 8052
N,M=map(int,input().split())
a=[0]*(N+1)
INF=10**100
NUM=7+10**9
dp=[0]*(N+1)

for _ in range(M):
    tmp=int(input())
    a[tmp]=1

dp[0]=1
if not a[1]: dp[1]+=dp[0]
for i in range(2,N+1):
    if a[i]: continue
    dp[i]+=dp[i-1]+dp[i-2]
    dp[i]%=NUM

print(dp[N])

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

int main() {
  int N, M;
  cin >> N;
  vector<string> vec1(N);
  for (int i = 0; i < N; i++){
   cin >> vec1.at(i);
  }
  cin >> M;
  vector<string> vec2(M);
  for (int i = 0; i < M; i++){
   cin >> vec2.at(i);
  }
  string c;
  int MAX = 0;
  for (int i = 0; i < N;i++){
   c = vec1.at(i);
   int kaunto = 0;
   for (int i = 0; i < N; i++){
      if (vec1.at(i) == c){
        kaunto++;
      }
   }
   for (int i = 0; i < M; i++){
      if (vec2.at(i) == c){
        kaunto--;
      }
   }
   if (kaunto > MAX){
     MAX = kaunto;
   }
  }
  cout << MAX << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)

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

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

	int minv;
	int minj;
	int tmp;
	int swap_count = 0;
	FOR(i, 0, n - 1) {
		minv = a[i];
		minj = i;
		FOR(j, i + 1, n) {
			if (minv > a[j]) {
				minv = a[j];
				minj = j;
			}
		}
		if (minj != i) {
			tmp = a[i];
			a[i] = a[minj];
			a[minj] = tmp;
			swap_count++;
		}
	}

	REP(i, n) {
		if (i == n - 1) {
			cout << a[i] << endl;
		}
		else cout << a[i] << " ";
	}
	cout << swap_count << endl;

	return 0;
}


Measured memory_bytes: 3120
// finish date: 2018/05/20

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <climits>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvvi vector<vector<vector<int>>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vvd vector<vector<double>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define bigmod 1000000007
#define INF 1050000000
#define pii pair<int,int>


int main() {
    int N;
    cin >> N;
    vi P(N);
    vi A(N);
    rep(i, N) {
        cin >> P[i];
        P[i]--;
        A[P[i]] = i;
    }
    int ma = 1;
    int cnt = 1;
    FOR(i, 1, N) {
        if (A[i - 1] > A[i]) {
            ma = max(ma, cnt);
            cnt = 1;
        } else {
            cnt++;
            if (i == N - 1) {
                ma = max(ma, cnt);
            }
        }
    }
    cout << N - ma << endl;

    return 0;
}




Measured memory_bytes: 1792
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = Long.parseLong(sc.nextLine());
        String S = sc.nextLine();
        sc.close();

        char baseChar = "*".toCharArray()[0];
        long count = 0;

        for (int i = 0; i < S.length(); i++) {
            char s = S.charAt(i);
            if (baseChar != s) {
                baseChar = s;
                count++;
            }
        }

        System.out.println(count);
    }

}

Measured memory_bytes: 26556
import java.util.*;
import java.util.Arrays;
import java.util.Collections;
 
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    Integer[] L= new Integer[N];
    for(int i = 0;i<N;i++){
      L[i]=sc.nextInt();
      }
    int r = 0;
    Arrays.sort(L,Collections.reverseOrder());
    for (int i = 0;i<N-2;i++){
      for(int k = i+1;k<N-1;k++){
        int invm = -1;
        int invs = -1;
        int m = L[i]+L[k];
        int s = L[i]-L[k];
        int Mstart = 0;
        int Sstart = 0;
        if(L[k+(N-k)/2]>=m) Mstart = (N-k)/2;
        if(L[k+(N-k)/2]>s) Sstart = (N-k)/2;
        for(int j = 0;j<(N-k)/2;j++){
          if(invm == -1 &&k+Mstart+j+1<N&&L[k+Mstart+j+1]<m){
            if(L[(k+Mstart+j+1+N)/2]>=m){
              invm = (k+Mstart+j+1+N)/2-1;
            }else{
              invm = k+Mstart+j;
            }
          }
          if(invs ==-1 &&k+Sstart+j+1<N&&L[k+Sstart+j+1]<=s){
            if(L[(k+Mstart+j+1+N)/2]>=m){
              invs=(k+Sstart+j+1+N)/2-1;
            }else{
            invs = k+Sstart+j;
            }
          }
        }
        if(invs == -1) invs = N-1;
        if(invs>invm) r+=invs-invm;
      }
    }
    System.out.println(r);
  }
}

Measured memory_bytes: 39820
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;

int n, m, k;
bool swi[11][11];
int p[11];
bool onoff[11];

int test(){
	for (int i = 1; i <= m; i++){
		int coun = 0;
		for (int j = 1; j <= n; j++){
			if (swi[i][j]){
				if (onoff[j]) coun++;
			}
		}
		if (coun%2 != p[i]) return 0;
	}
	return 1;
}


int main(){
 	cin >> n >> m;
 	for (int i = 1; i <= m; i++){
 		cin >> k;
 		for (int j = 0; j < k; j++){
 			int temp;
 			cin >> temp;
 			swi[i][temp] = true;
 		}
 	}
 	for (int i = 1; i <= m; i++) cin >> p[i];

 	int ans = 0;
 	for (int i = 0; i < (1<<n); i++){
 		for (int j = 0; j < n; j++){
 			if (i & (1<<j)){
 				onoff[j+1] = 1;
 			}else{
 				onoff[j+1] = 0;
 			}
 		}
 		ans += test();
 	}
 	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=(0);i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef double ld;

template<class T> inline void read(T &x){
	int f=0;x=0;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())f|=(ch=='-');
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(f)x=-x;
}

const ld pi=acos(-1);
const int N=6005;
int t[N],n,L;
ld ansx,ansy;

ld solvex(int a,int b,int c){
	if(a==b||b==c||c==a)return 0;
	ld A=sqrt(1-cos(2*pi*(c-b)/L));
	ld B=sqrt(1-cos(2*pi*(a-c)/L));
	ld C=sqrt(1-cos(2*pi*(b-a)/L));
	return (A*cos(2*pi*a/L)+B*cos(2*pi*b/L)+C*cos(2*pi*c/L))/(A+B+C);
}

ld solvey(int a,int b,int c){
	if(a==b||b==c||c==a)return 0;
	ld A=sqrt(1-cos(2*pi*(c-b)/L));
	ld B=sqrt(1-cos(2*pi*(a-c)/L));
	ld C=sqrt(1-cos(2*pi*(b-a)/L));
	return (A*sin(2*pi*a/L)+B*sin(2*pi*b/L)+C*sin(2*pi*c/L))/(A+B+C);
}

int main(){
	read(n),read(L);
	rep(i,1,n){
		read(t[i]);
		t[i+n]=t[i]+L;
	}
	ld cnt=0;
	rep(i,2,n-1)rep(j,i+1,n){
		int c=i-1+n-j-(j-i-1);
		ansx+=c*solvex(t[1],t[i],t[j]);
		ansy+=c*solvey(t[1],t[i],t[j]);
		cnt+=c;
	}
	ansx/=cnt,ansy/=cnt;
	printf("%.10f %.10lf\n",ansx,ansy);

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;

#define forn(i,n) for (int i = 0; i < int(n); ++i)
#define forsn(i,x,y) for(long long i = (x) ; i <= (y) ; ++i)
typedef long long ll;
typedef long double ld;


int main() {
  ll n;
  cin >> n;
  vector<ll> a;
  vector<ll> subs;
  ll total = 0;
  ll ave = 0;
  forn(n0,n) {
    ll t;
    cin >> t;
    a.push_back(t);
    total += t;
  }
  subs.push_back(a[0] - a[a.size()-1]);
  for(int i =1 ;i < n; i++) {
    subs.push_back(a[i] - a[i-1]);
  }
  ave = (n * (n+1)) / 2;
  if(total % ave != 0) {
    cout << "NO" << endl;
    return 0;
  }
  ll numadd = total / ave;
  ll sub = n-1;
  ll num_sub = numadd;
  /*
  forn(i,n) {
    cout << subs[i] << " " ;
  }
  cout << endl;
  cout << "numadd:" << numadd << endl;
  */
  for(int i = 0; i < n; i++) {
    //cout << "i:" << i << endl;
    if((subs[i] - numadd) % n != 0) {
      cout << "NO" << endl;
      return 0;
    }
    if(subs[i] - numadd > 0) {
      cout << "NO" << endl;
      return 0;
    }
    //cout << (subs[i] - numadd) / n << endl;
    num_sub += (subs[i] - numadd) / n;
  }
  
  
  if(true) { //num_sub == 0) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }

  return 0;
}

Measured memory_bytes: 2676
#include <bits/stdc++.h>
using namespace std;
int main() {
  string s;
  cin >> s;
  map<char,int> list;
  for (int i=0; i<s.size(); i++) {
    list[s.at(i)] += 1;
  }
  bool j = true; 
  for (auto x:list) {
    if (x.second%2 != 0) {
      j = false;
    }
  }
  if (j) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

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

int main() {
    int n, x;
    cin >> n >> x;
    vector< int> v(n);
    for (int &i : v) {
        cin >> i;
        x -= i;
    }
    int res = n;
    sort(v.begin(), v.end());
    res += x / v[0];
    printf("%d\n", res);
}

Measured memory_bytes: 256
def move(position):
    x = position[0]
    y = position[1]
    d = position[2]
    if d == "L":
        p = "DLUR"
    elif d == "R":
        p = "URDL"
    elif d == "U":
        p = "LURD"
    else:
        p = "RDLU"
    for i in range(4):
        if p[i] in grid[y][x]:
            d = p[i]
            if d == "L":
                print("L",end="")
                x -= 1
                break
            elif d == "R":
                print("R",end="")
                x += 1
                break
            elif d == "U":
                print("U",end="")
                y -= 1
                break
            else:
                print("D",end="")
                y += 1
                break
    return [x, y, d]

pos = [1,1,"R"]
grid = [["" for i in range(6)] for j in range(6)]
for i in range(9):
    inp = input()
    if i%2 == 0:
        for j in range(4):
            if inp[j] == "1":
                grid[i//2 + 1][j + 1] += "R"
                grid[i//2 + 1][j + 2] += "L"
    else:
        for j in range(5):
            if inp[j] == "1":
                grid[i//2 + 1][j + 1] += "D"
                grid[i//2 + 2][j + 1] += "U"
while True:
    pos = move(pos)
    if pos[0] == 1 and pos[1] == 1:
        break
print("")


Measured memory_bytes: 5572
program main
  implicit none
  integer(8) :: n, i, res, r
  integer(8), allocatable :: a(:), left(:), right(:)
  read (*, *) n
  allocate (a(n), left(n), right(n))
  read (*, *) a(:)
  left(1) = a(1)
  do i = 2, n
    left(i) = gcd(left(i - 1), a(i))
  end do
  right(n) = a(n)
  do i = n - 1, 1, -1
    right(i) = gcd(right(i + 1), a(i))
  end do
  res = 1
  do i = 1, n
    if (i == 1) then
      r = right(2)
    else if (i == n) then
      r = left(n - 1)
    else
      r = gcd(left(i - 1), right(i + 1))
    end if
    res = max(res, r)
  end do
  write (*, "(i0)") res
  contains
  pure function gcd(x, y) result(a)
    integer(8), intent(in) :: x, y
    integer(8) :: a, b, r
    a = max(x, y)
    b = min(x, y)
    do while (b > 0)
      r = mod(a, b)
      a = b
      b = r
    end do
  end function gcd
end program main


Measured memory_bytes: 3200
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <queue>
#include <vector>
#include <cmath>
#include <cctype>
#include <cstring>
#include <cstdio>

using namespace std;

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

int main(void){
  int p, q, r;
  cin >> p >> q >> r;

  int min_time = 200;

  if (p + q < min_time) min_time = p+q;
  if (p + r < min_time) min_time = p+r;
  if (q + r < min_time) min_time = q+r;

  cout << min_time << endl;


  return 0;
}

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

int main() {
  
  int ans = 0;
  int n;
  int a;
  int p;
  int sum = 0;
  int squ = 0;
  cin >> n;
  
  for(int i =0; i < n; i++) {
    cin >> a;
    sum = sum + a;
    squ = squ + a * a;
  }
  
  if(sum % n * 2 < n) {
    p = sum / n;
  }
  else {
    p = sum / n + 1;
  }
  
  ans = squ - 2 * sum * p + n * p * p;
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
n = int(input())
lis = []
for i in range(n):
    lis.append(list(map(int, input().split())))
s = 0
for i in range(n):
    for j in range(i,n):
        s += ((lis[i][0] - lis[j][0])**2 + (lis[i][1] - lis[j][1])**2)**(1/2)
print(s*2/n)

Measured memory_bytes: 3064
n,y = map(int,input().split())
for i in range(n+1):
    for j in range(n+1-i):
        k = n - i - j
        if (10000 * i + 5000 * j + 1000 * k == y) & (i+j+k==n):
            print(i,j,k)
            exit()
print('-1 -1 -1')

Measured memory_bytes: 3060
#include <bits/stdc++.h> 
#define pb push_back 
#define gc getchar 
#define mp make_pair
#define pii pair<int,int> 
#define pll pair<lli,lli>
#define vi vector<int>
#define vc vector<char>
#define pdd pair<double,double>
#define rep(i,n) for(int i=0;i<n;i++)
#define repi(i,a,b) for(int i=a;i<=b;i++)
#define repd(i,a,b) for(int i=a;i>=b;i--)
#define vvi vector<vector<int> >
#define vvli vector<vector<long long int> >
#define vli vector<long long int> 
#define pq priority_queue 
#define lli long long int
#define li long int
#define f first
#define len length
#define p(x) cout<<x<<" "
#define pline(x) cout<<x<<"\n"
#define pcase(test) cout<<"Case #"<<test<<": "
#define take(x) cin>>x
#define s second
#define arrtake(n,inp) rep(i,n){int x;cin>>x;inp.pb(x);}
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define M 1000000007
#define PI 3.14159265358979323
using namespace std;
     /*ios_base::sync_with_stdio(false);
         cin.tie(NULL);*/
template <typename T>
void printvec(vector<T>& vec){
   rep(i,vec.size()){
       cout<<vec[i]<<" ";
   }
   cout<<endl;
}



int main() {

    ios_base::sync_with_stdio(false);

   	string s;
   	cin>>s;


   	lli sum = 0;

   	rep(i,s.length())
   	{
   		sum+=s[i]-'0';
   	}

   	if(sum%9==0)
   	{
   		cout<<"Yes\n";
   	}
   	else cout<<"No\n";

}



Measured memory_bytes: 3780
n=int(input())
a_l=sorted(map(int,input().split()))
a_l.append("!")
cnt = 1
ans = 0

for i in range(1,n+1):
    a1 = a_l[i-1]
    a2 = a_l[i]
    if a1 == a2:
        cnt += 1
    else:
        if cnt - a1 >= 0:
            ans += cnt - a1
        else:
            ans += cnt
        cnt = 1

print(ans)

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

int par[100005],ran[100005];
void init(){ for(int i=0;i<100005;i++) par[i] = i; }
int find(int x){ if(x == par[x]) return x; else return par[x] = find(par[x]); }
void unite(int x,int y){
	x = find(x); y = find(y); if(x==y) return;
	if(ran[x] < ran[y]) par[x] = y;
	else{
		par[y] = x;
		if(ran[x] == ran[y]) ran[x]++;
	}
}
bool same(int x,int y){ return find(x)==find(y); }
multiset<P>S;
int main(){
	scanf("%d%d",&n,&m);
	init();
	rep(i,m){
		int a,b;
		scanf("%d%d",&a,&b);
		unite(a,b);
		S.insert(mp(a,b));
		deg[a]++; deg[b]++;
	}
	for(int i=1;i<=n;i++){
		if(find(1) != find(i)){
			puts("No");
			return 0;
		}
		if(deg[i]%2 == 1){
			puts("No");
			return 0;
		}
	}
	int ok = 0;
	vector<int>vi;
	for(int i=1;i<=n;i++){
		if(deg[i] >= 6){
			ok += 5;
		}
		else if(deg[i] == 4){
			ok ++;
			vi.pb(i);
		}
	}
	if(ok == 2){
	    int x = vi[0], y = vi[1];
	    init();
	    for(auto it:S){
	    	if(it.fi != x && it.sc != x){
	    		if(same(it.fi,it.sc)){
	    			puts("Yes");
	    			return 0;
	    		}
	    		unite(it.fi,it.sc);
	    		//cout << it.fi << " " << it.sc << endl;
	    	}
	    }
	    puts("No"); return 0;
	}
	puts(ok >= 2 ? "Yes":"No");
}


Measured memory_bytes: 6144
N = int(input())
L = list(map(int, input().split()))
c = 0
for i in range(len(L)):
    for j in range(i+1,len(L)):
        for k in range(j+1, len(L)):
            if (L[i] != L[j] and L[j] != L[k] and L[k] != L[i]
                and L[i] + L[j] > L[k]
                and L[j] + L[k] > L[i]
                and L[k] + L[i] > L[j]):
                c += 1
print(c)

Measured memory_bytes: 9200
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long x = sc.nextLong();
		sc.close();

		if (x <= n) {
			System.out.println(0);
			return;
		}

		long[] pTotal = new long[n + 1];
		pTotal[0] = 1;
		for (int i = 1; i <= n; i++) {
			pTotal[i] = pTotal[i - 1] * 2 + 1;
		}

		long total = (long) Math.pow(2, n + 2) - 3;
		if (total - n <= x) {
			System.out.println(pTotal[n]);
			return;
		}

		int n2 = n;
		long x2 = x;
		long ans = 0;
		while (n2 >= 0) {
			if (n2 == 0) {
				ans += pTotal[n2];
				break;
			}
			long mid = total / 2 + 1;
			n2--;
			if (x2 == mid) {
				ans += pTotal[n2] + 1;
				break;
			}
			if (x2 > mid) {
				ans += pTotal[n2] + 1;
				x2 -= mid;
			} else {
				x2--;
			}
			if (x2 == 0) {
				break;
			}
			total -= mid + 1;
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 23124