akhauriyash/Code-Regression huggingface dataset:
/*
.   Bismillahir Rahmanir Rahim
.   Author - Marajul islam
.   created- Sun Mar 22 19:02:10 2020

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


 
int sc1() {int x; scanf("%d", &x); return x;}
long long sc2() {long long x; scanf("%lld", &x); return x;}

const int mod= 1e9 + 7;
inline int add(int a, int b) {a += b; return a >= mod ? a - mod : a;}
inline int sub(int a, int b) {a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b) {return (long long)a * b % mod;}
 
#define F               first
#define S               second 
#define mp              make_pair
#define pb              push_back
#define pf              push_front
#define speed_up        ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define sz(x)           (int)x.size()
#define all(x)          x.begin(), x.end()
#define debug           cerr << "OK\n";
#define ub              upper_bound
#define lb              lower_bound
#define gcd(a,b)        __gcd(a,b)
#define lcm(a,b)        (a*b)/gcd(a,b)
#define Int             sc1()
#define LL              sc2()
#define For(n)          for(int i=0;i<n;i++)
#define Forj(n)         for(int j=0;j<n;j++)
#define Fork(n)         for(int k=0;k<n;k++)
#define For1(n)         for(int i=1;i<=n;i++)

typedef long long       ll;
typedef vector<int>     vi;
typedef vector<ll>      vll;
typedef pair<int, int>  pii;
typedef pair<ll, ll>    pll;
typedef vector<pii>     vpii;
typedef set <int>       si;
typedef set <ll>        sll;
typedef multiset <int>  msi;
typedef multiset <ll>   msll;
typedef map <int, int>  mi;
typedef map <ll, ll>    mll;

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {cout << endl;}
template<typename T, typename... Args> void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << ", ";
    err(++it, args...);
}
  
const int inf           = (int)2e9 + 5;
const ll  Inf           = (ll)1e18 + 5;
const int N             = 5e6 + 5;
 
 
 
int solve() {
 
	double n;
	cin>>n;
	double x=n/3.0;

	cout<<fixed<<setprecision(10);
	cout<<x*x*x<<endl;
 
	return 0;
}
 
 
 
 
int main()
{
	//speed_up;
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
 
	int test = 1, tc = 0;
	//scanf("%d", &test);
	//cin >> test;
	while (test--) {
		//printf("Case %d: ", ++tc);
		solve();
	}
 
	return 0;
 
 
 
 
}




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

using namespace std;
typedef long long int ll;

ll monster(ll H)

{
    if(H == 1)
        return 1;
    else{
        return 2*monster(floor(H/2))+1;
    }
}

int main(void)

{
    ll H, a;
    cin>>H;
    a = monster(H);
    cout<<a<<"\n";
    return 0;
}


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

using namespace std;

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

const int INF = 1000000000;
const ll LINF = (ll) 4000000000000000000;
const ll MOD = (ll) 998244353;
const double PI = acos(1.0);
const int limit = 100010;

#define REP(i,m,n) for(ll i = m; i < (ll)(n); i++)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define NP(v) next_permutation(v.begin(),v.end())
#define smaller_queue  priority_queue <ll, vector<ll>, greater<ll> >

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

const ll MAX_N = 3 * limit;
ll fact[MAX_N];
ll fact_inv[MAX_N];

ll bin_pow_mod(ll x, ll y) { //x^y mod
    if (x == 0) return 0;
    ll prod = 1;
    while (y > 0) {
        if (y % 2 == 1) prod = (prod * x) % MOD;
        x = (x * x) % MOD;
        y /= 2;
    }
    return prod % MOD;
}

void init_fact() {
    fact[0] = fact_inv[0] = 1;

    REP(i, 1, MAX_N) {
        fact[i] = (fact[i - 1] * i) % MOD;
        fact_inv[i] = bin_pow_mod(fact[i], MOD - 2);
    }
}

ll comb_mod(ll n, ll r) {
    if (n < r) return 0;
    else return ((fact[n] * fact_inv[n - r]) % MOD * fact_inv[r]) % MOD;
}

int main() {
    ll n, a, b, k;
    cin >> n >> a >> b >> k;

    init_fact();

    vector<pll> v;

    REP(m, 0, n + 1) {
        ll bi_n = k - a*m;
        if (bi_n >= 0 && bi_n % b == 0 && bi_n / b <= n) v.push_back(MP(m, bi_n / b));
    }

    ll ans = 0;

    for (auto p : v) {
        ll ai = p.first;
        ll bi = p.second;

        ans += comb_mod(n, ai) * comb_mod(n, bi) % MOD;
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 11120
import std.algorithm;
import std.array;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

void main() {
    int r; scan(r);
    writeln(3 * r * r);
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int D = sc.nextInt();
        int X = sc.nextInt();
        int[] A = new int[N];
        for(int i = 0; i< N; i++) A[i] = sc.nextInt();
        
        //食べたチョコ数を宣言・初期化
        int count = 0;
        for(int i = 0; i < N; i++){
          	//チョコを食べた日
            for(int j = 0; j*A[i] + 1 <= D; j++){
                count++;
            }
        }
        System.out.println(count + X);
    }
}


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

#define fi first
#define se second
#define FOR(a, b, c) for(int a = b; a <= c; ++a)
#define pb push_back
#define double long double

const int MOD = 1e9 + 7;
const int oo = 1e9;
const int N = 1e5 + 10;

typedef pair<double, int> ii;

int n;
int BIT[N];
double a[N], b[N], c[N];
double eps = 1e-10;
ii pa[N];
struct con{
    double a, b;
    // y = ax + b
    // :D
}t[N];

bool cmp(const con x, const con y)  {
    if(x.a != y.a) return x.a < y.a;
    else {
        return x.b < y.b; // :D
    }
}

bool cmpv(ii x, ii y)   {
    if(x.fi != y.fi) return x.fi < y.fi;
    return x.se < y.se;
}

double get(con x, double s) {
    return 1.00 * x.a * s + x.b;
}

void upd(int pos)   {
    for(int i = pos; i <= n; i += (i & -i)) BIT[i] ++;
    return; // :D
}

int getBIT(int pos) {
    int res = 0;
    for(int i = pos; i >= 1; i -= (i & -i)) res += BIT[i];
    return res;
}

bool check(double s)    {
    FOR(i, 1, n) BIT[i] = 0;
    FOR(i, 1, n)    pa[i] = ii(get(t[i], s), i);
    sort(pa + 1, pa + 1 + n, cmpv);
    //FOR(i, 1, n) cout << i << ' ' << t[i].a << ' ' << t[i].b << '\n';
    //cout << "spm\n";
    //FOR(i, 1, n) cout << pa[i].fi << ' ' << pa[i].se << '\n';
    int cnt = 0;
    for(int i = n; i >= 1; --i)    {
        cnt += getBIT(pa[i].se);
        upd(pa[i].se);
    }

    int tmp = (n - 1) * n / 2;
    cnt = tmp - cnt;
    return cnt >= (tmp + 1) / 2;
}

double solve()  {
    // we need to find x
    // x = s => a = 1 && b = -s
    double l = (-1.00) * oo, r = 1.00 * oo;
    while(r - l > eps)  {
        //cout << l << ' ' << r << '\n';
        double mid = (l + r) / 2;
        if(check(mid)) // >= mid
            r = mid;
        else l = mid + eps;
    }
    //cout << l << ' ' << r << '\n';
    //cout << fixed << setprecision(9) << l << ' ' << r << '\n';
    if(check(l)) return 1.00 * l;
    else return 1.00 * r;
}

signed main()
{
    //freopen("test.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    FOR(i, 1, n) cin >> a[i] >> b[i] >> c[i];
    FOR(i, 1, n)    {
        t[i].a = (-1.00) * a[i] / b[i];
        t[i].b =  1.00 * c[i] / b[i];
    }
    sort(t + 1, t + n + 1, cmp);
    //cout << check(-1.000000000000000) << '\n'; return 0;
    //cout << solve() << '\n'; return 0;
    double x = solve(); //cout << fixed << setprecision(9) << x << '\n';
    FOR(i, 1, n)    {
        // ay + b = x
        t[i].a = (-1.00) * b[i] / a[i];
        t[i].b = 1.00 * c[i] / a[i];
    }
    sort(t + 1, t + n + 1, cmp);
    double y = solve();
    cout << fixed << setprecision(10) << x << ' '<< y;
    // :D
    return 0;
}


Measured memory_bytes: 9856
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MP make_pair
#define ull unsigned long long int
#define F first
#define S second
#define put insert
#define pb push_back
#define rsort(arr) sort(arr.begin(),arr.end(),greater<int>())
#define srt(arr) sort(arr.begin(),arr.end())
ll MOD = 1e9+7;
int main() {
    ll n,k;
    cin>>n>>k;
    vector<ll> marks(n);
    for(int i=0;i<n;i++)
        cin>>marks[i];
    int i = k, j = 0;
    vector<string> res;
    while(i < n) {
        if(marks[j] < marks[i])
            res.pb("Yes");
        else
            res.pb("No");
        i++, j++;
    }
    for(string s : res)
        cout<<s<<"\n";
    return 0;
}

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

char op(int i){
  if(i == 0) return '+';
  else return '-';
}

int main() {
  string S;
  cin >> S;
  vector<int> ticket(4);
  for(int i=0; i<4; i++){
    ticket.at(i) = S.at(i) - '0';
  }
  int ret = 0;
  for(int i=0; i<2; i++){
    for(int j=0; j<2; j++){
      for(int k=0; k<2; k++){
        ret = ticket.at(0) + ticket.at(1)*(1-2*i) + ticket.at(2)*(1-2*j) + ticket.at(3)*(1-2*k);
        if(ret == 7){
          cout << S.at(0) << op(i) << S.at(1) << op(j) << S.at(2) << op(k) << S.at(3) << '=' << ret << endl;
          return 0;
        }
      }
    }
  }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
   long n;
   cin >> n;
   //cout << n;
   if (n%1000==0)
   {
       cout << 0;
   }
   else
   {
       for (int i=1; i<=10; i++)
       {
           if ((1000*i)>n)
           {
               cout << (i*1000)-n;
               break;
           }
           continue;
       }
   }
   return 0;
}

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

namespace A
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine();
            var data = input.ToCharArray();
            if(data[2] == data[3] && data[4] == data[5])
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
            Console.ReadKey();
        }
    }
}


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

#define FOR(i, a, b) for(long long int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000 //2000000000
#define LLINF 1000000000000000000 //9000000000000000000
#define PI 3.14159265358979

using namespace std;
typedef long long int ll;
typedef pair< long long int, long long  int> P;


int main(void) {
	
	int n;

	cin >> n;

	if (n >= 1000) {
		cout << "ABD" << endl;
	}
	else {
		cout << "ABC" << endl;
	}
}

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

int main(){
 	int n,sum=0;
  	cin>>n;
  	for(int i=0;i<n;i++){
    	int l,r;
      	cin>>l>>r;
      	sum+=r-l+1;
    }
  	cout<<sum<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<utility>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define prin(arg) std::cout<<arg<<"\n"
#define prin2(arg1,arg2) std::cout<<arg1<<" "<<arg2<<"\n"
#define fill(arg,n) std::memset(arg,n,sizeof(arg))
#define mp std::make_pair
#define pb push_back
using std::cin;
typedef long long ll;
typedef std::pair<int,int> pi;
typedef std::vector<int> vi;
typedef std::set<int> si;
typedef std::string str;
const int INF=1e+9;
const ll INFLL=1e+17;
const ll MOD=1e+9+7;
const int NMAX=100010;
int N,M;
int K[100010];
class uft{
public:
  int par[NMAX];//親
  int rank[NMAX];//木の深さ
  int size[NMAX];//木の大きさ
  uft(int n);//コンストラクタ
  int find(int x);
  void unite(int x,int y);
  bool same(int x,int y);
  int usize(int x);
};
uft::uft(int n){//コンストラクタ uft uf(N)でサイズNのunionfindtreeを宣言 
  for(int i=0;i<n;i++){
    par[i]=i;
    rank[i]=0;
    size[i]=1;
  }
}
int uft::find(int x){//xの根を返す
  if(par[x]==x) return x;//根の親は自分自身
  else return par[x]=find(par[x]);//再起で親を辿る
}
void uft::unite(int x,int y){//x,yを併合
  x=find(x);
  y=find(y);
  if(x==y) return ;//根が同じなら併合する必要なし

  if(rank[x]<rank[y]){//木の深い方に浅い方をつける
    par[x]=y;
    size[y]+=size[x];
  }
  else{
    par[y]=x;
    size[x]+=size[y];
    if(rank[x]==rank[y]) rank[x]++;//同じ深さなら深さを増やす
  }
}
bool uft::same(int x,int y){//x,yが同じグループにいるかどうかを返す
  return find(x)==find(y);//根が同じかどうかを判断する
}
int uft::usize(int x){//xの属する木のサイズを返す
  return size[find(x)];
}

int main(){
  vi v[100010];  
  cin>>N>>M;
  rep(i,N){
    cin>>K[i];
    rep(j,K[i]){
      int L;
      cin>>L;
      L--;
      v[L].pb(i);
    }
  }
  uft uf(N);
  rep(i,M){
    if(v[i].size()==0) continue;
    rep(j,v[i].size()-1){
      uf.unite(v[i][j],v[i][j+1]);
    }
  }
  if(uf.usize(0)==N) prin("YES");
  else prin("NO");
  
  
  return 0;
}


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

int main(){ 
  Int N;
  cin >> N;
  
  vector<Int> h(N);
  rep(i,N) cin >> h[i];
  
  vector<Int> dp(N);
  dp[0] = 0;
  dp[1] = abs(h[1] - h[0]);
  if (N >= 3) {
    for (Int i = 2; i < N; i++) {
      dp[i] = min(dp[i-2] + abs(h[i]-h[i-2]), dp[i-1] + abs(h[i] - h[i-1]));
    }
  }
  
  cout << dp[N-1] << endl;

}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pint;

int  main() {
    int n, d;
    cin >> n >> d;
    float arr[n][d];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < d; j++) {
            cin >> arr[i][j];
        }
    }
    int ans = 0;
    double x, y;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            x = 0.0;
            for (int k = 0; k < d; k++) {
                x += (arr[i][k] - arr[j][k]) * (arr[i][k] - arr[j][k]);
            }
            y = sqrt(x);
            if (y - (int) y == 0.0) ans++;
        }
    }
    cout << ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    char ch;
    cin>>ch;
    if(ch=='A') cout<<"T\n";
    if(ch=='T') cout<<"A\n";
    if(ch=='C') cout<<"G\n";
    if(ch=='G') cout<<"C\n";
    return 0;
}


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

using namespace __gnu_pbds;
using namespace std;

#define ff first
#define ss second
#define pb push_back
#define ll long long
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*(b/__gcd(a,b))
#define mkp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define test ll t;cin>>t;while(t--)
#define check(a) cout<<#a<<" = "<<a<<endl;
#define loop(n) for(int i=0;i<n;i++)
#define rloop(n) for(int i=n-1;i>=0;i--)
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fileio freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

const ll Mod = 1000000007LL;
const ll Inf = 2242545357980376863LL;
const int maxn = 2e5;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef vector<pii> vpi;
typedef map<int,int> mii;
typedef map<string,int> msi;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> omset;


//////////////////////// Template Ends ///////////////////////////////////


int main(){
	int n; cin>>n;
	if(n<600 )cout<<8;
	else if(n<800 )cout<<7;
	else if(n<1000)cout<<6;
	else if(n<1200)cout<<5;
	else if(n<1400)cout<<4;
	else if(n<1600)cout<<3;
	else if(n<1800)cout<<2;
	else cout<<1;
	
	return 0;
}





Measured memory_bytes: 3632
// by Balloons
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() puts("okkkkkkkk")
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

using namespace std;

typedef long long LL;

const int inf = 1e9;
int a,b;
char ca='.',cb='#';
char s[105][105];
int main(){
//	freopen("1.in","w",stdout);
	scanf("%d%d",&a,&b);
	puts("100 100");
	int n=100,m=100,nd=b-1;
	for(int i=1;i<=50;i++){
		for(int j=1;j<=100;j++){
			if(i%2==1&&j%2==1&&nd)putchar('#'),--nd;
			else putchar('.');
		}
		puts("");
	}
	nd=a-1;
	for(int i=1;i<=50;i++){
		for(int j=1;j<=100;j++){
			if(i%2==0&&j%2==1&&nd)putchar('.'),--nd;
			else putchar('#');
		}
		puts("");
	}

	return 0;
}


Measured memory_bytes: 256
from bisect import bisect_right

A, B, C, D, E, F = map(int, input().split())

w = set()
for i in range(F // (100 * A) + 1):
    for j in range(F // (100 * B) + 1):
        a = (A * i + B * j) * 100
        if a < F:
            w.add(a)
w.remove(0)

s = set()
t = E * F // 100
for i in range(t // C + 1):
    for j in range(t // D + 1):
        b = C * i + D * j
        if b < t:
            s.add(b)
s = list(s)
s.sort()

best_concentration = -1
best_a = -1
best_b = -1
for a in w:
    i = bisect_right(s, min(E * a // 100, F - a))
    if i == 0:
        continue
    b = s[i - 1]
    concentration = 100 * b / (a + b)
    if concentration > best_concentration:
        best_concentration = concentration
        best_a = a
        best_b = b
print(best_a + best_b, best_b)


Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 10e15+9
#define MOD 1000000007
#define EPS 1e-10
#define MAX_N 100100
#define MAX_M 100100

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

string s;

int a[100];

int main(){
	cin >> s;
	REP(i, s.size()){
		a[s[i] - 'a']++;
	}
	REP(i, 26){
		if (a[i] % 2 == 1){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
}

Measured memory_bytes: 256
while(1):
    s=''
    h,w=map(int,input().split())
    if (w==0)&(h==0):
        break
    else:
        if w>1:
            s1='#.'*(w//2)+'#'*(w%2)
            s2='.#'*(w//2)+'.'*(w%2)
        else:
            s1='#'
            s2='.'
        for i in range(h):
            if i%2:
                print(s2)
            else:
                print(s1)
        print()


Measured memory_bytes: 5608
N = int(input())
K = input()

# 秘密鍵
KEY = N

# 以下に、記述してください。
enc = ""

for char in list(K):
    ASCII = ord(char)
    num = ASCII - 65
    num = (num + KEY) % 26
    ASCII = num + 65
    enc += chr(ASCII)

print(enc)
#シーザー暗号
#https://qiita.com/Naoto9282/items/0c7dd06b0b6cd574d7d3


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iomanip>
#include <functional>
#include <bitset>
#include <limits>
#include <cstdio>
#include <cmath>
#include <cassert>
#include <random>

#ifdef DEBUG
#include "library/Utility/debug.cpp"
#else
#define debug(...)
#endif

#define rep(i,n) for(int i=0;i<(n);++i)
#define EL '\n'
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
using lnt = long long;
struct FIO{FIO(){std::cin.tie(0);std::cout.tie(0);std::ios_base::sync_with_stdio(0);std::cout<<std::setprecision(15);}}fIO;
template<typename T> using V = std::vector<T>;
template<typename T> void fill(V<T>&v) { for(T&e:v) std::cin >> e; }
/*-*/

int main() {
	std::string s;
	std::cin >> s;
	lnt sum=0;
	for(auto c:s) {
		sum+=(lnt)(c-'0');
	}
	if(sum%9==0) print("Yes");
	else print("No");
}


Measured memory_bytes: 3740
N,K=map(int,input().split())
A=sorted([int(i) for i in input().split()])
B=[A[-i-1] for i in range(N)]
mod=10**9+7
Fact=[0 for i in range(N+1)]
Finv=[0 for i in range(N+1)]
Fact[0]=1;Finv[0]=1
def inv(x):
    return pow(x,mod-2,mod)
for i in range(N):
    Fact[i+1]=((i+1)*Fact[i])%mod
    Finv[i+1]=inv(Fact[i+1])
def C(n,k):
    return (Fact[n]*((Finv[k]*Finv[n-k])%mod))%mod
ans1=0
ans2=0
for i in range(K-1,N):
    #print(C(i,K-1))
    ans1+=A[i]*C(i,K-1)
    ans1%=mod
    ans2+=B[i]*C(i,K-1)
    ans2%=mod

print((ans1-ans2)%mod)

Measured memory_bytes: 66984
#include<bits/stdc++.h>
using namespace std;
int k,a[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
int main()
{
	cin>>k;
	cout<<a[k-1];
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <cmath>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;

struct P {
	int x, y, r, c;

	P() : x(0), y(0), r(0), c(0) {}
	P(int x, int y, int r, int c) : x(x), y(y), r(r), c(c) {}
};

int n, ans;
vector<P> v;
set<int> memo;

void dfs(int S) {
	if(memo.find(S) != memo.end()) return;
	memo.insert(S);

	ans = max(ans, __builtin_popcount(S));
	if(ans == n) return;

	bool up[50];
	memset(up, 0, sizeof(up));
	for(int i = n-1; i >= 0; i--) {
		if(S & (1<<i)) continue;

		bool flag = true;
		for(int j = i-1; j >= 0; j--) {
			if(S & (1<<j)) continue;
			int dist = (v[j].x - v[i].x) * (v[j].x - v[i].x) + (v[j].y - v[i].y) * (v[j].y - v[i].y);
			int len = (v[i].r + v[j].r) * (v[i].r + v[j].r);

			if(dist < len) {
				flag = false;
			}
		}

		if(!flag) up[i] = true;
	}

	set<int> st[5];
	for(int i = n-1; i >= 0; i--) {
		if((S & (1<<i)) || up[i]) continue;

		bool flag = true;

		for(int j = i-1; j >= 0; j--) {
			if((S & (1<<j)) || up[j]) continue;

			int dist = (v[j].x - v[i].x) * (v[j].x - v[i].x) + (v[j].y - v[i].y) * (v[j].y - v[i].y);
			int len = (v[i].r + v[j].r) * (v[i].r + v[j].r);

			if(dist >= len && v[i].c == v[j].c) {
				dfs(S + (1<<i) + (1<<j));
			}
		}
	}
}

int main() {
	while(cin >> n && n) {

		v.clear();
		memo.clear();

		rep(i, n) {
			int x, y, r, c;
			cin >> x >> y >> r >> c;
			v.push_back(P(x, y, r, c));
		}

		vector<bool> used(n);
		rep(i, n) used[i] = false;

		ans = 0;
		int S = 0;
		dfs(S);

		cout << ans << endl;
	}

	return 0;
}

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

string s[51];
bool done[51][51];

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

int main() {
	int w,h;
	while(1) {
		cin >> w >> h;
		memset(done, 0, sizeof(done));
		if(w==0 and h==0) break;
		for(int i=0;i<h;i++) {
			cin >> s[i];
		}
		int bcnt = 0, wcnt = 0;
		for(int y=0;y<h;y++) {
			for(int x=0;x<w;x++) {
				if(done[y][x] || s[y][x]=='W' || s[y][x]=='B') continue;
				bool bwith = false, wwith = false;
				queue<pair<int,int> > que;
				que.push({y,x});
				done[y][x] = true;
				int cnt = 1;
				while(!que.empty()) {
					auto tmp = que.front();
					que.pop();
					for(int k=0;k<4;k++) {
						int ny = tmp.first + dy[k];
						int nx = tmp.second + dx[k];
						if(0<=nx && nx<w && 0<=ny && ny<h) {
							if(s[ny][nx]=='.' && !done[ny][nx]) {
								done[ny][nx] = true;
								cnt++;
								que.push({ny,nx});
							} else if(s[ny][nx]=='W') {
								wwith = true;
							}else if(s[ny][nx]=='B') {
								bwith = true;
							}
						}
					}
				}
				if(bwith && !wwith) bcnt += cnt;
				if(!bwith && wwith) wcnt += cnt;
			}
		}
		cout << bcnt << " " << wcnt << endl;
	}
}


Measured memory_bytes: 3036
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define P pair<int, int>
#define sz(x) x.size()
#define all(x) (x).begin(),(x).end()
#define V vector<int>
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;
}

using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}


const long long MOD = 1000000007;
const long long INF = 1LL << 60;

// pair -> vector<pair<int,int>> 
//		   AandB.push_back(make_pair(a[i],b[i]))



signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string s; cin >> s;
	int a = 0, b = 0;
	rep(i, s.size()) {
		if (s.at(i) == 'A') {
			a = i; break;
		}
	}
	reverse(all(s));
	rep(i, s.size()) {
		if (s.at(i) == 'Z') {
			b = s.size()-i; break;
		}
	}
	cout << b - a << endl;
	return 0;
}

Measured memory_bytes: 720
#include <iostream>

int main()
{
    int n,m;

    std::cin >> n >> m;

    int *matrix = new int[n*m];
    int *vector = new int[m];

    for (int row = 0; row < n; row++)
    {
        for (int col = 0; col < m; col++)
        {
            std::cin >> matrix[row*m + col];
        }
    }

    for (int row = 0; row < m; row++)
    {
        std::cin >> vector[row];
    }

    int res;
    for (int row = 0; row < n; row++)
    {
        res = 0;
        for (int col = 0; col < m; col++)
        {
            res += matrix[row*m+col] * vector[col];
        }
        std::cout << res << std::endl;
    }

}


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

int root(int *u,int x){
  if(u[x]==x) return x;
  return u[x]=root(u,u[x]);
}

int same(int *u,int x,int y){
  return root(u,x)==root(u,y);
}

void unite(int *u,int x,int y){
  x=root(u,x);
  y=root(u,y);
  if(x==y) return;
  u[x]=y;
}

void run(void){
  int n,m;
  scanf("%d%d",&n,&m);
  int *u=(int *)calloc(n+1,sizeof(int));
  int i;
  for(i=1;i<=n;i++) u[i]=i;
  int *d=(int *)calloc(m+1,sizeof(int));
  for(i=1;i<=n;i++){
    int k;
    scanf("%d",&k);
    while(k--){
      int l;
      scanf("%d",&l);
      if(d[l]==0){
	d[l]=i;
      } else {
	unite(u,d[l],i);
      }
    }
  }
  for(i=1;i<=n;i++) if(!same(u,1,i)) break;
  printf("%s\n",i>n?"YES":"NO");
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 2176
/**
 * 降参
 * 解説のやり方を試す
 */

#include <iostream>
#include <stack>
#include <unordered_map>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <functional>
#include <iterator>
#include <tuple>
#include <set>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> ps(n+1);
  
  for (int i = 1; i <= n; i++) {
    int p;
    cin >> p;
    ps[p] = i;
  }
   
  long long int result = 0;

  multiset<int> s; // setは内部でソートされる。(されないのはunordered_set。さらにmultiだと、同じキーを複数持てる(番兵用に)
  // 番兵
  s.emplace(0);
  s.emplace(0);
  s.emplace(n+1);
  s.emplace(n+1);

  for (int p = n; p > 0; p--) { // 値が大きい順に処理して、setには自分自身以上の値しかない状態にする。
    const auto& set_result = s.emplace(ps[p]); // 挿入時、自分の位置を返してくれるので、再度findする必要はない
    int w = *prev(set_result, 2);
    int x = *prev(set_result, 1);
    int i = *set_result;
    int y = *next(set_result);
    int z = *next(next(set_result));

    // 自分自身が2番目になる組み合わせ
    // 自分の周辺5点とりだして、
    long long int c = (x-w) * (y-i) // 自分の1個前が1番目で、自分が2番目。つまり、wと自分のみlrの範囲に含む組み合わせ数
      + (z-y) * (i-x); // 自分の1個跡が1番目で、自分が2番目。つまり、yと自分のみlrの範囲に含む組み合わせ数
    result += p*c;
  }
  
  cout << result << endl;
  
  
}


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

namespace ConsoleApplication5
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                char[] input = Console.ReadLine().ToCharArray();
                int[] numbers = (Array.ConvertAll(input, new Converter<char, int>(s => int.Parse(s.ToString()))));

                if (input[0] != '0')
                {
                    Console.WriteLine(numbers.Sum());
                }
                else
                {
                    break;
                }
            }
        }
    }
}

Measured memory_bytes: 9532
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using vc = vector<char>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;

#define rep(i, n) for (ll i = 0; i < ll(n); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define all(x) x.begin(), x.end()

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

    string s;
    cin >> s;

    int n = s.size();

    vi a(n, 0);
    int num = 0;
    char c = 'R';
    rep(i, n - 1) {
        num++;
        if(s[i + 1] != c) {
            if(c == 'R') {
                a[i] = num;
            } else {
                a[i - num + 1] = num;
            }
            num = 0;
            c = s[i + 1];
        }
    }
    repd(i, n) {
        if(s[i - 1] != 'L') {
            a[i] = num + 1;
            break;
        }
    }

    rep(i, n - 2) {
        if(a[i] == 0) {
            cout << 0 << " ";
        } else {
            cout << (a[i] + 1) / 2 + a[i + 1] / 2 << " ";
            cout << a[i] / 2 + (a[i + 1] + 1) / 2 << " ";
            i++;
        }
    }
    if(s[n - 2] == 'R') {
        cout << (a[n - 2] + 1) / 2 + a[n - 1] / 2 << " ";
        cout << a[n - 2] / 2 + (a[n - 1] + 1) / 2 << endl;
    } else {
        if(s[n - 3] == 'L') {
            cout << 0 << " " << 0 << endl;
        } else {
            cout << 0 << endl;
        }
    }
} 

Measured memory_bytes: 3872
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
int main(void)
{
  int n;
  int i;
  int sum=1;
  scanf("%d",&n);
  char a[n][11];
   for(i=0; i<n; i++){
       scanf("%s",&a[i]);
   }

  qsort(a,n,11,strcmp);

  for(i=1;i<n;i++){
      if(strcmp(a[i],a[i-1])!=0) 
        sum++;    
  }
   
  printf("%d",sum);
  return 0;
}


Measured memory_bytes: 5716
N, Q = map(int, input().split())
S = input()
B = [0] * N
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        B[i] = 1
for i in range(1, N-1):
    B[i] += B[i-1]
for i in range(Q):
    l, r = map(int, input().split())
    print(B[r-2] - B[l-2])

Measured memory_bytes: 9204
#include <cstdio>

int main()
{
	int x, a, b, c, ans=0, i, j;

	scanf("%d", &a);
	scanf("%d", &b);
	scanf("%d", &c);
	scanf("%d", &x);

	for(i=0; i<=x/500 && i<=a ; i++){
		for(j=0; j<=(x-500*i)/100 && j<=b; j++){
			if(500*i+100*j+50*c>=x){
				ans++;
			}
		}
	}

	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128
import sys

INF = 1001001001

def resolve():
  s, t = input().split()
  a , b = map(int, input().split())
  u = input()
  if (s == u):
    print(a - 1, b)
  else:
    print(a, b - 1)
  return

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 2940
#include <cstdio>
#include <algorithm>

#define Rep(i, n) for (int i = 1; i <= n; i ++)

using namespace std;

const int N = 200010;

int p[N];

struct Tr{
	int mx0, mx1;
	int mx0i, mx1i;
	int l0, tg;
}t[N * 4];

void up(Tr &x, Tr lc, Tr rc)
{
	if (lc.mx0 > rc.mx0) x.mx0 = lc.mx0, x.mx0i = lc.mx0i;
	else x.mx0 = rc.mx0, x.mx0i = rc.mx0i;
	if (lc.mx1 > rc.mx1) x.mx1 = lc.mx1, x.mx1i = lc.mx1i;
	else x.mx1 = rc.mx1, x.mx1i = rc.mx1i;
	
	if (lc.l0) x.l0 = lc.l0;
	else x.l0 = rc.l0;
}

void push_down(int x)
{
	if (t[x].tg) {
		swap(t[x << 1].mx0, t[x << 1].mx1);
		swap(t[x << 1].mx0i, t[x << 1].mx1i);
		swap(t[x << 1 | 1].mx0, t[x << 1 | 1].mx1);
		swap(t[x << 1 | 1].mx0i, t[x << 1 | 1].mx1i);
		t[x << 1].tg ^= 1, t[x << 1 | 1].tg ^= 1, t[x].tg = 0;
	}
}

void build(int x, int l, int r)
{
	if (l == r) {
		if (l & 1) t[x].mx1 = p[l], t[x].mx1i = l;
		else t[x].mx0 = p[l], t[x].mx0i = l; 
		return;
	}
	int mid = (l + r) >> 1;
	build(x << 1, l, mid); build(x << 1 | 1, mid + 1, r);
	up(t[x], t[x << 1], t[x << 1 | 1]);
}

void modify(int x, int l, int r, int a)
{
	if (l == r) {
		if ((l & 1) ^ t[x].tg) t[x].mx1 = 0;
		else t[x].mx0 = 0;
		t[x].l0 = l;
		return;
	}
	push_down(x);
	int mid = (l + r) >> 1;
	if (a <= mid) modify(x << 1, l, mid, a);
	else modify(x << 1 | 1, mid + 1, r, a);
	up(t[x], t[x << 1], t[x << 1 | 1]);
}

void modify0(int x, int l, int r, int a, int b)
{
	if (a <= l && r <= b){
		t[x].tg ^= 1;
		swap(t[x].mx0, t[x].mx1);
		swap(t[x].mx0i, t[x].mx1i);
		return;
	}
	push_down(x);
	int mid = (l + r) >> 1;
	if (a <= mid) modify0(x << 1, l, mid, a, b);
	if (b > mid) modify0(x << 1 | 1, mid + 1, r, a, b);
	up(t[x], t[x << 1], t[x << 1 | 1]);
}

Tr query(int x, int l, int r, int a, int b)
{
	if (a <= l && r <= b) return t[x];
	push_down(x);
	int mid = (l + r) >> 1;
	Tr ret = (Tr){0, 0, 0}, lc = (Tr){0, 0, 0}, rc = (Tr){0, 0, 0};
	if (a <= mid) lc = query(x << 1, l, mid, a, b);
	if (b > mid) rc = query(x << 1 | 1, mid + 1, r, a, b);
	up(ret, lc, rc);
	return ret;
}

int ans[N];

int main()
{
	//freopen("B.in", "r", stdin);
	//freopen("B.out", "w", stdout);
	
	int n;
	scanf("%d", &n);
	Rep(i, n){ scanf("%d", &p[i]); p[i] = n + 1 - p[i];}
	//Rep(i, n) printf("%d ", p[i]);
	//printf("\n");
	build(1, 1, n);
	
	Rep(i, n / 2){
		Tr t1 = query(1, 1, n, 1, n);
	//	printf("_%d %d\n", t1.mx1, t1.mx1i);
		int tr = query(1, 1, n, t1.mx1i, n).l0;
		if (!tr) tr = n + 1;
		Tr t0 = query(1, 1, n, t1.mx1i + 1, tr - 1);
		//printf("%d %d\n", t1.mx1i + 1, tr - 1);
		ans[i * 2 - 1] = t1.mx1, ans[i * 2] = t0.mx0;
		//printf("%d %d\n", t1.mx1i, t0.mx0i);
		modify(1, 1, n, t1.mx1i); modify(1, 1, n, t0.mx0i);
		modify0(1, 1, n, t1.mx1i, t0.mx0i);
	}
	
	Rep(i, n) printf("%d ", n + 1 - ans[i]);
	
	return 0;
}
/*
4
3 2 4 1
*/

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

rate = [0] * 8
s = 0

for i in a:
    if i < 400:
        rate[0] = 1
    elif 400 <= i < 800:
        rate[1] = 1
    elif 800 <= i < 1200:
        rate[2] = 1
    elif 1200 <= i < 1600:
        rate[3] = 1
    elif 1600 <= i < 2000:
        rate[4] = 1
    elif 2000 <= i < 2400:
        rate[5] = 1
    elif 2400 <= i < 2800: 
        rate[6] = 1
    elif 2800 <= i < 3200:
        rate[7] = 1
    elif 3200 <= i:
        s += 1



    
ans1 = 8-rate.count(0)
ans2 = ans1+s
if ans1 == 0 and s != 0:
    ans1 = 1


print(ans1, ans2)

Measured memory_bytes: 9112
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    vector<int> vec(N);
    for (int i = 0; i < N; ++i) cin >> vec[i];
    sort(vec.begin(), vec.end());
 
    int ans = 0;
 
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            for (int k = 0; k < j; ++k) {
                if (vec[k] != vec[j] and vec[i] != vec[j] and
                    vec[k] + vec[j] > vec[i]) {
                    ans++;
                }
            }
        }
    }
 
    cout << ans << endl;
 
    return 0;
}

Measured memory_bytes: 3584
import * as fs from 'fs'

const input = fs.readFileSync('/dev/stdin', 'utf8');
const args: string[][] = input.split('\n').map(l => l.split(' '));

const [n, m] = args[0].map(x => BigInt(x));
const a = args[1].map(x => BigInt(x));

const sum = a.reduce((x, y) => x + y);

const d = sum > n ? -1 : n - sum;

console.log(Number(d));

Measured memory_bytes: 31128
n = int(input())
a = list(map(int, input().split()))
b = [0 for i in range(n)]
s = 0

for i in range(n):
    b[a[i]-1] += 1

for i in range(n):
    s += (b[i]*(b[i]-1))//2

for i in range(n):
    print(s-b[a[i]-1]+1)

Measured memory_bytes: 25644
// https://atcoder.jp/contests/abc118/tasks/abc118_c

// http://ctylim.hatenablog.com/entry/2015/08/30/191553
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <cstdio>

#define ALL(a) (a).begin(), (a).end()
#define EACH(i, c) for (auto i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())
#define RSORT(c) sort((c).rbegin(), (c).rend())
#define MAXINDEX(c) distance((c).begin(), max_element((c).begin(), (c).end()))
#define MININDEX(c) distance((c).begin(), min_element((c).begin(), (c).end()))
#define DEBUG(x) std::cerr << #x << " = " << (x) << " (" << __FILE__ << "::" << __LINE__ << ")" << std::endl;
#define ERROR(s) std::cerr << "Error::" << __FILE__ << "::" << __LINE__ << "::" << __FUNCTION__ << "::" << (s) << std::endl;
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)

#define repd(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)
typedef long long ll;


void print() { std::cout << std::endl; }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail){
  std::cout << head << ",";
  print(std::forward<Tail>(tail)...);
}

using namespace std;

void solve0(){
  int64_t N, Q;
  scanf("%lld%lld", &N, &Q);
  vector<char> s(N);
  vector<pair<char, char>> td(Q);
  getc(stdin);
  for (int i = 0; i < N; i++)
  {
    s[i] = getc(stdin);
  }
  getc(stdin);
  for (int i = 0; i < Q; i++)
  {
    char t, d;
    scanf("%c %c\n", &t, &d);
    td[i] = make_pair(t, d);
    // print(t,d);
  }

  int L = 0;
  int R = N - 1;
  for (int i = Q - 1; i >= 0; i--)
  {
    char t = td[i].first;
    char d = td[i].second;
    if (L<N && d == 'L') L = L + (t == s[L]);
    else if (L<N && L > 0) L = L - (t == s[L - 1]);

    if (R>=0 && d == 'R') R = R - (t == s[R]);
    else if (R>=0 && R < N - 1) R = R + (t == s[R + 1]);
  }

  cout << (L <= R ? R - L + 1 : 0) << endl;
}

int main(int argc, char **argv)
{
  solve0(); //wrong answer
  return 0;
}


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

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

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

  int N;
  cin >> N;

  if(N == 1){
    cout <<setprecision(6) <<  1.0 << endl;
    return 0;
  }

  if(N%2 == 0){
    cout << setprecision(6) << 0.500000 << endl;
  }else{
    cout << setprecision(6) << (((N-1) / 2.0) + 1.0) / N << endl;
  }
  
  return 0;
}


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

using namespace std;

int main() {
    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;
    int t = c * 2;
    int cost = 0;
    if (a + b > t) {
        if (x < y) {
            cost = t * x + b * (y - x);
            if (t * y < cost)
                cost = t * y;
        }
        else {
            cost = t * y + a * (x - y);
            if (t * x < cost)
                cost = t * x + y;
        }
    }
    else {
        cost = a * x + b * y;
    }
    cout << cost << endl;
}

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

int main()
{
    char c;
    vector<int> v('z' - 'a' + 1);

    while (cin.get(c))
        if (isalpha(c))
            v[tolower(c) - 'a']++;

    for (int i = 0; i < v.size(); i++)
        cout << (char) ('a' +  i) << " : " << v[i] << endl;

    return 0;
}



Measured memory_bytes: 3120
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
//////////////////////////////////

int main() {
  int n; cin >> n;
  int cnt = 0;
  int a;
  for(int i=0; i<n; i++) {
    cin >> a;
    if(i%2 == 0 && a%2 == 1) cnt++;
  }
  cout << cnt << endl;
  return 0;
}

// EOF

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define int long long

#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl

template<typename T> T gcd(T a,T b) { if(a==0) return b; return gcd(b%a,a); }
template<typename T> T pow(T a,T b, long long m){T ans=1; while(b>0){ if(b%2==1) ans=(ans*a)%m; b/=2; a=(a*a)%m; } return ans%m; }

const int N=3e5+5;

int n;
int a[N], b[N], c[N];

int32_t main()
{
    IOS;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
    }
    sort(a+1, a+n+1);
    sort(b+1, b+n+1);
    sort(c+1, c+n+1);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int smaller=lower_bound(a+1, a+n+1, b[i]) - (a+1);
        int larger=n - (upper_bound(c+1, c+n+1, b[i]) - (c+1));
        ans+=smaller*larger;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 5248
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define ld long double
#define zeros(x) x^(x-1)&x
#define pii pair<ll,ll>
#define cd complex<double>
#define dbg(x) cerr<<#x<<": "<<x<<endl;ll
#define Nmax 400005
#define OFF 100001
#define MOD 1000000007
using namespace std;

ll n, x, y, A[Nmax], sav;
vector<ll> v[Nmax];

ll dfs(ll nod, ll ant){
    ll s = 0;
    vector<ll> L;
    for (auto it : v[nod]){
        if (it == ant) continue;
        L.push_back(dfs(it, nod));
        s += L.back();
    }
    if (L.empty()){
        return A[nod];
    }
    sort(L.begin(), L.end());
    ll mn = max(0LL, L.back() - (s - L.back()));
    ll up = mn;
    A[nod] -= mn;
    s -= mn;
    if (s%2) s--, up++, A[nod]--;
    ll y = A[nod] - s / 2;
    ll x = A[nod] - 2 * y;
    if (x >= 0 && y >= 0 && 2 * y + x == A[nod] && A[nod] >= 0 && x + y == s/2)
        return 2 * y+up;
    cout << "NO\n";
    exit(0);
}

int main()
{
    cin >> n;
    for (int i=1;i<=n;i++) cin >> A[i];
    for (int i=1;i<n;i++){
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
        if (v[x].size() > 1) sav = x;
        if (v[y].size() > 1) sav = y;
    }
    if (n==2){
        if (A[1] == A[2]) cout << "YES\n";
        else cout << "NO\n";
        return 0;
    }

    if (dfs(sav, -1) == 0) cout << "YES\n";
    else cout << "NO\n";

    return 0;
}


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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;

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

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 7;
constexpr long long LINF = 1e18;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;

void solve() {
    int n, q;
    string s;
    cin >> n >> s >> q;
    vector<int> k(q);
    for (int i=0; i<q; ++i) {
        cin >> k.at(i);
    }

    for (int i=0; i<q; ++i) {
        int kk = k.at(i);
        ll cntM = 0, cntC = 0, dp = 0, res = 0;
        for (int j=0; j<kk; ++j) {
            if (s.at(j) == 'M') {
                ++cntM;
            } else if (s.at(j) == 'C') {
                ++cntC;
                dp += cntM;
            }
        }
        for (int j=0; j<n; ++j) {
            if (s.at(j) == 'D') {
                res += dp;
            } else if (s.at(j) == 'M') {
                --cntM;
                dp -= cntC;
            } else if (s.at(j) == 'C') {
                --cntC;
            }
            if (j < n-kk) {
                if (s.at(j+kk) == 'M') {
                    ++cntM;
                } else if (s.at(j+kk) == 'C') {
                    ++cntC;
                    dp += cntM;
                }
            }
        }
        cout << res << '\n';
    }
}

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

    solve();

    return 0;
}


Measured memory_bytes: 1948
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

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

    const double PI = acos(-1);
    cout << setprecision(15);
    if (a * a * b == 2 * x) {
        cout << 45 << endl;
    } else if (a * a * b < 2 * x) {
        cout << atan(2 * (b - x / (a * a)) / a) / (2 * PI) * 360 << endl;
    } else {
        cout << atan(a * b * b / (2 * x)) / (2 * PI) * 360 << endl;
    }
}

Measured memory_bytes: 384
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#include <fstream>
//#include <random>
#include <map>
//#include <unordered_map>
#include <cstdlib>
#include <functional>
#include <time.h>
//#include <chrono>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <limits>
#include <numeric>
//#include <type_traits>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define MOD 1000000007
#define SORT(s) sort(s.begin(), s.end());
#define REVERSE(s) reverse(s.begin(), s.end());
#define SUM(s) accumulate(s.begin(), s.end(), 0LL);
#define P pair<int,int>
#define mp make_pair
#define valid(x,y,h,w) (0<=x&&x<h&&0<=y&&y<w)
//#define int ll
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int ndx[8] = { 0,1,0,-1, 1,1,-1,-1 };
int ndy[8] = { 1,0,-1,0, 1,-1,-1,1 };
double pi = 3.141592653589793;
using namespace std;
int POW(int x, int y) { return int(pow(double(x), double(y))); }
double log(double a, double b) { return log(b) / log(a); }



int main() {
	int a;
	cin >> a;
	cout << a + a * a + a * a * a << endl;
}






Measured memory_bytes: 3680
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;

const int MAXN = 4000;
int was[MAXN];
vector<int> eds[MAXN];
int n;
ll a[MAXN];

int dfs1(int v) {
	was[v] = 1;
	for (int u: eds[v]) {
		if (was[u])
			continue;
		int x = dfs1(u);
		if (x)
			continue;
		if (a[v] > a[u])
			return 1;
	}
	return 0;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%lld", a + i);
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		--a, --b;
		eds[a].push_back(b);
		eds[b].push_back(a);
	}
	for (int i = 0; i < n; ++i) {
		memset(was, 0, sizeof(was));
		if (dfs1(i)) {
			cout << i + 1 << " ";
		}
	}
	cout << "\n";
	return 0;
}




Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
int main(void){
    // Your code here!
    unsigned int a,b,r;
    string s;
    cin >> a >> b;
    s = to_string(a) + to_string(b);
    float sq = floor(sqrt(stoi(s)));
    cout << (sq*sq == stoi(s) ? "Yes" : "No");
    
    return 0;
}


Measured memory_bytes: 256