akhauriyash/Code-Regression huggingface dataset:
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <cmath>
using namespace std;

int main()
{   long long n,i,j,k;
    cin>>n>>k;
    long long h[n],cost[n];
    for(i=0;i<n;i++){cin>>h[i];}
    cost[0]=0;
    cost[1]=abs(h[1]-h[0]);
    for(i=2;i<n;i++){
        cost[i]=1000000007;
        for(j=1;j<=k;j++){
            if(i-j>=0){cost[i]=min(cost[i],cost[i-j]+abs(h[i]-h[i-j]));}
        }
    }
    cout<<cost[n-1];

    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}
using int64 = long long;

int N, Q;
struct LazySegmentTree {
private:
    int n;
    vector<int64> node, lazy;

public:
    LazySegmentTree(vector<int64> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 0);

        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
    }

    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2*k+1] += lazy[k] / 2;
                lazy[2*k+2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }

    void add(int a, int b, int64 x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else {
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }

    int64 getsum(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        int64 vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        int64 vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }
};


int main() {
    int64 n,d,a;
    int64 ans = 0;
    cin >> n >> d >> a;
    vector<pair<int64,int64>> xh;
    vector<int64> x(n);
    vector<int64> h(n+1,0);

    for (int64 i=0; i<n; i++) {
        cin >> x[i] >> h[i];
        xh.emplace_back(x[i], h[i]);
    }

    sort(xh.begin(), xh.end());

    for (int i=0; i<n; i++) {
        x[i] = xh[i].first;
        h[i] = xh[i].second;
    }
    LazySegmentTree seg(h);




    for (int64 i=0; i<n; i++) {
//        for (int64 j=0; j<n; j++) cout << seg.getsum(j,j+1) << " "; cout<<endl;

        h[i] = seg.getsum(i,i+1);
        if (h[i] <= 0) continue;
        int64 r = x[i] + 2*d;

        auto it = upper_bound(x.begin(), x.end(), r);
        it--;
        int64 index = it - x.begin();

        int64 nboms = (h[i] + a - 1) / a;
        ans += nboms;
        seg.add(i,index+1, -(nboms * a));
    }

    cout << ans << endl;
}

Measured memory_bytes: 17132
#include<stdio.h>
int main(){
	int ans,list[10001][2],num[501],n,k,i,j;
	while(1){
		scanf("%d%d",&n,&k);
		if(n==0 && k==0)break;
		for(i=0;i<n;i++)num[i]=0;
		for(i=0;i<k;i++){
			scanf("%d%d",&list[i][0],&list[i][1]);
			if(list[i][0]==1)num[list[i][1]-1]=1;
		}
		for(i=0;i<n;i++){
			if(num[i]==1){
				for(j=1;j<k;j++){
					if(num[list[j][0]-1]==1 && num[list[j][1]-1]==0)num[list[j][1]-1]=2;
					if(num[list[j][1]-1]==1 && num[list[j][0]-1]==0)num[list[j][0]-1]=2;
				}
			}
		}
		num[0]=0;
		ans=0;
		for(i=0;i<n;i++){
			if(num[i]!=0)++ans;
		}
		printf("%d\n",ans);
	}
	return 0;
}


Measured memory_bytes: 1992
#include<stdio.h>
#include<string.h>
int main(void)
{
	char x[27]="abcdefghijklmnopqrstuvwxyz",s[100001];
	int y[26],i,k,a;
	for(i-0;i<26;i++)  y[i]=0;
	scanf("%s",s);
	a=strlen(s);
	for(i=0;i<a;i++){
		for(k=0;k<26;k++){
			if(s[i]==x[k]){
				y[k]++;
				break;
			}
		}
	}
	a=1;
	for(i=0;i<26;i++){
		if(y[i]==0){
			a=0;
			break;
		}
	}
	if(a==1)  printf("None\n");
	if(a==0)  printf("%c\n",x[i]);
	return 0;
}

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

int main() {
	string res;
	int cnt = 0;

	cin >> res;

	for (int i = 0; i <= 2; i++) {
		if (res[i] == '1') {
			cnt++;
		}
	}

	cout << cnt << "\n";

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <math.h>

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define repP(i, a, b) for(int i = a; i < b; i++)
#define repM(i, a, b) for(int i = a - 1; i >= b; i--)

using namespace std;

int main()
{
  int a = 0 , b = 0, c = 0, d = 0, e = 0, f = 0, i = 0, j = 0;
  int sum = 0, num = 0, count = 0, ans = 0, min = 0, max = 0;
  double d1 = 0, d2 = 0, d3 = 0, d4 = 0, d5 = 0, d6 = 0;
  int a1[999999], a2[999999], a3[999999];
  //char s1[200000], s2[200000], s3[200000];
  string s1, s2, s3;
  
  cin >>a>> s1 >> s2;
  for(i = 0; i < a * 2; i++){
    if(i % 2 == 0){
      s3 += s1[i / 2];
    }else{
      s3 += s2[i / 2];
    }
  }
  cout << s3 << endl;
}
  


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef int ll;
typedef long double ld;
const ll N = 200005;
char en = '\n';
ll inf = 1e16;
ll mod = 1e9 + 7;
ll power(ll x, ll n, ll mod) {
  ll res = 1;
  x %= mod;
  while (n) {
    if (n & 1)
      res = (res * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return res;
}
bool comp(pair<ll, ll> &a, pair<ll, ll> &b) { return a.second < b.second; }
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll n;
  cin >> n;

  ll X[n + 5], L[n + 5];
  map<ll, ll> par;
  vector<pair<ll, ll>> arr;
  for (ll i = 1; i <= n; i++) {
    cin >> X[i] >> L[i];
    arr.push_back({X[i] - L[i], X[i] + L[i]});
  }

  sort(arr.begin(), arr.end(), comp);

  ll left1 = -inf;
  ll res = 0;
  for (pair<ll, ll> &x : arr) {
    if (x.first < left1)
      continue;

    res++;
    left1 = x.second;
  }
  cout << res << en;

  return 0;
}

Measured memory_bytes: 3568
#include <set>
#include <queue>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define debug(x) cerr<<#x<<'='<<x<<endl
#define set0(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
template<typename T> void read(T &x){
	x = 0;char ch = getchar();ll f = 1;
	while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
	while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}

int mod = 998244353;
inline int mul(int x,int y){return 1ll*x*y%mod;}
int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int sub(int x,int y){return x-y<0?x-y+mod:x-y;}
int sq(int x){return 1ll*x*x%mod;}
int pow(int a,int b){return b == 0 ? 1 : ( b&1 ? mul(a,sq(pow(a,b/2))) : sq(pow(a,b/2)));}


int n;
int dp[5050] = {0};
void upd(int i){
	for(int j=i;j<=n;j++){
		dp[j] = add(dp[j],dp[j-i]);
	}
}
int main() {
	read(n);read(mod);
	dp[0] = 1;
	if(n%2 == 1){
		int k = (n-1)/2;
		for(int i=1;i<=k+1;i++)upd(i);
		for(int i=k;i>=2;i--)upd(i);
	}else{
		int k = n/2;
		for(int i=1;i<=k;i++)upd(i);
		for(int i=k;i>=2;i--)upd(i);
	}
	int ans = 0;
	for(int i=0;i<=n;i++){
		ans = add(ans,mul(dp[i],n-i));
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define per(i, a, b) for (int i = a; i >= b; i--)
#define ll long long
#define mset(s, _) memset(s, _, sizeof s)
#define ALL(a) (a).begin(), (a).end()
using namespace std;

int main(void) {
  int N, M;
  cin >> N >> M;
  vector<int> s[M + 3];
  vector<int> p;

  rep(m, 1, M) {
    int K;
    cin >> K;
    rep(k, 1, K) {
      int S;
      cin >> S;
      S--;
      s[m - 1].push_back(S);
    }
  }

  rep(i, 1, M) {
    int P;
    cin >> P;
    p.push_back(P);
  }

  int ans = 0;

  rep(bit, 1, (1 << N)) {
    vector<bool> Sw;
    rep(i, 0, N - 1) {
      if (bit & (1 << i)) {
        // スイッチi on
        // cout << 1;
        Sw.push_back(1);
      } else {
        // cout << 0;
        Sw.push_back(0);
        // スイッチi off
      }
    }
    // cout << endl;

    bool mark = true;

    rep(m, 0, M - 1) {
      int on_sw_cnt = 0;
      for (auto si : s[m]) {
        if (Sw[si]) {
          on_sw_cnt++;
        }
      }

      // cout << m << ":" << on_sw_cnt << endl;

      if (on_sw_cnt % 2 != p[m]) {
        mark = false;
      }
    }

    // cout << "mark: " << mark << endl;

    if (mark) {
      ans++;
    }
  }

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


Measured memory_bytes: 3652
import sys
sys.setrecursionlimit(10**6)
n = int(input())
edge = [[] for _ in range(n)]

for i in range(n-1):
    a,b,c=map(int, input().split())
    edge[a-1].append([b-1,c])
    edge[b-1].append([a-1,c])
#任意の点から行ける偶数の距離で行けるところを同じ色で塗る。
col = [-1]*n
visited = [0]*n

def dfs(i,c):
    visited[i]=1
    col[i] = c
    for j in edge[i]:
        if not visited[j[0]]:
            if j[1]%2==0:
                dfs(j[0],c)
            else:
                dfs(j[0],-1*c)


def main():
    dfs(0,1)
    for i in range(n):
        print(max(col[i],0))



if __name__ == '__main__':
    main()


Measured memory_bytes: 85972
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<string,int> P;
const ll MOD=1e9+7;
vector<ll> temoti;
ll v[50];
int main()
{
	int n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++)
		cin>>v[i];
	ll ans=0;
	for(int l=-1;l<n;l++)
	{
		for(int r=n;r>l;r--)
		{
			//取り出す回数
			int cnt=l+1+n-r;
			if(cnt>k)
				break;
			//取り出される宝石
			temoti.clear();
			for(int i=0;i<=l;i++)
				temoti.push_back(v[i]);
			for(int i=n-1;i>=r;i--)
				temoti.push_back(v[i]);
			ll tmp=0;
			sort(temoti.begin(),temoti.end());
			for(int i=0;i<temoti.size();i++)
			{
				if(cnt==k || temoti[i]>=0)
				{
					while(i<temoti.size())
					{
						tmp+=temoti[i];
						i++;
					}
				}
				cnt++;
			}
			ans=max(tmp,ans);
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
	public static void main(String[] args){
		FastScanner sc = new FastScanner(System.in);
		int n = sc.nextInt();
		int d = sc.nextInt();

		int list[][] = new int[n][d];
		for (int i=0;i<n;i++) {
			for (int j=0;j<d;j++) {
				list[i][j] = sc.nextInt();
			}
		}
		int count = 0;
		for (int i=0;i<n-1;i++) {
			for (int j=i+1;j<n;j++) {
				double dis = 0;
				for (int k=0;k<d;k++) {
					double p =(int) Math.pow(list[i][k]-list[j][k], 2);
					dis += p;
				}
				if (Math.sqrt(dis) == (int)Math.sqrt(dis)) {
					count++;
				}
			}
		}


		System.out.println(count);



	}

}

class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }

    public String next() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        return tokenizer.nextToken("\n");
    }

    public long nextLong() {
        return Long.parseLong(next());
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    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;
    }
}

Measured memory_bytes: 20692
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

int main(){
    int n; cin >> n;
    set<int> se;
    for(int i=0; i<n; i++){
        int a; cin >> a;
        se.insert(a);
    }

    cout << se.size() << endl;
}

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

using ll = int64_t;
#define int ll

#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, b) FOR(i, 0, b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(), x.end()

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

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

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

ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}

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

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

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

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

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

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

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

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

const int mod = 1e9 + 7;

signed main() {
  int n = read();
  vi a;
  REP(i, n) a.PB(read());
  bool o = 1;
  vi b(n);
  int r = n - 1, l = 0;
  for (int i = n - 1; i >= 0; i--) {
    if (o)
      b[l++] = a[i];
    else
      b[r--] = a[i];
    o ^= 1;
  }
  REP(i, n) print(b[i], 2);
}


Measured memory_bytes: 5488
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;

ll t[3][33];
ll co[30][30];
int fi[510][510];


int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n,c; cin >> n >> c;
	for(int i=0;i<c;i++){
		for(int j=0;j<c;j++){
			cin >> co[i][j];
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin >> fi[i][j];
			fi[i][j]--;
			t[(i+j)%3][fi[i][j]]++;
		}
	}
	ll ans=1e18;
	for(int i=0;i<c;i++){
		for(int j=0;j<c;j++){
			for(int k=0;k<c;k++){
				if(i==j||j==k||k==i)continue;
				ll res=0;
				for(int l=0;l<c;l++){
					if(i!=l){
						res+=t[0][l]*co[l][i];
					}
					if(j!=l){
						res+=t[1][l]*co[l][j];
					}
					if(k!=l){
						res+=t[2][l]*co[l][k];
					}
				}
				ans=min(res,ans);
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define int long
#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define IOS cin.tie(0); ios::sync_with_stdio(false)
const int INF = 1e9;
using namespace std;

main() {
    int N; cin >> N;
    map<int,int> m;
    rep(i,N){
        int a; cin >> a;
        m[a]++;
    }
    vector<int> v;
    for(auto p:m){
        if(p.second>=2) v.push_back(p.first);
        if(p.second>=4) v.push_back(p.first);
    }
    if(v.size()<2) {cout << 0 << endl; return 0;}
    sort(v.begin(),v.end(),greater<int>());
    cout << v[0]*v[1] << endl;
}


Measured memory_bytes: 6528
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      	int a = sc.nextInt();
      	int b = sc.nextInt();
      	if(a <= b) System.out.println(a);
      	else System.out.println(a-1);
    }
}

Measured memory_bytes: 35584
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REPR(i,n) for (int i=(int)(n)-1;i>=0;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
#define tpl(...) make_tuple(__VA_ARGS__)
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1);
const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};
typedef long long ll;
typedef pair<int,int> pii;
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 Ch,typename Tr,typename C,typename=decltype(begin(C()))>basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>&os,
const C& c){os<<'[';for(auto i=begin(c);i!=end(c);++i)os<<(i==begin(c)?"":" ")<<*i;return os<<']';}
template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';}
template<int N,class Tp>void output(ostream&,const Tp&){}
template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);}
template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';}
template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20];
int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);}
template<class T>void outputs(T t){output(t);}
template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);}
template<class T>void output(T *a,int n){REP(i,n)cout<<a[i]<<(i!=n-1?',':'\n');}
template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);}
template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;);
if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;}
template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);}
template<class T>bool inputs(T *a, int n) { REP(i,n) if(!input(a[i])) return 0; return 1;}

int v[1000];

int main() {
  int n;
  while(cin>>n) {
    inputs(v,n);
    sort(v,v+n);
    double ans = v[0];
    for (int i=1; i<n; i++) {
      ans = (ans + v[i]) / 2;
    }
    printf("%.10f\n", ans);
  }
}


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

int main()
{
    int N;
    cin >> N;
    if (N == 0)
    {
        cout << "0" << endl;
        return 0;
    }

    int count = 0;
    queue<int> fact;
    bool is_positive = (N > 0);
    while (N != 0)
    {
        if (N % 2 != 0)
        {
            fact.push(count);
            if (N > 0)
            {
                N--;
            }
            else
            {
                N++;
            }
        }
        N /= 2;
        count++;
    }

    int a[32] = {};
    for (int i = 0; i < 32; i++)
    {
        if (i == fact.front())
        {
            a[i]++;
            if (is_positive)
            {
                if (i % 2 != 0)
                {
                    a[i + 1]++;
                }
            }
            else
            {
                if (i % 2 == 0)
                {
                    a[i + 1]++;
                }
            }
            fact.pop();
        }
        while (a[i] > 1)
        {
            a[i + 1]++;
            a[i + 2]++;
            a[i] -= 2;
        }
    }

    queue<int> printqueue;
    string ans;
    for (int i = 0; i < 32; i++)
    {
        printqueue.push(a[i]);
        if (a[i] == 1)
        {
            while (printqueue.size() > 0)
            {
                ans += to_string(printqueue.front());
                printqueue.pop();
            }
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
//increase stack size
#pragma comment(linker, "/STACK:16777216")

ll mxm() {return LLONG_MIN;}
template<typename... Args>
ll mxm(ll a, Args... args) { return max(a,mxm(args...)); }

ll mnm() {return LLONG_MAX;}
template<typename... Args>
ll mnm(ll a, Args... args) { return min(a,mnm(args...)); }

template<class T> ostream& operator<<(ostream& os,vector<T> V){
	os<<"[ ";for(auto v:V)os<<v<<" ";return os<<"]";
}
template<class L,class R> ostream& operator<<(ostream& os,pair<L,R> P){
	return os<<"("<<P.first<<","<<P.second<<")";
}

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__,__VA_ARGS__)
template<typename Arg1>
void __f(const char* name,Arg1&& arg1){
	cout<<name<<" : "<<arg1<<endl;
}
template <typename Arg1,typename... Args>
void __f(const char* names,Arg1&& arg1,Args&&... args){
	const char* comma=strchr(names+1,',');cout.write(names,comma-names)<<" : "<<arg1<<" | ";__f(comma+1,args...);
}
#else
#define trace(...) 1
#endif

#define ld long double
#define pll pair<ll,ll>
#define ii pair<int,int>
#define vll vector<ll>
#define vii vector<ii>
#define vi vector<int>
#define vpll vector<pll>
#define vld vector<ld>
#define vvld vector<vld>
#define vvi vector<vi>
#define vvll vector<vll>
#define vvpll vector<vpll>
#define vvii vector<vii>
#define I insert
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x)	x.begin(),x.end()

const int mod=1e9+7;
// 128 bit: __int128
inline int add(int a,int b){a+=b;if(a>=mod)a-=mod;return a;}
inline int sub(int a,int b){a-=b;if(a<0)a+=mod;return a;}
inline int mul(int a,int b){return (a*1ll*b)%mod;}
inline int power(int a,int b){int rt=1;while(b>0){if(b&1)rt=mul(rt,a);a=mul(a,a);b>>=1;}return rt;}
inline int inv(int a){return power(a,mod-2);}

struct compare{
	bool operator() (const int &a,const int &b) const{
		return a>b;
	}
};

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<setprecision(25);
	int n;
	cin >> n;
	cout << 360 / __gcd(n, 360) << endl;			
}

Measured memory_bytes: 3632
import math
k = int(input())
ans = 0
for i in range(1, k + 1):
    for j in range(i + 1, k + 1):
        for l in range(j + 1, k + 1):
            # print(i, j, l)
            ans += (math.gcd(math.gcd(i, j), l)) * 6

for i in range(1, k + 1):
    for j in range(i + 1, k + 1):
        # print(i, j)
        ans += math.gcd(i, j) * 6

for i in range(1, k + 1):
    # print(i)
    ans += i
print(ans)

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

using namespace std;

#define pb push_back
#define ll long long
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define bug cout << "ok" << endl

const ll INF = 1e9 + 5, N = 2e3 + 5, mod = 1e9 + 7, M = 1e5 + 5;

int dp[N];

int main(){
	ll n;
	cin >> n;
	dp[0] = 1;
	for(ll sum = 3; sum <= n; sum++){
		for(ll last = 3; last <= sum; last++){
			dp[sum] = (dp[sum] + dp[sum - last]) % mod;
		}
	}
	cout << dp[n] << endl;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define REP(i,x,n) for(int i = (x); i < (n); ++i)
#define ll long long
#define P pair<ll,ll>
#define all(v) (v).begin(),(v).end()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1);


struct UnionFind{
    vector<ll> d;
    UnionFind(ll n): d(n,-1) {}
    ll find(ll x){
        if(d[x] < 0) return x;
        return d[x] = find(d[x]);
    }
    bool unite(ll x, ll y){
        x = find(x); y = find(y);
        if(x == y) return false;
        if(d[x] < d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(ll x, ll y) { return find(x) == find(y);}
    ll size(ll x) { return -d[find(x)];}
};


int main(void)
{
    ll n,m,ans=0;
    cin>>n>>m;
    UnionFind uf(n);
    rep(i,m){
        ll a,b;
        cin>>a>>b;
        a--; b--;
        uf.unite(a,b);
    }
    rep(i,n) ans=max(ans, uf.size(i));
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 10996
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE RankNTypes #-}
import qualified Data.ByteString.Lazy.Char8 as B
import Data.Maybe
-- import Data.List
-- import qualified Data.Vector.Unboxed as VU
-- import qualified Data.Vector.Unboxed.Mutable as VUM
-- import Control.Monad
-- import Control.Monad.ST
-- import Debug.Trace
-- trace _ = id

solve :: Int -> String -> String -> String -> Int
solve n a b c = sum (zipWith3 f a b c)
  where
    f x y z | x == y && y == z = 0
            | x == y || y == z || x == z = 1
            | otherwise = 2

readBInt :: B.ByteString -> Int
readBInt = fst . fromJust . B.readInt

tmain :: B.ByteString -> Int
tmain cont =
  let remLines0 = map B.words (B.lines cont)
      [bs_n]:remLines1 = remLines0
      n = readBInt bs_n
      [bs_a]:remLines2 = remLines1
      a = B.unpack bs_a
      [bs_b]:remLines3 = remLines2
      b = B.unpack bs_b
      [bs_c]:remLines4 = remLines3
      c = B.unpack bs_c
  in solve n a b c

outAnswer :: Int -> IO ()
outAnswer = putStrLn . show

main :: IO ()
main = outAnswer . tmain =<< B.getContents


-------------------------------------------------------------------------------

inp1 = "4\nwest\neast\nwait\n"
inp2 = "9\ndifferent\ndifferent\ndifferent\n"
inp3 = "7\nzenkoku\ntouitsu\nprogram\n"
tv1 = tmain $ B.pack inp1
tv2 = tmain $ B.pack inp2
tv3 = tmain $ B.pack inp3
test1 = tv1 == 3
test2 = tv2 == 0
test3 = tv3 == 13
alltest = test1 && test2 && test3



Measured memory_bytes: 508
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
  static Scanner sc = new Scanner(System.in);
  static final long MOD = 1_000_000_007;

  public static void main(String[] args) {
    long N = sc.nextInt();
    long K = sc.nextInt();
    if (N == 1) {
      System.out.println(K);
      return;
    }
    ArrayList<Long> divisor = new ArrayList<>();
    for (long i = 2; i * i <= N; i++) {
      if (N % i != 0) continue;
      divisor.add(i);
      if (i * i != N) {
        divisor.add(N / i);
      }
    }
    divisor.add(N);
    Collections.sort(divisor);
    HashMap<Long, Long> map = new HashMap<>();
    map.put(1L, K);
    for (long d : divisor) {
      long add = pow(K, (d + 1) / 2) - K;
      for (long i = 2; i * i <= d; i++) {
        if (d % i != 0) continue;
        add += MOD - map.get(i);
        if (i * i != d) add += MOD - map.get(d / i);
      }
      map.put(d, add % MOD);
    }
    long ans = 0;
    for (long k : map.keySet()) {
      ans += (k % 2 == 0 ? k / 2 : k) * map.get(k);
    }
    System.out.println(ans % MOD);
  }

  static long pow(long base, long p) {
    if (p == 0) return 1;
    if (p == 1) return base;
    long ret = pow(base, p / 2);
    ret = ret * ret % MOD;
    if (p % 2 == 1) {
      ret = ret * base % MOD;
    }
    return ret;
  }

}


Measured memory_bytes: 15068
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

//Family Tree
public class Main{

	class V{
		int id;
		String name;
		V parent;
		List<V> adj;
		public V(int id, String name) {
			this.id = id;
			this.name = name;
			parent = null;
			adj = new ArrayList<V>();
		}
		void add(int depth, String name, int id){
			if(depth==0){
				V t = new V(id, name);
				t.parent = this;
				adj.add(t);
				v[id] = t;
			}
			else{
				adj.get(adj.size()-1).add(depth-1, name, id);
			}
		}
		boolean isChild(String s){
			for(V t:adj)if(t.name.equals(s))return true;
			return false;
		}
		boolean isParent(String s){
			if(parent==null)return false;
			return parent.name.equals(s);
		}
		boolean isSibling(String s){
			if(parent==null)return false;
			for(V t:parent.adj)if(t.name.equals(s))return true;
			return false;
		}
		boolean isDesc(String s){
			for(V t:adj){
				if(t.name.equals(s))return true;
				if(t.isDesc(s))return true;
			}
			return false;
		}
		boolean isAnc(String s){
			if(parent==null)return false;
			if(parent.name.equals(s))return true;
			return parent.isAnc(s);
		}
	}
	
	V[] v;
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt();
			int m = sc.nextInt();
			if((n|m)==0)break;
			v = new V[n+1];
			v[0] = new V(0, "");
			sc.nextLine();
			Map<String, Integer> ref = new HashMap<String, Integer>();
			for(int i=1;i<=n;i++){
				String s = sc.nextLine();
				int depth = 0;
				while(s.charAt(depth)==' ')depth++;
				String name = s.substring(depth, s.length());
				v[0].add(depth, name, i);
				ref.put(name, i);
			}
			while(m--!=0){
				String[] s = sc.nextLine().split(" ");
				String a = s[0];
				String cmd = s[3];
				String b = s[5].substring(0, s[5].length()-1);
				boolean f;
				if("child".equals(cmd))f = v[ref.get(b)].isChild(a);
				else if("parent".equals(cmd))f = v[ref.get(b)].isParent(a);
				else if("sibling".equals(cmd))f = v[ref.get(b)].isSibling(a);
				else if("descendant".equals(cmd))f = v[ref.get(b)].isDesc(a);
				else f = v[ref.get(b)].isAnc(a);
				System.out.println(f?"True":"False");
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 0
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

typedef long long ll;

#define rep(i, a, b) for (ll i = a; i < (ll)b; ++i)
#define digit(a) to_string(a).size()
#define INF 10e12
#define MAX 51000
#define all(x) (x).begin(), (x).end()
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))

using namespace std;

const long long MOD = 1e9 + 7;

int main(void)
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll a, v, b, w, t;
    cin >> a >> v >> b >> w >> t;
    string ans = "NO";
    if (b > a)
    {
        if (a + v * t >= b + w * t)
            ans = "YES";
    }
    else
    {
        if (a - v * t <= b - w * t)
            ans = "YES";
    }

    cout << ans << endl;
}


Measured memory_bytes: 3596
h,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]

max_a=max(a for a,_ in ab)
dp = [0] * (h+max_a)

for i in range(0,h+max_a):
    if i==0:
        dp[i]=0
    else:
        dp[i]=min(dp[i-a]+b for a,b in ab)
print(min(dp[h:]))

Measured memory_bytes: 3668
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <string>
#include <utility>
#include <algorithm>
#include <iostream>
#include <functional>
#include <cmath>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999

using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

int main(){
  int N;
  scanf("%d",&N);
  llong L0 = 2;
  llong L1 = 1;
  llong L2 = 3;

  if(N>=2){
    for(int i=2; i<=N; i++){
      L2 = L0 + L1;
      L0 = L1;
      L1 = L2;
    }
  printf("%lld\n",L2);
  }else{
    printf("1\n");
  }


	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
const int MOD = 1e9 + 7;
typedef long long lint;
const int INF = 1e7;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repi(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(), (x).end()
#define pb push_back
template<class Abel> struct UnionFind {
    vector<int> par;
    vector<int> rank;
    vector<Abel> diff_weight;
    UnionFind(int n = 1, Abel SUM_UNITY = 0) {
        init(n, SUM_UNITY);
    }
    void init(int n = 1, Abel SUM_UNITY = 0) {
        par.resize(n); rank.resize(n); diff_weight.resize(n);
        for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
    }
    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            diff_weight[x] += diff_weight[par[x]];
            return par[x] = r;
        }
    }
    Abel weight(int x) {
        root(x);
        return diff_weight[x];
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    bool unite(int x, int y, Abel w) {
        w += weight(x); w -= weight(y);
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y), w = -w;
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        diff_weight[y] = w;
        return true;
    }
    Abel diff(int x, int y) {
        return weight(y) - weight(x);
    }
};
int main()
{
    int n,m;
    cin>>n>>m;
    UnionFind<int> uf(n);
    rep(i,m){
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        if(uf.same(a,b)){
            int diff = uf.diff(a, b);
            if(diff!=c){
                cout << "No" << endl;
                return 0;
            }
        }
        else
        {
            uf.unite(a, b, c);
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 1408
from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools

def j(q):
    if q==1: print("Yes")
    else:print("No")
    exit(0)


def ct(x,y):
    if (x>y):print("")
    elif (x<y): print("")
    else: print("")

def ip():
    return int(input())

def swap(s,pos):
    s[pos]-=1
    s[pos+1]+=1
    print(s)
    if pos == n-2: return s
    if s[pos+2] == 0: swap(s,pos+1)
    return s

pl = 'abcdefghijklmnopqrstuvwxyz'

#n = ip()                              #入力整数1つ
#h,w= (int(i) for i in input().split())      #入力整数横2つ
#n,x,y = (int(i) for i in input().split())    #入力整数横3つ
a,b,c,d= (int(i) for i in input().split())  #入力整数横4つ
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)

#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
e = set([i for i in range(a,b)])
f = set([i for i in range(c,d)])
print(len(e & f))

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

using namespace std;

int main(){
    int N,a=0,w=0,t=0,r=0;
    cin >> N;
    for(int i=0;i<N;i++){
        string s;
        cin >> s;
        if(s[0]=='A'){
            a++;
        }else if(s[0]=='W'){
            w++;
        }else if(s[0]=='T'){
            t++;
        }else{
            r++;
        }
    }

    cout << "AC x " << a << endl;
    cout << "WA x " << w << endl;
    cout << "TLE x " << t << endl;
    cout << "RE x " << r << endl;
}

Measured memory_bytes: 3632
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

int main() {
  string s;
  ll k;
  cin >> s >> k;
  for (int i = 0; i < min((ll)s.size(), k); i++) {
    if (s[i] >= '2') {
      cout << s[i] << endl;
      return 0;
    }
  }
  cout << '1' << endl;
  return 0;
}


Measured memory_bytes: 256
/**
* Copyright(c)
* Author : tiketiskte
* Date : 2020-04-26-21.03.53
*/
#include <bits/stdc++.h>
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
using namespace std;
int S, W;
int main()
{
    IOS
    cin >> S >> W;
    if(S > W) {
        puts("safe");
    } else {
        puts("unsafe");
    }
    return 0;
}


Measured memory_bytes: 3652
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

struct Cake {
  int a, b, c;
  ll score;

  bool operator<(const Cake& rhs) const {
    if (score != rhs.score) return score < rhs.score;
    if (a != rhs.a) return a < rhs.a;
    if (b != rhs.b) return b < rhs.b;
    return c < rhs.c;
  }
};

int main() {
#ifdef DEBUG
  ifstream cin("in.txt");
#endif
  int X, Y, Z, K;
  while (cin >> X >> Y >> Z >> K) {
    vector<ll> A(X), B(Y), C(Z);
    for (int i = 0; i < X; i++) cin >> A[i];
    for (int i = 0; i < Y; i++) cin >> B[i];
    for (int i = 0; i < Z; i++) cin >> C[i];
    sort(A.rbegin(), A.rend());
    sort(B.rbegin(), B.rend());
    sort(C.rbegin(), C.rend());
    set<Cake> used;
    priority_queue<Cake> pq;
    auto push = [&](int a, int b, int c) {
      if (a < X && b < Y && c < Z) {
        Cake cake = {a, b, c, A[a] + B[b] + C[c]};
        if (!used.count(cake)) {
          pq.push(cake);
          used.insert(cake);
        }
      }
    };
    push(0, 0, 0);
    for (int k = 0; k < K; k++) {
      auto cake = pq.top();
      pq.pop();
      cout << cake.score << endl;
      push(cake.a + 1, cake.b, cake.c);
      push(cake.a, cake.b + 1, cake.c);
      push(cake.a, cake.b, cake.c + 1);
    }
  }
  return 0;
}


Measured memory_bytes: 896
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000009LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define fo(i,j,n) for (int i=(j); i < (n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {    
    double a, b, h, m; cin >> a >> b >> h >> m;
    
    double hour = h * (360.0/ 12) + m * (1.0 / 2);
    double minutes = m * (360.0/ 60);

    double ang = abs(hour - minutes); //度数
    ang = min(ang, (360 - ang)) * M_PI / 180; //度数→ラジアン

    cout << fixed << setprecision(12); 
    double res = sqrt(b * b + a * a - cos(ang) * 2 * b * a);
    cout << res << ln;
}

Measured memory_bytes: 4080
#include<stdio.h>

int main(){
  int a,b,k,i;
  scanf("%d%d%d",&a,&b,&k);
  
  for(i=0;i<k;i++){
    if(i%2==0){
      if(a%2==1) a=a-1;
      b=b+a/2;
      a=a/2;
    }
    else{
      if(b%2==1) b=b-1;
      a=a+b/2;
      b=b/2;
    }
  }
  printf("%d\t%d\n",a,b);
  return 0;
}


Measured memory_bytes: 128
#define INF 10000000000
#define MOD 1000000007

#if 1   // use_templates

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define rep(i, up) for (ll i = 0; i < up; ++i)
#define repp(i, up) for (ll i = 0; i <= up; ++i)
#define rrep(i, lo, up) for (ll i = lo; i < up; ++i)
#define rrepp(i, lo, up) for (ll i = lo; i <= up; ++i)
#define eep(i, lo, up) for ((i) = (lo); (i) < (up); ++(i))
#define eepp(i, lo, up) for ((i) = (lo); (i) <= (up); ++(i))


ll gcd(ll a, ll b);

ll gcd(ll a, ll b)
{
    if (a < b) {
        return gcd(b, a);
    }
    ll r;
    while (r = a % b) {
        a = b;
        b = r;
    }
    return b;
}

#endif  // end of use_templates


int main()
{
    ll n;
    cin >> n;
    map<ll, ll> a;
    rep(i, n) {
        ll aa;
        cin >> aa;
        ++a[aa];
    }
    ll sum = 0;
    for (auto it = a.begin(); it != a.end(); ++it) {
        sum += it->first * it->second;
    }

    ll q;
    cin >> q;
    rep(_, q) {
        ll b, c;
        cin >> b >> c;
        sum += a[b] * (c - b);
        a[c] += a[b];
        a[b] = 0;
        cout << sum << endl;
    }
    return 0;
}


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

using namespace std;
int main()
{
	std::ios::sync_with_stdio(false);
	string str;
	cin>>str;
	int A[27],count=0;
	mem(A,0);
	for(int i=0;str[i]!='\0';i++){
		A[str[i]-65]++;
	}
	for(int i=0;i<26;i++){
		if(A[i]==2){
			count++;
		}
	}
	if(count==2){
		cout<<"Yes";
	}
	else{
		cout<<"No";
	}
	return 0;
}


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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define ALL(name) name.begin(),name.end()
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 0
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

ll N;
vector<ll> A;

int cnt[MAX_N] = {};     // i が出てくる数

// 位置 i より前に出てくる数 j の数
int cnt2[MAX_N][100];

int cnt3[MAX_N];

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

    cin >> N;
    A.resize(N);
    REP(i, N) {
        cin >> A[i];
        cnt[A[i]]++;
    }

    // 0 チェック
    REP(i, N) {
        if(cnt[i] > 3) {
            printf("0\n");
            return 0;
        }
        if(i > 0 && cnt[i - 1] == 0 && cnt[i] > 0) {
            printf("0\n");
            return 0;
        }
    }

    REP(j, 100) {
        int tmp = 0;
        REP(i, N) {
            cnt2[i][j] = tmp;
            if(A[i] == j) {
                tmp++;
            }
        }
    }

    ll ans = 1;
    REP(i, N) {
        int num = A[i];
        if(num == 0) {
            cnt3[num]++;
            continue;
        }

        // 自分より前にいる、自分より 1 少ないものの数
        ll val1 = cnt3[num - 1];

        // 自分より前にいる、自分と同じものの数
        ll val2 = cnt3[num];

        ans *= (val1 - val2);
        //ans *= cnt2[i][num - 1] - cnt2[i][num];
        ans %= MOD;

        cnt3[num]++;
    }

    if(cnt[0] == 1) {
        ans *= 3;
        ans %= MOD;
    }
    else {
        ans *= 6;
        ans %= MOD;
    }
    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 80768
def f(x,y):
    while 1:
        x,y=(x+1)%n,(y+1)%n
        if A[y][x]==0:break
        x,y=(x-1)%n,(y+1)%n
        if A[y][x]==0:break
    return x,y

def magic(n):
    c=1
    x=n/2
    y=x+1
    while 1:
        A[y][x]=c
        if c==n*n:break
        x,y=f(x,y)
        c+=1
    return

while 1:
    n=input()
    if n==0:break
    N=range(n)
    A=[[0]*n for i in N]
    magic(n)
    for i in N:
        print "".join(["%4d"%(e)for e in A[i]])

Measured memory_bytes: 4260
N = int(input())
A = list(map(int, input().split()))
D = {}
for a in A:
    if a not in D: D[a] = 0
    D[a] += 1

n2 = 0
for k in D:
    D[k] = 2 if D[k]%2==0 else 1
    if D[k]==2: n2+=1

print(len(D) - n2%2)

Measured memory_bytes: 18272
N, M = map(int, input().split())                                                                  
S = []
for _ in range(M):                                                                                
    S.append(list(map(int, input().split()))[1:])                                                                      
P = list(map(int, input().split()))                                                               

ans = 0

for x in range(2**N):                                                                             
    ok = True                                                                                                          
    for si in range(M):                                                                           
        cnt = 0
        for s in S[si]:                                                                           
            if x & (1 << (s - 1)):                                                                                     
                cnt += 1
        if cnt % 2 != P[si]:                                                                                           
            ok = False                                                                            
            break
    if ok:
        ans += 1
print(ans)                                                                                        




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

#define _For(idx, from, to, inc, cmp) \
	for(auto idx=(from) ; idx cmp (to) ; inc idx)
#define ForLE(idx, from, to) \
	_For(idx, from, to, ++, <=)
#define ForGE(idx, from, to) \
	_For(idx, from, to, --, >=)
#define ForLT(idx, from, to) \
	_For(idx, from, to, ++, <)
#define ForGT(idx, from, to) \
	_For(idx, from, to, --, >)
#define For(idx, from, to) \
	_For(idx, from, to, ++, <)

using u64 = uint64_t;
u64 MakePair(const int from, const int to) {
	return (u64(from) << 32) | to;
}
#include <unordered_set>
#include <algorithm>
int main() {
	int NLand,
		NEdge;
	std::cin >> NLand >> NEdge;
	std::vector<u64> edge(NEdge);
	std::unordered_set<u64> edgeSet;
	For(i, 0, NEdge) {
		int e0, e1;
		std::cin >> e0 >> e1;
		edge[i] = MakePair(e0, e1);
		edgeSet.emplace(edge[i]);
	}
	std::sort(edge.begin(), edge.end());
	const auto chk = [&](){
		const auto itr0E = std::upper_bound(edge.begin(), edge.end(), MakePair(2, 0));
		for(auto itr = edge.begin() ; itr!=itr0E ; ++itr) {
			const auto inter = (*itr & 0xffffffff);
			if(edgeSet.count(MakePair(inter, NLand)) == 1)
				return true;
		}
		return false;
	};
	if(chk())
		std::cout << "POSSIBLE";
	else
		std::cout << "IMPOSSIBLE";
	std::cout << std::endl;
	return 0;
}

Measured memory_bytes: 10056