akhauriyash/Code-Regression huggingface dataset:
//  ____            _                  _                       _       _
// |  _ \ _   _ ___| |_    ___ _ __   | |_ ___ _ __ ___  _ __ | | __ _| |_ ___
// | |_) | | | / __| __|  / __| '_ \  | __/ _ \ '_ ` _ \| '_ \| |/ _` | __/ _ \
// |  _ <| |_| \__ \ |_  | (__| |_) | | ||  __/ | | | | | |_) | | (_| | ||  __/
// |_| \_\\__,_|___/\__|  \___| .__/___\__\___|_| |_| |_| .__/|_|\__,_|\__\___|
//                            |_| |_____|               |_|

//https://github.com/manta1130/Competitive_Programming_Template_Rust

#[macro_use]
mod input {

    use std;
    use std::io;

    const SPLIT_DELIMITER: char = ' ';

    #[macro_export]
    #[allow(unused_macros)]
    macro_rules! input {
    ( $($x:expr ),*) => {
        {
            let temp_str = input_line_str();
            let mut split_result_iter = temp_str.split_whitespace();
                $(
                let buf_split_result = split_result_iter.next();
                let buf_split_result = buf_split_result.unwrap();
                    ($x) = buf_split_result.parse().unwrap();
                )*
        }
    };
}

    #[allow(dead_code)]
    pub fn input_line_str() -> String {
        let mut s = String::new();
        io::stdin().read_line(&mut s).unwrap();
        s.trim().to_string()
    }

    #[allow(dead_code)]
    pub fn p<T>(t: T)
    where
        T: std::fmt::Display,
    {
        println!("{}", t);
    }

    #[allow(dead_code)]
    pub fn input_vector2d<T>(line: usize) -> Vec<Vec<T>>
    where
        T: std::str::FromStr,
    {
        let mut v: Vec<Vec<T>> = Vec::new();

        for _ in 0..line {
            let vec_line = input_vector();
            v.push(vec_line);
        }
        v
    }

    #[allow(dead_code)]
    pub fn input_vector<T>() -> Vec<T>
    where
        T: std::str::FromStr,
    {
        let mut v: Vec<T> = Vec::new();

        let s = input_line_str();
        let split_result = s.split(SPLIT_DELIMITER);
        for z in split_result {
            let buf = match z.parse() {
                Ok(r) => r,
                Err(_) => panic!("Parse Error"),
            };
            v.push(buf);
        }
        v
    }

    #[allow(dead_code)]
    pub fn input_vector_row<T>(n: usize) -> Vec<T>
    where
        T: std::str::FromStr,
    {
        let mut v = Vec::with_capacity(n);
        for _ in 0..n {
            let buf = match input_line_str().parse() {
                Ok(r) => r,
                Err(_) => panic!("Parse Error"),
            };
            v.push(buf);
        }
        v
    }

    pub trait ToCharVec {
        fn to_charvec(&self) -> Vec<char>;
    }

    impl ToCharVec for String {
        fn to_charvec(&self) -> Vec<char> {
            self.to_string().chars().collect::<Vec<_>>()
        }
    }
}

use input::*;

fn main()
{
    let (a,b,c,d):(usize,usize,usize,usize);
    input!(a,b,c,d);
    println!("{}",std::cmp::max(a*b,c*d));
}



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

const int INF=1001001001;
int N;
int dp[100010];

int main(){
    cin>>N;
    fill_n(dp,N+3,INF);


    for(int i=0;i<N;i++){
        int A;cin>>A;
        *lower_bound(dp,dp+N+3,A)=A;
    }

    cout<<lower_bound(dp,dp+N+3,INF)-dp<<endl;
}

Measured memory_bytes: 1552
#include <bits/stdc++.h>
#define REP(i, a, n) for (int i = (a); i < (int)(n); ++i)
#define REPC(i, a, n) for (int i = (a); i <= (int)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init) \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T>
using VEC = std::vector<T>;
template <class T>
using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail>
void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}
int pgreater(pair<int, int> p1, pair<int, int> p2) {
  return p1.second > p2.second;
}

int main() {
  int n;
  cin >> n;
  VEC<int> v(n);
  REP(i, 0, n) { cin >> v[i]; }
  map<int, int> even, odd;
  REP(i, 0, n) {
    if (i % 2 == 0) {
      ++even[v[i]];
    } else
      ++odd[v[i]];
  }

  auto cmp = [](pair<int,int>p1,pair<int,int>p2){return p1.second<p2.second;};
  priority_queue<pair<int, int>, vector<pair<int, int>>,
                 decltype(cmp)>
      qeven(cmp), qodd(cmp);
  for (auto i : even) {
    qeven.push(i);
  }
  for (auto i : odd) {
    qodd.push(i);
  }
  qeven.push({-1,0});
  qodd.push({-1,0});
  auto max_even1 = qeven.top();
  qeven.pop();
  auto max_even2 = qeven.top();

  auto max_odd1 = qodd.top();
  qodd.pop();
  auto max_odd2 = qodd.top();
  DUMP(max_even1,max_even2,max_odd1,max_odd2);

  if(max_even1.first==max_odd1.first){
    int cand1 = n-max_even1.second-max_odd2.second;
    int cand2 = n-max_even2.second-max_odd1.second;
    cout<<min(cand1,cand2);

  }else{
    cout<<n-max_even1.second-max_odd1.second;

  }
  return 0;
}


Measured memory_bytes: 6520
#include <iostream>

int w, h, dp[101][101][16];

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

// 00: down
// 01: right
// 11: 初期状態用
int rec(int x, int y, int r){
    if(x <= h && y <= w);
    else{
        return 0;
    }

    if(dp[x][y][r] != -1){
        return dp[x][y][r];
    }

    if(x == h && y == w){
        return 1;
    }
    
    int res = 0, first = r >> 2, second = r & 0x3;

    //down
    if(first == second || first != 0x0){
        res = (res + rec(x, y+1, second << 2)) % 100000;
    }


    //right
    if(first == second || first != 0x1){
        res = (res + rec(x+1, y, ((second << 2) | 0x1))) % 100000;
    }


    return dp[x][y][r] = res;
}

int main(){
    while(std::cin >> w >> h, w){
        FOR(i, 1, h+1){
            FOR(j, 1, w+1){
                REP(k, 16){
                    dp[i][j][k] = -1;
                }
            }
        }

        std::cout << rec(1, 1, 0xf) << std::endl;
    }
}

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

int main() {
    int N;
    cin >> N;
    int A[8] = {0};
    int gold = 0;
    for(int i=0; i<N; ++i) {
        int a;
        cin >> a;
        if(a < 3200) A[a / 400] += 1;
        else ++gold;
    }
    int ans = 0;
    for(int i=0; i<8; ++i) {
        if(A[i]) ++ans;
    }
    cout << max(1, ans) << " " << ans + gold << endl;
}

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

#define INF 1e9

int solve(int i,vector <int>& h,vector <int>& dp){
	if(dp[i]>=0) return dp[i];
	int n = h.size();
	if(i>=n){dp[i]=0; return 0; }
	if(i==n-1){dp[i] = 0; return 0; }
	int m = INF;
	if(i+1<n) m=min(abs(h[i]-h[i+1])+solve(i+1,h,dp),m);
	if(i+2<n) m=min(m,abs(h[i]-h[i+2])+solve(i+2,h,dp));
	dp[i]= (m == INF) ? 0 : m;
	return m;
	}
int main(){
	int n;
	cin>>n;
	vector <int> h (n,0);
	for(int i=0;i<n;i++){
		cin>>h[i];
	}
	vector <int> dp (n+2,-1);
	cout<<solve(0,h,dp)<<"\n";
	return 0;
}



Measured memory_bytes: 8832
#include<stdio.h>
int main()
{
    int a;
    scanf("%d",&a);
    char s[10];
    scanf("%s",s);

    if(a<3200)
    {
        printf("red");
    }
    else if(a==3200)
    {
        printf("%s",s);
    }
    else
    {
        printf("%s",s);
    }
    return 0;

}



Measured memory_bytes: 128
a = int(input())
b = list(map(float, input().split()))
c = list(map(float, input().split()))

min = abs(b[1]-b[0] - 0.006*c[0])
minn = 1

for i in range(a):
    if min > abs(b[1]-(b[0] - 0.006*c[i])):
        min = abs(b[1]-(b[0] - 0.006*c[i]))
        minn = i + 1
print(minn)

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

int main(){
  string str;

  cin>>str;
  if(str.size()%2==0&&str[0]==str[str.size()-1]) cout<<"First"<<endl;
  else if(str.size()%2==0||str[0]==str[str.size()-1]) cout<<"Second"<<endl;
  else cout<<"First"<<endl;
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define calc(a, b) ((a) + (b) + min(a, b))
using namespace std;

int n, k;
int x[100010];

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; ++i)
		scanf("%d", &x[i]);
	int ans = 2147483647;
	for (int i = 0; i <= n - k; ++i)
		ans = min(ans, calc(max(-x[i], 0), max(x[i + k - 1], 0)));
	printf("%d\n", ans);
	return 0;
}



Measured memory_bytes: 4092
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
//#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef pair<int,int> Pi;
typedef long long int ll;
const int INF=(ll)(1LL<<31)-1;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int h,w;

char s[55][55];
int d[55][55];
queue<pair<int,int> > q;

void bfs(){
	q.push(pair<int,int>(0,0));
	while(q.size()){
		pair<int,int> p=q.front();q.pop();
		if(p.first+1<h&&s[p.first+1][p.second]=='.'&&d[p.first+1][p.second]==INF){
			d[p.first+1][p.second]=d[p.first][p.second]+1;
			q.push(pair<int,int>(p.first+1,p.second));
		}
		
		if(p.first-1>=0&&s[p.first-1][p.second]=='.'&&d[p.first-1][p.second]==INF){
			d[p.first-1][p.second]=d[p.first][p.second]+1;
			q.push(pair<int,int>(p.first-1,p.second));
		}
		
		if(p.second+1<w&&s[p.first][p.second+1]=='.'&&d[p.first][p.second+1]==INF){
			d[p.first][p.second+1]=d[p.first][p.second]+1;
			q.push(pair<int,int>(p.first,p.second+1));
		}

		if(p.second-1>=0&&s[p.first][p.second-1]=='.'&&d[p.first][p.second-1]==INF){
			d[p.first][p.second-1]=d[p.first][p.second]+1;
			q.push(pair<int,int>(p.first,p.second-1));
		}
	}
}
int main(){
	cin>>h>>w;
	int sum=0;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin>>s[i][j];
			if(s[i][j]=='.')
				sum++;
		}
	}
	for(int i=0;i<55;i++){
		for(int j=0;j<55;j++){
			d[i][j]=INF;
		}
	}
	d[0][0]=0;
	bfs();
	if(d[h-1][w-1]==INF){
		cout<<-1<<endl;
	}else{
	cout<<sum-d[h-1][w-1]-1<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 100010
#define LL long long
#define INF 1000000000
int Adj[MAXN],V[MAXN*2],nxt[MAXN*2],W[MAXN*2],c;
void AddEdge(int u,int v,int w)
{
	c++;V[c]=v,W[c]=w,nxt[c]=Adj[u];Adj[u]=c;
}
int siz[MAXN],mx[MAXN],rt,rt2,n,tmp=INF;
LL ans;
void dfs1(int u,int p)
{
	siz[u]=1;
	for(int i=Adj[u];i;i=nxt[i])
		if(V[i]!=p)
		{
			dfs1(V[i],u);
			siz[u]+=siz[V[i]];
			mx[u]=max(mx[u],siz[V[i]]);
		}
	mx[u]=max(mx[u],n-siz[u]);
	if(mx[u]<=n/2)
	{
		if(rt==0) rt=u;
		else rt2=u;
	}
}
void dfs2(int u,int p,LL dep)
{
	ans+=dep*2;
	for(int i=Adj[u];i;i=nxt[i])
		if(V[i]!=p)
		{
			dfs2(V[i],u,dep+W[i]);
			if(V[i]==rt2||(rt2==0&&u==rt))
				tmp=min(tmp,W[i]);
		}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		AddEdge(u,v,w);
		AddEdge(v,u,w);
	}
	dfs1(1,0);
	dfs2(rt,0,0);
	ans-=tmp;
	printf("%lld\n",ans);
}

Measured memory_bytes: 7680
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>

using namespace std;

int a[234567];

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    if(n%2){
        for(int i=n;i>=1;i--){
            if(i%2) printf("%d ",a[i]);
        }
        for(int i=1;i<=n;i++){
            if(i%2==0) printf("%d ",a[i]);
        }
    } else {
        for(int i=n;i>=1;i--){
            if(i%2==0) printf("%d ",a[i]);
        }
        for(int i=1;i<=n;i++){
            if(i%2) printf("%d ",a[i]);
        }
    }
    return 0;
}

Measured memory_bytes: 2944
N = int(input())
mylist=[]

for i in range(N+1):
    if i==0:
        mylist.append(2)
    elif i==1:
        mylist.append(1)
    else:
        a=0
        a=mylist[-1]+mylist[-2]
        mylist.append(a)
print(mylist[-1])

Measured memory_bytes: 3060
<?php
//https://atcoder.jp/contests/abc051/tasks/abc051_b
fscanf(STDIN,"%d %d",$k, $s);
$count = 0;
for($i=0; $i<=$k; ++$i){
    if(($s-$i)/2 > $k){
        continue;
    }else{
        $start = ($s - $i - $k)<0 ? 0: ($s - $i - $k);
        for($j=$start;$j<=$k;$j++){
            if(($i + $j) > $s){
                break;
            }else{
                //$l = $s - ($i + $j);
                $count++;
            }
        }
    }
}
echo $count;

Measured memory_bytes: 4728
import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

H, W = map(int, input().split())

L, R = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

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

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

L = list(map(int,input().split()))
R = list(map(int,input().split()))

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

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''



N = int(input())

g_sosuu = [] # bool



def eratos(n):
    global g_sosuu

    for i in range(n):
        g_sosuu.append(True)
        
    g_sosuu[0] = False
    g_sosuu[1] = False
    for i in range(2, int(math.sqrt(n)) + 1):
        if g_sosuu[i]:
            for j in range(i*2, n, i):
                g_sosuu[j] = False


eratos(N+10)

sosuu_list = []
for i in range(N+10):
    if g_sosuu[i]:
        sosuu_list.append(i)


ans = 1
count = [0]*1010
for n in range(1, N+1):
    
    for s in sosuu_list:

        for i in range(1, 100):
            if n%(s**i) == 0:
                count[s] += 1
            else:
                break

for c in count[2:]:
    ans *= (c+1)%MOD
    ans %= MOD

print(ans)







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

#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz:" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}

template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
    os << "(" << p.first << "," << p.second
       << ")";
    return os;
}


constexpr ll MOD = (ll)1e9 + 7LL;

template <typename T>
constexpr T INF = numeric_limits<T>::max() / 100;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    int sum = 1900 * M + 100 * (N - M);
    for (int i = 0; i < M; i++) {
        sum *= 2;
    }
    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
int n,m,a[100005],f[100005];
int main()
{
	scanf("%d%d",&n,&m);
	f[0]=1;
	for (int i=1;i<=m;i++)
	{
		int x;
		scanf("%d",&x);
		a[x]=1;
	}
	if(!a[1]) f[1]=1;
	for (int i=2;i<=n;i++) if (!a[i]) f[i]=(f[i-1]+f[i-2])%1000000007;
	printf("%d\n",f[n]);
}

Measured memory_bytes: 2504
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String []a=sc.next().split("",0);
        String[]aa=new String[]{"0","1"};
        int count=0;
        for(int i=0;i<a.length;i++){
            if(a[i].equals(aa[i%2]))count++;
        }
        System.out.println(Math.min(count,a.length-count));
    }
}


Measured memory_bytes: 33480
import sys
buf = sys.stdin.buffer

import numpy as np
MOD = 10 ** 9 + 7

H,W = map(int,buf.readline().split())

grid = np.frombuffer(buf.read(),dtype='S1').reshape(H,-1)[:,:W]

#print(grid)

MOD = 10 ** 9 + 7
dp = np.zeros(W, dtype = np.int64)
dp[0] = 1

for row in grid:
  #print(row == b"#")
  wall = (row == b'#')
  # 上から落としてくる
  dp[wall] = 0
  # 左から右に
  np.cumsum(dp, out = dp)
  # 壁の補正
  sub = np.maximum.accumulate(dp * wall)
  dp -= sub
  dp %= MOD

answer = dp[-1]
print(answer)

Measured memory_bytes: 14408
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(c) (c).begin(), (c).end()
#define pb push_back
#define eb emplace_back
using namespace std;
const long long INF = 1LL<<60; // 仮想的な無限大の値;
using ll = long long;
using P  = pair<int, int>;
#define vi vector<int>
#define vll vector<ll>
#define vs vector<string>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main()
{
    int k, a, b;
    cin >> k >> a >> b;
    int x = a/k;
    if(a%k == 0)
    {
        cout << "OK" << endl;
        return 0;
    }
    x++;
    int y = b/k + 1;
    rep2(i, x, y)
    {
        if(a <= k*i && k*i <= b)
        {
            cout << "OK" << endl;
        return 0;
        }
    }
    cout << "NG" << endl;
        return 0;
    return 0;
}

Measured memory_bytes: 3632
from itertools import accumulate
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    r = 0
    for i in range(N):
        r += B[A[i] - 1]
        if i < N - 1 and A[i+1] - A[i] == 1:
            r += C[A[i] - 1]
    print(r)


if __name__ == '__main__':
    main()


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

#include <iostream>
#include <string>
using namespace std;

int LR[502][502] = {0};
int dp[502][502] = {0};

void calcdp(){
	for(int i=1; i<=500; i++){
		dp[i][i] = LR[i][i];
	}
	for(int i=1; i<500; i++){
		for(int j=i; j<500; j++){
			int s = 0;
			for(int k=i; k<=j+1; k++){
				s += LR[k][j+1];
			}
			dp[i][j+1] = dp[i][j] + s;
		}
	}
}

int main(int argc, char* argv[]){
	int N, M, Q;
	cin >> N >> M >> Q;
	
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){ dp[i][j] = -1;}
	}

	for(int i=1; i<=M; i++){
		int l, r;
		cin >> l >> r;
		LR[l][r]++;
	}
	calcdp();
	for(int i=1; i<=Q; i++){
		int p, q;
		cin >> p >> q;
		printf("%d\n",dp[p][q]);
	}
	return 0;
}

Measured memory_bytes: 2944
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


# リスト l の最大公約数
def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a, l[i])
    return a

K = int(input())

result = 0

for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            l = [i, j, k]
            result += gcdlist(l)

print(result)

Measured memory_bytes: 72068
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
typedef long long ll;
typedef long double ld;
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define rrep(i,l,r)for(ll i=(l);i>=(r);i--)
#define INF (1LL<<60)
#define MOD1 1000000007
#define MOD2 998244353
#define MAX_N (1 << 17)
#define YES printf("Yes\n")
#define NO printf("No\n")
#define PN printf("\n")

void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a=c;}
ll max2(ll a,ll b){return a>=b?a:b;}
ll min2(ll a,ll b){return a>=b?b:a;}
ll min3(ll a, ll b, ll c){return (a<=b && a<=c) ? a : b<=c ? b : c;}
ll max3(ll a, ll b, ll c){return (a>=b && a>=c) ? a : b>=c ? b : c;}
ll minn(ll n, ll a[n]){ll b=INF;rep(i,0,n) b=min2(b,a[i]);return b;}
ll maxn(ll n, ll a[n]){ll b=-INF;rep(i,0,n) b=max2(b,a[i]);return b;}
ll ABS(ll a){return a>=0?a:(-a);}
ll POW(ll a, ll b){ll c=1;rep(i,0,b) c*=a;return c;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll mod(ll n){return n%=MOD1;}
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

typedef struct{ ll a , b;}fr;
int cmp1( const void *p, const void *q ) { return ((fr*)p) ->a - ((fr*)q)->a;}
int cmp2( const void *p, const void *q ) { return ((fr*)q) ->a - ((fr*)p)->a;}
void strsortup(fr*a,int n){qsort(a,n,sizeof(fr),cmp1);}
void strsortdown(fr*a,int n){qsort(a,n,sizeof(fr),cmp2);}

/*aのb進数時の桁数*/
ll digits(ll a, ll b){return a/b?1+digits(a/b,b):1;}
/*nをa進数にしたときの、i桁目の数*/
ll a_base2(ll n, ll a, ll i){return i==1?n%a:a_base2(n/a,a,i-1);}
/*n(a)の中にあるiの数*/
ll a_base3(ll n, ll a, ll i){return (n<a) ? (n==i?1:0) : a_base3(n/a,a,i) + (n%a==i?1:0) ;}

int main(void){
    // char ;
    ll n,ans=0;
    scanf("%lld",&n);
    ll a[n],x[15][15],y[15][15];
    rep(i,0,n){
        scanf("%lld",&a[i]);
        rep(j,0,a[i]){
            scanf("%lld%lld",&x[i][j],&y[i][j]);
        }
    }
    rep(i,0,POW(2,n)){
        ll j1=0;
        rep(j,0,n){
            ll j2=0;
            if(a_base2(i,2,j+1) == 0){
                if(j==n-1) j1=1;
                continue; 
            }
            if(a[j]==0){
                if(j==n-1) j1=1;
                continue;
            }
            // printf("%lld %lld aa\n",i,j);
            rep(k,0,a[j]){
                // printf("%lld %lld tt\n",y[j][k],a_base2(i,2,x[j][k]));
                if(y[j][k] != a_base2(i,2,x[j][k]) ){
                    break;
                }
                if(k==a[j]-1) j2=1;
            }
            if(j2==0) break;
            if(j2 && j==n-1) j1=1;
        }
        if(j1) ans=max2(ans,a_base3(i,2,1));
    }

    
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner d = new Scanner(System.in);
		int a = d.nextInt();
		int b = d.nextInt();
		double c;
		c=(a*b*1.0/(a+b));
		System.out.println(c);
	}
}

Measured memory_bytes: 10324
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int N = scanner.nextInt();
    int digits = 0;
    int m = N;
    while (m > 0) {
      digits++;
      m /= 10;
    }

    int c = 0;
    for (int d = 3; d <= digits; d++) {
      for (int i = 1; i <= Math.pow(3, d); i++) {
        int n = i;
        int o = 0;
        int p = 1;
        int[] count = new int[3];
        for (int j = 0; j < d; j++) {
          count[n % 3]++;
          o += ((n % 3) * 2 + 3) * p;
          p *= 10;
          n /= 3;
        }
        if (count[0] == 0 || count[1] == 0 || count[2] == 0 || o > N) continue;
        c++;
      }
    }
    System.out.println(c);
  }
}


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)    FOR (i,0,n)
#define ALL(f,x,...) ([&](decltype((x)) ALL) {                          \
            return (f)(begin(ALL), end(ALL), ## __VA_ARGS__); })(x)

using namespace std;

vector<int> HamiltonishPath;
vector<bool> check;
vector< vector<int> > es;

template<class T> void gc(T &x)
{
    char c;
    int s = 0;
    x = 0;

    c = getchar_unlocked();

    if (c == '-') s = 1;
    else if ('0' <= c && c <= '9')  x = c - '0';

    while (true)
    {
        c = getchar_unlocked();

        if (c < '0' || c > '9') break;
        x = x * 10 + (c - '0');
    }

    if (s) x = -x;
}

int main()
{
    int N, M;

    gc(N);
    gc(M);

    es.resize(N);

    REP(i, M)
    {
        int l, r;
        gc(l);
        gc(r);

        // 0-indexed
        l--;
        r--;

        es[l].push_back(r);
        es[r].push_back(l);
    }

    // 初期値 false
    check.resize(N);

    function<void (int)>  dfs = [&](int e)
    {
        // e 訪問済
        check[e] = true;
        HamiltonishPath.push_back(e);

        // e -> s
        for (auto &&s : es[e])
        {
            if (check[s]) continue;
            else
            {
                dfs(s);
                break;
            }
        }
    };

    dfs(0);
    ALL(reverse, HamiltonishPath);

    check[0] = false;
    HamiltonishPath.pop_back();

    dfs(0);

    cout << HamiltonishPath.size() << endl;

    REP(i, (signed)HamiltonishPath.size())
    {
        cout << HamiltonishPath[i] + 1
             << (i + 1 == (signed)HamiltonishPath.size() ? '\n' : ' ');
    }

    return 0;
}


Measured memory_bytes: 9720
#include <algorithm>
#include <climits>
#include <complex>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

// using
using namespace std;

// typedef
typedef long long ll;

// define
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REVERSE(c) reverse(ALL(c))
#define UNIQ(c) unique(ALL(c))
#define FOR(i, a, b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))
#define REP(i, n) FOR(i, 0, n, 1)
#define RFOR(i, a, b, c) for (int i = (int)(a); i >= (int)(b); i -= (int)(c))
#define RREP(i, n) RFOR(i, n, 0, 1)

// functions
int ceil(int a, int b) {
    return (a + b - 1) / b;
}
int round(int a, int b) {
    return (a + b / 2) / b;
}
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
template <class T> bool amax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

// main
int main() {
    int N, p;
    cin >> N;
    int res = 0, m = 0;
    REP(i, N) {
        cin >> p;
        res += p;
        amax(m, p);
    }
    cout << res - m / 2 << endl;
    return 0;
}


Measured memory_bytes: 256
def maxHeapify(A, i):
    H = len(A) - 1
    l = 2*i
    r = 2*i + 1
    Max = i
    if l <= H and A[l] > A[i]:
        Max = l
    if r <= H and A[r] > A[Max]:
        Max = r
    if Max != i:
        A[i], A[Max] = A[Max], A[i]
        maxHeapify(A, Max)

def buildMaxHeap(A):
    H = len(A) - 1
    for i in range(H//2, 0, -1):
        maxHeapify(A, i)

n = int(input())
A = [''] + list(map(int, input().split()))
buildMaxHeap(A)

print(*A)


Measured memory_bytes: 63700
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define repi(i,n,init) for(int i=init;i<(int)(n);i++)
#define repd(i,n,init) for(int i=(int)(n);i>=init;i--)
#define repm(i,m) for(auto i=m.begin();i!=m.end();i++)

int main()
{
    int A,B;
    cin >> A >> B;
    if(A > 9 || B > 9){
        cout << -1 << endl;
        return 0;
    }
    cout << A * B << endl;
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define PI 3.141592
#define LL_INF 9000000000000000000
#define LL_MINF -9000000000000000000
#define INT_INF 2000000000
#define INT_MINF -2000000000
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int main(){
    int H, W;
    cin >> H >> W;
    vector<vector<char>> A(H, vector<char>(W));
    for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) cin >> A[i][j];
    vector<vector<char>> Ae(H + 2, vector<char>(W + 2, '#'));
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            Ae[i + 1][j + 1] = A[i][j];
        }
    }
    for(int i = 0; i < H + 2; i++){
        for(int j = 0; j < W + 2; j++){
            cout << Ae[i][j];
        }
        cout << endl;
    }
}


Measured memory_bytes: 3588
import std.stdio;
import std.ascii;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;
import std.c.string;
import std.regex;
import std.typecons;
import std.random;

class S {
    int from, to;
    int id;
    int size() { return to - from; }
    this(int from, int to, int id) {
        this.from = from;
        this.to = to;
        this.id = id;
    }
    override string toString() const {
        return format("S(%s,%s,%s)", from, to, id);
    }
}

const M = cast(int)1e9 + 1;

void main() {
    int N;
    while (scanf("%d\n", &N), N > 0) {
        //stderr.writeln(t);
        int id, size;
        auto buf = new char[16];
        auto init = new S(0, M, -1);
        auto D = [init];
        BinaryHeap!(Array!S, "a.from > b.from") PQ;
        PQ.insert(init);
        foreach (i; 0 .. N) {
            scanf("%s %d", buf.ptr, &id);
            switch (buf[0]) {
                case 'W': 
                    scanf("%d", &size);
                    while (size > 0) {
                        auto s = PQ.front; PQ.removeFront;
                        if (s.size > size) {
                            s.from += size;
                            D ~= new S(s.from - size, s.from, id);
                            PQ.insert(s);
                            size = 0;
                        } else {
                            s.id = id;
                            size -= s.size;
                        }
                    }
                    break;
                case 'R':
                    foreach (ref d; D) {
                        if (d.from <= id && id < d.to) {
                            writeln(d.id);
                            break;
                        }
                    }
                    break;
                case 'D':
                    foreach (d; D) {
                        if (d.id == id) {
                            d.id = -1;
                            PQ.insert(d);
                        }
                    }
                    break;
                default: assert(0);
            }
            //writeln(D);
        }
        writeln;
    }
}

Measured memory_bytes: 1616
//#define __USE_MINGW_ANSI_STDIO 0
#include <iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
using namespace std;

#define debug(x) cout<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;

#define boost ios::sync_with_stdio(0); cin.tie(0)

#define fi first
#define se second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)

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

const int N = 2000 + 5;

/***************************************************************************/

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

int DP[N][N];
ordered_set S;
int W[N], B[N];

int main() {

	boost;

	int n; cin>>n;
	for(int i=1; i<=2*n; i++) {
		char ch; int a; cin>>ch>>a;
		if(ch == 'B') {
			B[a] = i;
		}
		else {
			W[a] = i;
		}
	}

	for(int i=n; i>=0; i--) {

		if(i < n) S.insert(B[i+1]);

		for(int j=n; j>=0; j--) {

			if(j < n) S.insert(W[j+1]);

            if(i == n and j == n) continue;
            else if(i == n) DP[i][j] = S.order_of_key(W[j+1]) + DP[i][j+1];
            else if(j == n) DP[i][j] = S.order_of_key(B[i+1]) + DP[i+1][j];
            else DP[i][j] = min(S.order_of_key(B[i+1]) + DP[i+1][j], 
                                S.order_of_key(W[j+1]) + DP[i][j+1]);
		}
		for(int j=n-1; j>=0; j--) {
			S.erase(S.find(W[j+1]));
		}
	}

	cout<<DP[0][0]<<"\n";
	return 0;
}

Measured memory_bytes: 16128
let d1 (x, y, l, r) s =
  match x, y, s with
    1, 0, 0 -> 1
  | 0, 1, 0 -> 1
  | 1, 1, 0 -> 2
  | _, _, _ -> s
let a1 = (d1, [0; 2])

let d2 (x, y, l, r) s =
  match x, l, s with
    1, 0, 0 -> 1
  | 0, 1, 0 -> 2
  | _, _, _ -> s
let a2 = (d2, [0; 1])

let d3 (x, y, l, r) s =
  match y, r, s with
    1, 0, 0 -> 1
  | 0, 1, 0 -> 2
  | _, _, _ -> s
let a3 = (d3, [0; 2])

let d4 (x, y, l, r) s =
  match x, y, s with
    1, 0, 0 -> 1
  | _, _, _ -> s
let a4 = (d4, [0])

let aus = [a1; a2; a3; a4]

let mo = 1_000_000_007

let () = Scanf.scanf "%d %d" @@ fun l r ->
  let a = Array.make (60 * 81) (-1) in
  let rec f i ss =
    let j = List.fold_left (fun x y -> x * 3 + y) 0 ss in
    if i < 0
    then if List.for_all2 (fun s (_, acs) -> List.mem s acs) ss aus
         then 1
         else 0
    else if a.(i * 81 + j) <> -1
         then a.(i * 81 + j)
         else let v = List.fold_left (fun s (a, b) ->
                          let ss = List.map2 (fun s (d, _) -> d (a, b, (l lsr i) land 1, (r lsr i) land 1) s) ss aus in
                          (s + f (i - 1) ss) mod mo) 0 [(0, 0); (0, 1); (1, 0); (1, 1)] in
              let () = a.(i * 81 + j) <- v in
              a.(i * 81 + j) in
  Printf.printf "%d\n" @@ f 59 [0; 0; 0; 0]



Measured memory_bytes: 3072
//A.cpp
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const ll mod=1e9+7;
// const int imax = 100000;

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  if(b >= a*c) printf("%d\n", c);
  else printf("%d\n", b/a);

  return 0;
}


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

using namespace std ;

const int MAX = 2e5 + 10 ;

struct segment_tree
{
	vector<int>v ;
	vector<long long>tree ;
	multiset<long long>tree2[4*MAX] ;
	int sz ;
	bool flag ;
	void init(vector<int>v2 , bool t)
	{
		if(t == 0)
			flag = 0 ;
		else
			flag = 1 ;
		sz = (int)v2.size() ;
		v = v2 ;
		sort(v.begin() , v.end()) ;
		tree.resize(sz*4+10) ;
		for(int i = 0 ; i < sz*4+10 ; ++i)
			tree[i] = 0 ;
	}
	int getidx1(long long idx)
	{
		int idx2 = lower_bound(v.begin() , v.end() , idx) - v.begin() ;
		return idx2 ;
	}
	int getidx2(long long idx)
	{
		int idx2 = lower_bound(v.begin() , v.end() , idx) - v.begin() ;
		idx2-- ;
		return idx2 ;
	}
	void update(int node , int l , int r , int idx , long long v)
	{
		if(idx > r || idx < l || idx < 0)
			return ;
		if(l == r)
		{
			if(v < 0)
				tree2[node].erase(tree2[node].find(-1ll*v)) ;
			else
				tree2[node].insert(v) ;
			if(tree2[node].size() > 0)
				tree[node] = *tree2[node].rbegin() ;
			else
				tree[node] = 0 ;
			return ;
		}
		int mid = (l + r) >> 1 ;
		update(node << 1 , l , mid , idx , v) ;
		update(node << 1 | 1 , mid+1 , r , idx , v) ;
		if(flag == 0)
			tree[node] = max(tree[node << 1] , tree[node << 1 | 1]) ;
		else
			tree[node] = (tree[node << 1] + tree[node << 1 | 1]) ;
	}
 
	long long query(int node , int l , int r , int from , int to)
	{
		if(from > r || to < l || from > to)
			return 0 ;
		if(l >= from && r <= to)
			return tree[node] ;
		int mid = (l + r) >> 1 ;
		long long a = query(node << 1 , l , mid , from , to) ;
		long long b = query(node << 1 | 1 , mid+1 , r , from , to) ;
		if(flag == 0)
			return max(a , b) ;
		else
			return (a + b) ;
	}
 
	void update(long long idx , long long val)
	{
		idx = getidx1(idx) ;
		update(1 , 0 , sz , idx , val) ;
	}
 
	long long query(long long idx)
	{
		idx = getidx2(idx) ;
		return query(1 , 0 , sz , 0 , idx) ;
	}
};

int arr[MAX] , ans[MAX] ;
int n ;

vector< vector<int> >adj(MAX) ;

segment_tree tree ;

void dfs(int node , int par , int Max)
{
	int x = tree.query(arr[node])+1 ;
	ans[node] = max(Max , x) ;
	tree.update(arr[node] , x) ;
	for(auto &child : adj[node])
	{
		if(child == par)
			continue ;
		dfs(child , node , ans[node]) ;
	}
	tree.update(arr[node] , -1*x) ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	for(int i = 0 ; i < n-1 ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		adj[x].push_back(y) ;
		adj[y].push_back(x) ;
	}
	vector<int>v ;
	for(int i = 1 ; i <= n ; ++i)
		v.push_back(arr[i]) ;
	tree.init(v , 0) ;
	dfs(1 , -1 , 0) ;
	for(int i = 1 ; i <= n ; ++i)
		cout<<ans[i]<<"\n" ;
	return 0 ;
}		


Measured memory_bytes: 98504
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int main() {
  string n;
  cin >> n;
  ull max=0;
  for(int i=0;i<n.size();i++) {
    max += (n[i]-'0');
  }
  if(stoull(n)%max==0) cout << "Yes" << endl;
  else cout << "No" << endl;
}


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

int main() {
int n;
cin >> n;
vector<int> a(n);
vector<int> b(n);
vector<int> c(n-1);
rep(i,n) cin >> a.at(i);
rep(i,n) cin >> b.at(i);
rep(i,n-1) cin >> c.at(i);

int sum = 0;
for(int i: b){
sum += i;
}

for(int i = 0; i < n-1 ;i++){
  if(a.at(i) == a.at(i+1) - 1){
    sum += c.at(a.at(i)-1);
  }
}
cout << sum << endl;
}
  


Measured memory_bytes: 384
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <ccomplex>
#include <unordered_map>
#include <cstring>
#include <iostream>
#include <numeric>
#include <sstream>
#include <set>
#include <tuple>
#include <iomanip>

using namespace std;
#define MAX 1LL << 60

typedef long long ll;

#define rep(i, s, e) for(ll i = s; i < e; i++)
#define repR(i, s, e) for(ll i = s; i > e; i--)
#define reft0(i, j) setfill('0') << setw(i) << j

template<class T> inline bool chMax(T& a, T b){ if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chMin(T& a, T b){ if (a > b) { a = b; return true; } return false; }

int main(){
	ll A, B;
	string S;
	cin >> A >> B >> S;
	if (S[A] != '-'){
		cout << "No" << endl;
		return 0;
	}
	S.erase(A, 1);
	rep(i, 0, S.size()){
		if (S[i] < '0' || '9' < S[i]){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
 	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
  int n,k,i,f,h[100000];
  
  scanf("%d%d",&n,&k);
  
  for(i=0;i<n;i++)
    scanf("%d",&h[i]);
  
  f=0;
  for(i=0;i<n;i++)
    if(h[i]>=k) f++;
  printf("%d\n",f);
  return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const ll INF = 1000000000000000000;
const ll mod = 1000000007;
const ll MAX = 510000;

ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
ll COM(ll n, ll k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
signed main() {
    ll k, not0 = 0; string s; cin >> s >> k; COMinit();
    if (k == 1) {
        cout << (ll)(s[0] - '0') + 9 * (s.size() - 1) << endl;
    }
    for (int h = 1; h < s.size(); h++) {
        if ((s[h] - '0') != 0) { not0 = h; break; }
    }
    if (k == 2) {
        ll x = 9 * 9 * COM(s.size() - 1, 2);//最初入れない
        ll y = ((ll)(s[0] - '0') - 1) * 9 * (s.size() - 1);//最初入れる（NO最高)
        if (not0 == 0) { cout << x + y << endl; return 0; }
        cout << x + y + (ll)(s[not0] - '0') + 9 * (s.size() - not0 - 1) << endl;
    }

    if (k == 3) {
        ll x = 9 * 9 * 9 * COM(s.size() - 1, 3);//最初入れない
        x += ((ll)(s[0] - '0') - 1) * 9 * 9 * COM(s.size() - 1, 2);//最初入れる（NO最高)
        if (not0 == 0) { cout << x << endl; return 0; }
        x += ((s[not0] - '0') - 1) * 9 * (s.size() - not0 - 1);//not0含める(NO最高)
        x += 9 * 9 * COM(s.size() - not0 - 1, 2);//not0含めない
        ll z = 0;
        for (int h = not0 + 1; h < s.size(); h++) {
            if ((s[h] - '0') != 0) { not0 = h; z++; break; }
        }
        if (z == 0) { cout << x << endl; return 0; }
        x += (ll)(s[not0] - '0') + 9 * (s.size() - not0 - 1);
        cout << x << endl;
    }
	return 0;
}

Measured memory_bytes: 12288
/*
   ~~~~~~~~~~~~~~~~~~~
   \  |\/| | |\ | |  /
   /  |  | | |/ |_|  \
   ~~~~~~~~~~~~~~~~~~~
*/
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string.h>
#define sp setprecision
typedef long long ll;
using namespace std;
int main()
{	
	char a;
	cin>>a;
	if(a>64 && a<91) cout<<"A\n";
	else cout<<"a\n";
	return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cctype>
#include<map>
#include<cstring>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,b) for (int (i)=a;(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long int;

const int inf = 1001001000;
const long long int Inf = 1001001001001001000;



void print(vector<vector<int>> a){
	for (int i = 0; i < a.size(); i++)
	{
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<vector<long long int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(vector<long long int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(set<int> a){
	for (auto x:a)
		cout << x << " ";
	cout << endl;
}

// int main(){
// 	ll n, m, s;
// 	cin >> n >> m >> s;
// 	vector<vector<ll>> map(m);
// 	rep(i,m){
// 		ll a, b, c, d;
// 		cin >> a >> b >> c >> d;
// 		map[i] = {a, b, c, d};
// 	}
// 	vector<vector<ll>> cost(n);
// 	rep(i,n){
// 		ll a, b;
// 		cin >> a >> b;
// 		cost[i] = {a, b};
// 	}

// 	return 0;
// }

//nCrを返す関数.
long long int comb(long long int n, long long int r){
	long long int x = 1, y = 1;
	if (n-r < r) r = n - r;
	for (long long int i = 0; i < r; i++)
	{
		x = x * (n - i);
		y = y * (i + 1);
	}
	return x / y;
}

int main(){
	string s;
	cin >> s;
	reverse(all(s));
	vector<int> t;
	t.push_back(1);
	rep(i, s.size() - 1)
	{
		t.push_back((t.back() * 10) % 2019);
	}
	vector<ll> t2(t.size());
	rep(i, t.size()) {
		t2[i] = ((s[i]-'0') * t[i]) % 2019;
	}
	vector<ll> r(t2.size() + 1);
	rep(i,t2.size()) {
		r[i + 1] = (r[i] + t2[i])%2019;
	}
	map<ll, int> k;
	for (ll x :r){
		k[x] += 1;
	}
	ll ans = 0;
	for (auto x : k)
	{
		if(x.second > 1){
			ans += comb(x.second, 2);
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 7280
#include<cstdio>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<complex>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

#define reps(i,f,n) for(int i=f;i<int(n);i++)
#define rep(i,n) reps(i,0,n)

const int M = 24;
const int INF = 1000000000;
const int C = 5;

typedef pair<int,int> pii;

int n;
int x[M];
int y[M];
int r[M];
int c[M];

vector<pii> colpair;
vector<int> on[M];
map<int,int> memo;

bool ok(int state, pii& p){
	bool ret = (state&(1<<p.first))==0 && (state&(1<<p.second))==0;
	if(ret==false)return ret;
	
	rep(i,on[p.first].size()){
		if((state&(1<<on[p.first][i]))==0)ret = false;
	}
	rep(i,on[p.second].size()){
		if((state&(1<<on[p.second][i]))==0)ret = false;
	}
	return ret;
}

int saiki(int state){
	if(memo.find(state)!=memo.end())return memo[state];
	
	int ans = 0;
	rep(i,colpair.size()){
		if(ok(state, colpair[i])){
			int v = saiki(state | (1<<colpair[i].first) | (1<<colpair[i].second));
			ans = max(ans, v+2);
		}
	}
	
	return memo[state]=ans;
}

void init(){
	memo.clear();
	rep(i,n)on[i].clear();
	colpair.clear();
	
	rep(i,n)reps(j,i+1,n){
		if(c[i]==c[j])colpair.push_back(pii(i,j));
	}
	
	rep(i,n){
		rep(j,i){
			int dx = x[i]-x[j];
			int dy = y[i]-y[j];
			int r2 = r[i]+r[j];
			
			if(dx*dx + dy*dy < r2*r2){
				on[i].push_back(j);
			}
		}
	}
	/*
	rep(i,colpair.size()){
		printf("%d %d\n",colpair[i].first, colpair[i].second);
	}
	rep(i,n){
		printf("on ");
		rep(j,on[i].size())printf("%d ",on[i][j]);puts("");
	}*/
}
int solve(){
	rep(i,n)cin>>x[i]>>y[i]>>r[i]>>c[i];
	init();
	
	return saiki(0);
}


int main(){
	while(1){
		cin>>n;
		if(n==0)break;
		printf("%d\n",solve());
		//break;
	}
}

Measured memory_bytes: 50348
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

N = ii()
A = sorted(li())

if N%2==1:
    if A[0]!=0:
        print(0)
        exit()
    for i in range(1, N//2+1):
        i2 = i*2
        if A[i2-1]!=i2 or A[i2]!=i2:
            print(0)
            exit()

else:
    for i in range(N//2):
        i2 = i*2
        if A[i2]!=i2+1 or A[i2+1]!=i2+1:
            print(0)
            exit()

INF = 10**9+7
print(2**(N//2)%INF)

Measured memory_bytes: 13876
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;


int main(){
	int n;
	int ary1[10100];
	int ary2[10100];

	while (cin >> n, n != 0) {
		int sum1 = 0, sum2 = 0;
		for (int i = 0; i < n; i++) {
			cin >> ary1[i] >> ary2[i];
		}

		for (int i = 0; i < n; i++) {
			if (ary1[i] > ary2[i]) {
				sum1 += (ary1[i] + ary2[i]);
			}
			else if (ary1[i] < ary2[i]) {
				sum2 += (ary1[i] + ary2[i]);
			}
			else {
				sum1 += ary1[i];
				sum2 += ary2[i];
			}
		}

		cout << sum1 << " " << sum2 << endl;
	}

	return 0;
}

Measured memory_bytes: 3068
#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, x, y;
  cin >> n >> x >> y;
  x--;
  y--;
  vector<int> cnt(n);
  rep(i, n - 1) {
    for(int j = i + 1; j < n; j++) {
      int a;
      a = min(j - i, abs(x - i) + 1 + abs(j - y));
      cnt[a]++;
    }
  }
  rep(i, n - 1) cout << cnt[i + 1] << endl;
}


Measured memory_bytes: 3580
a,b,c,x,y = map(int,raw_input().split())

result = int()
minc = min([x,y])
x_,y_ = map(lambda i: i-minc, [x,y])
    
if a+b > 2*c:
    result = (minc*2) * c
    result += x_ * 2*c if a > 2*c else x_ * a
    result += y_ * 2*c if b > 2*c else y_ * b
else:
    result = a*x + b*y

print result

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


int main(){
  string s;
  cin >> s;
  if (s == "SUN") cout << 7 << endl;
  else if (s == "MON") cout << 6 << endl;
  else if (s == "TUE") cout << 5 << endl;
  else if (s == "WED") cout << 4 << endl;
  else if (s == "THU") cout << 3 << endl;
  else if (s == "FRI") cout << 2 << endl;
  else cout << 1 << endl;
  return 0;
} 

Measured memory_bytes: 256