akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include<iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#define INF 1e9+7
#define rep(i,m,n) for(int i=m;i<n;i++)
#define mrep(i,m,n) for(int i=m;i>n;i--)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;


//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない

int main() {

	int n;
	ll ans = 0;
	int a[200000];

	cin >> n;
	rep(i, 0, n) {
		cin >> a[i];
		a[i] = a[i] - (i + 1);
	}

	sort(a, a + n);

	int b;
	if (n % 2 == 0) {
		b = (a[n / 2 - 1] + a[n / 2]) / 2;
	}
	else {
		b = a[n / 2];
	}

	rep(i, 0, n) {
		ans += abs(a[i] - b);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, x, y;
    cin>>n>>x>>y;
    int a[n] = {0};
    for (int i = 1; i < n; i++) {
    	for (int j = i + 1; j <= n; j++) {
    		int dis = min(j - i, (abs(x - i) + abs(y - j) + 1));
    		a[dis]++;
		}
	}
	for (int i = 1; i < n; i++) cout<<a[i]<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
int ask(int i){
  cout<<i<<endl;
  string s;
  cin>>s;
  if(s[0]=='M')return 1;
  else if(s[0]=='F')return 0;
  return -1;
}
void solve(int l,int r,int x,int y){
  int mid=(l+r)>>1;
  int z=ask(mid);
  if(z==-1)return;
  if((mid-l+1)%2==1){
    if(x==z)solve(mid,r,z,y);
    else solve(l,mid,x,z);
  }
  else{
    if(x!=z)solve(mid,r,z,y);
    else solve(l,mid,x,z);
  }
}
int main(){
  
  int n;
  cin>>n;
  int x=ask(0);
  if(x==-1)return 0;
  int y=ask(n-1); 
  if(y==-1)return 0;
  solve(0,n-1,x,y);
  return 0;
}


Measured memory_bytes: 852
#include <cmath>
#include <iostream>
#include <iomanip>
using namespace std;

int main(){
	double x1,y1,x2,y2;
	cin>>x1>>y1>>x2>>y2;
	cout << fixed << setprecision(9) << sqrt((x1-x2)*(x1-x2)+(y2-y1)*(y2-y1)) << endl;
	return 0;
}

Measured memory_bytes: 1280
//#include "pch.h"
#include<stdio.h>
//#include<string.h>

int main()
{
	int H, W, h, w;
	//scanf_s("%d %d", &H, &W);
	//scanf_s("%d %d", &h, &w);
	scanf("%d %d", &H, &W);
	scanf("%d %d", &h, &w);
	printf("%d", (H - h)*(W - w));


	return(0);
}



Measured memory_bytes: 128
n,m,*t=map(int,open(0).read().split());a,c=[0]*-~n,0
for l,r in zip(t[::2],t[1::2]):a[l-1]+=1;a[r]-=1
for i in range(n):a[i+1]+=a[i];c+=a[i]==m
print(c)

Measured memory_bytes: 82800
n = int(input())
a_list = list(map(int, input().split()))
abs_max = 0
for i in range(len(a_list)-1):
    for j in range(i+1, len(a_list)):
        abs_max = max(abs_max, abs(a_list[i]- a_list[j]))
print(abs_max)

Measured memory_bytes: 38896
#include <iostream>
#include <iomanip>
#include <math.h>

using namespace std;

int main()
{
	int a, b, C;
	double S, L, h, r, p = 3.141592653589793;

	cin >> a >> b >> C;

	r = C * p / 180.0;
	S = (a * b * sin(r)) / 2;
	L = a + b + sqrt((a * a) + (b * b) - (2 * a * b * cos(r)));
	h = b * sin(r);

	cout << fixed << S << endl << L << endl << h << endl;

	return 0;
}

Measured memory_bytes: 1240
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, a[200000];
    vector<int> b;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = n - 1; i >= 0; i-=2) b.push_back(a[i]);
    for (int i = n % 2; i < n; i+=2) b.push_back(a[i]);
    for (int i = 0; i < n - 1; i++) cout << b[i] << " ";
    cout << b[n-1] << endl;
}

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

int main() {
  int N;
  cin >> N;
  string S;
  cin >> S;
  int count=1;
  for (int i=0; i<S.size()-1; i++){
    if(S.at(i) == S.at(i+1))
      continue;
    else
      count++;
  }
  cout << count << endl;
}

Measured memory_bytes: 512
a = input()
b = input()
c = input()
first_str = a[0]
a = a[1:]
while(1):
  if first_str == 'a':
    if len(a)==0:
      print('A')
      break
    first_str = a[0]
    a = a[1:]
    
  elif first_str == 'b':
    if len(b)==0:
      print('B')
      break
    first_str = b[0]
    b = b[1:]
    
  elif first_str == 'c':
    if len(c)==0:
      print('C')
      break
    first_str = c[0]
    c = c[1:]
    

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

bool p[10000000];

void erato(){
	fill(p, p+10000000, true);
	p[0] = p[1] = false;

	for(int i=0; i < 10000000; i++){
		if(!p[i]) continue;
		for(int j=i+i; j < 10000000; j+=i){
			p[j] = false;
		}
	}
}

int main(){
	erato();
	int n;

	while(cin >> n, n){
		for(int i=n;; i--){
			if(p[i] && p[i-2] && p[i-6] && p[i-8]){
				cout << i << endl;
				break;
			}
		}
	}
}

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

int main(){
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  
  bool flag = false;
  
  while(true){
    C-=B;
    if(C<=0){
      flag = true;
      break;
    }
    A-=D;
    if(A<=0){
      break;
    }
  }
  if(flag) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

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

  ll n;
  cin >> n;
  map<string, ll> s;
  rep(i, n) {
    string t;
    cin >> t;
    sort(all(t));
    s[t]++;
  }

  ll ans = 0;
  for (auto&& i : s) {
    ans += i.second * (i.second-1) / 2;
  }
  cout << ans << endl;
}


Measured memory_bytes: 11264
#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
#define endl '\n'
using namespace std;


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

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

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

	vector<int> v(3);
	for(auto &i : v) cin >> i;

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

	bool ans = (v[0] + v[1] == v[2]);

	cout << (!ans ? "No" : "Yes") << endl;

	return 0;
}


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

#define ll long long
#define mod 1000000007
#define ffor(i,a,b) for(int i=a;i<b;i++)
#define bfor(i,a,b) for(int i=a-1;i>=b;i--)
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define mem(x,y) memset(x,y,sizeof(x))
#define all(x) x.begin(),x.end()
#define SP(x) setprecision(x)
#define sz(x) (int)x.size()
#define fast  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define PI 3.14159265358979323846
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define endl '\n'

int main()
{
    

    int n;
    cin>>n;
    int a[10]={0};
    while(n>0)
    {
        a[n%10]++;
        n=n/10;
    }
    if(a[7]) cout<<"Yes";
    else cout<<"No";
    
    return 0;
}



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

#define LISTMAX 1000000

struct command {
	char str[20];
	int key;
};

class dlList {
private:
	int list[LISTMAX];
	int head, num;
public:
	dlList();
	void Ins(int);
	void Del(int);
	void DelFirst();
	void DelLast();
	void ShowList();
	void show();
};

dlList::dlList()
	:list()
	,head(0),
	num(0)
{}

void dlList::Ins(int x)
{
	this->head = (head + LISTMAX - 1) % LISTMAX;
	this->num++;
	this->list[head] = x;
	return;
}

void dlList::Del(int x)
{
	int flag = 0;
	for (int i = 0; i < this->num; i++)
		if (list[(head + i) % LISTMAX] == x && !flag)
			flag = 1;
		else if (flag)
			list[(head + i - 1 + LISTMAX) % LISTMAX] = list[(head + i) % LISTMAX];
	this->num -= flag;

	return;
}

void dlList::DelFirst()
{
	this->head = (this->head + 1) % LISTMAX;
	this->num--;
	return;
}

void dlList::DelLast()
{
	this->num--;
	return;
}

void dlList::ShowList()
{
	int tmp;
	tmp = this->head;
	for (int i = 0; i < this->num; i++)
	{
		if (i)
			cout << " ";
		cout << this->list[tmp];
		tmp = (tmp + 1) % LISTMAX;
	}
	cout << endl;
	return;
}

int main()
{
	int n;
	dlList dll;
	command tmp;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> tmp.str;
		if (!strcmp(tmp.str, "insert"))
		{
			cin >> tmp.key;
			dll.Ins(tmp.key);
		}
		else if (!strcmp(tmp.str, "delete"))
		{
			cin >> tmp.key;
			dll.Del(tmp.key);
		}
		else if (!strcmp(tmp.str, "deleteFirst"))
			dll.DelFirst();
		else
			dll.DelLast();
	}
	dll.ShowList();

	return 0;
}


Measured memory_bytes: 7036
a,b,c,d,e,f=map(int,input().split())
ans=[100*min(a,b),0]
for i in range(31):
  for j in range(31):
    if i==0 and j==0:
      break
    l1=f-(100*a*i+100*b*j)
    l2=(a*i+b*j)*e
    l=min(l1,l2)
    cc,dc=0,0
    for k in range(l//c+1):
      tc=k
      td=(l-c*tc)//d
      if l-(c*tc+d*td)<l-(c*cc+d*dc):
        cc,dc=tc,td
    wa=100*a*i+100*b*j
    sa=c*cc+d*dc
    tmp=[wa+sa,sa]
    if wa+sa>f or sa>e*(a*i+b*j):
      break
    if tmp[1]/tmp[0]>ans[1]/ans[0]:
      ans=tmp
print(ans[0],ans[1])

Measured memory_bytes: 3064
import itertools
sx,sy,tx,ty = map(int,input().split())
f = ""
f += abs(tx-sx)*"R" + abs(ty-sy)*"U"
f += abs(tx-sx)*"L" + abs(ty-sy)*"D"

f += "D"

f += (1+abs(tx-sx))*"R" + (1 + abs(ty-sy))*"U"
f += "LU"
f += (1+abs(tx-sx))*"L" + (1+abs(ty-sy))*"D"
f += "R"
print(f)


Measured memory_bytes: 38384
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B, C = [], []
for i in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)
data = {}
SUM = sum(A)
for i in range(N):
    if A[i] in data:
        data[A[i]] += 1
    else:
        data[A[i]] = 1
for i in range(Q):
    if B[i] in data:
        SUM += data[B[i]]*(C[i]-B[i])
        if C[i] in data:
            data[C[i]] += data[B[i]]
        else:
            data[C[i]] = data[B[i]]
        data[B[i]] = 0
    print(SUM)

Measured memory_bytes: 100068
import java.util.*;
import java.util.Map.Entry;
 
 
 class Main {
	 static int mod =  (int) (Math.pow(10,9)+7);
	 static List<ArrayList<Integer>>  list = new ArrayList<ArrayList<Integer>>();
    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        
        
        
        long[] a = new long[(int)N];
        long[] s = new long[(int)N];
        for (int i=0 ; i<N; i++) {
            a[i] = sc.nextLong();
        }
        Arrays.sort(a);
        for (int i=0 ; i<N; i++) {
            s[i] = modinv(a[i])%mod;
        }
        
        boolean[] m = new boolean[1000];
        int[] p = new int[100000];
        int k=0;
        for(int i=2;i<1000;i++) {
        	if(m[i]==false) {
        		p[k]=i;
        		k++;
        		for(int j=i;j<1000;j=j+i) {
        			m[j]=true;
        		}
        	}
        }
        int[][] ap= new int[N][k];
        
        long lcm=1;
        for(int i=0;i<N;i++) {
    		for(int j=0;j<k;j++) {
    			if(a[i]%p[j]==0) {
    				while(a[i]%p[j]==0) {
    					a[i]=a[i]/p[j];
            			ap[i][j]++;
    				}
    			}
        	}
        }
        
        Arrays.sort(a);
        for(int i=0;i<N;i++) {
        	if(i==0||a[i-1]!=a[i]) {
        		lcm=(lcm*a[i])%mod;
        	}
        }
        
        int[] max= new int[1000000];
        for(int i=0;i<k;i++) {
        	for(int j=0;j<N;j++) {
        		max[i]=Math.max(max[i], ap[j][i]);
        	}
        	lcm=(long) ((lcm*Math.pow(p[i],max[i]))%mod);
        }
        
        
        long sum=0;
        long b=0;
        for(int i=0;i<N;i++) {
        	b=(lcm*s[i])%mod;
        	sum=(sum+b)%mod;
        }
        
        System.out.println(sum);  	
               		
    }
	public static long pow(long a,long n) {
	    long res=1;
	    while (n>0) {
	        if ((n-n/2*2)==1) {
	            res=(res*a)%mod;
	        }
	        a=(a*a)%mod;
	        n>>=1;
	    }
	    return res;
	}
 
	public static long modinv(long n) {
		return pow(n, mod-2);
	}
    
	public static boolean isprime(long n) {
		for(int i=0;i<Math.pow(n, 0.5);i++) {
			if(n%i==0)return false;
		}
		return true;
	}
}

Measured memory_bytes: 50036
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using pii = pair<int, int>;
#define rep(i,n) for(int i=0; i<(int)(n);i++)

int main(){
  long h,w;
  cin >> h >> w;
  if(h%3 == 0 || w%3 == 0){
    cout << 0 << endl;
    return 0;
  }
  long tmph = h;
  long tmpw = w;
  long x,y,smax,smin;
  long ans1,ans2,ans3,ans4;
  x = tmph / 3;
  if(x == 0) x++;  
  tmph -= x;
  y = tmpw / 2;
  tmpw -= y;
  smax = max(w*x,max(tmph*tmpw,y*tmph));
  smin = min(w*x,min(tmph*tmpw,y*tmph));
  ans1 = smax - smin;
  
  tmph = h;
  tmpw = w;
  x = (tmph / 3) + 1;
  tmph -= x;
  y = tmpw / 2;
  tmpw -= y;
  smax = max(w*x,max(tmph*tmpw,y*tmph));
  smin = min(w*x,min(tmph*tmpw,y*tmph));
  ans2 = smax - smin;
  
  tmph = h;
  tmpw = w;
  x = (tmpw / 3) + 1;
  tmpw -= x;
  y = tmph / 2;
  tmph -= y;
  smax = max(h*x,max(tmph*tmpw,y*tmpw));
  smin = min(h*x,min(tmph*tmpw,y*tmpw));
  ans3 = smax - smin;
  
  tmph = h;
  tmpw = w;
  x = (tmpw / 3);
  if(x == 0) x++;
  tmpw -= x;
  y = tmph / 2;
  tmph -= y;
  smax = max(h*x,max(tmph*tmpw,y*tmpw));
  smin = min(h*x,min(tmph*tmpw,y*tmpw));
  ans4 = smax - smin;
  long answer = min(min(ans1,ans2),min(ans3,ans4));
  if(h % 3 == 1 && h > 2){
    answer = min(answer,w);
  }
  if(h % 3 == 2 && h > 2){
    answer = min(answer,w);
  }
  if(w % 3 == 1 && w > 2){
    answer = min(answer,h);
  }
  if(w % 3 == 2 && w > 2){
    answer = min(answer,h);
  }
  cout << answer << endl;
}



Measured memory_bytes: 256
a = input().rstrip().split(" ")

H = int(a[0])   #行
W = int(a[1])   #列
K = int(a[2])   #操作後に残る黒いマスの数

m = []
for i in range(H):
    n = list(input())
    m.append(n)

#print(m)
ans = 0

#2進数のyes/no(赤く塗るか否か)列を作る
for maskR in range(1 << H):
    for maskC in range(1 << W):
        black = 0
        
        for i in range(H):
            for j in range(W):
                if (maskR >> i & 1) == 0 and (maskC >> j & 1) == 0 and m[i][j] == "#":
                    black += 1
    
        if black == K:
            ans += 1

print(ans)

Measured memory_bytes: 9108
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include<climits>
#include <string>
#include <map>
#include <set>
#include <list>

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)

using namespace std;

int i,j,k,l,m,n;
/////////////////////////////////////////////////////


int X,Y;
int main(){
    scanf("%d%d",&X,&Y);
    printf("%d\n", X + Y / 2);
    return 0;
}

Measured memory_bytes: 256
import scala.io.StdIn._
import scala.collection._

object Main {

  class Sieve(val n: Int){
    private[this] val top = (n - 3) / 2 + 1
    private[this] val sqrtLimit = (Math.sqrt(n).toInt - 3) / 2

    private[this] val cmpsts = new Array[Int]((top >>> 5) + 1)
    def isPrime(ci: Int): Boolean = (cmpsts(ci >>> 5) & (1 << (ci & 31))) == 0
    def notPrime(ci: Int): Unit = cmpsts(ci >>> 5) |= 1 << (ci & 31)

    def next(i: Int): Int = if((i > top) || isPrime(i)) 2 * i + 3 else next(i + 1)

    def exec: Iterator[Int] = {

      for{
        i <- 0 to sqrtLimit
        if isPrime(i)
        j <- Range(((2 * i + 3)*(2 * i + 3)-3)/2, top, (2 * i + 3))
      } notPrime(j)
      
      /*
      (0 to sqrtLimit).map{ i =>
        val p = 2 * i + 3
        if(isPrime(i))Range((p*p-3)/2, top, p).map{notPrime}
      }
      */
/*
      (0 to sqrtLimit).withFilter(isPrime).map{ i =>
        val p = 2 * i + 3
        Range((p*p-3)/2, top, p).map(notPrime)
      }
      */

      if(n==2)Iterator.single(2)
      else Iterator.single(2) ++ Iterator.iterate(3)(p => next((p - 1) / 2)).takeWhile(_ <= n)
    }
  }

  def loop(s: String){
    if(s != null){
       val Array(n,_*) = s.split(" ").map(_.toInt)
       if(n<2) println(0)
       else println(new Sieve(n).exec.size)
       loop(readLine)
    }
  }

  def main(args: Array[String]): Unit = loop(readLine)
}

Measured memory_bytes: 65800
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;

LL n,ans = 0,u,v;

int main(){
	cin >> n;
	for(LL i = 1;i <= n;i ++) ans += (i * (n - i + 1));
	for(LL i = 1;i < n;i ++){
		cin >> u >> v;
		if(u > v) swap(u,v);
		ans -= (u * (n - v + 1));
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
 string s;
 cin >> s;
 if(s.size()==2) cout <<s<<endl;
 else{
   for(int i=s.size()-1;i>=0;i--) cout << s[i];
   cout <<endl;
 }

}


Measured memory_bytes: 764
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAXNUM (100000000)
#define SIZE 	(50000000)

int main(void) {
	register long i, j;
	long n, d, c, end1, end2;
	char *num;
	
	num = (char *)calloc(SIZE, sizeof(char));
	
	end1 = (long)sqrt((double)MAXNUM);
	for (i = 3; i < end1; i+=2) {
		if (!num[i >> 1]) {
			end2 = MAXNUM / i;
			for (j = 3; j < end2; j += 2) {
				num[(i * j) >> 1] = 1;
			}
		}
	}
	
	scanf("%ld", &n);
	c = 0;
	while (n-- > 0L) {
		scanf("%ld", &d);
		if (d & 1) {
			if (!num[d >> 1]) {
				c++;
			}
		} else {
			if (d == 2) {
				c++;
			}
		}
	}
	printf("%d\n", c);
	
	free(num);
	
	return 0;
}

Measured memory_bytes: 49292
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <string.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;


int main()
{
//回答が整数の場合
ll ans=1;
//整数値の入力
int n;
cin >> n;
//行列の入力
char table[n]={};
for (int i = 0; i < n; ++i) {
    cin >> table[i];
}
sort(table, table+n);
int al[26]={};
al[0]++;
int syu=0;
for (int i = 0; i < n-1; ++i) {
    if(table[i]==table[i+1]){al[syu]++;}
    else{syu++;al[syu]++;}
}
for (int i = 0; i < 26; ++i) {
    ans=ans*(al[i]+1);
    ans=ans%1000000007;
 
}

//回答
cout << ans-1 << endl;
return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <list>
#include <ctime>
#include <complex>
#include <bitset>
#include <tuple>
#define MOD 998244353
using namespace std;

typedef long long int lli;
struct strt{
    lli g, x, y;
};
lli gcd(lli a, lli b){
    if(!b)
        return a;
    return gcd(b, a % b);
}
strt egcd(lli a, lli b){
    if(!b)
        return {a, 1, 0};
    strt t = egcd(b, a % b);
    return {t.g, t.y, t.x - (a / b) * t.y};
}

lli N, M, K, ans = 1;
lli power(lli v, int e){
    if(e == 0) return 1;
    if(e == 1) return v % MOD;
    if(e % 2){
        return power(v, e - 1) * v % MOD;
    }
    lli t = power(v, e / 2) % MOD;
    return t * t % MOD;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M >> K;
    for(int j = 0; j < N; ++j){
        ans *= M;
        ans %= MOD;
    }
    lli combi = 1;
    for(int j = 0; j < N - 1 - K; ++j){
        ans -= (combi * M % MOD) * power(M - 1, j) % MOD;
        ans = (ans + MOD) % MOD;
        //cout << (combi * M % MOD) * power(M - 1, j) << endl;

        lli rev = (egcd(j + 1, MOD).x + MOD) % MOD;
        combi *= N - j - 1;
        combi %= MOD;
        combi *= rev;
        combi %= MOD;
        //cout << combi << endl;
    }
    cout << ans;
    return 0;
}

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

#define ll long long
#define ld long double
#define ull unsigned long long
#define endl "\n"
#define MohamedMotaz ios::sync_with_stdio(0); cin.tie(0); ios_base::sync_with_stdio(0);
#define f(a, b, c) for(int a = b; a < c; a++)
using namespace std;
const ll mod = 1e9 + 7;



//ll fact[1000001]; ll inv[1000001];
//ll primes[100007];
//ll arr[1000007];
//ll modPower(ll b, ll p) {
//	if (p == 0)
//		return 1;
//
//	ll halfpow = modPower(b, p / 2);
//	ll toReturn = (halfpow * halfpow) % mod;
//	if (p % 2)
//		toReturn = (toReturn * b) % mod;
//
//	return toReturn;
//}
//
//ll fastPower(ll b, ll p) {
//	if (p == 0)
//		return 1;
//	ll ans = fastPower(b, p / 2);
//	ans = (ans * ans);
//	if (p % 2 != 0)
//		ans = (ans * b);
//	return ans;
//}
//ll GcdRecursive(ll a, ll b) {
//	if (b == 0) return a;
//	return GcdRecursive(b, a % b);
//}
//ll modLCM(ll a, ll b) {
//	ll val = GcdRecursive(a, b);
//	ll tmp = ((a % mod) * (b % mod)) % mod;
//	ll finalVal = ((tmp % mod) * (arr[val] % mod)) % mod;
//	return finalVal;
//
//}
//ll LCM(ll a, ll b) {
//	return (a * b) / GcdRecursive(a, b);
//}
//void move1step(ll& a, ll& b, ll q) { // a and b by reference
//	ll c = a - q * b;
//	a = b;
//	b = c;
//}
//ll GcdIterative(ll a, ll b) {
//	while (b) move1step(a, b, a / b);
//	return a;
//}
//
//void pre(ll n) {
//
//	fact[0] = 1;
//	inv[0] = 1;
//
//	for (ll i = 1; i <= n; i++) {
//		fact[i] = (i * fact[i - 1]) % mod;
//		inv[i] = modPower(fact[i], mod - 2);
//		arr[i] = modPower(i, mod - 2);
//	}
//}
//
//ll npr(ll n, ll r) {
//	return ((fact[n] * inv[n - r]) % mod);
//}
//
//ll ncr(ll n, ll r) {
//	return ((((fact[n] * inv[n - r]) % mod) * inv[r]) % mod);
//}
//
//void sieve(ll val) {
//	memset(primes, 1, sizeof primes);
//	primes[0] = primes[1] = false;
//	for (int i = 2; i <= val; i++) {
//		if (primes[i]) {
//			for (int j = i * i; j <= val; j += i) {
//				primes[j] = 0;
//			}
//		}
//	}
//
//}











int main()
{
    MohamedMotaz;
    
    ll n;
    cin >> n;
    vector<ll> mon(n + 1), her(n);
    ll c = 0;

    f(i, 0, n + 1) cin >> mon[i];
    f(i, 0, n) cin >> her[i];

    f(i, 0, n) {
        ll a = min(max(her[i], (ll)0), mon[i]);
        c += a;
        her[i] -= a, mon[i] -= a;

        ll b = min(max(her[i], (ll)0), mon[i + 1]);
        c += b;
        her[i] -= b, mon[i + 1] -= b;

    }
    cout << c << endl;
  
}








Measured memory_bytes: 1792
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <bitset>
#include <boost/algorithm/string/replace.hpp>

using namespace std;

#define FOR(i, n) for (int i = 0; i < n; i++)
#define OUT(s) cout << s << endl;
#define IN(a) cin >> a;
#define PACK(a, n)                                                             \
  for (int i = 0; i < n; i++)                                                  \
    cin >> a[i];
#define LIST(a, n)                                                             \
  for (int i = 0; i < n; i++)                                                  \
    cout << "[" << i << "] " << a[i] << endl;

int main() {
  // input
  string S;
  IN(S);

  boost::replace_all(S, "/", "");
  int i = stoi(S);
  if (i <= 20190430) {
    OUT("Heisei");
  } else {
    OUT("TBD");
  }
  return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7
N, M = map(int, input().split())
S = list(input().split())
T = list(input().split())

# Sのi文字目までと、Tのj文字目までで、dp[i][j]こ
dp = [[0]*(M+1) for _ in range(N+1)]

for r in range(1, N+1):
    for k in range(1, M+1):
        if S[r-1] == T[k-1]:
            dp[r][k] = 1+dp[r-1][k]+dp[r][k-1]
            dp[r][k] %= MOD
        else:
            dp[r][k] = dp[r-1][k]+dp[r][k-1]-dp[r-1][k-1]
            dp[r][k] %= MOD
print((dp[-1][-1]+1) % MOD)


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

int main() {
  int n;
  cin >> n;
  int a[n];

  // m = a1*...*aN
  // m mod ai = 0
  // m - 1 mod ai = -1 mod ai
  //              = ai - 1
  // ai - 1 は mod a1 で考えたときの最大値
  // よって m = a1*...*aN - 1 とすればよい
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    ll a;
    cin >> a;
    a--;
    ans += a;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define INF LLONG_MAX
#define eps LDBL_EPSILON
#define moder 1000000007
#define pie 3.141592653589793238462643383279
#define P std::pair<int,int>
#define prique priority_queue
using namespace std;
signed main(){
	int n,a;
	cin>>n;
	int ans=0;
	rep(i,n){
		cin>>a;
		ans+=a-1;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

int main(void) {
	int a, b;
	cin >> a >> b;
	
	if( a % 2 == 0 || b % 2 == 0 ) cout << "No" << endl;
	else cout << "Yes" << endl;
	
	return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;

public static class P
{
    public static void Main()
    {
        int q = int.Parse(Console.ReadLine());
        Node root = null;
        for (int i = 0; i < q; i++)
        {
            var query = Console.ReadLine().Split();
            if (query[0] == "print")
            {
                Console.WriteLine(" " + string.Join(" ", Node.GetInOrderWalk(root)));
                Console.WriteLine(" " + string.Join(" ", Node.GetPreOrderWalk(root)));
                continue;
            }
            var z = new Node() { Key = int.Parse(query[1]) };
            {
                Node y = null;
                Node x = root;
                while (x != null)
                {
                    y = x;
                    x = z.Key < x.Key ? x.Left : x.Right;
                }
                if (y == null) root = z;
                else if (z.Key < y.Key) y.Left = z;
                else y.Right = z;
            }
        }
    }
}


class Node
{
    public int Key;
    public Node Left;
    public Node Right;

    public static IEnumerable<int> GetInOrderWalk(Node node) =>
        node == null ?
        Enumerable.Empty<int>() :
        GetInOrderWalk(node.Left)
        .Concat(new[] { node.Key })
        .Concat(GetInOrderWalk(node.Right));

    public static IEnumerable<int> GetPreOrderWalk(Node node) =>
        node == null ?
        Enumerable.Empty<int>() :
        new[] { node.Key }
        .Concat(GetPreOrderWalk(node.Left))
        .Concat(GetPreOrderWalk(node.Right));
}



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

using namespace std;

typedef long long LL;
typedef pair<int,int> pi;
typedef vector<int> vi;
#define ST first
#define ND second
#define PB push_back
#define DET(a,b,c) (LL(b.x-a.x)*LL((c.y-a.y))-LL((c.x-a.x))*LL((b.y-a.y)))

const LL INF = (LL)1000*1000*1000*1000*1000*1000;
int n;
int com[16][16];
LL dp[(1<<16)];
LL sum[(1<<16)];

void rec(int nr,vi&Rabbits,int mask,LL score,int mask2) {
    if(nr==Rabbits.size()) {
        dp[mask] = max(dp[mask],(score+sum[mask2]));
        return;
    }
    rec(nr+1,Rabbits,mask,score,mask2);
    rec(nr+1,Rabbits,mask ^ (1<<Rabbits[nr]), score,mask2 ^ (1<<Rabbits[nr]));
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=0; i<n;i++) {
        for(int j=0; j<n;j++) {
            cin>>com[i][j];
        }
    }
    for(int mask = 0; mask<(1<<n);mask++) {
        for(int i=0; i<n;i++) {
            if(mask&(1<<i)) {
                for(int j = i+1; j<n;j++) {
                    if(mask&(1<<j)) {
                        sum[mask] = (sum[mask]+com[i][j]);
                    }
                }
            }
        }
        //cout<<mask<<" "<<sum[mask]<<"\n";
    }
    for(int mask=1; mask<(1<<n); mask++) dp[mask] = -INF;
    dp[0]=0;
    for(int mask=0; mask<(1<<n); mask++) {
        vi getRabbit;
        for(int i=0; i<n;i++) {
            if(!(mask&(1<<i))) {
                getRabbit.PB(i);
            }
        }
        rec(0,getRabbit,mask,dp[mask],0);
    }
    cout<<dp[(1<<n)-1];
}


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

using pil = std::pair<long long, int>;
constexpr long long mod{1000000007};

struct Node {
	// いずれも0:s→t、1:t→s
	long long path_num[2]{}, distance[2]{-1, -1};
	std::list<std::pair<int, long long>> edges;
};
int n, m, s, t;
std::vector<Node> graph;

void dijkstra(int, int);
long long calcNum(int, int);
long long pow2(long long);

int main()
{
	scanf("%d%d%d%d", &n, &m, &s, &t);
	s--; t--;
	graph.resize(n);
	for (int i{}; i < m; i++)
	{
		int u, v;
		long long d;
		scanf("%d%d%lld", &u, &v, &d);
		u--; v--;
		graph[u].edges.push_back({v, 2 * d});
		graph[v].edges.push_back({u, 2 * d});
	}
	dijkstra(s, 0);
	dijkstra(t, 1);

	graph[s].path_num[0] = graph[t].path_num[1] = 1;
	calcNum(t, 0);
	calcNum(s, 1);
	
	const long long encount_time{graph[t].distance[0] / 2};
	long long encount_combi{};
	for (int i{}; i < n; i++)
	{
		if (!graph[i].path_num[0] || graph[i].distance[0] > encount_time) continue;
		// 以下、頂点iが最短経路上に存在するかつ頂点sのencount_time閉近傍内の場合のみ
		if (graph[i].distance[0] == encount_time && graph[i].distance[1] == encount_time)
		{
			encount_combi = (encount_combi + pow2(graph[i].path_num[0] * graph[i].path_num[1] % mod)) % mod;
			continue;
		}
		// 以下、頂点iは頂点sのencount_time近傍内
		for (auto& e: graph[i].edges)
		{
			if (!graph[e.first].path_num) continue;
			int& dir{i}, rev{e.first};
			// 以下、revは最短経路上に存在
			if (graph[rev].distance[1] >= encount_time) continue;
			// 以下、revはtのencount_time近傍上に存在
			if (graph[dir].distance[0] + e.second != graph[rev].distance[0]) continue;
			// 辺(dir,rev)を通る最短経路が存在
			encount_combi = (encount_combi + pow2(graph[dir].path_num[0] * graph[rev].path_num[1] % mod)) % mod;
		}
	}
	printf("%lld\n", (pow2(graph[t].path_num[0]) % mod + mod - encount_combi) % mod);

	return 0;
}

void dijkstra(int from, int direct)
{
	std::priority_queue<pil, std::vector<pil>, std::greater<pil>> pq;
	pq.push({0, from});
	while (!pq.empty())
	{
		pil dist{pq.top()};
		pq.pop();
		if (graph[dist.second].distance[direct] >= 0) continue;
		graph[dist.second].distance[direct] = dist.first;
		for (auto& e: graph[dist.second].edges)
			if (graph[e.first].distance[direct] < 0)
				pq.push({dist.first + e.second, e.first});
	}
	return;
}

long long calcNum(int index, int direct)
{
	long long& path_num{graph[index].path_num[direct]};
	if (path_num > 0) return path_num;
	for (auto& e: graph[index].edges)
		if (graph[e.first].distance[direct] + e.second == graph[index].distance[direct])
			path_num = (path_num + calcNum(e.first, direct)) % mod;
	return path_num;
}

long long pow2(long long x) { return x * x % mod; }

Measured memory_bytes: 31556
using System;
using System.Collections.Generic;
using System.Linq;
using BitArray = System.Collections.BitArray;
using BigInteger = System.Numerics.BigInteger;

namespace AtCoderProject
{
    public class Program
    {
        public object Calc()
        {
            var line = consoleReader.SplitInt32();
            var N = line[0];
            var K = line[1];
            var h = consoleReader.RepeatInt32(N).OrderBy(i => i).ToArray();

            var min = int.MaxValue;
            for (int i = K - 1; i < N; i++)
            {
                var tmp = h[i] - h[i - K + 1];
                if (tmp < min)
                    min = tmp;
            }

            return min;
        }

        const int mod = 1000000007;
        private readonly ConsoleReader consoleReader;
        public Program() : this(new ConsoleReader()) { }
        public Program(ConsoleReader consoleReader) { this.consoleReader = consoleReader; }
        static void Main() => Console.WriteLine(new Program().Calc());
        public static string MultiLine<T>(IEnumerable<T> source) => string.Join("\n", source);
    }

    public class ConsoleReader
    {
        public virtual string String() => Console.ReadLine();
        public int Int32() => int.Parse(String());
        public long Int64() => long.Parse(String());
        public ulong UInt64() => ulong.Parse(String());
        public double Double() => double.Parse(String());
        public string[] Split() => String().Split().ToArray();
        public int[] SplitInt32() => String().Split().Select(int.Parse).ToArray();
        public long[] SplitInt64() => String().Split().Select(long.Parse).ToArray();
        public ulong[] SplitUInt64() => String().Split().Select(ulong.Parse).ToArray();
        public double[] SplitDouble() => String().Split().Select(double.Parse).ToArray();

        public IEnumerable<string> Repeat(int count)
        {
            for (int i = 0; i < count; i++)
                yield return String();
        }
        public IEnumerable<int> RepeatInt32(int count)
        {
            for (int i = 0; i < count; i++)
                yield return Int32();
        }
        public IEnumerable<long> RepeatInt64(int count)
        {
            for (int i = 0; i < count; i++)
                yield return Int64();
        }
        public IEnumerable<string[]> RepeatSplit(int count)
        {
            for (int i = 0; i < count; i++)
                yield return Split();
        }
        public IEnumerable<int[]> RepeatSplitInt32(int count)
        {
            for (int i = 0; i < count; i++)
                yield return SplitInt32();
        }
    }
}


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

h, w, k = map(int, input().split())


def f(x):
    lst = [1, 2, 3, 5, 8, 13, 21]
    if 0 <= x < 7:
        return lst[x]
    else:
        return 1


ptn = [[0] * (w + 2) for _ in range(w + 2)]
for i in range(w + 2):
    for j in range(w + 2):
        if i == 0 or i == w + 1 or j == 0 or j == w + 1:
            continue
        elif i == j:
            ptn[i][j] = f(i-2)*f(w-i-1)
        elif i == j + 1:
            ptn[i][j] = f(i-3)*f(w-i-1)
        elif i == j - 1:
            ptn[i][j] = f(i-2)*f(w-i-2)

for _ in range(h - 1):
    temp = [[0] * (w + 2) for _ in range(w + 2)]
    for i in range(w + 2):
        for j in range(w + 2):
            if i == 0 or i == w + 1 or j == 0 or j == w + 1:
                continue
            else:
                temp[i][j] = ptn[i-1][j]*f(i-3)*f(w-i-1) + ptn[i][j]*f(i-2)*f(w-i-1) + ptn[i+1][j]*f(i-2)*f(w-i-2)

    ptn = temp

print(ptn[1][k] % 1000000007)


Measured memory_bytes: 3064
import java.math.*

fun main(args: Array<String>) {
    val N = readInputLine().toInt()
    
    val aList = readInputLine().split(" ").map { it.toInt() }.toIntArray()
    
    val (ceil, floor) = aList.sum().let {
        Pair(it / N + if (it % N == 0) 0 else 1, it / N)
    }

    println(Math.min(
        aList.sumBy { (it - ceil) * (it - ceil) },
        aList.sumBy { (it - floor) * (it - floor) }
    ))
}

fun readInputLine(): String {
    return readLine()!!
}


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

using namespace std;

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

int main()
{
    int n ;
    cin>>n ;
    int arr[n+5];
    for(int i = 0 ; i <= n ; ++i)
     arr[i] = sum_of_digits(i);
    int MIN = 1e9 ;
    for(int i = 1 ; i <= n/2 ; ++i)
        MIN = min(MIN , arr[i] + arr[n-i]);
    cout<<MIN;
    return 0 ;
}


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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

using ll=long long;
using R=long double;
const R EPS=1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max(x,0.0L));}

template<typename T> vector<T> make_vector(size_t sz){
	return vector<T>(sz);
}

template<typename T,typename... Ts> 
auto make_vector(size_t sz, Ts... ts){
	return vector<decltype(make_vector<T>(ts...))>(sz, make_vector<T>(ts...));
}

template<typename T,typename U,typename... V> 
typename enable_if<is_same<T, U>::value!=0>::type 
fill_value(U &u, const V... v){
	u=U(v...);
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_value(U &u, const V... v){
	for(auto &e:u){
		fill_value<T>(e,v...);
	}
}

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

const pid_t pid = getpid();
// Problem Specific Parameter:

int main(void){
	int h, w, n;
	cin >> h >> w >> n;
	const int base = max(h, w);
	const int ans = (n + base - 1) / base;
	cout << ans << endl;
	return 0;
}

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

int main(){
  double a, b, x; cin >> a >> b >> x;
  double delta = M_PI / pow(2, 26);
  double capa;
  double ans;
  
  if(a * a * b / 2 < x){
    for(double theta = 0; tan(theta) <= (b/a); theta += delta){
      capa = a * a * b - 0.5 * a * a * a * tan(theta);

      if(x >= capa){
        ans = theta;
        break; 
      }
    }
  }else{
    for(double theta = atan(b/a); theta <= M_PI / 2; theta += delta){
      capa = 0.5 * a * b * b / tan(theta);  
      if(x >= capa){          
        ans = theta;
        break;
        } 
      }
    }
    
  printf("%lf\n", ans *180 / M_PI);
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.14159265359
#define NIL (-1)
#define LL long long
using namespace std;
const int64_t MOD = 1e9 + 7;

int main() {
	for (int i = 0; i < 3; i++) {
		string s;
		cin >> s;
		cout << s.at(i);
	}
	cout << endl;
}

Measured memory_bytes: 3600
#include <stdio.h>
#include <random>
int D;
int c[26];
int l[367][26];
int s[366][26];
int t[366];
int m, p, q, d, k;
int md[1000001];
int mq[1000001];
int ans, bans;
unsigned long long a;
int main() {
	scanf("%d", &D);
	for (int i = 0; i < 26; i++) {
		scanf("%d", c + i);
	}
	for (int i = 1; i <= D; i++) {
		for (int j = 0; j < 26; j++) {
			scanf("%d", s[i] + j);
		}
	}
	std::mt19937_64 rd(468);
	for (int i = 1; i <= D; i++) {
		a = rd();
		t[i] = a % 26;
	}
	m = 100000;
	for (int i = 0; i < 100000; i++) {
		a = rd();
		md[i] = a % D + 1;
		mq[i] = a % 26;
	}
	for (int i = 1; i <= D; i++) {
		ans += s[i][t[i]];
		for (int j = 0; j < 26; j++) {
			l[i][j] = l[i - 1][j] + 1;
		}
		l[i][t[i]] = 0;
		for (int j = 0; j < 26; j++) {
			ans -= c[j] * l[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		q = mq[i];
		d = md[i];
		p = t[d];
		if (p != q) {
			bans = ans;
			t[d] = q;
			ans -= s[d][p];
			ans += s[d][q];
			k = d;
			while (l[k][q] && k <= D) {
				ans -= c[q] * (k - d - l[k][q]);
				l[k][q] = k - d;
				k++;
			}
			k = d;
			do {
				ans -= c[p] * (l[k - 1][p] + 1 - l[k][p]);
				l[k][p] = l[k - 1][p] + 1;
				k++;
			} while (l[k][p] && k <= D);
			a = rd();
			if (ans < bans && (a % m) < i) {
				mq[i + 1] = p;
				md[i + 1] = d;
			}
		}
	}
	for (int i = 1; i <= D; i++) {
		printf("%d\n", t[i] + 1);
	}
}

Measured memory_bytes: 2600
n = int(input())
s = input()

all_count_b = s.count("#")
all_count_w = n - all_count_b

count_b = 0
count_w = all_count_w

minimum = min([all_count_b, all_count_w])

for s1, s2 in zip(s, s[1:]):
    if s1 == "#":
        count_b += 1
    else:
        count_w -= 1
        if s2 == "#":
            minimum = min([count_b + count_w, minimum])

print(minimum)


Measured memory_bytes: 3500
#include "bits/stdc++.h"
#include <random>
#define REP(i, n) for (ll i = 0; i < ll(n); ++i)
#define RREP(i, n) for (ll i = ll(n) - 1; i >= 0; --i)
#define FOR(i, m, n) for (ll i = m; i < ll(n); ++i)
#define RFOR(i, m, n) for (ll i = ll(n) - 1; i >= ll(m); --i)
#define ALL(v) (v).begin(), (v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n, k;
  cin >> n >> k;
  if (2 * k + 2 * n - 1 > k + 2 * n - 1 + (n + 1) / 2) {
    cout << -1 << endl;
    return 0;
  }
  vector<ll> a(n), b(n), c(n);
  REP(i, n) {
    a[i] = k + i;
    b[i] = k + n + i;
    c[i] = k + n + n + i;
  }
  if (n & 1) {
    int s = (n / 2 + 1) / 2, t = n / 4;
    REP(i, s) {
      swap(a[i], a[2 * s - 1 - i]);
    }
    REP(i, t) {
      swap(a[2 * s + i], a[2 * s + 2 * t - i]);
    }

  }
  else {
    int s = ((n - 1) / 2 + 1) / 2, t = (n - 1) / 4;
    REP(i, s) {
      swap(a[i], a[2 * s - 1 - i]);
    }
    REP(i, t) {
      swap(a[2 * s + i], a[2 * s + 2 * t - i]);
    }
  }
  vector<int> pos(n);
  REP(i, n) pos[i] = i;
  sort(ALL(pos),
       [&](int i, int j) { return a[i] + b[n - 1 - i] < a[j] + b[n - 1 - j]; });
  REP(i, n) {
    assert(a[pos[i]] + b[n - 1 - pos[i]] <= c[i]);
    cout << a[pos[i]] << " " << b[n - 1 - pos[i]] << " " << c[i] << endl;
  }
}


Measured memory_bytes: 4992
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define SZ(x) ((int)(x).size())
#define rep(i,m,n) for(int i=(m);i<(n);++i)
#define fore(i,a) for(auto &i:a)
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;
#define answer cout << ans << endl;
signed _main(); signed main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
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; }
template<class T> using v = vector<T>;
template<class T> using vv = vector<v<T>>;
const int MOD=1e9+7;
const long long INF = 1LL << 60;

class UnionFind {
public:
  vector<int> d;
  UnionFind(int n): d(n,-1){}

  int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
  if(d[x]<0) return x;
  return d[x] = root(d[x]);
}

bool unite(int x, int y) { // xとyの木を併合
  x = root(x); //xの根をrx
  y = root(y); //yの根をry
  if (x == y) return false; //xとyの根が同じ(=同じ木にある)時はそのまま
  if(d[x]>d[y]) swap(x,y);
  d[x]+=d[y];
  d[y]=x;
  return true;
}

bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
  int rx = root(x);
  int ry = root(y);
  return rx == ry;
}

int size(int x){ return -d[root(x)];}
};

signed _main(){
  int N,M,K; cin >> N >> M >> K;
  v<int> deg(N,0);
  UnionFind Friend(N);
  v<int> block(N,0);
  rep(i,0,M){
    int a,b; cin >> a >> b;
    a--;b--;
    Friend.unite(a,b);
    deg[a]++;
    deg[b]++;
  }
  rep(i,0,K){
    int a,b; cin >> a >> b;
    a--;b--;
    if(Friend.same(a,b)){
      block[a]++;
      block[b]++;
    }
  }
  rep(i,0,N){
    cout << Friend.size(i)-deg[i]-1-block[i] << endl;
  }
  return 0;
}


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

const int N = 1e5+10;
 
int n;
int a[N][3];
int dp[N][3];
 
int solve (int day, int bef) 
{
	if (day > n)
	{
		return 0;
	}
	
	if (dp[day][bef] != -1) 
	{
		return dp[day][bef];
	}
	for (int i = 0; i < 3; i++)
	{
		if (i != bef)
		{
			dp[day][bef] = max (dp[day][bef], solve (day+1, i) + a[day][i]);
		}
	}
	return dp[day][bef];
}
 
int main () 
{
	for(int i=0;i<N;i++)
	{
		dp[i][0] = -1;
		dp[i][1] = -1;
		dp[i][2] = -1;
	}
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> a[i][j];
		}
	}
		
	int ans = -1;

	for (int i = 0; i < 3; i++)
	{
		ans = max(ans,solve(2, i) + a[1][i]);
	}
	cout << ans;
}

Measured memory_bytes: 10368
N=int(input())
S = input()

Lr = [0]*(N+2)
Lg = [0]*(N+2)
Lb = [0]*(N+2)
Rr = [0]*(N+2)
Rg = [0]*(N+2)
Rb = [0]*(N+2)
for i,s in enumerate(S):
    Lr[i+1] = Lr[i]
    Lg[i+1] = Lg[i]
    Lb[i+1] = Lb[i]
    if s=="R":
        Lr[i+1] += 1
    elif s=="G":
        Lg[i+1] += 1
    elif s=="B":
        Lb[i+1] += 1

for i,s in enumerate(S[::-1]):
    i = N-i
    Rr[i] = Rr[i+1]
    Rg[i] = Rg[i+1]
    Rb[i] = Rb[i+1]
    if s=="R":
        Rr[i] += 1
    elif s=="G":
        Rg[i] += 1
    elif s=="B":
        Rb[i] += 1

ans = 0
for i,s in enumerate(S):
    if s=="R":
        ans += Lg[i+1]*Rb[i+1] + Lb[i+1]*Rg[i+1]
        for j in range(1,N+1):
            if i-j < 0 or i+j >= N: break
            if (S[i-j] == "B" and S[i+j] == "G") or (S[i-j] == "G" and S[i+j] == "B"):
                ans -= 1
    elif s=="G":
        ans += Lr[i+1]*Rb[i+1] + Lb[i+1]*Rr[i+1]
        for j in range(1,N+1):
            if i-j < 0 or i+j >= N: break
            if (S[i-j] == "B" and S[i+j] == "R") or (S[i-j] == "R" and S[i+j] == "B"):
                ans -= 1
    elif s=="B":
        ans += Lg[i+1]*Rr[i+1] + Lr[i+1]*Rg[i+1]
        for j in range(1,N+1):
            if i-j < 0 or i+j >= N: break
            if (S[i-j] == "R" and S[i+j] == "G") or (S[i-j] == "G" and S[i+j] == "R"):
                ans -= 1
print(ans)

Measured memory_bytes: 9400
N = int(input())
A = list(map(int, input().split()))

print(' '.join(map(str, A)))
for i in range(1, N):
    v = A[i]
    j = i - 1
    while j >= 0 and A[j] > v:
        A[j+1] = A[j]
        j -= 1
    A[j+1] = v
    print(' '.join(map(str, A)))



Measured memory_bytes: 5592
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        System.out.println(n * (n - 1) / 2 + m * (m - 1) / 2);
        scan.close();
    }
}

Measured memory_bytes: 21972
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <utility>
#include <functional>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_map>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const int MOD = 1000000007;
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; }

void draw(int h, int w){
    rep(i, h){
        cout << string(w, '#') << endl;
    }
    cout << endl;
}

int main() {
    while(true){
        int h, w;
        cin >> h >> w;
        if(h==0 && w==0) break;
        draw(h, w);
    }
    return 0;
}


Measured memory_bytes: 3164
// ALPC-C.cpp
#include <iostream>
#include<atcoder/math.hpp>

using namespace std;
using namespace atcoder;
#define rep(i,n) for(ll i=0;i<(n);++i)
using ll = long long;
int main()
{
    int t;
    cin >> t;
    ll n, m,a,b;
    
    rep(i, t) {
        cin >> n >> m >> a >> b;
        cout<<floor_sum(n, m, a, b)<<endl;
    }
}


Measured memory_bytes: 3140
n = int(input())
nums = list(map(int, input().split()))

for idx1 in range(len(nums)):
    num  = nums[idx1]
    idx2 = idx1 - 1
    while idx2 >= 0 and nums[idx2] > num:
        nums[idx2 + 1] = nums[idx2]
        idx2 -= 1
    nums[idx2+1] = num
    print(" ".join(map(str, nums)))


Measured memory_bytes: 5596
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] d = new int[n];
        Arrays.setAll(d, i -> sc.nextInt());
        Arrays.sort(d);
        System.out.println(d[n/2] - d[n/2 - 1]);
    }
}


Measured memory_bytes: 51020