akhauriyash/Code-Regression huggingface dataset:
def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)


def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g

s = input()
flag = False
for i in range(3):
    if s[i] == s[i+1]:
        flag = True

if flag:
    print("Bad")
else:
    print("Good")

Measured memory_bytes: 3064
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
#define PI 3.141592653589793
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}
int gcd(int a, int b){//ユークリッドの互除法
  if (a < b) gcd(b,a); //aの方がbよりでかいのが前提
  if (b == 0) return a; //aをbで割り切れたらreturn
  else gcd(b, a % b);
}
const int INF = 1<<30;
const int MOD = 1000000007;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

int n,u,v;
vector<int> g[100005],dist;

void dfs(int now, int d = 0, int p = -1){
  dist[now] = d;
  for(auto to:g[now]){
    if(to == p) continue;
    dfs(to,d+1,now);
  }
}

vector<int> distCalc(int u){
  dist = vector<int>(n);
  dfs(u);
  return dist;
}

int main(){
  cin >> n >> u >> v;
  u--,v--;
  rep(i,n-1){
    int a,b; cin >> a >> b;
    a--,b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  
  auto distT = distCalc(u);
  auto distA = distCalc(v);
  
  int ans = 0;
  rep(i,n){
    if(distT[i] < distA[i]){
      chmax(ans, distA[i]);
    }
  }
  cout << ans - 1 << endl;
  return 0;
}

Measured memory_bytes: 10744
#include <bits/stdc++.h>
using namespace std;
int main()
{
  char b;
  cin >> b;
  if(b=='A') cout << 'T' << endl;
  else if(b=='T') cout << 'A' << endl;
  else if(b=='C') cout << 'G' << endl;
  else  cout << 'C' << endl;
}


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

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repd(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define forr(i,a,b) for(ll i=(a);i<=(b);i++)
#define ford(i,a,b) for(ll i=(a);i>=(b);i--)
#define all(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define size(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MAXR 100000 //10^5:最大のrange(素数列挙などで使用)



int main(void) {
    long int N,i,j;
    cin >> N;
    long int n[2000001];
    long int m[2000001];
    for(i=0;i<N-1;++i){
       cin >> n[i];
      
    }
     for(i=0;i<N-1;++i){
     
       m[n[i]-1]++;
    }
    for (j=0;j<N;++j){
        
         cout << m[j] << "\n";
    

    }   
    
  return 0;
}

Measured memory_bytes: 6664
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<numeric>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<functional>
 
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
 
using namespace std;
 
#define int long long
//typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	int x,y;
	cin >> x >> y;
	if(abs(x - y) <= 1) cout << "Brown" << endl;
	else cout << "Alice" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

void comp(int a, int b, int c, int d) {
  int ab = a * b, cd = c * d;
  if (ab > cd)
    printf("%d\n", ab);
  else
    printf("%d\n", cd);
}

int main(void) {
  int a, b, c, d;
  scanf("%d %d %d %d", &a, &b, &c, &d);
  comp(a, b, c, d);
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;

int main() {
  string s;
  cin >> s;
  if(s=="hi"||s=="hihi"||s=="hihihi"||s=="hihihihi"||s=="hihihihihi"){
    cout<<"Yes"<<endl;
  } else {
    cout<<"No"<<endl;
  }
  return 0;
}


Measured memory_bytes: 764
#include <stdio.h>
typedef long long ll;
using namespace std;

int main(void) {
  ll i, j, k, a, b, t, ans = 0;
  scanf("%lld%lld", &a, &b);
  t = b - a;
  for(i = 1; i < t; ++i) ans += i;
  ans -= a;
  printf("%lld", ans);
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vector<int> >
#define pii pair<int, int>
#define rep(i,n) for(int i = 0;i < n; i++)
#define Rep(i,n) for(int i = 1;i <= n; i++)

int main(){
    int n,a = 0;string s;map<string, int> m;
    cin >> n;
    rep(i, n){
        cin >> s;
        m[s]++;
        a = max(a, m[s]);
    }
    for(auto i = m.begin(); i != m.end(); i++){
        if((*i).second == a)cout << (*i).first << endl;
    }
    return 0;
}

Measured memory_bytes: 25216
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
ll fac[100001];
ll mod = 1e9 + 7;
ll fact(ll n) {
    if (n == 0 || n == 1) return fac[n] = 1;
    if (fac[n] != 0) return fac[n];
    return fac[n] = (fact(n-1) * n) % mod;
}
int main() {
    ll N, M;
    cin >> N >> M;
    cout << (abs(N - M) > 1 ? 0 : (N == M ? (2 * (fact(N) * fact(M)) % mod) % mod : (fact(N) * fact(M)) % mod)) << endl;
}

Measured memory_bytes: 2560
#include <cstdio>
#include <cctype>
#include <algorithm>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
using namespace std;

typedef long long LL;
const int p=1000000007;
int n,maxa,maxb,a[200100],b[200100],f[4010][4010],ans,fac[8010],inv[8010];

int getint()
{
    char ch;
    while (!isdigit(ch=getchar()));
    int x=ch-'0';
    for (; isdigit(ch=getchar()); x=x*10+ch-'0');
    return x;
}

int calc(int n,int m)
{
    return LL(fac[n])*inv[m]%p*inv[n-m]%p;
}

int main()
{
    n=getint();
    repu(i,1,n)
    {
        a[i]=getint(),b[i]=getint();
        maxa=max(maxa,a[i]),maxb=max(maxb,b[i]);
    }
    repu(i,1,n)
        ++f[maxa-a[i]][maxb-b[i]];
    repu(i,0,maxa*2)
        repu(j,0,maxb*2)
            if (f[i][j])
            {
                (f[i+1][j]+=f[i][j])%=p;
                (f[i][j+1]+=f[i][j])%=p;
            }
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    repu(i,2,maxa*2+maxb*2)
        inv[i]=LL(p-p/i)*inv[p%i]%p;
    repu(i,2,maxa*2+maxb*2)
        fac[i]=LL(fac[i-1])*i%p,inv[i]=LL(inv[i-1])*inv[i]%p;
    repu(i,1,n)
    {
        (ans+=f[a[i]+maxa][b[i]+maxb])%=p;
        (ans+=p-calc(a[i]*2+b[i]*2,a[i]*2))%=p;
    }
    printf("%d\n",500000004LL*ans%p);
    return 0;
}

Measured memory_bytes: 64640
using System;
using System.IO;
using System.Linq;
using System.Diagnostics;
using System.Threading.Tasks;
using System.Collections.Generic;

//

namespace Kyoupro
{
    class Program
    {
        
        static void Main(string[] args)
        {    

            //整数の数を取得
            var input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int N = input[0];//ボール個数
            int K = input[1];//あるべき種類 

            //空白区切り一行
            var balls = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            balls = balls.GroupBy(x => x).Select(x =>x.Count()).ToArray();
            
            //降順ソート
            Array.Sort(balls);
            Array.Reverse(balls);
            
            int count = 0;

            if(balls.Length>K){
                
                for(int k=0;k<K;k++)
                {       
                count +=balls[k];
                }
                count = N-count;
            }
            
            Console.WriteLine(count);
                       
        }
    }
}

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

typedef long long int int64;
static const int64 mod = 998244353LL;
int64 inv[500003],fac[500003],invfac[500003];
int64 choice(int a,int b)
{
	if(a < b || b < 0) return 0;
	return fac[a]*invfac[b]%mod*invfac[a-b]%mod;
}
int64 cat(int a,int b,int c)
{
	return choice(a+b,a)-choice(a+b,b-c);
}
int n,k;
int main()
{
	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;
	}
	scanf("%d%d",&n,&k);
	int64 ans = 0;
	if(k%2==0) {
		int a = k/2;
		if(a >= n-1) ans = cat(a,a-1,a-n+1);
	}
	for(int a = std::max(n-1,k/2+1);a <= k;++a) {
		ans += cat(a,k-a,a-n+1);
	}
	printf("%lld\n", ans%mod);
}


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

//typedef
//------------------------------------------
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

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

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;

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

//main code

int main(int argc, char const* argv[])
{
    int x,a,b;
    cin >> x >> a >> b;
    if (b <= a) {
        cout << "delicious" << endl;
    }
    else if (b <= a + x) {
        cout  << "safe" << endl;
    }
    else {
        cout << "dangerous" << endl;
    }
    return 0;
}


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

using namespace std;

int N;
int ans[504][504];

void sol(vector < int > arr, int gap){
    for(int i = 0; i < (int)arr.size(); ++i){
        int j = (i + 1) % (int)arr.size();
        if(i + 1 == (int)arr.size()) j = (i + 1) % (int)arr.size();
        int x = j;
        while(1){
            ans[arr[i]][arr[j]] = gap;
            j = (j + 1) % (int)arr.size();
            j = (j + 1) % (int)arr.size();
            if(j == x) break;
        }
    }
    if((int)arr.size() > 2){
        vector < int > A, B;
        for(int i = 0; i < (int)arr.size(); ++i){
            if(i % 2) A.push_back(arr[i]);
            else B.push_back(arr[i]);
        }
        sol(A, gap + 1), sol(B, gap + 1);
    }
}

int main(){
    scanf("%d", &N);
    vector < int > vc;
    for(int i = 1; i <= N; ++i) vc.push_back(i);
    sol(vc, 1);
    for(int i = 1; i <= N; ++i){
        for(int j = i + 1; j <= N; ++j){
            printf("%d ", ans[i][j]);
        }
        puts("");
    }
    return 0;
}


Measured memory_bytes: 1536
#!/usr/bin/ruby
#encoding: utf-8

s = gets.chomp

evenFlg = true
oddFlg = true

(0..s.size-1).each do |i|
  if i.even?
    if s[i] == 'L'
      oddFlg = false
      break
    end
  else
    if s[i] == 'R'
      evenFlg = false
      break
    end
  end
end

if oddFlg & evenFlg == true
  puts "Yes"
else
  puts "No"
end

Measured memory_bytes: 1788
#include <stdio.h>
#include <vector>
using namespace std;

typedef vector<long long int> Row;
typedef vector<Row> Matrix;

vector<Row> scan_matrixA(int n, int m)
{	
	vector<Row> matrixA;
	
	for(int i = 0; i < n; i++){
		Row row;		
		for(int j = 0; j < m; j++){
			int a;
			scanf("%d", &a);
			row.push_back(a);
		}
		matrixA.push_back(row);
	}
	return matrixA;
}
vector<Row> scan_matrixB(int m, int l)
{	
	vector<Row> matrixB;
	
	for(int i = 0; i < m; i++){
		Row row;		
		for(int j = 0; j < l; j++){
			int a;
			scanf("%d", &a);
			row.push_back(a);
		}
		matrixB.push_back(row);
	}
	return matrixB;
}
long long int get_answer(vector<Row> matrixA, vector<Row> matrixB, int r, int c)
{
	int m = matrixA[0].size();
	long long int sum = 0;
	for(int i = 0; i < m; i++){
		sum += matrixA[r][i] * matrixB[i][c];
	}
	return sum;
}
vector<Row> keisan(vector<Row> matrixA, vector<Row> matrixB)
{
	int n = matrixA.size();
	int l = matrixB[0].size();
	
	Matrix matrixC(n, Row(l));
	
	for(int i = 0; i < n; i++){	
		for(int j = 0; j < l; j++){
			matrixC[i][j] = get_answer(matrixA, matrixB, i, j);
		}
	}
	return matrixC;
}
void print_matrix(vector<Row> matrix)
{
	int n = matrix.size();
	for(int i = 0; i < n; i++){	
		Row row = matrix[i];
		int l = row.size();
		for(int j = 0; j < l; j++){
			if(j == 0){
				printf("%lld", row[j]);
			}
			else{
				printf(" %lld", row[j]);
			}
		}
		printf("\n");
	}
}

int main(void)
{
	int n, m, l;//??????A????????°?????????A????????°????????????B????????°?????????B????????°
	scanf("%d %d %d", &n, &m, &l);
	
	vector<Row> matrixA;
	vector<Row> matrixB;
	
	matrixA = scan_matrixA(n, m);
	matrixB = scan_matrixB(m, l);
	
	vector<Row> matrix;
	matrix = keisan(matrixA, matrixB);
	
	print_matrix(matrix);
	
	return 0;
}

Measured memory_bytes: 3032
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n;
int main() {
  cin>>n;
  ll x, y;
  for (int i = 1; i <= n; ++i) {
  	ll t, a;
    cin>>t>>a;
    if (i == 1) {
      x = t;
      y = a;
    } else {
      ll det = max((x+t-1)/t, (y+a-1)/a);
      x = det * t;
      y = det * a;
    }
  }
  cout<<x+y<<endl;
  return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

bool solve(const vector<int>& a, int x)
{
    int n = (a.size() + 1) / 2;
    for(int i=0; i<n-1; ++i){
        if((a[n-1-i] >= x) == (a[n-2-i] >= x))
            return a[n-1-i] >= x;
        if((a[n-1-i] >= x) == (a[n+i] >= x))
            return a[n-1-i] >= x;
    }
    return (a[n-1] >= x) ^ (n % 2 == 0);
}

int main()
{
    int n;
    cin >> n;
    vector<int> a(2*n-1);
    for(int i=0; i<2*n-1; ++i)
        cin >> a[i];

    int left = 1;
    int right = 2 * n - 1;
    while(left < right){
        int mid = (left + right + 1) / 2;
        if(solve(a, mid))
            left = mid;
        else
            right = mid - 1;
    }
    cout << left << endl;

    return 0;
}

Measured memory_bytes: 1024
num = int(input())

list_A = list(map(int,input().split()))

cnt=0
for i in range(num-2):
    if list_A[i] < list_A[i+1] and list_A[i+1] < list_A[i+2]:
        cnt += 1
    elif list_A[i] > list_A[i+1] and list_A[i+1] > list_A[i+2]:
        cnt += 1

    else:
        pass

print(cnt)

Measured memory_bytes: 3064
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
n = readi()
t = []
for i in range(n):
    s = list(read())
    s.sort()
    t.append(s)
t.sort()
index = 0
count = 0
# print(t)
d = 0
for i in range(1,n):
    if t[index] == t[i]:
        d += 1
    else:
        if d >= 1:
            d += 1
            count += cmb(d, 2)
        d = 0
        index = i
if d >= 1:
    d += 1
    count += cmb(d,2)
print(count)

Measured memory_bytes: 26928
#include<iostream>
 
int main(){
int a,b,c;
std::cin>>a>>b>>c;
if(((a==5)&&(b==5)&&(c==7))||
((a==5)&&(b==7)&&(c==5))||
((a==7)&&(b==5)&&(c==5))){
 std::cout<<"YES"<<std::endl;
}else{
std::cout<<"NO"<<std::endl;
}
 
}

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, X;
    cin >> N >> X;
    ll ans = X;
    ll d = N - X;
    ll cnt = N / d;
    ans += 2 * d * cnt - d;
    ll tmp = d;
    if (N % d == 0) ans -= d;
    d = N % d;
    N = tmp;
    while (d > 0) {
        cnt = N / d;
        ans += 2 * d * cnt;
        tmp = d;
        if (N % d == 0) {
            ans -= d;
        }
        d = N % d;
        N = tmp;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
#from functools import reduce
import copy

cost = [0,2,5,5,4,5,6,3,7,6]

dic = {}
def dic_add(dic, key, val):
  if key in dic:
    dic[key] += adic
def dic_pop(dic, key):
  if key in dic:
    dic.pop(key)
  
for a in A:
  dic[cost[a]] = a
if 2 in dic:
  dic_pop(dic,4)
  dic_pop(dic,6)
  if 3 in dic:
    dic_pop(dic,5)
    dic_pop(dic,7)
  elif 5 in dic:
    dic_pop(dic,7)
elif 3 in dic:
  dic_pop(dic,6)
  if 4 in dic:
    dic_pop(dic,7)

dic_inv = [0 for _ in range(10)]
A = []
for c in dic:
  dic_inv[dic[c]] = c 
  A.append(dic[c])
A.sort(reverse = True)
label = [-1 for _ in range(10)]
for i in range(len(A)):
  label[A[i]] = i
  
def larger(a_lis, b_lis): # a > b の判定
  if sum(a_lis) > sum(b_lis):
    del b_lis
    return a_lis
  elif sum(a_lis) < sum(b_lis):
    del a_lis
    return b_lis
  else:
    if a_lis > b_lis:
      del b_lis
      return a_lis
    else:
      del a_lis
      return b_lis
INF = 10**20
DP = [[-INF for a in A] for _ in range(N+1)]
DP[0] = [0 for a in A]
for n in range(2,N+1):
  for a in A:
    if n - cost[a] >= 0:
      tmp = copy.copy(DP[n - cost[a]])
      tmp[label[a]] += 1
      DP[n] = larger(DP[n], tmp)
      
ans = 0
for a in A:
  num_a = DP[N][label[a]] 
  for i in range(num_a):
    ans *= 10
    ans += a 
    
print(ans)
"""
print(A)
print(label)
print(*DP, sep = "\n")
"""
  
  
      
      
      
  
    
  
  

Measured memory_bytes: 72780
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
// 0 w  1 e
const int N = 3*(int)1e5+100;
char s[N];
int l[N]={0},r[N]={0};
int main()
{
    int n;
    scanf("%d%s",&n,s);
    for(int i=1;i<n;++i)
    {
        if(s[i-1]=='W')
            l[i] = l[i-1]+1;
        else
            l[i] = l[i-1];
    }
    for(int i=n-2;i>=0;--i)
    {
        if(s[i+1]=='E')
            r[i] = r[i+1]+1;
        else
            r[i] = r[i+1];
    }
    int ans = N+100;
    for(int i=0;i<n;++i)
        ans = min(ans,l[i]+r[i]);
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 2944
import java.util.Scanner;

public class Main
{
    public static void main(String[] args) 
    {
        Scanner scan = new Scanner(System.in);
        int array[] = new int[30];
        
        while(scan.hasNext())
        {
            int n = scan.nextInt();
            if(n==0)
                break;
            fact(n,n,array,0);
        }
    }
    
    public static void fact(int n, int num, int[] array, int count)
    {
        if(num<=0)
        {
            System.out.print(array[0]);
            for(int i=1;i<count;i++)
            {
                System.out.print(" "+array[i]);
            }
            System.out.println();
        }
        else
        {
            for(int i=min(n,num);i>0;i--)
            {
                array[count]=i;
                fact(i,num-i,array,count+1);
            }
        }
           
    }

    public static int min(int a, int b)
    {
        if(a>b)
            return b;
        else
            return a;
    }
}

Measured memory_bytes: 38108
s = list(input())

A = list(set(s))

B = []

for i in range(len(A)):
    C = []
    for j in range(len(s)):
        if A[i] == s[j]:
            C.append(j)
    C.append(-1)
    C.append(len(s))
    C = sorted(C)
    D = []
    for i in range(len(C) - 1):
        D.append(C[i+1] - C[i] - 1)
    
    B.append(max(D))
print(min(B))

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

using namespace std;
const int MAXN = 1e4 + 5;

char str[40000];
int sg[MAXN], sr[MAXN], sb[MAXN];
int main() {
	int n; cin >> n;
	scanf("%s", str + 1);
	for (int i = n; i >= 1; i--) 
		sg[i] += sg[i + 1] + (str[i] == 'G'),
		sr[i] += sr[i + 1] + (str[i] == 'R'),
		sb[i] += sb[i + 1] + (str[i] == 'B');
	long long ans = 0;
	for (int i = 1; i < n - 1; i++) 
		for (int j = i + 1; j < n; j++) 
			if (str[j] != str[i]) {
				if (str[j] != 'G' && str[i] != 'G') 
					ans += sg[j + 1];
				if (str[j] != 'R' && str[i] != 'R') 
					ans += sr[j + 1];
				if (str[j] != 'B' && str[i] != 'B') 
					ans += sb[j + 1];
				
				if (2 * j - i <= n && str[2 * j - i] != str[i] && str[2 * j - i] != str[j]) 
					ans--;
			}
	cout << ans << endl;
} 

Measured memory_bytes: 3780
#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 h, n;
    int a;
    
    cin >> h >> n;
    rep(i, n){
        cin >> a;
        h -= a;
    }
    
    if(h <= 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}




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

int main(){
    int n;
    cin >> n;
    vector<int> p(n+1);
    rep(i,n) {
        int a;
        cin >> a;
        p[a] = i+1;
    }
    vector<int> num;
    int k = 1;
    while (k <= n) {
        int c = 1;
        while(k < n && p[k] < p[k+1]){
            k++; c++;
        }
        num.push_back(c);
        k++;
    }
    sort(num.begin(),num.end(),greater<int>());
    cout << n - num[0] << endl;
    return 0;
}


Measured memory_bytes: 2168
while 1:
        table = input().split()
        a = int(table[0])
        op = table[1]
        b = int(table[2])

        if op =='?':
                break

        if op == '+':
                print ( '%d' % (a+b))
        elif op == '-':
                print('%d' % (a-b))
        elif op == '*':
                print('%d' % (a*b))
        elif op == '/':
                print('%d' % (a/b))


Measured memory_bytes: 5592
// AtCoder Regular Contest 070
// C - Go Home

#include <cstdio>
#define MAX_X ((ll)1e9)
using namespace std;
typedef long long int ll;


ll X;

int main() {

  ll l, r, m, sum;

  scanf("%lld", &X);

  // (l, r]
  l = 0;
  r = MAX_X;
  while (r - l > 1) {
    m = (r + l + 1) / 2;
    sum = m * (m + 1) / 2;
    if (sum >= X) {
      r = m;
    } else {
      l = m;
    }
  }
  printf("%lld\n", r);

  return 0;

}




Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef vector<int> vec1;
typedef vector<string> vec2;
typedef vector<double> vec3;

int main() {

  int w, a , b;
  cin >> w >> a >> b;
  int c = min(a,b);
  int ans = 0;
  if(c == a) {
    for(int i = 0; i < 10e10; i++) {
      if(b <= a+w ) {
        cout << ans << endl;
        return 0;
      } else {
        ans++;
        b--;
      }
    }
  } else if(c == b) {
    for(int i = 0; i < 10e10; i++) {
      if(b+w >= a) {
        cout << ans << endl;
        return 0;
      } else {
        ans++;
        b++;
      }
    }
  }
}

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

using ULL = unsigned long long;

int main()
{
    ULL N;
    map<string, ULL> map;
    cin >> N;
    
    for (ULL i = 0; i < N; ++i)
    {
        string si;
        cin >> si;
        sort(si.begin(), si.end());
        
        if (map.find(si) == map.end()) map[si] = 0;
        else ++map[si];
    }
    
    ULL ans = 0;

    for(auto itr = map.begin(); itr != map.end(); ++itr) {
        if (itr->second == 0) continue;
        for (int i = 1; i <= itr->second; ++i)
        {
            ans += i;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 11136
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<string>

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

using namespace std;

typedef long long int ll;

const ll INF=(ll)1e18;

int N, K;

int main(){
    cin >> N >> K;
    ll dp[N];
    
    vector<ll> h(N);
    REP(i,N){
      cin >> h[i];
    }
    
    dp[0]=0;
    FOR(i,1,N){
      vector<ll> v;
      FOR(j,1,K+1){
        if(i-j<0)break;
        v.push_back(dp[i-j] + abs(h[i] - h[i-j]));
      }
      dp[i] = *min_element(v.begin(), v.end());
    }
    cout << dp[N-1] << endl;
}


Measured memory_bytes: 1792
class SegmentTreeMax():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=val
    while pos>1:
      pos=pos//2
      self.tree[pos]=max(self.tree[2*pos],self.tree[2*pos+1])
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=max(ret,self.tree[r])
      r=(r-1)//2
      ret=max(ret,self.tree[l])
      l=(l+1)//2
    return ret

mod=998244353
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
arr=sorted(arr,key=lambda x:x[0])
st=SegmentTreeMax(n,0)
ranges=[]
for i in range(n):
  x=arr[i][0]+arr[i][1]
  l=-1
  r=n
  while r-l!=1:
    mid=(l+r)//2
    if arr[mid][0]>=x:
      r=mid
    else:
      l=mid
  ranges.append(r-1)
  st.update(i,r-1)
for i in range(n-1,-1,-1):
  ranges[i]=st.query(i,ranges[i])
  st.update(i,ranges[i])
dp=[0]*(n+1)
dp[-1]=1
for i in range(n-1,-1,-1):
  j=ranges[i]+1
  dp[i]=dp[i+1]+dp[j]
  dp[i]%=mod
print(dp[0])

Measured memory_bytes: 109144
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long mod = 998244353;
  int n,s;
  cin >> n >> s;
  long long d[3005][3005];
  int a[3005];
  for(int i=0; i<n; i++) cin >> a[i];
  for(int j=0; j<=n; j++){
    for(int k=0; k<=s; k++){
      d[j][k] = 0;
    }  
  }
  d[0][0]=1;
  for(int i=0; i<n; i++){
    for(int k=0; k<=s-a[i]; k++) d[i+1][k+a[i]] = d[i][k];
    for(int k=0; k<=s; k++) d[i+1][k] = (d[i+1][k]+2*d[i][k])%mod;
  }
  cout << d[n][s] << endl;
}

Measured memory_bytes: 74072
#include<bits/stdc++.h>
using namespace std;
#define ms(x,y) memset(x, y, sizeof(x))
#define lowbit(x) ((x)&(-x))
#define sqr(x) ((x)*(x))
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

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

void run_case() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> g(n, vector<char>(m));
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            cin >> g[i][j];
    function<int(int,int)> bfs = [&](int x, int y) {
        queue<pair<pair<int,int>,int>> q;
        q.push(make_pair(make_pair(x, y), 0));
        int ans = 0;
        vector<vector<int>> vis(n, vector<int>(m));
        while(!q.empty()) {
            auto now = q.front();
            q.pop();
            if(vis[now.first.first][now.first.second]++) continue;
            if(g[now.first.first][now.first.second] == '#') continue;
            ans = max(ans, now.second);
            for(int i = 0; i < 4; ++i) {
                int nx = now.first.first + dx[i], ny = now.first.second + dy[i];
                if(nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    q.push(make_pair(make_pair(nx, ny), now.second+1));
                }
            }
        }
        return ans;
    };
    int ans = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            if(g[i][j] == '.') ans = max(ans, bfs(i, j));
    cout << ans;
}


int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cout.flags(ios::fixed);cout.precision(9);
    //int t; cin >> t;
    //while(t--)
    run_case();
    cout.flush();
    return 0;
}

Measured memory_bytes: 256
let split_string ?(pattern="") = Str.split @@ Str.regexp pattern

let (n, m, k) = Scanf.sscanf (read_line ()) "%d %d %d" @@ fun n m k -> (n, m, k)
let a = read_line () |> split_string ~pattern:" " |> List.map int_of_string |> Array.of_list
let b = read_line () |> split_string ~pattern:" " |> List.map int_of_string |> Array.of_list


let sa = Array.make (n + 1) 0
let sb = Array.make (m + 1) 0

let rec solve i = function
  | 0 -> (i, 0)
  | j -> if sa.(i) + sb.(j) > k then solve i (j - 1) else (i + j, j)

let () =
  for i = 1 to n do sa.(i) <- sa.(i - 1) + a.(i - 1) done;
  for i = 1 to m do sb.(i) <- sb.(i - 1) + b.(i - 1) done;
  Printf.printf "%d\n" @@ fst 
    @@ Array.fold_left (fun (m, j) i -> 
      if sa.(i) > k then (m, j)
      else let (nm, nj) = solve i j in (max m nm, nj)
    ) (0, m) 
    @@ Array.init (n + 1) @@ fun i -> i

Measured memory_bytes: 39196
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

using System.Collections;

class Program
{
    static void Main()
    {
        int[] xy = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();

        int X = xy[0];
        int Y = xy[1];

        Console.WriteLine(X + Y / 2);
    }
    
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define all(x) (x).begin(), (x).end()
#define len(x) ((long long)(x).size())
#define g(a, b) __gcd((a), (b))
#define l(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
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; }
template<class T, class U>T rem(T a, U b) { return a - b*floor(a/b); }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



int main()
{
        ll N;
        cin >> N;
        vector<string> S(N);
        rep(i, 0, N) {
            cin >> S[i];
            sort(all(S[i]));
        }
        sort(all(S));

        ll ans = 0;
        ll cnt = 0;
        string now = S[0];
        rep(i, 0, N) {
            if (S[i] == now) {
                ++cnt;
            } else {
                ans += cnt*(cnt-1)/2;
                cnt = 1;
                now = S[i];
            }
        }
        ans += cnt*(cnt-1)/2;
        cout << ans << endl;
}





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

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

typedef long long ll;
int main(int argc, char const *argv[])
{
    cin.tie(0);
   	ios::sync_with_stdio(false);
    int A, B, C; cin >> A >> B >> C;
    if (A == B) {
        if (A != C) {
            cout << "Yes" << endl; return 0;
        }
        else {
            cout << "No" << endl; return 0;
        }
    }
    else if (A == C){
        cout << "Yes" << endl; return 0;
    }
    else {
        if (B == C) {
            cout << "Yes" << endl; return 0;
        }
        else {
            cout << "No" << endl; return 0;
        }
    }
    return 0;
}


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

using namespace std;

typedef long long LL;

#define MAX_N 105

int N;
void input()
{
  cin >> N;
}

string InitString[4];
bool used[4];

void solve()
{

  string Q;

  InitString[0] = "..";
  InitString[1] = ".#";
  InitString[2] = "#.";
  InitString[3] = "##";

  memset(used, 0, sizeof(used));

  string A, B;
  bool f = true;
  bool update = false;

  while(true){

    update = false;

    if(A.length() == N){
      cout << A << endl << B << endl;
      cin >> Q;
      return;
    }

    for (size_t i = 0; i < 4; i++) {
      if(f){
        string _A = A + InitString[i][0];
        string _B = B + InitString[i][1];
        cout << _A << endl << _B << endl;
        cin >> Q;
        if(Q == "T"){
          A += InitString[i][0];
          B += InitString[i][1];
          update = true;
          break;
        }
        else if(Q == "end"){
          return;
        }
      }
      else{
        string _A = InitString[i][0] + A;
        string _B = InitString[i][1] + B;
        cout << _A << endl << _B << endl;
        cin >> Q;
        if(Q == "T"){
          A = InitString[i][0] + A;
          B = InitString[i][1] + B;
          update = true;
          break;
        }
        else if(Q == "end"){
          return;
        }
      }
    }

    if(!update){
      f = false;
    }

  }

}

int main()
{
  input();
  solve();
  return 0;
}


Measured memory_bytes: 724
#include<iostream>

using namespace std;

#define H_MAX 500000
#define left(i) (i*2)
#define right(i) (i*2 + 1)

int h, A[H_MAX + 1];

void maxHeapify(int i){
  int r = right(i);
  int l = left(i);
  int max = i;

  if(l <= h && A[l] > A[max])
    max = l;

  if(r <= h && A[r] > A[max])
    max = r;

  if(max != i) {
    swap(A[i],A[max]);
    maxHeapify(max);
  }
}

int main() {
  cin >> h;

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

  for(int i = h/2; i >= 1; i--){
    maxHeapify(i);
  }

  for(int i = 1; i <= h; i++){
    cout << " " << A[i];
  }

  cout << "\n";
}



Measured memory_bytes: 5048
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;

int main(){
    string S, T;
    cin >> S >> T;
    size_t sz = S.size();
    unsigned answer = 0;
    for (size_t i = 0; i < sz; i++){
        if(S[i] != T[i]) answer++;
    }
    printf("%u\n", answer);
	return 0;
}

Measured memory_bytes: 3900
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()

B = []
for i in range(N):
    if i==0 or i==N-1:
        B.append((-1)**i)
    else:
        B.append(((-1)**i)*2)
B.sort()

print(max(abs(sum([A[i]*B[i] for i in range(N)])),abs(sum([A[i]*B[N-1-i] for i in range(N)]))))

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

int kansuu(int x){
  int y,z=1;
  rep(i,x){
    y=y+z;
    z=z*10;
  }
  return y;
}
    

int main(){
  int a,b;
  cin >>a>>b;
  
  cout << min(a,b)*kansuu(max(a,b))<<endl;
}

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

uint32_t mod;
class modint{
    uint64_t value;
public:
    modint(const int64_t x=0) noexcept: value(x % mod + (x < 0 ? mod : 0)){ }
    explicit operator uint64_t() const noexcept{ return value; }
    modint inverse() const noexcept{ return pow(*this, mod-2); }
    bool operator==(const modint &rhs) const noexcept{ return value == rhs.value; }
    bool operator!=(const modint &rhs) const noexcept{ return value != rhs.value; }
    modint operator+() const noexcept{ return modint(*this); }
    modint operator-() const noexcept{ return modint(mod - value); }
    modint operator+(const modint &rhs) const noexcept{ return modint(*this) += rhs; }
    modint operator-(const modint &rhs) const noexcept{ return modint(*this) -= rhs; }
    modint operator*(const modint &rhs) const noexcept{ return modint(*this) *= rhs; }
    modint operator/(const modint &rhs) const noexcept{ return modint(*this) /= rhs; }
    modint &operator+=(const modint &rhs) noexcept{
        if((value += rhs.value) >= mod) value -= mod;
        return *this;
    }
    modint &operator-=(const modint &rhs) noexcept{ return *this += mod - rhs.value; }
    modint &operator*=(const modint &rhs) noexcept{
        if((value *= rhs.value) >= mod) value %= mod;
        return *this;
    }
    modint &operator/=(const modint &rhs) noexcept{ return *this *= rhs.inverse(); }
    modint operator++(int) noexcept{
        modint ret(*this);
        if((++value) >= mod) value -= mod;
        return ret;
    }
    modint operator--(int) noexcept{
        modint ret(*this);
        if((value += mod - 1) >= mod) value -= mod;
        return ret;
    }
    modint &operator++() noexcept{ return *this += 1; }
    modint &operator--() noexcept{ return *this -= 1; }
    friend std::ostream &operator<<(std::ostream &os, const modint &x){ return os << x.value; }
    friend std::istream &operator>>(std::istream &is, modint &x){
        int64_t i;
        is >> i;
        x = modint(i);
        return is;
    }
    friend modint pow(const modint &x, uint64_t y){
        modint ret{1}, m{x};
        while(y > 0){
            if(y & 1) ret *= m;
            m *= m;
            y >>= 1;
        }
        return ret;
    }
};

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

    int n, p;
    cin >> n >> p;
    string s;
    cin >> s;
    if(p == 2 || p == 5){
        int64_t ans = 0;
        for(int i=0;i<n;++i){
            if((s[i] - '0') % p == 0) ans += i + 1;
        }
        cout << ans << endl;
        return 0;
    }

    static int64_t cnt[100001];
    cnt[0] = 1;
    mod = p;
    modint sum = 0;
    for(int i=n-1;i>=0;--i){
        sum += pow(modint{10}, n-1-i) * (s[i] - '0');
        ++cnt[(uint64_t)sum];
    }
    int64_t ans = 0;
    for(int i=0;i<p;++i) ans += cnt[i] * (cnt[i] - 1) / 2;
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 720
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
const double pi=3.14159265358979323846;
int ctoi(const char c) {
    if ('0' <= c && c <= '9') return (c - '0');
    return -1;
}
vector<int> input(int n) {
    vector<int> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec.at(i);
    }
    return vec;
}
void output(vector<int> vec) {
    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << " ";
    }
    return;
}
vector<vector<int>> input(int n, int m) {
    vector<vector<int>> table(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> table. at(i).at(j);
        }
    }
    return table;
}
void output(vector<vector<int>> table) {
    for (int i = 0; i < table.size(); i++) {
        for (int j = 0; j < table.at(0).size(); j++) {
            cout << table.at(i).at(j) << " ";
        }
        cout << endl;
    }
}
long long perm(int n, int r) {
    if (n < r) {
        cout << "error" << endl;
        return 0;
    }
    long long perm = 1;
    for (int i = n; i > n - r; i--) {
        perm *= i;
    }
    return perm;
}
long long comb(int n, int r) {
    if (n < r) {
        cout << "error" << endl;
        return 0;
    }
    long long comb = perm(n,r);
    for (int i = r; i > 0; i--) {
        comb /= i;
    }
    return comb;
}
long long homo(int n, int r) {
    return comb(n + r - 1, n - 1);
}
long long fact(int n) {
    long long fact = 1;
    for (int i = n; i > 0; i--) {
        fact *= i;
    }
    return fact;
}
int gcd(int a, int b){
    if (a % b == 0){
        return(b);
    }else{
        return(gcd(b, a % b));
    }
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
bool isprime(int n){
    if (n < 2) return false;
    else if (n == 2) return true;
    else if (n % 2 == 0) return false;

    for (int i = 3; i <= sqrt(n); i += 2){
        if (n % i == 0){
            return false;
        }
    }
    return true;
}
void sayYes(bool f) {
    if (f) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}
void sayYES(bool f) {
    if (f) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}

int main() {
  int n,a,b;
  cin >> n >> a >> b;
  string s;
  cin >> s;
  int cnta=0,cntb=0;
  rep(i,n){
    if(s[i]=='a'){
      if(cnta<a+b){
        cout << "Yes" << endl;
        cnta++;
      }else{
        cout << "No" << endl;
      }
    }
    else if(s[i]=='b'){
      if(cnta<a+b&&cntb<b){
        cout << "Yes" << endl;
        cnta++;
        cntb++;
      }else{
        cout << "No" << endl;
      }
    }else{
      cout << "No" << endl;
    }
  }
}


Measured memory_bytes: 896
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

int MAX;
vector<int> g[10];
int dfs(int u=0, int b=0){
  if(b>>u&1) return 0;
  b ^= 1<<u;
  if(b==MAX) return 1;
  int res = 0;
  for(int v:g[u]) res += dfs(v,b);
  return res;
}
int main() {
  int n,m;
  cin >> n >> m;
  MAX = (1<<n)-1;
  rep(i,m){
    int a,b;
    cin >> a >> b;
    --a; --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  cout << dfs() << endl;
}


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

int main() {
  ll n;cin>>n;
  vector<ll> a(n);
  ll cnt=0;
  ll mod=1e9+7;
  rep(i,n){
    cin>>a[i];
    cnt+=a[i];
    cnt%=mod;
  }
  ll ans=0;
  rep(i,n-1){
    cnt-=a[i];
    if(cnt<0)cnt+=mod;
    ans+=(a[i]*cnt)%mod;
    ans%=mod;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 4840
// #include <bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define exf(x)	 for(auto&& tmp : x) { cout << tmp << endl; }	// 拡張for
#define PI 3.14159265358979323846264338327950288
const int MOD{ int(1e9 + 7) };	// = 1000000007
const int inf{ 2100000000 };	// = 2100000000 (MAX:2147483647)
typedef long long ll;
using namespace std;

// -------------------------------------------------- //
// ------------------ ここから本編 ------------------ //
// -------------------------------------------------- //

set<ll> prime_set; // [0]2, [1]3, [2]5, [3]7, ... のように代入される
void PRIME_SET(ll x) {
	if (x <= 1)return;

	for (ll i = 2; i * i <= x; i++) {
		if (x % i == 0) {
			PRIME_SET(i);
			PRIME_SET(ll(x / i));
			return;
		}
	}
	prime_set.insert(x);
	return;
}

int main(void) {

	ll A, B; cin >> A >> B;

	prime_set.clear();
	PRIME_SET(A);
	set<ll> a_map = prime_set;
	
	prime_set.clear();
	PRIME_SET(B);
	set<ll> b_map = prime_set;

	ll ans = 1;
	for (auto x : a_map) {
		if (find(b_map.begin(), b_map.end(), x) != b_map.end()) ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3644
#include <iostream>
using namespace std;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main(){
  int a , b, c , x;
  cin >> a >> b >> c >> x;
  int sum = 0;
  for(int A = 0;A <= a;A++){
    for(int B = 0;B <= b;B++){
      for(int C = 0;C <= c;C++){
        int X = 500*A + 100*B + 50*C;
        if(X == x)sum++;
      }
    }
  }
  cout << sum << endl;
}



Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,a,b) for(int i =(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPm(i,n) for(int i=(n)-1;i>=0;i--)
#define REP1(i,n) for(int i=1;i<=(n);i++)
typedef long long ll;
#define MAX_N 100000
struct qdata{
    int x;
    int y;
    int d;
};
bool isW[50][50];
bool flag[50][50];
int main(){
    int H,W;
    string s[50];
    cin >> H >> W;
    REP(i,H) cin >> s[i];
    int bcount = 0;
    REP(i,H){
        REP(j,W){
            if(s[i][j] == '.') isW[i][j] = true;
            else bcount++;
        }
    }
    queue<qdata> que;
    que.push((qdata){0,0,1});
    flag[0][0] = true;
    while(! que.empty()){
        qdata q = que.front();
        que.pop();
        if(q.x == H-1 && q.y == W-1){
            cout << H*W - q.d - bcount << endl;
            return 0;
        }
        if(q.x < H-1 && isW[q.x+1][q.y] &&! flag[q.x+1][q.y]){
            flag[q.x+1][q.y] = true;
            que.push((qdata){q.x+1,q.y,q.d+1});
        }
        if(q.x > 0 && isW[q.x-1][q.y] &&! flag[q.x-1][q.y]){
            flag[q.x-1][q.y] = true;
            que.push((qdata){q.x-1,q.y,q.d+1});
        }
        if(q.y < W-1 && isW[q.x][q.y+1] &&! flag[q.x][q.y+1]){
            flag[q.x][q.y+1] = true;
            que.push((qdata){q.x,q.y+1,q.d+1});
        }
        if(q.y > 0 && isW[q.x][q.y-1] &&! flag[q.x][q.y-1]){
            flag[q.x][q.y-1] = true;
            que.push((qdata){q.x,q.y-1,q.d+1});
        }
    }
    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <complex>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cassert>
#include <cstring>
using namespace std;
 
#define REP(i,x,n) for(int i = x; i < (int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define f first
#define s second
#define mp make_pair
#define pb push_back
 
typedef pair<int,int> P;
typedef long long ll;
 
static const int INF = (1 << 29);
static const double EPS = 1e-9;
static const double PI = acos(-1.0);
 
int come[100003];
 
int main(){
  int N;
  scanf("%d",&N);
  rep(i,N){
    int a,b;
    scanf("%d%d",&a,&b);
    come[a]++;
    come[b + 1]--;
  }
  int ans = 0;
  int sum = 1;
  rep(i,100003){
    sum += come[i];
    if(i <= sum) ans = i;
  }
  printf("%d\n",--ans);
  return 0;
}

Measured memory_bytes: 3552
#include <bits/stdc++.h>
    using namespace std;
     
    int main () 
    {
        int a, b;
        std::cin >> a >> b;
        
        if (a <= b)
        {
            cout << a << endl;
        }
        else
        {
            cout << a - 1 << endl;
        }
        
        return 0;
    }

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

int parse(string x, int &i)
{
	switch (x[i])
	{
	case '0': i++; return 0;
	case '1': i++; return 1;
	case '2': i++; return 2;
	case '-': i++; return (2 - parse(x, i));
	}

	i++;
	int l = parse(x, i);
	int flag = -1;
	if (x[i] == '*')
		flag = 0;
	else
		flag = 1;
	i++;
	int r = parse(x, i);
	i++;

	if (flag == 0)
	{
		if (l == 2 && r == 2) return 2;
		if (l == 0 || r == 0) return 0;
		return 1;
	}

	if (l == 0 && r == 0) return 0;
	if (l == 2 || r == 2) return 2;
	return 1;
}

string replace(string src, string from, string to)
{
	string::size_type Pos(src.find(from));
	while (Pos != string::npos)
	{
		src.replace(Pos, from.length(), to);
		Pos = src.find(from, Pos + to.length());
	}
	return src;
}

int main()
{
	while (1)
	{
		string s; cin >> s;
		if (s[0] == '.') return 0;

		int ans = 0;
		rep(p, 0, 3) rep(q, 0, 3) rep(r, 0, 3)
		{
			string ss = s;
			ss = replace(ss, "P", to_string(p));
			ss = replace(ss, "Q", to_string(q));
			ss = replace(ss, "R", to_string(r));

			int i = 0;
			if (parse(ss, i) == 2) ans++;
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 3200