akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;
int main()
{
	int k,q,i,d1[5005],d,n,x,m;
	long long sum;
	cin>>k>>q;
	for(int i=0;i<k;i++)
	cin>>d1[i];
	while(q--)
	{
		sum=0;
		cin>>n>>x>>m;
		n--;
		for(i=0;i<k;i++)
		{
			d=d1[i]%m;
			if(d==0) d=m;
			sum+=d;
		}
		sum=sum*(n/k);sum=sum+x%m;
		for(i=0;i<(n%k);i++)
		{
			d=d1[i]%m;
			if(d==0) d=m;
			sum+=d;
		}
		cout<<n-sum/m<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))

def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

for i in range(N-1):
  A[i+1] = gcd(A[i],A[i+1])
  
print(A[-1])
  


Measured memory_bytes: 14252
import numpy as np

N = int(input())

n = N

count = 0

num = 0

while n >= 10:
    n = n / 10
    count = count + 1

if(int(n) != 0):
	n = N - (10 ** count) + 1

for i in range(count + 1):
    if(i % 2 == 1):
        num = num + (0.9 * (10 ** i))

if(count % 2 == 0):
    num = num + n

print(int(num))

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

using namespace std;

int main()
{
    int a,b,c;
    int x;
    cin >> a >> b >> c >> x;

    int ans=0;
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int k=0;k<=c;k++){
                if(x==(i*500+j*100+k*50)) ans++;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
class Notation
  def initialize(index, value)
    @index = index
    @value = value
  end

  def merge?(index, value)
    value == @value + (index - @index)
  end

  def merge(value)
    @last = value
  end

  def to_s
    @last ? "#{@value}-#{@last}" : @value.to_s
  end
end

while n = gets.chomp.to_i
  break if n == 0

  results = []

  list = gets.chomp.split(' ').map(&:to_i)

  now = Notation.new 0, list[0]
  results << now

  list.each_with_index do |value, index|
    next if index == 0
    now.merge value if now.merge? index, value

    if !now.merge?(index, value)
      now = Notation.new index, value
      results << now
    end
  end

  puts results.map(&:to_s).join(' ')

end

Measured memory_bytes: 8664
n = int(input())

if n <600:
    print(8)
elif n <800:
    print(7)
elif n <1000:
    print(6)
elif n <1200:
    print(5)
elif n <1400:
    print(4)
elif n <1600:
    print(3)
elif n <1800:
    print(2)
elif n <2000:
    print(1)

Measured memory_bytes: 9180
#include<bits/stdc++.h>
#include<string>
#include<cctype> 
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
 
int main(){
  string S;
  int i;
  int ans=0;
  cin >> S;
  for(i=1;i<S.size();i++){
    if((S[i-1]=='B' && S[i]=='W') || (S[i-1]=='W' && S[i]=='B')){
      ans+=1;
    }
  }
  cout << ans << endl;

  return 0;
} 



Measured memory_bytes: 512
#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int K, N;
vector<int>res;

int main() {
	cin >> K >> N;
	if (K & 1) {
		for (int i = 0; i < N; ++i) {
			res.push_back(K / 2 + 1);
		}
		for (int i = 0; i < N / 2; ++i) {
			if (res.size() != N) {
				--res.back();
				if (!res.back()) {
					res.pop_back();
				}
				else {
					while (res.size() != N) {
						res.push_back(K);
					}
				}
			}
			else {
				--res.back();
				if (!res.back()) {
					res.pop_back();
				}
			}
		}
		for (int i : res) {
			cout << i << sp;
		}
		cout << endl;
	}
	else {
		cout << K / 2 << sp;
		for (int i = 1; i < N; ++i) {
			cout << K << sp;
		}
		cout << endl;
	}
}

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

using namespace std;

int lcs(string X,string Y){
	int m = X.size();
	int n = Y.size();
	int maxi = 0; 
	int C[1001][1001];
	X = ' ' + X;
	Y = ' ' + Y;
	for(int i = 1;i <= m;i++) C[i][0] = 0;
	for(int i = 1;i <= n;i++) C[0][i] = 0;
	for(int i = 1;i <= m;i++){
		for(int j = 1;j <= n;j++){
			if(X[i] == Y[j]){
				C[i][j] = C[i-1][j-1] + 1;
			}else{
				C[i][j] = max(C[i-1][j],C[i][j-1]);
			}
			maxi = max(maxi,C[i][j]);
		}
	}
	return maxi;
}

int main(){
	int n;
	cin >> n;
	string x,y;
	for(int i = 0 ;i < n;i++){
		cin >> x >> y;
		cout << lcs(x,y) << endl;;
	}
	return 0;
}

Measured memory_bytes: 5128
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <complex>

#define FOR(i,b,n) for(int i=b;i<n;i++)
#define RFOR(i,b,n) for(int i=n-1;i>=b;i--)
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define NCLR(mat) memset(mat, -1, sizeof(mat))
#define EPS 1e-15

using namespace std;

typedef complex<double> point;
typedef pair<int, int> paii;
typedef long long ll;

double dot(point va, point vb){
	return real(va) * real(vb) + imag(va) * imag(vb);
}

bool is_orthogonal(point a, point b, point c, point d)
{
	return abs(dot(b-a, d-c)) < EPS;
}

int main()
{
	point pt[4];
	
	while( cin >> pt[0].real() >> pt[0].imag() >> pt[1].real() >> pt[1].imag() >>
			pt[2].real() >> pt[2].imag() >> pt[3].real() >> pt[3].imag(), !cin.eof())
	{
		cout << (is_orthogonal(pt[0], pt[1], pt[2], pt[3]) ? "YES" : "NO") << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1216
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define pb push_back
#define pf pop_front
#define mp make_pair
#define mod 1000000007
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mat vector<vector<int>>
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define fo(i,n) for(int i=0;i<n;i++)
#define inp(a) int a;cin>>a;
#define inpa(a,n)vector<int> a(n);fo(i,n)cin>>a[i];
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
using namespace std;
#define int ll


auto max(auto a){auto ans=a[0];for(auto i:a)if(i>ans)ans=i;return ans;}
auto min(auto a){auto ans=a[0];for(auto i:a)if(i<ans)ans=i;return ans;}
void print(auto a){for(auto i:a)cerr<<i<<' ';cerr<<'\n';}

int dp[400][400];
int n;
vector<int> a,cum;

int fdp(int l,int r)
{
	if(l==r)
		return 0;
	if(dp[l][r]!=-1)
		return dp[l][r];
	int ans=1e18;
	for(int k=l;k<r;k++)
		ans=min(ans,fdp(l,k)+fdp(k+1,r)+cum[r+1]-cum[l]);
	dp[l][r]=ans;
	return ans;
}


signed main()
{
	fio
	cin>>n;
	a.resize(n);
	cum.resize(n+1);
	fo(i,n)
		cin>>a[i];
	cum[0]=9;
	fo(i,n)
		cum[i+1]=cum[i]+a[i];
	memset(dp,-1,sizeof(dp));
	cout<<fdp(0,n-1)<<'\n';
	printclock;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define all(v) (v).begin(), (v).end()
using ll = long long;
using P = pair<int, int>;
/* ------------------------------------------------ */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i;
}
ll gcd(ll a, ll b) {        //最大公約数
    if(b == 0) return a;
    return gcd(b, a % b); 
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
int keta(ll n) {        //桁数を求める
    if(n == 0) return 1;
    int count = 0;
    while(n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}
/* ------------------------------------------------ */
int main() {
    ll a;
    string b;
    cin >> a >> b;
    int B = ctoi(b[0]) * 100 + ctoi(b[2]) * 10 + ctoi(b[3]);
    // cout << b[0] << b[1] << b[2] << b[3] << endl;
    // cout << B << endl;
    
    cout << a * B / 100 << endl;
    return 0;
}

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

for i in range(n):
    if s[i]==')':
        s[i]=1
    else:
        s[i]=-1

ans=0
v=[]
for i in range(n):
    ans+=s[i]
    if ans>0:
        v.append(-1)
        ans-=1
s=v+s
if ans<0:
    for i in range(abs(ans)):
        s.append(1)
for i in range(len(s)):
    if s[i]==-1:
        s[i]='('
    else:
        s[i]=')'
print(''.join(s))
            
            
            
    
        

        
    


Measured memory_bytes: 38384
#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 MOD 1000000007

typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
  int N;
  string S;
  cin >> N;
  cin >> S;

  int dp[N][N+1];
  dp[N-1][N] = 0;

  REP(i,N)REP(j,N+1){
    dp[i][j]=0;
  }

  int ans=0;
  for(int j = N-1; j > 1; j--){
    for(int i = j - 1; i >= 0; i--){
      if(S[i] == S[j]){
        dp[i][j] = min(j-i,dp[i+1][j+1] + 1);
      }else{
        dp[i][j] = 0;
      }
      ans = max(ans,dp[i][j]);
    }
  }

  // REP(i,N)REP(j,N+1){
  //   cout << i << " : " << j << " = " << dp[i][j] << endl;
  // }
  cout << ans << endl;
}



Measured memory_bytes: 97920
#include<bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
int main(){
  string s,t;cin >> s >> t;
  int n = s.size(),m = t.size(),i,j,ans = 10000,now;
  for(i=0;i<=n-m;i++){
    now = 0;
    for(j=0;j<m;j++) now += s[i+j] != t[j];
    ans = min(ans,now);
  }
  cout << ans << "\n";
}

Measured memory_bytes: 3628
X,Y=map(int,input().split())
if (X+Y)%3!=0:
    print(0)
    exit()
mod=10**9+7
N=(X+Y)//3
'''
k*(1,2)+(n-k)*(2,1)=(x,y)
(k+2n-2k,2k+n-k)=(x,y)
(2n-k,n+k)=(x,y)
2y=2n+2k
x=2n-k
2y-x=3k
'''
K=(2*Y-X)//3
if not(0<=K<=N):
    print(0)
    exit()
ans=1
for i in range(1,K+1):
    ans*=(N+1-i)*pow(i,mod-2,mod)
    ans%=mod
print(ans)


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
vector<int> a;
int main()
{
	int n;
	scanf("%d",&n);
	a.resize(n + 2);
	a[0] = 0;
	a[n + 1] = 0;
	int total = 0;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d",&a[i]);
		total +=fabs(a[i] - a[i - 1]);
	}
	total+= fabs(a[n] - a[0]);
	for (int i = 1; i <= n; i++)
	{
		int s = total -fabs(a[i]-a[i-1]) - fabs(a[i]-a[i + 1]) + fabs(a[i - 1] - a[i + 1]);
		printf("%d\n",s);
	}
	return 0;
}

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

int main(void){
  int N;
  cin >> N;
  
  vector<int> A(N);
  for(int i = 0;i<N;i++){
    cin >> A[i];
  }
  int M = 1000005;
  vector<int> cnt(M);
  for(int x : A){
    if(cnt[x] != 0){
      cnt[x] =2;
      continue;
    }
    for(int i=x;i<M;i+=x){
      cnt[i]++;
    }
  }
  int ans = 0;
  for(int x : A){
    if(cnt[x]==1)ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 7992
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String x = br.readLine();
		String[] cut = x.split(" ");
		int a = Integer.parseInt(cut[0]);
		int b = Integer.parseInt(cut[2]);

		System.out.println(cut[1].equals("+") ? a + b : a - b);
	}
}

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

int main() {
  int n;
  cin >> n;
  vector<int> t(n);
  rep(i, n) cin >> t[i];
  int m;
  cin >> m;
  vector<int> p(m), x(m);
  rep(i, m) cin >> p[i] >> x[i];

  int sum = 0;
  rep(i, n) sum += t[i];
  rep(i, m) cout << sum - t[p[i] - 1] + x[i] << endl;


  
  return 0;
}

Measured memory_bytes: 256
a,b,c=gets.split.map &:to_i


1000.times{|x|
  if( a%2+b%2+c%2 > 0 )
    puts x
    exit(0)
  end
  i=b/2+c/2
  j=c/2+a/2
  k=a/2+b/2
  a=i
  b=j
  c=k
}
puts -1


Measured memory_bytes: 1788
//#include "bits/stdc++.h"

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

const int MAX = 210000;

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

	int n;
	cin >> n;
	cout << 1110 - n << endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int a, b;
	
	scanf("%d %d",&a, &b);

	if(a > b)
	{
		printf("a > b\n");
	}
	
	if(a < b)
	{
		printf("a < b\n");
	}
	
	if(a == b)
	{
		printf("a == b\n");
	}
	return 0;
}

Measured memory_bytes: 580
#include<bits/stdc++.h>
#include <algorithm>
#include <cctype>
#include <iostream>
#include <string>
using namespace std;

#define ll long long
#define rep(i,n) for(int (i)=0; (i)<(n); (i)++)

const ll MOD = 1e9+7;

// Combinationの使い方
// vector<vector<ll>> v(N+1, vector<ll>(N+1, 0));
// comb(v);
void comb(vector<vector<ll>> &v){
    for(int i = 0; i < v.size(); i++){
        v[i][0] = 1;
        v[i][i] = 1;
    }
    for(int k = 1; k < v.size(); k++){
        for(int j = 1; j < k; j++){
            v[k][j] = (v[k-1][j-1] + v[k-1][j]);
            //余りを求める問題は毎回計算ごとにやる
            // v[k][j] = (v[k-1][j-1] + v[k-1][j]) % MOD;
        }
    }
}

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

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

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

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

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

// vector<tuple<long,long>> items; // (value, weight)
// auto item = items[i];
// long v = get<0>(item);
// long w = get<1>(item);
// long v, w;
//   for( int i = 0; i < N; i++ ){
//     cin >> v >> w;
//     items.push_back( make_tuple(v, w) ); // item : (value, weight)
//   }

// 1 << 3 : int "3" change to bit "100"
// rep(pattern, 1 << N) if (pattern & (1 << x)) cnt++

// 過去問第3問ABC113Bまでdone

int main(){
    int D, G;
    cin >> D >> G;
    vector<int> p(11,0);
    vector<int> c(11,0);
    rep(i,D) cin >> p[i] >> c[i];

    int min_solve = 10000007;
    for(int bit=0; bit<(1<<D); bit++){
        int score = 0;
        int solve = 0;
        int rest_i = -1;

        rep(i,D){
            if(bit&(1<<i)){
                score += (100*(i+1)) * p[i] + c[i];
                solve += p[i];
            }else{
                rest_i = i;
            }
        }

        if(score >= G){
            if(solve < min_solve) min_solve = solve;
        }
        else{
            int rest_add_num = 0;
            while(true){
                if(score >= G) break;
                score += (100*(rest_i+1));
                solve++;
                rest_add_num++;
            }
            if(solve < min_solve && rest_add_num <= p[rest_i]) min_solve = solve;
        }
    }
    cout << min_solve << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
using namespace std;
int number_min(int digit, int max, int s[], int c[])
{
    double sum = 0;
    int digit_max = -1;

    if (digit == 1 && max == 0)
    {
        return 0;
    }
    if (digit > 1 && max == 0)
    {
        return sum += pow(10, digit - 1);
    }
    for (int j = 0; j < max; j++)
    {
        if (digit > 1 && s[j] == 1 && c[j] == 0)
        {
            return -1;
        }
        else if (s[j] == 1)
        {
            digit_max = 0;
        }
    }
    for (int i = 1; i <= digit; i++)
    {
        for (int j = 0; j < max; j++)
        {
            if (s[j] == i)
            {
                sum += c[j] * pow(10, digit - i);
                for (int k = j + 1; k < max; k++)
                {
                    if (s[k] == i && c[k] != c[j])
                    {
                        return -1;
                    }
                }
                break;
            }
        }
    }
    if (digit_max == -1)
    {
        sum += pow(10, digit - 1);
    }
    return sum;
}
int main()
{
    int digit;
    int max;
    cin >> digit >> max;
    int s[max], c[max];
    for (int i = 0; i < max; i++)
    {
        cin >> s[i] >> c[i];
    }
    cout << number_min(digit, max, s, c) << endl;
    return 0;
}

Measured memory_bytes: 256
N, M = list(map(int, input().split()))
abc = [list(map(int, input().split())) for _ in range(M)]

inf = 1000000
L = [[0] * N for _ in range(N)]
C = [[inf] * N for _ in range(N)]
for i in range(M):
  a, b, c = abc[i]
  a -= 1
  b -= 1
  C[a][b] = c
  C[b][a] = c

for i in range(N):
  C[i][i] = 0

for k in range(N):
  for i in range(N):
    for j in range(N):
      if C[i][j] > C[i][k] + C[k][j]:
        C[i][j] = C[i][k] + C[k][j]
        L[i][j] = 1

n = 0
for i in range(N):
  for j in range(N):
    if L[i][j] == 1:
      n += 1

print(M - ((N * (N - 1) // 2) - (n // 2)))


Measured memory_bytes: 42476
/*author* Priyanshu Shrivastav (from IIT Palakkad) *
 * *_ __ ___  _ ______ ___  _ ____   ___  ___| |_  *
 * | '_ ` _ \| '__/ __/ _ \| '_ \ \ / / |/ __| __| *
 * | | | | | | | | (_| (_) | | | \ V /| | (__| |_  *
 * |_| |_| |_|_|(_)___\___/|_| |_|\_/ |_|\___|\__| *
When I wrote this, only God and I understood what I was doing
 ** * * * * * * * Now, only God knows * * * * * * */
#include         <bits/stdc++.h>
using namespace std;
#pragma GCC      optimize ("Ofast")
#pragma GCC      optimize ("unroll-loops")
#pragma GCC      target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define IOS      ios_base::sync_with_stdio(false); cin.tie (nullptr)
#define PREC     cout.precision (10); cout << fixed
#define bg(x)    " [ " << #x << " : " << (x) << " ] "
#define x        first
#define y        second
using ll = long long;
using ff = long double;
using pii = pair<int,int>;

#define debug(args...) { \
/* WARNING : do NOT compile this debug func calls with following flags: // \
 * // -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -D_FORTIFY_SOURCE=2*/ \
   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) { it->empty();
   cerr << " (Line : " << __LINE__ << ")" << '\n';
}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << fixed << setprecision(15) << " [ " <<  *it << " : " << a  << " ] "<< ' ';
	err(++it, args...);
}

const int N = 22, MOD = (int)1e9 + 7;

int dp[N][1 << N];
int ar[N][N];
int n;

inline int add (int a, int b) { return ((a%MOD) + (b%MOD)) % MOD; };

void solve() {
   for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < (1 << n); ++j) {
         dp[i][j] = 0;
      }
   }

   for (int k = 0; k < n; ++k) {
      if (ar[1][k+1]) dp[1][1 << k] = 1;
   }

   for (int i = 2; i <= n; ++i) {
      for (int j = 0; j < (1 << n); ++j) {
         if (__builtin_popcount(j) != i) continue;
         for (int k = 0; k < n; ++k) {
            if (ar[i][k+1]) dp[i][j] = add(dp[i][j], dp[i-1][j - (1 << k)]);
         }
      }
   }
   int total = dp[n][(1 << n)-1];
   cout << total << '\n';
}

signed main() {
   IOS; PREC;
   cin >> n;
   for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
         cin >> ar[i][j];
   solve();

   return EXIT_SUCCESS;
}




Measured memory_bytes: 215296
function Main(input) {
  input=input.split("\n");
  if(input[input.length-1]===''){
    input.pop();
  }
  const A=input[0].split(' ')[0]-0;
  const B=input[0].split(' ')[1]-0;
  if(A<=9&&B<=9){
    console.log(A*B);
  }else{
    console.log(-1);
  }

}




//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

int main() {
    
    int a[3], c5=0, c7=0;
    for(int i=0; i<3; i++){
        cin >> a[i];
        if(a[i]==5) ++c5;
        else if(a[i]==7) ++c7;
    }
    if(c5==2 && c7==1) cout << "YES" << endl;
    else cout << "NO" << endl;

    
    
	return 0;
}

Measured memory_bytes: 3468
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        String S = sc.next();
        int sl = S.length();
        if(K >= sl){
            System.out.print(S);
        }else{
            for(int i = 0;i < K; i++){
                System.out.print(S.charAt(i));
            }
            System.out.print("...");
        }
    }
}

Measured memory_bytes: 27092
#include<stdio.h>
#include<string.h>
int a[13],vis[13],flag;
void dfs(int x,int l,int r)
{
    int i;
    if(x==11)return; 
    if(flag)return ;
    if(a[x]>l)dfs(x+1,a[x],r);
    else  if(a[x]>r)dfs(x+1,l,a[x]);
    else  {flag=1;return;}
}
int main()
{
int T,i,j,k;
scanf("%d",&T);
while(T--)
{
flag=0;
for(i=1;i<=10;i++)
scanf("%d",&a[i]);
memset(vis,0,sizeof(vis));
dfs(1,0,0);
if(flag)printf("NO\n");
else printf("YES\n");
}
return 0;
}

Measured memory_bytes: 1004
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		double[] stack = new double[40];
		int sp = 0;
		double a;
		double b;
		while(scan.hasNext()){
			sp = 0;
			String[] str = scan.nextLine().split(" ");
			for(int i = 0;i < str.length;i++){
				if(str[i].equals("+")){
					a = stack[--sp];
					b = stack[--sp];
					stack[sp++] = a + b;
				}else if(str[i].equals("-")){
					a = stack[--sp];
					b = stack[--sp];
					stack[sp++] = b - a;
				}else if(str[i].equals("*")){
					a = stack[--sp];
					b = stack[--sp];
					stack[sp++] = a * b;
				}else if(str[i].equals("/")){
					a = stack[--sp];
					b = stack[--sp];
					stack[sp++] = b / a;
				}else{
					stack[sp++] = Double.parseDouble(str[i]);
				}
			}
			System.out.printf("%.6f\n",stack[0]);
		}
	}
}

Measured memory_bytes: 17200
N = int(raw_input())
h = map(int, raw_input().split())

dp = [0] * N
dp[1] = abs(h[1] - h[0])
for i in range(2, N):
	dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]))

print(dp[-1])


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

public class Main{

	static int []a;
	static long f(int v) {
		long ans=0;
		for(int i=1;i<=a.length;i++) {
			ans+=Math.abs(a[i-1]-(v+i));
		}
		return ans;
	}
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner();
		PrintWriter out=new PrintWriter(System.out);
		int n=sc.nextInt();
		a=new int [n];
		for(int i=0;i<n;i++)
			a[i]=sc.nextInt();
		
		int lo=-(int)1e9,hi=(int)1e9;
		while(hi-lo>=3) {
			int p1=lo+(hi-lo)/3;
			int p2=hi-(hi-lo)/3;
			long v1=f(p1),v2=f(p2);
			if(v2>v1)
				hi=p2;
			else
				lo=p1;
			
		}
		long ans=(long)(1e18);
		for(int i=lo;i<=hi;i++) {
			ans=Math.min(f(i),ans);
		}
		out.println(ans);
		
		out.close();
	}
	
	static class Scanner
	{
		BufferedReader br;
		StringTokenizer st;
		Scanner(){
			br=new BufferedReader(new InputStreamReader(System.in));
		}
		Scanner(String fileName) throws FileNotFoundException{
			br=new BufferedReader(new FileReader(fileName));
		}
		String next() throws IOException {
			while(st==null || !st.hasMoreTokens())
				st=new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		String nextLine() throws IOException {
			return br.readLine();
		}
		int nextInt() throws IOException{
			return Integer.parseInt(next());
		}
		long nextLong()  throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}
		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}
	}
}

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

using namespace std;

#define PI 3.14159265358979323846264338327950L

int main(void){

    int N,K;
    double tmp2;
    long long tmp;


    cin>>N>>K;

    vector<long long> A(N+5,0),value(N+5,0);

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

    tmp=1;
    for(int i=0;i<K;i++){
        tmp=tmp*A[i];
    }
    // value[K]=tmp;
    // for(int i=K;i<N;i++){
    //     tmp=tmp*A[i];
    //     value[i]=tmp;
    // }

    for(int i=0;i<N-K;i++){
        tmp2=(double)A[i+K]/A[i];
        if(tmp2 > 1){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }


    return 0;
}



Measured memory_bytes: 6420
n = gets.to_i

red = []
n.times {red << gets.split.map(&:to_i)}
red.sort!{|a,b| a[0] <=> b[0]}

blue = []
n.times {blue << gets.split.map(&:to_i)}
blue.sort!{|a,b| a[0] <=> b[0]}

j = 0
ans = 0
while j < n
    i = 0
    index = -1
    s = red.size
    while i < s && red[i][0] < blue[j][0]
        if red[i][1] < blue[j][1] && (index == -1 || red[index][1] < red[i][1])
            index = i
        end
        i += 1
    end
    j += 1
    next if index == -1
    ans += 1
    red.delete_at(index)
end

puts ans

Measured memory_bytes: 1788
#include<iostream>
using namespace std;
const int INF=1e9;

int abs(int n){
  if(n>=0)return n;
  else return -n;
}

int min(int a,int b){
  if(a<=b)return a;
  else return b;
}

main(){
  int N;
  cin >> N;
  int h[N];
  for(int ii=0;ii<N;ii++){
    cin >> h[ii];
  }
  int dp[N];//初期化
  for(int ii=0;ii<N;ii++){
    dp[ii]=INF;
  }
  dp[0]=0;
  for(int ii=0;ii<N-2;ii++){
    dp[ii+1]=min(dp[ii+1],dp[ii]+abs(h[ii+1]-h[ii]));
    dp[ii+2]=min(dp[ii+2],dp[ii]+abs(h[ii+2]-h[ii]));
    /*    for(int ii=0;ii<N;ii++){
      cout << dp[ii] << endl;
    }
    cout << endl;*/
  }
  int ii=N-2;
  dp[ii+1]=min(dp[ii+1],dp[ii]+abs(h[ii+1]-h[ii]));  
  /*  for(int ii=0;ii<N-1;ii++){
    dp[ii+1]=min(dp[ii+1],dp[ii]+abs(h[ii+1]-h[ii]));
    }*/
  cout << dp[N-1] << endl;
}


Measured memory_bytes: 1024
from fractions import gcd
from math import ceil
def div(n,a,b):
    m = b//n-(a-1)//n
    #print(m)
    return max(m,0)
a,b,c,d = map(int,input().split())
e = c*d//gcd(c,d)
print(b-a+1-(div(c,a,b) + div(d,a,b) - div(e,a,b)))

Measured memory_bytes: 5048
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;

void solve() {
    int a, b, t; cin >> a >> b >> t;
    int count = 0;
    while(true){
        if(a*count > t) break;
        else count++;
    }
    cout << b*(count-1) << endl;
}

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

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

using namespace std;

int main() {
  int A, B;
  cin >> A >> B;
  
  int a = A + B;
  
  int b = A - B;
  
  int c = A * B;
  
  if (a > b && a > c) {
    cout << a << endl;
  }
  else if (b > a && b > c) {
    cout << b << endl;
  }
  else if (c > a && c > b) {
    cout << c << endl;
  }
  else if (a == b) {
    cout << a << endl;
  }
  else if (a == c) {
    cout << a << endl;
  }
  else if (b == c) {
    cout << b << endl;
  }
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();		
        int b = 0;
        int c;
        int [][] in = new int [10][10];
        for(int i=1;i<=a;i++){if(i<10){c=i;}else{if(i<100){c=i/10;}
                                                else{if(i<1000){c=i/100;}
                                                    else{if(i<10000){c=i/1000;}
                                                        else{if(i<100000){c=i/10000;}
                                                            else{c=i/100000;}}}}}                                     
        in[c][i%10]++;}
        for(int i=0;i<=9;i++){
        for(int j=0;j<=9;j++){b+=in[i][j]*in[j][i];}}
		System.out.println(b);
	}
}


Measured memory_bytes: 21972
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <string>

using namespace std;

int main(){
    int N,K;
    scanf("%d %d", &N, &K);
    int ret = (K > 1)?N-K : 0;
    printf("%d\r\n", ret);
    fflush(stdout);
    return 0;
}

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

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

    for(int i=0; i<n; i++){
        int a;
        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;

const int inf = 1e9;

int main(int argc, char *argv[]) {
  string s, t;
  cin >> s >> t;
  auto cal = [](string s, string t) {
    int n = s.size();
    bool flag = false;
    for (auto c : t) {
      if (c == '1') {
        flag = true;
      }
    }
    if (!flag) {
      return (s == t ? 0 : -1);
      return 0;
    }
    vector<int> L(n), R(n);
    for (int i = 0; i < n; i++) {
      for (int j = i; t[j] != '1'; j = (j + 1) % n, R[i]++);
      for (int j = i; t[j] != '1'; j = (j + n - 1) % n, L[i]++);
    }
    int ans = inf;
    for (int i = 0; i < n; i++) {
      vector<pair<int, int>> vec;
      for (int j = 0; j < n; j++) {
        if (s[(j - i + n) % n] != t[j]) {
          vec.push_back({max(0, L[j] - i), R[j]});
        }
      }
      sort(vec.begin(), vec.end());
      if (vec.empty()) {
        ans = min(ans, i);
        continue;
      }
      if (i == 1) {
        for (auto e : vec) {
          //            cout << e.first << " " << e.second << endl;
        }
      }
      vector<int> mx(vec.size() + 1);
      for (int j = (int)vec.size() - 1; j >= 0; j--) {
        mx[j] = max(mx[j + 1], vec[j].second);
      }
      ans = min(ans, i + 2 * mx[0] + (int)vec.size());
      //      cout << i << " " << ans << endl;
      for (int j = 0; j < (int)vec.size(); j++) {
        ans = min(ans, i + vec[j].first * 2 + mx[j + 1] * 2 + (int)vec.size());
      }
      //      cout << i << " " << ans << endl;
    }
    return ans;
  };
  int ans = cal(s, t);
  //  cout << ans << endl;
  //int ans = 22;
  reverse(s.begin(), s.end());
  reverse(t.begin(), t.end());
  ans = min(ans, cal(s, t));
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 384
N, K = map(int, input().split())
D = {}
for _ in range(N):
    a, b = map(int, input().split())
    if a in D:
        D[a] += b
    else:
        D[a] = b

cnt = 0
for i in sorted(D.keys()):
    cnt += D[i]
    if cnt >= K:
        print(i)
        exit()

Measured memory_bytes: 10588
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
void solve()
{
    ll r,n,a,b;
    cin>>n>>a>>b;
    cout<<((n)/(a+b))*a+min(a,n%(a+b))<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //int _t;cin>>_t;while(_t--)
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#define N 200010
#define ll long long
using namespace std;
ll C[N][3],T[N<<1],t[N],tot,cnt,n,k,Ans;

void Run_yh() {
	C[1][1]=1;
	for (int i=2; i<=N; i++) {
		C[i][1]=i;
		C[i][2]=C[i-1][1]+C[i-1][2];
	}
	//cout<<C[N][2]<<endl;
}

int Lower_b(int x) {
	int l=1,r=cnt,ans=0;
	while (l<=r) {
		int mid=(l+r)>>1;
		if (T[mid]<=x) {
			l=mid+1;
			ans=mid;
		}
		else r=mid-1;
	}
	return ans;
}

int Upper_b(int x) {
	int l=1,r=cnt,ans=0;
	while (l<=r) {
		int mid=(l+r)>>1;
		if (T[mid]>=x) {
			r=mid-1;
			ans=mid;
		}
		else l=mid+1;
	}
	return ans;
}

int main() {
	Run_yh();
	scanf("%lld%lld",&n,&k);
	int Base=k;
	while (Base<=2*n) {
		T[++cnt]=Base;
		if (Base%2==0)  t[++tot]=Base/2;
		Base+=k; 
	}
	for (int i=1; i<=tot; i++) {
		int p1=Upper_b(t[i]+1),p2=Lower_b(n+t[i]);
		//cout<<i<<" "<<p1<<" "<<p2<<" "<<C[p2-p1+1][2]<<" "<<endl;
		Ans+=(C[p2-p1+1][2]*2+p2-p1+1);
	}
	printf("%lld",Ans);
}


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

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

class E{
public:
	int from,to,cost;

	E(int _from,int _to,int _cost){
		from = _from;
		to = _to;
		cost = _cost;
	}

	bool operator<(const E &e)const{
		return cost < e.cost;
	}

	void show(void){
		cout<<"["<<from<<"->"<<to<<" : "<<cost<<"]"<<endl;
	}
};

int n,m;
vector<E> es;

int par[102];
int rank[102];

void init(void){
	rep(i,102){
		par[i] = i;
		rank[i] = 0;
	}
}

int find(int x){
	if(par[x] == x){
		return x;
	} else{
		return par[x] = find(par[x]);
	}
}

void unite(int x,int y){
	x = find(x);
	y = find(y);
	if(x == y) return;

	if(rank[x] < rank[y]){
		par[x] = y;
	} else{
		par[y] = x;
		if(rank[x] == rank[y]) rank[x]++;
	}
}

bool same(int x,int y){
	return find(x) == find(y);
}

int kruskal(void){
	sort(es.begin(),es.end());
	init();
	int res = 0;

	rep(i,es.size()){
		E e = es[i];

		if(!same(e.from,e.to)){
			bool flg1=false, flg2=false;
			rep(j,n){
				if(!flg1 && same(j,e.from)){
					flg1 = true;
				}
				if(!flg2 && same(j,e.to)){
					flg2 = true;
				}
			}

			if(!flg1 || !flg2){
				unite(e.from,e.to);
				res += e.cost;
			}
		}
	}
	return res;
}

int main(void){
	while(cin>>n>>m,n){
		es.clear();
		rep(i,n) rep(j,m) {
			int x;
			cin>>x;
			if(x != 0){
				es.push_back(E(i,n+j,x));
			}
		}
		rep(i,m-1) rep(j,m-i-1) {
			int x;
			cin>>x;
			if(x != 0){
				es.push_back(E(n+i,n+i+j+1,x));
			}
		}

		cout<<kruskal()<<endl;
	}

	return 0;
}

Measured memory_bytes: 0
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;
constexpr double pi = acos(-1);
constexpr double EPS = 1e-10;

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

class SegmentTree{
public:
    int n;
    vector<ll> node;

    // Range Minumum Query
    SegmentTree(vector<ll> v){
        int sz = v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, INF);
        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = min(node[2*i+1], node[2*i+2]);
    }

    void update(int x, ll val){
        x += (n - 1);
        node[x] = val;
        while(0 < x){
            x = (x - 1) / 2;
            node[x] = min(node[2*x+1], node[2*x+2]);
        }
    }

    ll getmin(int a, int b, int k=0, int l=0, int r=-1){
        if(r < 0) r = n;
        if(r <= a || b <= l) return INF;
        if(a <= l && r <= b) return node[k];

        ll vl = getmin(a, b, 2*k+1, l, (l+r)/2);
        ll vr = getmin(a, b, 2*k+2, (l+r)/2, r);
        
        return min(vl, vr);
    }
};

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

    int n, q; cin>>n>>q;
    vector<ll> a(n, (1LL<<31)-1);
    SegmentTree seg(a);

    while(q--){
        int c, x, y; cin>>c>>x>>y;
        if(c == 0) seg.update(x, y);
        else cout << seg.getmin(x, y + 1) << endl;
    }

    return 0;
}


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

int cnt[10];
char s[100];

int main() {
    int n;
    scanf("%d",&n);
    for (; n--;) {
        scanf("%s",s);
        if (s[0] == 'M')
            cnt[0]++;
        else
            if (s[0] == 'A')
                cnt[1]++;
            else
                if (s[0] == 'R')
                    cnt[2]++;
                else
                    if (s[0] == 'C')
                        cnt[3]++;
                    else
                        if (s[0] == 'H')
                            cnt[4]++;
    }
    long long ans = 0;
    for (int i = 0; i < 5; i++)
        for (int j = i + 1; j < 5; j++)
            for (int k = j + 1; k < 5; k++)
                if (cnt[i] && cnt[j] && cnt[k])
                    ans += (long long)cnt[i] * cnt[j] * cnt[k];
    printf("%lld\n",ans);
    return 0;
}


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

signed main(){
    ios::sync_with_stdio(false);
    int n , k;

    cin >> n >> k;
    int a[n];
    for(int i =0;i<n;i++){
        cin >> a[i];
       
    }
    sort(a,a+n,greater<>());
   
    int e=0;
    while(e<n&&a[e]>=k)e++;
    if(e==n)cout << 0;
    else{
    int b[n-e];
    int c[n-e];
    c[n-e-1]=0;
    
    for(int i= n-e-2;i>=0;i--){c[i]=c[i+1]+a[i+e+1];}
   int t;
   int mine = e-1;
    for(int i=e;i<n;i++){
        t=a[i];
        for(int j=e;j<i;j++){
            
            if(b[j-e]+a[i]<k&&t<b[j-e]+a[i])t =b[j-e]+a[i];
            

        }
        b[i-e]=t;
        //cout << t<<' ';

    }
    int ans=0;
    int u=0;
    if(b[0]+c[0]<k){
        u=1;
        ans++;
    }

     //cout << b[0]<<' '<< c[0]<< ' '<<ans<<endl;
    for(int i=1;i<n-e;i++){
        if(a[i-1+e]==a[i+e]){
            if(u==1)ans++;
        }else{
            if(b[i-1]+a[i+e]+c[i]<k){
                ans++;
                u=1;
            }else{
                u=0;
            }
        }
        
       // cout << b[i-1]<<' '<<a[i+e]<<' '<< c[i]<<' '<<ans<< endl;

    }
    cout << ans;
    }
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#define INF 1000000009
#define LINF 1000000000000000009
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
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 (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }

int pcnt(int n) {
	int ans = 0;
	for (int i = 0; i < 20; i++) {
		if ((1 << i)&n) ans ^= 1;
	}
	return ans;
}

vector<vector<int>> graph;
vector<vector<int>> st;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n - 1), b(n - 1);
	graph.assign(n, vector<int>());
	vector<vector<int>> dis(n, vector<int>(n, INF));
	for (int i = 0; i < n; i++) dis[i][i] = 0;
	map<P, int> mp;
	for (int i = 0; i < n - 1; i++) {
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
		graph[a[i]].push_back(b[i]);
		graph[b[i]].push_back(a[i]);
		dis[a[i]][b[i]] = 1;
		dis[b[i]][a[i]] = 1;
		mp[{a[i], b[i]}] = i;
		mp[{b[i], a[i]}] = i;
	}
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				chmin(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
	/*for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (dis[i][j] == INF) cout << "INF" << ' ';
			else cout << dis[i][j] << ' ';
		}
		cout << endl;
	}*/
	int m;
	cin >> m;
	vector<int> u(m), v(m);
	st.assign(m, vector<int>());
	for (int i = 0; i < m; i++) {
		cin >> u[i] >> v[i];
		u[i]--; v[i]--;
		int np = u[i];
		while (np != v[i]) {
			for (int j : graph[np]) {
				if (dis[j][v[i]] < dis[np][v[i]]) {
					st[i].push_back(mp[{np, j}]);
					np = j;
					//cout << j << endl;
					continue;
				}
			}
		}
	}
	/*for (int i = 0; i < m; i++) {
		for (int j : st[i]) {
			cout << j << ' ';
		}
		cout << endl;
	}*/
	ll ans = 0;
	int sz = (1 << m);
	ans += (1LL << (n - 1));
	bitset<1100010> pcnts;
	for (int i = 0; i < sz; i++) {
		if (pcnt(i)) pcnts[i] = 1;
	}
	for (int i = 1; i < sz; i++) {
		set<int> sts;
		for (int j = 0; j < m; j++) {
			if (i&(1 << j)) {
				for (int k : st[j]) {
					if (!sts.count(k)) {
						sts.insert(k);
					}
				}
			}
		}
		int nm = sts.size();
		//cout << nm << endl;
		if (!(pcnts[i] & 1)) ans += (1LL << (n - 1 - nm));
		else ans -= (1LL << (n - 1 - nm));
		//cout << dp[i] << endl;
	}
	cout << abs(ans) << endl;
}

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

int main(int argc, char *argv[]) {
    int N, M;
    cin >> N >> M;

    int L[M], R[M];
    for (int i = 0; i < M; i++) { cin >> L[i] >> R[i]; }

    int mi = 0, ma = N;
    for (int i = 0; i < M; ++i) {
        int Li = L[i];
        int Ri = R[i];

        if (Li >= mi) {
            mi = Li;
        }

        if (Ri <= ma) {
            ma = Ri;
        }
    }
    int ret = ma - mi + 1;
    if (ret <= 0) {
        ret = 0;
    }
    cout << ret << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 2000000

struct node {
  int key;
  struct node *next;
  struct node *prev;
};

struct node *head;
struct node *tail;

void insert(int key) {
  struct node *ptr;
  ptr = (struct node*)malloc(sizeof(struct node));
  ptr -> key = key;
  ptr -> next = head -> next;
  ptr -> prev = head;
  head -> next -> prev = ptr;
  head -> next = ptr;
  return;
}

void delete(int key) {
  struct node *ptr, *tmp;
  for (ptr = head; ptr -> next != NULL; ptr = ptr -> next) {
    if (ptr -> next -> key == key) {
      tmp = ptr -> next;
      ptr -> next -> next -> prev = ptr;
      ptr -> next = ptr -> next -> next;
      free(tmp);
      return;
    }
  }
  return;
}

void deleteFirst() {
  struct node *tmp = head -> next;
  head -> next -> next -> prev = head;
  head -> next = head -> next -> next;
  free(tmp);
  return;
}

void deleteLast() {
  struct node *tmp = tail -> prev;
  tail -> prev -> prev -> next = tail;
  tail -> prev = tail -> prev -> prev;
  free(tmp);
  return;
}

int main(){
  
  int i, n, a;
  char str[12];
  struct node *ptr;
  
  head = malloc(sizeof(struct node));
  tail = malloc(sizeof(struct node));
  head -> next = tail;
  head -> prev = NULL;
  tail -> prev = head;
  tail -> next = NULL;
  
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%s", str);
    if (strcmp(str, "insert") == 0) {
      scanf("%d", &a);
      insert(a);
      continue;
    }
    if (strcmp(str, "delete") == 0) {
      scanf("%d", &a);
      delete(a);
      continue;
    }
    if (strcmp(str, "deleteFirst") == 0) {
      deleteFirst();
      continue;
    }
    if (strcmp(str, "deleteLast") == 0) {
      deleteLast();
      continue;
    }
  }
  
  for (ptr = head -> next; ptr -> next -> next != NULL; ptr = ptr -> next) {
    printf("%d ", ptr -> key);
  }
  printf("%d\n", ptr -> key);
  
  return 0;
}



Measured memory_bytes: 33028
#include <bits/stdc++.h>
	using namespace std;
	typedef long long int ll;
	
	#define mod					1000000007
	#define pii                 pair<int,int>
	#define vi                  vector<int>
	#define vii                 vector<std::vector<int>> v;
	#define mem(dp,a)           memset(dp,a,sizeof dp)
	#define sonic               ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	#define pb(x)               push_back(x)
	#define mkp(x,y)             make_pair(x,y)
	#define all(c)              c.begin(), c.end()
	#define ff                  first
	#define ss                  second
	#define INF                 INT_MAX
	
	/* Bit Manipulation */
	
	#define isOn(S, j) (S & (1 << j))
	#define setBit(S, j) (S |= (1 << j))
	#define clearBit(S, j) (S &= ~(1 << j)) // to turn off
	#define toggleBit(S, j) (S ^= (1 << j))
	#define lowBit(S) (S & (-S)) // to get lsb
	#define setAll(S, n) (S = (1 << n) - 1)
	
	#define modulo(S, N) ((S) & (N - 1))   // returns S % N, where N is a power of 2
	#define isPowerOfTwo(S) (!(S & (S - 1)))
	#define nearestPowerOfTwo(S) ((int)pow(2.0, (int)((log((double)S) / log(2.0)) + 0.5)))
	#define turnOffLastBit(S) ((S) & (S - 1))
	#define turnOnLastZero(S) ((S) | (S + 1))
	#define turnOffLastConsecutiveBits(S) ((S) & (S + 1))
	#define turnOnLastConsecutiveZeroes(S) ((S) | (S - 1))
	
	void printSet(int vS) {                         // in binary representation
	  printf("S = %2d = ", vS);
	  stack<int> st;
	  while (vS)
	    st.push(vS % 2), vS /= 2;
	  while (!st.empty())                         // to reverse the print order
	    printf("%d", st.top()), st.pop();
	  printf("\n");
	}
	
	
	bool isValid(string s)
	{
		ll sum = 0;
		for (int i=0,l=s.length();i<l;i++)
		{
			sum += (s[i]-'0');
		}
		return (sum%9 == 0);
	}
	
	
// Main Starts...
	int main()
	{
	    sonic;
		string s;
		cin >> s;
		if (isValid(s))
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	//******Main Ends here****************//
	
	
	


Measured memory_bytes: 3756
#include <stdio.h>
int main(){
  char x[1001];
  int sum,i;
  while(1){
    sum=0;
    scanf("%s",x);
    if(x[0]=='0')break;
    for(i=0;i<1001;i++){
      if(x[i]!='\0')sum+=x[i]-'0';
      else break;
    }
    printf("%d\n",sum);
  }
 
  return 0;
}

Measured memory_bytes: 536
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define repsg(i,s,g) for(int i = s; i <g; i++)
#define name(x) #x
using namespace std;


const int INF = 10000000;
const long long INFL = (1LL<<40);
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}

template< typename T >
struct edge{
    int src, to;T cost;
    edge(int to,T cost) :src(-1),to(to),cost(cost){}
    edge(int src, int to, T cost) :src(src),to(to),cost(cost){}edge
    &operator=(const int &x){
        to =x;
        return *this;
    }
    operator int() const{ return to;}
};


int main() {
    int n;cin>>n;
    set<char> hina;
    rep(i,n){
        char in;cin>>in;
        hina.insert(in);
    }
    if(hina.size()==4)cout<<"Four"<<endl;
    else cout<<"Three"<<endl;
    
    return 0;
}







Measured memory_bytes: 256