akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>

#include <numeric>

#include <map>

using namespace std;

typedef long long LL;

int a[10][10];

int n, cnt;

int main() {
   for (int i = 1; i <= 3; ++i)
    for (int j = 1; j <= 3; ++j)
      cin >> a[i][j];

   cin >> n;
   for (int k = 1; k <= n; ++k) {
       int x;
       cin >> x;
       for (int i = 1; i <= 3; ++i)
        for (int j = 1; j <= 3; ++j) {
            if (a[i][j] == x) {
                a[i][j] = 0;
            }
        }
       
   }
   bool ok = false;
   if (a[1][1] == 0 && a[2][2] == 0 && a[3][3] == 0) ok = true;
   if (a[1][3] == 0 && a[2][2] == 0 && a[3][1] == 0) ok = true;

   if (a[1][1] == 0 && a[1][2] == 0 && a[1][3] == 0) ok = true;
   if (a[2][1] == 0 && a[2][2] == 0 && a[2][3] == 0) ok = true;
   if (a[3][1] == 0 && a[3][2] == 0 && a[3][3] == 0) ok = true;

   if (a[1][1] == 0 && a[2][1] == 0 && a[3][1] == 0) ok = true;
   if (a[1][2] == 0 && a[2][2] == 0 && a[3][2] == 0) ok = true;
   if (a[1][3] == 0 && a[2][3] == 0 && a[3][3] == 0) ok = true;

  if (ok)cout<<"Yes"; else cout << "No";
    
}

Measured memory_bytes: 256
<?php
$n = (int)trim(fgets(STDIN));
$works = [];
for ($i=0; $i < $n; $i++) { 
	$input = explode(' ', trim(fgets(STDIN)));
	$works[] = [
		(int)$input[0],
		(int)$input[1],
	];
}

usort($works, function($a, $b){
	return $b[1] - $a[1];
});
$end = $works[0][1];

foreach ($works as $w) {
	if ($w[1] < $end) {
		$end = $w[1];
	}
	$end -= $w[0];
}
if ($end < 0) {
	echo 'No';
}else{
	echo 'Yes';
}

Measured memory_bytes: 95088
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int main()
{
	int N;
	cin >> N;
	printf("%.6f\n", ((N + 1) / 2) / (double)N);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define ALL(x) x.begin(), x.end()
 
typedef long long int lld;
typedef pair<int, int> pii;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(15);
	cout << fixed;
 
	int n = 0;
	cin >> n;

	vector<int> vec(n);
	
	lld sum = 0;
	for (auto &x : vec)
		cin >> x, sum += x;

	vector<int> ans(n);

	for (int i = 0; i < n - 1; i += 2) {
		sum -= vec[i] * 2;
	}

	ans[n - 1] = sum;
	ans[0] = vec[n - 1] * 2 - ans[n - 1];

	for (int i = 0; i < n - 2; i++) {
		ans[i + 1] = vec[i] * 2 - ans[i];
	}

	for (int i = 0; i < n; i++) {
		if (i)
			cout << ' ';
		cout << ans[i];
	}

	cout << '\n';


	
 
	return 0;
}

Measured memory_bytes: 2176
import sys

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")


s=input()

if s[0] == s[1] and s[2] == s[3] and s[2] == s[0]:
    print('No')
elif s[0] == s[1] and s[2] == s[3]:
    print('Yes')
elif s[0] == s[2] and s[1] == s[3]:
    print('Yes')
elif s[0] == s[3] and s[1] == s[2]:
    print('Yes')
else:
    print('No')



Measured memory_bytes: 3064
#include<stdio.h>
#include<string.h>
int main()
{
    int n;
    char S[6];
    gets(S);
    n=strcmp(S,"Sunny");
    if(n==0)
    {
        printf("Cloudy\n");
    }
    n=strcmp(S,"Cloudy");
    if(n==0)
    {
        printf("Rainy\n");
    }
    n=strcmp(S,"Rainy");
    if(n==0)
    {
        printf("Sunny\n");
    }
    return 0;
}

Measured memory_bytes: 128
import java.util.*;
import java.awt.*;
import static java.lang.System.*;
import static java.lang.Math.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int X=sc.nextInt();
        int Y=sc.nextInt();
        int[] x=new int[n];
        for (int i = 0; i < n; i++) {
            x[i]=sc.nextInt();
        }
        int[] y=new int[m];
        for (int i = 0; i < m; i++) {
            y[i]=sc.nextInt();
        }
        Arrays.sort(x);
        Arrays.sort(y);
        if(x[n-1]<y[0]&&X<y[0]&&x[n-1]<Y){
            out.println("No War");
        }else{
            out.println("War");
        }
    }
    //階乗
static long fact(long a){
    long b=1;
    for (long i = 1; i <= a; i++) {
        b*=i;
    }
    return b;
}
//最大公約数
static int gcd (int a, int b) {
    int temp;
    while((temp = a%b)!=0) {
        a = b;
        b = temp;
    }
    return b;
}
//※最小公倍数はa*b/gcd(a,b)である
//二項係数
static long combi (long a, long b) {
    b=min(a-b,b);
    return permu(a,b)/fact(b);
}
//順列
static long permu(long a,long b){
    long temp=1;
    for (long i =a ; i > a-b; i--) {
        temp*=i;
    }
    return temp;
}
}

Measured memory_bytes: 23764
#include <iostream>
#include <cstdio>
using namespace std;
char a[101][101];
int fm[101];
int fn[101];
void init()
{
    for(int i=0;i<101;i++){
        fm[i]=1;
        fn[i]=1;
    }
}
int main()
{
    int m,n;
    init();
    cin>>m>>n;
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }
    int flagm=1;
    int flagn=1;
    int indexm=-1;
    int indexn=-1;
    for(int i=0;i<m;i++){
        flagm=1;
        for(int j=0;j<n;j++){
            if(a[i][j]=='#'){
                flagm=0;
            }
        }
        if(flagm>0){
            fm[i]=0;
        }
    }
    for(int i=0;i<n;i++){
        flagn=1;
        for(int j=0;j<m;j++){
            if(a[j][i]=='#'){
                flagn=0;
            }
        }
        if(flagn>0){
            fn[i]=0;
        }
    }
    for(int i=0;i<m;i++){
        if(fm[i]){
            for(int j=0;j<n;j++){
                if(fn[j])
                    cout<<a[i][j];
            }
            cout<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int i;

    //入力
    int n;
    scanf("%d", &n);
    int R[n];
    for( i = 0; i < n; ++i )
        scanf("%d", &R[i]);

    //minが最小になるようにmaxを選ぶ
    int min = R[0], max = R[1] - R[0];
    for( i = 1; i < n; ++i ){
        max = max < R[i] - min ? R[i] - min : max;
        min = min > R[i] ? R[i] : min; //minは後から更新しないと R[i]-min == min-min になる
    }

    printf("%d\n", max);

    return 0;
}


Measured memory_bytes: 2648
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, A, B, P1, P2;
  cin >> N >> A >> B;
  
  P1 = A * N;
  P2 = B;
  
  if (P1 < P2) {
    cout << P1 << endl;
  }
  else{
    cout << P2 << endl;
  }
}

Measured memory_bytes: 3608
#!/usr/bin/env python3

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

i = 1
ans = 0
flg = False
while A[i] != 0 and not flg:
    if i == 2:
        flg = True
    else:
        ans += 1
        tmp = i
        i = A[i]
        A[tmp] = 0

if flg:
    print(ans)
else:
    print(-1)




Measured memory_bytes: 12916
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#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 REVERSE(v,n) reverse(v,v+n);
#define llong long long
#define pb(a) push_back(a)
#define INF 9999999

using namespace std;

typedef pair<int,int> P;

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

int main(){
	int n,m,x;
	cin>>n>>m>>x;
	int a[100];
	REP(i,n){
		a[i]=0;
	}
	REP(i,m){
		int k;
		cin>>k;
		a[k]=1;
	}
	int p1=0;
	REP(i,x){
		p1+=a[i];
	}
	int p2=0;
	for(int i=x;i<n;i++){
		p2+=a[i];
	}
	cout<<min(p1,p2)<<endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] num = new int[N+1];
        int count = 0;
        for(int i = 1; i <= N;i++){
            num[i] = i;
            if(String.valueOf(num[i]).length() % 2 == 1){
                count++;
            }
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 25940
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    int N; cin>>N;
    vint a(N);
    REP(i,N) cin>>a[i];

    sort(ALL(a),greater<int>());

    int fst=0,scd=0;
    for(int i=0;i<N-1;i++){
        if(a[i]==a[i+1]){
            scd=fst;
            fst=a[i];
            i++;
            if(scd>0) break;
        }
    }
    cout<<fst*scd<<endl;

}


Measured memory_bytes: 1024
package main

import (
    "fmt"
    "os"
    "bufio"
    "strings"
    "strconv"
)

func main() {
    var fp *os.File = os.Stdin
    reader := bufio.NewReaderSize(fp, 1024)

    line := readLine(reader)
    N, _ := strconv.Atoi(line)
    line = readLine(reader)
    arr := strings.Split(line, " ")
    var nums []int = make([]int, N)

    for k, v := range arr {
        val, _ := strconv.Atoi(v)
        nums[val-1] = k + 1
    }

    for i := 0; i < N; i++ {
        fmt.Print(nums[i])

        if i != N -1 {
            fmt.Print(" ")
        }
    }
}

func readLine(reader *bufio.Reader) string {
    buf := make([]byte, 0, 1024)

    for {
        l, p, _ := reader.ReadLine()

        buf = append(buf, l...)

        if !p {
            break
        }
    }

    return string(buf)
}

Measured memory_bytes: 7680
fact = [1]
for i in range(1, 101):
    fact.append(fact[-1]*i)
    
def C(a, b):
    return fact[a]//(fact[b]*fact[a-b])

def sC(a, b):
    ret = 0
    for i in range(min(b, a-b) + 1):
        ret += C(b, i) * C(a - b, i)
    return ret

def calc(n, k):
    if n<=0:
        return []
    i = 0
    while (1<<(i+1)) -1 <= n:
        i += 1
        
    ret = [str(k)] * (i+1)
    rem = n-((1<<i) - 1)
    kk = k + 1
    i += 1
    j = i // 2
    
    while j > 0:
        while True:
            tmp = sC(i, j)
            if tmp <= rem:
                ret.insert(j, str(kk))
                ret.append(str(kk))
                kk += 1
                rem -= tmp

            else:
                break
                
        j -= 1
        
    return ret + calc(rem, kk)

N = int(input())

X = calc(N, 1)
print(len(X))
print(" ".join(X))


Measured memory_bytes: 3064
from sys import setrecursionlimit


def f(i, links, dp):
  if dp[i] != -1:
    return dp[i]
  if len(links[i]) == 0:
    dp[i] = 0
  else:
    dp[i] = max(f(j, links, dp) for j in links[i]) + 1
  return dp[i]


setrecursionlimit(1000000)

N, M = map(int, input().split())

links = [[] for _ in range(N)]
for _ in range(M):
  x, y = map(int, input().split())
  links[x - 1].append(y - 1)

dp = [-1] * N
print(max(f(i, links, dp) for i in range(N)))


Measured memory_bytes: 121392
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rep2(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define rev(i, n) for (int (i) = (n)-1; (i) >= 0; (i)--)
#define rev2(i, a, b) for (int (i) = (a)-1; (i) >= (b); (i)--)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define yn {puts("Yes");}else {puts("No");}
using namespace std;
using ll = long long;
using P = pair<int, int>;
using Pll = pair<long long, long long>;
template<class T> using Vec = vector<T>;
template<class T> using VVec = vector<vector<T>>;
long long TEN(int i) {return !i ? 1 : TEN(i-1)*10LL;}
template<class T, class U> 
bool chmin(T& a, const U& b) {if (a > b) {a = b; return 1;} return 0;}
template<class T, class U> 
bool chmax(T& a, const U& b) {if (a < b) {a = b; return 1;} return 0;}

void debug_out() {cout << endl;}
template<typename Head, typename...Tail>
void debug_out(Head H, Tail... T) {
	cout << H << " ";
	debug_out(T...);
}
#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif


struct IoSetup {
	IoSetup() {
		cin.tie(nullptr);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(10);
	}
} iosetup;

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~//

int H, W, D, Q;
int A[305][305];
int L[100005], R[100005];

void solve() {
	map<int, P> memo;
	rep (i, H) rep (j, W) memo[A[i][j]] = {i, j};
	Vec<ll> sums[D + 1];
	rep2 (i, 1, D + 1) {
		sums[i].pb(0);
		for (int j = i + D; j <= H * W; j += D) {
			sums[i].pb(abs(memo[j - D].fi - memo[j].fi) + abs(memo[j - D].se - memo[j].se));
		}
		rep (j, sums[i].size()) sums[i][j + 1] += sums[i][j];
	}

	rep (i, Q) {
		int use = (R[i] % D == 0 ? D : R[i] % D);
		cout << sums[use][R[i] / D - (R[i] % D == 0)] - sums[use][L[i] / D - (R[i] % D == 0)] << endl;
	}
}

int main() {
	cin >> H >> W >> D;
	rep (i, H) rep (j, W) cin >> A[i][j];
	cin >> Q;
	rep (i, Q) cin >> L[i] >> R[i];
	solve();
	
	return 0;
}

Measured memory_bytes: 15252
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(ll i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(ll i=(begin);i>(end);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define ISORT(a) sort(a.begin(), a.end(),greater<ll>())
#define REVERSE(a) reverse(a.begin(), a.end())

#define ll long long
#define f first
#define s second
using namespace std;

using vec = vector<ll>;
using mat = vector<vec>;
using Pii = pair<ll, ll>;
using PiP = pair<ll, Pii>;
using PPi = pair<Pii, ll>;

int main()
{
	// 入力
	ll N,A,B,C,D;
	cin >> N>>A>>B>>C>>D;
	A--;
	B--;
	C--;
	D--;
	string S;
	cin>>S;
	FOR(i,A,C){
		if(S[i]=='#' && S[i+1]=='#') {
			cout<<"No"<<endl;
			return 0;
		}
	}
	FOR(i,B,D){
		if(S[i]=='#' && S[i+1]=='#') {
			cout<<"No"<<endl;
			return 0;
		}
	}

	bool exists=false;
	if(D<C){
		FOR(i,B-1,D){
			if(S[i]=='.' && S[i+1]=='.' && S[i+2]=='.') {
				exists=true;
				break;
			}
		}
		if(!exists){
			cout<<"No"<<endl;
			return 0;
		}
	}

	cout<<"Yes"<<endl;

	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
  
using namespace std;
  
#define MAX 50
  
int N, day;
bool ok[MAX][31];
bool visited[MAX];
  
void init(){
  day = 0;
  memset(ok, false, sizeof(ok));
}
  
int solve(){
  int ans = -1;
  set<int> dp[MAX];
 
  for(int i = 0 ; i < N ; i++){
    dp[i].insert(i);
  }
 
  for(int i = 0 ; i <= day ; i++){
    for(int j = 0 ; j < N-1 ; j++){
      if(!ok[j][i]) continue;
      for(int k = j+1 ; k < N ; k++){
        if(ok[k][i]){
          set<int>::iterator it;
          for(it = dp[j].begin() ; it != dp[j].end() ; ++it){
            dp[k].insert(*it);
          }
          for(it = dp[k].begin() ; it != dp[k].end() ; ++it){
            dp[j].insert(*it);
          }
        }
      }
      if(dp[j].size() == N) return i+1;
    }
  }
  return ans;
}
  
int main(){
  int K, in;
  while(cin >> N && N){
    init();
    for(int i = 0 ; i < N ; i++){
      cin >> K;
      for(int j = 0 ; j < K ; j++){
        cin >> in;
        ok[i][in-1] = true;
        day = max(day, in);
      }
    }
    cout << solve() << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1308
#include <iostream>
#include <iomanip>
#include<math.h>
#include<list>
#include <algorithm>
#include<set>
#include<vector>
#include<math.h>
#include<map>
#include<string>
#include <numeric>
#include <queue>
#include <sstream>
#include <bitset>
#include<stack>

using namespace std;
using ll = long long;
using vll = vector<long long>;
using sll = set<long long>;

template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

template<typename T>
map<T, T> getPrimeFactor(T n) {
	map<T, T> res;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			res[i] ++;
			n /= i;
		}
	}
	if (n != 1) res[n] = 1;
	return res;
}

template<typename T>
bool IsPrimeNumber(T num)
{
	if (num <= 2) return true;
	else if (num % 2 == 0) return false;

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


#define in(x) cin >> x
#define out(x) cout << x
#define outn(x) cout << x << '\n'
#define outs(x) cout << x << ' '
#define rep(i,s,e) for(ll i=s;i<e;i++)
#define repeq(i,s,e) for(ll i=s;i<=e;i++)

int main() {
	ll N, M, a, b, c;
	std::cin >> N >> M;
	vector<vll> t(N + 1, vll(N + 1, 1e9));
	vector<vector<vector<pair<ll, ll>>>> e(N + 1, vector<vector<pair<ll, ll>>>(N + 1));
	repeq(i, 1, N) {
		t[i][i] = 0;
	}

	rep(i, 0, M) {
		std::cin >> a >> b >> c;
		t[a][b] = c;
		t[b][a] = c;
		e[min(a, b)][max(a, b)].push_back(make_pair(min(a, b), max(a, b)));
	}

	repeq(k, 1, N) {
		repeq(i, 1, N) {
			repeq(j, 1, N) {
				if (t[i][j] > t[i][k] + t[k][j]) {
					t[i][j] = t[i][k] + t[k][j];

					e[i][j] = {};
					std::copy(e[i][k].begin(), e[i][k].end(), std::back_inserter(e[i][j]));
					std::copy(e[k][j].begin(), e[k][j].end(), std::back_inserter(e[i][j]));
				}
			}
		}
	}

	ll ans = M;
	map<ll, map<ll, bool>> dic;
	repeq(i, 1, N) {
		repeq(j, 1, N) {
			rep(k, 0, e[i][j].size()) {
				if (!dic[e[i][j][k].first][e[i][j][k].second]) {
					dic[e[i][j][k].first][e[i][j][k].second] = true;
					ans--;
				}
			}
		}
	}

	std::cout << ans << endl;

	return 0;

}


Measured memory_bytes: 5376
S = input()


ki = ['R', 'U', 'D']
gu = ['L', 'U', 'D']

c = 0
for s in range(len(S)):
    if s % 2 == 0:
        if S[s] in ki:
            c += 1
    else:
        if S[s] in gu:
            c += 1
# print(c)
if c == len(S):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);

		ArrayList<Integer> list = new ArrayList<Integer>();

		boolean  flg = true;

		while (flg) {
	        list.add(Integer.valueOf(scanner.nextInt()));
	        for(int i=0; i<list.size(); i++){
	        	if(list.get(i) == 0){
	        		list.remove(i);
	        		flg = false;
	        		break;
	        	}
	        }
		}

		//Case 1: 3
		for(int i=0; i<list.size(); i++){
			System.out.println("Case " + (i+1) + ": " + list.get(i));
		}

	}
}

Measured memory_bytes: 40124
N = int(input())

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

while True:
  K = 0
  for i in range(N):
    if D[i] % 2 == 0:
      K += 1
  if K == N:
    for j in range(N):
      D[j] = D[j] / 2
    A += 1
  else:
    break

print(A)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;

const lint mod = 1e9 + 7;
const int d = (1<<17) - 1;
lint dp[2][1<<17];

lint powmod(lint x, lint n){
  lint ret = 1;
  while(n > 0){
    if(n&1) ret *= x, ret %= mod, n -= 1;
    else x *= x, x %= mod, n >>= 1;
  }
  return ret;
}

int main(){
    int n, x, y, z;
    scanf("%d%d%d%d", &n, &x, &y, &z);
    rep(i, 2)rep(j, 1<<17) dp[i][j] = 0;
    dp[0][1] = 1;
    rep(i, n){
        rep(j, 1<<17)if(dp[0][j]){
            For(k, 1, 11){
                lint t = ((lint)j << k) | 1;
                if(((t>>(x)) & 1) && ((t>>(x+y)) & 1) && ((t>>(x+y+z)) & 1)) continue;
                (dp[1][t & d] += dp[0][j]) %= mod;
            }
        }
        rep(j, 1<<17){
            dp[0][j] = dp[1][j];
            dp[1][j] = 0;
        }
    }
    lint cnt = 0;
    rep(j, 1<<17) (cnt += dp[0][j]) %= mod;
    printf("%lld\n", (powmod(10, n) - cnt + mod) % mod);
}

Measured memory_bytes: 2432
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


d, g = LI()
g //= 100
p, c = list(zip(*LIR(d)))
c = [c[i] // 100 for i in range(d)]



ans = INF
for i in range(2 ** d):
    cnt = 0
    score = 0
    for j in range(d):
        if 1 << j & i:
            cnt += p[j]
            score += (j + 1) * p[j]
            score += c[j]


    max_score = -INF
    for k in range(d):
        if not (1 << k) & i:
            max_score = max(max_score, k + 1)
    if score < g:
        remain_num = (g - score) // max_score + bool((g - score) % max_score)
        if remain_num >= p[max_score - 1]:
            continue
        cnt += remain_num
    ans = min(ans, cnt)


print(ans)

Measured memory_bytes: 43504
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	int p[10];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>p[i];
	}
	sort(p,p+n);
	int ans=0;
	for(int i=0;i<n;i++){
		if(i!=n-1){
			ans+=p[i];
		}else{
			ans+=p[i]/2;
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;

ll a[55], cnt = 0;

int main(){
    int n;
    cin >> n;
    rep(i, n) cin >> a[i];    

	while(true) {
		rep(i, n) {
            if(a[i] < n) continue;
			ll tmp = a[i] / n;
			cnt += tmp;
			a[i] -= tmp * n;
			rep(j, n) {
                if (i != j) a[j] += tmp;
            }
		}
        bool flag = 0;
        rep(i, n) flag |= (a[i] >= n);
        if(!flag) break;
	}
	cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3644
//Nihal Mittal - nihal_47
//Strike First , Strike Hard , No Mercy !!

/**⠀⠀⠀⠀⠀⠀⣀⣤⣤⣄⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⣀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⣰⣿⣿⣿⣿⠿⠿⣿⣿⣿⣿⣿⣿⣿⣧⢀⠀⠀⠀⠀
⠀⠀⠀⣿⣿⣿⠋⠀⠀⠀⠀⠀⠙⠀⠙⣿⣿⣿⣷⢳⢀⠀⠀⠀
⠀⠀⣠⣿⣿⣿⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⢀
⠀⠀⣸⣿⣿⣿⠸⠀⠀⠀⠒⠒⠒⠐⠀⠀⢿⣿⣿⣿⣿⣿⠀⠀
⠀⣴⣿⣿⣿⡿⠀⠒⣋⣙⡒⢰⠀⠤⣖⠒⢾⣿⣿⣿⣿⣧⠀⠀
⢺⣿⣿⣿⣿⢀⠀⠀⠉⠉⠉⠸⠀⡇⠉⠉⠀⢿⣿⣿⣿⣄⠀⠀
⠀⠙⣿⣿⣧⢻⠀⠀⠀⠀⠀⠠⠀⠰⠀⠀⠀⣸⠸⣿⣿⠿⠰⠀
⠀⠀⠀⠹⣿⣿⣿⣷⠀⡠⠙⣲⣔⣅⢡⣰⣷⣿⣿⣿⣧⠀⠀⠀
⠀⠀⠀⣼⣿⣿⣿⣿⠀⡿⠭⠭⠭⠭⢿⠀⣿⢻⣿⣿⠃⠀⠀⠀
⠀⠀⠀⠙⠛⣿⢻⠹⣿⠐⠙⠛⠟⠉⢀⣴⡟⢿⣿⡏⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⡟⠀⠀⠻⣦⣤⣶⠾⠋⠀⠀⠁⡦⢄⢀⠀⠀⠀
⠀⠀⠀⠀⡠⠁⡇⠑⢄⠀⠀⠀⠀⠀⠀⠔⠀⠀⠁⠀⠀⠀⠉⠁
⠀⠔⠊⠁⠀⠀⣇⠀⠀⠀⠑⡤⠤⢎⠁⠀⠀⡘⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢢⠠⠀⡠⢆⠀⠀⡠⠙⢄⠀⡸⠀
**/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define mk make_pair
#define pb push_back
#define in insert
#define se second
#define fi first
#define mod 1000000007
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define all(v) (v).begin(),(v).end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define pii pair<ll,ll>
#define vi(x) vector<x>
#define maxn 100005
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
using namespace std;
using namespace __gnu_pbds;

signed main()
{
    fast;
   
    string s;
    cin>>s;
    ll n = s.length(),di=1,di1=1,ans=0;
    reverse(all(s));
    ll i,j,sum=0;
    map<ll,ll> ma;
    ll a[n+2];
    for(i=0;i<n;i++)
    {
    	ll da = s[i] - '0';
    	a[i] = (da%2019 * di%2019)%2019;
    	di = (di * 10LL)%2019;
    }
    for(i=0;i<n;i++)
    {
    	sum += a[i];
    	ma[((sum%2019) + 2019 )%2019]++;
    }
    for(i=0;i<2019;i++)
    {
    	if(ma[i]>1)
    	{
    		ans += (ma[i] * (ma[i]-1)) / 2;
    	}
    }
    ans += ma[0];
    cout<<ans;




}

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

ll l1[100005];

int main()
{
    ll n,k;
    cin>>n>>k;
    ll a,b,y=0,x=0;
    for(int i=1;i<=n;i++){
        cin>>a>>b;
        x+=b;
        //if(x>=m&&y==0)y=a;
        l1[a]+=b;
    }
    for(int i=1;i<=100000;i++){
        if(k<=l1[i]){
            cout<<i<<endl;return 0;
        }
        k-=l1[i];
    }
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i ,n) for(int i = 0 ; i < (n) ; i ++ )
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using vin=vector<int>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;

int main() {
 int n;
  cin>>n;
  map<string,int> mp;
  int mx=0;
  rep(i,n){
    string s;
    cin>>s;
    mp[s]++;
    mx=max(mx,mp[s]);
  }
  for(auto v:mp){
   if(v.second==mx) cout<<v.first<<endl; 
    
  }
  
}

Measured memory_bytes: 25216
from collections import deque

n = int(input())
to = [[0] for _ in range(n)]
cost = [[0] for _ in range(n)]
for i in range(n - 1):
    a, b, w = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
    cost[a].append(w)
    cost[b].append(w)

q = deque()
q.append(0)
ans = [-1] * n
ans[0] = 0

while len(q):
    v = q.pop()
    for i in range(len(to[v])):
        u = to[v][i]
        w = cost[v][i]

        if ans[u] != -1:
            continue
        ans[u] = (ans[v] + w) % 2
        q.append(u)
for i in range(n):
    print(ans[i])


Measured memory_bytes: 83576
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <string.h>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define FOR(i,n,m) for(int i=n; i<m; i++)
#define ROF(i,n,m) for(int i=n; i>m; i--)
#define ri(a) scanf("%d",&a)
#define rii(a,b) ri(a),ri(b)
#define riii(a,b,c) rii(a,b),ri(c)
#define lri(a) scanf("%lld",&a)
#define lrii(a,b) lri(a),lri(b)
#define lriii(a,b,c) lrii(a,b),lri(c)
#define pb push_back
#define _1 first
#define _2 second
#define ALL(s) s.begin(),s.end()
#define SZ(x) int((x).size())

const int INF = 0x3f3f3f3f;
const ll INFLL = 1e18;
const int MOD = 1e9+7;
const int alphabet = 26;
const double PI = 3.1415926535;
const int MAXINT = 1e5+1;

int main(){
	int n, k, h[MAXINT];

	rii(n,k);
	FOR(i,0,n) ri(h[i]);

	int dp[n]; dp[n-1] = 0;
	ROF(i,n-2,-1){
		dp[i] = INF; int k2 = 1;
		while(i+k2<n && k2<=k){			
			dp[i] = min( dp[i], abs(h[i]-h[i+k2]) + dp[i+k2] ); 
			k2++;
		}
	}
	printf("%d\n", dp[0]);
	return 0;
}
/*

*/  


Measured memory_bytes: 4500
# -*- coding:utf-8 -*-

n = int(input())
str = input()
str = str.split()
a = []
for i in range(n):
    a.append(int(str[i]))

count = 0
for i in range(n):
    min = i
    for j in range(i,n):
        if a[j] < a[min]:
            min = j

    tmp = a[min]
    a[min] = a[i]
    a[i] = tmp
    if a[min] != a[i]:
        count += 1
for i in range(n-1):
    print(a[i],end = ' ')
print(a[n-1])
print(count)

Measured memory_bytes: 7712
n,k=map(int,input().split())

am = [0]*k
for i in range(1, n+1):
  res = i%k
  if (res+res)%k==0:
    am[res]+=1

#print(am)

ans = 0
for i in am:
  ans += i**3 
  
print(ans)

Measured memory_bytes: 10376
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstdlib>

using namespace std;

void tswap(vector<int>& data, int a, int b, int N);

int main()
{
    int N;
    int cnt = 0;
    int flg = 0;
    cin >> N;

    vector<int> data(N);
    vector<int> data2(N);

    for (int i = 0; i < N; i++) {
        cin >> data.at(i);
    }

    for (int i = 0; i < N; i++) {
        data2.at(i) = data.at(i);
    }

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

    for (int i = 0; i < N; i++) {
        if (data.at(i) != data2.at(i) && cnt == 0) {
            // 入れ替え
            tswap(data, data.at(i), data2.at(i), N);
            // 1回しか実施できない
            cnt++;
        }
    }


    for (int i = 0; i < N; i++) {
        if (data.at(i) != data2.at(i)) {
            cout << "NO" << endl;   
            flg = 1;         
            break;
        }
    }

    if (flg == 0) {
        cout << "YES" << endl;   
    }


    return 0;
    
}

void tswap(vector<int>& data, int a, int b, int N)
{
    int tmp, num1, num2;

    for (int i = 0; i < N; i++) {
        if (data[i] == a) {
            num1 = i;
            tmp = data[i];
        } else if (data[i] == b) {
            num2 = i;
        }
    }

    tmp = data.at(num1);
    data.at(num1) = data.at(num2);
    data.at(num2) = tmp;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
using ll = long long;
using graph = std::vector<std::vector<ll>>;

using namespace std;

int main() {
    int N;
    string S;
    cin >> N >> S;
    ll count = 0;
    for(int i = 0; i < N - 2; i++){
        if(S[i] == 'A' && S[i + 1] == 'B' && S[i + 2] == 'C'){
            count++;
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 256
use strict;
use warnings;

my $k = <>;

my @num = split(', ', "1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51");

print $num[$k-1];



Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define FIND(s, e) ((s).find(e) != (s).end())
#define EB emplace_back
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

const int MAX = 1e5 + 10;
int N;
LL a, b;
LL h[MAX];
priority_queue<LL> pq;

bool check(LL num) {
    LL cnt = 0;
    REP(i, N) {
        if (num * b < h[i]) {
            LL buf = (h[i] - num * b);
            cnt += buf / (a - b) + (buf % (a - b) != 0);
        }
    }
    return cnt <= num;
}

int main(void) {
    scanf("%d%lld%lld", &N, &a, &b);
    REP(i, N) {
        scanf("%lld", h + i);
    }
    LL high = 1e10, low = 0;
    while (high - low > 1) {
        const LL mid = (high + low) / 2;
        if (check(mid)) high = mid;
        else low = mid;
    }
    while (!check(low)) ++low;
    cout << low << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

int main() {
	int a[5];
	for(int i=0; i<5; ++i) cin >> a[i];
	int ans=0, mx=0;
	for(int i=0; i<5; ++i){
	    ans += (a[i]+9)/10*10;
	    mx=max(mx, (a[i]+9)/10*10-a[i]);
	}
	cout << ans-mx << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long int n;
  cin >> n;
  long int p = sqrt(n);
  long int ans = 0;
  for(long int i = 1; i <= p; i++){
    if(n % i == 0) ans = max(ans, i);
  }
  long int q = n/ans;
  long int x = log10(q+1)+1;
  cout << x << endl;
}

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

int main(){

    int N;
    cin >> N;
    long int l[N],r[N],ans = 0;
    for(int i=0;i<N;i++){
        cin >> l[i] >> r[i];
        ans += r[i] - l[i] + 1;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int sum_a(int num[], int i);
int sum_b(int num[], int i, int n);

int main(void)
{
  int num[128],n,i,result = 1000,difference;
  char str[400],trush[4];
//数の個数を受け取る
  fgets(str,sizeof(str),stdin);
  sscanf(str,"%d",&n);
//n個の数を受ける
  for(i=0;i<n;++i)
  {
    scanf("%d",&num[i]);
  }

  scanf("%c", trush);
//分け方はn-1通り
//全ての分け方を試す
  for(i=0;i<n-1;++i)
  {
    difference = sum_a(num,i) - sum_b(num,i,n);
    if (difference < 0)
    {
      difference *= -1;
    }
//前より絶対値のさが小さければ更新
    if(result > difference)
    {
      result = difference;
    }
  }
//表示
  printf("%d", result);
  return 0;
}

int sum_a(int num[],int i)
{
  int j,sum=0;
  for (j=0;j<=i;++j)
  {
    sum += num[j];
  }
  return sum;
}

int sum_b(int num[],int i,int n)
{
  int j,sum = 0;
  for(j=i+1;j < n;j++)
  {
    sum += num[j];
  }
  return sum;
}


Measured memory_bytes: 128
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <climits>
#include <cmath>
#include <functional>
#include <map>
#include <queue>
#include <set>

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define size_t unsigned long long
#define ll long long
#define rep(i,a) for(int i=0;i<(a);i++)
#define repr(i,a) for(int i=(int)(a)-1;i>=0;i--)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(int)(b)-1;i>=a;i--)
#define ALL(a) a.begin(), a.end()
using namespace std;
int si() { int x; scanf("%d", &x); return x; }
long long sl() { long long x; scanf("%lld", &x); return x; }
string ss() { string x; cin >> x; return x; }
void pi(int x) { printf("%d ", x); }
void pl(long long x) { printf("%lld ", x); }
void pd(double x) { printf("%.15f ", x); }
void ps(const string &s) { printf("%s ", s.c_str()); }
void br() { putchar('\n'); }

const int MOD = 1e9 + 7;

struct mint {
    int n;
    mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; }
mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; }
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }

const int maxi = 1e6+10;
string s;
vector<int> v[maxi];
int n;
ll a[maxi];

int main () {
  cin >> n >> s;
  int count = n;
  rep(i,n) {
    if(s[i] == s[i+1]) count--;
  }

  cout << count << endl;
}


Measured memory_bytes: 25600
#include <bits/stdc++.h>
using namespace std;
int main() {
	string a, b;
	cin >> a;
	cin >> b;
	if(a.length() < b.length()) {
		cout << "LESS" << endl;
	} else if(b.length() < a.length()) {
		cout << "GREATER" << endl;
	} else {
		for(int i = 0; i < a.length(); i++) {
			int x = a[i] - '0';
			int y = b[i] - '0';
			if(x < y) {
				cout << "LESS" << endl;
				return 0;
			} else if(y < x) {
				cout << "GREATER" << endl;
				return 0;
			}
		}
		cout << "EQUAL" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
s = input()
k = int(input())

keys = []
for start in range(len(s)):
  for end in range(start+1, min(start+6, len(s)+1)):
    key = s[start:end]
    if key in keys:
      continue
    if len(keys) < 5:
      keys.append(key)
      keys.sort()
    elif keys[-1] > key:
      keys.append(key)
      keys.sort()
      keys = keys[:-1]
print(keys[k-1])

Measured memory_bytes: 3064
import sys
def f(c):
 if sum(c)in c:return 1
 if 5 in c:return 0
 if 4 in c:
  k=c.index(4);c[k]-=3
  if f(c):return 1
  c[k]+=3
 if 3 in c:
  k=c.index(3);c[k]-=3
  if f(c):return 1
  c[k]+=3
 for i in range(7):
  if c[i]and c[i+1]and c[i+2]:
   c[i]-=1;c[i+1]-=1;c[i+2]-=1
   if f(c):return 1
   c[i]+=1;c[i+1]+=1;c[i+2]+=1
n='123456789'
for e in sys.stdin:
 c=[list(e).count(j)for j in n]
 a=[]
 for i in range(9):
  t=c[:];t[i]+=1
  if f(t):a+=[i+1]
 if a:print(*a)
 else:print(0)


Measured memory_bytes: 5572
N, M = map(int, input().split())
A = []

K, *A_row_first = map(int, input().split())
set_A           = set(A_row_first)

for _ in range(N-1):

    K, *A_row = map(int, input().split())
    set_A     = set_A & set(A_row)

print(len(set_A))

Measured memory_bytes: 3060
distance,num = map(int, input().split())
tmp = input()
a = tmp.split()
a = list(map(int,a))
b = []

for i in range(len(a)-1):
    b.append(a[i+1] - a[i])
b.append(distance - a[i+1] + a[0])

b = sorted(b)
min = 0
for i in range(len(b)-1):
    min += b[i]

print(min)

Measured memory_bytes: 27228
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
ct=0
ans=0
for i in range(n):
  if ct+l[i][1]>=m:
    ans+=l[i][0]*(m-ct)
    break
  else:
    ct+=l[i][1]
    ans+=l[i][0]*l[i][1]
print(ans)

Measured memory_bytes: 27760
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,i;
	char c1[10],c2[10];
	scanf("%d %d",&a,&b);
	for(i=0;i<b;i++)	c1[i]=a+'0';
	c1[b]='\0';
	for(i=0;i<a;i++)	c2[i]=b+'0';
	c2[a]='\0';	
	if(strcmp(c1,c2)<0)	printf("%s\n",c1);
	else printf("%s\n",c2);
	return 0;
}

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

const int N = 1e5+7;

string s[N];
char ans[N];
int n;

void DFS(int x,int a,int b,int c)
{
	if(x>n){
		puts("Yes");
		for(int i=1;i<=n;i++) printf("%c\n",ans[i]);
		exit(0);
	}
	if(s[x]=="AB"){
		if(a) ans[x] = 'B', DFS(x+1,a-1,b+1,c);		//两个选择爆搜 
		if(b) ans[x] = 'A', DFS(x+1,a+1,b-1,c);
	}
	else if(s[x]=="AC"){
		if(a) ans[x] = 'C', DFS(x+1,a-1,b,c+1);
		if(c) ans[x] = 'A', DFS(x+1,a+1,b,c-1);
	}
	else {
		if(b) ans[x] = 'C', DFS(x+1,a,b-1,c+1);
		if(c) ans[x] = 'B', DFS(x+1,a,b+1,c-1);
	}
}


int main()
{
	int a,b,c;
	cin>>n>>a>>b>>c;
	for(int i=1;i<=n;i++) cin>>s[i];
	DFS(1,a,b,c);
	puts("No");
	return 0;
}

Measured memory_bytes: 14724
#include <iostream>
#include <string>
#include <map>

using namespace std;

int n;
int k[110];
string s;
map< char, int > cmap;
char c[55];

char parse(const char s, int k) {
	int p = cmap[s];
	p = (p-k+52)%52;
	return c[p];
}

void solve() {
	int size = (int)s.size();
	for (int i=0; i<size; i++) {
		s[i] = parse(s[i], k[i%n]);
	}
	cout << s << endl;
}

int main() {
	for (int i=0; i<26; i++) cmap['a'+i] = i;
	for (int i=0; i<26; i++) cmap['A'+i] = 26+i;
	for (int i=0; i<26; i++) c[i] = 'a' + i;
	for (int i=0; i<26; i++) c[26+i] = 'A' + i;
	
	while (1) {
		cin >> n; if ( n==0 ) break;
		for (int i=0; i<n; i++) cin >> k[i];
		cin >> s;
		solve();
	}
	
	return 0;
}

Measured memory_bytes: 1208
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <fstream>
#include <climits>
#include <cstdio>
#include <vector>
#include <string>
#include <memory>
#include <queue>
#include <cmath>
#include <list>
#include <set>
#include <map>


using namespace std;

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

map<int,int> m;

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int a;
        scanf("%d",&a);
        if(a>=1&&a<=399)
            m[1]++;
        else if(a<=799)
            m[2]++;
        else if(a<=1199)
            m[3]++;
        else if(a<=1599)
            m[4]++;
        else if(a<=1999)
            m[5]++;
        else if(a<=2399)
            m[6]++;
        else if(a<=2799)
            m[7]++;
        else if(a<=3199)
            m[8]++;
        else
            m[9]++;
    }
    
    int xres=0;
    int yres=0;
    if(m.count(9))
    {
        if(m.size()>1)
        {
            xres=(int)m.size()-1;
            yres=(int)(m.size()-1)+m[9];
        }
        else
        {
            xres=1;
            yres=m[9];
        }
    }
    else
    {
        xres=yres=(int)m.size();
    }
    cout<<xres<<" "<<yres<<endl;
    return 0;
}


Measured memory_bytes: 256
#pragma gcc optimize("Ofast")

#include "bits/stdc++.h"
using namespace std;
typedef int64_t lld;
const int mod = 1000000007;
vector<int> dp[2];
signed main(){
    int n, k, sqn;
    cin >> n >> k;
    sqn = pow(n, 0.5)-1;
    while(sqn*sqn <= n)sqn++;
    sqn--;
    int l = sqn*2 - (n/sqn == sqn? 1: 0);
    auto val = [&](int i){return i <= sqn ? i : n/(l+1-i);};
    dp[0].resize(l+1);
    dp[1].resize(l+1);
    dp[0][1] = 1;
    for(int i = 0; i < k; i++){
        int cnt = 0;
        for(int j = l; j > 0; j--)
            dp[1-i%2][j] = (cnt = (cnt + (lld)dp[i%2][l+1-j]*(val(l+1-j)-val(l-j))%mod) % mod);
    }
    int ans = 0;
    for(int i = 1; i <= l; i++)ans = (ans + (lld)dp[k%2][i]*(val(i)-val(i-1))%mod)%mod;
    cout << ans << endl;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}else{return false;}}
template<class T> inline bool chmax(T&a, T b){if(a < b){a = b; return true;}else{return false;}}
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1.0)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int d, score;
vector<int> c(26);
vector<vector<int>> s(400, vector<int>(26)), pos(26);

int get_score(vector<int> t){
    vector<int> pos(26, 0);
    int ans = 0;
    rep(i, t.size()){
        int l = i + 1 - pos[t[i]];
        ans -= (l * (l-1) / 2) * c[t[i]];
        ans += s[i][t[i]];
        pos[t[i]] = i+1;
    }
    rep(i, 26){
        int l = t.size() + 1 - pos[i];
        ans -= (l * (l-1) / 2)* c[i];
    }
    return ans;
}

int main() {
    cin >> d;
    rep(i, 26)cin >> c[i];
    rep(i, d)rep(j, 26)cin >> s[i][j];
    //-----code------// 
    vector<int> t, pos(26, 0);
    rep(i, d){
        int max_score = -mod;
        int best_j = -1;
        rep(j, 26){
            t.push_back(j);
            int score = get_score(t);
            if(max_score < score){
                best_j = j;
                max_score = score;
            }
            t.pop_back();
        }
        t.push_back(best_j);
    }
    vector<int> ans = t;
    double start_temp = 100, end_temp = 10;
    int current_max_score = get_score(t), i = 0;
    while(clock() < 1.95 * CLOCKS_PER_SEC){

        if(i % 2 == 0){
            int D = rand() % d, q = rand() % 26;
            int old = t[D];
            int olds = get_score(t);
            t[D] = q;
            int score = get_score(t);
            double temp = start_temp + (end_temp - start_temp) * clock() / (1.95 * CLOCKS_PER_SEC);
            double prob = exp((olds - score)/temp);

            if(chmax(current_max_score, score)){
                ans = t;
            }else{
                if(prob <= (double)(rand() % 10000) / 10000){
                    t[D] = old;
                }
            }

            if(prob >= ((rand()%inf)/(double)inf))t[D] = old;
        }else{
            int a = 5 + rand() % (d-10), b = 1 + rand() % 4;
            int olds = get_score(t);
            swap(t[a], t[b]);
            int score = get_score(t);
            double temp = start_temp + (end_temp - start_temp) * clock() / (1.95 * CLOCKS_PER_SEC);
            double prob = exp((olds - score)/temp);

            if(chmax(current_max_score, score)){
                ans = t;
            }else{
                if(prob <= (double)(rand() % 10000) / 10000){
                    swap(t[a], t[b]);
                }
            }
        }
        i++;
    }
    rep(i, d)cout << ans[i]+1 << endl;
}


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

int main(){
  string str;
	string tmp;
	vector<string> res_str;
	int K;
	cin >> str;
	cin >> K;
	for(int i=1;i<=K;i++){
    for(int j=0;j<str.length();j++){
			tmp = "";
			if(j+i<=str.length()){

			//cout << j+i << endl;
			for(int k=j;k<j+i;k++){
				tmp += str[k];
			}
			//cout << tmp << endl;
			//tmp = str.substr(j,i);
			//cout << tmp << endl;
			res_str.push_back(tmp);
			}
		}
	}
	sort(res_str.begin(), res_str.end());
	res_str.erase(unique(res_str.begin(),res_str.end()), res_str.end());
	cout << res_str[K-1] << endl;
	return 0;
}


Measured memory_bytes: 1660
//Using vim gui now
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void solve(int case_number) {
	long long x, answer = 0;
	cin >> x;
	long long start = 100;
	while(start < x) {
		answer++;
		start += start/100;
	}
	cout << answer << endl;
}

int main() {
	int cases = 1;
//	cin >> cases;
	for(int i = 0; i < cases; i++)
		solve(i + 1);
	return 0;
}


Measured memory_bytes: 3188
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define MAX 1000000007
using namespace std;

int ans[250000][4];

int main(void){
	int h,w;
	cin>>h>>w;
	int a[h+1][w+1];

	rep(i,h)rep(j,w)cin>>a[i+1][j+1];

	bool have=false;
	int num=0;

	int px,py;
	for(int x=1;x<h+1;x++){
		if(x%2==1){
			for(int y=1;y<w+1;y++){
				if(have){
					if(a[x][y]%2==1)have=false;
					//cout<<px<<" "<<py<<" "<<x<<" "<<y<<endl;
					ans[num][0]=px;
					ans[num][1]=py;
					ans[num][2]=x;
					ans[num][3]=y;
					num++;
				}
				else{
					if(a[x][y]%2==1)have=true;
				}
				px=x;
				py=y;
			}
		}
		else{
			for(int y=w;y>0;y--){
				if(have){
					if(a[x][y]%2==1)have=false;
					//cout<<px<<" "<<py<<" "<<x<<" "<<y<<endl;
					ans[num][0]=px;
					ans[num][1]=py;
					ans[num][2]=x;
					ans[num][3]=y;
					num++;
				}
				else{
					if(a[x][y]%2==1)have=true;
				}
				px=x;
				py=y;	
			}
		}
	}

	cout<<num<<endl;
	rep(i,num)cout<<ans[i][0]<<" "<<ans[i][1]<<" "<<ans[i][2]<<" "<<ans[i][3]<<endl;
	return 0;
}


Measured memory_bytes: 4992
require 'prime'

def main
    n = gets.to_i
    factors = n.prime_division

    ans = 0
    factors.each do |factor|
        full = factor[1]
        cnt = 1
        while 1
            full -= cnt
            break if full < 0
            cnt += 1
        end
        ans += cnt-1
    end
    puts ans
end

main


Measured memory_bytes: 14500
//============================================================================
    // Name        : test.cpp
    // Author      : Qihan
    // Version     :
    // Copyright   : Your copyright notice
    // Description : Hello World in C++, Ansi-style
    //============================================================================
     
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long int LLI;
    typedef pair<int,int> PII;
    const int maxs = (10000 + 10);
    int main(){
    //	freopen("/home/qihan/Documents/in","r",stdin);
    	LLI x,y;
    	scanf("%lld",&x);
    	LLI cnt = x / 11 * 2;
    	y = x % 11;
    	if(y > 6)	cnt += 2;
    	else if(y <= 6 && y >= 1)	cnt += 1;
    	printf("%lld\n",cnt);
    	return 0;
    }

Measured memory_bytes: 256