akhauriyash/Code-Regression huggingface dataset:
import java.util.HashMap;
import java.util.Scanner;

public class Main {

	static HashMap<String, Long> DP[];
	static String Chars = "ACGT";

	static boolean isValid(String S) {
		if (S.contains("AGC")) {
			return false;
		}
		for (int i = 1; i < S.length(); i++) {
			String temp = "";
			for (int j = 0; j < i - 1; j++) {
				temp += S.charAt(j);
			}
			temp += S.charAt(i) + "" + S.charAt(i - 1);
			for (int j = i + 1; j < S.length(); j++) {
				temp += S.charAt(j);
			}
			if (temp.contains("AGC")) {
				return false;
			}
		}
		return true;
	}

	static long DFS(int N, String cur) // N is the remaining length of string; cur is the last 3 characters of the
										// current string
	{
		if (DP[N].containsKey(cur)) {
			return DP[N].get(cur);
		}
		if (N == 0)
			return 1;
		DP[N].put(cur, 0l);
		for (int i = 0; i < Chars.length(); i++) {
			if (isValid(cur + Chars.charAt(i))) {
				long prev = DP[N].get(cur);
				long result = DFS(N - 1, cur.substring(1) + Chars.charAt(i));
				int MOD = (int) 1e9 + 7;
				DP[N].put(cur, (prev + result) % MOD);
			}
		}
		return DP[N].get(cur);
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		DP = new HashMap[N + 1];
		for (int i = 0; i <= N; i++) {
			DP[i] = new HashMap<>();
		}
		long result = DFS(N, "TTT");
		System.out.println(result);

	}

}


Measured memory_bytes: 48932
#include <iostream>

using namespace std;

int main()
{
    int n,x,c=0;
    while(true){
        cin>> n >> x;
        if(n==0&&x==0){
            break;
        }

        for(int i=1;i<=n;++i){
            for(int j=i+1;j<=n;j++){
                for(int k=j+1;k<=n;++k){
                    if(i+j+k==x){
                        c++;
                    }
                }
            }
        }
        cout << c <<endl;
        c=0;
    }
    return 0;
}



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

#include <stdio.h>
using namespace std;
int main(void){
    int n, i=0;
    cin >> n;
    int a[n];
    int l;
    
    while(cin>>l){
        a[i] = l;
       
        i++;
}
    int b[n];
    int j;
    for(j=0;j<n;j++){
        b[j] = a[j];
       
    }
    sort(b, b + n);
    int c=0;
    for(j=0;j<n;j++){
        
        if(b[j]-a[j]!=0){
            c=c+1;
        }
           }
    if(c==0 || c==2){
        cout << "YES";
    }else{
        cout << "NO";
   
  }
}

Measured memory_bytes: 384
from collections import deque
s=input()
q=int(input())
n=0
que=deque(s)
for i in range(q):
    l=input()
    if l[0]=='1':
        n+=1
    else:
        if (l[2]=='1' and n%2==0) or (l[2]=='2' and n%2==1):
            que.appendleft(l[4])
        else:
            que.append(l[4])

ans=''.join(que)
if n%2==0:
    print(ans)
else:
    print(ans[::-1])


Measured memory_bytes: 14440
n=int(input())
arr=[]
for _ in range(n):
    arr.append(int(input())-1)
cur=0
for i in range(n):
    nxt = arr[cur]
    if nxt==0:
        print(-1)
        break
    elif nxt==1:
        print(i+1)
        break
    cur=nxt
else:
    print(-1)


Measured memory_bytes: 7084
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;

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

    int N;
    string name;

    cin >> N;
    long long a[5] = {};

    for (int i = 0; i < N; ++i)
    {
        cin >> name;
        if (name[0] == 'M')
            ++a[0];
        if (name[0] == 'A')
            ++a[1];
        if (name[0] == 'R')
            ++a[2];
        if (name[0] == 'C')
            ++a[3];
        if (name[0] == 'H')
            ++a[4];
    }

    long long ans = 0, p = 1;
    for (int i = 0; i < 3; i++)
        for (int j = i + 1; j < 4; j++)
            for (int k = j + 1; k < 5; k++)
            {
                p = a[i] * a[j] * a[k];
                ans += p;
            }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define SUM(a)  accumulate((a).begin(),(a).end(),0)
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
typedef long long ll;
const int INF = 999999999;
const int MOD = (int)1e9 + 7;
const int EPS = 1e-9;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  cin >> s;
  int ans = s.size();
  REP(i,s.size()){
      if (s[i]=='A'){
          ans-=i;
          break;
      }
  }
  REV(s);
  REP(i,s.size()){
      if (s[i]=='Z'){
          ans-=i;
          break;
      }
  }
  cout << ans << endl;
}

Measured memory_bytes: 720
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // get a integer
        int n = sc.nextInt();
        // get two integers separated with half-width break
        int x = sc.nextInt();

        int m[] = new int[100];

        int smallest = 999999;
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            int mi = sc.nextInt();
            sum += mi;
            m[i] = mi;
            if (mi < smallest) {
                smallest = mi;
            }
        }


        int rest = x - sum;
        int additional = rest / smallest;
        int result = n + additional;

        System.out.println(result);
    }

}

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

typedef long long int int64;
static const int64 mod = 998244353LL;
int n,m;
int64 pown1[500003],powm1[500003];
int64 fac[500003],inv[500003],invfac[500003];
int main()
{
	scanf("%d%d",&n,&m);
	pown1[0] = 1;
	for(int i = 1;i <= m;++i) {
		pown1[i] = pown1[i-1] * (n+1) % mod;
	}
	powm1[0] = 1;
	for(int i = 1;i <= n;++i) {
		powm1[i] = powm1[i-1] * (m+1) % mod;
	}
	inv[1] = fac[0] = fac[1] = invfac[0] = invfac[1] = 1;
	for(int i = 2;i <= 500000;++i) {
		fac[i] = (fac[i-1] * i) % mod;
		inv[i] = (mod-mod/i) * inv[mod%i] % mod;
		invfac[i] = (invfac[i-1]*inv[i]) % mod;
	}
	int64 ans = 0;
	for(int i = 0;i <= n && i <= m;++i) {
		ans += pown1[m-i] * powm1[n-i] % mod * fac[n] % mod * invfac[n-i] % mod * fac[m] % mod * invfac[m-i] % mod * invfac[i] % mod * ((i&1)==0?1:-1);
	}
	ans %= mod;
	if(ans < 0) ans += mod;
	printf("%lld\n", ans);
}


Measured memory_bytes: 19836
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
ll MOD = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;
    int ans = 0;
    int x_rest = x;
    int y_rest = y;
    if ( a + b >= c * 2 ) {
        ans += min(x, y) * 2 * c;
        x_rest -=  min(x,y);
        y_rest -=  min(x,y);
    }
    if ( x_rest >= 0 ) {
        if ( a >= c * 2 ) {
            ans += c * 2 * x_rest;
            x_rest = 0;
            y_rest = max(0, y_rest - x_rest);
        }
    }
    if ( y_rest >= 0 ) {
        if ( b >= c * 2 ) {
            ans += c * 2 * y_rest;
            y_rest = 0;
            x_rest = max(0, x_rest - y_rest);
        }
    }
    ans += x_rest * a + y_rest * b;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
bool compare(int a,int b)
{
return a>b;
}
int main(){
	int n,a[100000];
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	int co=0;
	for(int i=1;i<=n;i++){
		if(a[i]==i){
			co++;
			int t=a[i];
			if(i+1<=n){
				a[i]=a[i+1];
				a[i+1]=t;
			}
			else {
				a[i]=a[i-1];
				a[i-1]=t;
			}
		}
	}
	cout<<co<<endl;
	return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int main() {
    ll h, w;
    cin >> h >> w;

    if (h == 1 || w == 1) {
        cout << 1 << endl;
        return 0;
    }
    
    ll ans = 0;
    ans += w * (h / 2);
    if (h % 2 == 1) {
        ans += (w + 1) / 2;
    }

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

Measured memory_bytes: 256
# coding : utf-8

K = int(input())

Sunuke = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def ns(n):
    return n / sum(map(int, list((str(n)))))

# 10以上は、ある位に注目したとき、その下の位全てが9の場合すぬけ数の候補となる
if K <= len(Sunuke):
    for i in range(K):
        print(Sunuke[i])

else:
    # 見つけなければいけない残りのすぬけ数
    resi = K - len(Sunuke)
    # 注目している位
    digit = 0
    snk = 9

    while resi > 0:
        nxt1 = snk + 10**digit
        nxt2 = snk + 10**(digit+1)

        # 注目の位に対して1つ上の位により小さな値があったときは、注目の位を１つ上げる
        if ns(nxt1) > ns(nxt2):
            digit +=1
            snk = nxt2
            Sunuke.append(snk)
            resi -= 1
        else:
            snk = nxt1
            Sunuke.append(snk)
            resi -= 1


for i in range(K):
    print(Sunuke[i])

Measured memory_bytes: 3188
#include <cstddef>
#include <cstdint>
#include <vector>

namespace null_null {

using i32 = std::int_fast32_t;
using i64 = std::int_fast64_t;
using u32 = std::uint_fast32_t;
using u64 = std::uint_fast64_t;
using usize = std::size_t;

constexpr usize operator"" _z(unsigned long long x) noexcept {
  return static_cast<usize>(x);
}

template <typename T>
std::vector<T> make_v(usize a) { return std::vector<T>(a); }
template <typename T, typename... Ts>
auto make_v(usize a, Ts... ts) {
  return std::vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template <typename T, typename V>
typename std::enable_if<std::is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }
template <typename T, typename V>
typename std ::enable_if<std::is_class<T>::value != 0>::type
fill_v(T &t, const V &v) {
  for (auto &e : t) fill_v(e, v);
}

template <typename T, typename V>
inline void chmin(T &a, V b) {
  if (a > b) a = b;
}
template <typename T, typename V>
inline void chmax(T &a, V b) {
  if (a < b) a = b;
}

} // namespace null_null

#include <algorithm>
#include <iostream>
#include <utility>

namespace null_null {

void main_() {
  int a, b;
  std::cin >> a >> b;
  std::cout << std::max({a + b, a - b, a * b}) << std::endl;
}

} // namespace null_null

int main() {
  null_null::main_();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
 
    int n;
 
    cin >> n;
 
    vector<int> v(n + 1);
 
    vector<int> ans(n + 1, 0);
 
    for(int i = 1; i <= n; ++i)
        cin >> v[i];
 
    bool isTrue = true;
 
    for(int i = n; i >= 1; --i) {
 
        int sum = 0;
        for(int j = i + i; j <= n; j += i)
            sum ^= ans[j];
 
        ans[i] = sum ^ v[i];
 
   }
 
    vector<int> x;
 
    for(int i = 1; i <= n; ++i)
        if(ans[i])
            x.push_back(i);
 
    cout << x.size() << endl;
 
    for(int i = 0; i < x.size(); ++i)
        cout << x[i] << " ";
 
 
    return 0;
 
}

Measured memory_bytes: 5396
#include <stdio.h>

int main() {
  int a[5];
  int one = 10;
  int time = 0;
  for (int i=0; i<5; i++) {
    scanf("%d", a+i);
    int buf = a[i]%10;
    if (buf != 0) {
      time = time + a[i] - buf + 10;
      if (buf < one) one = buf;
    }
    else time += a[i];
  }
  time = time + one - 10;
  printf("%d\n", time);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include<climits>

using namespace std;
#define ll long long int
#define Max 110000

int main() {
	int n;
	cin>>n;
	int arr[n];
	for(int i=0 ;i<n ; i++)
	{
		cin>>arr[i];
	}
	ll dp[Max+1];
	for(int i=0 ; i<=Max ; i++)
	{
		dp[i]=INT_MAX;
	}
	dp[0]=0;
	//cout<<dp[1];
	for(int i=0 ; i<n ; i++)
	{
		if(i+1<n)
		{
			dp[i+1]=min(dp[i+1],dp[i]+abs(arr[i+1]-arr[i]));
		}
		if(i+2<n)
		{
			dp[i+2]=min(dp[i+2],dp[i]+abs(arr[i+2]-arr[i]));
		}
	}
	cout<<dp[n-1];
	return 0;
}

Measured memory_bytes: 1536
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <algorithm>
#include <numeric>
#include <random>
#include <stdio.h>

using namespace std;

typedef long long LL;
typedef long double LD;
typedef string ST;


#define REP(i,n) for(LL (i)=0;(i)<(n);(i)++)
#define ALL(v) v.begin(), v.end()
#define PRINTLN(v) for(auto (a): v )   cerr << a << endl
#define PRINTSP(v) for(auto (a): v ) {cerr << a << " ";} cerr << endl


void func() {
  LL N,K;
  cin >> N >> K;
  LL cnt=0;
  REP(i, N) {
    LL H;
    cin >> H;
    if (H >= K) {
      cnt++;
    }
  }
  cout << cnt;

  
}

#ifdef CALC_TIME 
#include <windows.h>
int main()
{
  LARGE_INTEGER freq;
  QueryPerformanceFrequency(&freq);
  LARGE_INTEGER start, end;
  QueryPerformanceCounter(&start);
  // 何かの処理
  func();
  QueryPerformanceCounter(&end);
  double time = static_cast<double>(end.QuadPart - start.QuadPart) * 1000.0 / freq.QuadPart;
  fprintf(stderr, "\n%lf[ms]\n", time);
  return 0;
}
#else 
int main()
{
  func();
  return 0;
}
#endif





Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int maxn = 444, mod = 1000000007;
int mul(long long a, long long b){
	return a * b % mod;
}
int pw[maxn][maxn];
int f[maxn][maxn], a[maxn], b[maxn], sum[maxn][maxn];
int main(){
	for(int i = 0; i < maxn; i++){
		pw[i][0] = 1;
		for(int j = 1; j < maxn; j++){
			pw[i][j] = mul(pw[i][j - 1], i);
		}
	}
	int n, c; cin >> n >> c;
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++) cin >> b[i];
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= c; j++){
			for(int k = a[i]; k <= b[i]; k++){
				sum[i][j] += pw[k][j];
				if(sum[i][j] >= mod) sum[i][j] -= mod;
			}
		}
	}
	f[0][0] = 1;
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= c; j++){
			if(f[i][j]){
				for(int k = 0; k <= c && j + k <= c; k++){
					f[i + 1][j + k] += mul(f[i][j], sum[i][k]);
					if(f[i + 1][j + k] >= mod) f[i + 1][j + k] -= mod;
				}
			}
		}
	}
	cout << f[n][c] << endl;
	return 0;
}


Measured memory_bytes: 2432
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;

int dp[52][52];
int W,H;
int map[52][52];

int main(){

  cin >> H >> W;
    
    //入力
    char tmp[100];
    for(int i = 0; i < H ; i++){
      cin >> &tmp[0];
      for(int j = 0; j < W ; j++){
	char x = tmp[j+1];
	tmp[j+1] = '\n';
	map[i][j] = atoi(&tmp[j]);
	tmp[j+1] = x;
      }
    }
    /*   
    for(int i = 0; i < H ; i++){
      for(int j = 0; j < W ; j++){
	cout << map[i][j];
      }
      cout << endl;
    }
    */
    dp[0][0] = map[0][0];
    for(int i = 0; i < H ; i++){
      for(int j = 0; j < W ; j++){
	if(i == 0 && j == 0) continue;
	if(i == 0)
	  dp[i][j] = dp[i][j-1] + map[i][j];
	else if(j == 0)
	  dp[i][j] = dp[i-1][j] + map[i][j];
	else
	  dp[i][j] = min( dp[i-1][j] , dp[i][j-1]) + map[i][j];
      }
    }
    
    /*
      for(int i = 0; i < H ; i++){
      for(int j = 0; j < W ; j++){
      cout << dp[i][j] << " ";
      }
      cout << endl;
      }
    */
    cout << dp[H-1][W-1] - map[H-1][W-1] - map[0][0] << endl;
  
  return 0;
}

Measured memory_bytes: 1196
def bingo(C):
    if C[0]==C[1]==C[2] and C[0]==1:
        return True
    elif C[3]==C[4]==C[5] and C[3]==1:
        return True
    elif C[6]==C[7]==C[8] and C[6]==1:
        return True
    elif C[0]==C[3]==C[6] and C[0]==1:
        return True
    elif C[1]==C[4]==C[7] and C[1]==1:
        return True
    elif C[2]==C[5]==C[8] and C[2]==1:
        return True
    elif C[0]==C[4]==C[8] and C[0]==1:
        return True
    elif C[2]==C[4]==C[6] and C[2]==1:
        return True   
    else:
        return False

A=[]
for _ in range(3):
    x1,x2,x3=map(int, raw_input().split())
    A.append(x1)
    A.append(x2)
    A.append(x3)

B=[ 0 for _ in range(9) ]

N=input()

for _ in range(N):
    b=input()
    for i,x in enumerate(A):
        if b==x:
            B[i]=1
        

if bingo(B):
    print "Yes"
else:
    print "No"


Measured memory_bytes: 28524
#include <iostream> // cout, endl, cin
#include <cmath> //sqrt pow
#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
 
#define rep(i,n) for(int i = 0; i < n; i++)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define mod 1000000007
using ll = long long;
using namespace std;
int main(){
  int n;
  cin >> n;
  char before;
  map<string, int> s;
  rep(i, n){
    string w;
    cin >> w;
    if(i){
      if(w[0] != before){
        cout << "No" << endl;
        return 0;
      }else before = w[w.size() - 1];
      if(s[w] >= 1){
        cout << "No" << endl;
        return 0;
      }
      s[w]++;
    }else{
      before = w[w.size() - 1];
      s[w]++;
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void) {

	int x;
	int a, b, c, d, e, f;
	int tmp;  
	
	scanf("%d", &x);

	for (a = 0; a <= (x/100); a++) {
		for (b = 0; b <= (x/100); b++) {
			for (c = 0; c <= (x / 100); c++) {
				for (d = 0; d <= (x / 100); d++) {
					for (e = 0; e <= (x / 100); e++) {
						for (f = 0; f <= (x / 100); f++) {
							tmp = 100*a + 101*b + 102*c + 103*d + 104*e + 105*f;
							if (tmp == x) {
								printf("1");
								return 0;
							}
						}
					}
				}
			}
		}
	}
	
	printf("0");

	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<random>

//使い方がよくわからない
#include<stack>
#include<queue>
#include<bitset>
#include<sstream>

#define rep(i,n) for(int i=0;i<(n);i++) 
#define rep1(i,n) for(int i=1;i<(n);i++)
#define co(x) cout << x << endl
#define cosp(x) cout << x << " "

using namespace std;
using ll = long long;

int main(int argc, const char *argv[]){
    int n,k;
    cin >> n >> k;
    vector<int> h(n);
    rep(i,n) cin >> h[i];
    int cnt=0;
    rep(i,n) if(h[i]>=k) cnt++;
    co(cnt);
    return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
int main()
{ int n,i;
    float count=0.0, f;
 
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        if(i%2==1)
        count++;
    }
    f=count/n;
    printf("%f",f);
   
    return 0;
}





Measured memory_bytes: 128
import java.util.*;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while(true){
		int H = scan.nextInt();
		int W = scan.nextInt();
		if(H==0&&W==0) break;
		for(int i=0; i<H; i++){
			for(int j=0; j<W; j++){
				if(i%2==0){
					if(j%2==0) System.out.print("#");
					else System.out.print(".");
				}
				else {
					if(j%2==0) System.out.print(".");
					else System.out.print("#");
				}
			}
			System.out.println();
		}
		System.out.println();
		
		}
	}

}

Measured memory_bytes: 26820
import java.io.*;
import java.util.*;

 
public class Main{
	
	public void solve(){
		int N = nextInt();
		int A = nextInt();
		int B = nextInt();
		int ans = 0;
		for(int i = 0; i < N; i++){
			int t = nextInt();
			if(t < A || B <= t){
				ans++;
			}
		}
		out.println(ans);
	}
	
	private static PrintWriter out;
	public static void main(String[] args){
		out = new PrintWriter(System.out);
		new Main().solve();
		out.flush();
	}
	
	
	
	public static int nextInt(){
		int num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10 + (c - '0');
		}
		return minus ? -num : num;
	}
	
	public static long nextLong(){
		long num = 0;
		String str = next();
		boolean minus = false;
		int i = 0;
		if(str.charAt(0) == '-'){
			minus = true;
			i++;
		}
		int len = str.length();
		for(;i < len; i++){
			char c = str.charAt(i);
			if(!('0' <= c && c <= '9')) throw new RuntimeException();
			num = num * 10l + (c - '0');
		}
		return minus ? -num : num;
	}
	public static String next(){
		int c;
		while(!isAlNum(c = read())){}
		StringBuilder build = new StringBuilder();
		build.append((char)c);
		while(isAlNum(c = read())){
			build.append((char)c);
		}
		return build.toString();
	}
	
	
	private static byte[] inputBuffer = new byte[1024];
	private static int bufferLength = 0;
	private static int bufferIndex = 0;
	private static int read(){
		if(bufferLength < 0) throw new RuntimeException();
		if(bufferIndex >= bufferLength){
			try{
				bufferLength = System.in.read(inputBuffer);
				bufferIndex = 0;
			}catch(IOException e){
				throw new RuntimeException(e);
			}
			if(bufferLength <= 0) return (bufferLength = -1);
		}
		return inputBuffer[bufferIndex++];
	}
	
	private static boolean isAlNum(int c){
		return '!' <= c && c <= '~';
	}
}

Measured memory_bytes: 8276
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    string S,T;
    cin >>S>>T;
    sort(all(S));
    sort(all(T));
    reverse(all(T));
    if(S<T){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }



    return 0;
    

}

Measured memory_bytes: 3632
import itertools
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
s=list(itertools.permutations(range(1,n+1)))
count=0
for lis in s:
    flag=False
    if lis[0]==1:
        if all([lis[i],lis[i+1]] in l or [lis[i+1],lis[i]] in l for i in range(n-1)):
            count+=1          
print(count)

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

int main() {
  int N,sum;
  cin >> N;
  for (int i = 0; i < N; i++) {
    int x,y;
    cin >> x >> y;
    sum += y - x + 1;
  }
  
  cout << sum << endl;
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repp(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
#define all(v) v.begin(), v.end()
const int INF = 1 << 30;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
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() {
    ll n;cin >> n;
    vector<ll> a(n,0);
    ll sum = 0;
    rep(i,n){
        cin >> a[i];
        sum += a[i];
    }
    vector<ll> b(n,0);
    ll b_sum = 0;
    rep(i,n){
        cin >> b[i];
        b_sum += b[i];
    }
    if(sum < b_sum){
        cout << -1 << "\n";
        return 0;
    }
    sum = 0;
    vector<ll> amari;
    rep(i,n){
        if(a[i] < b[i]){
            sum -= (b[i] - a[i]);
            a[i] = b[i];
        }else{
            sum += (a[i] - b[i]);
            amari.emplace_back(a[i] - b[i]);
            a[i] = b[i];
        }
    }
    sort(all(amari));
    ll res = 0;
    rep(i,amari.size()){
        if(sum >= amari[i]){
            ++res;
            sum -= amari[i];
        }else break;
    }
    cout << n - res << "\n";
    return 0;
}

Measured memory_bytes: 5708
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))

passed = [-1 for _ in range(n)]

cnt = 0
now = 0
_next = a[now]
remain = 0
for i in range(k):
    _next = a[now]
    if passed[_next] != -1:
        pre = passed[_next]
        remain = (k-pre) % (cnt + 1 - pre)
        now = _next
        break
    passed[now] = cnt
    now = _next
    cnt += 1

for _ in range(remain):
    now = a[now]

print(now + 1)


Measured memory_bytes: 32380
/*	Don’t Quit
	
	When things go wrong as they sometimes will;
		When the road you’re trudging seems all uphill;
			When the funds are low, and the debts are high;
				And you want to smile, but you have to sigh;
					When care is pressing you down a bit
						Rest if you must, but don’t you quit.
*/
#pragma gcc optimize ("unroll-loop")
#pragma gcc optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0)
#define pb push_back
//#define mp make_pair
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define int long long
const int MOD=1e9+7;
const int N=3e5+10;
int gcd(int n,int m)
{
	if(n==0)
		return m;
	else
		return gcd(m%n,n);
}
int sz[N];
int a[N];
void initialize()
{
    for(int i = 1;i<=100000;i++)
    {
        a[i] = i ;
        sz[i]=1;
    }
}
int root(int i)
{
    while(a[i]!=i)
    {
        a[i]=a[a[i]]; 
        i=a[i]; 
    }
    return i;
}
void merge(int x,int y)
{
    int u=root(x);
    int v=root(y);
    if(sz[u] < sz[v])
    {
        swap(u,v);
    }
    a[v] = a[u];
    sz[u]+=sz[v];

}
pair<int,int>x[N];
int32_t main()
{
	IOS;
	int n,m;
	initialize();
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>x[i].ff>>x[i].ss;
	}
	reverse(x+1,x+m+1);
	int ans=n*(n-1)/2;
	vector<int>vp;
	for(int i=1;i<=m;i++)
	{
		if(sz[root(x[i].ff)]==n)
		{
			vp.pb(0);
			continue;
		}
		vp.pb(ans);
		if(root(x[i].ff)!=root(x[i].ss))
		{
			ans-=sz[root(x[i].ff)]*sz[root(x[i].ss)];
			merge(x[i].ff,x[i].ss);

		}
	}
	reverse(all(vp));
	for(int i=0;i<m;i++)
	{
		cout<<vp[i]<<endl;
	}


}

Measured memory_bytes: 7924
n, x, y = map(int, input().split())

ans = [0] * (n-1)
for i in range(n-1):
  for j in range(i+1, n):
    d = min(j-i, abs(i-x+1)+abs(j-y+1)+1)
    ans[d-1] += 1

for a in ans:
    print(a)
 


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

const int mod = 1e9+7;

struct mint{
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint& operator+=(const mint a){
        (x+=a.x)%=mod;
        return *this;
    }
    mint& operator-=(const mint a){
        (x-=mod-a.x)%=mod;
        return *this;
    }
    mint& operator*=(const mint a){
        (x *= a.x)%= mod;
        return *this;
    }
    mint operator+(const mint a)const{
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a)const{
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a)const{
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
      if(!t)return 1;
      mint a = pow(t>>1);
      a*=a;
      if(t%1)a*=*this;
      return a;
    }

    // for prime mod
    mint inv() const {
      return pow(mod-2);
    }
    mint& operator/=(const mint a){
      return (*this) *= a.inv();
    }
    mint operator/(const mint a)const{
      mint res(*this);
      return res/=a;
    }
};

struct combination{
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1){
    fact[0] = 1;
    for(int i = 1; i<n;++i)fact[i] = fact[i-1] * i;
    ifact[n] = fact[n].inv();
    for(int i = n; i>=1;--i) ifact[i-1] = ifact[i] * i;
  }
  mint operator()(int n, int k){
    if(k<0 || k>n)return 0;
    return fact[n] * ifact[k] + ifact[n-k]; 
  }
};

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n)cin>>a[i];
    int m;
    rep(i,n)m+=a[i];
    m = round((double)m/n);
    ll ans=0;
    rep(i,n)ans+=pow(a[i]-m,2);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
from fractions import Fraction


def main():

    N = int(input())
    elements = list(map(int,input().split()))
    elements.sort()

    while(len(elements)!=1):
        left = elements.pop(0)
        right = elements.pop(0)
        newElement = (left+right)/2
        elements.append(newElement)
        elements.sort()
    print(elements[0])



if __name__== "__main__":
    main() 











Measured memory_bytes: 5688
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
//const ll MOD = 1e9+7;
const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const ld EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

//mod-int構造体
//計算量 加減乗算:O(1)、除算:O(log(MOD))、K乗:O(log(K))

template<ll mod> struct Mod_Int{
    ll x;
    Mod_Int() {}
    Mod_Int(ll y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod){}

    Mod_Int &operator += (const Mod_Int &p) {
        x = (x + p.x) % mod;
        return *this;
    }

    Mod_Int &operator -= (const Mod_Int &p) {
        x = (x + mod - p.x) % mod;
        return *this;
    }

    Mod_Int &operator *= (const Mod_Int &p) {
        x = (x * p.x) % mod;
        return *this;
    }

    Mod_Int &operator /= (const Mod_Int &p) {
        *this *= p.inverse();
        return *this;
    }

    Mod_Int operator -() const {return Mod_Int(-x);}

    Mod_Int operator + (const Mod_Int &p) const {return Mod_Int(*this) += p;}

    Mod_Int operator - (const Mod_Int &p) const {return Mod_Int(*this) -= p;}

    Mod_Int operator * (const Mod_Int &p) const {return Mod_Int(*this) *= p;}

    Mod_Int operator / (const Mod_Int &p) const {return Mod_Int(*this) /= p;}

    bool operator == (const Mod_Int &p) const {return x == p.x;}

    bool operator != (const Mod_Int &p) const {return x != p.x;}

    Mod_Int pow (ll n) const{
        Mod_Int now = *this, ret = 1;
        while(n > 0){
            if(n & 1) ret *= now;
            now *= now, n >>= 1;
        }
        return ret;
    }

    Mod_Int inverse () const{
        return pow(mod-2);
    }
};

using mint = Mod_Int<MOD>;
const int MAX_N = 1e7;
mint fac[MAX_N+1], ifac[MAX_N+1];

void init(){
    fac[0] = 1;
    rep2(i, 1, MAX_N){
        fac[i] = fac[i-1]*mint(i);
    }
    ifac[MAX_N] = fac[MAX_N].inverse();
    rep3(i, MAX_N-1, 0){
        ifac[i] = ifac[i+1]*(i+1);
    }
}

mint comb(mint n, mint k){
    return fac[n.x]*ifac[n.x-k.x]*ifac[k.x];
}

mint perm(mint n, mint k){
    return fac[n.x]*ifac[n.x-k.x];
}

int main(){
    int N;
    cin >> N;
    init();
    mint tw = 2, th = 3, ans = th.pow(N);
    rep(i, N/2){
        ans -= comb(N, i)*tw.pow(i+1);
    }
    cout << ans.x << endl;
}

Measured memory_bytes: 156544
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define FOR(i, a, b) for(ll i = a; i < b; ++i)
#define ALL(a) (a).begin(),(a).end()
#define pb push_back
#define INF (long long)1000000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
int dh[4] = {1, 0, -1, 0};
int dw[4] = {0, 1, 0, -1};

int main(void) {
	int n;
	cin>>n;
	vector<int> a(n);
	REP(i, n) cin>>a[i];
	vector<int> b(8, 0);
	int c = 0;
	REP(i, n) {
		if(a[i] <= 399) {
			++b[0];
		}

		else if(a[i] <= 799) {
			++b[1];
		}

		else if(a[i] <= 1199) {
			++b[2];
		}

		else if(a[i] <= 1599) {
			++b[3];
		}

		else if(a[i] <= 1999) {
			++b[4];
		}

		else if(a[i] <= 2399) {
			++b[5];
		}

		else if(a[i] <= 2799) {
			++b[6];
		}

		else if(a[i] <= 3199) {
			++b[7];
		}
		else {
			++c;
		}
	}
	int cnt = 0;
	REP(i, 8) {
		if(b[i] != 0) ++cnt;
	}
	if(cnt == 0 && c != 0) {
		cout<<1<<" ";
	} else {
		cout<<cnt<<" ";
	}
	if(c != 0) {
		cout<<cnt + c<<endl;
	} else {
		cout<<cnt<<endl;
	}
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

const int kMaxN = 100;

int bubbleSort(int *a, int n) {
    int count = 0;

    for (int i = 0; i < n; i++) {
        for (int j = n - 1; j > i; j--) {
            if (a[j] < a[j - 1]) {
                swap(a[j], a[j - 1]);
                count++;
            }
        }
    }

    return count;
}

int main() {
    int n;
    int A[kMaxN];
    cin >> n;

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

    int count = bubbleSort(A, n);

    for (int i = 0; i < n; i++) {
        cout << A[i];
        if (i != n - 1) {
            cout << " ";
        }
    }

    cout << endl;
    cout << count << endl;

}




Measured memory_bytes: 3092
/*||>>>> Praveen Ojha <<<<>>>> 22 June 2019 <<<<>>>> 05:04:19 <<<<||*/
// #pragma GCC optimize("Ofast") //(Very Fast but Inaccurate)
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //(Small operations in many loops)
// #pragma GCC optimize("unroll-loops")
// #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define mod 1000000007
#define inf (int)1e18+5
#define sz(x) (int)x.size()
#define PI 3.141592653589793238510
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define __ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define vi vector<int>
#define vpii vector<pair<int,int> > 
#define vvi vector<vector<int> >
#define PRINT_TIME cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." <<endl;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename   enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef long double ld;
typedef pair<int,int> pii;
//Read Problems Carefully & Check for corner cases N=0,1 ?
///////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////

int32_t main(){__
	int a,b;
	char c;
	cin>>a>>c>>b;
	if(c=='+')
		cout<<a+b<<"\n";
	else
		cout<<a-b<<"\n";
return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
const int MaxN = 1e2;

char s[MaxN + 5][MaxN + 5];

int main()
{
	int a,b,x,ans,biu,piu;
	while(~scanf("%d %d",&a,&b))
	{
		for(int i = 1;i <= 100;i++)
		{
			for(int j = 1;j <= 100;j++)
			{
				s[i][j] = '.';
			}
		}
		biu = 0;
		for(int i = 1;i <= 100;i+=2)
		{
			for(int j = 1;j <= 100;j+=2) 
			{
				biu++;
				if(biu==b) break;
				s[i][j] = '#';
			}
			if(biu == b) break;
		}
		for(int i = 100;i >= 51;i--)
		{
			for(int j = 100;j >= 1;j--)
			{
				s[i][j] = '#';
			}
		}
		piu = 0;
		for(int i = 100;i >= 51;i-=2)
		{
			for(int j = 100;j >= 1;j -= 2)
			{
				piu++;
				if(piu==a) break;
				s[i][j] = '.';
			}
			if(piu == a) break;
		}
		printf("100 100\n");
		for(int i = 1;i <= 100;i++)
		{
			for(int j = 1;j <= 100;j++)
			{
				printf("%c",s[i][j]);
			}
			printf("\n");
		}
	}
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
vector<int> e[200005];
int n,s[200005],a[2];
void dfs(int x,int y,int z){
	s[x]=z,a[z]++;
	for(int i=0;i<e[x].size();i++)
		if(e[x][i]!=y)dfs(e[x][i],x,1-z);
}
int main(){
	n=read();
	for(int i=1;i<n;i++){
		int x=read(),y=read();
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1,0,0);
	int n0=n/3,n1=n/3+((n%3)>0),n2=n-n1-n0;
	for(int j=0;j<2;j++)
		if(a[j]<=n0){
			for(int i=1;i<=n;i++)
				if(s[i]==j){
					printf("%d ",n0*3);
					n0--;
				}
				else{
					if(n1){
						printf("%d ",n1*3-2);
						n1--;
					}
					else if(n2){
						printf("%d ",n2*3-1);
						n2--;
					}
					else{
						printf("%d ",n0*3);
						n0--;
					}
				}
			return 0;
		}
	for(int i=1;i<=n;i++)
		if(s[i]==0){
			if(n1){
				printf("%d ",n1*3-2);
				n1--;
			}
			else{
				printf("%d ",n0*3);
				n0--;
			}
		}
		else{
			if(n2){
				printf("%d ",n2*3-1);
				n2--;
			}
			else{
				printf("%d ",n0*3);
				n0--;
			}
		}
	return 0;
}

Measured memory_bytes: 20864
#include <iostream>
#include <map>
#include <string>
#include <functional>
#include <sstream>

class cStack
{
private:
    int64_t max;
    int64_t p;
    double *pBuff;

public:
    cStack()
    {
        max = 1;
        pBuff = new double[1];
        p = 0;
    }
    void push(int64_t v)
    {
        ++p;
        if (max <= p)
        {
            int64_t tmax = p * 2;
            double *tpBuff = new double[tmax];
            for (int64_t i = 0; i < max; ++i)
            {
                tpBuff[i] = pBuff[i];
            }
            max = tmax;
            delete[] pBuff;
            pBuff = tpBuff;
        }
        pBuff[p] = v;
    }
    double top()
    {
        return pBuff[p];
    }
    void pop()
    {
        if (p > 0)
        {
            --p;
        }
        else
        {
            std::cerr << "cStack underflow\n";
            throw;
        }
    }
    void show()
    {
        std::cerr << "[";
        for (int i = 1; i <= p; ++i)
        {
            std::cerr << pBuff[i] << " ";
        }
        std::cerr << "]\n";
    }
};
void fComment(auto f)
{
    //f();
}
int main(int argc, char *argv[])
{
    cStack oStack;
    fComment([&] {
        std::cerr << "version 1.0.1\n";
    });
    std::string line;
    std::string str;
    std::getline(std::cin, line);
    std::istringstream iss(line);
    fComment([&] {
        std::cerr << line << "\n";
    });
    while (iss >> str)
    {
        if (str == "+")
        {
            double v1, v2;
            v1 = oStack.top();
            oStack.pop();
            v2 = oStack.top();
            oStack.pop();
            oStack.push(v2 + v1);
        }
        else if (str == "-")
        {
            double v1, v2;
            v1 = oStack.top();
            oStack.pop();
            v2 = oStack.top();
            oStack.pop();
            oStack.push(v2 - v1);
        }
        else if (str == "*")
        {
            double v1, v2;
            v1 = oStack.top();
            oStack.pop();
            v2 = oStack.top();
            oStack.pop();
            oStack.push(v2 * v1);
        }
        else if (str == "/")
        {
            double v1, v2;
            v1 = oStack.top();
            oStack.pop();
            v2 = oStack.top();
            oStack.pop();
            oStack.push(v2 / v1);
        }
        else
        {
            oStack.push(std::stod(str));

            fComment([&] {
                oStack.show();
                std::cerr << "a\n";
            });
        }
    }

    std::cout << oStack.top() << "\n";

    fComment([&] {
        std::cerr << "finished\n";
    });

    return 0;
}


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

int main(){
  	long long N,M,m;
  	std::cin >> N >> m >> M;
  	if(m>M || (N==1 && m!=M)){
      	std::cout << "0\n";
      	return 0;
    }
  	std::cout << 1ll+std::max((M-m)*(N-2),0ll) << "\n";
  	return 0;
}

Measured memory_bytes: 3172
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2")
#pragma GCC optimize ("trapv")

#include <bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(cin.failbit);
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (x).size()
#define what_is(x) cerr << #x << " is " << x << endl;
#define wis cout<<endl<<"I already speak english, bitch"<<endl<<endl;
 
typedef long long int lli;
typedef vector<lli> vi;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef pair<ii,lli> iii;
typedef long double C; 

#define trace(args...) { string  _s =#args; replace(_s.begin(), _s.end(), ',',' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);}
void err(istream_iterator<string> it){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args){
    cerr <<  *it  << " : " << a << endl;
    err(++it, args...);
}


int main(){
	fastio;
	int n,l; cin>>n>>l;
	vector<string> v;
	rep(i,0,n){
		string foo; cin>>foo;
		v.pb(foo);
	}
	sort(all(v));
	for(auto x : v) cout<<x;
	return 0;
}

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?), set tle
    * do smth instead of nothing and stay organized
*/


Measured memory_bytes: 256
S = input()
T = input()

len0 = len(S)
S = S * ((len(T) + len(S) - 1) // len(S) * 2)

MOD = 2 ** 31 + 7
base = 26

hashS = [0]
hashT = 0
for s in S :
    hashS.append((hashS[-1] * base + ord(s) - 97) % MOD)
for t in T :
    hashT = (hashT * base + ord(t) - 97) % MOD

ok = [False] * len0
for i in range(len0) :
    if (hashS[i+len(T)] - hashS[i] * pow(base, len(T), MOD)) % MOD == hashT :
        ok[i] = True

def solve() :
    ret = 0
    visited = [-1]*len0
    for i in range(len0) :
        if ok[i] and visited[i] == -1 :
            j = i
            count = 0
            while ok[j] :
                if visited[j] != -1 :
                    count += visited[j]
                    break
                    
                count += 1
                visited[j] = 1
                j = (j+len(T))%len0
                if j == i :
                    return -1
            visited[i] = count
            ret = max(ret, count)
    return ret
        
print(solve())

Measured memory_bytes: 118252
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000

int N;
vector<int> ans;

void dfs(int x,int y,vector<bool> used){
	//cout<<x<<','<<y<<endl;
	int c = 0;
	for(int i=0;i<N;i++){
		if(!used[i])c++;
	}
	if(c==1){
		ans.push_back(x);
		ans.push_back(y);
		return;
	}
	for(int i=0;i<N;i++){
		if(used[i])continue;
		if(((x>>i)&1)==((y>>i)&1))continue;
		used[i] = true;
		int u0 = x;
		int u1;
		int v1 = y;
		int v0;
		for(int j=0;j<N;j++){
			if(used[j])continue;
			u1 = x ^ (1<<j);
			v0 = u1 ^ (1<<i);
			break;
		}
		dfs(u0,u1,used);
		dfs(v0,v1,used);
		break;
	}
}
		


int main(){
	int A,B;
	cin>>N>>A>>B;
	vector<bool> used(N,false);
	
	int cnt = 0;
	for(int i=0;i<N;i++){
		if(((A^B)>>i)&1)cnt++;
	}
	
	if(cnt%2==0){
		cout<<"NO"<<endl;
		return 0;
	}
	
	dfs(A,B,used);
	cout<<"YES"<<endl;
	for(int i=0;i<ans.size();i++){
		if(i!=0)cout<<' ';
		cout<<ans[i];
	}
	cout<<endl;
	
	return 0;
}

Measured memory_bytes: 1656
H, W = map(int, input().split())
board = [list(input()) for i in range(H)]

skip_col = [False] * W
for i in range(len(board[0])):
    for j in range(H):
        if board[j][i] == '#':
            break
    else:
        skip_col[i] = True

for i in range(H):
    if all([c == '.' for c in board[i]]):
        continue
    for j in range(W):
        if skip_col[j]:
            continue
        print(board[i][j], end='')
    print('')


Measured memory_bytes: 4596
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define FOR(i,a,b) for(int i=(a); i<=(b); i++) 
#define rep(i,n) for(int i = 0; i < (n); i++)
const int MOD = 1e9+7;
const int INF = 1e9;
int gcd(int a, int b){/*a>=0,b>=0,￢(a=b=0)*/while(min(a,b)>0){if(a<b)swap(a,b);a=a%b;}return max(a,b);}
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
struct Edge{int to,weight;};
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 dp[101010][4]; //i(0-index)日まででの最大値、i日目はj=0,1,2
int a[101010][3];

signed main(){
  int n;
  cin>>n;
  rep(i,n) cin>>a[i][0]>>a[i][1]>>a[i][2];
  rep(j,3) dp[0][j]=a[0][j];
  rep(i,n-1)rep(j,3) dp[i+1][j]=max(dp[i][(j+1)%3],dp[i][(j+2)%3])+a[i+1][j];
  // dp[i+1][0]=max(dp[i][1],dp[i][2])+a[i+1][0];
  // dp[i+1][1]=max(dp[i][2],dp[i][0])+a[i+1][1];
  // dp[i+1][2]=max(dp[i][0],dp[i][1])+a[i+1][2];
  int ans=dp[n-1][0];
  chmax(ans,dp[n-1][1]);
  chmax(ans,dp[n-1][2]);
  cout<<ans<<endl;
  cout<<endl;
  /*rep(i,n){
    rep(j,3) cout<<dp[i][j]<<" ";
    cout<<endl;
  }*/
  return 0;
}


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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl
#define POSSIBLE(condition) if(condition){cout << "POSSIBLE" << endl;}else{cout << "IMPOSSIBLE" << endl;}
#define Possible(condition) if(condition){cout << "Possible" << endl;}else{cout << "Impossible" << endl;}
#define possible(condition) if(condition){cout << "possible" << endl;}else{cout << "impossible" << endl;}
#define Size(n) (n).size()

typedef long long ll;


using namespace std;

const int INF = 1e9,MOD = 1e9 + 7,ohara = 1e6;
const ll LINF = 1e18;


long long int n,cnt=0,ans=0,a,b,c,d,cmp,cmpp,m,h,w,x,y,sum=0,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl=true;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

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

      
      cin>>a>>b;
     if(a%b==0){
         Cout(0);
     }
     else{
         Cout(1);
     }
     

       
return 0;
}


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

int main(){

  ll N,M;
  cin>>N>>M;
  
  ll a[N],b[N];
  rep(i,N){
    cin>>a[i]>>b[i];
  }
  
  ll c[M],d[M];
  rep(i,M){
    cin>>c[i]>>d[i];
  }
  
  rep(i,N){

    ll distance=INF;
    int label=0;
    rep(j,M){

      ll now=abs(c[j]-a[i])+abs(d[j]-b[i]);
      if(now<distance){
        distance=now;
        label=j+1;
      }

    }
    cout<<label<<endl;

  }

}

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

int main() {
  int A,B,C,K,sum;
  cin >> A >> B >> C >> K;
  if (K<=A) {
    sum=K;
    cout << sum << endl;
  }
  if ((K<=A+B)&&(K>A)) {
    sum=A;
    cout << sum << endl;
  }
  if (K>A+B) {
    sum=A-(K-A-B);
    cout << sum << endl;
  }
}

Measured memory_bytes: 3652