akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>  // ver2.2.0
#define int long long
#define endl "\n"
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define VVi vector<Vi>
#define Vs vector<string>
#define Pii pair<int,int>
#define VPii vector<Pii>
#define Tiii tuple<int,int,int>
#define PQi priority_queue<int>
#define PQir priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define FI first
#define SE second
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define sortr(v) sort(v,greater<>())
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define repreq(i,a,b) for(int i=a;i>=b;i--)
#define leng(n) (int)(log10(n)+1)
#define dem(a,b) ((a+b-1)/(b))
#define Vin(a) rep(iI,0,a.size())cin>>a[iI]
#define Vout(a) rep(lZ,0,a.size()-1)cout<<a[lZ]<<' ';cout<<a.back()<<endl
#define VVout(a) rep(lY,0,a.size()){Vout(a[lY]);}
#define VPout(a) rep(lX,0,a.size())cout<<a[lX].FI<<' '<<a[lX].SE<<endl
#define INF 3000000000000000000  //  3.0 * 10 ^ 18 (MAXの1/3くらい)
#define MOD 1000000007  //  10^9 + 7
using namespace std;
 
int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm
void uniq(Vi &v){sort(ALL(v)); v.erase(unique(ALL(v)),v.end());}  //  uniqのやつ
 
int mypow(int x, int n, int m){  //  累乗x^n(mod m)  O(log(n))
if(n==0)return 1;if(n%2==0)return mypow(x*x%m,n/2,m);else return x*mypow(x,n-1,m)%m;}

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

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

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

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

signed main() {
  cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(12);
  int n;
  cin >> n;
  VVi gr(n,Vi(n));
  UnionFind tree(n);
  int qw,er;
  
  rep(i,0,n-1){
    cin >> qw>> er;
    qw--,er--;
    gr[qw][er]=1;
    gr[er][qw]=1;
    tree.unite(qw,er);
  }
  
  Vi a(n);
  int ans = 0;
  rep(i,0,n){
    cin >> qw;
    ans += qw;
    a[i]=qw;
  }
  sortr(ALL(a));
  ans -= a[0];
  int rt= tree.root(0);
  
  Vi ansv(n);
  int now,ct=0;
  queue<int> next,next2;
  set<int> kind;
  next.push(rt);
  kind.insert(rt);
  
  while(next.size()!=0){
    now = next.front();
    next.pop();
    ansv[now]=a[ct];
    rep(i,0,n){
      if(gr[now][i]==1 && kind.count(i)==0) {
        next.push(i);
        kind.insert(i);
      }
    }
    ct++;
  }
  cout << ans << endl;
  Vout(ansv);
  return 0;
}

Measured memory_bytes: 782720
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    token.parse().ok().unwrap()
}

fn main() {
    let a = input::<i64>();
    let b = input::<i64>();

    let ans = if b % a == 0 { a + b } else { b - a };
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include <math.h>
#include <vector>
#include <stack>
#include <cstdio>
#include <string>
#include <bitset>
#include <list>
#include <set>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <functional>
#include <queue>
// #include "bits/stdc++.h"

using namespace std;
//debug

#define rep(i, N) for (int i = 0; i < N; i++)
#define rep2(i, N, M) for (int i = N; i < M; i++)
#define pb push_back



typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef priority_queue<pll, vector<pll>, greater<pll>> greater_pq ;


#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define vec(a) vector<a>

void f(string& str) {
	str.insert(str.begin(), str.back());
	str.pop_back();
}

int main() {
	string a, b;
	cin >> a >> b;
	rep(i, a.size()+1) {
		f(a);
		if (a == b) {
			cout << "Yes"<<endl;
			return 0;
		}
	}
	cout << "No"<<endl;
	return 0;
}



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

const ll MOD = 1e9 + 7;
const ll MAX_V = 100100;
ll fact[MAX_V + 1], invfact[MAX_V + 1];

template <typename T, typename U>
T mypow(T b, U n) {
    if (n == 0) return 1;
    if (n == 1) return b % MOD;
    if (n % 2 == 0) {
        return mypow(b * b % MOD, n / 2);
    } else {
        return mypow(b, n - 1) * b % MOD;
    }
}

void precalc() {
    invfact[0] = fact[0] = 1;
    for (ll i = 1; i <= MAX_V; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
    }

    invfact[MAX_V] = mypow(fact[MAX_V], MOD - 2);
    for (ll i = MAX_V - 1; i >= 0; --i) {
        invfact[i] = invfact[i + 1] * (i + 1) % MOD;
    }
    return;
}

ll comb(ll a, ll b) {
    if (a < b) return 0;
    if (a == 0) return 1;  // a = b = 0

    return fact[a] * invfact[a - b] % MOD * invfact[b] % MOD;
}

int main() {
    precalc();
    ll N, M;
    cin >> N >> M;

    ll ans = 1;
    ll _M = M;
    for (ll i = 2; i * i < _M; ++i) {
        int cnt = 0;
        while (M % i == 0) {
            M /= i;
            ++cnt;
        }

        ans *= comb(N + cnt - 1, cnt);
        ans %= MOD;
    }

    if (M > 1) {
        ans *= N;
        ans %= MOD;
    }

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


Measured memory_bytes: 1792
import math

N, K = map(int,input().split())
A = list(map(int,input().split()))

L = 1
R = 10**9+1
ans = float("INF")

while True: # midの長さの丸太に切るとして2分探索
    mid = (L + R) // 2
    cur = 0
    for i in range(N):
        cur += math.ceil(A[i]/mid) - 1 # 切る必要回数
    
    if cur > K: #K回より大きい時は、L=midとして長くする 
        if L == mid:
            break
        L = mid
    else: #K回以下の時は、R=midとして短くする 
        ans = min(ans, mid)
        if R == mid:
            break
        R = mid
        
print(ans)

Measured memory_bytes: 104308
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define REP(X, Y, Z) for (ll(X) = (Y); (X) < (Z); (X)++)
#define REV(X, Y, Z) for (ll(X) = (Y); (X) > (Z); (X)--)

using namespace std;
using ll = long long;
using dll = deque<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using usll = unordered_set<ll>;
using umll = unordered_map<ll, ll>;
using sll = stack<int>;
using vll = vector<ll>;
using vvll = vector<vll>;

constexpr ll kMod = 1e9 + 7;

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

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

void init() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

int main() {
  init();

  string S;
  cin >> S;

  if (S[0] != 'A') {
    cout << "WA" << endl;
    return 0;
  }

  ll cnt = 0;
  REP(i, 2, S.size() - 1) {
    if (S[i] == 'C') {
      cnt++;
    }
  }
  if (cnt != 1) {
    cout << "WA" << endl;
    return 0;
  }

  ll c = 0;
  REP(i, 1, S.size()) {
    if (isupper(S[i])) {
      c++;
    }
  }
  if (c != 1) {
    cout << "WA" << endl;
    return 0;
  }
  cout << "AC" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
const int inf = 1e9;
using namespace std;






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

    double d, t, s;
    cin >> d >> t >> s;
    cout << (d/s <= t ? "Yes\n" : "No\n");


    return 0;
}


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

class MainClass
{
    static void Main()
    {
        int A = int.Parse(Console.ReadLine());
        int B = int.Parse(Console.ReadLine());
        int C = int.Parse(Console.ReadLine());
        var X = int.Parse(Console.ReadLine());
        int ans = 0;
        for (int i = 0; i < A+1; i++)
        {
            for (int j = 0; j < B+1; j++)
            {
                for (int k = 0; k < C+1; k++)
                {
                    if (500 * i + 100 * j + 50 * k == X)
                        ans++;
                }
            }
        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 27528
import sys

d = [0] * 26
def judge(n, t):
    today = t[n - 1] - 1
    res = S[n - 1][today]
    for j, dd in enumerate(d):
        if today != j:
            res -= C[j] * (n - dd)
    return res

D = int(input())
C = list(map(int, sys.stdin.readline().rsplit()))
S = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(D)]

d = [0] * 26
res = 0
tt = []
for i in range(1, D + 1):
    maxi = 0
    for j in range(26):
        tt.append(j + 1)
        jg = judge(i, tt)
        if maxi < jg:
            maxT = j + 1
            maxi = jg
        tt.pop()
    d[maxT - 1] = i
    tt.append(maxT - 1)
    print(maxT)


Measured memory_bytes: 9368
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define brep(index,num) for(int index=num-1;index>=0;index--)
#define brep1(index,num) for(int index=num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int N;
	scan(N);
	char t[334];
	char ans[334];
	vint r,b;
	int firsti=1,lasti=N+1;
	string T;

	printf("? ");
	for(int j=firsti;j<=firsti+N-1;j++){
		printf("%d ",j);
	}
	kaigyo;
	std::flush(std::cout);
	scan(T);
	t[firsti]=T[0];

	printf("? ");
	for(int j=lasti;j<=lasti+N-1;j++){
		printf("%d ",j);
	}
	kaigyo;
	std::flush(std::cout);
	scan(T);
	t[lasti]=T[0];

	int midi;
	while(firsti+1<lasti){
		midi=(firsti+lasti)/2;
		printf("? ");
		for(int j=midi;j<=midi+N-1;j++){
			printf("%d ",j);
		}
		kaigyo;
		std::flush(std::cout);
		scan(T);
		if(T[0]=='-'){
			int gomi[2];
			gomi[334]=114514;
			return 0;
		}
		t[midi]=T[0];
		if(t[midi]==t[1]){
			firsti=midi;
		}
		else{
			lasti=midi;
		}
	}
	ans[firsti]=t[firsti];
	ans[firsti+N]=t[lasti];

	vint que1;
	rep1(i,N-1){
		que1.push_back(firsti+i);
	}
	vint que2;
	rep1(i,N-1){
		int p=firsti+N+i;
		if(p>2*N) p-=2*N;
		que2.push_back(p);
	}

	rep(i,N-1){
		printf("? ");
		rep(j,que1.size()){
			printf("%d ",que1[j]);
		}
		printf("%d\n",que2[i]);
		std::flush(std::cout);
		string T;
		scan(T);
		if(T[0]=='-'){
			int gomi[2];
			gomi[334]=114514;
			return 0;
		}
		ans[que2[i]]=T[0];
	}

	rep(i,N-1){
		printf("? ");
		rep(j,que2.size()){
			printf("%d ",que2[j]);
		}
		printf("%d\n",que1[i]);
		std::flush(std::cout);
		string T;
		scan(T);
		if(T[0]=='-'){
			int gomi[2];
			gomi[334]=114514;
			return 0;
		}
		ans[que1[i]]=T[0];
	}

	printf("! ");
	rep1(i,2*N){
		printf("%c",ans[i]);
	}
	kaigyo;
	return 0;
}


Measured memory_bytes: 724
行数, 列数 = map(int, input().split())

#行列の初期化
行列 = [[0 for _ in range(列数)] for __ in range(行数)]

#データをもとに行列を作成
for 現在行 in range(行数):
    行データ = list(map(int, input().split()))
    for 現在列 in range(列数):
        行列[現在行][現在列] = 行データ[現在列]

#ベクトルデータを取得
ベクトル = [0 for _ in range(列数)]
for 現在行 in range(列数):
    ベクトル[現在行] = int(input())

答え = []
#ベクトルを掛ける
for i in range(行数):
    c = 0
    for j in range(列数):
        c += 行列[i][j] * ベクトル[j]
        
    答え.append(c)

#表示
for i in range(len(答え)):
    print(答え[i])


Measured memory_bytes: 6068
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include<stack>
#include<tuple>
using namespace std;
#define INF 1100000000000
#define MAX 1100000
#define MOD 1000000007
typedef long long ll;
typedef pair<int,int> P;
typedef pair<pair<int,int>,int> p;
typedef pair< pair<int,int>, int> p; 
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)

ll fac[MAX],finv[MAX],inv[MAX];
//http://drken1215.hatenablog.com/entry/2018/06/08/210000
//テーブルを作る前処理　O(n)
//pが素数でなくてはならない
void COMinit(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<MAX;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}
//二項係数計算
ll 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();
    int X,Y; cin>>X>>Y;
    int x,y; x=X;y=Y;
    X=max(x,y);
    Y=min(x,y);
    ll sum=0;
    for(int i=1;i<=Y;i++){
        if(X-Y+2*Y-2*i!=i) continue;
        sum+=COM(i,Y-i);
        sum%=MOD;
        //cout<<i<<" "<<sum<<endl;
    }
    cout<<sum<<endl;
    
}



Measured memory_bytes: 25984
#include <iostream>
#include <vector>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<map>
#include<bitset>
#include<math.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
typedef pair<int,int> pint;
typedef long long ll;
const int inf   = 1e9+7;
const ll  longinf = 1LL<<60;
const int mod=1e9+7;
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};

int main(){
  int n,a,b;
  cin>>n>>a>>b;
  int x[n],c[n];
  rep(i,n){
    int l,r;
    cin>>l>>r>>c[i];
    x[i]=a*r-b*l;
    }
  int dp[41][10000];
  rep(i,10000)dp[0][i]=inf;
  dp[0][5000]=0;
  int ans=inf;
  rep(i,n){
    rep(j,10000){
      if(0<=j-x[i]&&j-x[i]<10000)dp[i+1][j]=min(dp[i][j],dp[i][j-x[i]]+c[i]);
      else dp[i+1][j]=dp[i][j];
      }
    ans=min(ans,dp[i][5000-x[i]]+c[i]);
    }
  if(ans==inf)ans=-1;
  cout<<ans<<endl;
  return 0;         
  }

Measured memory_bytes: 1792
n = int(input())
A = list(map(int, input().split()))

def battle(lis):
  while True:
    if len(lis) == 1: break
    lis = [i for i in lis if i != 0]
    lis.sort()
    for i in range(len(lis)-1):
      lis[i+1] %= lis[0]
  return lis[0]

print(battle(A))

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

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

#define pb push_back
#define in ,
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod 1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

int main() {
  int w;
  while(cin >> w) {
    if(w == -1) return 0;
    int ans = 0;
    if(w > 30) ans += (w - 30) * 160, w = 30;
    if(w > 20) ans += (w - 20) * 140, w = 20;
    if(w > 10) ans += (w - 10) * 125, w = 10;
    ans += 1150;
    cout << 4280 - ans << endl;
  }
}

Measured memory_bytes: 3060
fun main(args: Array<String>) {
    readLine()
    val (t, a) = readLine()!!.split(' ').map { it.toInt() }
    val hs = readLine()!!.split(' ').map { it.toInt() }

    var m = Double.MAX_VALUE
    var r = -1

    hs.forEachIndexed { i, x ->
        val y = Math.abs(a - (t - x * 0.006))
        if (y < m) {
            m = y
            r = i
        }
    }

    println(r + 1)
}


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

#define REP(i, n) for (int i = 0; i < (n); ++i)

int main(void) {
    const int INF = 1 << 30;
    int n, ans = INF, sum = 0, part_sum = 0;

    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    vector<int> w(n);
    REP(i, n) {
        cin >> w[i];
        sum += w[i];
    }

    REP(i, n - 1) {
        part_sum += w[i];
        ans = min(ans, abs(part_sum - abs(sum - part_sum)));
    }

    cout << ans << "\n";
    return 0;
}

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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int a,b,c,d; cin>>a>>b>>c>>d;
	cout << min(a,b)+min(c,d) << endl;
	return 0;
}


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

using namespace std;

void hawawa()
{
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto&& i : a) {
    cin >> i;
  }
  auto b = a;
  sort(b.begin(), b.end());
  for (auto&& i : a) {
    if (b[n / 2] <= i) {
      cout << b[n / 2 - 1] << "\n";
    } else {
      cout << b[n / 2] << "\n";
    }
  }
}

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

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

using namespace std;

const int N = 200 * 1000 + 17;
const int MOD = 1000 * 1000 * 1000 + 7;

int n;
int a[N];
long long dp[N], f[N];

bool read() {
    if (!(cin >> n))
        return false;

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

    return true;
}

void solve() {
    dp[0] = 1;

    for (int i = 1; i <= n; ++i)
        dp[i] = (a[i] == a[i - 1]) ? dp[i - 1] : (f[a[i]] += dp[i - 1]) %= MOD;

    cout << dp[n] << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    while (read())
        solve();

    return 0;
}



Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
int main() {
  string S, T;
  cin >> S >> T;
  int sum = 0;
  for (int i = 0; i < S.size(); i++) {
    if (S.at(i) != T.at(i)) {
      S.at(i) = T.at(i);
      sum += 1;
    }
  }
  cout << sum << endl;
}
    
  
  

Measured memory_bytes: 3920
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using ll = long long;
const long long INF = 1LL << 60;
const int MOD = 1e9 + 7;

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


/* ACL */

//using namespace atcoder;



int main(){
    int N,K;
    cin >> N >> K;
    vector<int> LR(K*2);

    rep(i,K){
        int l,r;
        cin >> l >> r;
        LR.at(i*2) = l;
        LR.at(i*2+1) = r;
    }
    sort(LR.begin(),LR.end());

    vector<ll> dp(N,0);
    
    ll mod = 998244353;
    ll shakutori = 0;

    dp[0] = 1;
    rep(i,N){
        if(i == 0){
            continue;
        }

        rep(j,LR.size()){
            if(j%2 == 0){
                if(LR[j] <= i){
                    shakutori += dp[i-LR[j]];
                }
            }else{
                if(LR[j] <= i-1){
                    shakutori -= dp[i-LR[j]-1];
                }
            }
            shakutori %= mod;
            if(shakutori < 0){
                shakutori += mod;
            }
        }
        dp[i] = shakutori;
    }
    cout << dp[N-1]<<endl;
    return 0;
}

Measured memory_bytes: 4832
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 1007681537;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";

void chemthan() {
    int n; cin >> n;
    int cnt = 0, pv = -1;
    int res = 0;
    FOR(i, 0, n) {
        int x; cin >> x;
        if (x != pv) {
            res += cnt >> 1;
            pv = x;
            cnt = 1;
        }
        else {
            cnt++;
        }
    }
    res += cnt >> 1;
    cout << res << "\n";
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0), cin.tie(0);
    if (argc > 1) {
        assert(freopen(argv[1], "r", stdin));
    }
    if (argc > 2) {
        assert(freopen(argv[2], "wb", stdout));
    }
    chemthan();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

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

		long n = scan.nextLong();
		long num1 = 0;
		long num2 = 0;
		long distance = (long)Math.pow(10, 12);
		boolean judge = false;

		for(long i = 2;i <= Math.sqrt(n);i++) {
			if(n % i == 0) {
				judge = true;

				if(Math.abs((n / i) - i) < distance) {
					num1 = n / i;
					num2 = i;
				}
			}
		}

		if(judge) {
			System.out.println((num1 - 1) + (num2 - 1));
		}else {
			System.out.println(n - 1);
		}
	}
}


Measured memory_bytes: 23764
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            var N = cin.ReadInt;
			var arr = cin.ReadIntArray(N);

			int cnt = 1;
			int isInc = 0;
			
			for (int i = 1; i < N; i++)
			{
				if (arr[i] > arr[i-1])
				{
					if (isInc == 0)
					{
						isInc = 1;
					}else if (isInc == -1)
					{
						cnt++;
						isInc = 0;
					}
				}else if (arr[i] < arr[i - 1])
				{
					if(isInc == 0)
					{
						isInc = -1;
					}else if (isInc == 1)
					{
						cnt++;
						isInc = 0;
					}
				}
			}

			Console.WriteLine(cnt);

        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }
}

Measured memory_bytes: 22496
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const ll INF = 1e18;
const long double EPS = 1e-10;

int main() {
  string s;
  cin >> s;
  int x, y;
  cin >> x >> y;

  int n = s.size();
  s += 'T';
  vector<vector<int>> w(2);
  int com = -1, cnt = 0;
  rep(i, n + 1) {
    if (s[i] == 'F') cnt++;
    else {
      if (com == -1) x -= cnt;
      else if (com != -1 && cnt > 0) w[com].push_back(cnt);
      com = (com + 1) % 2;
      cnt = 0;
    }
  }

  vector<int> m(2, 0), sum(2, 0);
  rep(i, 2) {
    m[i] = w[i].size();
    rep(j, m[i]) {
      sum[i] += w[i][j];
    }
  }

  if (abs(y) > sum[0] || abs(x) > sum[1]) {
    cout << "No" << endl;
    return 0;
  }
  if ((abs(y) - sum[0]) & 1 || (abs(x) - sum[1]) & 1) {
    cout << "No" << endl;
    return 0;
  }

  vector<int> v(2);
  v[0] = (sum[0] - abs(y)) / 2, v[1] = (sum[1] - abs(x)) / 2;
  vector<vector<bool>> dp(max(m[0], m[1]) + 1, vector<bool>(max(sum[0], sum[1]) + 1, false));
  dp[0][0] = true;
  rep(i, m[0]) {
    rep(j, sum[0] + 1) {
      if (dp[i][j]) {
        dp[i + 1][j] = true;
        dp[i + 1][j + w[0][i]] = true;
      }
    }
  }
  if (!dp[m[0]][v[0]]) {
    cout << "No" << endl;
    return 0;
  }

  rep(i, m[1] + 1) {
    rep(j, sum[1] + 1) {
      dp[i][j] = false;
    }
  }
  dp[0][0] = true;
  rep(i, m[1]) {
    rep(j, sum[1] + 1) {
      if (dp[i][j]) {
        dp[i + 1][j] = true;
        dp[i + 1][j + w[1][i]] = true;
      }
    }
  }
  if (!dp[m[1]][v[1]]) {
    cout << "No" << endl;
    return 0;
  }
  cout << "Yes" << endl;
  
  return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a,b,k; cin>>a>>b>>k;
  vector<int> v;
  for(int i=min(a,b); i>0; i--) if(!(a%i||b%i)) if(!(--k)){cout<<i; break;}
}

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

int main() {
	// your code goes here
	int n,i,sum,b,c,q;
	cin>>n;
	int a[n];
	for(i=1;i<=n;i++)
	cin>>a[i];
	cin>>q;
	while(q--)
	{
	    cin>>b>>c;
	    sum=0;
	    for(i=1;i<=n;i++)
	    {
	        if(b==i)
	        {
	            sum+=c;
	        }
	        else
	        sum+=a[i];
	    }
	    cout<<sum<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
  int N,i,M;
  scanf("%d %d",&N,&M);
  
  int A[N],sum=0,number=0;
  for(i=0;i<N;i++)
  {
  scanf("%d",&A[i]);
    sum=sum+A[i];
  }
  
  for(i=0;i<N;i++)
  {
  if(A[i]*4*M>=sum)
    number++;
  }
  
  if(number<M)
    printf("No\n");
  
  else
    printf("Yes\n");
  
  return 0;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n,m;
	cin>>n>>m;
	if(n%3==0||m%3==0)
	{
		puts("0");
		return 0;
	}
	long long ans=min(n,m);
	for(long long i=1;i<n;i++)
	{
		long long x=max(i,n-i),y=min(i,n-i);
		long long a1=y*m,a2=x*m,a3;
		a3=(m/2)*x;
		a2=a2-a3;
		ans=min(ans,max(max(abs(a1-a2),abs(a2-a3)),abs(a1-a3)));
	}
	swap(n,m);
	for(long long i=1;i<n;i++)
	{
		long long x=max(i,n-i),y=min(i,n-i);
		long long a1=y*m,a2=x*m,a3;
		a3=(m/2)*x;
		a2=a2-a3;
		ans=min(ans,max(max(abs(a1-a2),abs(a2-a3)),abs(a1-a3)));
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
def check(x)
  c = 0
  while x>0
    ppc = x.to_s(2).count('1')
    x %= ppc
    c += 1
  end
  return c
end

n = gets.strip.to_i
x = gets.strip
ppc = x.count('1') #popcount
ppcp = ppc + 1
ppcm = ppc - 1
# xp,xm = x % ppcp,ppcm
xp = 0
xm = 0
dp = 1
dm = 1
n.times do |i|
  if x[-i-1] == '1'
    xp += dp
    xp -= ppcp if xp >= ppcp
    if ppc > 1
      xm += dm
      xm -= ppcm if xm >= ppcm
    end
  end
  dp *= 2
  dp %= ppcp
  if ppc > 1
    dm *= 2
    dm %= ppcm
  end
end
n.times do |i|
  if x[i] == '0'
    xt = xp + 2.pow(n-1-i, ppcp)
    xt -= ppcp if xt >= ppcp
    if xt == 0
      p 1
    else
      p check(xt) + 1
    end
  else
    if ppc == 1
      p 0
    else
      xt = xm - 2.pow(n-1-i, ppcm)
      xt %= ppcm
      if xt == 0
        p 1
      else
        p check(xt) + 1
      end
    end
  end
end


Measured memory_bytes: 14596
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, a, b) for(int i = (a); i <= (b); i++)
#define PER(i, a, b) for(int i = (a); i >= (b); i--)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define all(S) (S).begin(), (S).end()
#define pf push_front
#define pb push_back
#define mk make_pair
#define S second
#define F first
typedef long long ll;
typedef long double lf;
typedef pair<int, int> ii;
const int MAX = 2e5+5;

int main(int argc, char** argv) {
	char c;
	scanf("%c", &c);
	printf("%c\n", isupper(c) ? 'A' : 'a');
	return 0;
}



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

int main() {
  int N, M;
  cin >> N >> M;
  // グラフへの入力
  Graph G(N);
  for (int i=0; i<M; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    G[a].push_back(b);
    // 無向グラフの場合は以下を追加
    G[b].push_back(a);
  }
  // BFSのためのデータ構造
  vector<int> dist(N, -1); // 全頂点を「未訪問」に初期化
  queue<int> que;
  // 初期条件 (頂点0を初期ノードとする)
  dist[0] = 0;
  que.push(0); // 0を発見済み頂点にする
  // BFS開始 (キューが空になるまで探索を行う)
  while (!que.empty()) {
    int v = que.front(); // キューから先頭頂点を取り出す
    que.pop();
    // vから辿れる頂点をすべて調べる
    for (int nv: G[v]) {
      if (dist[nv]!=-1) continue; // すでに発見済みの頂点は探索しない
      // 新たな未発見頂点nvについて距離情報を更新してキューに追加する
      dist[nv] = dist[v]+1;
      que.push(nv);
    }
  }
  cout << "Yes" << endl;
  for (int v=1; v<N; v++) {
    int num = MAX;
    for (int nv: G[v]) num = min(num, dist[nv]);
    for (int nv: G[v]) {
      if (num==dist[nv]) {
        cout << nv+1 << endl;
        break;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 10268
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.TreeSet;

public class Main {
	int H,W,N;
	int[] a,b;
	Set<P> color,point;
	long[] cnt;

	private class P implements Comparable<P>{
		int x,y;
		public P(int y,int x){
			this.x = x;
			this.y = y;
		}

		public int compareTo(P p){
			if(this.x == p.x && this.y == p.y)return 0;

			if(this.y < p.y)return -1;
			if(this.y > p.y)return 1;

			if(this.x < p.x)return -1;
			else return 1;
		}
	}

	public void solve() {
		H = nextInt();
		W = nextInt();
		N = nextInt();

		color = new TreeSet<P>();
		point = new TreeSet<P>();

		a = new int[N];
		b = new int[N];
		cnt = new long[10];
		cnt[0] = (long)(H - 2)* (W - 2);
		for(int k = 0;k < N;k++){
			a[k] = nextInt() - 1;
			b[k] = nextInt() - 1;

			color.add(new P(a[k],b[k]));

			for (int i = -2; i <= 0; i++) {
				for (int j = -2; j <= 0; j++) {
					if (a[k] + i >= 0 && b[k] + j >= 0 && a[k] + i + 3 <= H && b[k] + j + 3 <= W) {
						point.add(new P(a[k] + i, b[k] + j));
					}
				}
			}
		}

		for(P p : point){
			int c = 0;
			for(int i = 0;i < 3;i++){
				for(int j = 0;j < 3;j++){
					if(color.contains(new P(p.y + i,p.x + j))){
						c++;
					}
				}
			}
			cnt[c]++;
		}

		for(int i = 1;i <= 9;i++){
			cnt[0] -= cnt[i];
		}

		for(int i = 0;i < 10;i++){
			out.println(cnt[i]);
		}

	}

	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

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

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

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

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

Measured memory_bytes: 102220
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 20;
ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

int main() {
	int N, Y;
	scanf("%d %d", &N, &Y);
	Y /= 1000;

	int a, b, c;
	for (c = Y % 5; c <= Y; c += 5) {
		N -= c;
		Y -= c;
		a = Y / 5 - N;
		b = 2 * N - Y / 5;
		if (a >= 0 && b >= 0) return !printf("%d %d %d\n", a, b, c);
		N += c;
		Y += c;
	}
	return !printf("-1 -1 -1\n");
}
//*/

Measured memory_bytes: 256
#include<bits/stdc++.h>
    using namespace std;
     
    int main()
    {
       int n;
      cin>>n;
       if(n%1000==0)
       {
         cout<<0;
       }
      else if(n>1000)
      {
          int x=n%1000;
        cout<<1000-x;
      }
      else
      {
          cout<<1000-n;
      }
    }

Measured memory_bytes: 3632
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>

template <class T>
T generalDistance(const std::vector<T> &lhs, const std::vector<T> &rhs,
                  const T &p) {
  T sum = 0.0;
  for (int i = 0; i < lhs.size(); i++) {
    sum += pow(abs(lhs[i] - rhs[i]), p);
  }
  return pow(sum, 1.0 / p);
}

template <class T>
T chebyshevDistance(const std::vector<T> &lhs, const std::vector<T> &rhs) {
  T max = -1.0;
  for (int i = 0; i < lhs.size(); i++) {
    T val = abs(lhs[i] - rhs[i]);
    if (val > max) max = val;
  }
  return max;
}

template <class T>
std::vector<T> getElements(int n) {
  std::vector<T> vec;
  while (n-- > 0) {
    T x;
    std::cin >> x;
    vec.push_back(x);
  }
  return vec;
}

int main() {
  int n;
  std::cin >> n;
  auto vecA = getElements<double>(n), vecB = getElements<double>(n);
  std::cout << std::fixed << std::setprecision(6);
  std::cout << generalDistance(vecA, vecB, 1.0) << std::endl;
  std::cout << generalDistance(vecA, vecB, 2.0) << std::endl;
  std::cout << generalDistance(vecA, vecB, 3.0) << std::endl;
  std::cout << chebyshevDistance(vecA, vecB) << std::endl;
  return 0;
}



Measured memory_bytes: 3476
using System;

class D
{
	static void Main()
	{
		var n = long.Parse(Console.ReadLine());

		var r = 0L;
		for (long i = 1; i * i + i < n; i++) if (n % i == 0) r += n / i - 1;
		Console.WriteLine(r);
	}
}


Measured memory_bytes: 13140
//=template==================================================================//
// include
#include <vector>
#include <list>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <numeric>
 
// namespace
using namespace std;
 
// define
#define FOR(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define REP(i,n) FOR(i,0,n)
 
// typedef
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef long long LL;
 
// conversion
inline int toInt(string s) {int v; istringstream sin(s); sin>>v; return v;}
template<class T> inline string toString(T x) {ostringstream sout; sout<<x; return sout.str();}
//===========================================================================//
 
//=function prototype========================================================//
VI getDigits(int n);
//===========================================================================//
 
//=variables=================================================================//
 
//===========================================================================//
int main(void)
{
  // Scan begin.
  int n;
  cin >> n;
  // Scan done.
 
  // Code begin.
  VI digits = getDigits(n);
  int sum = accumulate(digits.begin(), digits.end(), 0);
  if (sum==1) {
    cout << 10 << endl;
  }
  else {
    cout << sum << endl;
  }
  // Code done.
 
  return 0;
}
 
//=functions=================================================================//
VI getDigits(int n) {
  VI digits;
  while (n>0) {
      digits.push_back(n%10);
      n /= 10;
  }
  return digits;
}
//===========================================================================//

Measured memory_bytes: 256
import scala.math.pow

object Main extends App {

  val sc = new java.util.Scanner(System.in)
  sc.useDelimiter("\n")
  val N = sc.nextInt()
  val X = sc.next().split(' ').map(_.toInt).toList
  val max = X.max
  val results = for (i <- 1 to max) yield {
    X.map(n => pow(i - n, 2).toInt).sum
  }
  println(results.min)
}

Measured memory_bytes: 55608
compare=lambda a,b: a.real<b.real if a.real!=b.real else a.imag<b.imag
cross=lambda a,b: (a.conjugate()*b).imag
dot=lambda a,b: (a.conjugate()*b).real

def solve(poly, p):
	f=False
	for i in range(len(poly)):
		a=poly[i]-p
		b=poly[(i+1)%len(poly)]-p
		if a.imag>b.imag: a,b=b,a
		if a.imag<=0 and 0<b.imag and cross(a,b)<0: f=not f
		if cross(a,b)==0 and dot(a,b)<=0: return 1
	return 2 if f else 0

checkio=lambda data: solve([complex(*e) for e in data[0]],complex(*data[1]))

n=int(raw_input())
poly=[[float(e) for e in raw_input().split()] for i in range(n)]
n=int(raw_input())
try:
	for i in range(n):
		print(checkio([poly,[float(e) for e in raw_input().split()]]))
except EOFError:
	pass

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

public static partial class Program
{
    public static void Main()
    {
        var s = CRL();
        if (s[0] == s[1] || s[1] == s[2] || s[2] == s[3])
        {
            CWL("Bad");
            return;
        }
        
        CWL("Good");
    }
}

public static partial class Program
{
    //テンプレここから
    public static int Sigma(int n, int next = 1, int val = 0) => next > n ? val : Sigma(n, next + 1, val + next);
    public static long GCD(long a, long b) => b == 0 ? a : GCD(b, a % b);
    public static int GCD(int a, int b) => b == 0 ? a : GCD(b, a % b);
    public static long LCM(long a, long b) => a * b / GCD(a, b);
    public static int LCM(int a, int b) => a * b / GCD(a, b);
    public static string CRL() => Console.ReadLine();
    public static void CWL(object obj) => Console.WriteLine(obj);
    public static int ToInt(this double d) => (int) d;
    public static long ToLong(this double d) => (long) d;
    public static int ToInt(this string str) => int.Parse(str);
    public static long ToLong(this string str) => long.Parse(str);
    public static long[] ToLong(this IEnumerable<string> strs) => strs.Select(x => x.ToLong()).ToArray();
    public static int[] ToInt(this IEnumerable<string> strs) => strs.Select(x => x.ToInt()).ToArray();
    public static long[] ArrayLongs(this string str, char opr = ' ') => str.Split(opr).ToLong();
    public static int[] ArrayInts(this string str, char opr = ' ') => str.Split(opr).ToInt();
    public static long Diff(long a, long b) => Math.Abs(Math.Max(a, b) - Math.Min(a, b));
    public static int Diff(int a, int b) => Math.Abs(Math.Max(a, b) - Math.Min(a, b));
    public static long Sign(this long i) => Math.Sign(i);
    public static bool IsEven(this long i) => i % 2 == 0;
    public static bool IsEven(this int i) => i % 2 == 0;
    public static readonly int[] Dx = {0, -1, 0, 1};
    public static readonly int[] Dy = {-1, 0, 1, 0};
    public const int Mod = 1000000007;
    public static string alphabet = "abcdefghijklmnopqrstuvwxyz";
    public static long ToLong(this char c) => c.ToString().ToLong();
    public static int ToInt(this char c) => c.ToString().ToInt();
    public static long[] Sort(this long[] array) => array.OrderBy(x => x).ToArray();
    public static int[] Sort(this int[] array) => array.OrderBy(x => x).ToArray();
    public static long[] DSort(this long[] array) => array.OrderByDescending(x => x).ToArray();
    public static int[] DSort(this int[] array) => array.OrderByDescending(x => x).ToArray();
    public static string Join(this IEnumerable<string> array, string sep = "") => string.Join(sep, array);
    public static string Join(this IEnumerable<char> array, string sep = "") => string.Join(sep, array);

    public static string JoinToStr(this IEnumerable<int> array, string sep = "")
        => array.Select(x => x.ToString()).Join(sep);

    //テンプレここまで
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define rep(i,N) for(int i=0;i<N;i++)
using namespace std;
int main(){
int N,M,K;
int d[200][200];
int inf = 1e9;
cin>>N>>M>>K;
rep(i,N) rep(j,N) d[i][j] = inf;
rep(i,N) d[i][i] = 0;
vector<int> ks;
rep(i,K){
int x;
cin>>x;
x--;
ks.push_back(x);
}
sort(ks.begin(),ks.end());
rep(i,M){
int a,b,c;
cin>>a>>b>>c;
a--,b--;
d[a][b] = d[b][a] = c;
}
rep(i,N) rep(j,N) rep(k,N) d[j][k] = min(d[j][k],d[j][i]+d[i][k]);
int ans = inf;
do{
int s = 0;
rep(i,K-1) s+=d[ks[i]][ks[i+1]];
ans = min(ans,s);
}while(next_permutation(ks.begin(),ks.end()));
cout<<ans<<endl;
}

Measured memory_bytes: 384
s = list(input())
b = s[0]
dp = [0]*len(s)
dp[0] = 1

for i in range(1,len(s)):
    if s[i] != s[i-1]:
        dp[i] = dp[i-1]+1
    else:
        dp[i] = dp[i-1]
        if i >=2:
            dp[i] = max(dp[i],dp[i-2]+1)
        if i >= 3:
            dp[i] = max(dp[i],dp[i-3]+2)
print(dp[-1])


Measured memory_bytes: 12312
#include <bits/stdc++.h>
#define newl "\n"
using namespace std;
using lli = long long int;
using vvint = vector <vector <int>>;
const int mod = 1e9 + 7;

void solve(){
	int k;
	cin >> k;
	int num = 7;
	for(int i = 1;i <= k;++i){
		if(num % k == 0){
			cout << i << newl;
			return;
		}
		num = (10 * num % mod + 7) % k;
	}
	cout << -1 << newl;
	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(10);
	#ifdef EXECUTE_LOCALLY
		   freopen("in.txt","r",stdin);
	#endif
	int t = 1;
	//cin >> t;
	while(t--) solve();
	#ifdef EXECUTE_LOCALLY
    	cout << setprecision(3) << "program time: " << (double)clock() / CLOCKS_PER_SEC << newl;
	#endif
	return 0;
}


Measured memory_bytes: 3600
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <stack>
#include <vector>
#include <random>
#include <unordered_set>
//#include <set>
#include <queue>
using namespace std;
typedef long long ll;

vector< pair<int,int> > leaf_to_root(const vector<int> &u,const vector<int> &v,const int root){
	// return <parent,child>
	int yet = 1000000000;
	vector<int> d(u.size()+1,yet);
	vector< pair<int,int> > res;
	queue<int> Q;
	Q.push(root);
	d[root] = 0;
	vector< vector<int> > G(u.size()+1);
	for(int i=0;i<u.size();i++){
		G[u[i]].push_back(v[i]);
		G[v[i]].push_back(u[i]);
	}
	while( Q.size() ){
		int now = Q.front();
		Q.pop();
		for(auto nex:G[now]){
			if(d[nex]!=yet)continue;
			d[nex] = d[now] + 1;
			Q.push(nex);
			res.push_back( make_pair(now,nex) );
		}
	}
	reverse(res.begin(), res.end());
	return res;
}

int main(){
	int N,K;
	cin >> N >> K;
	vector<int> a(N-1),b(N-1),cnt(N,0);
	for(int i=0;i<N-1;i++){
		cin >> a[i] >> b[i];
		a[i]--;b[i]--;
	}
	ll ans = 1 ,MOD = 1000000007;
	auto edge = leaf_to_root(a,b,0);
	reverse(edge.begin(),edge.end());
	for(auto e:edge){
		int p = e.first;
		int c = e.second;
		(ans *= K-cnt[p]-1) %= MOD;
		cnt[p]++;cnt[c]++;
	}
	cout << ans*K%MOD << endl;
}


Measured memory_bytes: 9208
from collections import Counter
x = int(input())
a = list(map(int,input().split()))
c = Counter(a)

suma = sum([v for v in c.values()])
lenc = len(c)
if suma == lenc:
    print(suma)
    exit()
    
b = suma - lenc
if b % 2 == 0:
    print(lenc)
else:
    print(lenc - 1)
    

Measured memory_bytes: 18656
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<math.h>
#include<string>
#include <iomanip>
#include<deque>
#include<queue>
#include<stack>
#include<set>


using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;
const ll LINF = 1e18;
const int INF = 1e9;

//マクロ定義
#define vvint(vec,n,m,l) vector<vector<int>> vec(n, vector<int>(m,l));	// lで初期化
#define vvll(vec,n,m,l) vector<vector<ll>> vec(n,vector<ll>(m,l));
#define vint vector<int>
#define pint pair<int,int>
#define rep(i,a) for(int i=0;i<(a);i++)
#define all(x) (x).begin(),(x).end()
#define debug system("pause")				//デバッグ用
#define ret return 0

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

#define ketasitei setprecision(15) //15桁表示



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

	char c;
    cin>>c;
    c=c+1;
    cout<<c<<endl;
    
	return 0;
}

Measured memory_bytes: 256