akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define M 1046527
#define NIT (-1)
#define L 14

char H[M][L];

int getchar(char ch)
{
    if(ch=='A')return 1;
    else if(ch=='C')return 2;
    else if(ch=='G')return 3;
    else if(ch=='T')return 4;
    else return 0;
}

long long getkey(char str[])
{
    long long sum=0,p=1,i;
    for(i=0;i<strlen(str);i++)
    {
        sum+=p*(getchar(str[i]));
        p*=5;
    }
    return sum;
}

int h1(int key){return key%M;}
int h2(int key){return 1+(key%(M-1));}

int find(char str[])
{
    long long key,i,h;
    key=getkey(str);
    for(i=0;;i++)
    {
        h=(h1(key)+i*h2(key))%M;
        if(strcmp(H[h],str)==0)return 1;
        else if(strlen(H[h])==0)return 0;
    }
    return 0;
}

int insert(char str[])
{
    long long key,i,h;
    key=getkey(str);
    for(i=0;;i++)
    {
         h=(h1(key)+i*h2(key))%M;
         if(strcmp(H[h],str)==0)return 1;
         else if(strlen(H[h])==0)
         {
             strcpy(H[h],str);
             return 0;
         }
    }
    return 0;
}

int main()
{
    int h,i,n;
    char str[L],com[9];
    for(int i=0;i<M;i++)H[i][0]='\0';
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%s %s",com,str);
        if(com[0]=='i')
        {
            insert(str);
        }else
        {
            if(find(str))
            {
                printf("yes\n");
            }else
            {
                printf("no\n");
            }
        }
    }
    return 0;
}

Measured memory_bytes: 17436
#include<iostream>
#include<queue>
using namespace std;
using P=pair<int,int>;
const int value=1000000;
const int x[4]={1,0,-1,0},y[4]={0,1,0,-1};
int h,w;
int x1,y1,x2,y2;
char s[50][50];
int a[50][50];
int BFS(void){
  queue<P> que;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      a[i][j]=value;
    }
  }
  a[x1][y1]=0;
  que.push(P(x1,y1));
  while(que.size()){
    P p=que.front();
    que.pop();
    for(int i=0;i<4;i++){
      int x3=p.first+x[i],y3=p.second+y[i];
      if(0<=x3 && x3<h && 0<=y3 && y3<w && s[x3][y3]=='.' && a[x3][y3]==value){
        a[x3][y3]=a[p.first][p.second]+1;
        if(x2==x3 && y2==y3){
          return a[x3][y3]+1;
        }
        que.push(P(x3,y3));
      }
    }
  }
  return a[x2][y2]+1;
}
int main(void){
  cin>>h>>w;
  x1=0,y1=0;
  x2=h-1,y2=w-1;
  int mul=h*w;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin>>s[i][j];
      if(s[i][j]=='#'){
        --mul;
      }
    }
  }
  mul-=BFS();
  if(a[x2][y2]==value){
    mul=-1;
  }
  cout<<mul<<endl;
  return 0;
}

Measured memory_bytes: 3644
import sys
sys.setrecursionlimit(4100000)

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

dp = [-1] * 81
dp[0] = 1000

for i in range(1, N):
    dp[i] = dp[i - 1]
    for j in range(i):
        kabu = dp[j] // A[j]
        dp[i] = max(dp[i], dp[j] + (A[i] - A[j]) * kabu)

print(dp[N - 1])


Measured memory_bytes: 9192
#include<stdio.h>

int main() {
	int A, B = 0;

	scanf("%d %d", &A, &B);

	if (A == 1) {
		A = 14;
	}
	if (B==1) {
		B = 14;
	}

	if (A == B) {
		printf("Draw");
	}
	if ( A > B ) {
		printf("Alice");
	}
	if(B>A) {
		printf("Bob");
	}
	return 0;
}

Measured memory_bytes: 128
#include"iomanip"
#include"iostream"
#include"limits"
#include"cmath"
#include"vector"
#include"algorithm"
#include"list"
#include"queue"
#include"stack"
#include"set"
#include"unordered_set"
#include"map"
#include"unordered_map"
#include"string"
#include"cstring"
#include"assert.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define mp make_pair
#define pb push_back
#define mset(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1e6+20;

int co[maxn];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,p;
    cin>>n>>p;
    ll sqp=sqrt(p+0.2)+0.2;
    for(ll i=2;i<=sqp;++i)
    {
        while(p%i==0)
        {
            co[i]++;
            p/=i;
        }
    }
    if(p>1)
    {
        if(p<maxn)
        {
            co[p]++;
            p=1;
        }
        else co[0]++;
    }
    ll ans=1;
    for(ll i=2;i<maxn;++i)
    {
        while(co[i]>=n)
        {
            ans*=i;
            co[i]-=n;
        }
    }
    while(co[0]>=n)
    {
        ans*=p;
        co[0]-=n;
    }
    cout<<ans<<'\n';
}












Measured memory_bytes: 256
import Data.List
import Data.Char
import Debug.Trace

mPrime = 10^9+7

mAdd :: Int -> Int -> Int
mAdd x y = (x + y) `mod` mPrime

mMul :: Int -> Int -> Int
mMul x y = (x * y) `mod` mPrime

mPow :: Int -> Int -> Int
mPow x y = foldl' mMul 1 (zipWith f (unfoldr bin_f y) (binpow x))
  where
    f 0 _ = 1
    f 1 t = t
    bin_f 0 = Nothing
    bin_f y = let (yd, ym) = y `divMod` 2 in Just (ym, yd)
    binpow x = iterate (\t -> mMul t t) x

mSum = foldl' mAdd 0

solve :: String -> Int
solve str = ans
-- (trace (show (cntL, cntR)) ans)
  where
    cntR = scanr f [0,0,0,0] str
      where f c v = zipWith (+) (vc c) v
    aCnt = head cntR
    cntL = map (zipWith (-) aCnt) cntR
    ans = mSum $ zipWith3 f str (init cntL) (tail cntR)
      where
        f z [la, lb, lc, lq] [ra, rb, rc, rq]
          | z == 'B' || z == '?' = (numz la lq) `mMul` (numz rc rq)
          | otherwise            = 0
        numz x 0 = x
        numz x y = (x `mMul` (mPow 3 y)) `mAdd` (y `mMul` (mPow 3 (y-1)))

vc 'A' = [1,0,0,0]
vc 'B' = [0,1,0,0]
vc 'C' = [0,0,1,0]
vc '?' = [0,0,0,1]

main :: IO ()
main = putStrLn . show . solve . takeWhile (not . isSpace) =<< getContents


Measured memory_bytes: 46460
//#include"cpp_kyopro.h"
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <stdlib.h>
#include <math.h>
using namespace std;
int main() {
	int n, k; cin >> n >> k;
	if (k != 1)cout << n - k << endl;
	else cout << "0" << endl;
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <cstring>

using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define pii pair < int, int >
#define pll pair < long long, long long>
#define ull unsigned long long
#define vi vector < int >
#define vll vector < long long >
#define sz(a) (int)a.size()
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++)
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x))
#define fname "searching"

const int inf = (int)1e9;
const ll INF = (ll)1e18;
const double eps = 1e-9;
const double pi = acos(-1.0);
const int mod = (int)1e9 + 7;

int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
    int n, k, x, y;
    cin >> n >> k >> x >> y;
    // k, n - k
    cout << min(n, k) * x + max(0, n - k) * y << "\n";
	return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#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++)
#define ALL(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using vs = vector<string>;
using vll = vector<long long>;
using vpii = vector<pair<int,int>>;
using vivi = vector<vector<int>>;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const int mod = 10000007;
const int inf = 1001001001;



int main(void) {
  int a,b;
  cin >> a >> b;
  if(a>=13) cout << b << endl;
  else if(a>=6) cout << b/2 << endl;
  else cout << 0 << endl;
    
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <cassert>
#include <fstream>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

const ll mod = 1e9 + 7;

vector<string> g;

int main() {
    
    
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    
    ll n;
    cin >> n;
    map<ll, ll> m1;
    map<ll, ll> m2;
    
    for (int i = 1; i <= n; ++i)
    {
        ll tmp;
        cin >> tmp;
        m1[i + tmp]++;
        if (i - tmp > 0)
        {
            m2[i - tmp]++;
        }
    }
    
    ll ret = 0;
    for (auto itr = m2.begin(); itr != m2.end(); ++itr)
    {
        ret += (itr->second * m1[itr->first]);
    }
    
    cout << ret << endl;

    return 0;
}

Measured memory_bytes: 22576
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

  int a;
  string s;
  cin >> a >> s;
  cout << (a >= 3200 ? s : "red") << endl;
}


Measured memory_bytes: 256
from itertools import permutations
N = int(input())
P = tuple(map(int,input().split()))
Q = tuple(map(int,input().split()))
Z_list = [n for n in range(1, N + 1)]
for i,j in enumerate(permutations(Z_list, r = N)):
    if j == P:
        a = i 
    if j == Q:
        b = i
print(abs(b - a))

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

typedef long long intl;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	intl n;
	cin>>n;
	vector <intl> v;
	map<intl,intl> m;
	for(intl i=0;i<n;i++){
		intl a;
		cin>>a;
		v.push_back(a);
		if(m.count(a)){
			m[a]++;
		}
		else{
			m[a]=1;
		}
	}
	intl ans=0;
	sort(v.begin(),v.end());
	for(int i=n-1;i>=0;i--){
		intl a=v[i];
		intl pow=1;
		while(pow<2e9){
			if(pow-a<0){
			}
			else{
				if(m.count(pow-a)){
					if(pow-a==a){
						if(m[pow-a]>1){
							m[pow-a]--;
							m[a]--;
							ans++;
							break;
						}
					}
					else if(m[pow-a]>0 &&m[a]>0){
						m[pow-a]--;
						m[a]--;
						ans++;
						break;
					}
				}
			}
			pow*=2;
		}
	
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 14320
// D.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

int main(int argc, char* argv[]) {
	while (true) {
		LL n = -1, m = -1;
		cin >> n >> m;
		if (n <= 0) break;
		vector<LL> a(m), b(m), c(m), d(n, 1LL << 60);
		d[0] = 0;
		for (LL i = 0; i < m; ++i) {
			cin >> a[i] >> b[i] >> c[i];
			--a[i], --b[i];
			c[i] = -c[i];
		}
		auto update = [&]() {
			for (LL j = 0; j < m; ++j) {
				if (d[b[j]] > d[a[j]] + c[j]) {
					d[b[j]] = d[a[j]] + c[j];
				}
			}
		};
		for (LL i = 0; i < n; ++i) {
			update();
		}
		vector<LL> first = d;
		for (LL i = 0; i < n; ++i) {
			update();
		}
		LL ans = -d[n - 1];
		if (ans > -first[n - 1]) {
			cout << "inf" << endl;
		} else {
			cout << ans << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
int main()
{
	int n,flag=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		int a,b,c,d;
		scanf("%d%d%d",&a,&b,&c);
		d=a-b-c;
		if(d<0||d%2==1)
		{
			flag=1;
		}
	}
	if(flag)
	printf("No\n");
	else
	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <map>

using std::cin;
using std::cout;

int main(int argc, char* argv[]) {
  int n;
  cin >> n;
  std::map<int, int> m;
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    m[a] = i + 1;
  }

  for (auto i = m.begin(); i != m.end(); ++i) {
    cout << i->second << " ";
  }

  return 0;
}


Measured memory_bytes: 5504
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <queue>
typedef long long ll;
#define rep(i,n) for(int i = 0;i<n;++i)
#define repc(bit,k,n) for (int bit = (1<<k)-1;bit < (1<<n); bit = next_combination(bit))
#define repi(itr,vec) for(auto itr = vec.begin();itr!=vec.end();++itr)
using namespace std;
using Graph = vector<vector<int> >;

/* next combination
 * usage:repc(bit,k,n)
 * */
inline int next_combination(int sub) {
  int x = sub & -sub, y = sub + x;
  return (((sub & ~y) / x) >> 1) | y;
}

/* uniq
 * usage:uniq(vec)
 * */
void uniq(vector<int> &vec){
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  return;
}

/* BinaryIndexedTree
 * usage:update and sum of 1~N
 * */
int N;
int bit[1000010];
void add(int a, int w) {
  for (int x = a; x <= N; x += x & -x) bit[x] += w;
}
int sum(int a) {
  int ret = 0;
  for (int x = a; x > 0; x -= x & -x) ret += bit[x];
  return ret;
}

/* DP
 * usage: chmin(dp[i],dp[i-1]+v);
 * */
const ll INF = 1LL << 60;
ll dp[100010];

template<class T> inline bool chmin(T& a, T b) {
      if (a > b) {
                a = b;
                        return true;
                            }
          return false;
}
template<class T> inline bool chmax(T& a, T b) {
      if (a < b) {
                a = b;
                        return true;
                            }
          return false;
}
int main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
  ll d,t,s;cin>>d>>t>>s;
  if(d<=t*s)cout<<"Yes\n";
  else cout<<"No\n";

        return 0;
}

Measured memory_bytes: 3628
n=int(input())
s=list(input())

def Z_algorithm(s):
  N=len(s)
  Z_alg=[0]*N
  Z_alg[0]=N
  i=1
  j=0
  while i<N:
    while i+j<N and s[j]==s[i+j]:
      j+=1
    Z_alg[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<N and k+Z_alg[k]<j:
      Z_alg[i+k]=Z_alg[k]
      k+=1
    i+=k
    j-=k
  return Z_alg

ans=0
for i in range(n):
  S=s[i:n]
  z=Z_algorithm(S)
  for j in range(len(z)):
    if z[j]<=j:
      if ans<z[j]:
        ans=z[j]
print(ans)

Measured memory_bytes: 50268
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cout<<(#v)<<":";for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;
#define printVS(vs) cout<<(#vs)<<":"<<endl;for(auto(s):(vs)){cout<<(s)<< endl;}
#define printVV(vv) cout<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;}
#define printP(p) cout<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cout<<(#vp)<<":"<<endl;for(auto(p):(vp)){cout<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cout << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cout << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1ll << 60;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

string s;
int n;
bool dp[100010];
bool visited[100010];
string key[4] = {"dream", "dreamer", "erase", "eraser"};

bool dfs(int i) {
    assert(0 <= i && i <= n);
    bool& ret = dp[i];
    if (visited[i]) return ret;
    visited[i] = true;
    rep(k, 4) {
        string t = key[k];
        if (i + t.size() <= n && s.substr(i, t.size()) == t) {
            ret |= dfs(i + t.size());
        }
    }
    return ret;
}

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

    cin >> s;
    n = s.size();
    dp[n] = true;
    visited[n] = true;
    cout << (dfs(0) ? "YES" : "NO") << endl;
}


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

int main() {
  int N,ans;
  cin>>N;
  for(int i=0;i<=N;i++){
    double I=i;
    I*=1.08;
     ans=I;
    if(ans==N){
      cout<<i;
      break;
    }
    else if(i==N){
      cout<<":(";
      break;
    }
  }
      
}

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

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    if(n>12)printf("%d\n",m);
    else if(n>5)printf("%d\n",m/2);
    else printf("0\n");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#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++)
typedef long long ll;

int N;
int A[20];
int x[20][20];
int y[20][20];

int counter(int x) {
  if(x == 0) return 0;
  return counter(x >> 1) + (x & 1);
}

void solve() {
  cin >> N;
  for(int i = 1; i <= N; i++) {
    cin >> A[i];
    for(int j = 1; j <= A[i]; j++) {
      cin >> x[i][j] >> y[i][j];
    }
  }
  int ans = 0;
  for(int bits = 1; bits < (1 << N); bits++) {
    bool ok = true;
    for(int i = 1; i <= N; i++) {
      if(!(bits & (1 << (i-1)))) continue;
      for(int j = 1; j <= A[i]; j++) {
        if(((bits >> (x[i][j]-1)) & 1) ^ y[i][j]) ok = false;
      }
    }
    if(ok) ans = max(ans, counter(bits));
  }
  cout << ans << endl;
  return;
}

int main() {
  solve();
}

Measured memory_bytes: 256
#include<stdio.h>
#include <string.h>
#include <stdlib.h>
struct node {
    int key;
    struct node *prev, *next;
};
struct node *nil;

void insert(int key);
void delete(struct node *t);
struct node *linear_search(int key);
void print_list();

int main(void) {
  int i, n, key;
  char command[10];
  nil = (struct node*)malloc(sizeof(struct node));
  nil->next = nil;
  nil->prev = nil;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%s",command);
    if(strlen(command) > 6) {
      if( command[6] == 'F') delete(nil->next);
      else delete(nil->prev);
    }else {
      scanf("%d", &key);
      if (command[0] == 'd') delete(linear_search(key));
      else insert(key);
    }
  }
  print_list();
  return 0;
}

void insert(int key) {
    struct node *p = (struct node*)malloc(sizeof(struct node));
    p->key = key;
    p->next = nil->next;
    nil->next->prev = p;
    nil->next = p;
    p->prev = nil;
}

void delete(struct node *t) {
  if (t == nil) return;
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

struct node *linear_search(int key) {
    struct node *current = nil->next;
    while(current != nil && current->key != key ) {
        current = current-> next;
    }
    return current;
}

void print_list() {
  int isf = 0;
  struct node *current = nil->next;
  while(current != nil) {
    if(isf++) putchar_unlocked(' ');
    printf("%d", current->key);
    current = current->next;
  }
  putchar_unlocked('\n');
}


Measured memory_bytes: 33116
#include<stdio.h>
#include<string.h>
//#define N 10000

int main(){
  int i,tlen,plen;
  char T[1000001],P[10001];

  scanf("%s%s",T,P);
  tlen=strlen(T);
  plen=strlen(P);

  for(i=0;i<tlen;i++){
      if(strncmp(&T[i],P,plen)==0){
	printf("%d\n",i);
      }
  }
 
  return 0;
}

Measured memory_bytes: 1544
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long ll;
typedef pair<int, int> pii;
#define mp make_pair



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

	int a, b, c;
	ll k;
	cin >> a >> b >> c >> k;
	int ans = a - b;
	if (k & 1) ans *= -1;
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import fractions
from functools import reduce
from operator import mul
import bisect
import sys
import logging
import heapq
import itertools

logging.basicConfig(level=logging.ERROR)

#input = sys.stdin.readline

setrecursionlimit(1000000)


def main():
    a,b,n = map(int,input().split())
    x = min(n,b-1)
    print(math.floor(a*x/b) - a*math.floor(x/b))

main()


Measured memory_bytes: 73064
#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;

unordered_map<ll,ll> mmp[23];
ll c[37],ans;
bool v[77];
char s[77];
int n,num;

inline ll G(char x){ return x-'a'+3;}

inline void update(){
	ll z=0,f=0;
	num=0; for(int i=n;i;i--) if(v[i]) f=f+G(s[i])*c[num++];
	num=0; for(int i=1;i<=n;i++) if(!v[i]) z=z+G(s[i])*c[num++];
	mmp[num][z-f*c[num]]++;
}

inline void calc(){
	ll z=0,f=0;
	num=0; for(int i=2*n;i>n;i--) if(v[i]) f=f+G(s[i])*c[num++];
	num=0; for(int i=n+1;i<=n*2;i++) if(!v[i]) z=z+G(s[i])*c[num++];
	ans+=mmp[n-num][f-z*c[n-num]];
}

void dfs1(int L){
	if(L==n){ update(); return;}
	dfs1(L+1),v[L+1]=1,dfs1(L+1),v[L+1]=0;
}

void dfs2(int L){
	if(L==n*2){ calc(); return;}
	dfs2(L+1),v[L+1]=1,dfs2(L+1),v[L+1]=0;
}

int main(){
	scanf("%d",&n),scanf("%s",s+1);
	c[0]=1; for(int i=1;i<=n;i++) c[i]=c[i-1]*233ll;
	dfs1(0);
	dfs2(n);
	printf("%llu\n",ans);
	return 0;
}

Measured memory_bytes: 23452
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <math.h>

#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;



int main() {
	
	int n,m;
    cin>>n>>m;
    vector<int> a(m);
    int sum=0;
    rep(i,m) cin>>a[i];
    rep(i,m) sum+=a[i];
	if(sum<=n) 
    {
        cout<<n-sum<<endl;
    }
    else
    {
        cout<<-1<<endl;

    } 
	return 0;
}

Measured memory_bytes: 3612
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <cmath>
using namespace std;

#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define fir first
#define sec second
#define m_p make_pair
#define rep(i,n)  for(int i=0; i<(int) (n); i++)
#define vecin(v) for(int i=0; i<(int)v.size(); i++)cin>>v[i];
#define vecout(v,n) for(int i=0; i<n; i++)cout<<v[i]<<" "; cout<<endl;

const int mod = 1000000007;
const int INF = 2000000015;
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
int jousu(int x00, int y00) {
	int z00 = 1;
	for (int i = 0; i < y00; i++) {
		z00 *= x00;
	}
	return z00;
}
int keta(int x00) {
	int z00 = x00;
	int w00 = 0;
	while (z00 != 0) {
		z00 /= 10;
		w00++;
	}
	return w00;
}
int krag(double xx) {
	return INF - (int)(INF - xx);
}

//x未満の要素数を返す二分探索関数
int b_s(vector<int>&vecxx, int xx) {
	if (xx <= vecxx[0]) { //x以下の要素数を返させる時は"<"に変える
		return 0;
	}
	if (vecxx.back() < xx) { //x以下の要素数を返させる時は"<="に変える
		return vecxx.size();
	}
	int aa1 = 0, aa2 = vecxx.size() - 1, aa3;
	while (aa1 + 1 < aa2) {
		aa3 = (aa1 + aa2) / 2;
		if (vecxx[aa3] >= xx) { //x以下の要素数を返させる時は">"に変える
			aa2 = aa3;
		}
		else {
			aa1 = aa3;
		}
	}
	return aa2;
}


int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int modpow(int a, int n) {
	int res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
//n個を1個以上のx組のグループに分ける重複組み合わせはcom(n-1,x-1)
//グループが0個でもいいときはnにxを足す

int com(int xx, int yy) {
	int zz = 1;
	for (int i = xx; i > xx - yy; i--) {
		zz *= i;
		zz %= mod;
	}
	for (int i = 1; i <= yy; i++) {
		zz *= modinv(i, mod);
		zz %= mod;
	}
	return zz;
}
int gcd(int xx, int yy) {
	int p = xx;
	int q = yy;
	if (q > p)swap(p, q);
	while (p % q != 0) {
		p %= q;
		swap(p, q);
	}
	return q;
}
int lcm(int xx, int yy) {
	return xx * yy / gcd(xx, yy);
}
bool prime(int xx) {
	int a = xx;
	for (int i = 2; i * i <= xx; i++) {
		if (xx % i == 0) {
			return 0;
		}
	}
	return 1;
}

signed main() {
	int a, b;
	cin >> a >> b;
	if (a <= b) {
		cout << a << endl;
	}
	else {
		cout << a - 1 << endl;
	}
}




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

int main() {
  int n;
  string a, b, c;
  cin >> n >> a >> b >> c;
  int ans = 0;
  rep(i, n) {
    if (a[i] == b[i] && a[i] == c[i]) continue;
    if (a[i] != b[i] && b[i] != c[i] && c[i] != a[i]) ans++;
    ans++;
  }
  cout << ans << endl;
  return 0;
}

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

int main()
{
    int n=0,x=0;

    cin>>n>>x;

    while (n != 0 || x != 0)
    {
        int count=0;
        for(int i=1;i<=n-2;i++)
        {
            for(int j=i+1;j<=n-1;j++)
            {
                for(int k=j+1;k<=n;k++)
                {
                    if(i+j+k == x)
                    {
                        count++;
                    }
                }
            }
        }
        cout<<count<<"\n";
        cin>>n>>x;
    }

    return 0;
}

Measured memory_bytes: 1164
n = int(input())
A = [int(_) for _ in input().split()]

flag = 1
count = 0
while flag:
    flag = 0
    for j in range(n-1, 0, -1):
        if A[j] < A[j-1]:
            t = A[j]
            A[j] = A[j-1]
            A[j-1] = t
            flag = 1
            count += 1

print(' '.join(map(str, A)))
print(count)


Measured memory_bytes: 5600
require 'set'
N = gets.to_i
as = gets.split.map(&:to_i)
MOD = 10 ** 9 + 7
set1 = Set.new
set2 = Set.new
set3 = Set.new
ans = 1
as.each do |n|
  count = 0
  if (n == 0 && !set1.include?(n)) || (!set1.include?(n) && set1.include?(n - 1))
    set1.add(n)
    count += 1
  end
  if (n == 0 && !set2.include?(n)) || (!set2.include?(n) && set2.include?(n - 1))
    set2.add(n) if count == 0
    count += 1
  end
  if (n == 0 && !set3.include?(n)) || (!set3.include?(n) && set3.include?(n - 1))
    set3.add(n) if count == 0
    count += 1
  end
  ans = ans * count % MOD
end
puts ans


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

#define ran 1<<18

int n;
int a[ran];
int q[ran], l, r;
multiset<int> st;
multiset<int> ::iterator it;

int main() {
	scanf("%d", &n);
	int t = n;
	n = 1<<n;
	for(int i=0;i<n;i++) scanf("%d", &a[i]);
	sort(a, a+n);
	
	l = r = 0;
	q[r++] = a[n-1];
	st.clear();
	for(int i=0;i<n-1;i++)
		st.insert(a[i]);
	for(int i=1;i<=t;i++) {
		int lim = r;
		bool chk = true;
		for(int j=0;j<lim && chk;j++) {
			it = st.lower_bound(q[j]);
			if(it==st.begin()) { chk = false; break; }
			it--;
			q[r++] = (*it);
			st.erase(it);
		}
		if (!chk) {
			puts("No");
			return 0;
		}
	}
	puts("Yes");
	
	return 0;
}

Measured memory_bytes: 14592
#include <bits/stdc++.h>
#define rep(x, y) for(int x = 0; x < (y); x++)
#define REP(x, z, y) for(int x = (z); x < (y); x++)
#define all(x) x.begin(), x.end()
#define len(x) (sizeof(x) / sizeof(x[0]))
#define split_str(str, sp_word) istringstream stream(str); string res; for(int cnt = 0; getline(stream,res,sp_word); cnt++)
#define scanln(x) fgets(x, sizeof x, stdin)
#define down_queue(x) priority_queue<x>
#define up_queue(x) priority_queue<x, vector<x>, greater<x>>
#define i_str(x) atoi(x.c_str())
#define digit(x) ((int)log10((double)(x)) + 1)
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
using namespace std;
const int MOD = 1000000007; 
typedef long long ll;
typedef string str;
 
int main(){
  str s; cin >> s;
  char tmp = s[0];
  int block = 0;
  rep(i,s.length()){
    if(tmp != s[i]){
      block++;
      tmp = s[i];
    }
  }

  cout << block;
  return 0;
}

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

long long int GCD(long long int a, long long int b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

int main() {
	long long int N, L, D, M;
	cin >> N >> M;
	for (int i = 1; i < N; i++) {
		cin >> L;
		D = GCD(M, L);
		M *= L / D;
	}
	cout << M;
}

Measured memory_bytes: 256
import math
a, b, x = map(int, input().split())
if x/(a**2) > b/2:
    tang = 2*((a**2)*b-x)/(a**3)
    ans = math.degrees(math.atan(tang))
elif  x/(a**2) == b/2:
    tang = 1
    ans = math.degrees(math.atan(tang))
elif x/(a**2) < b/2:
    tang = a*(b**2)/(2*x)
    ans = math.degrees(math.atan(tang))

print(ans)

Measured memory_bytes: 3064
N,M = map(int,input().split())

L_list = []
R_list = []

for i in range(M):
    L,R = map(int,input().split())
    L_list.append(L)
    R_list.append(R)

l = max(L_list)
r = min(R_list)

if(l > r):
    print(0)
else:
    print(r-l+1)

Measured memory_bytes: 10996
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define LL long long
int n,s;
void dfs(LL x,int y)
{
    if(y==7)
        s++;
    if(x*10+3<=n)
        dfs(x*10+3,y|1);
    if(x*10+5<=n)
        dfs(x*10+5,y|2);
    if(x*10+7<=n)
        dfs(x*10+7,y|4);
}
int main()
{
    int i,j,k;
    scanf("%d",&n);
    s=0;
    dfs(0,0);
    printf("%d\n",s);
    return 0;
}


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

const string YES = "Yes";
const string NO = "No";

void solve(std::string S)
{
    if (!all_of(begin(S), end(S), [front = S.front()](auto ch) { return ch == front; })) {
        cout << YES << endl;
    } else {
        cout << NO << endl;
    }
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
// clang-format off
#pragma GCC diagnostic ignored "-Wunused-result"
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 256
from heapq import *
import math
import io
import sys

n, m = map(int, input().split())
pay = []
for _ in range(n):
    a, b = map(int, input().split())
    pay.append((a, b))
pay = sorted(pay, reverse=True)
q = []
ans = 0
for i in range(1, m+1):
    while pay and pay[-1][0] <= i:
        a, b = pay.pop()
        heappush(q, -b)
    if q:
        b = -heappop(q)
        ans += b
print(ans)

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

void solve(int d, int w){
	int a[d][w];
	for(int i=0; i<d; ++i)
		for(int j=0; j<w; ++j)
			cin >> a[i][j];
	int ans = 0;
	for(int i=0; i<d; ++i)
		for(int j=0; j<w; ++j)
			for(int k=0; k<d; ++k)
				for(int l=0; l<w; ++l){
					if(i+1 >= k || j+1 >= l) continue;
					int mi = 1e9, ma = 0;
					for(int m=i; m<=k; ++m)
						for(int n=j; n<=l; ++n){
							if(m == i || m == k || n == j || n == l) mi = min(mi, a[m][n]);
							else ma = max(ma, a[m][n]);
						}
					if(mi <= ma) continue;
					int tmp = 0;
					for(int m=i; m<=k; ++m)
						for(int n=j; n<=l; ++n)
							if(m != i && m != k && n != j && n != l)
								tmp += mi - a[m][n];
					ans = max(ans, tmp);
//					cout << i << " " << j << " " << k << " " << l << " " << tmp << " " << mi << " " << ma << "\n";
				}
	cout << ans << "\n";
}

int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	while(1){
		int d, w;
		cin >> d >> w;
		if(d == 0 && w == 0) return 0;
		solve(d, w);
	}
}


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

int main() {
    ll n, k;
    cin >> n >> k;
    const int MOD = 1e9 + 7;

    ll ans = 1;
    for (int i = k; i <= n; i++) {
        ans = (ans + i * (n - i + 1) + 1) % MOD;
    }

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


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

typedef long long ll;
const ll N=2e5 + 5;
const ll mod=1e9 + 7;
#define debug(x) cerr<<#x<<" is "<<x<<endl;

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

    ll n;
    cin>>n;

    ll moves=n-1;
    for(ll i=2;i*i<=n;i++){
        if(n%i)
            continue;
        ll f = i;
        ll s = n/i;
        ll op = f-1 + s-1;
        moves = min(moves , op);
    }

    cout<<moves;

}


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

int main() {

  vector<vector<int>> c(3,vector<int>(3));

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

  vector<int> a(3);
  vector<int> b(3);

  a[0] = 0;
  b[0] = c[0][0];
  b[1] = c[0][1];
  b[2] = c[0][2];
  a[1] = c[1][0] - b[0];
  a[2] = c[2][0] - b[0];

  string answer = "Yes";

  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      if (c[i][j] != a[i] + b[j]) {
        answer = "No";
      }
    }
  }

  cout << answer << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<ll, ll, ll> T;

int N, M, Q;

int main(void){
    
    scanf("%d %d %d", &N, &M, &Q);
    vector<vector<int>> sum(N + 1, vector<int>(N + 1, 0));
    for(int i = 0; i < M; ++i){
        int l, r; scanf("%d %d", &l, &r);
        ++sum[l][r];
    }
    
    for(int i = 1; i <= N; ++i) for(int j = 0; j < N; ++j) sum[i][j + 1] += sum[i][j];
    for(int i = 1; i <= N; ++i) for(int j = 0; j < N; ++j) sum[j + 1][i] += sum[j][i];
    
    for(int i = 0; i < Q; ++i){
        int p, q; scanf("%d %d", &p, &q);
        printf("%d\n", sum[q][q] - sum[p - 1][p - 1] - (sum[p - 1][q] - sum[p - 1][p - 1]) - (sum[q][p - 1] - sum[p - 1][p - 1]));
    }
    
    return 0;
}


Measured memory_bytes: 1920
def solve(string):
    n = len(string)
    q_pos = [i for i in range(n) if string[n - i - 1] == "?"]
    table = [[0] * 13 for _ in range(2)]
    table[0][int(string.replace("?", "0")) % 13] = 1
    for i in range(len(q_pos)):
        base = pow(10, q_pos[i], 13)
        for j in range(13):
            for k in range(10):
                table[1][(j + k * base) % 13] += table[0][j]
        for j in range(13):
            table[1][j] %= (10**9 + 7)
        table[0] = table[1]
        table[1] = [0] * 13
    return str(table[0][5])


if __name__ == '__main__':
    print(solve(input()))


Measured memory_bytes: 46960
h,w=map(int,input().split())
a =['']*h
for i in range(h):
    a[i]=input() #二重配列の入力
row = [False]*h
col = [False]*w
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            row[i]=True
            col[j]=True #同じ行か列に＃があるところは全てTrueに
for i in range(h):
	if row[i]:
		for j in range(w):
			if col[j]:
				print(a[i][j], end = '') 
		print()

Measured memory_bytes: 4468
#include<bits/stdc++.h>
using namespace std;
#define ll long long
 
#define INF pow(10,9)

int main(void){
    string s;
    cin >> s;
    ll ans = INF;
    for(int i=0;i<s.length()-2;i++){
        ll tmp = abs(753-stoi(s.substr(i,3)));
        if(tmp<ans){
            ans = tmp;
        }
    }cout << ans<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define For(i, a, b) for (int i = int(a); i < int(b); i++)
#define Dor(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define Foz(i, a) For(i, 0, a)
#define Doz(i, a) Dor(i, 0, a)
#define Trav(e, v) for (auto& e : v)
#define pb push_back
#define mp make_pair
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vii = vector<ii>;
template <typename T> bool ckmin (T& a, T b) { return (b < a) ? a = b, 1 : 0; }
template <typename T> bool ckmax (T& a, T b) { return (b > a) ? a = b, 1 : 0; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef XVENOM
	#define errp(...) fprintf(stderr, __VA_ARGS__)
	#define dbg(...) errp("[%s]: ", #__VA_ARGS__), dbg_str(__VA_ARGS__)
#else
	#define errp(...)
	#define dbg(...)
#endif
template <typename U, typename V> string to_string (pair<U, V>);
string to_string (string& e) { return "\"" + e + "\""; }
string to_string (char e) { return "\'" + string(1, e) + "\'"; }
string to_string (bool e) { return e ? "true" : "false"; }
template <typename T> string to_string (T e) {
	string s = "[ ";
	for (auto& x : e) s += to_string(x) + " ";
	return s + "]";
}
template <typename U, typename V> string to_string (pair<U, V> e) {
	return "(" + to_string(e.first) + ", " + to_string(e.second) + ")";
}
void dbg_str () { errp(" \n"); }
template <typename U, typename... V> void dbg_str (U u, V... v) {
 	errp(" %s", to_string(u).c_str()); dbg_str(v...);
}
/* --- */
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	/* --- */
	string s;
	int n;
	cin >> n >> s;
	int ans = 1;
	Foz(i, n - 1) {
		ans += (s[i] != s[i + 1]);	
	}
	cout << ans << '\n';
}



Measured memory_bytes: 512
# coding: utf-8
# Here your code !
count=0

def merge(A, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    L = [0 for i in xrange(n1 + 1)]
    R = [0 for i in xrange(n2 + 1)]
    for i in xrange(n1):
        L[i] = A[left + i]
    for i in xrange(n2):
        R[i] = A[mid + i]
    L[n1] = 1<<32 - 1
    R[n2] = 1<<32 - 1
    i = 0
    j = 0
    for k in xrange(left, right):
        count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) / 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
        
if __name__ == "__main__":
    n = int(raw_input())
    refA = map(int, raw_input().split())
    A = list(refA)
    mergeSort(A, 0, n)
    print " ".join(map(str,A))
    print count 

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

map<int, int> a;
int main() {
    long long ans = 0;
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x; cin >> x;
        ans += a[i-x];
        a[i+x]++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 20640
N = int(input())
s = []

result = 0
ABAB = 0
A = 0
B = 0
onon = 0

amari = 0
for i in range(N):
    s.append(input())

for S in s:
    AB = S.count("AB")
    result += AB
    if S[0] == "B" and S[-1] == "A":
        ABAB += 1
    elif S[0] == "B":
        B += 1
    elif S[-1] == "A":
        A += 1

if ABAB >= 1:
    onon = onon + ABAB - 1

if A >= 1 and ABAB >= 1 :
    onon += 1
    A -= 1
if B >= 1 and ABAB >= 1 :
    onon += 1
    B -= 1

if A >= 1 and B >= 1:
    if A >= B:
        onon += B
    else:
        onon += A


print(result + onon)


Measured memory_bytes: 3700
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
ll power(ll a,ll b)
{
    ll prod = 1;
    while(b)
    {
        if(b&1)
        prod = (prod%mod * a%mod)%mod;
        b >>= 1;
        a = (a%mod * a%mod)%mod;
    }
     return prod;
}
ll fact(ll n)
{
    if(n<0)
        return 0;
    if(n == 0)
        return 1;
    
    return (fact(n-1)%mod * n%mod)%mod;
}
ll ncr(ll i , ll j)
{   if(i<j) return 0;
    ll num = fact(i)%mod;
    ll num1 = (fact(j)%mod * fact(i-j)%mod)%mod;
    return (num%mod * power(num1,mod-2)%mod)%mod;
}
int main()
{
    ll x,y;
    cin >> x >> y;
    if((x+y)%3)
    {
        cout << 0;
    }
    else
    {
        ll num = (x+y)/3;
        cout << ncr(num,min(x,y)-num);
    }
    
    return 0;
}

Measured memory_bytes: 10624
n = int(input())
al = []
for i in range(n):
  a = int(input())
  al.append(a)
count = 0
i = 0
while (True):
  i = al[i] - 1
  count += 1
  if i == 1:
    break
  if count > n:
    break
if count > n:
  print('-1')
else:
  print(count)


Measured memory_bytes: 7084
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<sstream>
#include<cmath>
#include<climits>
#include<string>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb(a) push_back(a)
#define INF 0x1f1f1f1f
#define lson idx<<1,l,mid
#define rson idx<<1|1,mid+1,r
#define PI  3.1415926535898
void debug()
{
#ifdef ONLINE_JUDGE
#else
    freopen("d:\\in.txt","r",stdin);
    freopen("d:\\out1.txt","w",stdout);
#endif
}
char getch()
{
    char ch;
    while((ch=getchar())!=EOF)
    {
        if(ch!=' '&&ch!='\n')return ch;
    }
    return EOF;
}
double dp[25][200100];
int da[25];
double minn=INF;
int n;
double f(int k,int fa)
{
    if(dp[k][fa]>=0)return dp[k][fa];
    if(k==n+1)return 0;
    double minx=INF;
    for(int i=1;fa*i<=200000;i++)
    {
        int v=fa*i;
        if(da[k]<v&&((v-da[k])*1.0/(da[k]*1.0)>minx))break;
        if(da[k]>v&&((da[k]-v)*1.0/(da[k]*1.0)>minx))continue;
        minx=min(minx,max(f(k+1,v),abs(v-da[k])*1.0/(da[k]*1.0)));
    }
    return dp[k][fa]=minx;
}
int main()
{
   // int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&da[i]);
        memset(dp,-1,sizeof(dp));
        double x=f(1,1);
        printf("%.12lf\n",x);
    }
    return 0;
}

Measured memory_bytes: 40312
def atcoder_express(N: int, T: list, V: list)->float:
    MAXT = sum(T)
    graph = [0] * (2*MAXT + 1)

    T = [0, 0] + T + [0]
    for i in range(N+2):
        T[i+1] += T[i]

    V = [0] + V + [0]

    conditions = []
    for i in range(N+2):
        v, l, r = V[i], T[i], T[i+1]
        conditions.append((l, r, v))

    total = 0.0
    prev_v = 0.0
    for t in range(MAXT*2+1):
        min_v = float('inf')
        x = t / 2
        for l, r, v in conditions:
            if x < l:
                min_v = min(min_v, v + (l - x))
            elif r < x:
                min_v = min(min_v, v + (x - r))
            else:
                min_v = min(min_v, v)
        total += (prev_v + min_v) * 0.5 / 2
        prev_v = min_v

    return total


if __name__ == "__main__":
    N = int(input())
    T = [int(s) for s in input().split()]
    V = [int(s) for s in input().split()]
    ans = atcoder_express(N, T, V)
    print(ans)


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

using ll = long long int;

const ll MOD = (ll)(1e9 + 7);

ll x;

map<ll, ll> cnt;

ll ans;

/////////////////////////////////////////////////////////////
map<ll, ll> prime_factorization(ll n) {
  map<ll, ll> res;
  for (ll i = 2; i * i <= n; ++i) {
    while (n % i == 0) {
      res[i] += 1;
      n /= i;
    }
  }
  if (n != 1) res[n] = 1;
  return res;
}
/////////////////////////////////////////////////////////////

int main(void) {
    // Here your code !
    scanf("%lld", &x);

    for (int i = 2; i <= x; ++i) {
      for (auto &e: prime_factorization(i)) {
        if (cnt.find(e.first) != cnt.end()) {
          cnt[e.first] += e.second;
        }
        else {
          cnt[e.first] = e.second;
        }
      }
    }

    ans = 1;
    for (auto &e: cnt) {
      ans = ans * ((e.second + 1) % MOD);
      ans %= MOD;
    }

    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 256
import java.io.*;
 
class Main {
    public static void main(String[] args) {
        BufferedReader kb = new BufferedReader( new InputStreamReader( System.in ) );
        try {
            int n = Integer.parseInt( kb.readLine() );
			
			int[] nums = new int[n];
            int num, maxprofit, min;
            int i, j;
            
            maxprofit = 1-1000000000;
            min = Integer.parseInt( kb.readLine() );
            for( i=1; i<n; i++ ) {
            	num = Integer.parseInt( kb.readLine() );
				maxprofit = Math.max( maxprofit, num-min );
				min = Math.min( min, num );
            }
            
            System.out.println( maxprofit  );
             
            kb.close();
        } catch( IOException e ) {
            System.err.println( e );
        }
    }
}

Measured memory_bytes: 37600
N, Y = map(int, input().split())

y = 0
for i in range(Y // 10000 + 1):
    y = i * 10000

    for j in range((Y - y) // 5000 + 1):
        y2 = y + 5000 * j

        if y2 + (N - i - j) * 1000 == Y:
            print(i, j, N - i - j)
            exit()
print(-1, -1, -1)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  if (A+B > C+D) cout << "Left" <<endl;
  else if (A+B == C+D) cout << "Balanced" <<endl;
  else if (A+B < C+D) cout << "Right" <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define int ll
#define MOD (ll)(1e9+7)
using namespace std;
using ll=long long;
using pii=pair<int,int>;

int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
int lcm(int a,int b) { return a/gcd(a,b)*b; }

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin>>n;
	vector<int> v(n);
	for(auto &i:v) cin>>i;
	int cnt=0;
	For(i,1,n-2)
	{
		if(v[i]<max(v[i-1],v[i+1]) && v[i]>min(v[i-1],v[i+1])) cnt++;
	}
	cout<<cnt<<"\n";
	return 0;
}















Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
 
int main() {
  int n,a,b;
  cin>>n>>a>>b;
  
  cout<<min(n*a,b)<<endl;
  
  
  return 0;
}


Measured memory_bytes: 764
import math
X = int(input())
max = 0
bRange = math.floor(math.sqrt(X))
pRange = math.floor(math.log(X,2))
for b in range(bRange + 1):
    for p in range(pRange + 1):
        if(max < b**p <= X):
            max = b**p
print(max)

Measured memory_bytes: 3060