akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>

struct tree: std::vector<std::vector<size_t>> {
  tree(size_t n): std::vector<std::vector<size_t>>(n) {}

  void connect_with(size_t src, size_t dst) {
    (*this)[src].push_back(dst);
    (*this)[dst].push_back(src);
  }
};

std::vector<intmax_t> nya(const tree& g, intmax_t mod) {
  size_t n = g.size();
  std::vector<size_t> parent(n, -1);
  std::vector<std::vector<intmax_t>> dp0(n), dp1(n);
  std::vector<intmax_t> dp(n);
  for (size_t i = 0; i < n; ++i) {
    dp0[i].resize(g[i].size()+1, 1);
    dp1[i].resize(g[i].size()+1, 1);
  }

  [](auto f) {
    return [=](auto g) {
      return [=](auto&&... args) {
        return f(g(g), std::forward<decltype(args)>(args)...);
      };
    }([=](auto g) {
      return [=](auto&&... args) {
        return f(g(g), std::forward<decltype(args)>(args)...);
      };
    });
  }([&](auto f, size_t v, size_t p) -> intmax_t {
    intmax_t res = 1;
    for (size_t i = 0; i < g[v].size(); ++i) {
      size_t u = g[v][i];
      if (u == p) {
        parent[v] = i;
        continue;
      }
      intmax_t tmp = (f(u, v) + 1) % mod;
      (res *= tmp) %= mod;
      dp0[v][i+1] = tmp;
      dp1[v][i] = tmp;
    }
    return res;
  })(0, -1);

  [](auto f) {
    return [=](auto g) {
      return [=](auto&&... args) {
        return f(g(g), std::forward<decltype(args)>(args)...);
      };
    }([=](auto g) {
      return [=](auto&&... args) {
        return f(g(g), std::forward<decltype(args)>(args)...);
      };
    });
  }([&](auto f, size_t v, size_t p, size_t pi) -> void {
    if (v != 0) {
      intmax_t tmp = (dp0[p][pi] * dp1[p][pi+1] + 1) % mod;
      dp0[v][parent[v]+1] = tmp;
      dp1[v][parent[v]] = tmp;
    }
    {
      for (size_t i = 1; i < dp0[v].size(); ++i)
        (dp0[v][i] *= dp0[v][i-1]) %= mod;
      for (size_t i = dp1[v].size()-1; i--;)
        (dp1[v][i] *= dp1[v][i+1]) %= mod;
      dp[v] = dp1[v][0];
    }
    for (size_t i = 0; i < g[v].size(); ++i) {
      size_t u = g[v][i];
      if (u != p) f(u, v, i);
    }
  })(0, -1, -1);

  return dp;
}

int main() {
  size_t N;
  intmax_t M;
  scanf("%zu %jd", &N, &M);

  tree g(N);
  for (size_t i = 1; i < N; ++i) {
    size_t x, y;
    scanf("%zu %zu", &x, &y);
    --x;
    --y;
    g.connect_with(x, y);
  }

  auto dp = nya(g, M);
  for (size_t i = 0; i < N; ++i)
    printf("%jd\n", dp[i]);
}



Measured memory_bytes: 29824
#include<stdio.h>

int main()
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);

    if(b*a==b){
        printf("%d",c);
    }
    else if(b*a<c){
        printf("%d",b*a);
    }
    else{
        printf("%d",c);
    }

}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
set<string>ans;
int main()
{
      ios::sync_with_stdio(false),cin.tie(0), cout.tie(0);
      int n;
      cin >>n;
      for (int i=0; i<n; i++)
      {
            string temp;
            cin >> temp;
            ans.insert(temp);
      }cout << ans.size() << endl;
 	return 0;
}


Measured memory_bytes: 19136
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>


using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;


int main(){
    int a = 10;

    int N;

    cin >> N;

    priority_queue<int> q;

    REP(i,N){
        int a;
        cin >> a;
        q.push(a);
    }

    int olda = -1;
    int newa = -1;
    int count = 0;
    int ans = 0;

    if(q.empty()){
        cout << "0" << endl;
        return 0;
    }
    
    while(!q.empty()){        
        do{
            olda = q.top();
            count++;
            q.pop();
        }while(!q.empty() && olda == q.top() );
        if( count < olda) ans += count;
        else               ans += count - olda;
        count = 0;
    }

    cout << ans << endl;
   
}





Measured memory_bytes: 892
#include <iostream>
#include <cstdio>
#include <vector>
#define N 2005
using namespace std;

int n, k, mx;
bool v[N];
vector<int> a[N];

int f(int p, int q) {
	int i, s = 0;
	if (q < 0) return 0;
	if (v[p]) return 0;
	v[p] = 1;
	for (i = 0; i < a[p].size(); i++) s += f(a[p][i], q - 1);
	v[p] = 0;
	return s + 1;
}

int main()
{
	int i, j, t1, t2;
	cin >> n >> k;
	for (i = 1; i < n; i++) {
		scanf("%d %d", &t1, &t2);
		a[t1].push_back(t2);
		a[t2].push_back(t1);
	}
	if (k % 2 == 0) {
		for (i = 1; i <= n; i++) {
			mx = max(mx, f(i, k / 2));
		}
	} else {
		for (i = 1; i <= n; i++) {
			for (j = 0; j < a[i].size(); j++) {
				v[a[i][j]] = 1; t1 = f(i, k / 2); v[a[i][j]] = 0;
				v[i] = 1; t1 += f(a[i][j], k / 2); v[i] = 0;
				mx = max(mx, t1);
			}
		}
	}
    cout << n - mx << endl;
    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<cstdio>
#include<set>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repn(i, n) for(int i = 1; i <= n; i++) 
#define lint long long

const int MAX = 200000;
const long long MOD = 1000000007;
long long fac[MAX], facinv[MAX], inv[MAX];

// MOD の階乗、Permutation、Combinationなどを求めるための初期化
void facinit(){
    fac[0] = fac[1] = 1;
    facinv[0] = facinv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        facinv[i] = facinv[i - 1] * inv[i] % MOD;
    }   
}

// MOD のPermutation
long long Perm(long long a, long long b){
    if (a < b) return 0;
    if (a < 0 || b < 0) return 0;
    return fac[a] * facinv[a - b] % MOD;
}

// MOD のCombination
long long Combi(long long a, long long b){
    if (a < b) return 0;
    if (a < 0 || b < 0) return 0;
    return fac[a] * (facinv[b] * facinv[a - b] % MOD) % MOD;
}

int main(){
    facinit();
    lint N, M, K; cin>>N>>M>>K;
    lint ans = (((N-1)*N*(N+1) / 6) % MOD) * M*M % MOD;
    ans += (((M-1)*M*(M+1) / 6)%MOD) * N*N % MOD;
    ans = (ans * Combi(N*M-2, K-2)) % MOD;
    cout << ans << endl;
}

Measured memory_bytes: 5624
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<deque>
#include<functional>
#include<iterator>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<utility>
using namespace std;
typedef long long ll;
typedef pair<char,ll> P;
#define a first
#define b second
#define sz(x) (ll)((x).size())
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()
#define all(x) (x).bg,(x).ed
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rep1(i,n) for(ll i=1;i<=(n);i++)
#define rrep(i,n) for(ll i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(ll i=(n);i>=1;i--)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
const ll MOD=1000000007;
const ll INF=1000000000000000;
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;}
ll maxx(ll x,ll y,ll z){return max(max(x,y),z);}
ll minn(ll x,ll y,ll z){return min(min(x,y),z);}
ll gcd(ll x,ll y){if(x%y==0) return y;else return gcd(y,x%y);}
ll lcm(ll x,ll y){return x*(y/gcd(x,y));}
ll digsz(ll x){if(x==0) return 1;else{ll ans=0;while(x){x/=10;ans++;}return ans;}}
ll digsum(ll x){ll sum=0;while(x){sum+=x%10;x/=10;}return sum;}
vector<ll> pw2(62,1);vector<ll> pw_2(62,1);

//level1
//B(P)P(P)B
//level2
//B(BPPPB)P(BPPPB)B
//levelN
//1
//B()P()B

//levelN,下からX
//0:B 1:P
ll rec(ll N,ll X){
    if(N==0) return 1;
    
    if(X==1 || X==0) return 0;
    else if(X==pw2[N+1]-1) return pw2[N];
    else if(X==pw2[N+2]-3) return pw2[N+1]-1;
    else if(X<pw2[N+1]-1) return rec(N-1,X-1);
    else return pw2[N]+rec(N-1,X-pw2[N+1]+1);
}

int main(){
    {rep1(i,61) pw2[i]=2*pw2[i-1];}
    ll N,X; cin>>N>>X;
    //2^(N+2)-3
    cout<<rec(N,X)<<endl;
}



Measured memory_bytes: 3604
#include <stdio.h>

int main(){
  long long k;
  long n,q;
  scanf("%ld %lld %ld",&n,&k,&q);
  int point[100000];
  int i;
  for(i=0;i<100000;i++){
    point[i]=0;
  }
  int Ai;
  for(i=0;i<q;i++){
    scanf("%d",&Ai);
    point[Ai-1]++;
  }
  for(i=0;i<n;i++){
    long long a = k - q + point[i];
    if(a > 0){
      puts("Yes");
    }else{
      puts("No");
    }
  }
  return 0;
}


Measured memory_bytes: 896
import numpy as np
import math as m

def main(**kwargs):
    res = "Yes"

    if S == "AAA" or S == "BBB":
        res = "No"

    return res

if __name__ == "__main__":
    cin = np.array(input().split(" "))
    S, *_ = cin

    cout = main(S=S)
    print(cout)

Measured memory_bytes: 21888
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;

//typedef
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//conversion
inline LL toLong(string s) {LL v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) LL((a).size())
#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())

//repetition
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define UNTIL(p) while(!(p))

//constant
const double EPS = 1e-5;
const double PI  = acos(-1.0);

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

#define PUTS(x) cout << (x) << endl;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    LL n;
    cin>>n;
    
    if(n % 2 == 1){
        PUTS(0);
        return 0;
    }
    n /= 2;
    LL ans = 0;
    while(1){
        if(n >= 5){
            ans += n/5;
            n = n/5;
        }
        else{
            break;
        }
    }
    
    PUTS(ans);
}

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

public class Program
{
    public void Solve()
    {
        var sc = new Scanner();
        int a = sc.NextInt();
        int b = sc.NextInt();
        int k = sc.NextInt();
        var hs = new HashSet<int>();
        for (int i = 0; i < k; i++)
        {
            int aa = a + i;
            int bb = b - i;
            if (aa <= b)
            {
                hs.Add(aa);
            }

            if (bb >= a)
            {
                hs.Add(bb);
            }
        }

        var ar = hs.ToArray();
        Array.Sort(ar);

        Console.WriteLine(string.Join("\n", ar));
    }

    public static void Main(string[] args)
    {
        new Program().Solve();
    }
}

class Scanner
{
    public Scanner()
    {
        _pos = 0;
        _line = new string[0];
    }

    const char Separator = ' ';
    private int _pos;
    private string[] _line;

    #region スペース区切りで取得

    public string Next()
    {
        if (_pos >= _line.Length)
        {
            _line = Console.ReadLine().Split(Separator);
            _pos = 0;
        }

        return _line[_pos++];
    }

    public int NextInt()
    {
        return int.Parse(Next());
    }

    public long NextLong()
    {
        return long.Parse(Next());
    }

    public double NextDouble()
    {
        return double.Parse(Next());
    }

    #endregion

    #region 型変換

    private int[] ToIntArray(string[] array)
    {
        var result = new int[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = int.Parse(array[i]);
        }

        return result;
    }

    private long[] ToLongArray(string[] array)
    {
        var result = new long[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = long.Parse(array[i]);
        }

        return result;
    }

    private double[] ToDoubleArray(string[] array)
    {
        var result = new double[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = double.Parse(array[i]);
        }

        return result;
    }

    #endregion

    #region 配列取得

    public string[] Array()
    {
        if (_pos >= _line.Length)
            _line = Console.ReadLine().Split(Separator);

        _pos = _line.Length;
        return _line;
    }

    public int[] IntArray()
    {
        return ToIntArray(Array());
    }

    public long[] LongArray()
    {
        return ToLongArray(Array());
    }

    public double[] DoubleArray()
    {
        return ToDoubleArray(Array());
    }

    #endregion
}

Measured memory_bytes: 13524
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define mp make_pair
#define inf 1000000007
#define int long long
using namespace std;
int dis[114][114];
signed main(){
	int n,m;
	cin>>n>>m;
	vector<int> a,b,c;
	for(int i=0;i<m;i++){
		int tx,ty,tc;
		cin>>tx>>ty>>tc;
		a.pb(tx-1);b.pb(ty-1);c.pb(tc);
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			dis[i][j]=inf;
			if(i==j)dis[i][j]=0;
		}
	}
	for(int i=0;i<m;i++){
		dis[a[i]][b[i]]=c[i];
		dis[b[i]][a[i]]=c[i];
	}
	for(int k=0;k<n;k++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if( dis[i][j] > dis[i][k] + dis[k][j])dis[i][j] = dis[i][k] + dis[k][j];
			}
		}
	}
	int cnt=0;
	for(int i=0;i<m;i++){
		int fl = 0;
		for(int j=0;j<n;j++){
			for(int k=0;k<n;k++){
				if(dis[j][k] == dis[j][a[i]]+dis[b[i]][k]+c[i])fl=1;
			}
		}
		if(fl==0)cnt++;
	}
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 384
fun main(args: Array<String>) {
    val (n, a, b) = readLine()!!.split(" ").map(String::toInt)

    var sum = 0
    for (n in 1..n) {
        if (digitSum(n) in a..b) {
            sum += n
        }
    }
    println(sum)
}

fun digitSum(n: Int): Int = n.toString().split("").filter(String::isNotEmpty).map(String::toInt).sum()


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

int main()
{
  int n, m;
  cin >> n >> m;
  vector<int> data(2 * m);
  int i;
  for(i = 0; i < 2*m; i++)
  {
    cin >> data.at(i);
  }
  vector<int> ans(n);
  for(i = 0; i < 2*m; i++)
  {
    ans.at(data.at(i)-1)++;
  }
  for(i = 0; i < n; i++)
  {
    cout << ans.at(i) << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
const ll mod=998244353;
ll dp[3005];
int main(){
  ll n,s;
  cin>>n>>s;
  vector<ll> a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  ll ans=0;dp[0]=1;
  for(int i=0;i<n;i++){
      for(int j=s;j>=0;j--){
        if(j+a[i]<=s)(dp[j+a[i]]+=dp[j])%=mod;
        (dp[j]*=2)%=mod;
      }
  }
  cout<<dp[s]<<"\n";
}


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

int h,w;
char grid[10][10];
bool ok;
bool seen[10][10];

void dfs(int y, int x){
  if(y==h-1 && x==w-1){
    ok=1;
  }
  if(grid[y][x]!='#')return;
  if(grid[y+1][x]=='#' && grid[y][x+1]=='#')return;
  seen[y][x]=1;
  dfs(y+1,x);
  dfs(y,x+1);
  return;
}

int main(){
  cin>>h>>w;
  rep(i,h)rep(j,w){
    cin>>grid[i][j];
    seen[i][j]=0;
  }
  ok=0;
  dfs(0,0);
  if(ok){
    bool all=1;
    rep(i,h)rep(j,w){
      if(grid[i][j]=='#'){
        if(seen[i][j]==0) all=0;
      }
    }
    if(all)cout<<"Possible"<<endl;
    else cout<<"Impossible"<<endl;
  } 
  else cout<<"Impossible"<<endl;
}



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

using namespace std;

//make some global variables that are shared with main() and other functions. 
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int h,w;

int bfs(int x, int y, string *s){
    //make an array showing the distance from the start point (x,y)
    int dist[h][w];
    for(int i=0; i<h;i++){
        for(int j=0; j<w; j++)
            dist[i][j]=-1; //unchecked flag
    }
    
    queue <pair <int, int>> q;
    
    //starting initialization
    q.push({x,y});
    dist[x][y]=0;
    
    //bfs
    while(!q.empty()){
        pair<int, int> z = q.front();
        int u=z.first;
        int v=z.second;
        
        //delete the front
        q.pop();
        
        for(int i=0; i<4; i++){
            int next_x = u + dx[i];
            int next_y = v + dy[i];
            
            //check whether the next index is available or not
            if(0 <= next_x && next_x < h && 0 <= next_y && next_y < w){
                //check whether the content is new and sth to consider or not
                if(s[next_x][next_y]=='.' && dist[next_x][next_y]==-1){
                    dist[next_x][next_y] = dist[u][v] + 1;
                    q.push({next_x, next_y});
                }
            
            }

        }

    }
    
    //return the maximum distance
    int maxi=0;
    for(int i=0; i<h;i++){
        for(int j=0; j<w; j++)
            maxi = max(maxi, dist[i][j]);
    }
    
    return maxi;
    
}


int main()
{
    string str;
    cin >> h >> w;

    string s[h];
    string dist[h];
    int ans=0;
    
    //inputs
    //this array is fixed, i.e, showing the information of the input array
    for(int i=0; i<h;i++){
        cin >> str;
        s[i]=str;
    }
    
    //do search
    for(int i=0; i<h;i++){
        for(int j=0; j<w; j++){
            if(s[i][j]=='.')
                ans = max(ans, bfs(i,j,s));
        }
    }

    cout << ans <<  endl;
}

// GCC reference:
//   https://gcc.gnu.org/

// C++ language references:
//   https://cppreference.com/
//   https://isocpp.org/
//   http://www.open-std.org/jtc1/sc22/wg21/

// Boost libraries references:
//   https://www.boost.org/doc/


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <functional>
#include <tuple>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <utility>
#include <memory>
#include <valarray>

using namespace std;

using ll = long long int;
#define loop(i, N) for (int i = 0; i < N; ++i)
#define scanInt(x) int x; scanf("%d", &x); getchar();
#define scanLLInt(x) ll x; scanf("%lld", &x); getchar();
#define scanVecInt(A, N) vector<int> A(N); loop(i, N){scanf("%d", &(A[i])); getchar();}
#define scanVecLLInt(A, N) vector<ll> A(N); loop(i, N){scanf("%lld", &(A[i])); getchar();}

int main()
{
    scanInt(N);
    scanVecInt(A, N * 3);
    sort(A.begin(), A.end(), greater<int>());
    ll sum = 0;
    loop(i, N){
        sum += A[i * 2 + 1];
    }
    printf("%lld\n", sum);
}


Measured memory_bytes: 1408
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#define ll long long
#define mp(a,b) make_pair(a,b)
#define si(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
using namespace std;

int main(){
  ll arr[3] = {1,6,9};
  std::vector<ll> v6,v9;
  ll main = 6;
  while(true){
    v6.push_back(main);
    main*=6;
    if(main>1e5)
      break;
  }
  main = 9;
  while(true){
    v9.push_back(main);
    main*=9;
    if(main>1e5)
      break;
  }
  ll n;
  cin >> n;
  ll dp[n+10];
  for(ll i=0;i<n+1;i++){
    dp[i]=1e6;
  }
  dp[0]=0;
  for(ll i=1;i<=n;i++){
    dp[i] = min(dp[i], dp[i-1]+1);
    for(ll j=0;j<v6.size();j++){
      if(i-v6[j]>=0){
        dp[i] = min(dp[i], dp[i-v6[j]]+1);
      }
      else{
        break;
      }
    }
    for(ll j=0;j<v9.size();j++){
      if(i-v9[j]>=0){
        dp[i] = min(dp[i], dp[i-v9[j]]+1);
      }
      else{
        break;
      }
    }
  }
  cout << dp[n] << endl;
}


Measured memory_bytes: 1024
import java.util.*;
import java.lang.Math.*;
public class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int hund=n/500;
		n=n%500;
		int t=n/5;
		int ans=hund*1000+t*5;
		System.out.println(ans);
	}
}

Measured memory_bytes: 23764
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<cctype>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
 
#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lf else if
 
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
 
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> Vi;
 
int IN(){
	int c,f,x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}
 
const int N=200000+19;
const int oo=(1<<30)-1;
 
pii A[2*N];
int vis[N];
int n,x,y,c,mnx=oo,mxx=-oo,mny=oo,mxy=-oo,tmp;
ll ans;
 
int main(){
	n=IN();
	For(i,1,n+1){
		x=IN(),y=IN();
		if (x>y) swap(x,y);
		A[++c]=mp(x,i);
		A[++c]=mp(y,i);
		mnx=min(mnx,x);
		mxx=max(mxx,x);
		mny=min(mny,y);
		mxy=max(mxy,y);
	}
	ans=1ll*(mxx-mnx)*(mxy-mny);
	sort(A+1,A+c+1);
	for (int i=1,j=0;i<=c;i++){
		while (j+1<=c&&tmp!=n){
			if (++vis[A[++j].se]==1) tmp++;
		}
		if (tmp==n){
			ans=min(ans,1ll*(mxy-mnx)*(A[j].fi-A[i].fi));
		}
		if (--vis[A[i].se]==0) tmp--;
	}
	cout<<ans<<endl;
}

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

int main() {
	int N, M;
	cin >> N >> M;
	priority_queue<pair<int, int>> q;

	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;
		q.push(make_pair(a, 1));
	}

	for (int i = 0; i < M; i++) {
		int b, c;
		cin >> b >> c;
		q.push(make_pair(c, b));
	}

	long long ans = 0;

	for (int i = 0; i < N; i++)
	{
		pair<int, int> p = q.top();
		q.pop();
		ans += p.first;
		if (p.second > 1)
		{
			p.second--;
			q.push(p);
		}
	}

	cout << ans << endl;
	return 0;
}


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

struct dice {
	int eye[6];
	char order[101];
};

void rightroll(struct dice *a){
	char s = a->eye[0];
	a->eye[0] = a->eye[3];
	a->eye[3] = a->eye[5];
	a->eye[5] = a->eye[2];
	a->eye[2] = s;
}
void beyoroll(struct dice *a){
	char s = a->eye[0];
	a->eye[0] = a->eye[1];
	a->eye[1] = a->eye[5];
	a->eye[5] = a->eye[4];
	a->eye[4] = s;
}
void thisroll(struct dice *a){
	char s = a->eye[0];
	a->eye[0] = a->eye[4];
	a->eye[4] = a->eye[5];
	a->eye[5] = a->eye[1];
	a->eye[1] = s;
}
void leftroll(struct dice *a){
	char s = a->eye[0];
	a->eye[0] = a->eye[2];
	a->eye[2] = a->eye[5];
	a->eye[5] = a->eye[3];
	a->eye[3] = s;
}

void roll(struct dice *a){
	int i,t=strlen(a->order);
	for (i = 0; i < t; i++){
		switch (a->order[i]){
		case 'E':
			rightroll(a);
			break;
		case 'N':
			beyoroll(a);
			break;
		case 'W':
			leftroll(a);
			break;
		case 'S':
			thisroll(a);
			break;
		}
	}
}

int main(void){
	struct dice a;
	int i = 0;
	for (; i < 6; i++){
		scanf("%d", &a.eye[i]);
	}
	scanf("%s", a.order);

	roll(&a);
	printf("%d\n", a.eye[0]);


	return 0;
}


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

int main(void){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int a, b;
    cin>>a>>b;
    cout<<max(a-2*b, 0);
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
	bool exists_ball[3] = {true, false, false};
	char cup1, cup2;
	char dummy;
	
	while ( cin >> cup1 >> dummy >> cup2 ) {
		int iCup1 = cup1 - 'A';
		int iCup2 = cup2 - 'A';
		if (exists_ball[iCup1] != exists_ball[iCup2]) {
			exists_ball[iCup1] = !exists_ball[iCup1];
			exists_ball[iCup2] = !exists_ball[iCup2];
		}
	}
	
	for (int i=0; i<3; i++) {
		if (exists_ball[i]) cout << static_cast<char>(i+'A') << endl;
	}
	
	return 0;
}

Measured memory_bytes: 2992
def chmax(a, b):
  if a > b:
    return a
  else:
    return b
n = int(input())
h = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*3 for _ in range(n)]
dp[0] = h[0]
for i in range(n-1):
  for j in range(3):
    for k in range(3):
      if j == k:
        continue
      else:
        dp[i+1][j] = chmax(dp[i+1][j], dp[i][k] + h[i+1][j]) 
      
print(max(dp[n-1]))

Measured memory_bytes: 74840
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int n = sc.nextInt();
            if (n == 0) {
                break;
            }
            int[][] l = new int[n][n];
            int nx = n / 2;
            int ny = n / 2 + 1;
            l[ny][nx] = 1;
            for (int i = 2; i <= n * n; i++) {
                nx++;
                ny++;
                if (ny >= n) {
                    if (nx >= n) {
                        nx--;
                    }
                    for (int j = 0; j < n; j++) {
                        if (l[j][nx] == 0) {
                            l[j][nx] = i;
                            ny = j;
                            break;
                        }
                    }
                    continue;
                }
                if (nx >= n) {
                    for (int j = 0; j < n; j++) {
                        if (l[ny][j] == 0) {
                            l[ny][j] = i;
                            nx = j;
                            break;
                        }
                    }
                    continue;
                }
                if (l[ny][nx] != 0) {
                    nx--;
                    ny=++ny>=n?0:ny;
                }
                l[ny][nx] = i;
            }
            p(l);
        }
    }

    static void p(int[][] l) {
        for (int i = 0; i < l.length; i++) {
            for (int j = 0; j < l[0].length; j++) {
                System.out.printf("%4d", l[i][j]);
            }
            System.out.println();
        }
    }
}


Measured memory_bytes: 28192
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    map<int,int> m;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        m[a[i]]++;
    }
    long long int sum=0;
    for(auto i:m)
    {
        long long int x=i.second;
        sum=sum+(x*(x-1))/2;
    }
    for(int i=0;i<n;i++)
    {
        cout<<sum-m[a[i]]+1<<"\n";
    }
 
}

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

using namespace std;

int main()
{
    long long int n,m;
    cin>>n>>m;
    if(n==1&&m==1)
        cout<<0;
    else if(n==1&&m>1)
    cout<<m*(m-1)/2;
    else if(m==1&&n>1)
        cout<<n*(n-1)/2;
    else
        cout<<((n*(n-1))/2)+m*(m-1)/2;

    return 0;
}


Measured memory_bytes: 256
/*Author - Shubham Gupta (@shubham107)*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;      typedef vector<int> vi;
typedef vector<vl> vvl;     typedef vector<vi> vvi;
typedef pair<ll, ll> pll;   typedef pair<int, int> pii;
#define forn(i,n) for(int i=0;i<n;i++)
#define rforn(i,n) for(int i=n-1;i>=0;i--)
#define forne(i,n) for(int i=1;i<=n;i++)
#define forse(i,s,e) for(int i=s;i<e;i++)
#define rforse(i,s,e) for(int i=e-1;i>=s;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define MOD 1000000007
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define fill(a,x) memset(a,x,sizeof a);
#define trav(a,x) for(auto &a:x)
#define INF ll(1e18)
#ifdef SHUBHAM107
#include "../trace.h"
#else
#define trace(args...)
#endif

void solve() {
    ll a;
    string b;
    cin >> a >> b;
    int index = 0;
    forn(i, sz(b)){
        if(b[i] == '.'){
            index = i;
        }
    }
    ll c = stoi(b.substr(0, index));
    ll d = stoi(b.substr(index + 1));
    ll ans =  a * c + (a * d) / 100;
    cout << ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifdef SHUBHAM107
    freopen("inp.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("err.txt", "w", stderr);
#endif
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}


Measured memory_bytes: 3672
S = input()
ans = 0
if S[0] == '0':
    for i, x in enumerate(S):
        if i % 2 == 0 and x == '1':
            ans += 1
        elif i % 2 == 1 and x == '0':
            ans += 1
elif S[0] == '1':
    for i, x in enumerate(S):
        if i % 2 == 0 and x == '0':
            ans += 1
        elif i % 2 == 1 and x == '1':
            ans += 1
print(ans)

Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <algorithm>

int main()
{
	int n;
	std::string s;
	std::cin >> n >> s;
	int max = 0;
	std::string left, right;
	for (int i = 0; i < n - 1; i++)
	{
		int cnt = 0;
		left = s.substr(0, i);
		right = s.substr(i);
		for (char c = 'a'; c <= 'z'; c++)
		{
			if (std::find(left.begin(), left.end(), c) != left.end() &&
				std::find(right.begin(), right.end(), c) != right.end())
			{
				cnt++;
			}
		}
		// std::cout << left << " " << right << " " << cnt << std::endl;
		max = std::max(max, cnt);
	}
	std::cout << max << std::endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
// Begin Header {{{
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i,n) for(ll i=0; i<n; i++)
#define loop(i, j, n) for(ll i=j; i<n; i++)
#define all(x) (x).begin(), (x).end()
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
const long double PI = acos(-1);
// }}} End Header

int main() {
	ll x, a, b;
	cin >> x >> a >> b;
	if(b <= a) cout << "delicious" << endl;
	else if(b <= a+x) cout << "safe" << endl;
	else cout << "dangerous" << endl;
 	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  int A,B,X;cin>>A>>B>>X;
  
  if(A>X){
    cout<<"NO"<<endl;
  }
  else if(A<=X&&A+B>=X){
    cout<<"YES"<<endl;
  }
  else{
    cout<<"NO"<<endl;
  }
}
    

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

int main() {
  int h, w, i, j;
  string s[50], ans[50];
  cin >> h >> w;
  for(i=0; i<h; i++){
    cin >> s[i];
    ans[i] = s[i];
  }
  for(i=0; i<h; i++){
    for(j=0; j<w; j++){
      int num=0;
      if(s[i].at(j) != '#'){
        if(i>0 && j>0 && s[i-1].at(j-1) == '#') num++;      
        if(i>0 && s[i-1].at(j) == '#') num++;
        if(i>0 && j<w-1 && s[i-1].at(j+1) == '#') num++;
        if(j>0 && s[i].at(j-1) == '#') num++;
        if(j<w-1 && s[i].at(j+1) == '#') num++;
        if(i<h-1 && j>0 && s[i+1].at(j-1) == '#') num++;
        if(i<h-1 && s[i+1].at(j) == '#') num++;
        if(i<h-1 && j<w-1 && s[i+1].at(j+1) == '#') num++;
        ans[i].at(j) = to_string(num).at(0);
      }
    }
  }
  
  for(i=0; i<h; i++) cout << ans[i] << endl;  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const ll INF = 1LL << 60;

int main(){
    string s;
    cin >> s;
    int ans=0;
    int n=s.size();
    //偶数
    if(n%2==0){
        rep(i,n/2){
            if(s[i]!=s[n-1-i]) ans++;
        }
    }
    //奇数
    else{
        rep(i,n/2){
            if(s[i]!=s[n-1-i]) ans++;
        }
    }
    cout << ans << endl;
}

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

using ll = long long;
using P = pair<int, int>;

const int INF = 1e9;
const int MOD = 1e9 + 7;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main() {
  // 入力
  int a, b, c;
  cin >> a >> b >> c;

  // 解答
  cout << (a + b >= c ? "Yes" : "No") << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
    int x;
    cin >> x;
    int a,b;
    for(a=-120;a<=120;a++){
        for(b=-120;b<=120;b++){
        ll tmp = pow(a,5)-pow(b,5);
            if(tmp==x){
                cout << a << ' '<<b << endl;
                return 0;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 4028
MOD = 10**9+7
n = int(input())
A = list(map(int, input().split()))
F = [1]*(n+1)
for i in range(n):
  F[i+1] = F[i]*(i+1)%MOD
inv = [1]*n
for i in range(1, n):
  inv[i] = pow(i+1, MOD-2, MOD)
  inv[i] += inv[i-1]
  inv[i] %= MOD
ans = 0
for j in range(n):
  temp = inv[j] + inv[n-1-j] - 1
  temp %= MOD
  ans += A[j]*temp%MOD
  ans %= MOD
ans *= F[n]
ans %= MOD
print(ans)

Measured memory_bytes: 15284
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!$BDs=P;~$K%3%a%s%H%"%&%H(B!!
#ifdef DEBUG_
#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
#define dump(x)  ;
#endif

#define equals(a,b) (fabs((a)-(b)) < EPS)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

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

    template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

template <typename T>
void print_array(const T &ary, int size){
    REP(i,size){
        cout << ary[i] << " ";
    }
    cout << endl;
}

const int mod = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;
const double EPS = (1e-10);
const long double PI = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};

int C[510][510] = {};
int O[510][510] = {};
int N;

void dfs(int x, int y){
    int cost = C[x][y] + O[x][y];
    REP(i,4){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx < 0 or nx >= N or ny < 0 or ny >= N) continue;
        if(C[nx][ny] > cost){
            C[nx][ny] = cost;
            dfs(nx,ny);
        }

    }
}

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(12);
    cin >> N;
    REP(i,N) REP(j,N){
        int d1 = i, d2 = (N-1) - i, d3 = j, d4 = (N-1)-j;
        C[i][j] = min(min(d1,d2),min(d3,d4));
        O[i][j] = 1;
    }

    VI P(N*N);
    REP(i,N*N){
        cin >> P[i];
        P[i]--;
    }
    LL ans = 0;
    REP(i,N*N){
        int x = P[i] / N;
        int y = P[i] % N;
        ans += C[x][y];
        O[x][y] = 0;
        dfs(x,y);
    }
    cout << ans << endl;
}

Measured memory_bytes: 21420
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size1,init=nil,size2=-1) #size2に二次元配列時の最初の要素数、size1に次の配列の大きさ、initに初期値を投げることでその配列を返す
  if size2==-1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

N,Q=get_i
queue=[]
N.times do|i|
    nt=get
    nt[1]=nt[1].to_i
    queue.push(nt)
end
time=0
until queue==[]
    cur=queue.shift
    if cur[1]>Q
      cur[1]-=Q
      queue.push(cur)
      time+=Q
    else
        time+=cur[1]
        puts "#{cur[0]} #{time}"
    end
end


Measured memory_bytes: 13644
import math
import sys

def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()

    
    array_result.append(data.split(" "))

    flg = 1

    try:


        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result


arr_data = getinputdata()

n = int(arr_data[0][0])

arr_result = []

sum01 = 0
for v in range(1, 1 + n):
    
    if int(arr_data[v][0]) % 10 == 0:
        sum01 += int(arr_data[v][0])
        
    else:
        arr_result.append(int(arr_data[v][0]))
        
arr_result.append(sum01)
    
arr_result_desc = sorted(arr_result, reverse=True)    
        
chkflg = True

step = 0

while chkflg:
    
    mysum = 0
    cnt = len(arr_result_desc)-step
    
    if cnt == 0:
        
        break
        
    else:
    
        for i in range(0, cnt):

            mysum += arr_result_desc[i]

        else:

            if mysum % 10 != 0:

                chkflg = False

            else:

                step += 1
        
        
print(mysum)



Measured memory_bytes: 3064
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#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 CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

struct UnionFind {
	vector<int> v;
	UnionFind(int n) : v(n) { for (int i = 0; i < n; i++) v[i] = i; }
	int  find(int x) { return v[x] == x ? x : v[x] = find(v[x]); }
	void unite(int x, int y) { v[find(x)] = find(y); }
};

int main() {
	int n;
	while (cin >> n,n) {
		map<pii, pii> futon;
		REP(i, n) {
			int x1, y1, x2, y2;
			char c;
			cin >> x1 >> y1 >> c;
			x2 = x1;
			y2 = y1;
			if (c == 'x')
				x2++;
			else
				y2++;
			futon[{x1, y1}] = { x2,y2 };
			futon[{x2, y2}] = { x1, y1 };
		}
		string ans = "Yes";
		map<pii, bool> asi;
		auto it = futon.begin();
		while (it != futon.end()) {
			if (asi.find(it->first) == asi.end()) {
				asi[it->first] = true;
				asi[it->second] = false;
				queue<pii> Q;
				Q.push(it->first);
				queue<pii> Q2;
				Q2.push(it->second);
				while (!Q.empty() || !Q2.empty()) {
					while (!Q.empty()) {
						pii q = Q.front();Q.pop();
						REP(i, 4) {
							pii nq;
							nq.first = q.first + dx[i];
							nq.second = q.second + dy[i];
							if (futon.find(nq) != futon.end()) {
								if (asi.find(nq) == asi.end()) {
									asi[nq] = true;
									asi[futon[nq]] = false;
									Q.push(nq);
									Q2.push(futon[nq]);
								}
								else {
									if (asi[q] != asi[nq]&&nq!=futon[q]) {
										ans = "No";
										goto res;
									}
								}
							}
						}
					}
					while (!Q2.empty()) {
						pii q = Q2.front();Q2.pop();
						REP(i, 4) {
							pii nq;
							nq.first = q.first + dx[i];
							nq.second = q.second + dy[i];
							if (futon.find(nq) != futon.end()) {
								if (asi.find(nq) == asi.end()) {
									asi[nq] = false;
									asi[futon[nq]] = true;
									Q2.push(nq);
									Q.push(futon[nq]);
								}
								else {
									if (asi[q] != asi[nq] && nq != futon[q]) {
										ans = "No";
										goto res;
									}
								}
							}
						}
					}
				}
			}
			it++;
		}
	res:
		cout << ans << endl;
	}
}

Measured memory_bytes: 8068
#include <stdio.h>
#include <cmath>
#include <algorithm>

#define NUM 50000

int main(){
	int table[NUM],limit;

	for(int i=0; i < NUM;i++)table[i] = 1;
	table[0] = 0;
	table[1] = 0;

	limit = sqrt(NUM);

	for(int i=2;i<=limit;i++){
		if(table[i] == 1){
			for(int k=2*i;k < NUM; k += i){
				table[k] = 0;
			}
		}
	}

	int n,count;

	while(true){
		scanf("%d",&n);
		if(n == 0)break;

		count = 0;
		for(int i=2; i<= (n+1)/2; i++){
			if(i <= n-i &&  table[i] == 1 && table[n-i] == 1)count++;
		}
		printf("%d\n",count);
	}
	return 0;
}

Measured memory_bytes: 2828
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;

public class Main {

	static PrintWriter out;
	static InputReader ir;

	static void solve() {
		out.println((ir.nextInt()+ir.nextInt())*ir.nextInt()/2);
	}

	public static void main(String[] args) throws Exception {
		ir = new InputReader(System.in);
		out = new PrintWriter(System.out);
		solve();
		out.flush();
	}

	static class InputReader {

		private InputStream in;
		private byte[] buffer = new byte[1024];
		private int curbuf;
		private int lenbuf;

		public InputReader(InputStream in) {
			this.in = in;
			this.curbuf = this.lenbuf = 0;
		}

		public boolean hasNextByte() {
			if (curbuf >= lenbuf) {
				curbuf = 0;
				try {
					lenbuf = in.read(buffer);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (lenbuf <= 0)
					return false;
			}
			return true;
		}

		private int readByte() {
			if (hasNextByte())
				return buffer[curbuf++];
			else
				return -1;
		}

		private boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}

		private void skip() {
			while (hasNextByte() && isSpaceChar(buffer[curbuf]))
				curbuf++;
		}

		public boolean hasNext() {
			skip();
			return hasNextByte();
		}

		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (!isSpaceChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}

		public int nextInt() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}

		public long nextLong() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		public char[][] nextCharMap(int n, int m) {
			char[][] map = new char[n][m];
			for (int i = 0; i < n; i++)
				map[i] = next().toCharArray();
			return map;
		}
	}
}


Measured memory_bytes: 21204
#include <bits/stdc++.h>
using namespace std;
#define fast            ios_base::sync_with_stdio(false)
#define mems(x, y)      memset(x, y, sizeof x)
#define pii             pair < int, int >
#define prec(x)         << fixed << setprecision(x)
#define ll              long long
#define nl              << endl
#define spc             << " "
#define pb              push_back
#define PI              3.14159265358979323846
#define E               2.71828182845904523536
#define toint(x)        atoi(x.c_str())
//int fx[] = {1, -1, 0, 0};
//int fy[] = {0, 0, 1, -1};
const int mod=1e9+7;
const int mxn=1e5+200;
bool fl[10000002];
int n, k;
int arr[mxn];
ll dp[mxn];
ll frog_jump(int i, ll cost)
{
    if(i >= n)  return -1;
    if(dp[i] != -1)     return dp[i] + cost;
    dp[i] = LONG_MAX;
    bool fl = 0;
    for(int j = 1; j <= k; j++) {
        ll c = frog_jump(i + j, abs(arr[i] - arr[i + j]));
        if(c != -1) dp[i] = min(dp[i], c), fl = 1;
    }
    if(!fl) dp[i] = 0;
    return dp[i] + cost;
}
int main()
{
    mems(dp, -1);
    cin >> n >> k;
    for(int i = 0; i < n; i++)  cin >> arr[i];
    cout << frog_jump(0, 0) nl;
    return 0;
}




Measured memory_bytes: 6144
N = int(input())
m2 = []

if N == 0:
    print(0)
    
while N != 0:
    if N % -2 != 0:
        m2.append('1')
        N = N // -2 + 1
    else:
        m2.append('0')
        N = N // -2

m2.reverse()

print("".join(map(str, m2)))

Measured memory_bytes: 3064
/*
Author: Racer5x
 ***************************************   UNAUTHORISED COPYING OF CODE PROHIBITED   **********************************
*/
#include <bits/stdc++.h>

#define int         long long
#define double      long double
#define pb          push_back
#define pf          push_front
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        998244353 
#define PI          3.141592653589
using namespace std;

int gcd(int a, int b) {if (a == 0)  return b; return gcd(b % a, a);}  
bool mod(double a,double b) {return a/b - floor(a/b);}
bool f(int a,int b) {return a<b?0:1;}

signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int n,x;
    cin>>n>>x;
    string s;
    cin>>s;

    s[x-1] = s[x-1]+('a'-'A');
    cout<<s;
}

Measured memory_bytes: 256