akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(ll i=0;i<(n);++i)
#define reps(i,n) for(ll i=1;i<=(n);++i)
using ll = long long;
using str = string;
constexpr long long INF = (1LL<<60);
constexpr long long MOD = (1e9+7);
template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T>inline bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
inline void dump(){cout<<endl;}
template<class Head,class... Tail>inline void dump(Head&& head, Tail&&... tail){cout<<head<<", ";dump(forward<Tail>(tail)...);}
template<typename T>inline istream &operator>>(istream&input,vector<T>&v){for(auto &elemnt:v)input>>elemnt;return input;}
using vertex = struct vertex{ll to,cost;vertex(ll to,ll cost):to(to),cost(cost){}};
using _vertex = struct _vertex{ll to;_vertex(ll to):to(to){}};
using edge = struct edge{ll from,to,cost;edge(ll from,ll to,ll cost):from(from),to(to),cost(cost){}};
using _edge = struct _edge{ll from,to;_edge(ll from,ll to):from(from),to(to){}};
using un_weighted_adjlist = vector<vector<_vertex>>;
using weighted_adjlist = vector<vector<vertex>>;
using un_weighted_edge = vector<_edge>;
using weighted_edge = vector<edge>;

main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout<<fixed<<setprecision(10);
  
  ll n;
  cin>>n;
  weighted_adjlist adj(n);
  rep(i,n-1){
    ll u,v,w;
    cin>>u>>v>>w;
    u--;v--;
    adj[u].emplace_back(v,w);
    adj[v].emplace_back(u,w);
  }

  vector<ll> dist(n,INF);
  priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<>> que;
  que.emplace(0,0);
  while(!que.empty()){
    ll w,v;
    tie(w,v)=que.top();
    que.pop();
    if( chmin(dist[v],w) ){
      for(const auto& nv:adj[v]){
        if(nv.cost+w < dist[nv.to]){
          que.emplace(nv.cost+w,nv.to);
        }
      }
    }
  }

  rep(i,n){
    cout<<dist[i]%2<<endl;
  }


}


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

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

	for(int bit=0;bit<(1<<n);++bit){
		int cnt=0;
		for(int i=0;i<n;++i){
			if(bit>>i&1)++cnt;
		}
		if(cnt != k) continue;

		bitset<64> bs(0);
		for(int i=0;i<n;++i){
			if(bit>>i&1) bs.set(i);
		}
		cout<<bs.to_ulong()<<":";

		for(int i=0;i<n;++i){
			if(bit>>i&1) {
				cout<<" "<<i;
			}
		}
		cout<<endl;
	}
  return 0;
}



Measured memory_bytes: 3072
#include <iostream>

using namespace std;

int main()
{
int n, x=0, max=0; char arr[100];
cin>>n;
for(int i=0 ; i<n ; i++){
    cin >>arr[i];
    if (arr[i]=='I'){
        ++x ;if (i==0 ) max=x;else if ( x>max )max=x;}
    else if (arr[i]=='D') --x;}

cout <<max;
    return 0;
}


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

#define long long long int
using namespace std;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout.precision(6);
    int n;
    cin >> n;
    priority_queue<double, vector<double>, __greater> q;
    for (int i = 0; i < n; ++i) {
        double val;
        cin >> val;
        q.push(val);
    }
    while (q.size() > 1) {
        double a = q.top();
        q.pop();
        double b = q.top();
        q.pop();
        q.push((a + b) / 2);
    }
    cout << q.top();
    return 0;
}

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  int N,W;
  cin>>N>>W;
  vector<int>v(N),w(N);
  for(int i=0;i<N;i++)cin>>v[i]>>w[i];
  vector<vector<int>>dp(N+1,vector<int>(W+1,0));
  for(int i=1;i<=N;i++){
    for(int j=0;j<=W;j++){
      if(j-w[i-1]>=0)dp[i][j]=max(dp[i][j],dp[i-1][j-w[i-1]]+v[i-1]);
      dp[i][j]=max(dp[i][j],dp[i-1][j]);
    }
  }
  int ans=0;
  for(int i=0;i<=W;i++){
    ans=max(ans,dp[N][i]);
  }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 6848
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long,long long>
using namespace std;

int m[3][3],n,b;
bool ok[3][3],win;

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    for(int i=0; i<3; i++) for(int j=0; j<3; j++) cin >> m[i][j];

    cin >> n;
    for(int i=0; i<n; i++){
        cin >> b;
        for(int k=0; k<3; k++) for(int j=0; j<3; j++){
            if( m[k][j]==b ){
                ok[k][j] = true;
            }
        }
    }

    for(int i=0; i<3; i++){
        win = true;
        for(int j=0; j<3; j++) win&=ok[i][j];
        if( win ){
            cout << "Yes";
            return 0;
        }
    }
    for(int i=0; i<3; i++){
        win = true;
        for(int j=0; j<3; j++) win&=ok[j][i];
        if( win ){
            cout << "Yes";
            return 0;
        }
    }

    win = true;
    for(int i=0; i<3; i++){
        win&=ok[i][i];
    }
    if( win ){
            cout << "Yes";
            return 0;
        }
    win = true;
        for(int i=0; i<3; i++){

        win&=ok[i][2-i];
    }
    if( win ){
            cout << "Yes";
            return 0;
        }

        cout << "No";

    return 0;
}


Measured memory_bytes: 256
// D - Div Game
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
#define all(x) (x).begin(),(x).end()
#define rp(i,s,e) for(int i=(int)(s);i<(int)(e);++i)

// 素数と個数を求める
vector<pair<ll,ll>> factorize(ll n){
  vector<pair<ll,ll>> res;
  for(ll i=2L; i*i<=n; ++i){
    if (n%i) continue;
    res.emplace_back(i,0);
    while(n%i == 0){
      n /= i;
      res.back().second++;
    }
  }
  if(n != 1) res.emplace_back(n,1L);
  return res;
}

// a^n を計算する(二分累乗法:O(logn))
ll llpow(ll a, ll n) {
	ll x = 1;
	while(n > 0){
		if(n & 1) x = x * a;
		a = a * a;
		n >>= 1;
	}
	return x;
}

int main(){
	ll N; cin>>N;
	vector<pair<ll,ll>> P = factorize(N);
	ll ans = 0;
	for(auto x:P){
		ll p,c; tie(p,c) = x;
		for(int i=1; i<=c; ++i){
			ll pi = llpow(p, i);
			if(N%pi) continue;
			N /= pi;
			ans++;
		}
	}
	cout<< ans <<endl;
}


Measured memory_bytes: 3624
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	vector<int> A;
	int N, tmp;
	long long int h = 0, w = 0;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &tmp);
		A.push_back(-tmp);
	}
	sort(A.begin(), A.end());
	int i = 0;
	while (i + 1 < N && A[i] != A[i + 1])
		i++;
	if (i + 1 < N && A[i] == A[i + 1])
		h = -A[i];
	i += 2;
	while (i + 1 < N && A[i] != A[i + 1])
		i++;
	if (i + 1 < N && A[i] == A[i + 1])
		w = -A[i];
	printf("%lld\n", h * w);
}

Measured memory_bytes: 892
#include<bits/stdc++.h>
#define mod 1000000007
#define mod1 998244353
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long int li;
typedef unsigned long long int ull;
using namespace std;
bool sortbysec(const pair<li,li>&a,const pair<li,li>&b)
{
    return (a.second<b.second);
}
li mpow(li x,li y)
{
  li ans=1;
  while(y)
  {
    if(y%2!=0)
    ans=((ans%mod)*(x%mod))%mod;
    y/=2;
    x=((x%mod)*(x%mod))%mod;
  }
  return ans;
}
int main()
{
fast_io
li n,m,i;
cin>>n>>m;
li a[n]={0};
li b[n]={0};
for(i=0;i<m;i++)
{
  li x,y;
  cin>>x>>y;
  if(b[x-1]==0)
  {a[x-1]=y;
    b[x-1]=1;
  }
  else if(a[x-1]!=y)
  break;
}
if(i<m)
cout<<"-1";
else
{
  if(n>1)
  {
      if(a[0]==0&&b[0]!=0)
      {cout<<"-1";
      return 0;
       }
      else if(a[0]==0)
      cout<<"1";
      else
      cout<<a[0];
      for(i=1;i<n;i++)
      cout<<a[i];
  }
  else
  {
    cout<<a[0];
  }
}
  return  0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <iomanip>
#include <map>
using namespace std;

int main(void){
    map<int, int> ball;
    int n;
    cin >> n;
    int a[n];
    for(int i=0;i < n;i++){
        cin >> a[i];
        if(ball.find(a[i]) != ball.end()){
            ball[a[i]]++;
        }else{
            ball[a[i]]=1;
        }
    }

    long int sum = 0;
    for (auto itr = ball.begin(); itr != ball.end(); itr++){
        long int tmp = (*itr).second;
        sum += tmp*(tmp - 1)/2;
    }
    //cout << sum << endl;
        for (int i = 0; i < n; i++)
        {
            long int m = a[i];
            long int c = ball[m];
            cout << sum - (c-- *(c)/2 - (c--)*(c)/2)<<endl;
        }
    return 0;
}

Measured memory_bytes: 8320
// AOJ 2249: Road Construction
// 2017.11.15 bal4u@uu

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 16010
typedef struct { int t, node, c; } QUE;
QUE que[MAX]; int qsize;

#define PARENT(i) ((i)>>1)
#define LEFT(i)   ((i)<<1)
#define RIGHT(i)  (((i)<<1)+1)

void min_heapify(int i)
{
	int l, r, min;
	QUE qt;

	l = LEFT(i), r = RIGHT(i);
	if (l < qsize && (que[l].t < que[i].t ||
		que[l].t == que[i].t && que[l].c < que[i].c)) min = l; else min = i;
	if (r < qsize && (que[r].t < que[min].t ||
		que[r].t == que[min].t && que[r].c < que[min].c)) min = r;
	if (min != i) {
		qt = que[i], que[i] = que[min], que[min] = qt;
		min_heapify(min);
	}
}

void deq()
{
//	if (qsize == 0) return 0;
//	*n = que[0].node, *t = que[0].t, *c = que[0].c;
	que[0] = que[--qsize];
	min_heapify(0);
//	return 1;
}

void enq(int n, int t, int c)
{
	int i, min;
	QUE qt;

	i = qsize++;
	que[i].node = n, que[i].t = t, que[i].c = c;
	while (i > 0 && (que[min = PARENT(i)].t > que[i].t ||
		   que[min].t == que[i].t && que[min].c > que[i].c)) {
		qt = que[i], que[i] = que[min], que[min] = qt;
		i = min;
	}
}

#define INF 0x55555555
typedef struct { int to, d, c; } EG;
typedef struct { int len; EG e[100]; } TBL;
TBL *tbl;
char visited[10003]; int size;

int dijkstra(int start)
{
	int s, d, c, ans = 0;
	EG *e;

	qsize = 0;
	memset(visited, 0, sizeof(visited));
	enq(start, 0, 0);
	while(qsize) {
		s = que[0].node, d = que[0].t, c = que[0].c; deq();
		if (visited[s]) continue;
		visited[s] = 1;
		ans += c;
		for (e = tbl[s].e; e->to >= 0; e++) {
			if (visited[e->to]) continue;
			enq(e->to, d + e->d, e->c);
		}
	}
	return ans;
}

char buf[40], *p;
int getint()
{
	int n = 0;
	while (*p >= '0') n = (n<<3) + (n<<1) + (*p++ & 0xf);
	return n;
}

int main()
{
	int n, m, i, u, v, d, c;
	EG  *e;

	while (fgets(p=buf, 40, stdin) && *p != '0') {
		size = n = getint(), p++, m = getint();

		tbl = calloc(size+2, sizeof(TBL));
		memset(tbl, 0, sizeof(TBL)*size);
		for (i = 0; i < m; i++) {
			fgets(p=buf, 40, stdin);
			u = getint()-1, p++, v = getint()-1, p++, d = getint(), p++, c = getint();

			e = tbl[u].e + tbl[u].len;
			e->to = v, e->d = d, e->c = c, tbl[u].len++;

			e = tbl[v].e + tbl[v].len;
			e->to = u, e->d = d, e->c = c, tbl[v].len++;
		}
		for (i = 0; i < n; i++) tbl[i].e[tbl[i].len].to = -1;

		printf("%d\n", dijkstra(0));
		free(tbl);
	}
	return 0;
}

Measured memory_bytes: 12428
a, b = map(int, input().split())

ans = [["#" if i < 50 else "." for _ in range(100)] for i in range(100)]

for i in range(a - 1):
  rows = i // 50
  clms = (i % 50) * 2 + (rows % 2)
  ans[rows * 2][clms] = "."

for i in range(b - 1):
  rows = i // 50
  clms = (i % 50) * 2 + (rows % 2)
  ans[99 - rows * 2][clms] = "#"
  
print(100, 100)
for a in ans:
  print("".join(a))

Measured memory_bytes: 9264
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

using namespace std;

#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i <= b; i++)
#define revrep(i, s) for (int i = s-1; i > 0; i--)
#define revrrep(i, s) for (int i = s-1; i >= 0; i--)
#define all(a)  begin((a)),end((a))
#define uniq(c) (c).erase(unique(all((c))), end((c)))

int main()
{
    int N, M, X, Y; cin >> N >> M >> X >> Y;
    vector<int> X_vec, Y_vec;
    rep (i, 0, N) {
        int in; cin >> in;
        X_vec.push_back(in);
    }
    rep (i, 0, M) {
        int in; cin >> in;
        Y_vec.push_back(in);
    }

    int x_max = *max_element(X_vec.begin(), X_vec.end());
    int y_min = *min_element(Y_vec.begin(), Y_vec.end());
    rrep (i, X+1, Y) {
        if (x_max < i and y_min >= i) {
            cout << "No War" << endl;
            return 0;
        }
    }
    cout << "War" << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

char board[71][71];
char ans[71][71][71];
int W, H;

int gt(char *x, char *y);
int gt4dp(char *x, char *y);
char *solve(int x, int y, int level, char now[]);
void solve_dp(void);

int main(void)
{
    while(1){
        int i, j;

        scanf("%d %d", &W, &H);
        if(W ==0 && H == 0)
            break;

        for(i = 0; i < H; i++)
            scanf("%s", &(board[i + 1][1]));

        for(i = 0; i <= H + 1; i++)
            board[i][0] = board[i][W + 1] = 'A';
        for(i = 0; i <= W + 1; i++)
            board[0][i] = board[H + 1][i] = 'A';

        char max[71];
        char *temp;
        max[0] = '1';
        max[1] = '\0';


        solve_dp();
        for(i = 1; i <= H; i++){
            for(j = 1; j <= W; j++){
                if(isdigit(board[i][j]) && gt(ans[i][j], max)){
                    strcpy(max, ans[i][j]);
                }
            }
        }

        temp = max;
        while(*temp == '0')
            temp++;

        printf("%s\n", temp);

    }

    return 0;
}

int gt4dp(char *x, char *y)
{
    int len_x, len_y;
    char *px, *py;
    px = x;
    py = y;
    len_x = len_y = 0;
    while(*px != '\0'){
        len_x++;
        px++;
    }
    while(*py != '\0'){
        len_y++;
        py++;
    }
    if(len_x != len_y)
        return len_x > len_y;
    while(*x == *y){
        x++;
        y++;
    }

    return *x > *y;
}

int gt(char *x, char *y)
{
    char *px, *py;
    char *sx, *sy;
    px = x;
    py = y;
    int len_x, len_y;
    len_x = len_y = 0;
    while(*px == '0'){
        px++;
    }
    while(*py == '0'){
        py++;
    }

    sx = px;
    sy = py;
    while(*px != '\0'){
        px++;
        len_x++;
    }
    while(*py != '\0'){
        py++;
        len_y++;
    }

    if(len_x != len_y)
        return len_x > len_y;

    while(*sx == *sy){
        sx++;
        sy++;
    }

    return (*sx > *sy);
}

void solve_dp(void)
{
    int i, j;

    for(i = H; i >= 1; i--){
        for(j = W; j >= 1; j--){
            char temp[71];
            temp[0] = board[i][j];
            temp[1] = '\0';
            if(isalpha(board[i][j]))
                continue;

            if(isalpha(board[i][j + 1]) && isalpha(board[i + 1][j])){
                ans[i][j][0] = board[i][j];
                ans[i][j][1] = '\0';
                continue;
            }
            if(isdigit(board[i][j + 1]) && isdigit(board[i + 1][j])){
                if(gt4dp(ans[i][j + 1], ans[i + 1][j])){
                    strcat(temp, ans[i][j + 1]);
                }else{
                    strcat(temp, ans[i + 1][j]);
                }
                strcpy(ans[i][j], temp);
                continue;
            }
            if(isdigit(board[i][j + 1])){
                strcat(temp, ans[i][j + 1]);
                strcpy(ans[i][j], temp);
            }
            if(isdigit(board[i + 1][j])){
                strcat(temp, ans[i + 1][j]);
                strcpy(ans[i][j], temp);
            }
        }
    }
}

Measured memory_bytes: 936
n=int(input())
for i in range(1,3501):
    for j in range(1,3501):
        t1=n*i*j
        t2=4*i*j-n*i-n*j
        if t2>0:
            k,m=divmod(t1,t2)
            if k>0 and m==0:
                print(i,j,k)
                exit()

Measured memory_bytes: 40924
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
typedef long long int ll;
using namespace std;

ll n, a, b, c;
vector<string> s, ans;

int main(){
  cin >> n >> a >> b >> c;
  s = vector<string>(n);
  for(ll i=0;i<n;i++) cin >> s[i];
  
 
  for(ll i=0;i<n;i++){
    if (s[i] == "AB"){
      if (a==1 && b==1 && c==0 && i+1<n){
        if (s[i+1]=="AC") {a++; b--; ans.pb("A");} else {a--; b++; ans.pb("B");}
      }else{
	      if (a < b) {a++; b--; ans.pb("A");} else {a--; b++; ans.pb("B");}
      }
    }else if (s[i] == "BC"){
      if (a==0 && b==1 && c==1 && i+1<n){
        if (s[i+1]=="AB") {b++; c--; ans.pb("B");} else {b--; c++; ans.pb("C");}
      }else{
        if (b < c) {b++; c--; ans.pb("B");} else {b--; c++; ans.pb("C");}
      }
    }else{
      if (a==1 && b==0 && c==1 && i+1<n){
        if (s[i+1]=="AB") {a++; c--; ans.pb("A");} else {a--; c++; ans.pb("C");}
      }else{
        if (a < c) {a++; c--; ans.pb("A");} else {a--; c++; ans.pb("C");}
      }
    }
    if (a<0 || b<0 || c<0){
      cout << "No" << endl; return 0;
    }
  }
  cout << "Yes" << endl;
  for(ll i=0;i<n;i++){
    cout << ans[i] << endl;
  }

  return 0;
}
  


Measured memory_bytes: 10596
import sys
input=sys.stdin.readline

import fractions

n,x = map(int, input().split())
a = list(map(int, input().split()))

d = []
for i in a:
    d.append(abs(i-x))
ans = d[0]
for i in d:
    ans = fractions.gcd(i,ans)
print(ans)


Measured memory_bytes: 16240
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
N, M = map(int, input().split())
if N - 1 == M:
    print(0)
    exit()
if N < 2 * (N - M - 1):
    print('Impossible')
    exit()


parent = [i for i in range(N)]
rank = [0] * N


def find(i):
    if parent[i] == i:
        return i
    else:
        parent[i] = find(parent[i])
        return parent[i]


def same(x, y):
    return find(x) == find(y)


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return

    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


A = list(map(int, input().split()))
G = [[] for i in range(N)]
X, Y = [], []
for i in range(M):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    unite(x, y)

K = 0
D = defaultdict(list)
for i in range(N):
    k = find(i)
    if not D[k]:
        K += 1
    D[k].append((A[i], i))

ans = 0
used = [0] * N
for v in D.values():
    s = min(v)
    ans += s[0]
    used[s[1]] = 1

T = []
for i in range(N):
    if not used[i]:
        T.append(A[i])

T = sorted(T)
ans += sum(T[:2 * (N - M - 1) - K])
print(ans)


Measured memory_bytes: 41744
#include <iostream>
#include <unordered_set>

using namespace std;

class B {
	unordered_set<string> us;
	string s;
	int n;
public:
	void solve()
	{

		char last;
		cin >> s;
		us.insert(s);
		last = s.back();

		bool flag{ true };
		for (int i{ 1 }; i < n; i++)
		{
			cin >> s;
			if (s.front() != last || !(us.insert(s).second))
			{
				flag = false;
				break;
			}
			last = s.back();
		}

		if (flag) cout << "Yes" << endl;
		else cout << "No" << endl;
	}

	B()
	{
		cin >> n;
	}
};


int main()
{
	B solution;
	solution.solve();

	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
using namespace std;
int MOD = 1000000007;

signed main(){
    
    int w,h,x,y;
    cin >> w >> h >> x >> y;
    
    double s = w*h*1.0/2.0;
    int d = 0;
    if(w == 2*x && h == 2*y)d = 1;
    printf("%.10lf %lld\n",s,d);
    
    return 0;
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_a
// rm -r -f test;oj dl http://abc130.contest.atcoder.jp/tasks/abc130_b

Measured memory_bytes: 256
//14
#include<iostream>

using namespace std;

int main(){
  bool cmp[1<<15]={true,true};
  for(int i=2;i<1<<15;i++){
    if(!cmp[i]){
      for(int j=2;j*i<1<<15;j++){
	cmp[i*j]=true;
      }
    }
  }
  for(int n;cin>>n,n;){
    int ans=0;
    for(int i=0;i<=n/2;i++){
      ans+=!cmp[i]&&!cmp[n-i];
    }
    cout<<ans<<endl;
  }
  return 0;
}
	

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

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

	int N;
	cin >> N;
	int a[100];
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	sort(a, a + N);
	cout << a[N - 1] - a[0];
}


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

using namespace std;

#define MAX 100
#define MAX_H 100000
#define INF (1<<29)

int main(){
    int N,M;
    string in;
    while(cin >> N, N){
        int MHP = 0;
        vector<int> HP(N);
        for(int i = 0 ; i < N ; i++){
            cin >> HP[i];
            MHP = max(MHP,HP[i]);
        }
        cin >> M;
        vector<int> MP(M),t(M),d(M);
        for(int i = 0 ; i < M ; i++){
            cin >> in >> MP[i] >> in >> d[i];
            t[i] = (in == "All");
        }
        int dp[2][MAX_H+1];
        fill(dp[0],dp[0]+2*(MAX_H+1),INF);
        dp[0][0] = dp[1][0] = 0;
        for(int i = 0 ; i < M ; i++){
            for(int j = 0 ; j <= MHP ; j++){
                int nt = t[i],nhp = min(MHP,j+d[i]);
                dp[nt][nhp] = min(dp[nt][nhp],dp[nt][j]+MP[i]);
            }
        }
        for(int i = MHP ; i > 0 ; i--){
            dp[0][i-1] = min(dp[0][i-1],dp[0][i]);
            dp[1][i-1] = min(dp[1][i-1],dp[1][i]);
        }
        int res = INF;
        for(int i = 0 ; i <= MHP ; i++){
            int mp = dp[1][i],mp2 = 0;
            bool ok = true;
            if(mp == INF) continue;
            for(int j = 0 ; j < N ; j++){
                int rest = max(HP[j]-i,0);
                if(rest == 0) continue;
                if(dp[0][rest] == INF){
                    ok = false;
                }
                mp2 += dp[0][rest];
            }
            if(!ok) continue;
            res = min(res,mp+mp2);
        }
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 1996
#include <iostream>

int main() {
    int a[3][3];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            std::cin >> a[i][j];
        }
    }

    int n;
    std::cin >> n;
    for (int k = 0; k < n; k++) {
        int b;
        std::cin >> b;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (a[i][j] == b) {
                    a[i][j] = 0;
                }
            }
        }
    }

    for (int i = 0; i < 3; i++) {
        if (a[i][0] == 0 && a[i][0] == a[i][1] && a[i][0] == a[i][2]) {
            std::cout << "Yes" << std::endl;
            return 0;
        }
    }
    for (int j = 0; j < 3; j++) {
        if (a[0][j] == 0 && a[0][j] == a[1][j] && a[0][j] == a[2][j]) {
            std::cout << "Yes" << std::endl;
            return 0;
        }
    }
    if (a[0][0] == 0 && a[0][0] == a[1][1] && a[0][0] == a[2][2]) {
        std::cout << "Yes" << std::endl;
        return 0;
    }
    if (a[0][2] == 0 && a[0][2] == a[1][1] && a[0][2] == a[2][0]) {
        std::cout << "Yes" << std::endl;
        return 0;
    }

    std::cout << "No" << std::endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args) {
        // write your code here
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        long t = sc.nextLong();

        long start = sc.nextInt();
        long ans = t;

        for (int i = 1; i < n; i++) {
            long value = sc.nextLong();
            ans += Math.min(t, value - start);
            start = value;
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 64428
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int a,b,c;
  cin>>a>>b>>c;
  cout<<b+min(c,a+b+1)<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int i,j,n,m,k,l,b[20],a,c;
int main()
{
  for(cin>>n>>m>>c;i<m;i++)cin>>b[i];
  for(i=0;i<n;i++){
    for(k=0,j=0;j<m;j++){
      cin>>a;k+=(a*b[j]);
    }
    if(k>-1*c)l++;
  }
  cout<<l;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long a,b,n;
  cin>>a>>b>>n;
  long long x;
  if(b<=n){
    x=b-1;
  }
  else{
    x=n;
  }
  long long res=(a*x)/b - (a*(x/b));
  cout<<res;
}

Measured memory_bytes: 3624
#include "bits/stdc++.h"
#define MOD 1000000007
#define INF 11234567890
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

std::string S;
std::string temp = "CODEFESTIVAL2016";
int ans;

int main()
{
	in >> S;

	rep(i, 16)
	{
		if (S[i] != temp[i]) { ++ans; }
	}

	out << ans << std::endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
void ABC100(void);
void ABC101(void);
void ABC102(void);
void ABC103(void);
void ABC104(void);
void ABC105(void);
void ABC106(void);
void ABC107(void);
void ABC108(void);
void ABC109(void);

int main(void){
    ABC106();
}

void ABC106(){
    int a,b;
    cin>>a>>b;
    cout<<(a-1)*(b-1)<<endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>


using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>pii;
typedef array<int, 3> arr3;
std::random_device rd;
std::mt19937 mt(rd());
constexpr ll MOD = 1e9 + 7; constexpr int MAX = 2000020;
const double pi = acos(-1); constexpr double EPS = 1e-8;
constexpr ll INF = 1e18;
void y(bool c) {
	if (c)print("Yes");
	else print("No");
}
long long gcd(long long x, long long y) {
	long long m = max(x, y), n = min(x, y);
	if (m%n == 0)return n;
	else return gcd(m%n, n);
}

struct edge {
	int src, to, cost,index;
};
vector<edge>G[200020];
int deg[200010];
int ans[200010];
void solve() {
	int N; cin >> N;
	REP(i,N-1){
		int u, v; cin >> u >> v;
		u--, v--;
		G[u].push_back({ u,v,0 ,i});
		G[v].push_back({ v,u,0 ,i});
		deg[u]++, deg[v]++;
	}
	queue<int>que;
	vector<int>C(N);
	REP(i, N)cin >> C[i];
	priority_queue<int, vector<int>, greater<int>>pq;
	REP(i, N)pq.push(C[i]);
	REP(i, N) {
		if (deg[i] == 1)que.push(i);
	}
	while (!que.empty()) {
		int v = que.front(); que.pop();
		if (ans[v] != 0)continue;
		ans[v] = pq.top(); pq.pop();
		for (auto e:G[v]) {
			deg[e.to]--;
			if (deg[e.to] == 1)que.push(e.to);
		}
		//for (auto &e : G[v]) {
		//	if (e.cost != 0)continue;
		//	e.cost = pq.top();
		//	ans[v] = pq.top();
		//	pq.pop();
		//	deg[e.to]--;
		//	if (deg[e.to] == 1)que.push(e.to);
		//}
	}
	int sum = 0;
	REP(i, N) {
		for (auto e : G[i]) {
			sum += min(ans[i], ans[e.to]);
		}
	}
	sum /= 2;
	print(sum);
	REP(i, N) {
		pe(ans[i]);
	}cout << endl;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q; cin >> q;
	//while (q--)
	solve();
}




Measured memory_bytes: 7680
mod = 998244353
n, m, k = map(int, input().split())

def inv(a,mod):
    r = [1,0,a]
    w = [0,1,mod]
    while w[2]!=1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = w
        w = r_new
    x,y = w[0],w[1]    # a*x+y*mod = 1
    return (mod+x%mod)%mod

max_num = 2*10**5+1
fact = [0 for _ in range(max_num)]
ifact = [0 for _ in range(max_num)]

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

for i in range(2,max_num):
    fact[i] = fact[i-1] * i % mod

ifact[max_num-1] = inv(fact[max_num-1],mod)

for i in range(2,max_num):
    ifact[max_num-i] = (ifact[max_num-i+1] * (max_num-i+1)) %mod

def comb(x,y):
    if x < 0 or y < 0 or x < y:
        return 0
    else:
        return fact[x] * ifact[y] * ifact[x-y] % mod


ans = 0

for i in range(0,k+1):
    ans += comb(n-1,i)*m*pow(m-1,n-i-1,mod)
    ans %= mod

print(ans)

Measured memory_bytes: 94336
#include <iostream>
#include <cstring>
#include <math.h>
using namespace std;

#define big (1000000007)

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    long long s[n], sum[n] = {0};
    long long ans = 0;
    for (int i = 0; i < n; i++)
        cin >> s[i];
    sum[n - 1] = s[n - 1];
    for (int i = n - 2; i >= 0; i--)
        sum[i] = (long long)sum[i + 1] + s[i];
    for (int i = 0; i < n - 1; i++)
    {
        ans = (ans + ((sum[i + 1])%big * (s[i]%big)) % big) % big;
    }
    cout << ans;
}

Measured memory_bytes: 6752
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N (305)
int f[N][N][N];
char s[N];
int kk;
int main(){
    scanf("%s%d", s+1, &kk);
    int n = strlen(s+1);
    for (int i = 1; i <= n; ++i){
        for (int j = n; j >= i; --j){
            f[i][j][0] = max(f[i-1][j][0], f[i][j+1][0]);
            if (s[i] == s[j]){
                f[i][j][0] = max(f[i][j][0], f[i-1][j+1][0]+1);
            }
        }
    }
    for (int k = 1; k <= kk; ++k){
        for (int i=1; i <= n; ++i){
            for (int j = n; j>=i; --j){
                f[i][j][k] = max(max(f[i-1][j][k], f[i][j+1][k]), f[i-1][j+1][k-(s[i]!=s[j])]+1);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i){
        ans = max(2*f[i][i+1][kk], ans);
        ans = max(2*f[i-1][i+1][kk]+1, ans);
    }
    printf("%d\n", ans);
}

Measured memory_bytes: 110464
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner sc = new Scanner(System.in);

        //重複を許可しない集合構造
        Set<Integer> set = new HashSet<>();
        //a,b,cの格納
        set.add(sc.nextInt());  
        set.add(sc.nextInt());
        set.add(sc.nextInt());

        System.out.println(set.size());
    }
}

Measured memory_bytes: 21204
import java.util.Arrays;
import java.util.Scanner;

public class Main
{
	public static void main(String arg[])
	{
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext())
		{
			int a, b, c, d, e;
			a = sc.nextInt();
			b = sc.nextInt();
			c = sc.nextInt();
			d = sc.nextInt();
			e = sc.nextInt();
			int from = 0;
			int to = 0;
			from = a * 60 + b;
			to = c * 60 + d;
			System.out.println(to-from-e);

		}
	}
}

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

int main(){
    int n; 
    cin >>n;
    if(n<=111)
       cout<<111;
    else if(n<=222)
       cout<<222;
    else if(n<=333)
       cout<<333;
    else if(n<=444)
       cout<<444;
    else if(n<=555)
       cout<<555;
    else if(n<=666)
       cout<<666;
    else if(n<=777)
       cout<<777;
    else if(n<=888)
       cout<<888;
    else if(n<=999)
       cout<<999;
}


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

typedef long long ll;
typedef vector<long long> VLL;
typedef vector<pair<int,int>> VP;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define MOD (1e9+7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)

/*--------------------------------------------*/



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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        if(n<=111)
            cout<<"111"<<endl;
        else if(n<=222)
            cout<<"222"<<endl;
        else if(n<=333)
            cout<<"333"<<endl;
        else if(n<=444)
            cout<<"444"<<endl;
        else if(n<=555)
            cout<<"555"<<endl;
        else if(n<=666)
            cout<<"666"<<endl;
        else if(n<=777)
            cout<<"777"<<endl;
        else if(n<=888)
            cout<<"888"<<endl;
        else if(n<=999)
            cout<<"999"<<endl;

    }
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();
		String message = "NO";
		int n = 0;
		int i = 0;
		for(i = 0; i < b; i++) {
			n = n + a;
			if(n % b == c) {
				message = "YES";
				break;
			}
		}
		System.out.println(message);
	}
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 100000000;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; 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() {
    ll n;
    cin >> n;
    vector<ll> a(n, 0);
    ll count = 0;
    bool check = false;
    rep1(i, n){
        ll a, b;
        cin >> a >> b;
        if (a==b) count++;
        else count = 0;
        if (count==3) check = true;
    }
    if (check) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    //printf("%.12f", ans);
}

Measured memory_bytes: 3624
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int H = sc.nextInt();
		int W = sc.nextInt();
		int N = sc.nextInt();

		sc.close();

		int a = Math.max(H, W);

		int ans = (N + (a - 1)) / a;

		out.println(ans);

	}

	public static void main(String[] args) {
		new Main()._main(args);
	}
}


Measured memory_bytes: 21588
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		try (Scanner sc = new Scanner(System.in)) {

			int n = sc.nextInt();

			// 自然数(0は含まない)
			int[] aArray = new int[n];
			for(int i = 0 ; i < n ; i++){
				aArray[i] = sc.nextInt();
			}

			// すべてのAが割り切れた回数
			int ans = 0;

			ONE: while(true){
				for(int i = 0 ; i < n ; i++){
					if(aArray[i] % 2 == 0){
						// 2で割り切れたら割った後の数を入れる
						aArray[i] = aArray[i] / 2;
					} else {
						// 割り切れなければ処理を終える
						break ONE;
					}
				}
				// 全ての数が2で割り切れたらカウントアップ
				ans++;
			}
			System.out.println(ans);
		}

	}

}


Measured memory_bytes: 21844
/**
 *  author: mahfuzz
 *  created: 10.04.2020
**/
 
#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define debug(x) cout << #x << ':' << x << "\n"
typedef long long ll;

int main(int argc, char* argv[]){
    
    int n, k; cin >> n >> k;
    
    int cnt = 0;
    while(n){
        ++cnt;
        
        n /= k;
    }
    
    cout << cnt << "\n";
        
    return 0;
}



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

ll lc[90];
ll lucas(int n){
    if(lc[n]) return lc[n];
    if(n==0) return 2;
    if(n==1) return 1;
    return lc[n] = lucas(n-1)+lucas(n-2);
}

int main(void){
    int n;
    cin>>n;
    cout<<lucas(n)<<endl;
    return 0;
}


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

using namespace std;

#define COUNTOF(array) (sizeof(array) / sizeof(array[0]))
#define OUT(P) cout << (P) << endl
#define OUT2(P1, P2) cout << (P1) << " " << (P2) << endl

// integerの各桁を足す
int sum_digits(int num) {
    int rtn = 0;
    string num_str = to_string(num);
    for(int i=0; i<num_str.size(); i++) {
        rtn += num_str[i] - '0';
    } 
    return rtn;
}

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

    int ans = 0;
    for(int i=0; i<=n; i++) {
        int tmp = sum_digits(i);
        if(tmp >= a && tmp <= b) {
            ans += i;
        }
    }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<functional>
#include<iomanip>
#include<queue>
#include<cassert>
#include<tuple>
#include<set>
#include<map>
#include<list>
#include<bitset>

#define PB push_back
#define ALL(a)  (a).begin(),(a).end()
#define all(v) begin(v), end(v)
#define DWN(a)  (a).begin(),(a).end(), greater<int>()
#define rep(i, m) for (int i = 0; i < m; i++)
#define REP(i, n, m) for (int i = n; i < m; i++)

using namespace std;

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

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
const int INF = (int)1e9;
const ll inf = (ll)1e18;
const ll MOD{ (ll)1e9 + 7 };

int main()
{
	int n;
	cin >> n;
	int res = n;
	for (int i = 0; i <= n; i++) {
		int cc = 0;
		int t = i;
		while (t > 0) {
			cc += t % 6;
			t /= 6;
		}
		t = n - i;
		while (t > 0) {
			cc += t % 9;
			t /= 9;
		}
		if (res > cc) res = cc;
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
/*input

*/

#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <iomanip>
#include <utility>
#include <vector>
#include <math.h>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define pb          push_back
#define pp          pop_back
#define nl          cout << "\n"
#define MIN(con)    (*min_element(ALL(con)))
#define MAX(con)    (*max_element(ALL(con)))
#define NX(cont)    next_permutation(ALL(cont))
#define PX(cont)    prev_permutation(ALL(cont))
#define prec(n)     cout << fixed << setprecision(n)
#define PI          3.14159265358979323846264338327951
#define all(c)      c.begin(),c.end()
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define sp          cout << " "
#define ifalse      ios_base::sync_with_stdio(false),cin.tie(NULL)
#define debug(x)    cout << #x << " = " << x << "\n";

using ll = long long;
using ld = long double;
 
template <typename T> T GCD(T a, T b) { ll t; while(a){ t=a; a=b%a; b=t; } return b; }
template <typename T> T LCM(T a, T b) { return (a*b) / GCD(a, b); }
template <typename T> string toString(T a) { return to_string(a); }
template <typename T> void toInt(string s, T &x) { stringstream str(s); str >> x; }

ll add(ll x, ll y, ll MOD) { x += y; if(x >= MOD) x -= MOD; return x; }
ll sub(ll x, ll y, ll MOD) { x -= y; if(x < 0) x += MOD; return x; }
ll mul(ll x, ll y, ll MOD) { return ((x % MOD) * (y % MOD)) % MOD; }

ll powr(ll a, ll b, ll MOD) {
  ll x = 1LL;
  while(b) {
    if(b & 1) x = mul(x, a, MOD);
    a = mul(a, a, MOD);
    b >>= 1;
  }
  return x;
}

ll inv(ll a, ll MOD) { return powr(a, MOD-2, MOD); }
const ll INF =  1e18;
const int SINF = 1e9;
const ll MOD = 1e9 + 7;

bool check(ll n)
{
  if(n == 1) return 0;
  if(n == 2 or n == 3) return 1;
  if(n%2 == 0 or n%3 == 0) return 0;
  for(ll i = 5; i*i <= n; i += 6) if(n%i == 0 or n % (i+2) == 0) return 0;
  return 1;
}

/************************************START***************************************/
const int N = 100005;

int main()
{
  ifalse;
  string s;
  cin >> s;
  int n = s.length();
  int ans = 0;
  for(int i = 1; i < n; i ++) {
    if(s[i] == s[i - 1]) {
      if(s[i] == '1') s[i] = '0';
      else if(s[i] == '0') s[i] = '1';
      ans ++;
    }
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 512
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)
	w := nextInt()
	h := nextInt()
	x := nextInt()
	y := nextInt()

	area := float64(w) * float64(h) / 2.0
	fmt.Printf("%v ", area)
	if float64(x) == float64(w)/2 && float64(y) == float64(h)/2 {
		fmt.Println(1)
	} else {
		fmt.Println(0)
	}
}


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

#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " _ " <<

#define x first
#define y second
#define pb push_back

using namespace std;

typedef long long ll;

const int MAXN = 410;
const int MOD = 1e9 + 7;

inline int add(int a, int b) { return (a + b >= MOD) ? a + b - MOD : a + b; }
inline int sub(int a, int b) { return (a - b >= 0) ? a - b : a - b + MOD; }
inline int mul(int a, int b) { return (ll) a * b % MOD; }

int power(int a, int b) {
  int ret = 1;
  for (; b > 0; b >>= 1) {
    if (b & 1) ret = mul(ret, a);
    a = mul(a, a);
  }
  return ret;
}

int N, C;
int A[MAXN], B[MAXN];

int dp[MAXN][MAXN];
int p[MAXN][MAXN];
int f[MAXN][MAXN];

int Solve(int pos, int left) {
  if (pos == N) {
    if (left == 0) return 1;
    return 0;
  }

  int &ret = dp[pos][left];
  if (ret != -1) return ret;
  
  ret = 0;
  REP(i, left+1) {
    ret = add(ret, mul(f[pos][i], Solve(pos + 1, left - i)));
  }

  return ret;
}

int main(void) {
  ios_base::sync_with_stdio(false);
 
  cin >> N >> C;
  REP(i, N) cin >> A[i];
  REP(i, N) cin >> B[i];
 
  REP(i, MAXN)
    REP(j, MAXN)
      p[i][j] = power(i, j);

  REP(i, N) REP(j, C+1) {
    FOR(k, A[i], B[i]+1) {
      f[i][j] = add(f[i][j], p[k][j]);
    }
  }

  memset(dp, -1, sizeof dp);
  cout << Solve(0, C) << endl;

  return 0;
}


Measured memory_bytes: 2304
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

def main():
    n,m,q=map(int,input().split())
    # print(n,m,q)
    a = [ [int(x) for x in input().split()] for _ in range(q) ]
    # print(a)
    ans=0

    def solve(b):
        
        if len(b)-1==n:
            cnt=0
            for v in a:
                if b[v[1]]-b[v[0]]==v[2]:
                    cnt+=v[3]
            nonlocal ans
            ans=max(ans,cnt) 
            return

        for i in range(b[-1],m+1):
            b.append(i)
            solve(b)
            b.pop()

    b=[1]
    solve(b)
    print(ans)

# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# endregion

if __name__ == "__main__":
    main()

Measured memory_bytes: 74404
def main():
    N = int(input())
    A = []
    B = []
    for i in range(N):
        a, b = [int(i) for i in input().split()]
        A.append(a)
        B.append(b)
        
    #print(N)
    #print(A)
    #print(B)
    
    print(max(A) + min(B)) 

    
    
if __name__=="__main__":
    main()

Measured memory_bytes: 11400
use std::io::*;
use std::str::FromStr;

//https://qiita.com/tubo28/items/e6076e9040da57368845
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n: usize = read();
    let mut k: i64 = read();
    let mut ab: Vec<(i64,i64)> = (0..n).map(|_| (read(),read())).collect();

    ab.sort_by(|x,y| x.0.partial_cmp(&y.0).unwrap() );

    for i in 0..n{
        k -= ab[i].1;
        if k <= 0 {
            println!("{}",ab[i].0);
            break;
        }
    }

}


Measured memory_bytes: 4036
A = gets.split.map(&:to_i).sort
o = A.map{|v| v%2}.inject(&:+)
ans = 0
if o == 1 || o == 2 then
    ans += 1
    3.times{|i| A[i] += 1 if A[i]%2 == (o == 1 ? 0 : 1) }
end
ans += A.map{|v| (A[2] - v) / 2}.inject(&:+)
puts ans


Measured memory_bytes: 1788
#include <iostream>
#include <cstdio>
using namespace std;
int main(void){
    char ch;
    while(1){
        scanf("%c", &ch);
        if(ch == '\n')  break;
        if('a' <= ch && ch <= 'z'){
            ch = ch - 32;
        }
        else if('A' <= ch && ch <= 'Z'){
            ch = ch + 32;
        }
        printf("%c", ch);
    }
    cout << endl;
    return 0;
}



Measured memory_bytes: 3108
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;

class Main {

    public static void main(String[] args) throws IOException {
        doit(args, System.in, System.out);
    }

    static void doit(String[] args, InputStream in, PrintStream out)
            throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(in));
        String line = null;
        while ((line = reader.readLine()) != null) {
            if (line.isEmpty()) {
                continue;
            }
            double x = Double.parseDouble(line);
            double h = Double.parseDouble(reader.readLine());
            if (x == 0 && h == 0) {
                break;
            }
            double result = x * x + x * Math.sqrt(4.0 * h * h + x * x);
            out.println(result);
        }
    }
}

Measured memory_bytes: 9748
#!/usr/bin/env python3
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
ans = 0
for i in range(1, n + 1):
    count = 0
    for j in range(1, i + 1):
        if i % j == 0:
            count += 1
    if count == 8 and  i % 2 == 1:
        ans += 1
print(ans)


Measured memory_bytes: 3060