akhauriyash/Code-Regression huggingface dataset:
// By Mohit Gupta
#include <bits/stdc++.h>
using namespace std;
#define printint(v) copy(begin(v), end(v), ostream_iterator<int>(cout," "))
#define printintv(s,e) copy(s,e, ostream_iterator<int>(cout," "))
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i = 0; i < e; i++)
#define forsn(i,s,e) for(int i = s; i < e; i++)
#define rforn(i,s) for(int i = s; i >= 0; i--)
#define rforsn(i,s,e) for(int i = s; i >= e; i--)
#define clz(a) __builtin_clz(a) // count leading zeroes
#define ctz(a) __builtin_ctz(a) // count trailing zeroes
#define popc(a) __builtin_popcount(a) // count set bits (for ints only diff for ll)
//https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html for other in built
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
typedef pair<int,int> p32; 
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
typedef map<int,int> m32;
#pragma GCC optimize ("-O2")
const int LIM = 5e5+5, MOD = 998244353;
int t,n,m,k,x,y;
 
 
int32_t main()
{
	IOS;
	cin>>n;
	int flag=0;
	while(n){
		if(n%10==7) flag=1;
		n/=10;
	}
	if(flag) cout<<"Yes"<<ln;
	else cout<<"No"<<ln;
}


Measured memory_bytes: 3636
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
  int N;
  cin >> N;
  
  vector<int> count(N + 1);
  for (int i = 2; i <= N; i++) {
    int n = i;
    for (int j = 0; j < i; j++) {
      if (count[j] > 0) {
        while(n % j == 0) {
          count[j]++;
          n /= j;
        }
      }
    }
    if (n > 1) {
      count[n]++;
    }
  }
  
  int count3 = 0, count5 = 0, count15 = 0, count25 = 0, count75 = 0;
  for (int i = 0; i <= N; i++) {
    if (count[i] >= 2) {
      count3++;
    }
    if (count[i] >= 4) {
      count5++;
    }
    if (count[i] >= 14) {
      count15++;
    }
    if (count[i] >= 24) {
      count25++;
    }
    if (count[i] >= 74) {
      count75++;
    }
  }
  
  int ans =
    count75 +
    count25 * (count3 - 1) +
    count15 * (count5 - 1) +
    (count5 * (count5 - 1)) / 2 * (count3 - 2);
  
  cout << ans << endl;
  

  return 0;
}


Measured memory_bytes: 256
N,M,X,Y = [int(x) for x in input().split()]
x = [int(x) for x in input().split()]
y = [int(x) for x in input().split()]

for Z in range(Y,X,-1):
  if max(x) < Z and min(y) >= Z:
    print('No War')
    exit()
  else:
    continue

print('War') 

Measured memory_bytes: 3060
using System;
using System.Linq;

namespace AOJ.Volume2
{
    public class OutcomeOfBonze
    {
        public static int Main()
        {
            while (true)
            {
                int n = int.Parse(Console.ReadLine());
                if (n == 0) { break; }

                string input = Console.ReadLine();

                int ba = 0;
                var point = new int[n];
                int current = 0;
                for(int i = 0; i < 100; i++)
                {
                    if (input[i] == 'M')
                    {
                        // ???
                        point[current]++;
                    }
                    else if (input[i] == 'L')
                    {
                        // ?§?
                        point[current] += ba + 1;
                        ba = 0;
                    }
                    else
                    {
                        // ??????
                        ba += point[current] + 1;
                        point[current] = 0;
                    }
                    current++;
                    if (current >= n) { current = 0; }
                }

                string output = "";
                foreach (int i in point.OrderBy(x => x)) { output += i + " "; }
                output += ba;
                Console.WriteLine(output);
            }

            return 0;
        }
    }
}

Measured memory_bytes: 10092
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#include <queue>
#include <deque>
#include <map>
#include <stack>
#include <cmath>
using namespace std;

#define mod 1000000007
#define ten5 100005
#define ten52 200005
#define ten6 1000005
#define PI 3.1415926
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()
#define mkpr(x1,x2) make_pair(x1,x2)
typedef long long int ll;


//stack<char> stk;
//set<ll> sll;
//set<pair<ll,ll>> spll;
//map<string,ll> mp;
//map<pair<ll,ll>,ll>::iterator iter;
//map<ll,ll> mp;
//deque<ll> deq;
//vector<ll> vll;
ll num[ten5],pp[ten52],mm[ten52];
//priority_queue<ll> pq;          //decreasing

int main(void)
{
    ll m,n,i,j,k=1;
    cin>>n;
    if(n%2==0 || n%5==0) cout<<-1;
    else
    {
        j=7%n;
        while(j!=0)
        {
            j=j*10+7;
            j%=n;
            k++;
        }
        cout<<k;
    }

    return 0;
}





Measured memory_bytes: 3640
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {

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

        int k = Integer.parseInt(scan.next());

        scan.close();

        Deque<Long> queue = new ArrayDeque<Long>();

        queue.add((long)1);
        queue.add((long)2);
        queue.add((long)3);
        queue.add((long)4);
        queue.add((long)5);
        queue.add((long)6);
        queue.add((long)7);
        queue.add((long)8);
        queue.add((long)9);

        int counter = 1;
        while (counter < k) {
            long curNum = queue.poll();
            long tailCurNum = curNum % 10;

            if (tailCurNum != 0) {
                queue.add(curNum * 10 + tailCurNum - 1);
            }

            queue.add(curNum * 10 + tailCurNum);

            if (tailCurNum != 9) {
                queue.add(curNum * 10 + tailCurNum + 1);
            }

            counter++;
        }

        System.out.println(queue.poll());
    }

}


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

int main(){
  int a,b,c,x,y;
  cin>>a>>b>>c>>x>>y;
  
  int sum;
  if(a+b<2*c){
    sum=a*x+b*y;
  }
  if(a+b>=2*c){
    int j=max(x,y);
    if(x<y){
      sum=min(2*j*c,2*x*c+b*(y-x));
    }else{
      sum=min(2*j*c,2*y*c+a*(x-y));
    }
  }
 
  cout<<sum<<endl;
}
  
    


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

using namespace std;

int main()
{
	int n, m;

	cin >> n >> m;
	
	vector<int> a;
	vector<int> b;
	int wka, wkb;


	for (int i = 0; i < m; i++) {
		cin >> wka >> wkb;
		a.push_back(wka);
		b.push_back(wkb);
	}

	for (int i = 0; i < n; i++) {
		int wkans = 0;
		for (int j = 0; j < m; j++) {
			if (a[j] == i+1)wkans++;
			if (b[j] == i+1)wkans++;
		}

		cout << wkans << endl;
	}


	return 0;



}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void) {
	string str;
	cin >> str;
	int res = 0;
	for (int i = 0; i < str.length()/2; ++i) {
		if (str[i] != str[str.length()-i-1]) {
			++res;
		}
	}
	cout << res << endl;
	return 0;
}


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

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
int main()
{
  int s,g,n,i,j,c;
  int number[5];
  scanf("%d" ,&s);
  scanf("%d",&g);
  c=0;
  while(s<=g){
    n=s;
    for(i=0;i<5;++i){
      j=pow(10,4-i);
      number[4-i]=n/j;
      n-=number[4-i]*j;
    }
    if(number[0]==number[4] && number[1]==number[3]) ++c;
    ++s;
  }
  printf("%d\n",c);
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define N 18
#define ll long long
const ll mod=1e9+7;

int n,m,nn;
int a[N];
ll f[N][1<<18],fac[1<<18],invf[1<<18],ans;

inline ll power(ll x,ll y) {
	ll res=1;
	for (;y;y>>=1,x=x*x%mod)
		if (y&1) res=res*x%mod;
	return res;
}
inline ll inv(ll x) {return power(x,mod-2);}
inline ll C(int x,int y) {
	if (x<y) return 0;
	return fac[x]*invf[x-y]%mod*invf[y]%mod;
}
inline int bitcount(int x) {
	int cnt=0;
	for (;x;x>>=1)
		if (x&1) cnt++;
	return (cnt&1) ? -1 : 1;
}

int main()
{
	scanf("%d%d",&n,&m); nn=1<<n;
	fac[0]=1; for (int i=1;i<=nn;i++) fac[i]=fac[i-1]*i%mod;
	invf[nn]=inv(fac[nn]);
	for (int i=nn-1;i>=0;i--) invf[i]=invf[i+1]*(i+1)%mod;
	
	for (int i=1;i<=m;i++) scanf("%d",&a[i]);
	reverse(a+1,a+m+1);
	
	f[0][0]=1;
	for (int i=0;i<=m;i++)
		for (int j=0;j<(1<<n);j++)
			if (f[i][j])
			{
				//printf("f[%d][%d]=%lld\n",i,j,f[i][j]);
				(f[i+1][j]+=f[i][j])%=mod;
				for (int k=1;k<(1<<n);k<<=1)
					if (!(j&k))
						(f[i+1][j|k]+=f[i][j]*C((1<<n)-j-a[i+1],k-1)%mod*fac[k]%mod)%=mod;
			}
	
	for (int i=0;i<(1<<n);i++) (ans+=f[m][i]*fac[(1<<n)-i-1]%mod*bitcount(i)+mod)%=mod;
	printf("%lld\n",ans*(1ll<<n)%mod);
	return 0;
}

Measured memory_bytes: 39680
package main

import (
	"fmt"
	"math"
)

var used []bool
var perm []int
var tot float64
var pat int

type point struct {
	x, y float64
}

var points []point

func dist(a, b point) float64 {
	d := math.Sqrt((b.x-a.x)*(b.x-a.x) + (b.y-a.y)*(b.y-a.y))
	return d
}

func permutation1(pos, n int) {
	if pos == n {
		var d float64
		for i := 0; i+1 < len(perm); i++ {
			d += dist(points[perm[i+1]], points[perm[i]])
		}
		tot += d
		pat++
		return
	}
	for i := 0; i < n; i++ {
		if !used[i] {
			perm[pos] = i
			used[i] = true
			permutation1(pos+1, n)
			used[i] = false
		}
	}
	return
}

func main() {
	var n int
	fmt.Scan(&n)
	used = make([]bool, n)
	perm = make([]int, n)
	points = make([]point, n)
	for i := range points {
		fmt.Scan(&points[i].x, &points[i].y)
	}
	permutation1(0, n)
	fmt.Println(tot / float64(pat))
}


Measured memory_bytes: 512
import sys
input = sys.stdin.readline

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

target = 1
cnt = 0

for i in range(N-1):
    if a[i] == target:
        target += 1
    else:
        cnt +=1
if target == a[-1]:
    print(cnt)
elif target==1 and a[-1] != 1:
    print(-1)
else:
    print(cnt+1)


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

int main(){
    int h,m,s,S;
    cin >> S;
    h = S / 3600;
    m = (S - 3600*h) / 60;
    s = S % 60;
    cout << h << ":" << m << ":" << s << endl;
    return 0;
}


Measured memory_bytes: 3120
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
long long x[100010];
int main(){
	long long i,n,k,ans,c;
	cin >> n >> k;
	for(i=0;i<n;i++){
		cin >> x[i];
	}
	ans = 100000000000000;
	for(i=0;i<=n-k;i++){
		ans = min(min(abs(x[i]),abs(x[k+i-1]))+abs(x[k+i-1]-x[i]),ans);
	}
	
	cout << ans << endl;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

typedef long long LL;
const int maxn = 1e5;
vector<int> G[maxn+10];
int vis[maxn+10];
int n;

void init()
{
    for(int i = 1;i <= n;i++) {
        G[i].clear();
    }
    memset(vis, 0, sizeof(vis));
}

int main()
{
    int u, v, x, y;
    while(~scanf("%d", &n)) {
        init();
        for(int i = 1;i < n;i++) {
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        x = y = 0;

        queue<int> qe;
        qe.push(1);
        qe.push(n);
        vis[1] = 1;
        vis[n] = 2;
        while(!qe.empty()) {
            u = qe.front();
            qe.pop();
            for(int i = 0;i <(int)G[u].size();i++) {
                v = G[u][i];
                if(!vis[v]) {
                    vis[v] = vis[u];
                    qe.push(v);
                    if(vis[v] == 1) x ++;
                    else    y++;
                }
            }
        }

        if(x <= y) {
            printf("Snuke\n");
        }
        else {
            printf("Fennec\n");
        }
    }
    return 0;
}
/*
5
1 2
2 4
4 3
2 5
*/


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

long long gcd(long long x, long long y) {
    if(y == 0) return x;
    else return gcd(y, x % y);
}

int main() {
    int N, M; cin >> N >> M;
    vector<long long> A(N);
    for(int i=0; i<N; ++i) {
        cin >> A[i];
        A[i] /= 2;
    }

    long long lcm = A[0];
    for(int i=1; i<N; ++i) {
        if(lcm > M) {
            cout << 0 << endl;
            return 0;
        }
        lcm = (lcm / gcd(A[i], lcm)) * A[i];
    }

    for(int i=0; i<N; ++i) {
        if((lcm / A[i]) % 2 == 0) {
            cout << 0 << endl;
            return 0;
        }
    }

    cout << ((M / lcm) + 1) / 2 << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int,int>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) { return b?gcd(b, a%b):a;}
ll lcm(ll a, ll b) { return a*b/gcd(a,b);}
ll MOD=1000000007;

int main(){
  int a,b,m;cin>>a>>b>>m;
  vi aa(a),bb(b);
  rep(i,a) cin>>aa.at(i);
  rep(i,b) cin>>bb.at(i);
  int ans=5000000;
  rep(i,m){
    int x;cin>>x;x--;
    int y;cin>>y;y--;
    int c;cin>>c;
    chmin(ans,aa.at(x)+bb.at(y)-c);
  }
  sort(all(aa));
  sort(all(bb));
  chmin(ans,aa.at(0)+bb.at(0));
  cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include<stdio.h>

int a[50];

int fibo(int n) {
  if(n == 0 || n == 1)  return a[n] =1;
  if(a[n] != -1) return a[n];
  return a[n] = fibo(n-1) + fibo(n - 2);

}

int main () {
  int n,i;
  for (i = 0 ; i < 50 ; i++) a[i]=-1;
  scanf("%d",&n);
  printf("%d\n",fibo(n));
  return 0;
}

Measured memory_bytes: 1848
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  string S; cin>>S;
  vector<ll>A(S.size()+1);
  ll b=0;
  for(int i=0; i<S.size(); i++){
    if(S[i]=='<') b++;
    else b=0;
    A[i+1]=b;
  }
  b=0;
  for(int i=S.size()-1; i>=0; i--){
    if(S[i]=='>') b++;
    else b=0;
    A[i]=max(b,A[i]);
  }
  ll ans=0;
  for(int i=0; i<A.size(); i++){
    ans+=A[i];
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 4740
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(true){
            int n = sc.nextInt();
            if(n==0)break;
            Map<Integer,Integer>map =new HashMap<Integer,Integer>();
            for (int i = 0; i <= n; i++) {
                    map.put(i*i, i);
            }
            int ans=0;
            for (int i = 0; i <= n; i++) {
                if(i*i > n)break;
                for (int j = i; j <= n; j++) {
                    if(i*i + j*j> n)break;
                    for (int k = j; k <= n; k++) {
                        if(i*i + j*j + k*k> n)break;
                        int sum = n-(i*i+j*j+k*k);
                        if(map.containsKey(sum)){
                            if(map.get(sum) >= k){
                                ans++;
                            }
                        }
                    }
                }
            }
            System.out.println(ans);
        }
    }

}

Measured memory_bytes: 289556
package main

import (
	"fmt"
	"math"
)

func main() {
	var s string
	fmt.Scan(&s)

	var cnt,ma int
	for _, i := range s{
		if i=='A' || i=='C' || i=='G' || i=='T' {
			cnt++
		} else {
			cnt=0
		}
		ma = int(math.Max(float64(ma),float64(cnt)))
	}
	fmt.Println(ma)
}

Measured memory_bytes: 512
use std::io::{self, Stdin};
use std::str::{self, FromStr};
use std::error::Error;

fn exec() {
    let mut sc = Scanner::new();
    let n = sc.ne();
    let a: Vec<i64> = (0..n).map(|_| sc.ne()).collect();
    let mut mi = n * 10;
    let mut ma = 0;
    use std::cmp::*;
    for &x in &a {
        mi = min(mi, x);
        ma = max(ma, x);
    }
    if ma - mi > 1 {
        println!("No");
        std::process::exit(0);
    } else if ma == mi {
        if ma == n - 1 {
            println!("Yes");
        } else {
            let nn = 2 * ma;
            if nn <= n {
                println!("Yes");
            } else {
                println!("No");
            }
        }
    } else {
        let mut solo = 0;
        for &x in &a {
            if x == mi {
                solo += 1;
            }
        }
        if solo < ma && (ma - solo) * 2 + solo <= n {
            println!("Yes");
        } else {
            println!("No");
        }
    }
}

fn main() {
    const STACK: usize = 16 * 1024 * 1024;
    let _ = std::thread::Builder::new()
        .stack_size(STACK)
        .spawn(|| { exec(); })
        .unwrap()
        .join()
        .unwrap();
}

#[allow(dead_code)]
struct Scanner {
    stdin: Stdin,
    id: usize,
    buf: Vec<u8>,
}

#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            id: 0,
            buf: Vec::new(),
        }
    }
    fn next_line(&mut self) -> Option<String> {
        let mut res = String::new();
        match self.stdin.read_line(&mut res) {
            Ok(0) => None,
            Ok(_) => Some(res),
            Err(why) => panic!("error in read_line: {}", why.description()),
        }
    }
    fn next<T: FromStr>(&mut self) -> Option<T> {
        while self.buf.len() == 0 {
            self.buf = match self.next_line() {
                Some(r) => {
                    self.id = 0;
                    r.trim().as_bytes().to_owned()
                }
                None => return None,
            };
        }
        let l = self.id;
        assert!(self.buf[l] != b' ');
        let n = self.buf.len();
        let mut r = l;
        while r < n && self.buf[r] != b' ' {
            r += 1;
        }
        let res = match str::from_utf8(&self.buf[l..r])
                  .ok()
                  .unwrap()
                  .parse::<T>() {
            Ok(s) => Some(s),
            Err(_) => {
                panic!("parse error, {:?}",
                       String::from_utf8(self.buf[l..r].to_owned()))
            }
        };
        while r < n && self.buf[r] == b' ' {
            r += 1;
        }
        if r == n {
            self.buf.clear();
        } else {
            self.id = r;
        }
        res
    }
    fn ne<T: FromStr>(&mut self) -> T {
        self.next::<T>().unwrap()
    }
}

Measured memory_bytes: 10620
def test_function() :
	print(__name__) # __main__

#print("called :",test_function.__name__)
n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
C=[]
for i in range(m):
	b,c = map(int,input().split())
	C.append((b,c))
C = sorted(C,key = lambda x:x[1])
before = 0

for b,c in C[::-1]:
	cou = 0  
	#print("[before]=",before)
	for i in range(len(A)-before):
		if A[before+i] < c :
			A[before+i] = c
			cou += 1
			#print("A=",A)
		else :
			before += i+1
			break
		if cou == b:
			before += i+1
			break
print(sum(A))

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


int main() {
	
	int n;
	cin >> n;
	string t;
	cin >> t;
	for(int i=0; i<t.size(); i++){
		char s = t.at(i);
		cout << (s+n<='Z' ? (char)(s+n) : (char)(s+n-26));
	}
	cout << endl;
	
	return 0;
}

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

int main(){
   
    int N;
    cin >> N;
    int ans = 0;
    for(int i = 1; i <= N; i++) {
        int n = i;
        int sum = 0;
        while(n > 0) {
            n /= 10;
            sum++;
        }
        if(sum % 2 == 1) ans++;
    }

    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define FPEN freopen("in.txt", "r", stdin);
#define debug(...)                                                             \
    { cerr << "# " << __VA_ARGS__ << "\n"; }
#else
#define debug(...)
#define FPEN
#endif
const int maxn = 200009;
typedef long long i64;
typedef pair<i64, i64> pi64;
typedef pair<int, int> pi;
const i64 MOD = 119 << 23 | 1;
class {
  public:
    void solve() {
        double L;
        cin >> L;
        printf("%.10f\n", L * L * L / 27);
    }
} NSPACE;
int main() {
    FPEN;
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    NSPACE.solve();
}

Measured memory_bytes: 256
/** Which of the favors of your Lord will you deny ? **/

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

#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define MP make_pair
#define F first
#define S second

#define ALL(x) (x).begin(), (x).end()
#define DBG(x) cerr << __LINE__ << " says: " << #x << " = " << (x) << endl
#define READ        freopen("alu.txt", "r", stdin)
#define WRITE       freopen("vorta.txt", "w", stdout)

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class TIn>using indexed_set = tree<TIn, null_type, less<TIn>,rb_tree_tag, tree_order_statistics_node_update>;

/**

PBDS
-------------------------------------------------
1) insert(value)
2) erase(value)
3) order_of_key(value) // 0 based indexing
4) *find_by_order(position) // 0 based indexing

**/

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p);
template <class T>
ostream &operator <<(ostream &os, vector<T>&v);
template <class T>
ostream &operator <<(ostream &os, set<T>&v);

inline void optimizeIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int nmax = 2e5+7;
const LL LINF = 1e17;

template <class T>
string to_str(T x)
{
    stringstream ss;
    ss<<x;
    return ss.str();
}

//bool cmp(const PII &A,const PII &B)
//{
//
//}

int match[25][25];

const LL mod = 1e9+7;

void add_self(LL &a,LL b)
{
    a += b;
    if(a>=mod) a -= mod;
}

int main()
{
    optimizeIO();

    int n;
    cin>>n;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>match[i][j];

    vector<LL>dp(1<<n);

    dp[0] = 1;

    for(int mask=0;mask<(1<<n)-1;mask++)
    {
        int m = __builtin_popcount(mask); /// number of already matched men = number of already matched women

        for(int w=0;w<n;w++)
        {
            if(match[m][w] && !(mask&(1<<w))) /// this woman is not matched yet and can be matched with m+1 th man
                add_self(dp[mask|(1<<w)],dp[mask]);
        }
    }

    cout<<dp[(1<<n)-1]<<endl;

    return 0;
}

/**

**/

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p)
{
    os<<"{"<<p.first<<", "<<p.second<<"} ";
    return os;
}
template <class T>
ostream &operator <<(ostream &os, vector<T>&v)
{
    os<<"[ ";
    for(int i=0; i<v.size(); i++)
    {
        os<<v[i]<<" " ;
    }
    os<<" ]";
    return os;
}

template <class T>
ostream &operator <<(ostream &os, set<T>&v)
{
    os<<"[ ";
    for(T i:v)
    {
        os<<i<<" ";
    }
    os<<" ]";
    return os;
}




Measured memory_bytes: 19556
/*input
3
1 4
4 6
7 8
*/
#include "bits/stdc++.h"
using namespace std;
int n;
pair<long long,long long> a[55];

int check(int p, int q){
	int res = 0;
	set<pair<int,int>> s;
	for(int i=1;i<=n;++i){
		res += !s.count(a[i]);
		s.insert({a[i].first+p,a[i].second+q});
	}
	return res;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=1,x,y;i<=n;++i){
		cin>>a[i].first>>a[i].second;
	}

	sort(a+1,a+n+1);
	int ans = n;
	for(int i=1;i<=n;++i)
		for(int j=i+1;j<=n;++j){
			ans = min(ans,check(a[j].first-a[i].first,a[j].second-a[i].second));
		}
	cout<<ans;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scan(&s)

	n := len(s)
	n1 := (n - 1) / 2
	n2 := (n + 3) / 2

	s1 := s[:n1]
	s2 := s[n2-1 : n]

	if reverse(s) == s && reverse(s1) == s1 && reverse(s2) == s2 {
		fmt.Println("Yes")
		return
	}

	fmt.Println("No")
}

func reverse(s string) string {
	rs := []rune(s)
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		rs[i], rs[j] = rs[j], rs[i]
	}
	return string(rs)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for (int i=a; i<(b);++i)
const int INF = 1e9;

int dist[210][210];

int N,M,R,a,b,c;
int main(){
    cin >> N >> M >> R;
    vector<int> r(R);
    REP(i,R) cin >> r[i];
    REP(i,N){
        REP(j,N) dist[i][j] = INF;
        dist[i][i] = 0;
    }

    REP(i,M){
        cin >> a >> b >> c;
        --a;--b;
        dist[a][b] = c;
        dist[b][a] = c;
    }
    REP(k,N)
        REP(i,N)
            REP(j,N)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    int ans = INF;
    sort(r.begin(),r.end());
    do {
       int t = 0;
       REP(i,r.size()-1) t += dist[r[i+1]-1][r[i]-1];
       ans = min(ans, t);
    } while(next_permutation(r.begin(),r.end()));
    cout << ans << endl;
}

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

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

	vector<pair<pair<string, int>, int>> in(N);
	for (int i = 0; i < N; i++) {
		cin >> in[i].first.first >> in[i].first.second;
		in[i].second = i + 1;
	}

	sort(in.begin(), in.end());

	vector<int> ans;
	ans.emplace_back(0);
	int s = 0;
	for (int i = 1; i < N; i++) {
		if (in[i].first.first != in[i - 1].first.first) {
			ans.emplace_back(i);
			for (int j = i - 1; j >= ans[s]; j--) {
				cout << in[j].second << endl;
			}
			s++;
		}

	}

	for (int i = in.size() - 1; i >= ans[s]; i--) {
		cout << in[i].second << endl;
	}

	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define mem(a,k) memset(a,k,sizeof(a))
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define fore(i,v) for(int i=g[v],d=es[i].d;i;i=es[i].nxt,d=es[i].d)
using namespace std;

void read(int &x){ scanf("%d",&x); }

const int N=5e5+50,K=20,oo=1e9;

int suc[N],n,m,v,a[K],x[N],frw[1<<K],bkw[1<<K],R[K][N],L[K][N]; 

int main(int argc,char *argv[]){
#ifdef CURIOUSCAT
	freopen("dat.in","r",stdin);
	//freopen("my.out","w",stdout);
#endif
	read(n),read(v);
	rep(i,1,n){
		read(x[i]);  
	}
	//Range a[0,m]
	for(;v;v>>=1)a[m++]=v;
	rep(k,0,m){
		L[k][0]=1,L[k][1]=1;
		rep(i,2,n)L[k][i]=x[i]-x[i-1]<=a[k]?L[k][i-1]:i;
		R[k][n+1]=n,R[k][n]=n;
		dec(i,n-1,1)R[k][i]=x[i+1]-x[i]<=a[k]?R[k][i+1]:i;
	}
	fill(frw,frw+(1<<m),0); 
	fill(bkw,bkw+(1<<m),n+1); 
	lop(s,0,(1<<m)){
		lop(i,0,m)if((s>>i&1)^1){
			cmax(frw[s+(1<<i)],R[i+1][frw[s]+1]);
			cmin(bkw[s+(1<<i)],L[i+1][bkw[s]-1]);
		}
	}
	lop(s,0,(1<<m)){
		int p=((1<<m)-1)^s;
		int i=frw[s],j=bkw[p];
		if(R[0][i+1]>=j-1)suc[R[0][i+1]]=true;
	}
	rep(i,1,n)puts(suc[R[0][i]]?"Possible":"Impossible");
	return 0;
}


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

const int INF=1e9+5;
const int N=1000+5;
const int mod=1e9+7;


int main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
	// freopen("input.txt","r",stdin);
	int n;
	cin>>n;
	vector<double> dp(n+1);
	dp[0]=1;
	for(int coin=0;coin<n;++coin){
		double val;
		cin>>val;
		for(int i=coin+1;i>=0;--i){
			dp[i]=(!i?0:dp[i-1]*val)+dp[i]*(1-val);
		}
	}
	double ans=0;
	for(int head=(n+1)/2;head<=n;++head){
		ans+=dp[head];
	}
	cout<< setprecision(10)<<ans;
	return 0;
}
		


Measured memory_bytes: 256
def select_sort(array):
    N = len(array)
    count = 0
    
    for i in range(N - 1):
        min_i = i + array[i:].index(min(array[i:]))
        if i != min_i:
            count += 1
        array[i], array[min_i] = array[min_i], array[i]
        
    return array, count

n = int(input())
array = [int(i) for i in input().split()]
result = select_sort(array)

print(*result[0])
print(result[1])

Measured memory_bytes: 7756
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
#ifdef DEBUG
#include "../program_contest_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<60;

int main(void) {
    ll n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    b -= a, a = 0;

    REP(i, n) {
        // i回足す n-1-i回引く
        // ic-(n-1-i)*d以上 i*d-(n-1-i)*c以下はつくれる
        ll lb = i*c - (n-1-i)*d, ub = i*d - (n-1-i)*c;
        if(lb <= b && b <= ub) {
            cout << "YES" << endl;
            return 0;
        }
    }

    cout << "NO" << endl;

    return 0;
}

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

using namespace std;
using llong = long long;
using ldbl = long double;
using P = pair<int, int>;

#define BE(x) x.begin(), x.end()

const llong inf = llong(1e18)+7;
const llong mod = 1e9+7;

int main(){
	llong H, W, N;
	vector<P> black, masu;

	cin >> H >> W >> N;
	int h,w;
	for(int i = 0; i < N; i++){
		cin >> h >> w;
		black.push_back(P(h,w));
		for(int sh = h-2; sh <= h; sh++){
			for(int sw = w-2; sw <= w; sw++)
				if(1 <= sh && sh <= H-2 && 1 <= sw && sw <= W-2)
					masu.push_back(P(sh,sw));
		}
	}

	sort(BE(black));
	sort(BE(masu));
	masu.erase(unique(BE(masu)), masu.end());

	vector<llong> ans(10,0);
	ans[0] = (H-2)*(W-2) - masu.size();
	for(auto it = masu.begin(); it != masu.end(); it++){
		int res = 0;
		for(int h = it->first; h <= it->first+2; h++)
			for(int w = it->second; w <= it->second+2; w++)
				if(*lower_bound(BE(black), P(h,w)) == P(h,w))
					res++;
		ans[res]++;
	}

	for(auto x : ans)
		cout << x << endl;

	return 0;
}

Measured memory_bytes: 11372
A,B,M = map(int,input().split())
p = list(map(int,input().split()))
q = list(map(int,input().split()))

ans = min(p)+min(q)
for i in range(M):
  x,y,c = map(int,input().split())
  x,y = x-1,y-1
  tmp = p[x]+q[y]-c
  ans = min(ans,tmp)
  
print(ans)  
  

Measured memory_bytes: 18612
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <string>
#include <cctype>
#include <map>

using namespace std;

const int mod = 1000000007;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
#define ll long long

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

    int diff = b - a;

    int height = 0;
    for (int i = 1; i < diff; i++)
    {
        height += i;
    }
    
    cout << height - a << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;
typedef complex<ld> com;
constexpr int inf = 1000000000;
constexpr ll INF = 1000000000000000000;
constexpr ld EPS = 1e-12;
constexpr ld PI = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }

int dp[50][500][500];

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);

	int n, ma, mb;
	cin >> n >> ma >> mb;
	vector<int> a(n), b(n), c(n);
	rep(i, n) cin >> a[i] >> b[i] >> c[i];
	rep(i, n + 1) rep(j, 500) rep(k, 500) dp[i][j][k] = inf;
	dp[0][0][0] = 0;
	rep(i, n) {
		rep(j, 500) {
			rep(k, 500) {
				chmin(dp[i + 1][j][k], dp[i][j][k]);
				if (j >= a[i] && k >= b[i]) chmin(dp[i + 1][j][k], dp[i][j - a[i]][k - b[i]] + c[i]);
			}
		}
	}
	int ans = inf;
	rep(j, 500) {
		rep(k, 500) {
			if (j == 0 || k == 0) continue;
			if (j * mb == k * ma) chmin(ans, dp[n][j][k]);
		}
	}
	cout << (ans == inf ? -1 : ans) << '\n';
}

Measured memory_bytes: 41216
#include <iostream>
#include <vector>
#include <algorithm>

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

using namespace std;

typedef long long int lli;

int main () {
    int N;
    cin >> N;
    vector<vector<int>> A(N, vector<int>(N));
    lli ans = 0;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        cin >> A[i][j];
        ans += A[i][j];
    }

    bool check = true;
    for (int s = 0; s < N; s++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (A[i][j] > A[i][s] + A[s][j]) {
                    check = false;
                }
            }
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            bool isSame = false;
            for (int s = 0; s < N; s++) {
                if (i == s || s == j) continue;
                if (A[i][j] == A[i][s] + A[s][j]) {
                    isSame = true;
                }
            }
            if (isSame) {
                ans -= A[i][j];
            }
        }
    }
    if (!check) {
        cout << -1 << endl;
    } else {
        cout << ans / 2 << endl;
    }
    return 0;
}


Measured memory_bytes: 640
import std.stdio;
import std.algorithm;

void main(){
	string s;
	int n;
	int[][string] index;
	while (readf("%s %d\n", &s, &n)) {
		index[s] ~= n;
	}
	auto keys = sort!("a < b")(index.keys);
	foreach (key; keys) {
		writeln(key);
		auto values = sort!("a < b")(index[key]);
		write(values[0]); values.popFront();
		foreach (value; values) {
			write(" ", value);
		}
		writeln();
	}
}

Measured memory_bytes: 1084
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ll long long
#define BIT_FLAG_0 (1<<0) // 0000 0000 0000 0001
#define BIT_FLAG_1 (1<<1) // 0000 0000 0000 0010
#define BIT_FLAG_2 (1<<2) // 0000 0000 0000 0100
#define BIT_FLAG_3 (1<<3) // 0000 0000 0000 1000
#define BIT_FLAG_4 (1<<4) // 0000 0000 0001 0000
#define BIT_FLAG_5 (1<<5) // 0000 0000 0010 0000
#define BIT_FLAG_6 (1<<6) // 0000 0000 0100 0000
#define BIT_FLAG_7 (1<<7) // 0000 0000 1000 0000

int main(){
    string s;
    cin >> s;
    rep(i,s.length()){
        if(s[i]-'0'==7){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

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

int main(){
	int n;
	int a[110];
	cin>>n;

	for(int i = 0; i < n;i++) cin>>a[i];

	int res =1000000;

	for(int i = -100; i <=100; i++){
		int sum = 0;
		for(int j = 0; j < n;j++){
			int sq = a[j] - i;
			sum += (sq*sq);
		}
		res = min(res,sum);
		
	}
	cout<<res<<"\n";


}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define enld '\n'
#define rep(i,n) for(int i=0; i<(n); i++)
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[6] = {1, 0, -1, 0,1,1};
const int dy[6] = {0, 1, 0, -1,1,-1};
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(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i,N) cin >> A[i];
    map<int,int> pre,suf;
    vector<int> ans;
    for(int i=0; i<N; i++){
        pre[A[i]]++;
        suf[A[N-1-i]]++;
        if(pre == suf) ans.emplace_back(i);
    }
    for(int i=0; i<ans.size(); i++){
        cout << ans[i]+1 << " \n"[i+1 == ans.size()];
    }
    return 0;
}


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

vector<bool> c;
vector<int> s;
vector<vector<int>> v;

void dfs(int n) {
  for(auto nn : v[n]) {
    if(c[nn]) {
      c[nn] = false;
      s[nn] += s[n];
      dfs(nn);
    }
  }
}
int main() {
  int N, Q, a, b, p, x;cin >> N >> Q;
  c.assign(N, true);
  s.assign(N, 0);
  v.resize(N);
  rep(i, N-1) {
    cin >> a >> b;
    a--;
    b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  rep(i, Q) {
    cin >> p >> x;
    s[p-1] += x;
  }
  c[0] = false;
  dfs(0);
  for(auto y : s) cout << y << " ";
}

Measured memory_bytes: 24284
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
int main()
{
    int K;
    cin >> K;
    int x = 7%K;
    set<int> s;
    int i = 1;
    while(s.count(x) == 0){//まだ訪れていない場合続ける
        if(x==0){
            cout << i << endl;
            return 0;
        }
        s.insert(x);
        x = (x*10+7)%K;
        ++i;
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 50468
l = [int(i) for i in input().split() ]
N = l[0]
L = l[1]

words = []
_ap = words.append
for i in range(N) :
	_ap(input())

out_str = ""
_rm = words.remove
while True :
	min_word = min(words)
	out_str += min(words)
	_rm(min_word)
	
	if (len(words) == 0) :
		break;

print(out_str)



Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i ++)
#define irep(i,n) for (int i = (int)(n) - 1;i >= 0;--i)
using namespace std;
using ll = long long;
using PL = pair<ll,ll>;
using P = pair<int,int>;
constexpr int INF = 1000000000;
constexpr long long HINF = 1000000000000000;
constexpr long long MOD = 1000000007;// = 998244353;
constexpr double EPS = 1e-4;
constexpr double PI = 3.14159265358979;

using PS = pair<string,string>;
map<PS,ll> count_string(const string &a,int flag) {
    int N = a.size();
    map<PS,ll> cnt;
    rep(bit,1<<N) {
        string s,t;
        rep(i,N) {
            if ((bit>>i)&1) s += a[i];
            else t += a[i];
        }
        reverse(t.begin(),t.end());
        if (flag == 0) cnt[make_pair(s,t)] ++;
        else cnt[make_pair(t,s)] ++;
    }
    return cnt;
}

int main() {
    int N; cin >> N;
    string s; cin >> s;
    map<PS,ll> left = count_string(s.substr(0,N),0);
    map<PS,ll> right = count_string(s.substr(N,N),1);
    
    ll ans = 0;
    for (auto &p:right) {
        ans += left[p.first] * p.second;
    }
    cout << ans << '\n';
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<vector<ll>> VV;
typedef vector<vector<int>> VVi;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
const ll INF=1e18+18;
const ll MAX=100005;
const ll MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;}
#define dbgarr(n,m,arr) rep(i,n){rep(j,m){cerr<<arr[i][j]<<" ";}cerr<<endl;}
#define dbgdp(n,arr) rep(i,n){cerr<<arr[i]<<" ";}cerr<<endl;
#define sum(v) accumulate(ALL(v),0)
#define fi first
#define se second

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

template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}


bool ok(ll n) {
    ll x = n;
    ll y = n;
    bool ok = true;
    bool ok2 = true;
    while (x > 1) {
        if(x % 6 == 0 ){
            x /= 6;
        }else{
            ok = false;
            break;
        }
    }
    while (y > 1) {
        if(y % 9 == 0 ){
            y /= 9;
        }else{
            ok2 = false;
            break;
        }
    }
    return ok||ok2;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<std::setprecision(10);

    ll n;
    cin>>n;
    Vec v;
    REP(i,6,n+1){
        if(ok(i)){
            v.pb(i);
        }
    }
    ll ans = INF;

    rep(i,n+1){
        ll x = i;
        ll k = n-i;
        ll tmp = 0;

        while (x>0){
            tmp += x%6;
            x /= 6;
        }

        while (k>0){
            tmp += k%9;
            k /= 9;
        }
        chmin(ans,tmp);
    }

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


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

#define _GLIBCXX_DEBUG
#define all(v) (v).begin(),(v).end()

using namespace std;

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

const ll LINF=1LL<<60;
const int INF=1<<29;
const int MOD=2019;

int main(){
    int H, W, K; cin >> H >> W >> K;
    vector<vector<char>> c(H, vector<char>(W));
    for(int i=0; i<H; i++){
        for(int j=0; j<W; j++){
            cin >> c[i][j];
        }
    }
    ll ans=0;
    for(int R; R<(1<<H); R++){
        for(int C=0; C<(1<<W); C++){
            int cnt=0;
            for(int i=0; i<H; i++){
                if(~R & (1<<i)) continue;
                for(int j=0; j<W; j++){
                    if(~C & (1<<j)) continue;
                    if(c[i][j] == '#') cnt++;
                }
            }
            if(cnt == K) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<complex>
#define lol(i,n) for(ll i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;
using namespace std;
#define N 200010
bool t[N];
string s;
priority_queue<ll> Q[26];
ll n;

ll at[N];
ll Bit[N];
void Update(int i,int x){
	i++;
	while(i<=n){
		Bit[i]+=x;
		i+=i&-i;
	}
}
ll Sum(int i){
	ll ret=0;
	i++;
	while(i){
		ret+=Bit[i];
		i-=i&-i;
	}
	return ret;
}
ll Bubble_Sort(){
	//lol(i,n)cout<<at[i]<<" ";
	//cout<<endl;
	lol(i,N)Bit[i]=0;
	ll ans=0;
	for(int i=0;i<n;i++){
		ans+=Sum(n-1)-Sum(at[i]);
		Update(at[i],1);
	}
	return ans;
}

int main(){
	cin>>s;n=s.size();
	lol(i,n)t[i]=true;
	
	ll odds=0,cnt[26]={0};
	lol(i,n){
		cnt[s[i]-'a']++;
	}
	lol(i,26){
		if(cnt[i]%2==1){
			ll x=0;
			for(ll j=0;j<n;j++){
				if(s[j]=='a'+i){
					x++;
					if(x==(cnt[i]+1)/2){
						t[j]=false;
						at[j]=n/2;
					}
				}
			}
			odds++;
		}
		ll x=0;
		for(ll j=0;j<n;j++){
			if(s[j]=='a'+i){
				x++;
				if(x>(cnt[i]+1)/2){
					Q[i].push(j);
				}
			}
		}
	}
	
	if(odds>1){
		cout<<"-1"<<endl;
		return 0;
	}
	
	ll left=0,right=n-1;
	for(ll i=0;i<n;i++){
		if(t[i]==false)continue;
		ll j=Q[s[i]-'a'].top();
		Q[s[i]-'a'].pop();
		t[i]=false,t[j]=false;
		at[i]=left,at[j]=right;
		left++,right--;
	}
	cout<<Bubble_Sort()<<endl;
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;

vector<pll> items;
ll best;

bool cmp(const pll &a,const pll &b)
{
    ll x=a.first*b.second,y=a.second*b.first;
    if(x!=y)    return x>y;
    else    return a.first>b.first;
}

pair<ll,bool> estimate(int i,ll w)
{
    ll res=0;
    bool flag=true;
    for(;i<items.size()&&w>0;i++)
    {
        if(items[i].second>w)
        {
            res+=items[i].first*w/items[i].second;
            flag=false;
        }else
        {
            res+=items[i].first;
        }
        w-=items[i].second;
    }

    return make_pair(res,flag);
}

void dfs(int i,ll v,ll w)
{
    if(w<0) return;
    if(i>=items.size())
    {
        best=max(best,v);
        return;
    }
    pair<ll,bool> ub=estimate(i,w);
    if(ub.first+v<=best)    return;
    if(ub.second)
    {
        best=ub.first+v;
        return;
    }
    dfs(i+1,v+items[i].first,w-items[i].second);
    dfs(i+1,v,w);
}


int main()
{
    int N,W;
    while(cin>>N>>W)
    {
        items.clear();
        for(int i=0;i<N;i++)
        {
            ll v,w,m;
            cin>>v>>w>>m;
            for(ll j=1;m>0;j<<=1)
            {
                ll mul=min(j,m);
                m-=mul;
                if(mul*w>W) break;
                items.emplace_back(mul*v,mul*w);
            }
        }
        sort(items.begin(),items.end(),cmp);
        best=0;
        dfs(0,0,W);
        cout<<best<<endl;
    }

    return 0;
}



Measured memory_bytes: 3132
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> P;

int color[100000];
map<int, vector<P>> mp;
queue<int> q;

int main(){
    int n, u, v, w, i, cur;
    cin >> n;
    for(i=0; i<n; i++){
        color[i] = -1;
    }
    for(i=1; i<n; i++){
        cin >> u >> v >> w;
        mp[u-1].push_back(P(v-1, w));
        mp[v-1].push_back(P(u-1, w));
    }
    color[0] = 0;
    q.push(0);
    while(!q.empty()){
        cur = q.front();
        q.pop();
        for(i=0; i<mp[cur].size(); i++){
            if(color[mp[cur][i].first] == -1){
                if(mp[cur][i].second%2){
                    color[mp[cur][i].first] = color[cur]^1;
                }else{
                    color[mp[cur][i].first] = color[cur];
                }
                q.push(mp[cur][i].first);
            }
        }
    }
    for(i=0; i<n; i++){
        cout << color[i] << "\n";
    }
    return 0;
}

Measured memory_bytes: 12288
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, M: int, A: "List[int]"):
    summation = sum(A)

    result = 0
    for n in range(N):
        if A[n] >= summation * (1 / (4 * M)):
            result += 1
    if result >= M:
        print(YES)
    else:
        print(NO)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()


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

int main(){
 int a, b, C;
 double S, L, h, d;
 cin >> a >> b >> C;

 d=(acos(-1.0)*C)/180.0;
 S=a*b*sin(d)/2.0;
 L=a+b+sqrt(a*a+b*b-2*a*b*cos(d));
 h=b*sin(d);
 printf("%lf\n%lf\n%lf\n", S, L, h);
return 0;
}


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

int n,h[110000],f[110000];
int main(){   
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&h[i]);
    }
    f[1]=0;
    f[2]=abs(h[1]-h[2]);
    for(int i=3;i<=n;i++){
        f[i]=min(f[i-1]+abs(h[i]-h[i-1]),f[i-2]+abs(h[i]-h[i-2]));
    } 
    printf("%d",f[n]);    
    return 0;
}

Measured memory_bytes: 1024