akhauriyash/Code-Regression huggingface dataset:
import math
a,b=map(int,input().split())

a_min=math.ceil(a/(0.08))
a_max=(a+1)/(0.08)
b_min=math.ceil(b/(0.1))
b_max=(b+1)/(0.1)
if a_min>=a_max:
    print(-1)
elif b_min>=b_max:
    print(-1)
else:
    if a_min<b_min:
        if b_min<a_max:
            print(b_min)
        else:
            print(-1)
    if b_min<a_min:
        if a_min<b_max:
            print(a_min)
        else:
            print(-1)  
    if a_min==b_min:
        print(a_min)

Measured memory_bytes: 3064
/* Aditya0412 */
#include <bits/stdc++.h>
using namespace std; 
#define int long long 
#define pb push_back 
#define vii vector < int > 
#define pii pair < int , int >
#define fi first
#define all(a)      (a).begin(),(a).end()
#define si(x)       (int)((x).size())
#define debug(x)    cout<<#x<<" is "<<(x)<<endl;cout.flush();  
#define se second 
#define endl        '\n'
#define f(i,a,b)    for(int i=a;i<b;i++)
#define mem(a,x)          memset(a,x,sizeof(a))
#define fastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

// const int  mod=998244353;
const int  mod = 1000000000+7;
const int  N=1000000+6;
#define M_PI           3.14159265358979323846

// int x2[]={+1,-1,+0,+0};
// int y2[]={+0,+0,+1,-1};
// int x2[]={+0,+0,+1,-1,-1,+1,-1,+1};
// int y2[]={-1,+1,+0,+0,+1,+1,-1,-1};
// int x2[]={-2,-2,-1,-1,+1,+1,+2,+2};
// int y2[]={-1,+1,-2,+2,-2,+2,-1,+1};

// === Debug macro starts here ===

int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os,  const Cont& v){
    os<<"[";
    for(auto& x:v){os<<x<<", ";}
    return os<<"]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
    return os<<"{"<<p.first<<", "<<p.second<<"}";
}

// === Debug macro ends here ===

 main() 
{
    fastIO;
    int n;cin>>n;
    int arr[n],brr[n];
    f(i,0,n) 
    cin>>arr[i];
    f(i,0,n)
    cin>>brr[i];

    reverse(brr,brr+n);
    queue< int> q,qq;
    int c;
    f(i,0,n)
    {
        if(arr[i]==brr[i])
        {q.push(i);c=arr[i];}
    }
    bool bo;
    if(q.empty())
    bo=true;
    else
    {
        f(i,0,n)
        if(arr[i]!=c and brr[i]!=c)
        qq.push(i);
        bo=true;
        while(!q.empty())
        {
            int i=q.front();q.pop();
            if(qq.empty())
            {
                bo=false;break;
            }
            else
            {
                /* code */
                int j=qq.front();qq.pop();
                swap(brr[i],brr[j]);
            }
            
        }

    }
    if(bo)
    {
        cout<<"Yes\n";
        f(i,0,n)
        cout<<brr[i]<<' ';
    }
    else
    cout<<"No";
    

}   

Measured memory_bytes: 8124
//include
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <random>

using namespace std;

// 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();
}

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

//math
template <class T>
inline T sqr(T x) { return x * x; }

template <class T>
inline T nCr(T n, T r)
{
    T num = 1;
    for (int i = 1; i <= r; ++i)
    {
        num *= (n - i + 1) / i;
    }
    return num;
}
template <class T>
inline T nPr(T n, T r)
{
    r = n - r;
    T sum = 1;
    int i;
    for (i = n; i >= r + 1; --i)
        sum *= i;
    return sum;
}

template <class T>
inline T facctorial(T k)
{
    T sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

//numeric
template <class T>
inline T gcd(T a, T b)
{
    if (a < b)
    {
        a ^= b;
        b ^= a;
        a ^= b;
    }

    return b ? gcd(b, a % b) : a;
}

template <class T>
inline T lcm(T a, T b)
{
    return a * b / gcd(a, b);
}

//typedef
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())

//repetition
#define FOR(i, a, b) for (int i = (a); i <= (int)(b); ++i)
#define REP(i, n) FOR(i, 0, n)

//constant
constexpr double EPS = 1e-10;
const double PI = acos(-1.0);
constexpr LL INF = 1e10;

//clear memory
#define CLR(a) memset((a), 0, sizeof(a))

//debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;

int main()
{
    string s;
    cin >> s;
    int n = (int)s.size();
    char temp = s[0];
    if (n == 1)
    {
        cout << 1 << endl;
        return 0;
    }
    char now = s[1];
    int cnt = 1;
    for (int i = 1; i < n; ++i)
    {
        if (temp == now)
        {
            if (i != n - 1)
            {
                now += s[i + 1];
            }
        }
        else
        {
            ++cnt;
            temp = now;
            if (i != n - 1)
            {
                now = s[i + 1];
            }
        }
    }
    cout << cnt << endl;
}


Measured memory_bytes: 640
from itertools import combinations
import numpy as np

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

matrix = []
for _ in range(h):
  matrix.append([1 if word=='#' else 0 for word in input()])

h_list = list(range(h))
w_list = list(range(w))

h_check_list = []
w_check_list = []
for i in range(h):
  h_check_list += list(combinations(h_list, i))
for i in range(w):
  w_check_list += list(combinations(w_list, i))

for h_paint in h_check_list:
  for w_paint in w_check_list:
    tmp = np.array(matrix.copy())
    for row in h_paint:
      tmp[row] = [0]*w
    for column in w_paint:
      for i in range(h):
        tmp[i][column] = 0
    if np.sum(tmp)==k:
      cnt+=1
print(cnt)

Measured memory_bytes: 27248
a,b,c,d = list(map(int,list(input())))
ans = []
if a+b+c+d == 7:
    ans = ['+','+','+']
elif a+b+c-d == 7:
    ans = ['+','+','-']
elif a+b-c-d == 7:
    ans = ['+','-','-']
elif a+b-c+d == 7:
    ans = ['+','-','+']
elif a-b+c-d == 7:
    ans = ['-','+','-']
elif a-b-c-d == 7:
    ans = ['-','-','-']
elif a-b-c+d == 7:
    ans = ['-','-','+']
else:
    ans = ['-','+','+']

print('{}{}{}{}{}{}{}=7'.format(a,ans[0],b,ans[1],c,ans[2],d))


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int h[n];
  int dp[n];
  for(int i = 0;i < n;i++)cin >> h[i];
  dp[0] = 0;
  dp[1] = abs(h[1]-h[0]);
  for(int i = 2;i < n;i++){
    dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
  }
  cout << dp[n-1];
}
    

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define vv(T) std::vector<std::vector<T>>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;

int		main(void)
{
	int l, r, d;
	cin >> l >> r >> d;

	int ans = 0;
	for (int i = l; i <= r; ++i)
	{
		if (i % d == 0)
			++ans;
	}
	cout << ans << endl;
}



Measured memory_bytes: 3592
m, n = map(int, input().split())
if m == 1 and n == 1:
  print(1)
elif m == 1 or n == 1:
  print(m * n - 2)
else:
  print(m * n - 4 - (m - 2) * 2 - (n - 2) * 2)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) FOR(i, 0, (n))
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define LAR(a, b) ((a)=max((a),(b)))
#define SML(a, b) ((a)=min((a),(b)))
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
template<typename T>
using pque = priority_queue<T, vector<T>, greater<T>>;
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define ALL(a) (a).begin(), (a).end()
#ifdef LOCAL_DEBUG
#define DEBUG(...) printf(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

int ans[2123] = {};

int main(){
	int n, x, y; scanf("%d%d%d", &n, &x, &y);
	FOR(i, 1, n+1){
		FOR(j, i+1, n+1){
			int d = min({abs(i-j), abs(i-x) + 1 + abs(y-j), abs(i-y) + 1 + abs(x-j)});
			DEBUG("(%d, %d): %d\n", i, j, d);
			ans[d]++;
		}
	}
	FOR(i, 1, n) printf("%d\n", ans[i]);
}


Measured memory_bytes: 256
#include<stdio.h>

//トランプの構造体
struct Card{
  char mark;
  int num;
};

typedef struct Card card;




int main(void){
  int n,i,j,min,flag=0;
  card c1[36],c2[36],temp;
  char a;

  //入力
  scanf("%d%c",&n,&a);
  for(i=0;i<n;i++){
    scanf("%c%d%c",&c1[i].mark,&c1[i].num,&a);
    c2[i]=c1[i];
  }
  
  //バブル
  for(i=0;i<n;i++){
    for(j=n-1;j>i;j--){
      if(c1[j].num < c1[j-1].num){
	temp=c1[j];
	c1[j]=c1[j-1];
	c1[j-1]=temp;
      }
    }
  }

    
  //セレクション
  for(i=0;i<n;i++){
    min=i;
    for(j=i;j<n;j++){
      if(c2[j].num < c2[min].num) min=j;
    }
    temp=c2[min];
    c2[min]=c2[i];
    c2[i]=temp;
  }


  for(i=0;i<n;i++){
    if(i==n-1) printf("%c%d\n",c1[i].mark,c1[i].num);
    else  printf("%c%d ",c1[i].mark,c1[i].num);
  }
  printf("Stable\n");
  
  for(i=0;i<n;i++){
    if(i==n-1) printf("%c%d\n",c2[i].mark,c2[i].num);
    else  printf("%c%d ",c2[i].mark,c2[i].num);
  }
  
  for(i=0;i<n;i++){
    if(c1[i].mark != c2[i].mark) flag=1;
  }
  if(flag==1)printf("Not stable\n");
  else printf("Stable\n");
  
  return 0;
}

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

using namespace std;

int main(){
	string str;
	cin>>str;
	
	int N = str.length();
	long int ans = 0;
	
	int idx = 0;
	for(int i=0;i<N;i++){
		if(str[i] == 'W'){
			ans += (i-idx);
			idx++;
		} 	
	}
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))

using P = pair<s64, int>;

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

    s64 h, w, k;
    cin >> h >> w >> k;

    int si, sj, ti, tj;
    cin >> si >> sj >> ti >> tj;
    --si, --sj, --ti, --tj;
    vector< string > field(h);
    rep (i, h) cin >> field[i];

    const s64 inf = 1e18;
    vs64 d(h * w, inf);
    auto id = [&](int i, int j) { return i * w + j; };

    queue<int> q;
    q.push(id(si, sj));
    d[id(si, sj)] = 0;
    int dy[] = {-1, 0, 1, 0};
    int dx[] = {0, -1, 0, 1};
    while (!q.empty())
    {
        int from = q.front(); q.pop();
        int fi = from / w;
        int fj = from % w;
        rep (i, 4)
        {
            rep (j, k)
            {
                s64 ni = fi + dy[i] * (j + 1);
                s64 nj = fj + dx[i] * (j + 1);
                if (!(IN(0, h, ni) && IN(0, w, nj))) break;
                int to = id(ni, nj);
                if (d[to] < d[from] + 1 || field[ni][nj] == '@') break;
                if (d[to] != inf) continue;
                d[to] = d[from] + 1;
                q.push(to);
            }
        }
    }

    s64 ans = d[id(ti, tj)];
    if (ans == inf) cout << "-1\n";
    else cout << ans << "\n";

    return 0;
}



Measured memory_bytes: 12924
#include <stdio.h>
 
int main(){
	int i,N,K;
	int cnt = 0;
	int a[100001];
	scanf("%d %d",&N,&K);
	for(i=0;i<N;i++){
		scanf("%d",&a[i]);
		if(a[i]>=K) cnt++;
	}
	printf("%d\n",cnt);
	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <climits>
#define ll long long
#define MAX 25 * 1e13
#define N  100010

using namespace std;
int MOD = 1000000007;
vector<vector<ll>> dp(N,vector<ll>(2));

int add_edge(vector<vector<int>> &g, int x , int y ){
    g[x].push_back(y);
    g[y].push_back(x);
    return 0;
}

int dfs2(vector<vector<int>>& g,int cur,int fa){
    //0 is black
    //1 is white
    if( g[cur].size() == 1 && g[cur][0] == fa ){
      dp[cur][0] = 1;
      dp[cur][1] = 1;
      return 0;
    }
    for(int i = 0 ; i < g[cur].size() ; i++ ) if(g[cur][i] != fa ){
        dfs2(g,g[cur][i],cur);
    }
    ll cnt0 = 1;
    ll cnt1 = 1;
    for(int i = 0 ; i < g[cur].size() ; i++ ) if( g[cur][i] != fa ){
        cnt0  = (cnt0 * dp[g[cur][i]][1]) % MOD;
    }
    for(int i = 0 ; i < g[cur].size() ; i++ ) if( g[cur][i] != fa ){
        cnt1 = (cnt1 * (dp[g[cur][i]][1]+dp[g[cur][i]][0]) % MOD ) % MOD;
        
    }
    dp[cur][0] = cnt0;
    dp[cur][1] = cnt1;
    return 0;
}

int main(){
    int n;
    cin >> n;
    vector<vector<int>> g(n+1);
    vector<int> isroot(n+1,1);
    for(int i = 0 ; i < n-1 ; i++ ){
        int n1,n2;
        cin >> n1 >> n2;
        add_edge(g,n1,n2);
        isroot[n2] = 0;
        //add_edge(g,n2,n1);
    }
    //root == 1
    int root = 0;
    for( int i = 1 ; i <= n ; i++ ){
      if( isroot[i] == 1 ){
        root = i;
        break;
      }
    }
    root = 1;
    //dfs1(g,root,-1);//find leaf and initialize
    dfs2(g,root,-1);//clac the # of ways
    int ret =  (dp[root][1] + dp[root][0] ) % MOD;
    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 15744
import java.util.*;

class Main {



	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long A = sc.nextLong();
        long B = sc.nextLong();
        int count = 1;

        //AとBの最大公約数を求める
        long gcdAB = Main.gcd(A, B);

        //最大公約数を、「素数 or 1」になるまで素因数分解
        //新しい素数で割れた時にcountを増やす
        for(long i = 2 ; i <= Math.sqrt(gcdAB); i++){
            //自身の平方根より小さい数字で割り切れない場合、その数は素数である
            if(gcdAB % i == 0) count++;
            while(gcdAB % i == 0){
                gcdAB /= i;
            }
        }
        //gcdABが「素数 or 1」になっているので、素数の場合はcountを増やす
        if(gcdAB > 1) count++;

        System.out.println(count);

    }

    //gcd  = greateset common divisor
    public static long gcd(long A, long B){
        if(B == 0) return A;
        else return gcd(B, A % B);
    }




}







Measured memory_bytes: 21844
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <cstdio>
#include <climits>
#include <complex>
#include <cstdint>
#include <tuple>

#define M_PI       3.14159265358979323846

using namespace std;

//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(); }
inline int readInt() { int x; scanf("%d", &x); return x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()


struct Edge {
    int to, cost, nm;
    Edge(int to, int cost, int nm): to(to), cost(cost), nm(nm) {}
};

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<Edge>> AdjList;
AdjList graph;
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
const int INF = 100000000;

ll GCD(ll a, ll b){
    if(a < b) swap(a, b);
    if(b == 0) return a;
    return GCD(b, a%b);
}

bool cmp(const pii& a, const pii& b){
    if(a.first == b.first){
        return a.second < b.second;
    }
    return a.first < b.first;
}


int N, M;
double r;
int n;

int main() {


    //cout << fixed << setprecision(10);


    int N; cin >> N;
    int A[100010];
    for(int i=0; i<N; ++i) cin >> A[i];

    int sum = 0;
    for(int i=0; i<N; ++i){
        if(i%2==0){
            sum += A[i];
        }else{
            sum -= A[i];
        }
    }
    vector<int> ans;
    int t = 2*A[0];

    int B[100010]={0};
    B[0] = sum;
    for(int j=1; j<N; ++j){
        B[j] = 2*A[j-1] - B[j-1];
    }
    for(int i=0; i<N; ++i){
        if(i) cout << " ";
        cout << B[i];
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 2048
#include<cstdio>
#include <numeric>

using namespace std;

int w,n;
int v[30];

int main(){
    for( int i = 0; i < 30; i++ )
    {
        v[i] = i + 1;
    }
    scanf( "%d \n%d\n", &w, &n );
    while( n > 0 )
    {
        int a,b;
        scanf( "%d,%d\n", &a, &b );
        swap( v[a - 1], v[b - 1] );
        n--;
    }
    
    for( int i = 0; i < w; i++ )
    {
        printf( "%d\n", v[i] );
    }
    return 0;
}


Measured memory_bytes: 2700
listA=[1,3,5,7,8,10,12]
listB=[4,6,9,11]
x,y=map(int,input().split())
if x in listA:
    x = 1
elif x in listB:
    x = 2
else: x = 3
if y in listA:
    y = 1
elif y in listB:
    y = 2
else: y = 3
if x == y:print("Yes")
else:print("No")

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

const long long MOD = 5;
const string YES = "YES";
const string NO = "NO";

void solve(long long A, long long B, long long C){
    for(ll k=1; k<= B; k++){
        if(k*A % B == C) {
            cout << YES << endl;
            return;
        }
    }
    cout << NO << endl;
}

int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    solve(A, B, C);
    return 0;
}


Measured memory_bytes: 256
import sys

MOD = 10 ** 9 + 7


class ModInt:

	def __init__(self, x, inv=None):
		self.x = x.x if isinstance(x, ModInt) else x % MOD
		self.inv = inv

	__str__ = lambda self:str(self.x)
	__repr__ = __str__
	__int__ = lambda self: self.x
	__index__ = __int__

	__add__ = lambda self, other: ModInt(self.x + ModInt(other).x)
	__radd__ = lambda self, other: ModInt(other + self.x)
	__iadd__ = __add__

	__sub__ = lambda self, other: ModInt(self.x - ModInt(other).x)
	__rsub__ = lambda self, other: ModInt(other - self.x)
	__isub__ = __sub__

	__mul__ = lambda self, other: ModInt(self.x * ModInt(other).x)
	__rmul__ = lambda self, other: ModInt(other * self.x)
	__imul__ = __mul__

	__pow__ = lambda self, other: ModInt(pow(self.x, ModInt(other).x, MOD))
	__rpow__ = lambda self, other: ModInt(pow(other, self.x, MOD))
	__pow__ = __pow__

	def __truediv__(self, other):
		if isinstance(other, ModInt) and other.inv != None:
			return ModInt(self.x * other.inv)
		else:
			return ModInt(self.x * pow(ModInt(other).x - 2))
	
	def __rtruediv__(self, other):
		if not self.inv:
			return ModInt(other * pow(self.x - 2))
		else:
			return ModInt(other * self.inv)

	__itruediv__ = __truediv__

	__floordiv__ = __truediv__
	__rfloordiv__ = __rtruediv__
	__ifloordiv__ = __itruediv__

	__mod__ = lambda self, other: ModInt(self.x % other)
	__rmod__ = lambda self, other: ModInt(other % self.x)
	__imod__ = __mod__

	__lt__ = lambda self, other: self.x < ModInt(other).x
	__gt__ = lambda self, other: self.x > ModInt(other).x
	__le__ = lambda self, other: self.x <= ModInt(other).x
	__ge__ = lambda self, other: self.x >= ModInt(other).x
	__eq__ = lambda self, other: self.x == ModInt(other).x
	__ne__ = lambda self, other: self.x != ModInt(other).x

class Fact:
	def __init__(self, MAX):
		MAX += 1
		self.fact = [0] * MAX
		finv = [0] * MAX
		inv = [0] * MAX
		self.fact[0] = 1
		self.fact[1] = 1
		finv[0] = 1
		finv[1] = 1
		inv[1] = 1
		for i in range(2, MAX):
			self.fact[i] = self.fact[i - 1] * i % MOD
			inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
			finv[i] = finv[i - 1] * inv[i] % MOD
		for i in range(MAX):
			self.fact[i] = ModInt(self.fact[i], inv=finv[i])
	def __call__(self, value):
		return self.fact[value]

class Comb:
	def __init__(self, fact):
		self.fact = fact
	def __call__(self, n, r):
		return self.fact(n) // self.fact(n-r) // self.fact(r)

class MiniComb:
	def __init__(self, fact):
		self.fact = fact
	def __call__(self, n, r):
		a = ModInt(1)
		for i in range(r):
			a *= n - i
		return a // self.fact(r)


def main():
	n, a, b = map(int, sys.stdin.readline().split())
	fact = Fact(2*10**5)
	comb = MiniComb(fact)
	print(ModInt(2**ModInt(n) - 1 - comb(n, a) - comb(n, b)))
main()



Measured memory_bytes: 59988
N,M = map(int,input().split())
l_s,l_l,B_s,B_l = [],[],[],[]
for i in range(M):
    a,b = map(int,input().split())
    if a == 1 :
        if b < N:
            B_s.append(b) #Nより小さい
        elif b > N:
            B_l.append(b) #Nより大きい
    if a == N:
        l_l.append(b) #Nより大きい
    elif b == N:
        l_s.append(a) #Nより小さい
common_1 = len(list(set(l_s) & set(B_s)))
common_2 = len(list(set(l_l) & set(B_l)))
if common_1 > 0 or common_2 > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

int a[100001],b[100001];

int f(int i,int j){
	return b[i] - b[j+1];
}

int main(){
	int n,k;
	while( cin >> n >> k , n||k ){
		b[0] = 0;
		for(int i=0 ; i < n ; i++ ){
			cin >> a[i];
			b[0] += a[i];
		}
		for(int i=1 ; i <= n ; i++ ){
			b[i] = b[i-1] - a[i-1];
		}
		int s = f(0,k-1);
		for(int i=1 ; i+k < n ; i++ ){
			s = max( s , f(i,i+k-1) );
		}
		cout << s << endl;
	}
}

Measured memory_bytes: 1240
#include "bits/stdc++.h"
using namespace std;
#define fst first
#define scd second
constexpr int D = 365, n = 26;
int c[n]/*dec sc*/, s[D][n]/*inc_sc*/, ans = 0;
int last[D][n], held[D]; 
random_device seed;
mt19937 rnd(seed());
clock_t start;
inline void init()
{
	scanf("%*d");
	for(int i = 0; i < n; ++i)
	{
		scanf("%d", &c[i]);
	}
	for(int i = 0; i < D; ++i)
	{
		for(int j = 0; j < n; ++j)
		{
			scanf("%d", &s[i][j]);
		}
	}
	for(int i = 0; i < D; ++i)
	{
		for(int j = 0; j < n; ++j)
		{
			last[i][j] = -1;
		}
		held[i] = rnd() % n; 
	}
}
inline void score()
{
	for(int i = 0; i < D; ++i)
	{
		for(int j = 1; j < n; ++j)
		{
			last[i][j] = last[i - 1][j];
		}
		last[i][held[i]] = i;
		ans += s[i][held[i]];
		for(int j = 0; j < n; ++j)
		{
			ans -= c[j] * (i - last[i][j]);
		}
	}
}
void local_search()
{
	for(int d, t, _ans; (clock() - start) * 100 < 197 * CLOCKS_PER_SEC; )
	{
		_ans = ans;
		d = rnd() % D;
		t = rnd() % n;
		for(int i = d; last[i][held[d]] == d; ++i)
		{
			_ans += c[held[d]] * (i - d);
		}
		/*if(d > 0)
		{
			for(int i = last[d - 1][held[d]]; last[i]
				*/
	}		
}
inline void output()
{
	for(int i = 0; i < D; ++i)
	{
		printf("%d\n", held[i] + 1);
	}
}
signed main()
{
	start = clock();
	init();
	score();
	local_search();
	output();
}


Measured memory_bytes: 3908
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010


int main(){
  int N, H, prevH;
  int step = 0, ans = 0;

  cin >> N;

  prevH = -1;

  for (int i=0; i<N; i++) {
    cin >> H;

    if (prevH >= H) {
      step++;
    } else {
      step = 0;
    }

    ans = max(ans, step);
    prevH = H;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;


	public class Main {
		
		

		public static void main(String[] args) {

			Scanner sc = new Scanner(System.in);
	        
			int n = sc.nextInt();
			int[] p = new int[n];
			int num = 0;
			int ren = 0;
			int zenkai = -1;
			
			for(int i=0;i<n;i++) {
				p[i] = sc.nextInt();
				if(p[i]==i+1) {
					num++;
					if(zenkai==i) {
						ren++;
						zenkai = -1;
						continue;
					}
					zenkai = i+1;
				}
			}
			
			System.out.println(num-ren);
			
			
			
		}
		
	}


Measured memory_bytes: 52836
a,b,k = [int(x) for x in input().split()]
res = []
for i in range(a,min(b,k+a-1) + 1):
  res.append(i)
for i in range(max(b-k+1,a),b+1):
  res.append(i)
res = list(set(res))
res.sort()
for i in range(len(res)):
  print(res[i])

Measured memory_bytes: 9144
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<stack>
#include<queue>
#include<sstream>
#include<string>
#include<cassert>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i);

using namespace std;

int cnt1[1000100], cnt2[1000100];

int main() {
	vector<int> nums;

	int a = 2, c = 1, num = 1;

	while (num < 1000100) {
		nums.push_back(num);
		c += a;
		++a;
		num += c;
	}

	rep(j,nums.size()) {
		cnt1[nums[j]] = 1;
		if (nums[j] % 2) cnt2[nums[j]] = 1;
	}

	REP(i,1,1000100) {
		rep(j,nums.size()) {
			if (i - nums[j] <= 0) break;

			if (cnt1[i] == 0) cnt1[i] = cnt1[i - nums[j]] + 1;
			else cnt1[i] = min(cnt1[i], cnt1[i - nums[j]] + 1);

			if (nums[j] % 2) {
				if (cnt2[i] == 0) cnt2[i] = cnt2[i - nums[j]] + 1;
				else cnt2[i] = min(cnt2[i], cnt2[i - nums[j]] + 1);
			}
		}
	}

	int n;
	while (cin >> n, n) {
		cout << cnt1[n] << " " << cnt2[n] << endl;
	}
}

Measured memory_bytes: 9032
input1=gets.chomp.split(' ').map!(&:to_i)
input2=gets.chomp.split(' ').map!(&:to_i)
xmin=input1[0]
xmax=input1[0]
loop do
    if input2.include?(xmin) then
        xmin-=1
    else
        puts xmin
        break;
    end
    if input2.include?(xmax) then
        xmax+=1
    else
        puts xmax
        break;
    end
end

Measured memory_bytes: 14408
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;

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

    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n);
    rep(i, m){
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    const int INF = 1001001001;
    vector<int> dist(n, INF);
    dist[0] = 0;
    queue<int> q;
    q.push(0);

    map<int, int> nxt;

    while(!q.empty()){
        int v = q.front();
        q.pop();

        for(int nv: g[v]){
            if(dist[nv] != INF) continue;

            dist[nv] = dist[v] + 1;
            nxt[nv] = v;
            q.push(nv);
        }
    }


    bool flg = false;
    rep(i, n){
        if(dist[i] == INF) flg = true;
    }

    if(flg) cout << "No" << endl;
    else{
        cout << "Yes" << endl;
        rep1(i, n){
            if(dist[i] == 1) cout << 1 << endl;
            else cout << nxt[i]+1 << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 14796
#include<iostream>
using namespace std;
int main(){
	char brick[100010];
	int cnt1=0,cnt2=0;
	int l=0;
	int flag=0;
	cin>>brick;
	while(brick[l])l++;
	for(int i=0;i<l;i++){
		if(brick[i]-'0'!=flag)cnt1++;
		flag=1-flag;
	} 
	flag=1;
	for(int i=0;i<l;i++){
		if(brick[i]-'0'!=flag)cnt2++;
		flag=1-flag;
	} 
	cout<<(cnt1>cnt2?cnt2:cnt1);
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
using P = pair<int, int>;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 1e9 + 7;

signed main(){
	int n,m;
	cin >> n >> m;
	vector<pair<ll, int>> v(n);
	rep(i,n){
		cin >> v[i].first >> v[i].second;
	}
	sort(ALL(v));
	ll ans = 0;
	rep(i,n){
		if(m - v[i].second >= 0){
			ans += v[i].first * v[i].second;
			m -= v[i].second;
		}else{
			ans += v[i].first * m;
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

int main(){
	int x, y, z;
	scanf("%d %d %d", &x, &y, &z);
	int ans = (x / (y + z));
	if (x % (y + z) < z)
		ans--;
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int[] ary = new int[n];

        for (int i = 0; i < n; i++) {
            ary[i] = Integer.parseInt(sc.next());
        }
        Arrays.sort(ary);
        double x = ary[0];
        for (int i = 1; i < n ; i++) {
            x = (x + ary[i]) / 2;
        }
        System.out.print(x);
    }
}

Measured memory_bytes: 21844
#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

int main(){
	int n,m,x,y;cin>>n>>m>>x>>y;
  vector<int> vx(n),vy(m);
  for(auto&& u:vx)cin>>u;
    for(auto&& u:vy)cin>>u;
  int tx=vx[0],ty=vy[0];
  for(auto&& u:vx)tx=max(tx,u);
    for(auto&& u:vy)ty=min(ty,u);
  if(tx<ty && tx<y && x<ty)cout<<"No War"<<endl;
  else cout<<"War"<<endl;
  
}

Measured memory_bytes: 256
H,W,K = [int(i) for i in input().split()]
c = []
for i in range(H):
  c.append(list(input()))



def calc_black(field):
  co = 0
  for i in field:
    for j in i:
      if j == "#":
        co += 1
  return co

import copy
import itertools

aaa = list(itertools.product([0,1],repeat = H ))
bbb = list(itertools.product([0,1],repeat = W ))


count = 0
for i in aaa:
  for j in bbb:
    c_tmp = copy.deepcopy(c)    
    for ind,ii in enumerate(i):
      if(ii):
        c_tmp[ind] = ["r"]*W
    for ind,jj in enumerate(j):
      if (jj):
        for iii in range(H):
          c_tmp[iii][ind] = "r"
          
    if K == calc_black(c_tmp):
      count += 1


print(count)



Measured memory_bytes: 80012
import sys
from decimal import Decimal

input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))

    ave = sum(A) / Decimal(N)
    min_diff = 100
    for i, a in enumerate(A):
        if abs(ave - a) < min_diff:
            min_diff = abs(ave - a)
            ans = i

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9876
#include <bits/stdc++.h>
using namespace std;
struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20);} } fast;

int main() {
    int n, y;
    cin >> n >> y;
    for (int i = 0; i < n + 1; i++){
        for (int j = 0; j < n + 1 - i; j++){
            if (10000 * i + 5000 * j + 1000 * (n - i - j) == y){
                cout << i << ' ' << j << ' ' << n - i - j << endl;
                return 0;
            }
        }
    }
    cout << -1 << ' ' << -1 << ' ' << -1 << endl;
}

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

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

  vector<int> h(n);
  for (int i = 0; i < n; ++i)
    cin >> h[i];

  sort(h.rbegin(), h.rend());

  long long cnt = 0;
  for (int i = 0; i < n; ++i) {
    if (i < k)
      continue;
    cnt += h[i];
  }

  cout << cnt << endl;
}

Measured memory_bytes: 1024
fn read<T: std::str::FromStr>(
    stdin_lock: &mut std::io::StdinLock,
    buf: &mut Vec<u8>,
    delimiter: u8,
) -> T {
    buf.clear();
    let l = std::io::BufRead::read_until(stdin_lock, delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let n = read::<usize>(&mut stdin_lock, &mut buf, b'\n');
    let mut ts = vec![("".to_owned(), 0, 0); n];
    for i in 0..n {
        ts[i].0 = read(&mut stdin_lock, &mut buf, b' ');
        ts[i].1 = -1 * read::<i32>(&mut stdin_lock, &mut buf, b'\n');
        ts[i].2 = i + 1;
    }
    ts.sort();
    for t in ts.iter() {
        println!("{}", t.2);
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using in6 = int64_t;
using ind = double;
using vi = vector<in6>;
using vii = vector<vi>;
using vs = vector<string>;
using pii = pair<in6,in6>;
using psi = pair<string,in6>;
using vpi = vector<pii>;
using vps = vector<psi>;
#define rep(i, n) for (in6 i = 0; i < (in6)(n); i++)
#define repa(i,a,n) for(in6 i = a; i < (in6)(n); i++)
#define repdown(i,n) for(in6 i = n; i > 0; i--)
#define kyun ios::sync_with_stdio(false)
#define hinata cout << "\n"
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define inf 2147483647
#define dset(n) cout << fixed << setprecision(n)

void yes() {
  cout << "Yes";
}

void no() {
  cout << "No";
}

int main() {
  kyun;
  in6 a,b,c,d,e,k;
  cin >> a>>b>>c>>d>>e>>k;
  if(e-a > k) cout << ":(";
  else cout << "Yay!";
  hinata;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  int P = K;
  
  for (int i = 0; i < N - 1; i++) {
    P *= (K - 1);
  }
  
  cout << P << endl;
  return 0;
}


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

# define x first
# define y second
# define mp make_pair
// everything goes according to my plan
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector
// shimkenttin kyzdary, dzyn, dzyn, dzyn...
# define y1    Y_U_NO_y1
# define left  Y_U_NO_left
# define right Y_U_NO_right

# ifdef Local
# define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
# else
# define debug(...) (__VA_ARGS__)
# define cerr if(0)cout
# endif

using namespace std;

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

const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4e18;
const int Sz = 1110111;
// a pinch of soul
inline void Read_rap () {
  ios_base :: sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}
inline void randomizer3000 () {
  unsigned int seed;
  asm ("rdtsc" : "=A"(seed));
  srand (seed);
}
void files (string problem) {
  if (fopen ((problem + ".in").c_str(),"r")) {
    freopen ((problem + ".in").c_str(),"r",stdin);
    freopen ((problem + ".out").c_str(),"w",stdout);
  }
}
void localInput(const char in[] = "s") {
  if (fopen (in, "r")) {
    freopen (in, "r", stdin);
  }
  else
    cerr << "Warning: Input file not found" << endl;
}

int main()
{
  # ifdef Local
    //localInput();
  # endif
  Read_rap();
  int n;
  cin >> n;

  ll A = 1, B = 1;
  for (int i = 1; i <= n; i++) {
    int p, q;
    cin >> p >> q;
    ll x = (A+B+ p+q-1) / (p + q);
    // A/p<=x
    x = max (x, (A + p-1) / p);
    x = max (x, (B + q-1) / q);

    A = p * x, B = q*x;
    // cout << A << ' ' << B << endl;
  }
  cout << A+B;



  return 0;
}






// Coded by Z..

Measured memory_bytes: 256
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {
    let s: String = read();
    let v = read_vec::<i64>();
    let (goal_x, goal_y) = (v[0], v[1]);

    let s = s.split('T').map(|x| x.len() as i64).collect::<Vec<_>>();

    let mut cur_x = s[0];
    let mut cur_y = 0;


    let mut lateral_moves = Vec::new();
    for (i, m) in s.iter().enumerate() {
        if i % 2 == 0 && i > 1 {
            lateral_moves.push(m);
        }
    }
    let mut longitudinal_moves = Vec::new();
    for (i, m) in s.iter().enumerate() {
        if i % 2 == 1 {
            longitudinal_moves.push(m);
        }
    }

    // println!("lateral moves {:?}", lateral_moves);
    // println!("longitudinal {:?}", longitudinal_moves);
    lateral_moves.sort();
    lateral_moves.reverse();
    // println!("start {:?}", (cur_x, cur_y));
    for m in lateral_moves {
        if cur_x < goal_x {
            cur_x += *m;
        } else {
            cur_x -= *m;
        }
        // println!("{:?}", (cur_x, cur_y));
    }

    longitudinal_moves.sort();
    longitudinal_moves.reverse();
    for m in longitudinal_moves {
        if cur_y < goal_y {
            cur_y += *m;
        } else {
            cur_y -= *m;
        }
        // println!("{:?}", (cur_x, cur_y));
    }
    // println!("{:?}", (cur_x, cur_y));
    if cur_x == goal_x && cur_y == goal_y {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int W = sc.nextInt();
		int H = sc.nextInt();
		int T = sc.nextInt();
		int P = sc.nextInt();
		int[] X = new int[P];
		int[] Y = new int[P];
		for (int i = 0; i < P; ++i) {
			X[i] = sc.nextInt();
			Y[i] = sc.nextInt();
			sc.next();
		}
		int[][] S = new int[H][W];
		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < W; ++j) {
				S[i][j] = sc.nextInt();
			}
		}
		int ans = 0;
		for (int i = 0; i < P; ++i) {
			ans += S[Y[i]][X[i]];
		}
		System.out.println(ans);
	}

}

Measured memory_bytes: 32872
// C - Sequence
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rp(i,n) for(int i=0;i<(n);i++)

ll counter(vector<ll> &A, int N, int sign){//sign: (+)start -> 1, (-)start -> -1
	ll c = 0, s = 0;
	rp(i,N){
		s += A[i];
		if(sign*s<=0){
			c += abs(s) + 1;
			s = sign;
		}
		sign *= -1;
	}
	return c;
}

int main(){
	int N; cin>>N;
	vector<ll> A(N);
	rp(i,N) cin>>A[i];
	ll a = counter(A,N, 1);
	ll b = counter(A,N,-1);
	cout<< (a<b?a:b) <<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
const long long mod=1e9+7;
long long fact[200010];
void pre(){
    fact[0]=1;
    for(long long i=1; i<200010; ++i){
        fact[i]=(fact[i-1]*i)%mod;
    }
}
long long pwr(long long x, long long e){
    if(e==0)
        return 1;
    long long tmp=pwr(x,e/2);
    tmp=(tmp*tmp)%mod;
    if(e%2)
        tmp=(tmp*x)%mod;
    return tmp;
}
long long cmb(long long x, long long y){
    long long res, tmp;
    tmp=pwr(fact[x-y], mod-2);
    res=(fact[x]*tmp)%mod;
    tmp=pwr(fact[y],mod-2);
    res=(res*tmp)%mod;
    return res;
}

int main(){
    ll n, k;
    pre();
    while(cin>>n>>k){
        ll ans=1, tmp1, tmp2;
        for(int i=1; i<=min(n-1, k); ++i){
        	tmp1=cmb(n, i);
        	// tmp2=cmb(i, n-i);
        	tmp2=cmb(i+n-i-1, n-i-1);
        	// tmp2=fact[i+1]*pwr(fact[n-i-1], mod-2);
        	tmp2%=mod;
        	ans+=tmp1*tmp2;
        	ans%=mod;
        }
        cout<<ans<<endl;
    }
  return 0;
}




Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)n; i++)

int main() {
  int n;
  cin >> n;
  vector<int> p(n);
  rep(i,n) cin >> p[i];
  int k=0;
  rep(i,n) if (p[i] != i+1) k++;
  if(k<=2) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int list[3][3];
  for(int i = 0; i<3; i++) {
    for(int j = 0; j<3; j++) {
      cin >> list[i][j];
    }
  }
  int x[3] = {0};
  int y[3] = {0};
  for(int i = 0; i < 3; i++) {
    y[i] = list[0][i] - x[0];
  }
  for(int i = 0; i < 3; i++) {
    x[i] = list[i][0] - y[0];
  }

  bool res = true;
  int cnt = 0;
  for(int i = 0; i<3; i++) {
    for(int j = 0; j<3; j++) {
      if(x[i] + y[j] != list[i][j]) cnt++ ;
    }
  }
  cout << (cnt > 0 ? "No" : "Yes") << endl;

  return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int main(){
  ll h,w;cin>>h>>w;
  vector<string>a(h);
  rep(i,h)cin>>a[i];
  ll dp[h][w];
  rep(i,h){
    rep(j,w)dp[i][j]=0;
  }
  dp[0][0]=1;
  for(ll i=0;i<h;i++){
    for(ll j=0;j<w;j++){
      if(a[i][j]=='#')continue;
      if(i>=1)dp[i][j]+=dp[i-1][j];
      if(j>=1)dp[i][j]+=dp[i][j-1];
      dp[i][j]%=MOD;
    }
  }
  //rep(i,h){
    //rep(j,w)cout<<dp[i][j]<<" ";
    //cout<<endl;
  //}
  cout<<dp[h-1][w-1]<<endl;
}

Measured memory_bytes: 9088
n, m = map(int, input().split())
x = list(map(int, input().split()))

# if m == 1:
#     print(n//2)
#     exit()

lst = [{} for i in range(m)]
lst_num = [0 for i in range(m)]
for i in range(n):
    xi = x[i]
    amari = xi % m
    if xi in lst[amari]:
        lst[amari][xi] += 1
    else:
        lst[amari][xi] = 1
    lst_num[amari] += 1

lst_kisu = [0 for i in range(m)]
lst_gusu = [0 for i in range(m)]
for i in range(m):
    num = 0
    for value in lst[i].values():
        if value % 2 == 1:
            num += 1
    lst_kisu[i] = num
    lst_gusu[i] = lst_num[i] - num

ans = 0
ans += lst_num[0] // 2
for i in range(1, (m-1)//2+(m-1)%2+1):
    amari1 = i
    amari2 = m - i
    if amari1 == amari2:
        ans += lst_num[amari1] // 2
    else:
        if lst_num[amari1] <= lst_num[amari2]:
            ans += lst_num[amari1]
            if lst_num[amari1] <= lst_kisu[amari2]:
                ans += lst_gusu[amari2] // 2
            else:
                ans += (lst_gusu[amari2]-(lst_num[amari1]-lst_kisu[amari2])) // 2
        else:
            ans += lst_num[amari2]
            if lst_num[amari2] <= lst_kisu[amari1]:
                ans += lst_gusu[amari1] // 2
            else:
                ans += (lst_gusu[amari1]-(lst_num[amari2]-lst_kisu[amari1])) // 2
print(ans)

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define PI 3.14159265358979
#define MOD 1000000007 // = 10^9 + 7

using namespace std;
using ll = long long;

void solve()
{
	string s;
	cin >> s;

	int q;
	cin >> q;

	int t;
	bool reverse = false;

	deque<char> d;
	for(int i = 0; i < s.length(); ++i)
	{
		d.push_back(s[i]);
	}

	for(int i = 0; i < q; ++i)
	{
		cin >> t;
		if (t == 1)
		{
			reverse = !reverse;
		}
		else if (t == 2)
		{
			int f;
			char c;
			cin >> f >> c;
			if ((f - 1) == (int)reverse)
			{
				d.push_front(c);
			}
			else
			{
				d.push_back(c);
			}
		}
	}

	string ans = "";
	while(!d.empty())
	{
		ans += d.front();
		d.pop_front();
	}
	if (reverse)
	{
		std::reverse(ans.begin(), ans.end());
	}
	cout << ans;
}

int main()
{
	fastio;
	solve();

	return 0;
}

Measured memory_bytes: 1368
import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, log2, factorial
from pprint import pprint

# sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
# N = int(input())
# A,B,C = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

N, M = [int(x) for x in input().split()]
A = [int(input()) for _ in range(M)]
A = set(A)

dp = [0] * (N + 1000)
dp[0] = 1

for i in range(N):
    if i + 1 not in A:
        dp[i + 1] += dp[i]
        # dp[i + 1] %= MOD
    if i + 2 not in A:
        dp[i + 2] += dp[i]
        # dp[i + 2] %= MOD

print(dp[N] % MOD)


Measured memory_bytes: 463468
from collections import deque
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
a=[input() for _ in range(h)]
dxy=[(0,1),(1,0),(-1,0),(0,-1)]
inf=float("inf")

dp=[[inf]*w for _ in range(h)]
q=deque()

for y,l in enumerate(a):
    for x,c in enumerate(l):
        if c=="#":
            dp[y][x]=0
            q.append((x,y))
ans=0
while q:
    x,y=q.popleft()
    d=dp[y][x]
    for dx,dy in dxy:
        nx,ny=x+dx,y+dy
        if not 0<=nx<w: continue
        if not 0<=ny<h: continue
        if dp[ny][nx]<=d+1: continue
        dp[ny][nx]=d+1
        q.append((nx,ny))
        ans=max(ans,d+1)
print(ans)


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

int main(){
	int n;
	while(cin>>n){
		int count = 0;
		for(int i=0; i<10; i++)
			for(int j=0; j<10; j++)
				for(int k=0; k<10; k++)
					for(int l=0; l<10; l++)
						if(i+j+k+l==n) count++;
		cout << count << endl;
	}
	return 0;
}

Measured memory_bytes: 3068
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n;
    cout << n/3;

    return 0;
}


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

int main()
{
    int n, x, cnt= 0 ;
    cin >> n;
    for(int i=1; i<=n; ++i) {
        cin >> x; cnt += x != i;
    }
    if (cnt > 2) cout << "NO"; else cout << "YES";
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
    int w,h,x,y,r;
    scanf("%d %d %d %d %d",&w,&h,&x,&y,&r);
    if(x+r<=w&&y+r<=h&&x-r>=0&&y-r>=0)
    printf("Yes\n");
    else
    printf("No\n");
    return 0;
}


Measured memory_bytes: 2104
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    k = int(input())
    if k % 2 == 0 or k % 5 == 0:
        print(-1)
        sys.exit()
    p = 7
    plus = 7
    amari = set()
    r = 1
    while (p % k) != 0:
        if p in amari:
            print(r, -1, p)
            sys.exit()
        else:
            amari.add(p)
            plus = (plus * 10) % k
            p += plus
            p = p % k
            r += 1
    print(r)

if __name__ == '__main__':
    main()

Measured memory_bytes: 77748