akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (1LL<<60)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
typedef unsigned long long int ull;
typedef long long lint;

int main(void){
    int N;
    cin >> N;
    int A[N];
    rep(i,N) cin >> A[i];
    int ans=0,check=0;
    while(true){
        rep(i,N){
            if(A[i]%2==0) A[i]/=2;
            else check=1;
        }
        if(check==1) break;
        ans++;
    }
    cout << ans << endl;
}

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

vector<int> a;

bool possible(int max,int k)
{
	for(int i=0;i<(int)a.size();i++)
	{
		k-=(a[i]+max-1)/max-1;
	}
	return k>=0;
}

int main()
{
	// #ifndef ONLINE_JUDGE
	// 	freopen("input.txt","r",stdin);
	// 	freopen("outputc.txt","w",stdout);
	// #endif
	
	//int t;
	//cin>>t;
	//while(t--)
	{
		int n,k;
		cin>>n>>k;
		a=vector<int> (n);
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
		}
		ll low=1,high=1e9;
		while(low<=high)
		{
			ll mid=(low+high)/2;
			if(possible(mid,k))
			{
				high=mid-1;
			}
			else
			{
				low=mid+1;
			}
		}
		cout<<low<<'\n';
		
	}
		
}



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

typedef long long ll;

const ll LLINF = 4e18;
const int INF = 1e9;
const ll SHIFT = 2.01e9;

const int MAXK = 1010;
int K;

const int MAXN = 2 * MAXK;
int N, M;
int S, T;

struct edge {
	int nxt, rev, cap; ll dist;
	edge() {}
	edge(int nxt_, int rev_, int cap_, ll dist_) : nxt(nxt_), rev(rev_), cap(cap_), dist(dist_) { }
};

vector<edge> adj[MAXN];

void add_edge(int a, int b, int c, ll d) {
	adj[a].push_back(edge(b, int(adj[b].size()), c, d));
	adj[b].push_back(edge(a, int(adj[a].size()) - 1, 0, -d));
}

bool vis[MAXN];
ll dist[MAXN];
int ptr[MAXN];

bool reach() {
	vector<int> q;
	q.push_back(S);
	fill_n(dist, N, -LLINF);
	fill_n(vis, N, false);
	dist[S] = 0;
	for (size_t i = 0; i < q.size(); i++) {
		int cur = q[i]; vis[cur] = false;
		for (size_t j = 0; j < adj[cur].size(); j++) {
			edge& e = adj[cur][j];
			if (!e.cap || dist[e.nxt] >= dist[cur] + e.dist) {
				continue;
			}
			dist[e.nxt] = dist[cur] + e.dist;
			if (!vis[e.nxt]) {
				vis[e.nxt] = true;
				q.push_back(e.nxt);
			}
		}
	}
	return dist[T] != -LLINF;
}

int dfs(int cur, int rem) {
	if (cur == T) {
		return rem;
	}
	int tot = 0;
	vis[cur] = true;
	for (int& i = ptr[cur]; i < int(adj[cur].size()); i++) {
		edge& e = adj[cur][i];
		if (!e.cap || vis[e.nxt] || dist[e.nxt] != dist[cur] + e.dist) {
			continue;
		}
		ll d = dfs(e.nxt, min(rem - tot, e.cap));
		tot += d;
		e.cap -= d;
		adj[e.nxt][e.rev].cap += d;
		if (tot == rem) {
			vis[cur] = false;
			break;
		}
	}
	return tot;
}

ll mcf(int rem = INF) {
	int totflow = 0; ll totcost = 0;
	while (reach()) {
		fill_n(ptr, N, 0);
		int d = dfs(S, rem - totflow);
		totflow += d;
		totcost += d * dist[T];
	}
	return totcost;
}

int main() {
	scanf("%d", &K);
	S = 0, T = 1;
	N = 2 * K + 6;
	int tot = 0;
	for (int i = 0; i < K; i++) {
		ll x, y; int c; scanf("%lld %lld %d", &x, &y, &c);
		tot += c;
		add_edge(S, 6+i, c, 0);
		add_edge(6+i, 2, INF, x + y);
		add_edge(6+i, 3, INF, x - y);
		add_edge(6+i, 4, INF, -x + y);
		add_edge(6+i, 5, INF, -x - y);
	}
	for (int i = 0; i < K; i++) {
		ll x, y; int c; scanf("%lld %lld %d", &x, &y, &c);
		add_edge(6+K+i, T, c, 0);
		add_edge(2, 6+K+i, INF, -x - y);
		add_edge(3, 6+K+i, INF, -x + y);
		add_edge(4, 6+K+i, INF, x - y);
		add_edge(5, 6+K+i, INF, x + y);
	}

	ll ans = mcf(tot);
	printf("%lld\n", ans);

	return 0;
}


Measured memory_bytes: 1024
# https://beta.atcoder.jp/contests/abc109/tasks/abc109_a
def solve():
    a, b = map(int, input().split())
    for i in range(1, 4):
        if a * b * i % 2 != 0:
            print('Yes')
            break
    else:
        print('No')


if __name__ == '__main__':
    solve()


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

int main() {
  int N, D;
  cin >> N >> D;
  int ViewedTrees = 2 * D + 1;
  int Watchmans = N / ViewedTrees;
  if (N % ViewedTrees ==0) cout << Watchmans <<endl;
  else cout << Watchmans + 1 << endl;
  
}
  
  
 

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
#include <tuple>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
#define modulo 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9
#define LLINF 1LL<<60



int A[2010];
int b[2010][2010]; // b[i][j] : A[i]～A[i-j]の最小値

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

	ll N, x;
	cin >> N >> x;
	for (int i = 0; i < N; i++) cin >> A[i];

	for (int i = 0; i < N; i++) {
		b[i][0] = A[i];
		for (int j = 1; j <= N - 1; j++) {
			b[i][j] = min(b[i][j - 1], A[(i - j + N) % N]);
		}
	}

	ll ans = LLINF;
	for (int k = 0; k <= N - 1; k++) {
		ll tmpAns = 0LL;
		for (int i = 0; i < N; i++) tmpAns += b[i][k];
		tmpAns += x * k;
		ans = min(ans, tmpAns);
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 16000
#include <stdio.h>

int main(void) {
	int i=0;
	char str[80];
	
	scanf("%s", str);
	
	while (str[i] != '\0' || i>=80)  i++;
	
	i--;
	while (i>=0) {
		putchar(str[i]);
		i--;
	}
	putchar('\n');
	
	return 0;
}

Measured memory_bytes: 524
def GCD(a: int, b: int) -> int:
    return a if b == 0 else GCD(b, a % b)


def LCM(a: int, b: int) -> int:
    return a * b // GCD(a, b)


n, m = map(int, input().split())
a = list(map(lambda x: int(x) // 2, input().split()))

a_lcm = a[0]
for i in range(1, n):
    a_lcm = LCM(a_lcm, a[i])
    if a_lcm > m:
        break

if a_lcm <= m:
    flag = True
    for i in range(n):
        if (a_lcm // a[i]) % 2 == 0:
            flag = False
            break

    if flag:
        ans = ((m // a_lcm) + 1) // 2
    else:
        ans = 0
else:
    ans = 0
print(ans)


Measured memory_bytes: 64112
require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

A, B = get_ints

puts A.lcm(B)


Measured memory_bytes: 14456
#include <iostream>
using namespace std;
 
int main() {
	int a,b,c;
	int aa,bb,cc;
	
	aa=3;
	cin >> a >> b>> c;
	
	if(a==b){
		if(b==c){
			aa=1;
		}else{
			aa=2;
		}
	}else{
		if(a==c){
			aa=2;
		}else if(b==c){
			aa=2;
		}
	}
	
	cout << aa <<endl;
	return 0;
}

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

using namespace std;

#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;

// 45106 - 111


void oneCase() {
   int n, k;
   cin >> n >> k;
   int x = 1;
   while (n > 0 && x < k) {
       --n;
       x <<= 1;
   }
   cout << x + n * k << "\n";
}


int main() {
    int t = 1;
//    cin >> t;
    while (t--) {
       oneCase();
    }

    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;


public class DwangoV
{	
  
    public static void Main()
	{
	    int N = int.Parse(Console.ReadLine());
	    string[] str = Console.ReadLine().Split(' ');
	    List<double> fm = new List<double>();
	    
	    
	    for(int i = 0 ; i < N ; i++) fm.Add(double.Parse(str[i]));
	    
	    double avg = fm.Sum() / N;

	    double min = 99999999;
	    for(int i = 0; i < N ; i++)
	    {
	        if(fm[i] < avg) fm[i] = avg - fm[i];
	        else fm[i] = fm[i] - avg;
	        if(min > fm[i]) min = fm[i];
	    }
        
        
        for(int i = 0 ; i < N ; i++)
        {
	        if(min == fm[i])
	        {
	            Console.WriteLine(i);
	            break;
	        }
	   }
	}
}

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

int main(){
    string S;cin>>S;
    if(S=="RRR") cout<<3<<endl;
    if(S=="RRS") cout<<2<<endl;
    if(S=="SRR") cout<<2<<endl;
    if(S=="SRS") cout<<1<<endl;
    if(S=="SSR") cout<<1<<endl;
    if(S=="RSS") cout<<1<<endl;
    if(S=="RSR") cout<<1<<endl;
    if(S=="SSS") cout<<0<<endl;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
struct node{
	int number,hao;
};
bool cmp(node x,node y){
	return x.number<y.number;
}
int main(){
	int n;
	scanf("%d",&n);
	node a[n+1];
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].number);
		a[i].hao=i;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		printf("%d ",a[i].hao);
	}
	return 0;
}

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

int main(){
    string S;
    cin >> S;
    
    if( S == "Sunny") cout << "Cloudy" << endl;
    else if( S == "Cloudy") cout << "Rainy" << endl;
    else cout << "Sunny" <<endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 2e5 + 5;

int a[N], b[N];

int main() {
    int n;
    scanf("%d", &n);
    rep(i, 1, n) scanf("%d", &a[i]);
    int ans = 0;
    drep(i, n, 1) {
        int x = 0;
        for(int j = 2 * i; j <= n; j += i)
            x ^= b[j];
        if(x != a[i]) b[i] = 1, ans++;
    }
    printf("%d\n", ans);
    rep(i, 1, n) if(b[i]) printf("%d ", i);
    puts("");
    return 0;
}


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

int main() {
   int N, K;
   cin >> N >> K;
   vector<ll> v(K);
  for(int i = 1; i <= N; i++) { 
      v[i % K] += 1;  
   }
    ll ans = 0;
   
   if(K % 2 == 0) {
       ll a = N / K;
       ll b = (N + K / 2) / K;
       ans = (a * a * a) + (b * b * b); 
   }else {
       ll c = N / K;
       ans = c * c * c;
       
   }

   cout << ans;
    return 0;

}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) (x).begin(),(x).end()
#include <numeric>
using ll = long long;
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() {
	
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	ll a,b; cin >> a >> b;
	//vector<int> a(n),b(n); rep(i,m) cin >> a[i];
	
	
	ll ab=a*b;
	
	if(a<b) swap(a,b);
	
	ll r=a%b;
	
	while(r!=0){
		a=b;
		b=r;
		r=a%b;
	}
	
	cout << ab/b << endl;
	
	//cout << ans << "\n";
	
	return 0;
}


Measured memory_bytes: 256
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    multimul = lambda L,i=0: (L[i] * multimul(L,i+1) % P  if i+1 < len(L) else  L[i])
    INF = 10**18+10

    N,K = LMIIS()
    A = LMIIS()
    
    if N == K:
        print(multimul(A))
        return
    not_negative = []
    negative = []
    for a in A:
        if a < 0:
            negative.append(a)
        else:
            not_negative.append(a)
    if len(negative) == N and K % 2 == 1:
        print(multimul(sorted(negative,reverse=True)[:K]))
        return
    not_negative.sort(reverse=True)

    not_negative = deque(not_negative)
    negative.sort()
    negative = deque(negative)
    ans = 1
    num_multiplied = 0
    while num_multiplied < K:
        if num_multiplied == K-1 or len(negative) < 2 or len(not_negative) >= 2 and not_negative[0] * not_negative[1] > negative[0] * negative[1]:
            ans = ans * not_negative.popleft() % P
            num_multiplied += 1
        else:
            ans = ans * negative.popleft() * negative.popleft() % P
            num_multiplied += 2
    print(ans)
            


    
main()

Measured memory_bytes: 253316
N = int(input())
X = list(map(int, input().split()))

candidates = [sum(X) // N, sum(X) // N + 1]

ans = 0

a = 0
b = 0
for x in X:
    a += (x - candidates[0]) ** 2
    b += (x - candidates[1]) ** 2

if a < b:
    print(a)
else:
    print(b)


Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
#define rep(i, n) for(int i=0; i<n; i++)
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int main(){
    int n; cin >> n;
    string s; cin >> s;
    vector<int> red, white;
    rep(i, n){
        if(s[i] == 'R') red.push_back(i);
        else white.push_back(i);
    }
    reverse(red.begin(), red.end());
    int i;
    if(red.size()==0 || white.size()==0){
        cout << 0 << endl;
        return 0;
    }
    while(red[i] > white[i]){
        if(i == red.size() || i == white.size()) break;
        i++;
    }
    cout << i << endl;
}

Measured memory_bytes: 4748
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 998244353
using namespace std;
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if(c >= a && c <= b) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <numeric>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <cassert>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >
#define endl '\n'
#define FIR first
#define SEC second
#define PB push_back
#define SZ(x) ((int)x.size())

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

template<class U, class V>
istream& operator >>(istream& in, pair<U, V>& pr) {
    return in >> pr.first >> pr.second;
}

template<class U, class V>
ostream& operator <<(ostream& out, pair<U, V>& p) {
    return out << p.first << " " << p.second;
}

template<class T>
ostream& operator <<(ostream& out, vector<T> vec) {
    for (T& e : vec)
        out << e << " ";
    return out << endl;
}

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

int digits(lint n)
{
    lint p10 = 1;
    int ret = 0;
    while (p10 <= n)
        p10 *= 10, ret++;
    return ret;
};

void solveSingleCase(int caseNo)
{
    lint N;
    cin >> N;

    int ret = digits(N);
    for (lint a = 1;a <= N / a; a++)
        if (N % a == 0)
            ret = min(ret, digits(N / a));
    cout << ret << endl;
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    int T = 1;
    // cin >> T;
    FOR(tcase, 1, T + 1) {
        solveSingleCase(tcase);
    }
    return 0;
};


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  if(a+b == c + d) cout << "Balanced" << endl;
    if(a+b < c+ d) cout << "Right" << endl;
    if(a+b > c+ d) cout << "Left" << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
 
int main() {

    int n, x;
    int y1, y2, y3;

    while (true)
    {
        scanf("%d %d", &n, &x);
        if (n==0 && x==0)
            break;

        int count = 0;
        for (y1 = 1; y1 <= n; y1++)
        {
            for (y2 = y1 + 1; y2 <= n; y2++)
            {
                for (y3 = y2 + 1; y3 <= n; y3++)
                {
                    if (y1 + y2 + y3 == x)
                    {
                        count++;
                    }
                }
            }
        }
        printf("%d\n", count);
    }
    return 0;
}


Measured memory_bytes: 2700
<?php
fscanf(STDIN, "%d", $n);
$str = trim(fgets(STDIN));
$s = $str;
for($i = 0; $i < 100; $i++){
    $s = str_replace("()", "", $s);
}
$open = $close = 0;
for($i = 0; $i < strlen($s); $i++){
    if($s[$i] == "("){
        $open++;
    }else{
        $close++;
    }
}
echo str_repeat("(", $close).$str.str_repeat(")", $open);



Measured memory_bytes: 4728
def add(i, j):
    global count, H, W
    if 0 <= i < H and 0 <= j < W:
        count[i][j] += 1

H, W = map(int, input().split())
S = [input() for _ in range(H)]

count = [[0] * W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            for k in range(-1, 2, 1):
                for h in range(-1, 2, 1):
                    if k == h == 0:
                        continue
                    else:
                        add(i + k, j + h)

ans = [[""] * W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            ans[i][j] = "#"
        else:
            ans[i][j] = str(count[i][j])

for i in range(H):
    print("".join(ans[i]))

Measured memory_bytes: 3188
import sys
import collections

N = int(input())

L = collections.deque()
for _ in range(N):
    com = (sys.stdin.readline().rstrip()).split()
    if com[0] == 'insert':
        L.appendleft(int(com[1]))
    elif com[0] == 'delete':
        try:
            L.remove(int(com[1]))
        except:
            pass
    elif com[0] == 'deleteFirst':
        L.popleft()
    elif com[0] == 'deleteLast':
        L.pop()

print(*L)


Measured memory_bytes: 45948
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int i,a,b,c;
	cin>>a>>b>>c;
	if(a==b&&b==c)
		cout<<"No";
	else if(a==b||a==c||b==c)
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
}

Measured memory_bytes: 3620
#include<stdio.h>
#include<string.h>
#include<utility>
#include<iostream>
#include<queue>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
 
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)

int main()
{
    int n,k;
    scanf("%d %d\n",&n,&k);
    long long int h[100005]={};
    REP(i,n)scanf("%lld\n",&h[i]);
    sort(h,h+n);
    long long int min=1145141919810;
    REP(i,n-k+1)if(h[i+k-1]-h[i]<min)min=h[i+k-1]-h[i];
    printf("%lld\n",min);
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <functional>
#include <queue>
//#include <stack>
#include <climits>
#include <map>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define put(a) cout<<a<<endl;
#define all(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
using namespace std;
typedef long long ll;
//typedef unsigned long long ull;
typedef pair<int, int> P;


struct city{
    int p,y,num;
    bool operator<( const city& right ) const {
        return y == right.y ? p < right.p : y < right.y;
    }
};

int n,m;
int pow10(int n){
    int res = 1;
    REP(i,n){
        res*=10;
    }
    return res;
}

string makenum(int p,int c){
    string rtn = "000000000000";
    REP(i,6){
        rtn[5-i] = to_string(p/pow10(i)-p/pow10(i+1)*10)[0];
    }
    REP(i,6){
        rtn[11-i] = to_string(c/pow10(i)-c/pow10(i+1)*10)[0];
    }
    return rtn;
}

int main(){
    cin >> n >> m;
    vector<int> p(m);
    vector<int> y(m);
    REP(i,m){
        cin >> p[i] >> y[i];
    }
    vector<city> ci(m);
    REP(i,m){
        ci[i].y = y[i];
        ci[i].p = p[i];
        ci[i].num = i;
    }
    sort(all(ci));
    vector<int> cnt(n,1);
    vector<pair<int, string>> res(m);
    REP(i,m){
        string s = makenum(ci[i].p,cnt[ci[i].p-1]++);
        res[i].first = ci[i].num;
        res[i].second = s;
        //put(s);
    }
    sort(all(res));
    REP(i,m){
        put(res[i].second);
    }
    return 0;
}




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

#define BUFSIZ 1024

int main (int ac, char **av) {
  char readline[BUFSIZ] = {0};
  int mountains[10] = {0};
  while (fgets(readline, BUFSIZ, stdin) != NULL) {
    int x = atoi(readline);
    if (mountains[0] == 0) {
      mountains[0] = x;
    } else {
      int idx = 0;
      for (idx = 0; idx < 10; idx++) {
	if (mountains[idx] < x) {
	  memmove(mountains+idx+1, mountains+idx, sizeof(int) * (9-idx));
	  mountains[idx] = x;
	  break;
	}
      }
    }
  }
  int i=0;
  for (i = 0; i < 3; i++) {
    fprintf(stdout, "%d\n", mountains[i]);
  }
      

  return 0;
}

Measured memory_bytes: 544
import java.util.Scanner;

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

        double r = sc.nextDouble();

        double area = r * r * Math.PI;
        double cir = 2 * r * Math.PI;

        String str = String.format("%.10f %.10f", area, cir);

        System.out.println(str);
    }
}


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




       
int main(){

long long x , k , d ;
cin >> x >> k >> d;
if(x <0) { x= -1*x;}
long long b = x/d ;
if(k <=b){ cout << (x- d*k) << endl;}
else {
long long  c= (b+1)*d - x;
  
   long long e = x - d*b;
   long long s1 = b;
   long long s2 = b+1;
   if(k== b+1){ cout << c << endl;}
   else {
   if((k-b)%2==0){ cout << e<< endl; }
   else { cout << c << endl;}

   }
}
return 0;
  
}
    

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

int a, b, c;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(), cout.tie();
	cin >> a >> b >> c;
	if ( a + b >= c ) cout << "Yes\n";
	else cout << "No\n";
}


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

int main()
{
    int y, m, d;
    char c1, c2;

    cin >> y >> c1 >> m >> c2 >> d;
    int time = y * 10000 + m * 100 + d;
    if(time > 20190430){
        cout << "TBD" << endl;
    }else{
        cout << "Heisei" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
mod=10**9+7


def main():
    n, m = map(int, input().split())
    if abs(n - m) > 1:
        return 0


    fact = 1
    for i in range(1, min(n, m) + 1):
        fact = fact * i % mod



    if n == m:
        return fact ** 2 * 2 % mod
    else:
        return fact * fact * (min(n, m) + 1) % mod




print(main())

Measured memory_bytes: 3060
import bisect

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

L.sort()
ans = 0
for i in range(N-1):
    a = L[i]
    for j in range(i+1, N):
        b = L[j]
        c = bisect.bisect_left(L, a+b)
        ans += c-j-1
print(ans)

Measured memory_bytes: 3188
# include <cmath>
# include <iostream>
# include <queue>
# include <set>
# include <stack>
# include <string>
# include <vector>


using namespace std;


int main() {
    int n, m; cin >> n >> m;
    vector<pair<int, int>> jobs(n);
    for (int i=0; i<n; i++) {
        cin >> jobs[i].first >> jobs[i].second;
    }

    sort(jobs.begin(), jobs.end());
    priority_queue<int> que;

    int ans = 0;
    int cur = 0;
    for (int t = 1; t <= m; t++) {
        for (; cur < n; cur++) {
            if (jobs[cur].first <= t) {
                que.push(jobs[cur].second);
            }
            else {
                break;
            }
        }

        if (que.size() > 0) {
            ans += que.top(); que.pop();
        }
    }

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



Measured memory_bytes: 1660
s = str(input())
ans =0
cnt =0
#print(s[0])
for i in range(len(s)):
    if s[i] == 'A' or s[i] =='C' or s[i] == 'G' or s[i] =='T':
        cnt += 1
        if ans < cnt:
            ans = cnt
    else:
        cnt = 0
print(ans)

Measured memory_bytes: 3060
#n=int(input())
n,k=map(int,input().split())
pl=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

expl=[0.0]
ansl=[]
cum=0
for i in range(n):
    cum+=(1+pl[i])/2
    expl.append(cum)

for i in range(n-k+1):
    ansl.append(expl[i+k]-expl[i])

print('{:.9f}'.format(max(ansl)))

Measured memory_bytes: 24812
class UnionFind():
    def __init__(self, n):
        self.rank = [0] * n
        self.parent = [i for i in range(n)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def unit(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            if self.rank[x] > self.rank[y]:
                self.parent[y] = x
            else:
                self.rank[x] += 1
                self.parent[y] = x


n, q = map(int, input().split())
u = UnionFind(n)
for i in range(q):
    c, x, y = map(int, input().split())
    if c == 0:
        u.unit(x, y)
    else:
        if u.same(x, y):
            print(1)
        else:
            print(0)


Measured memory_bytes: 6052
#include <bits/stdc++.h>
using namespace std;
int main(){
  	string S;
  	cin >> S;
  	size_t size = S.length();
  	int c = 0;
   	for(int i = 0; i <= size; i++){
  		if(S[i] == 'x'){
          c++;
        }
    }
    if(c>=8){
      		cout << "NO" <<endl;
        }else{
			cout << "YES" <<endl;
    }
}

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

int main() {
  string s,t,u;
  int a,b;
  cin>>s>>t>>a>>b>>u;
  if(s==u){
    a--;
  }
  else if(u==t){
    b--;
  }
  cout<<a<<" "<<b<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
#define endl '\n'
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define vpii vector<pii>
typedef long long ll;
typedef long double ld;
using namespace std;

const int N = 1e5 + 10;
int p[N];
int n;
ll ans = 0;
vpii v;
set<int> s;

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

  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
    v.pb({p[i], i});
  }

  sort(v.begin(), v.end());
  reverse(v.begin(), v.end());

  for (auto &pi : v) {
    int p = pi.f, i = pi.s;
    if (p == n) {
      s.insert(i);
      continue;
    }
    auto it = s.lower_bound(i);

    if (it == s.end()) {
      --it;
      if (it == s.begin()) {
        ans += *it * 1ll * (n - i + 1) * p;
      } else {
        auto it2 = it;
        --it2;
        ans += (*it - *it2) * 1ll * (n - i + 1) * p;
      }
    } else if (it == s.begin()) {
      if (s.size() == 1) {
        ans += i * 1ll * (n - *it + 1) * p;
      } else {
        auto it2 = it; 
        ++it2;
        ans += (*it2 - *it) * 1ll * i * p;
      }
    } else {
      auto up = it;
      auto down = it;
      --down;

      int gup = 1;
      int ldown = 1;

      if (down != s.begin()) {
        auto ptr = down;
        --ptr;
        ldown = *down - *ptr;
      } else {
        ldown = *down;
      }

      auto tmp = up; ++tmp;
      if (tmp != s.end()) {
        gup = *tmp - *up;
      } else {
        gup = n - *up + 1;
      }

      int x = ans;
      ans += gup * 1ll * (i - *down) * p;
      ans += ldown * 1ll * (*up - i) * p;

      // printf("%d %lld\n", p, ans - x);
    }
    s.insert(i);
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 6132
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) rep(i, x.size()) cerr << x[i] << (i == x.size() - 1 ? "\n" : " ")
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
const int INF = ((1LL << 30) + (1LL << 29));
const int MOD = 1000000007;

//=============================
int N,M,K;
string S,T;
int x_1,x_2,y_1,y_2;
//=============================
void input()
{
    cin>>x_1>>y_1>>x_2>>y_2;

    int x_3,x_4,y_3,y_4;
  
    x_4 = x_1 - y_2 + y_1;
    y_4 = y_1 + x_2 - x_1;
    x_3 = x_2 - y_2 + y_1;
    y_3 = y_2 + x_2 - x_1;

    printf("%lld %lld %lld %lld\n", x_3,y_3,x_4,y_4);


}
//=============================
void func(){}
//=============================
void solve()
{
}
//=============================
signed main()
{
    input();
    solve();
    return 0;
}

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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()
#define int ll

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

  int N;
  cin>>N;
  vector<int>hn;
  int Max=3500;
  for(int h=1;h<=Max;h++){
    for(int w=1;w<=Max;w++){
      if(N*w+N*h-4*h*w==0)continue;
      if((-N*h*w)%(N*w+N*h-4*h*w))continue;
      int n=(-N*h*w)/(N*w+N*h-4*h*w);
      if(n>=0){
        cout<<n<<" "<<h<<" "<<w<<endl;
        return 0;
      }
    }
  }
  return 0; 
}


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

using ll = long long int;
using ull = unsigned long long int;
using P = pair<ll, ll>;
using P3 = pair<ll, P>;
using PP = pair<P ,P>;
constexpr ll MOD = ll(1e9+7);
constexpr int IINF = INT_MAX;
constexpr ll LLINF = LLONG_MAX;
constexpr int MAX_N = int(2e5) + 5;
constexpr double EPS = 1e-8;
constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define ALL(v) (v).begin(), (v).end()

int main(){
    int n;
    cin >> n;
    vector<int> l(n);
    for(int i=0;i<n;i++){
        cin >> l[i];
    }
    SORT(l);
    ll ans = 0;
    for(ll i=2;i<n;i++){
        for(ll j=1;j<i;j++){
            int x = l[i]-l[j];
            ans += max(0LL, j - (upper_bound(ALL(l),x) - l.begin()));
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <limits.h>
#include <math.h>

typedef struct edge_t {
    int u, v;
    int w;
} EDGE;

int qsort_edge_u(const void *a, const void *b)
{
    return (*(EDGE *) a).u - (*(EDGE *) b).u;
}

void coloring(int n, EDGE e[], int index[], int links[], int color[], int p)
{
    int i;
    int v, w;
    int stack[200002];
    int p_r, p_w;
    p_r = 0;
    p_w = 0;

    stack[p_w] = p;
    p_w++;

    while(p_r != p_w) {
        p = stack[p_r];
        p_r++;

        for (i = 0; i < links[p]; i++) {
            v = e[index[p] + i].v;
            w = e[index[p] + i].w;
            if (color[v] == -1) {
                stack[p_w] = v;
                p_w++;
                if (w % 2 == 0) { //長さが偶数
                    color[v] = color[p];
                } else { // 奇数
                    color[v] = (color[p] + 1) % 2;
                }
            }
        }
    }

    return;
}

int main(int argc, char *argv[])
{
    int n;
    int u, v, w;
    EDGE e[200000];
    int index[100000];
    int links[100000];
    int color[100000];
    int i;
    int p;
    int ans;

    scanf("%d", &n);

    for (i = 0; i < n - 1; i++) {
        scanf("%d %d %d", &u, &v, &w);
        u--;
        v--;
        e[i * 2 + 0].u = u;
        e[i * 2 + 0].v = v;
        e[i * 2 + 0].w = w;
        e[i * 2 + 1].u = v;
        e[i * 2 + 1].v = u;
        e[i * 2 + 1].w = w;
    }

    qsort(e, 2 * (n - 1), sizeof(EDGE), qsort_edge_u);

    for (i = 0; i < n; i++) {
        color[i] = -1;
        index[i] = -1;
        links[i] = 0;
    }

    p = -1;
    for (i = 0; i < 2 * (n - 1); i++) {
        if (e[i].u != p) {
            p = e[i].u;
            index[p] = i;
        }
        links[e[i].u]++;
    }

    //いろづけ開始
    color[e[0].u] = 0; // 開始を白(0)
    coloring(n, e, index, links, color, e[0].u);

    for (i = 0; i < n; i++) {
        printf("%d\n", color[i]);
    }

    return 0;
}


Measured memory_bytes: 5756
#include <bits/stdc++.h>
using namespace std;
int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}
int main() {
  int64_t n;
  cin>>n;
  queue<int> sosuu;
  if(n==1){
    cout<<1;
  }
  else{
    sosuu.push(2);
  for(int i=2;i<=n;i++){
    for(int j=2;j<i;j++){
      if(i%j==0){
        break;
      }
      if(j==i-1){
        sosuu.push(i);
      }
    }
  }
    vector<int> sosu(sosuu.size());
    for(int i=0;i<sosu.size();i++){
      sosu.at(i)+=sosuu.front();
      sosuu.pop();
    }
    vector<int64_t> count(sosu.size());
   for(int j=2;j<=n;j++){
    for(int i=0;i<sosu.size();i++){
      int z=j;
        while(z%sosu.at(i)==0){
          count.at(i)++;
          z/=sosu.at(i);
        }
    }
    }
    int64_t ans=1;
    for(int i=0;i<count.size();i++){
      ans*=(count.at(i)+1);
      ans=ans%1000000007;
    }
    cout<<ans;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<numeric>
#include<cmath>
#include<vector>
#include<string>

using namespace std;

int main() {
   string N;
 
    cin>>N;
    if(N[0]==N[1] && N[1]==N[2]){
    cout<<"Yes"<<endl;
    }
    else if(N[2]==N[1] && N[3]==N[2]){
    cout<<"Yes"<<endl;
    }
    else{
    cout<<"No"<<endl;
    }
    
	return 0;
}

Measured memory_bytes: 256
import heapq
N,M=map(int,input().split())
lst=list(map(int,input().split()))
A=[]
for i in range(N):
  heapq.heappush(A,-1*lst[i])
while M!=0:
  val=heapq.heappop(A)
  M-=1
  new_val=val/2
  heapq.heappush(A,new_val)

ans=0
for i in range(N):
  ans+=-1*int(A[i])
print(ans)

Measured memory_bytes: 14180
a=int(input())

def f(n):
    if n%2==0:
        return n//2
    else:
        return 3*n+1

ans=1
l=[a]
t=a
while True:
    ans+=1
    t=f(t)
    if t in l:
        print(ans)
        exit()
    l+=[t]


Measured memory_bytes: 2940
#include <iostream>

#define min(x, y) (x < y? x : y)

using namespace std;

int main() {
  int N, K;
  cin>>N>>K;
  int x;
  int r = 0;
  for (int i=0;i<N;i++) {
    cin>>x;
    r += 2 * min(x, K-x);
  }
  cout<<r<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main()
{
    string S;
    cin >> S;
    int count = 0;

    if((S.length() % 2) == 0){
        for(int i = 0; i < S.length() / 2; i++){
            if(S[i] != S[S.length() - (i + 1)])
                count++;
        }
    }
    else{
        for(int i = 0; i < S.length() / 2; i++){
            if(S[i] != S[S.length() - (i + 1)])
            count++;
        }
    }
    cout << count << endl;

    return 0;
}

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




int main()
{
int n;
cin>>n;
int i,j,k;
vector<int> a1(n),a2(n),a3(n);
for(i=0;i<n;i++) cin>>a1[i];
for(i=0;i<n;i++) cin>>a2[i];
for(i=0;i<n;i++) cin>>a3[i];
sort(a1.begin(),a1.end());
sort(a2.begin(),a2.end());
sort(a3.begin(),a3.end());
ll ans=0;
for(i=0;i<n;i++){
    ans+=(lower_bound(a1.begin(),a1.end(),a2[i])-a1.begin())*(a3.end()-upper_bound(a3.begin(),a3.end(),a2[i]));
}
cout<<ans;
}


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

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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define all(x) (x).begin(),(x).end()
#define foreach(u,v) for(auto (u) : (v))
#define pb push_back
#define mp make_pair
#define mt make_tuple

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;

const int inf = 1e9;
const ll linf = 1LL<<60;
const ll mod = 1e9 + 7;
const double eps = 1e-9;

/*
  後ろから
  [s*a[i], (s+1)*a[i])
  この区間でとれるものがない -> -1
  この区間内の最小 -> min
  この区間内の最大 -> max
*/

int main()
{
  int k;
  cin >> k;

  vi a(k);
  rep(i, k) cin >> a[i];

  reverse(all(a));

  ll mi = 2, ma = 2;
  repi(i, 0, k){
    ll nmi = (mi+a[i]-1)/a[i]*a[i];
    ll nma = ma/a[i]*a[i]+a[i]-1;

    if(nmi > ma){
      cout << -1 << endl;
      return 0;
    }

    mi = nmi;
    ma = nma;
  }

  cout << mi << " " << ma << endl;

  return 0;
}


Measured memory_bytes: 768
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
typedef long long ll;
int n,m,q,u,v;
ll a[MAXN],l;
int go[MAXN][30];
int main(){
	SF("%d",&n);
	for(int i=1;i<=n;i++)
		SF("%d",&a[i]);
	int las=0;
	SF("%lld",&l);
	for(int i=1;i<=n;i++){
		while(a[i]-a[las]>l)	
			las++;
		go[i][0]=las;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=20;j++)
			go[i][j]=go[go[i][j-1]][j-1];
	SF("%d",&q);
	for(int i=1;i<=q;i++){
		SF("%d%d",&u,&v);
		if(u>v)
			swap(u,v);
		int len=20;
		int ans=0;
		while(u<v){
			while(len>0&&go[v][len]<u)
				len--;
			v=go[v][len];
			ans+=(1<<len);
		}
		PF("%d\n",ans);
	}
}

Measured memory_bytes: 13184
function myout(text){console.log(text);}//standard output
function Main(input) {
	//input = parseInt(input);
	//input = input.trim().split(" ");
	input = input.trim().split("\n");
	//input = input.trim().split(" ").map((a)=>Number(a));
	//input = input.trim().split("\n").map((a)=>Number(a));
  var N = parseInt(input[0]);
  var ruiseki = 0;
  var list = [];
  for(var i = 1; i <= N; i++){
    var tmp = input[i].split(" ").map((a)=>Number(a));
    var obj = {};
    obj["taskTime"] = tmp[0];
    obj["limitTime"] = tmp[1];
    list.push(obj);
  }
  list.sort(function(a,b){
  	return a["limitTime"] - b["limitTime"];
  });
  for(var i = 0; i < list.length; i++){
    ruiseki += list[i]["taskTime"];
    if(list[i]["limitTime"] < ruiseki){
       myout("No");
      return;
    }
  }
  myout("Yes");
}

Main(require("fs").readFileSync("/dev/stdin", "utf8").trim());


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

using namespace std;

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

const int INF = 1000000000;
const ll LINF = (ll) 4000000000000000000;
const ll MOD = (ll) 1000000007;
const double PI = acos(1.0);
const int limit = 100010;

#define REP(i,m,n) for(ll i = m; i < (ll)(n); i++)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define NP(v) next_permutation(v.begin(),v.end())
#define smaller_queue  priority_queue <ll, vector<ll>, greater<ll> >
//------------------------------------------------------
string s, t;

bool check(int start) {
    bool ok = true;

    rep(i, t.length()) {
        if (s[i + start] == '?') continue;
        if (s[i + start] != t[i]) {
            ok = false;
            break;
        }
    }
    return ok;
}

string make_str(int start) {
    string res = s;

    rep(i, t.length()) {
        res[i + start] = t[i];
    }

    for (auto& c : res) if (c == '?') c = 'a';
    return res;
}

int main() {
    cin >> s >> t;
    vector<string> v;

    int i = 0;
    while (i + t.length() <= s.length()) {
        if (check(i)) v.push_back(make_str(i));
        i++;
    }

    if (v.empty()) cout << "UNRESTORABLE" << endl;
    else {
        sort(v.begin(), v.end());
        cout << v[0] << endl;
    }
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong

signed main(){
    int n;
    int A[MAX],B[MAX];
    cin >> n;
    REP(i,n) scanf("%lld%lld",&A[i],&B[i]);
    pair<int,int> C[MAX];
    REP(i,n) {
        C[i].fi  = A[i] + B[i];
        C[i].se = i;
    }
    sort(C,C+n);
    llong ans = 0;
    int ii = 0;
    REPR(i,n-1){
        if(ii %2 ==0) ans += A[C[i].se];
        else ans -= B[C[i].se];
        ii ++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 6528
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>

#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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int main(){


    int h,w;
    cin >> h >> w;
    vector<string> s(h);
    REP(i,h){
        cin >> s[i];
        //cout << s[i] << endl;
    }

    bool map[h][w];

    REP(i,h){
        REP(j,w){
            map[i][j] = true;
        }
    }


    REP(i,h){
        int white_count = 0;
        REP(j,w){

            if(s[i][j] == '.'){
                white_count++;
            }
            if(white_count == w){
                REP(k,w){
                    map[i][k] = false;
                }
            }
        }
    }

    REP(i,w){
        int white_count = 0;
        REP(j,h){

            if(s[j][i] == '.'){
                white_count++;
            }
            if(white_count == h){
                REP(k,h){
                    map[k][i] = false;
                }
            }
        }
    }

    
    REP(i,h){
        int count = 0;
        REP(j,w){
            if(map[i][j]){
                cout << s[i][j];
                count++;
            }
        }
        if(count != 0){
            cout << endl;
        }
    }



    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)

using namespace std;
using ll = long long;
using P = pair<int,int>;
using ull= unsigned long long;
const ll K_MAX=1e5+5;



int main(){
  ll n,a,b;
  cin >>n>>a>>b;
  ll m=n/(a+b);
  ll c=n%(a+b);
  ll ans=m*a;
  ans+= min(c, a);
  
 
  cout<<ans <<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    int maxi, mini;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (!i) maxi = mini = a[i];
        maxi = max(maxi, a[i]);
        mini = min(mini, a[i]);
    }
    if (maxi - mini > 1) {
        cout << "No" << endl;
        return 0;
    }
    if (maxi == mini) {
        if (maxi == n-1 || maxi * 2 <= n) {
            cout << "Yes" << endl;
        } else cout << "No" << endl;
        return 0;
    }
    int maxcount = 0; int mincount = 0;
    for (int i = 0; i < n; i++) {
        if (maxi == a[i]) maxcount++;
        else mincount++;
    }
    if (mincount < maxi) {
        maxi -= mincount; n -= mincount;
        if (maxi * 2 <= n) {
            cout << "Yes" << endl;
        } else cout << "No" << endl;
        return 0;
    } else {
        cout << "No" << endl;
        return 0;
    }
    assert(false);
    return 0;
}

Measured memory_bytes: 640
import sys
import math
input = sys.stdin.readline
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

x,y=MI()
if y>2*x or x>2*y:
    print(0)
    sys.exit()
elif x%3==0 and y%3==0:
    m=x//3
    l=y//3
    print(cmb(m+l,2*l-m,mod))
    
elif x%3==1 and y%3==2:
    m=(x-1)//3
    l=(y-2)//3
    print(cmb(m+l+1,2*l-m+1,mod))
elif x%3==2 and y%3==1:
    m=(x-2)//3
    l=(y-1)//3
    print(cmb(m+l+1,2*l-m,mod))
else:
    print(0)


Measured memory_bytes: 121956
#include <bits/stdc++.h>
#define rep(i, a) for (int i = (int)0; i < (int)a; ++i)
#define rrep(i, a) for (int i = (int)a - 1; i >= 0; --i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define RREP(i, a, b) for (int i = (int)a - 1; i >= b; --i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define popcount __builtin_popcount
using ll = long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

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

ll gcd(ll n, ll m)
{
	ll tmp;
	while (m != 0)
	{
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m)
{
	return abs(n) / gcd(n, m) * abs(m); //gl=xy
}

using namespace std;

void solve()
{
	int n;
	cin>>n;
	map<pair<ll,ll>,ll>cnt;
	vector<pair<ll,ll>>v(n);
	rep(i,n){
		double num;
		cin>>num;
		ll x=llround(1e9*num);
		ll two=0,five=0;
		while(x%2==0){
			x/=2;
			++two;
		}
		while(x%5==0){
			x/=5;
			++five;
		}
		two-=9;
		five-=9;
		cnt[make_pair(two,five)]++;
		v[i]=make_pair(two,five);
	}
	ll ans=0;
	rep(i,n){
		ll two=v[i].first;
		ll five=v[i].second;
		cnt[make_pair(two,five)]--;
		for(auto x:cnt){
			if(two+x.first.first>=0&&five+x.first.second>=0){
				ans+=x.second;
			}
		}
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}


Measured memory_bytes: 6360