akhauriyash/Code-Regression huggingface dataset:
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <ctype.h>
#include <stdint.h>
#include <string.h>
#include <wchar.h>

#define N_MAX (100)
#define P_MAX (100)
#define DP_ARRAY_SIZE (N_MAX * P_MAX / 32 + 1)

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define ABS(a) ((a) < 0 ? -(a) : (a))
#define ABSS(a, b) ((a) > (b) ? (a) - (b) : (b) - (a))

int compare_f(const void* a, const void* b) {
    return *((int64_t*)a) < *((int64_t*)b) ? -1 : 1;
}

int compare_f2(const void* a, const void* b) {
    return *((uint64_t*)a) > * ((uint64_t*)b) ? -1 : 1;
}

static size_t comb(const size_t n, const size_t r) {
    size_t result = 1;

    for (size_t i = 0; i < r; i++) {
        result *= n - i;
        result /= i + 1;
    }

    return result;
}

static uint64_t combU64(const uint64_t n, const uint64_t r) {
    uint64_t result = 1;

    for (uint64_t i = 0; i < r; i++) {
        result *= n - i;
        result /= i + 1;
    }

    return result;
}

static uint64_t gcd(uint64_t m, uint64_t n)
{
    uint64_t temp;

    while (m % n != 0) {
        temp = n;
        n = m % n;
        m = temp;
    }

    return n;
}

int main(void) {
    size_t A[5];

    scanf("%zu\n%zu\n%zu\n%zu\n%zu", &A[0], &A[1], &A[2], &A[3], &A[4]);

    size_t minIdx = 0;

    for (size_t i = 1; i < 5; i++) {
        if ((A[i] + 9) % 10 < (A[minIdx] + 9) % 10) {
            minIdx = i;
        }
    }

    size_t sum = 0;

    for (size_t i = 0; i < 5; i++) {
        sum += (i == minIdx) ? A[i] : (A[i] + 9) / 10 * 10;
    }

    printf("%zu\n", sum);

    return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <ctype.h>
#include <climits>
#include <queue>
#include <iomanip>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i = 0; i < (ll)(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(){
	int n;
	cin >> n;
	vector<int> a(n);
	REP(i,n) cin >> a[i];
	
	map<int,int> m;
	REP(i,n){
		m[a[i]]++;
	}
	
	ll ans=0;
	for(auto x: m){
		int key = x.first;
		int value = x.second;
		if(key > value){
			ans += (ll)value;
		}else if(key < value){
			ans += (ll)(value-key);
		}
	}
	
	cout << ans << endl;
	
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;

int main() {
    int n, k;
    cin >> n >> k;
    int r, s, p;
    cin >> r >> s >> p;
    string t;
    cin >> t;

    int dp[100010][3] = {};
    int res = 0;
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j <= n / k + 1; ++j) {
            for (int l = 0; l < 3; ++l) {
                dp[i][l] = 0;
            }
        }

        int jmx = 0;
        for (int j = 0; i + j * k < n; ++j) {
            jmx = max(jmx, j);

            int id = i + j * k;
            if(t[id] == 'r'){
                for (int l = 0; l < 3; ++l) {
                    dp[j+1][l] = max(dp[j][(l+1) % 3], dp[j][(l+2) % 3]);
                }
               dp[j+1][0] += p;
            }
            if(t[id] == 's'){
                for (int l = 0; l < 3; ++l) {
                    dp[j+1][l] = max(dp[j][(l+1) % 3], dp[j][(l+2) % 3]);
                }
                dp[j+1][1] += r;
            }
            if(t[id] == 'p'){
                for (int l = 0; l < 3; ++l) {
                    dp[j+1][l] = max(dp[j][(l+1) % 3], dp[j][(l+2) % 3]);
                }
                dp[j+1][2] += s;
            }
        }

        int tmp = 0;
        for (int j = 0; j < 3; ++j) {
            tmp = max(tmp, dp[jmx + 1][j]);
        }
        res += tmp;
    }
    cout << res << endl;
}

Measured memory_bytes: 1664
#include <stdio.h>          // printf(), putchar(), fgets()
#include <stdbool.h>
#include <ctype.h>          // isalpha()

const char NUL = '\0';
char line[1025];

bool
is_word(const char *t, const char *s, int l)
{
	if (l < 3 || 6 < l)
		return false;

	if (t > line && *t != ' ' && *t != '.' && *t != ',')
		return false;

	if (*s != ' ' && *s != '.' && *s != ',' && *s != '\n' && *s != NUL)
		return false;

	return true;
}

int
main(int argc, char **argv)
{
	char word[7];

	fgets(line, sizeof(line), stdin);

	const char *s = line;
	const char *sep = "";
	while (*s != '\n' && *s != NUL)
	{
		while (!isalpha(*s) && *s != '\n' && *s != NUL)
			s++;

		int l = 0;
		int ix = 0;
		const char *t = s;
		for (; isalpha(*s) || *s == '\''; ++s, ++l)
		{
			if (l <= 6)
				word[ix++] = *s;
		}

		word[ix] = NUL;
		if (is_word(t - 1, s, l))
		{
			printf("%s%s", sep, word);
			sep = " ";
		}
	}

	putchar('\n');
	return 0;
}

Measured memory_bytes: 524
N=gets.strip.to_i
if N%2==0
  if N==4
    puts 4
  else
    puts N*2
  end
  a=[]
  a[0]=1
  a[1]=N
  (1..N/2-1).each do |i|
    a[2]=a[0]+1
    a[3]=a[1]-1
    (0..1).each do |j|
      (2..3).each do |k|
        puts "#{a[j]} #{a[k]}"
      end
    end
    a[0]=a[2]
    a[1]=a[3]
  end
  if N>4
    puts "1 #{a[0]}"
    puts "#{N} #{a[0]}"
    puts "1 #{a[1]}"
    puts "#{N} #{a[1]}"
  end
else
  if N==3
    puts 2
  else
    puts (N-1)*2
  end
  puts "1 #{N}"
  puts "#{N-1} #{N}"
  a=[]
  a[0]=1
  a[1]=N-1
  (1..(N-1)/2-1).each do |i|
    a[2]=a[0]+1
    a[3]=a[1]-1
    (0..1).each do |j|
      (2..3).each do |k|
        puts "#{a[j]} #{a[k]}"
      end
    end
    a[0]=a[2]
    a[1]=a[3]
  end
  if N>3
    puts "#{N} #{a[0]}"
    puts "#{N} #{a[1]}"
  end
end

Measured memory_bytes: 1788
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define rep(i,n) for(int i=0;i<n;i++)
int gcd(int a, int b){
    int r=1;
    while(r!=0){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
typedef long long ll;
void revStr(char* str){
    int size = strlen(str);
    int i,j;
    char tmp = {0};
    for(i = 0, j = size - 1; i < size / 2; i++, j--){
        tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;
    }return;
}
typedef struct{
    int p;
    int q;
}data;

//降順
int compare_int(const void *a, const void *b)
{
    return *(int*)b - *(int*)a;
}
int asc(const void *a, const void *b) {
  long *A = (long *)a;
  long *B = (long *)b;
  if (*A > *B) return 1;
  if (*A < *B) return -1;
  return 0;
}

int kai(int n){
    if(n==0){
        return 1;
    }
    int sum=1;
    for(int i=1;i<=n;i++){
        sum*=i;
    }
    return sum;
}
//構造体の.pを降順
int comp( const void *c1, const void *c2 )
{ data test1 = *(data *)c1;
  data test2 = *(data *)c2;
  int tmp1 = test1.p;   /* b を基準とする */
  int tmp2 = test2.p;
    return tmp2 - tmp1;}




int main(){
    int X;
    scanf("%d",&X);
    int temp=0;
    while(temp<X){
        temp+=1000;
    }
    printf("%d",temp-X);
}


Measured memory_bytes: 1732
#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<math.h>
#include<algorithm>
using namespace std;

const int maxn=1e6+100;
int n,m,f[maxn],d[maxn];

int get(int x)
{
    if(f[x]==x) return x;
    int t=get(f[x]);
    d[x]=d[f[x]]+d[x];
    return f[x]=t;
}

int pd(int x,int y,int dis)
{
    int fx=get(x);
    int fy=get(y);
    if (fx==fy) return dis==d[y]-d[x];
    f[fy]=fx;
    d[fy]=d[x]+dis-d[y];
    return 1;
}

int main()
{
    bool tag=1;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=0;i<m;i++)
    {
        int x,y,dis;
        scanf("%d %d %d",&x,&y,&dis);
        if(tag) tag=pd(x,y,dis);
    }
    if (tag) printf("Yes\n");
    else
        printf("No\n");
    return 0;
}


Measured memory_bytes: 4736
#include <iostream>
#include <iterator>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <numeric>
#include <iomanip>
#include <limits>

using namespace std;


int main(){
    bool ans=false;
    //int ans=0;
    int K,X;
    //vector<int> a;

    cin>>K>>X;

    if(500*K>=X){
        ans=true;
    }

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

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

int main(){
	string s;
  	cin >> s;
  	
  	string st0="";

  	for(int i=0; i<s.length(); i++){
		if(i%2 == 0)
      		st0 += "0";
      	else
      		st0 += "1";      
        
    }
  
  	int cnt0=0, cnt1=0;
  
  	for(int i=0; i<s.length(); i++){
		if(s[i] == st0[i])
			cnt0++;
      	else
          	cnt1++;
    }
  	
  	
  	cout << min(cnt0, cnt1) << endl;
   
	return 0;
}

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

int main(int argc, char const *argv[]) {
  int n, a, b;
  int s, l;
  int max, min;
  scanf("%d %d %d", &n, &a, &b);
  if(a>b){
    s = b;
    l = a;
  } else{
    s = a;
    l = b;
  }

  if(s+l<n) min = 0;
  else min = s+l-n;

  max = s;
  
  printf("%d %d\n", max, min);

  return 0;
}

Measured memory_bytes: 128
import heapq

n=int(input())
*a,=map(int,input().split())
inf=float("inf")

pos=n
q,r=[],[]
u,d=[-inf]*(3*n),[inf]*(3*n)

for i in range(n):
    heapq.heappush(q,a[i])
    u[i]=u[i-1] if i else 0
    u[i]+=a[i]

for i in range(n,2*n):
    heapq.heappush(q,a[i])
    b=heapq.heappop(q)
    u[i]=u[i-1]+a[i]-b

for i in range(2*n,3*n)[::-1]:
    heapq.heappush(r,-a[i])
    d[i]=d[i+1] if i!=3*n-1 else 0
    d[i]+=a[i]

for i in range(n,2*n)[::-1]:
    heapq.heappush(r,-a[i])
    b=heapq.heappop(r)
    d[i]=d[i+1]+a[i]+b

ans=-inf
for i in range(n-1,2*n):
    ans=max(ans,u[i]-d[i+1])

print(ans)

Measured memory_bytes: 123040
# coding:utf-8
N=int(input())

taro_pt=0
hanako_pt=0
for i in range(0,N):
    taro_str,hanako_str=map(str,input().split())
    if taro_str>hanako_str:
        taro_pt=taro_pt+3
    elif taro_str<hanako_str:
        hanako_pt=hanako_pt+3
    else:
        taro_pt=taro_pt+1
        hanako_pt=hanako_pt+1

print(str(taro_pt)+" "+str(hanako_pt))

Measured memory_bytes: 7676
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;

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

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

int main() {
  vector<vector<int>> c(3, vector<int>(3));
  rep(i, 3) {
    rep(j, 3) { cin >> c[i][j]; }
  }

  vector<vector<int>> diff(2, vector<int>(3));
  rep(i, 2) {
    rep(j, 3) { diff[i][j] = c[i + 1][j] - c[i][j]; }
  }

  int yes = true;
  rep(i, 2) {
    rep(j, 2) {
      if (diff[i][j] != diff[i][j + 1]) yes = false;
    }
  }
  if (yes)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

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

const int maxn=1;
typedef long long ll;

int n,m,ans;
int a,b,c;

int main()
{
	int i,j,k;
	scanf("%d%d%d",&a,&b,&c);
	for(i=0;i<=100;++i)
	{
		if(a*i%b==c)
		{
			printf("YES");
			return 0;
		}
	}
	printf("NO");
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<locale.h>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long int ll;
 
int main()
{
 int N;
 scanf("%d",&N);
 if(N==1){printf("Hello World");}
 if(N==2){int a,b; scanf("%d %d",&a,&b); a+=b; printf("%d",a);}
} 

Measured memory_bytes: 3796
#include <iostream>
#include <algorithm>

using namespace std;

/*
 * 
 */
int main(int argc, char** argv) {
    int n;
    char deck[200];
    cin >> n;
    while(n!=0){
        cin >> deck;

        int f=0,p[10]={0};
        for(int i=0;i<100;i++){
            switch(deck[i]){
                case 'M':
                    p[i%n]++;
                    break;
                case 'S':
                    f += p[i%n]+1;
                    p[i%n] = 0;
                    break;
                case 'L':
                    p[i%n] += f+1;
                    f = 0;
                    break;
            }
        }
        
        sort(p,p+n);
        for(int i=0;i<n;i++){
            cout << p[i] << " ";
        }
        cout << f << endl;
        cin >> n;
    }
    
    return 0;
}

Measured memory_bytes: 3144
import java.util.Scanner;


public class Main {
	public static void main(String args[])
	   {
	      String x,y;
	      x="";
	      y="";
	      Scanner in = new Scanner(System.in);
	      x = in.nextLine();
	 
	      int l = x.length();
	 
	      for ( int i = l - 1 ; i >= 0 ; i-- )
	         y = y + x.charAt(i);
	 
	      System.out.println(y);
	   }}

Measured memory_bytes: 17128
#include <iostream>
#include <numeric>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)




int main() {
	int N, M;
	cin >> N >> M;
	cout << N * (N - 1) / 2 + M * (M - 1) / 2 << endl;

	
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <map>
#include <cstdio>
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  set<int> X_, Y_;
  vector< pair<int,int> > x_y(n);
  int x, y;
  for(int i = 0; i < n; ++i){
    cin >> x >> y;
    X_.insert(x);
    Y_.insert(y);
    x_y[i] = make_pair(x,y);
  }
  vector<int> X, Y;
  for(set<int>::iterator itr = X_.begin(); itr != X_.end(); ++itr)
    X.push_back(*itr);
  for(set<int>::iterator itr = Y_.begin(); itr != Y_.end(); ++itr)
    Y.push_back(*itr);

  map<int,int> M_x, M_y;
  for(int i = 0; i < X.size(); ++i) M_x[X[i]] = i;
  for(int i = 0; i < Y.size(); ++i) M_y[Y[i]] = i;
  int h = X.size(), w = Y.size();
  vector< vector<int> >  acum(h+2,vector<int>(w+2,0));
  for(int i = 0; i < n; ++i){
    int x = x_y[i].first, y = x_y[i].second;
    ++acum[M_x[x]+1][M_y[y]+1];
  }
  
  
  for(int i = 1; i <= h+1; ++i){
    for(int j = 1; j <= w+1; ++j){
      acum[i][j] += acum[i][j-1];
    }
    for(int j = 1; j <= w+1; ++j){
      acum[i][j] += acum[i-1][j];
    }
  }
  int x_1, x_2, y_1, y_2;
  for(int i = 0; i < m; ++i){
    cin >> x_1 >> y_1 >> x_2 >> y_2;
    int x_1_ = lower_bound(X.begin(),X.end(),x_1)-X.begin(),
      y_1_ = lower_bound(Y.begin(),Y.end(),y_1)-Y.begin(),
      x_2_ = upper_bound(X.begin(),X.end(),x_2)-X.begin(),
      y_2_ = upper_bound(Y.begin(),Y.end(),y_2)-Y.begin();
    cout << acum[x_2_][y_2_] - acum[x_2_][y_1_] - acum[x_1_][y_2_] + acum[x_1_][y_1_] << endl;
  }
  return 0;
}



Measured memory_bytes: 101864
import math
MOD = 1000000007
N = int(input())
d_p = dict()
d_m = dict()
zz = 0
for n in range(N):
    a,b = map(int,input().split())

    if a==0 and b==0:
        zz += 1
        continue
    if a==0:
        n_sign = 0
        a=0
        b=0
    elif b==0:
        n_sign = 1
        a=0
        b=0  


    else:    
        n_sign = ((a<0) + (b<0))%2
        a = abs(a)
        b = abs(b)
        gcd = math.gcd(a,b)
        a//=gcd
        b//=gcd
        #print(n_sign,a,b)

    

    if n_sign==1:
        s =str(b)+'/'+str(a)
        d_m[s] = d_m.get(s,0) + 1
    elif n_sign==0:
        s =str(a)+'/'+str(b)
        d_p[s] = d_p.get(s,0) + 1      
    
#print (d_m,d_p)

ans = 1
for k,v in d_m.items():
    if k in d_p:
        ans *= (2**v + 2**d_p[k] - 1)
        
        d_p.pop(k)
    else:
        ans *= 2**v
    ans %= MOD

for k,v in d_p.items():
    ans *= 2**v
    ans %= MOD
ans -= 1
ans += zz
ans %= MOD
print (ans)


Measured memory_bytes: 38360
n = int(input())
red_list = []
blue_list = []

for i in range(n):
    x, y = map(int, input().split())
    red_list.append([x, y])
for i in range(n):
    x, y = map(int, input().split())
    blue_list.append([x, y])

#2. search
#2.1 red:descending order in y
red_list.sort(key=lambda x:(x[1], x[0]), reverse=True)

#2.2 blue: ascending order
blue_list.sort(key=lambda x:(x[0], x[1]), reverse=False)

#2.3 search a blue point such as [x_r, y_r] < [x_b, y_b]
ans = 0
for red in red_list:
    for blue in blue_list:
        if (red[0]<blue[0]) and (red[1]<blue[1]):
            blue_list.remove(blue)
            ans += 1
            break

#3. print the result
print(ans)

Measured memory_bytes: 3064
# -*- coding: utf-8 -*-

N = int(input())
A = [int(w) for w in input().split()]
if len(A) != N: raise

x = A[0]
s = A[0]
left = [0] * N  # left[r] = min{l | (l,r)が条件を満たす}
for i in range(1, N):
    x ^= A[i]
    s += A[i]
    left[i] = left[i-1]
    while x != s:
        x ^= A[left[i]]
        s -= A[left[i]]
        left[i] += 1

# numl[r] = (l,r)が条件を満たすようなlの個数
numl = [i - left[i] + 1 for i in range(N)]

print(sum(numl))


Measured memory_bytes: 23560
#include<iostream>
using namespace std;
long long solve(long long n,long long x)
{
	long long ans=0;
	if(n%x==0)
	{
		return n/x*x*2-x;
	}
	else ans=n/x*x*2+solve(x,n%x);
	return ans;
}
int main ()
{
	long long n,x;
	cin>>n>>x;
	cout<<n+solve(max(n-x,x),min(n-x,x));
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		
	Scanner sc = new Scanner(System.in);
	
	while(true){
		int a = sc.nextInt();
		String op = sc.next();
		int b = sc.nextInt();
		
		if(op.equals("?"))break;
		
		int sum = 0;
		
		switch(op){
		case "+":
		  sum = a+b;
		  break;
		  
		case "-":
		sum = a-b;
		break;
		
		case "*":
			sum = a*b;
			break;
			
		case "/":
			sum = a/b;
			break;
	
	}
	System.out.println(sum);
	}
	sc.close();
}
}


Measured memory_bytes: 26248
import java.util.*;


public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();
        String[] arr = sc.nextLine().split(" ");
        int sum = 0;
        for(int i = 0; i< arr.length ; i++){
            sum += Integer.parseInt(arr[i]);
        }
        if(n - sum >= 0){
            System.out.println(n-sum);
        }else{
            System.out.println(-1);
        }
    }

}


Measured memory_bytes: 39452
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int i = 0;
    int ans = 0;
    for(i=0;i<s.length()/2;i++){
      if(s.charAt(i) != s.charAt(s.length()-i-1))ans++;
    }
    System.out.println(ans);
  }
}


Measured memory_bytes: 21712
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(ll i = (ll)a;i < (ll)b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(ll i = (ll)b-1LL;i >= (ll)a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define SIGN(a) (a==0?0:(a>0?1:-1))

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef long double ld;
typedef pair<ld,ld> pdd;

const ll INF=(1LL<<50);
#if __cplusplus<201700L
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
template<class T>
bool chmax(T& a,const T& b){
  if(a<b){
    a=b;
    return true;
  }
  return false;
}
template<class T>
bool chmin(T& a,const T& b){
  if(a>b){
    a=b;
    return true;
  }
  return false;
}
template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}

class UF{
  vector<long> par,rank,size_uf;
  long _chunk_size;
public:
  UF(long size):_chunk_size(size){
    for (long i = 0; i < size; i++) {
      par.push_back(i);
      rank.push_back(0);
      size_uf.push_back(1);
    }
  }
  long find(long x){
    if(par[x]==x)return x;
    return par[x]=find(par[x]);
  }
  void unite(long x,long y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    --_chunk_size;
    if(rank[x]<rank[y]){
      par[x]=y;
      size_uf[y]+=size_uf[x];
    }
    else{
      par[y]=x;
      size_uf[x]+=size_uf[y];
      if(rank[x]==rank[y])rank[x]++;
    }
  }
  bool same(long x,long y){
    return find(x)==find(y);
  }
  long operator [](long x){
    return this->find(x);
  }
  long size(long x){
    x=find(x);
    return size_uf[x];
  }
  long chunk_size(){
    return this->_chunk_size;
  }
};


void solve(long long N, long long M, std::vector<long long> X, std::vector<long long> Y, std::vector<long long> Z){
  UF uf(N);
  REP(M){
    uf.unite(X[i],Y[i]);
  }
  cout<<uf.chunk_size()<<endl;
}

int main(){
  cout<<setprecision(1000);
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> X(M);
    std::vector<long long> Y(M);
    std::vector<long long> Z(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&X[i]);
        scanf("%lld",&Y[i]);
        scanf("%lld",&Z[i]);
        --X[i];--Y[i];
    }
    solve(N, M, std::move(X), std::move(Y), std::move(Z));
    return 0;
}


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

int main(){
	long long int a,b,c,k;
  	cin >> a >> b >> c >> k;
  	if (abs(a-b)>100000000000000000)cout << "Unfair" <<endl;
  	else if(k%2==0)cout << a-b << endl;
  	else cout << b-a <<endl;
}

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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

constexpr ll INF = 1'000'000'000'000'000'000;
int N;
ll A[100100];

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

  std::cin >> N;

  for(int i=0;i<N;++i){
      std::cin >> A[i];
  }

  if(std::count(A, A + N, 0) > 0){
      std::cout << 0 << std::endl;
      return 0;
  }

  ll res = 1;

  for(int i=0;i<N;++i){
      if(res <= INF / A[i]){
          res *= A[i];
      }else{
          res = -1;
          break;
      }
  }

  std::cout << res << std::endl;
}


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

int main(){
  int a,b,c,d,e;
  cin >> a >> b;
  c = a+b;
  d = a-b;
  e = a*b;
  if(c > d && c > e){
    cout << c << endl;
  }else if(d > c && d > e){
    cout << d << endl;
  }else if(e > c && e > d){
    cout << e << endl;
  }else{
    cout << c << endl;
  }
}

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

#define ll long long
#define ull unsigned long long
#define ld long double

#define tiii tuple < int, int, int >
#define pii pair < int, int >
#define pll pair < ll, ll >
#define pci pair < char, int >
#define psi pair < string, int >
#define pis pair < int, string >

#define vi vector < int >
#define vd vector < double >
#define vld vector < ld >
#define vll vector < ll >
#define vs vector < string >
#define vc vector < char >
#define vpi vector < pii >
#define vpll vector < pll >
#define vpis vector < pis >

#define pb push_back
#define mt make_tuple
#define gt0 get < 0 >
#define gt1 get < 1 >
#define gt2 get < 2 >

#define pi acos(-1)

#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

using namespace std;

const int maxn = 1e5 + 5;
const int mod = 1e9 + 9;

ll a[maxn], b[maxn], c[maxn], f[maxn][5];

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    fast;

    int n;

    cin >> n;

    for(int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];

    f[1][1] = a[1];
    f[1][2] = b[1];
    f[1][3] = c[1];

    for(int i = 2; i <= n; i++){
        f[i][1] = max(f[i - 1][2], f[i - 1][3]) + a[i];
        f[i][2] = max(f[i - 1][1], f[i - 1][3]) + b[i];
        f[i][3] = max(f[i - 1][1], f[i - 1][2]) + c[i];
    }

    cout << max(f[n][1], max(f[n][2], f[n][3])) << endl;

    return 0;
}


Measured memory_bytes: 9840
package main

import "fmt"

func main() {
	var inputRow, inputCol, inputCorrect int
	fmt.Scanf("%d", &inputRow)
	fmt.Scanf("%d", &inputCol)
	fmt.Scanf("%d", &inputCorrect)

	m := inputRow
	if inputRow < inputCol {
		m = inputCol
	}
	ans := int(inputCorrect / m)

	if inputCorrect%m != 0 {
		ans++
	}
	fmt.Printf("%d\n", ans)
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const int MAX = 510000;

int main() {
  ll N;
  string S;
  cin >> N >> S;
  ll numR = count(S.begin(), S.end(), 'R');
  ll numG = count(S.begin(), S.end(), 'G');
  ll numB = count(S.begin(), S.end(), 'B');
  ll res = numR*numG*numB;
  for (ll i=0; i<N-1; i++) {
    for (ll j=i; j<N; j++) {
      if (2*j-i<N) {
        ll k = 2*j-i;
        if (S[i]!=S[j]&&S[i]!=S[k]&&S[j]!=S[k]) res--;
      }
    }
  }
  cout << res << endl;
}


Measured memory_bytes: 3588
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include<iomanip>

using namespace std;
typedef long long ll;

int main() {
	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++) cin >> A[i];
	vector<int> B(N);
	for (int i = 0; i < N; i++) B[i] = A[i];
	sort(B.begin(), B.end());
	for (int i = 0; i < N; i++) {
		if (A[i] == B[N - 1]) cout << B[N - 2] << endl;
		else cout << B[N - 1] << endl;
	}
}


Measured memory_bytes: 4844
from itertools import permutations
n, m = map(int, input().split())
v = [set(map(int, input().split())) for _ in range(m)]

ans = 0
x = [i for i in range(2, n+1)]
cand = permutations(x)
for i in cand:
    crnt = 1
    for nxt in i:
        if set([crnt, nxt]) in v:
            crnt = nxt
        else:
            break
    else:
        ans += 1
print(ans)


Measured memory_bytes: 3064
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
const int N = 2e5+5;
int arr[N];


int main()
{
    string s,t;
    cin>>s>>t;
    int cha = s.size()-t.size();
    int max_=0;
    for(int i =0;i<cha;i++)
    {
        int max2=0;
        for(int j =0;j<t.size();j++)
        {
            if(t[j]==s[i+j])
                max2++;
        }
        if(max2>max_)
            max_=max2;
    }
    if(cha==0)
    {
        int max2=0;
        for(int j =0;j<t.size();j++)
        {
            if(t[j]==s[j])
                max2++;
        }
        if(max2>max_)
            max_=max2;
    }
    cout<<t.size()-max_;
    
    
}


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

typedef long long ll;

int main() { 
	string s1, s2;
	cin >> s1 >> s2;
	sort(s1.begin(),s1.end());
	sort(s2.rbegin(),s2.rend());
	if (s1 < s2) {
		cout << "Yes";
	}else {
		cout << "No";
	}
}


Measured memory_bytes: 256
# coding:utf-8

N, W = (int(x) for x in input().split())
w = [0 for x in range(N)]
v = [0 for x in range(N)]
for i in range(N):
	w[i], v[i] = (int(x) for x in input().split())

dp = [[0 for x in range(W+1)] for y in range(N+1)]

for i in range(1, N+1):
	for j in range(W+1):
		# 品物を選ばない
		dp[i][j] = max(dp[i][j], dp[i-1][j])
		# 品物を選ぶ
		if j - w[i-1] >= 0:
			dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1])

print(dp[N][W])

Measured memory_bytes: 171784
N = int(input())
L = sorted(list(map(int, input().split())))
M = list(set(L))

cnt = 0

if len(M) >= 3:
  for i in range(N):
    for j in range(i+1, N):
      for k in range(j+1, N):
        if L[i] != L[j] and L[j] != L[k] and L[i]+L[j] >  L[k]:
          cnt += 1
print(cnt)

Measured memory_bytes: 73308
n = int(input())
p = tuple(map(int,input().split()))
q = tuple(map(int,input().split()))
seq = [i+1 for i in range(n)]
# a = 0
# b = 0
from itertools import permutations
per = list(permutations(seq,n))
# for i in range(len(per)):
#     if per[i] == p:
#         a = i
#     if per[i] == q:
#         b = i
print(abs(per.index(p)-per.index(q)))

Measured memory_bytes: 8052
# -*- coding: utf-8 -*-
"""
B - Foods Loved by Everyone
https://atcoder.jp/contests/abc118/tasks/abc118_b

"""
import sys


def main(args):
    N, M = map(int, input().split())
    ans = set(range(1, M+1))
    for _ in range(N):
        _, *a = map(int, input().split())
        ans &= set(a)
    print(len(ans))


if __name__ == '__main__':
    main(sys.argv[1:])


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

#define mod 1000000007
#define ll long long

ll bow(ll x, ll y) {
  ll res = 1;
  for (ll i = 1; i <= y; ++i) {
    res = res * x % mod;
  }
  return res;
}

void solve() {
  ll n;
  cin >> n;
  ll ans = bow(10, n) - bow(9, n) - bow(9, n) + bow(8, n);
  ans %= mod;
  ans = (ans + mod) % mod;
  cout << ans << endl;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}

Measured memory_bytes: 3616
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#define dlog(str) cout << "====" << str << endl;
#else
#define dlog(str)
#endif
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
#define FOR(i, s, e) for(int i = s, i##_l = (e); i < i##_l; i++)
#define LLI long long int
#define _min(a,b) ((a<b)?a:b)
#define _max(a,b) ((a<b)?b:a)
#define chmax(a, b) a = _max(a, b)
#define chmin(a, b) a = _min(a, b)
#define bit(a, shift) ((a>>shift)&1))
#define pm(a) ((a)?1:-1)
#define SORT(v) sort(v.begin(),v.end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
// int 2.14E±9    lli 9.2E±18    double 1.7E±380


const int COMMAX = 210000;
long long fac[COMMAX], finv[COMMAX], inv[COMMAX];
void COMinit()
{
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < COMMAX; i++)
	{
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}
long long COM(int n, int k)
{
	if (n < k)
		return 0;
	if (n < 0 || k < 0)
		return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main()
{
	COMinit();
	cout << fixed << setprecision(10);
	LLI n, k;
	cin >> n >> k;
	if (k == 1)
	{
		cout << 0;
		return 0;
	}
	vector<LLI> a(n);
	REP(i, n)cin >> a[i];
	SORT(a);

	LLI ans = 0;

	LLI ma = 0;
	LLI mi = 0;
	REP(i, n)
	{
		ma = (ma + ((COM(i, k - 1) % MOD) * a[i]) % MOD) % MOD;
		mi = (mi + ((COM(n - i - 1, k - 1) % MOD) * a[i]) % MOD) % MOD;
		ma = ma;
	}
	cout << (ma - mi + MOD) % MOD;

	return 0;
}

Measured memory_bytes: 5888
import java.util.*;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int W = sc.nextInt();
		int H = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        int r = sc.nextInt();

		if((-100<=x && x<=100) && (-100<=y && y<=100) && ((0<W && W<=100) && (0<H && H<=100) && (0<r && r<=100))){
            if(x-r<0 || x+r>W || y-r<0 || y+r>H){
                System.out.println("No");
            }
            if(x-r>=0 && x+r<=W && y-r>=0 && y+r<=H){
                System.out.println("Yes");
            }
        }

	}
}


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

int64_t MOD = 1000000007;
int64_t MAX = 9223372036854775807;
double PI = 3.141592653589793;

int main()
{
    int64_t N;
    cin >> N;
    cout << (N * (N - 1)) / 2;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,D,X;
  cin>>N>>D>>X;
  vector<int> S(N);
  for(int i=0;i<N;i++){
    cin>>S.at(i);
    X = X+(D-1)/S.at(i)+1;
  }
cout<<X<<endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<string>
#include<assert.h>
#include<sstream>
using namespace std;
#define pb push_back
#define mp make_pair
#define sz(x) ((int)(x).size())
#define rep(i,l,r) for(int i=(l);i<(r);++i)
#define setIO(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
typedef long long ll;
typedef pair<int, int> pii;
const ll LINF = 1e18 + 7;
const int N = 1e5 + 7;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
//-------------head-------------
int n, m, L, x[N], f[N][20];
int main() {
	scanf("%d", &n);
	rep(i, 1, n + 1)
		scanf("%d", &x[i]);
	scanf("%d", &L);
	for (int i = n, sum = 0, p = n; i > 0; --i) {
		while (sum > L) {
			sum -= x[p] - x[p - 1];
			--p;
		}
		f[i][0] = p, sum += x[i] - x[i - 1];
	}
	for (int j = 1; j < 20; ++j)
		for (int i = n; i >= 1; --i)
			f[i][j] = f[f[i][j - 1]][j - 1];
	scanf("%d", &m);
	rep(_m, 0, m)
	{
		int l, r, ans = 0;
		scanf("%d%d", &l, &r);
//		printf("l = %d, r = %d\n", l, r);
		if (l > r)
			swap(l, r);
		for (int i = 19; i >= 0; --i)
			if (f[l][i] < r) {
				ans += 1 << i, l = f[l][i];
//				printf("%d ", l);
			}
		++ans;
		printf("%d\n", ans);
	}
	return 0;
}


Measured memory_bytes: 8960
// EducationalDpContest.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

//A
//int main()
//{
//	int n, h;
//	std::vector<int> heights;
//
//	cin >> n;
//	for (int i = 0; i < n; ++i)
//	{
//		cin >> h;
//		heights.push_back(h);
//	}
//
//	vector<int> m(n, 0);
//	m[0] = 0;
//	m[1] = abs(heights[1] - heights[0]);
//
//	for (int i = 2; i < n; ++i)
//	{
//		m[i] = min(m[i - 2] + abs(heights[i] - heights[i - 2]), m[i - 1] + abs(heights[i] - heights[i - 1]));
//	}
//
//	cout << m[n - 1];
//}


//B
int main()
{
	int n, k, h;
	std::vector<int> heights;

	cin >> n >> k;
	for (int i = 0; i < n; ++i)
	{
		cin >> h;
		heights.push_back(h);
	}

	vector<int> m(n, 0);
	m[0] = 0;	

	for (int i = 1; i < n; ++i)
	{
		int m_min = INT_MAX;
		for (int j = 1; j <= k; ++j)
		{
			if (i - j < 0) break;
			int m_cur = m[i - j] + abs(heights[i] - heights[i - j]);
			if (m_cur < m_min) m_min = m_cur;
		}
		m[i] = m_min;
	}

	cout << m[n - 1];
}


Measured memory_bytes: 1144
#include <iostream>
#include <algorithm>
using namespace std;

long long N, A[1 << 18], B[1 << 18], sum = 0, minx = (1LL << 60);

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i] >> B[i]; sum += A[i];
		if (A[i] > B[i]) minx = min(minx, B[i]);
	}
	if (minx == (1LL << 60)) cout << "0" << endl;
	else cout << sum - minx << endl;
	return 0;
}

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

int N;
char w_end;
set<string> M;

bool check(int k, string s) {
	int len = s.length();
	if (k == 0) {
		w_end = s[len - 1];
		M.insert(s);
		return true;
	}
	if (M.count(s) != 0)
		return false;
	M.insert(s);
	char w_top = s[0];
	if (w_top != w_end)
		return false;
	w_end = s[len - 1];
	return true;
}

int main(void) {
	cin >> N;

	bool ans = true;
	for (int i = 0; i < N; ++i) {
		string w;
		cin >> w;
		if (ans && !check(i, w))
			ans = false;
	}

	cout << (ans ? "Yes\n" : "No\n");
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1LL << 30;
int MOD = 1e9+7;
main(){
    ll N;
    cin >> N;
    ll maxi = 0,d = 10;
    while(N >= 1){
        ll num = N,cnt = 0;
        while(num){
            cnt += num % 10;
            num /= 10;
        }
        maxi = max(maxi, cnt);
        N -= N % d + 1;
        d *= 10;
    }
    cout << maxi << endl;
}

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

#define MOD 1000000007

int dp[1100][1100];
char grid[1100][1100];

int main() {
  int h, w;
  cin >> h >> w;
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      cin >> grid[i][j];
    }
  }

  dp[1][1] = 1;
  for (int i = 1; i <= h; i++) {
    for (int j = 1; j <= w; j++) {
      if (grid[i][j] == '#') {
        continue;
      }
      dp[i][j] += (dp[i][j - 1] + dp[i - 1][j])%MOD;
    }
  }
  cout << dp[h][w] << endl;
  return 0;
}

Measured memory_bytes: 5632
import bisect
horigin,worigin,m = map(int,input().split())
dich = {}
dicw = {}
 
havew = {}
for _ in range(m):
    h,w = map(int,input().split())
    if h in dich:
        dich[h] += 1
        havew[h].append(w)
    else:
        dich[h] = 1
        havew[h] = [w]
    if w in dicw:
        dicw[w] += 1
    else:
        dicw[w] = 1
 
dichi = list(dich.items())
dichi.sort(reverse=True, key=lambda x:x[1])
dicwi = list(dicw.items())
dicwi.sort(reverse=True, key=lambda x:x[1])
 
# print(havew)
#
# print(dichi)
# print(dicwi)
 
hmax = dichi[0][1]
wmax = dicwi[0][1]
 
for hs in dichi:
    if hs[1] != hmax:
        break
    wlis = sorted(havew[hs[0]])
    for ws in dicwi:
        if ws[1] != wmax:
            break
        idx = bisect.bisect_left(wlis, ws[0])
        if idx >= len(wlis):
            print(hmax+wmax)
            exit()
        if ws[0] != wlis[idx]:
            print(hmax+wmax)
            exit()
print(hmax+wmax-1)
 


Measured memory_bytes: 127584
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
using namespace std;
#define REP(i, a, n) for(int i=a; i<n; i++)
#define MP(a, b) make_pair(a, b)
#define F first
#define S second

int main() {
	int T, P, R; // team, problem, log
	while (cin >> T >> P >> R, T || P || R) {
		pair<bool, int> val[51][11]; // <correct, penalty>=[team, problem]
		REP(i, 0, T) REP(j, 0, P) val[i][j] = MP(false, 0);

		REP(i, 0, R) {
			int team, prob, time;
			string mes;
			cin >> team >> prob >> time >> mes;
			team--;
			prob--;

			if (mes == "WRONG") {
				val[team][prob].S += 1200;
			}
			else {
				val[team][prob].F = true;
				val[team][prob].S += time;
			}
		}

		pair<int, pair<int, int>> ans[51]; // <#correct, <penalty, team>>
		REP(i, 0, T) ans[i] = MP(0, MP(0, i + 1));
		REP(i, 0, T) {
			REP(j, 0, P) {
				if (val[i][j].F) {
					ans[i].F--;
					ans[i].S.F += val[i][j].S;
				}
			}
		}

		sort(ans, ans + T);
		REP(i, 0, T) cout << ans[i].S.S << " " << -ans[i].F << " " << ans[i].S.F << endl;
	}
	return 0;
}

Measured memory_bytes: 3148
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; 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;
}

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------
ll H, W;

int main()
{
    cin >> H >> W;
    if (H == 1 || W == 1)
    {
        cout << 1 << endl;
        return 0;
    }

    if (W % 2 == 0)
    {
        ll ans = (H + 1) / 2 * (W / 2) + (H / 2) * (W / 2);
        cout << ans << endl;
    }
    else
    {
        ll ans = (H + 1) / 2 * (W / 2 + 1) + (H / 2) * (W / 2);
        cout << ans << endl;
    }
}


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

int find(int n) {

	int sum = 0;
	while (n > 0) {
		sum += n % 10;
		n /= 10;
	}
	return sum;
}


int main() {
	int a, b, n;
	cin >> n >> a >> b;
	int ans = 0;
	int tmp = 0;

	for (int i = 1; i <= n; i++) {
		tmp = find(i);
		if (a <= tmp && tmp <= b) {
			ans += i;
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

enum inf = 1_001_001_001;
enum infl = 1_001_001_001_001_001_001L;


void main() {
    while (true) {
        int N;
        scan(N);

        if (N == 0) return;

        auto w = readln.split.to!(int[]);
        auto ans = solve(N, w);
        writeln(ans);
    }
}

int solve(int N, int[] w) {
    auto dp = new int[][](N + 1, N + 1);
    fillAll(dp, -1);

    int rec(int l, int r) {
        if (r - l <= 1) {
            return 0;
        }
        if (dp[l][r] != -1) {
            return dp[l][r];
        }
        dp[l][r] = 0;
        foreach (i ; l + 1 .. r) {
            chmax(dp[l][r], rec(l, i) + rec(i, r));
        }
        if (rec(l + 1, r - 1) == r - 1 - (l + 1) && abs(w[l] - w[r - 1]) <= 1) {
            dp[l][r] = r - l;
        }
        return dp[l][r];
    }

    auto ans = rec(0, N);
    return ans;
}












void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}



Measured memory_bytes: 11060
#include<bits/stdc++.h>
#define int long long

using namespace std;

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

    int n, a, b;
    cin >> n >> a >> b;

    if ((b - a) % 2)
    {
        int t = n - b, tt = a - 1;
        int aa = a + t, bb = b - tt;

        cout << min(t + (n - aa + 1) / 2, tt + bb / 2) << '\n';
    }
    else
        cout << (b - a) / 2 << '\n';

    return 0;
}

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


Measured memory_bytes: 384
// -> limitless <- //
#include <bits/stdc++.h>
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PB push_back
#define MP make_pair
using namespace std;
typedef  long long ll;
    const int N = 2e5 + 100 ;
int main()
{
  ll n;
  cin >> n;
  ll arr[N + 1] ={} ;
    for(int i = 0; i<n ;i++ ){
        cin >> arr[i];
        arr[i]-=(i+1);
    }
    sort(arr, arr+n);
    ll md = arr[n/2];
    ll res = 0;
    for(int i = 0; i<n ;i++){
        res += abs(arr[i]-md);
    }
    cout << res;
    return 0;
}


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

const int MAXN = 100005;

int n, a[MAXN];
long long R[MAXN];

int main(){
	scanf("%d", &n);
	
	for(int i = 0; i <= n; i++){
		scanf("%d", &a[i]);
		
		if(i == 0){
			R[i] = 1;
		}else{
			R[i] = (R[i - 1] - a[i - 1]) * 2;
		}
		R[i] = min(R[i], 1LL << 60);
		
		if(R[i] < a[i]){
			printf("-1\n");
			return 0;
		}
	}
	
	long long res = 0, c = a[n];
	for(int i = n; i >= 0; i--){
		res += c;
		
		if(i > 0){
			c = min(c + a[i - 1], R[i - 1]);
		}
	}
	printf("%lld\n", res);
		
	return 0;
}


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

using ll = long long;
const int maxn = 100000 + 5;
int N, M;
int P[maxn];
int Y[maxn];
vector<int> vec[maxn];

int main()
{
	cin >> N >> M;
	for(int i = 0; i < M; i++) cin >> P[i] >> Y[i], vec[P[i]].push_back(Y[i]);
	for(int i = 0; i < N; i++) sort(vec[i+1].begin(), vec[i+1].end());
	for(int i = 0; i < M; i++) printf("%012lld\n", ll(P[i])*1000000 + int(lower_bound(vec[P[i]].begin(), vec[P[i]].end(), Y[i])-vec[P[i]].begin())+1);
}

Measured memory_bytes: 7808
// ?????¬???????????¬??????

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int

template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}

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

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;

// calculate vector x which satisfy Ax = b
// (A is N*N Matrix, b, x is N-dim vector)

template <typename T>
using Matrix = vector< vector<T> >;
constexpr double EPS = 1e-8;

template <typename T>
vector<double> gauss_jordan(const Matrix<T> &A, const vector<T> &b) {
    int N = A.size();
    // B = [A b]
    Matrix<double> B(N, vector<double>(N+1));
    for(int i=0; i<N; i++) {
        for(int j=0; j<=N; j++) {
            if(j < N) B[i][j] = A[i][j];
            else B[i][j] = b[i];
        }
    }

    for(int i=0; i<N; i++) {
        int pivot = i;
        for(int j=i+1; j<N; j++) {
            if(abs(B[j][i]) > abs(B[pivot][i])) pivot = j;
        }
        swap(B[i], B[pivot]);

        // pivot is zero -> No solution or Not unique
        // assert(abs(B[i][i]) >= EPS);

        for(int j=i+1; j<=N; j++) B[i][j] /= B[i][i];
        for(int j=0; j<N; j++) {
            if(i != j) {
                for(int k=i+1; k<=N; k++) B[j][k] -= B[j][i] * B[i][k];
            }
        }
    }
    vector<double> x(N);
    for(int i=0; i<N; i++) x[i] = B[i][N];
    return x;
}

double pos[5][3];
signed main() {
    rep(i,0,5) rep(j,0,3) cin >> pos[i][j];

    Matrix<double> mat(3, vector<double>(3));
    vector<double> vec(3);

    rep(i,0,3) {
        mat[i][0] = pos[3][i] - pos[2][i];
        mat[i][1] = pos[4][i] - pos[2][i];
        mat[i][2] = pos[0][i] - pos[1][i];
    }
    rep(i,0,3) vec[i] = pos[0][i] - pos[2][i];

    vector<double> ans = gauss_jordan(mat, vec);
    if(ans[0] < -EPS || ans[1] < -EPS || ans[2] < -EPS) cout << "HIT" << endl;
    else if(ans[0] + ans[1] > 1.0 + EPS || ans[2] > 1.0 + EPS) cout << "HIT" << endl;
    else cout << "MISS" << endl;
    return 0;
}

Measured memory_bytes: 3284
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

H = [[b < a for b in A[:i]].count(True) for i, a in enumerate(A)]  # hukkisuu
T = [[b < a for b in A[i+1:]].count(True) for i, a in enumerate(A)]  # tentousuu

print(sum(h*K*(K-1)//2 + t*K*(K+1)//2 for h, t in zip(H, T)) % MOD)


Measured memory_bytes: 3188
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)

using namespace std;
#define ll long long

ll S(ll n){
  ll m = n;
  ll sum = 0;
  while(m > 0){
    sum += m % 10;
    m /= 10;
  }
  return sum;
}

int main(){
  ll N;
  cin >> N;
  if(N % S(N) == 0)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
import sys
from collections import deque
p=10**9+7

def main(n,a):
  h=n//2
  g=n%2
  a.sort()
  c=[2*(x//2)+g+1 for x in range(n-g)]
  if g==1:
    c.insert(0,0)
  if a!=c:
      return 0
  return 2**(h%(p-1)) % p

if __name__=='__main__':
  n=int(input())
  a=list(map(int,sys.stdin.readline().strip().split()))
  print(main(n,a))
  

Measured memory_bytes: 20740