akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

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

		while (sc.hasNextLine()) {
			String[] param = sc.nextLine().split(",");

			double[] x = new double[4];
			double[] y = new double[4];

			for (int i = 0; i < x.length; i++) {
				x[i] = Double.parseDouble(param[0 + i * 2]);
				y[i] = Double.parseDouble(param[1 + i * 2]);
			}
			
			boolean flag = true;
			for (int i = 0; i < x.length; i++) {
				int p = i;
				int q = (i + 1) % x.length;
				
				int r = (i + 2) % x.length;
				int s = (i + 3) % x.length;

				double dx = x[q] - x[p];
				double dy = y[q] - y[p];

				double e0;
				double e1;
				
				if (dx == 0.0) {
					e0 = x[r] - x[p];
					e1 = x[s] - x[p];
				} else if (dy == 0.0) {
					e0 = y[r] - y[p];
					e1 = y[s] - y[p];
				} else {
					double a = (y[q] - y[p]) / (x[q] - x[p]);
					double b = y[p] - a * x[p];
	
					e0 = a * x[r] + b - y[r];
					e1 = a * x[s] + b - y[s];
				}
				if (!(((e0 > 0.0) && (e1 > 0.0)) || ((e0 < 0.0) && (e1 < 0.0)))) flag = false;
			}

			if (flag == true) System.out.println("YES");
			else System.out.println("NO");
		}
	}
}

Measured memory_bytes: 26016
import java.util.Scanner;

class Main {

public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		// get a integer
		int num1 = sc.nextInt();
		int num2 = sc.nextInt();
		
		int total = getAreaTriangle(num1,num2);
		
		System.out.println(total);
	}
	
	public static boolean isMaxNum(int num) {
		return num > 100 ? true : false;
	}
	
	
	public static int getAreaTriangle(int num1,int num2) {
		
		if(isMaxNum(num1) || isMaxNum(num2) ) {
			return 0;
		}
		
		return  (num2 * num1) / 2; 
	}
	
}


Measured memory_bytes: 21844
package main

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

func main() {
	reader := bufio.NewReader(os.Stdin)
	var ant [5]int
	for i := 0; i < 5; i++ {
		tmp, _ := reader.ReadString('\n')
		tmp = strings.Trim(tmp, "\n")
		ant[i], _ = strconv.Atoi(tmp)
	}
	tmp, _ := reader.ReadString('\n')
	tmp = strings.Trim(tmp, "\n")
	k, _ := strconv.Atoi(tmp)

	min := ant[0]
	max := ant[0]

	for i := 0; i < 5; i++ {
		if min > ant[i] {
			min = ant[i]
		}
		if max < ant[i] {
			max = ant[i]
		}
	}

	if (max - min) > k {
		fmt.Println(":(")
	} else {
		fmt.Println("Yay!")
	}
}


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

int main() {

    int a,b,c;
    cin >> a >> b >> c;

    int tmp;
    tmp = a;
    a = b;
    b = tmp;

    tmp = a;
    a = c;
    c = tmp;

    printf("%d %d %d\n",a,b,c);

}

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

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

  if (a % 2 == 0) {
    cout << "Even" << endl;
  }
  else if (b % 2 == 0){
    cout << "Even" << endl;
  }
  else {
    cout << "Odd" << endl;
  }
}

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

int main() {
  int n, k;
  cin >> n;
  k = pow(n, 0.5);
  cout << k*k << endl;
  return 0;
}

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

#define vi vector<int>
#define vl vector<long>
#define vvi vector<vector<int>>
#define vvl vector<vector<long>>
#define pint pair<int, int>
#define plong pair<long, long>

int main() {
    int N;
    cin>>N;
    long S = 0;
    REP(i, 1, N+1){
        if( i % 5 != 0 && i % 3 != 0) S += i;
    }
    cout << S << endl;
}

Measured memory_bytes: 3636
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<tuple>
#include<bitset>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-15
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
long long COM(int n,int k){
    if(n < k) return 0;
    if (n < 0 || k < 0) return 0;
	if(k==0||k==n) return 1;
	ll ans=1,bunsinow=max(k,n-k)+1,bunbog=min(k,n-k),bunbonow=1;
	while(1){
		if(ans%bunbonow==0&&bunbonow<=bunbog){
			ans/=bunbonow;
			bunbonow++;
		}
		else{
			ans*=bunsinow;
			bunsinow++;
		}
		if(bunsinow>n&&bunbonow>bunbog) return ans;
	}
}
int main(){
	int N,P;
	int A[50];
	int mod[2]={};
	scan(N);scan(P);
	rep(i,N){
		scan(A[i]);
		mod[A[i]%2]++;
	}
	ll ans=(1LL<<mod[0]);
	ll kisuu=0;
	for(int i=P;i<=mod[1];i+=2){
		kisuu+=COM(mod[1],i);
	}
	ans*=kisuu;
	prin(ans);
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static int process(TestCase testCase) {
        int A = testCase.A;
        int B = testCase.B;
        int C = testCase.C;

        return B + Math.min(A + B + 1, C);
    }

    // Util func

    public static void main(String[] args) {
        TestCase testCase = readFromInput();

        final int result = process(testCase);

        output(result);
    }

    private static TestCase readFromInput() {
        Scanner sc = new Scanner(System.in);

        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();

        sc.close();
        return new TestCase(A, B, C);
    }

    private static void output(int result) {
        System.out.println(result);
    }

    public static class TestCase {
        final int A;
        final int B;
        final int C;

        public TestCase(int A, int B, int C) {
            this.A = A;
            this.B = B;
            this.C = C;
        }
    }
}


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

S = [0] * 13
H = [0] * 13
C = [0] * 13
D = [0] * 13

n = int(raw_input())

for i in xrange(n):
	symbol, num = map(str, raw_input().split())
	if symbol == 'S':
		S[int(num)-1] = 1
	elif symbol == 'H':
		H[int(num)-1] = 1
	elif symbol == 'C':
		C[int(num)-1] = 1
	else:
		D[int(num)-1] = 1

cards = [S, H, C, D]
marks = ['S', 'H', 'C', 'D']

for card, mark in zip(cards, marks):
	for index, num in enumerate(card):
		if num < 1:
			print mark, index+1

Measured memory_bytes: 4248
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int X = sc.nextInt();
    int ans = 0;
    if(X >= 400 && X < 600) ans = 8;
    else if(X >= 600 && X < 800) ans = 7;
    else if(X >= 800 && X < 1000) ans = 6;
    else if(X >= 1000 && X < 1200) ans = 5;
    else if(X >= 1200 && X < 1400) ans = 4;
    else if(X >= 1400 && X < 1600) ans = 3;
    else if(X >= 1600 && X < 1800) ans = 2;
    else  ans = 1;

    System.out.println(ans);
    sc.close();
  }
}

Measured memory_bytes: 35668
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; 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 ll long long
#define pb(a) push_back(a)

int main(){
 int n, m, x, y;
 cin >> n >> m >> x >> y;
 int a[n], b[m];
 REP(i, n) cin >> a[i];
 REP(i, m) cin >> b[i];

 int ans = 0;

 SORT(a, n);
 SORT(b, m);

 if(max(x, a[n - 1]) < min(y, b[0])) ans++;

 if(ans) cout << "No War";
 else cout << "War";

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
  #define ll long long
ll ans = 0,tmp=0,ave= 0;
ll COM(ll n, ll k){
    ll num=1;
    for(int i=0;i<k;i++) {
        num *= n-i;
        num /= (1+i);
    }
    return num;
}
int main()
{
  ll n,k,m;
  cin >> n >> k >> m;
  map<ll,ll>mp;
   vector<ll>V;
  ll ara[n+10];
  for(ll i=0; i<n; i++)
  {
      cin >> ara[i] ;
       V.push_back(ara[i]);
      mp[ara[i]]++;
  }
  sort(ara,ara+n);
  sort(V.begin(),V.end());
  ll sum = 0;
  for(ll i=n-1; i>=max(n-k,0*1LL); i--)
  {
      sum += ara[i];
  }
  printf("%f\n",sum*1.00/k*1.00);

      ll id1 = lower_bound(V.begin(), V.end(), V[n-k])-V.begin();
    if(id1!=n-k) {
        ll id2 = lower_bound(V.begin(), V.end(), V[n-k]+1)-V.begin();
        ans += COM(id2-id1, id2-(n-k));
        
        if(V[n-k]==V[n-1]) {
            for(int i=n-k-1;i>=max(n-m, id1);i--) {
                tmp = COM(id2-id1, id2-i);
                
                ans += tmp;
                //cout << id2-id1 << " " << id2-i << " " << tmp << endl;
            }
        }
    }
    cout << setprecision(18) << max(1LL, ans) << endl;

}


Measured memory_bytes: 3644
using System;
using System.Collections.Generic;

public class CSharp
{
    public static void Main()
    {
        Kyopuro chokudai = new Kyopuro();
        chokudai.AtCoder();
    }
}

public class Kyopuro
{

    int n, m, k;

    public void AtCoder()
    {
        string[] input;
        input = Console.ReadLine().Split(' ');
        n = int.Parse(input[0]);
        m = int.Parse(input[1]);
        k = int.Parse(input[2]);

        Console.WriteLine(Math.Min(n * m, k));
    }
    public static void DebugWL(object x) { System.Diagnostics.Debug.WriteLine(x); }
}

Measured memory_bytes: 11092
#include <iostream>
#include <cstdio>
#include <vector>
#include <complex>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <stack>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <cassert>

using namespace std;

typedef long long ll;
typedef ll li;
typedef pair<int,int> PI;
#define EPS (1e-10L)
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define F first
#define S second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SZ(a) (int)((a).size())
#define ALL(a) a.begin(),a.end()
#define FOR(it,a) for(__typeof(a.begin())it=a.begin();it!=a.end();++it)
void pkuassert(bool t){t=1/t;};
int dx[]={0,1,0,-1,1,1,-1,-1};
int dy[]={1,0,-1,0,-1,1,1,-1};

int c2i(char a){
  if(isdigit(a)) return a-'0';
  return tolower(a)-'a'+10;
}

ll get(){
  string in;
  cin >> in;
  ll ret=0;
  FOR(it,in) ret=ret*16+c2i(*it);
  return ret;
}
ll in[9];
void solve(){
  rep(i,9) in[i]=get();
  ll k=0;
  rep(ii,32){
    ll su=0;
    rep(j,8) su += in[j]^k;
    if(((in[8]^k)&(1LL<<ii)) != (su&(1LL<<ii))) k |= 1LL<<ii;
  }

  printf("%x\n",(unsigned)k);
}

int main(int argc, char *argv[])
{
  int n;
  cin >> n;
  rep(i, n) solve();
  return 0;
}

Measured memory_bytes: 1204
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] = a[i] // 400
    if a[i] >= 8:
        a[i] = 8
non_free = [i for i in a if i != 8]
if len(non_free) == 0:
    min_ans = 1
    max_ans = a.count(8)
else:
    min_ans = len(set(non_free))
    max_ans = len(set(non_free)) + a.count(8)
print(min_ans, max_ans)


Measured memory_bytes: 3064
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;
using myui = uint64_t;
using myint = int64_t;

template<typename T>
T diff(const T& a, const T& b) {
    return a > b ? a - b : b - a;
}

myint impl(myui n, const vector<myui>& h, vector<myint>& costs) {
    if (costs[n-1] == -1) {
        myint one = diff(h[n-1], h[n-2]) + impl(n-1, h, costs);
        myint two = diff(h[n-1], h[n-3]) + impl(n-2, h, costs);

        costs[n-1] = std::min(one, two);
    }
    return costs[n-1];
}

myint solve(myui n, const vector<myui>& h) {
        vector<myint> costs(n, -1);
        costs[0] = 0;
        costs[1] = diff(h[0], h[1]);
        return impl(n, h, costs);
}

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

    {
        myui n;
        cin >> n;

        vector<myui> h(n, 0);
        for(myui i = 0; i < n; i++) {
            myui tmp;
            cin >> tmp;
            h[i] = tmp;
        }

        cout << solve(n, h) << endl;
    }

    return 0;
}


Measured memory_bytes: 8064
#include<bits/stdc++.h>
using namespace std;
int main(){
    long s;
    cin >> s;
    vector<long> a;
    a.emplace_back(s);
    long i;
    long tmp;
    i=1;
    tmp=s;
    int h=0;
    int j,k;
    while(1){
        i++;
        if(tmp%2==0){
            tmp=tmp/2;
            a.emplace_back(tmp);
        }
        else{
            tmp=(3*tmp)+1;
            a.emplace_back(tmp);
        }
        for(j=0;j<a.size();j++){
            for(k=1;j+k<a.size();k++){
                if(a.at(j)==a.at(j+k)){
                    h++;
                    }
            }
        }
        if(h!=0){
            cout << i << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256
N = int(input())
  
def num2alpha(num):
    if num<=26:
        return chr(64+num)
    elif num%26==0:
        return num2alpha(num//26-1)+chr(90)
    else:
        return num2alpha(num//26)+chr(64+num%26)
      
ans = num2alpha(N)      
      
print(str.lower(ans))

Measured memory_bytes: 9168
if __name__ == '__main__':
    h, w = map(int, input().split())
    field = [list(input()) for i in range(h)]
    d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    for y in range(h):
        for x in range(w):
            flag = False
            if field[y][x] == "#":
                for dx, dy in d:
                    if 0 <= x + dx < w and 0 <= y + dy < h:
                        if field[y + dy][x + dx] == "#":
                            flag |= True
                if not flag:
                    print("No")
                    exit(0)
    print("Yes")


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <cmath>

using std::cin;
using std::cout;
using std::endl;

bool is_prime(int n) {
	if (n < 2) {
			return false;
	}
	if (n==2||n==3) {
		return true;
	}
	for (int i = 3; i < n; i = i+2) {
		if (n%i==0) {
			return false;
		}
	}
	return true;
}

int main(void) {
	int N = 1100000;
	int a,d,n;
	cin >> a;
	cin >> d;
	cin >> n;

	std::vector<bool> prime(N);
	for (int i = 0; i < N+1; i++) {
		prime[i] = true;
	}
	prime[0] = false;
	prime[1] = false;
	for (int i = 2; i <= sqrt(N); i++) {
		if (is_prime(i)) {
			for (int j = 2; i*j < N+1; j++) {
				prime[i*j] = false;
			}
		}
	}
	
	while (a!=0||d!=0||n!=0) {
		bool find = false;
		int count = 0;
		int b;
		for (int i = 0; !find; i++) {
			b = a + (d*i);
			if (prime[b]) {
				count++;
			}
			if (count == n) {
				cout << b << endl;
				find = true;
			}
		}

		cin >> a;
		cin >> d;
		cin >> n;
	}

	return 0;
}

Measured memory_bytes: 3072
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<stack>
#include<sstream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=500+10;
int main()
{
    int n,s[N],t[N],T[N];
    while(~scanf("%d",&n)){
        n--;
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&s[i],&t[i],&T[i]);
        }
        for(int i=1;i<=n;i++){
            ll sum=s[i]+t[i];
            for(int j=i+1;j<=n;j++){
                if(sum>t[j]){
                    if(sum%T[j]!=0){
                        sum=(sum/T[j]+1)*T[j];
                    }
 
 
                }
                else sum=t[j];
                sum+=s[j];
            }
            printf("%lld\n",sum);
        }
        printf("0\n");
    }
 
 
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
long n,a[1<<17];
vector<long>s,t;
long ans;
main()
{
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	sort(a,a+n);
	if(n%2)
	{
		for(int i=0;i<n;i++)s.push_back(abs(a[i]-a[n/2]));
		sort(s.begin(),s.end());
		ans=s[1];
		for(int i=2;i<s.size();i++)
		{
			ans+=s[i]*2;
		}
	}
	else
	{
		for(int i=0;i<n/2;i++)s.push_back(abs(a[i]-a[n/2]));
		sort(s.begin(),s.end());
		ans=s[0];
		for(int i=1;i<s.size();i++)ans+=s[i]*2;
		for(int i=n/2;i<n;i++)t.push_back(abs(a[i]-a[n/2]));
		sort(t.begin(),t.end());
		ans+=t[0];
		for(int i=1;i<t.size();i++)ans+=t[i]*2;
	}
	cout<<ans<<endl;
}

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

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

#define p_ary(ary,a,b) do { cout << "["; for (int count = (a);count < (b);++count) cout << ary[count] << ((b)-1 == count ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

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

const char newl = '\n';

int main() {
    int n,m;
    cin >> n >> m;
    vector<int> dist(n,0);
    vector<vector<int>> edges(n);
    
    for (int i = 0;i < m;++i) {
        int u,v;
        scanf("%d%d",&u,&v);
        u--;v--;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    ll a = 0,b = 0,c = 0,ans = 0;
    for (int i = 0;i < n;++i) if (dist[i] == 0) {
        if (edges[i].size() == 0) {
            c++;
            continue;
        }
        queue<int> que;
        que.push(i);
        bool nibu = true;
        while (!que.empty()) {
            int t = que.front();que.pop();
            for (int j : edges[t]) {
                if (dist[j]) {
                    if (dist[j]%2 == dist[t]%2) nibu = false;
                } else {
                    dist[j] = dist[t]+1;
                    que.push(j);
                }
            }
        }
        if (nibu) {
            ans += 2;
            a++;
        } else {
            ans += 1;
            b++;
        }
    }
    ans += a*(a-1)*2+b*(b-1)+b*a*2+(2*n*c-c*c);
    cout << ans << endl;
}

Measured memory_bytes: 7296
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<vector>
using namespace std;
#define ll long long
#define db double
ll dp[1<<12+5];
ll a[1005];
ll key[1005];
ll pow2[15];

int main()
{
    ll n,m;

    pow2[0]=1;
    for(ll i=1;i<15;i++)pow2[i]=pow2[i-1]<<1;
    memset(dp,1e9+5,sizeof(dp));

    scanf("%lld %lld",&n,&m);

    dp[0]=0;

    for(ll i=1;i<=m;i++)
    {
        ll b,t=1;
        scanf("%lld %lld",&a[i],&b);
        for(ll j=1;j<=b;j++)
        {
            ll tmp;
            scanf("%lld",&tmp);
            key[i]=key[i]+pow2[tmp-1];
        }
    }

    for(ll j=0;j<pow2[n];j++)
    {
        for(ll i=1;i<=m;i++)
        {
            dp[j|key[i]]=min(dp[j]+a[i],dp[j|key[i]]);
        }
    }


    if(dp[pow2[n]-1]>=1e9+5)
    {
        printf("-1");
        return 0;
    }
    printf("%lld",dp[pow2[n]-1]);
    return 0;
}




Measured memory_bytes: 4856
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    long int n;
    string a,b;
    cin >> n >> a >>  b;
    for (long int i = 0; i < n; i++)
    {
        cout << a[i] << b[i];
    }
    cout << endl;
    return 0;
}

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

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    ll n,m;cin>>n>>m;
    ll sum=0;
    for(int i=0;i<m;i++){
        ll d;cin>>d;
        sum+=d;
    }
    if(sum>n){
        cout<<"-1\n";
    }else{
        cout<<n-sum<<"\n";
    }
}


Measured memory_bytes: 3636
#include <iostream>
#include<string.h>
#include<string>
using namespace std;
int main()
{
    string s;int n;
    cin>>n>>s;
    int c=0;
    for(int i=0;i<n-2;i++)
      {
          string s1=s.substr(i,3);
             if(s1=="ABC")
                 c++;
      }
    
  cout<<c;
}

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

int main(void) {
  char S[10000] = {};
  int w;
  scanf("%s %d", S, &w);
  for (int i = 0; S[i*w] != '\0'; i++) printf("%c", S[i*w]);
  puts("");

  return 0;
}

Measured memory_bytes: 128
import math
N = int(input())
p = list(map(int,input().split()))
t = list(map(int,input().split()))
ans = [[0]*4 for i in range(4)]
for i in range(4):
    for j in range(4):
        ans[i][j] = (N//t[i])*p[i] + math.ceil((N%t[i])/t[j])*p[j]
ou = min(ans[0])
for i in ans:
    ou = min(ou,min(i))
print(ou)


Measured memory_bytes: 5672
from bisect import bisect_right
import sys

N = int(input())


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-(n ** 0.5) // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


S = [0]
now = 0
for i in range(1, 60):
    S.append(i * (i + 1) // 2)
# print(S)

fact_list = factorization(N)
# fact_list = sorted(fact_list, reverse=True)
# print(fact_list)
if fact_list == [[1, 1]]:
    print(0)
    sys.exit()
ans = 0
while fact_list:
    now_fact = fact_list.pop()
    idx = bisect_right(S, now_fact[1])
    ans += idx - 1

print(ans)

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

main() {
  int N; cin >> N;
  vector<ll> a(N);
  for (int i = 0; i < N; i++) cin >> a[i];
  ll ans = 0;
  while (1) {
    sort(a.begin(), a.end(), greater<ll>());
    if (a[0] < N) break;
    ll q = a[0] / N;
    for (int i = 0; i < N; i++) {
      a[i] += (i == 0) ? -q * N : q;
    }
    ans += q;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
	int i, j, n, a[100], sum = 0;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &a[i]);

	for (j = 0; j < n - 1; j++) {
		for (i = j + 1; i < n ; i++) {
			sum = sum + a[j] * a[i];
		}
	}

	printf("%d", sum);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdlib>

using namespace std;

int main(void) {
    int n,b,r,f,v;
    cin >> n;
    int Array[4][3][10] = {};
    for(int i=0; i<n; i++) {
        cin >> b >> r >> f >> v;
        Array[b-1][r-1][f-1] += v;
    }
    for(int i=0; i<4; i++) {
        for(int j=0;j<3; j++) {
            for(int k=0;k<10;k++) {
                    if(k==9) {
                        cout << ' ' << Array[i][j][k] << endl;
                        if(j==2 && i!=3) {
                            for(int k=0;k<20;k++) cout << '#';
                            cout << endl;
                        }
                    } else cout << ' ' << Array[i][j][k];
            }
        }
    }
    exit(EXIT_SUCCESS);
}


Measured memory_bytes: 3120
#include <stdio.h>
#include <math.h>

int main(void){
	int aLen, bLen, angle;
	scanf("%d%d%d", &aLen, &bLen, &angle);
	double radian = ((double) angle / 180) * M_PI;
	
	double area = 0.5 * aLen * bLen * sin(radian);
	printf("%.8f\n", area);
	
	double cLen = pow(aLen, 2) + pow(bLen, 2) - 2 * aLen * bLen * cos(radian);
	cLen = sqrt(cLen);
	double circum = aLen + bLen + cLen;
	printf("%.8f\n", circum);
	
	double height = bLen * sin(radian);
	printf("%.8f\n", height);
}


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

int partition(int *, int, int);

/*ここからがmain関数*/
int main()
{
  int A[100000], n, x;
  int i, j;
  
  scanf("%d", &n);
  
  for(i = 0 ; i < n ; i++)
    scanf("%d", &A[i]);
  
  x = partition(A, 0, n - 1);
  
  for(i = 0 ; i < n - 1 ; i++){
    if(i == x)
      printf("[%d] ", A[i]);
    else 
      printf("%d ", A[i]);
  }
  printf("%d\n", A[i]);

  return 0;
}

/*ここからがmain関数*/
int partition(int *A, int p, int r)
{
  int a, x, l;
  int i, j;
  
  i = p - 1;
  x = A[r];
  
  for(j = p; j <= r - 1 ; j++){
    if(A[j] <= x){
      i++;
      l = A[i];
      A[i] = A[j];
      A[j] = l;
    }
  }
  
  l = A[i + 1];
  A[i + 1] = A[r];
  A[r] = l;

  a = i + 1;
  
  return a;
}



Measured memory_bytes: 2124
a,b,k = map(int,input().split())
lia,lib = [],[]

for i in range(a,min(a+k,b)):
    lia.append(i)
for i in range(max(a,b-k+1),b+1):
    lib.append(i)

lia = list(set(lia+lib))
lia.sort()
for i in lia:
    print(i)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX;
/* テンプレートここまで */

int main() {
  string s;
  cin >> s;
  ll n = s.size();
  ll p = 0;
  ll ans = 0;
  REP(i, n){
    if(p >= n-i){
      p--;
      if(s[i] == 'g') ans++;
    }else{
      if(s[i] == 'g') p++;
      else p--;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 512
import collections
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,p= map(int, input().split())
s=list(input())
mod=0
ans=[]
count=0

if p==2 or p==5:
    for i in range(n):
        if p==2 and (s[n-1-i]=='0' or s[n-1-i]=='2' or s[n-1-i]=='4' or s[n-1-i]=='6' or s[n-1-i]=='8'):
            count+=n-i
        elif p==5 and (s[n-1-i]=='0' or s[n-1-i]=='5'):
            count+=n-i
    print(count)
    exit()

s+='0'

for i in range(n+1):
    if s[n-i]!=0:
        mod+=(pow(10,i,p)*int(s[n-i]))%p
        mod%=p
    ans.append(mod)

ans = collections.Counter(ans)
ans=ans.most_common()
for i in range(len(ans)):
    if ans[i][1]>=2:
        count+=combinations_count(ans[i][1],2)

print(count)

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

using namespace std;

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define endl '\n'

int main()
{
	int n;
	cin >> n;
	double odd = n/2;
	if(n%2) odd++;
	cout << fixed << setprecision(10) << odd/n << endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define RG register
using namespace std;
const int N=1e6+10;
int n,ans;
char st[N],ed[N];
queue<int> pn;
inline int mi(int a,int b){return a<b ? a : b;}
inline int mx(int a,int b){return a>b ? a : b;}
int main()
{
//	freopen("Shik and Copying String.in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d%s%s",&n,st+1,ed+1);
	if(!strcmp(st+1,ed+1)) return printf("0\n"), 0;
	for(int i=n,j=n;i;i--)
	{
		if(ed[i]==ed[i-1]) continue;
		j=mi(i,j);
		while(ed[i]!=st[j] && j) j--;
		if(!j) return printf("-1\n"), 0;
		while(!pn.empty())
		{
			if((int)pn.front()-(int)pn.size()>=i) pn.pop();
			else break;
		}
		pn.push(j);
		if(i!=j) ans=mx(ans,(int)pn.size());
	}
	printf("%d\n",ans+1);
	//fclose(stdin); fclose(stdout);
	return 0;
}


Measured memory_bytes: 6272
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;

LL n,m;
LL dp[505][505];
char ch[505][505];

int main(){
	ios::sync_with_stdio(false);
	memset(dp,INF,sizeof(dp));
	cin >> n >> m;
	for(LL i = 1;i <= n;i ++){
		for(LL j = 1;j <= m;j ++){
			cin >> ch[i][j];
		}
	}
	if(ch[1][1] == '.') dp[1][1] = 0;
	else dp[1][1] = 1;
	
	
	for(LL i = 1;i <= n;i ++){
		for(LL j = 1;j <= m;j ++){
			if(i > 1){
				if(ch[i][j] == ch[i - 1][j]) dp[i][j] = min(dp[i][j],dp[i - 1][j]);
				if(ch[i][j] != ch[i - 1][j]) dp[i][j] = min(dp[i][j],dp[i - 1][j] + 1);
			}
			if(j > 1){
				if(ch[i][j] == ch[i][j - 1]) dp[i][j] = min(dp[i][j],dp[i][j - 1]);
				if(ch[i][j] != ch[i][j - 1]) dp[i][j] = min(dp[i][j],dp[i][j - 1] + 1);
			}
		}
	}
	if(ch[n][m] == '#') dp[n][m] ++;
	dp[n][m] >>= 1;
	cout << dp[n][m] << endl;
	return 0;
}
//

Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	int D;
	cin >> D;
	vector<int> C(26);
	for (auto& x : C) cin >> x;
	vector<vector<int>> S(D, vector<int>(26));
	for (auto& x : S) for (auto& y : x) cin >> y;

	vector<int> last(26);

	vector<int> T(D);
	for (auto& x : T) { cin >> x; -- x; }
	ll score = 0;
	for (int d = 1; d <= D; ++ d) {
		int i = T[d-1];
		last[i] = d;
		score += S[d-1][i];
		for (int j = 0; j < 26; ++ j) {
			score -= C[j] * (d - last[j]);
		}
		cout << score << endl;
	}
}


Measured memory_bytes: 3576
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <utility>
#include <fstream>
#include <random>
#include <map>
#include <unordered_map>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#define INF 1000000001
#define mod 1000000007
#define p pair<int,int>
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
using namespace std;
int POW(int x,int y){return int(pow(double(x),double(y)));}

vector<bool> primenumber(int n){
	vector<bool> a(n+1);
	rep(i,n+1){
		a[i]=1;
	}
	a[0]=0;
	a[1]=0;
	for(int i=2;i*i<=n;i++){
		if(a[i]==1){
			for(int j=i+1;j<=n;j++){
				if(j%i == 0){
					a[j]=0;
				}
			}
		}
	}
	return a;
}


int main(){
	int n;
	cin>>n;
	vector<bool> a=primenumber(1571);
	int b=0;
	int i=0;
	while(1){
		i++;
		if(a[10*i+1]==1){
			b++;
			cout<<10*i+1;
			if(b>=n){
				cout<<endl;
				break;
			}
			cout<<" ";
		}
	}
}


Measured memory_bytes: 256
import heapq
import sys
input = sys.stdin.readline


def dijkstra_heap(s, n, edge):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


def main():
    H, W = map(int, input().split())

    edge = [[] for i in range(10)]
    for i in range(10):
        C = list(map(int, input().split()))
        for j in range(10):
            if i==j:
                continue
            edge[i].append([C[j],j])

    MP = [0]*10
    for i in range(10):
        if i==1:
            continue
        D = dijkstra_heap(i, 10, edge)
        MP[i] = D[1]

    ans = 0
    for i in range(H):
        A = list(map(int, input().split()))
        for a in A:
            if a==-1:
                continue
            ans += MP[a]

    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3188
n, q = gets.split.map(&:to_i)
history = [nil, 'kogakubu10gokan']
n.times do
  line = gets.chomp.split
  line[0] = line[0].to_i
  history[line[0]] = line.last
end

q.downto(0) do |i|
  if history[i]
    puts history[i]
    break
  end
end

Measured memory_bytes: 6104
r,c=gets.split(" ").map(&:to_i)
h = Array.new(r+1).map{Array.new(c+1,0)} 

for i in 1..r                                       # 変数 i を1からrまで増やして繰り返し処理する。
    
a= gets.split.map(&:to_i)
    for j in 1..c                                   # 変数 i を1からcまで増やして繰り返し処理する。
    h[i-1][j-1] = a[j-1]
    h[i-1][c] += a[j-1]
    h[r][j-1] += a[j-1]
    h[r][c] += a[j-1]
    end
end
for i in 0..r
    for j in 0..c
      print " " unless j == 0
      print h[i][j]
    end
    print "\n"
  end



Measured memory_bytes: 7056
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

int N, Q; string s;
char t[200010], d[200010];

int get_state(int x) {
    for(int i=0; i<Q; i++) {
        if(s[x] == t[i]) {
            if(d[i] == 'L') x--;
            if(d[i] == 'R') x++;
        }
        if(x <  0) return 1;
        if(x >= N) return 2;
    }
    return 0;
}

int bs1() {
    int ub = N, lb = -1;
    while(ub - lb > 1) {
        int mid = (ub + lb) / 2;
        if(get_state(mid) == 1) lb = mid;
        else ub = mid;
    }
    return lb;
}

int bs2() {
    int ub = N, lb = -1;
    while(ub - lb > 1) {
        int mid = (ub + lb) / 2;
        if(get_state(mid) == 2) ub = mid;
        else lb = mid;
    }
    return ub;
}

signed main() {
    cin >> N >> Q;
    cin >> s;
    for(int i=0; i<Q; i++) {
        cin >> t[i] >> d[i];
    }

    int s1 = bs1() + 1;
    int s2 = bs2();
    // fprintf(stderr, "s1 = %lld, s2 = %lld\n", s1, s2);
    int ans = N - s1 - (N - s2);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 900
#include <iostream>

using namespace std;

string en;
bool isp(int i, int j){
	while(i<j){
		if(en[i]!=en[j])return false;
		i++;j--;
	}
	return true;
}

int main(){
	
	cin.tie(0); ios_base::sync_with_stdio(0);
	cin>>en;
	if(isp(0,en.length()-1)&&isp(0,en.length()/2-1)&&isp(en.length()/2+1,en.length()-1))cout<<"Yes\n";
	else cout<<"No\n";
	
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(int argc, char const *argv[]) {
	char str[101];
	int n, m;

	fgets(str, 100, stdin);
	sscanf(str, "%d %d\n", &n, &m);

	printf("%d\n", n % m == 0 ? 0 : 1);

	return 0;
}


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

const int m = 2019;

int main(){

    string s;
    cin>>s;
    int n = s.size();
    reverse(s.begin(),s.end());
    int x = 1,tot = 0;
    vector<int> cnt(m);
    l1 ans = 0;
    rep(i,n){
        cnt[tot]++;
        tot += (s[i]-'0')*x;
        tot %= m;
        ans += cnt[tot];
        x = x*10%m;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3656
#include <iostream>

using namespace std;

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

  int sum = (L + L + N - 1) * N / 2;
  if (L > 0) {
    sum -= L;
  } else if (L < 0 && L + N - 1 < 0) {
    sum -= L + N - 1;
  }

  cout << sum << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>  // This will work only for g++ compiler. 
#include <ext/pb_ds/assoc_container.hpp> // Used to include policy based data structure 
using namespace __gnu_pbds;  // Only for g++ compiler
using namespace std;

#define for0(i, n) for (int i = 0; i < (int)(n); ++i) // 0 based indexing
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i) // 1 based indexing
#define forc(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i) // closed interver from l to r r inclusive
#define forr0(i, n) for (int i = (int)(n) - 1; i >= 0; --i) // reverse 0 based.
#define forr1(i, n) for (int i = (int)(n); i >= 1; --i) // reverse 1 based
#define max(a, b)  (a > b) ?a :b  // max of 2 elements 
#define min(a, b)  (a < b) ?a :b  // min of 2 elements

//short hand for usual tokens
#define pb              push_back
#define fi              first
#define se              second
#define mp              make_pair
#define mii             map<int,int>
#define pqb             priority_queue<int>   // Max Heap
#define pqs             priority_queue<int,vi,greater<int> >   // Min Heap
#define setbits(x)      __builtin_popcountll(x)   // returns the number of set bits in the binary representation of x
#define zrobits(x)      __builtin_ctzll(x)   // returns the number of zeroes before the first set bit in the binary representation of x       
#define mod             1000000007   // 1e9 + 7   
#define inf             1e18   // pow(10, 18)  
#define mk(arr,n,type)  type *arr=new type[n];   // generates a dynamic array
#define w(x)            int x; cin>>x; while(x--)   // for taking test cases 
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());   // used with shuffle

// to be used with algorithms that processes a container Eg: find(all(c),42)
#define all(x) (x).begin(), (x).end() //Forward traversal
#define rall(x) (x).rbegin, (x).rend() //reverse traversal

// traversal function to avoid long template definition. Now with C++11 auto alleviates the pain.
#define tr(c,i) for(__typeof__((c)).begin() i = (c).begin(); i != (c).end(); i++)

// find if a given value is present in a container. Container version. Runs in log(n) for set and map
#define present(c,x) ((c).find(x) != (c).end())

//find version works for all containers. This is present in std namespace.
#define cpresent(c,x) (find(all(c),x) != (c).end())

// Avoiding wrap around of size()-1 where size is a unsigned int.
#define sz(a) int((a).size())


typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;   // Used to implement policy-based data structure

// Shorthand for commonly used types
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;



int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;
    
    string s, t;
    cin>>s;
    cin>>t;
    int n = s.length();
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(s[i] != t[i])
           ans++;
    }  
  
    cout<<ans;
  
    return 0;
}


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

//const long double PIL = 3.141592653589793238462643383279502884L;
//const double PI = 3.14159265358979323846;

#define sz(a) int((a).size())
#define all(c) (c).begin(), (c).end()
#define debug(v) {for (auto z : v) {cerr << z << ' ';} cerr << endl;}

using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vll = vector<long long>;
using vii = vector<pair<int,int>>;

const int N = 25;
const int INF = 500;
int h, w;
char grid[N][N];
int dist[N][N];
int delta_r[4] = {0, -1, 0, 1};
int delta_c[4] = {-1, 0, 1, 0};

int bfs(int row, int col) {
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++) dist[i][j] = INF;
	dist[row][col] = 0;
	queue<ii> q;
	q.push({row, col});
	while (!q.empty()) {
		int r, c;
		tie(r, c) = q.front();
		q.pop();
		int d = dist[r][c] + 1;
		for (int i = 0; i < 4; i++) {
			int nr = r + delta_r[i];
			int nc = c + delta_c[i];
			if (0 <= nr && nr < h && 0 <= nc && nc < w && grid[nr][nc] == '.' && dist[nr][nc] > d) {
				dist[nr][nc] = d;
				q.push({nr, nc});
			}
		}
	}

	int ret = 0;
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			if (dist[i][j] != INF) ret = max(ret, dist[i][j]);
	return ret;
}

int main() {
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	//~ cout.tie(0);
	scanf("%d%d", &h, &w);
	for (int i = 0; i < h; i++) scanf("%s", grid[i]);

	int ans = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (grid[i][j] == '#') continue;
			ans = max(ans, bfs(i, j));
		}
	}
	printf("%d\n", ans);
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<set>
#include<algorithm>
#include<map>
#include<cmath>

using namespace std;

int main()
{
	for(int i=1;i<=9;i++)
	{
		for(int j=1;j<=9;j++)
		{
			cout<<i<<'x'<<j<<'='<<i*j<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1116
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
const int mod = 1000000007;

int main(){
    int n,m;cin>>n>>m;
    int ans=n*(n-1)/2+m*(m-1)/2;
    cout<<ans<<endl;
}

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

int main(int argc, char const *argv[])
{
	const long long mod=1000000007;
	string s;
	cin>>s;
	int n=s.size();
	reverse(s.begin(), s.end());
	long long dp[n][13]={};
	if (s.at(0)=='?')
	{
		for (int i = 0; i < 10; ++i)
		{
			dp[0][i]=1LL;
		}
	}
	else
	{
		dp[0][s.at(0)-'0']=1LL;
	}
	long long now10=10LL;
	for (int i = 1; i < n; ++i)
	{
		if (s.at(i)=='?')
		{
			for (int j = 0; j < 13; ++j)
			{
				for (int k = 0; k < 10; ++k)
				{
					dp[i][(j+now10*k)%13]+=dp[i-1][j];
					dp[i][(j+now10*k)%13]%=mod;
				}
			}
		}
		else
		{
			for (int j = 0; j < 13; ++j)
			{
				dp[i][(j+now10*(s.at(i)-'0'))%13]+=dp[i-1][j];
				dp[i][(j+now10*(s.at(i)-'0'))%13]%=mod;
			}
		}
		now10*=10LL;
		now10%=13LL;
	}
	cout<<dp[n-1][5]%mod<<endl;
	return 0;
}


Measured memory_bytes: 10624
K, N = map(int, input().split())
A = sorted(map(int, input().split()))
max_dis = abs(A[0]-A[-1]+K)
pre = A[0]
for a in A[1:]:
    max_dis = max(max_dis, abs(a-pre))
    pre = a
ans = K - max_dis
print(ans)


Measured memory_bytes: 100012
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys
from collections import defaultdict


def solve(values, _nb, max_capacity):
    dp = {}
    dp[0] = 0
    for w, v in values:
        keys = sorted(dp.keys(), reverse=True)
        for vk in keys:
            if vk + v in dp:
                dp[vk + v] = min(dp[vk + v], dp[vk] + w)
            else:
                dp[vk + v] = dp[vk] + w
    result = 0
    for v, w in dp.items():
        if w <= max_capacity and v > result:
            result = v
    return result


def solve_better(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        # dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    return dp[max_capacity]


def solve_slow(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    # print("\n".join(map(str, dp)))
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


Measured memory_bytes: 15780
N = int(input())
S = input()

ans = 0
for i in range(1, N):
    S1 = S[i:]
    S2 = S[:i]
    
    A = [0] * 26
    for j in range(len(S1)):
        t = ord(S1[j]) - 97
        A[t] += 1

    B = [0] * 26
    for j in range(len(S2)):
        t = ord(S2[j]) - 97
        B[t] += 1
    
    c = 0
    for k in range(26):
        if A[k] > 0 and B[k] > 0:
            c += 1

    ans = max(ans, c)

print(ans) 


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

using namespace std;

void solve()
{
	string s, t;
	cin >> s >> t;
	int sl = s.size(), tl = t.size();
	int dp[sl + 1][tl + 1];
	memset(dp, 0, sizeof(dp));
	int ans = 0;
	for (int ti = 0; ti < tl; ti++)
		for (int si = 0; si < sl; si++)
		{
			dp[si + 1][ti + 1] = max({dp[si + 1][ti + 1], dp[si][ti + 1], dp[si + 1][ti], dp[si][ti] + (s[si] == t[ti])});
			ans = max(ans, dp[si + 1][ti + 1]);
		}

	if (ans == 0)
	{
		cout << " " << endl;
		return;
	}
	/*
	for (int ti = 0; ti <= tl; ti++)
		for (int si = 0; si <= sl; si++)
		{
			cout << dp[si][ti] << (si == sl ? '\n' : ' ');
		}*/

	string go = "";

	int ti = tl, si = sl;

	while(ti > 0 && si > 0)
	{
		if (ans == 0) break;
		if (dp[si - 1][ti - 1] + 1 == dp[si][ti] && ans == dp[si][ti] && s[si - 1] == t[ti - 1])
		{
			si--;
			ti--;
			ans--;
			go.push_back(s[si]);
		}
		else if (dp[si][ti] == dp[si][ti-1])
			ti--;
		else if (dp[si][ti] == dp[si-1][ti])
			si--;
		//cout << si << ' ' << ti << ' ' << go << endl;
	}
	reverse(go.begin(), go.end());
	cout << go << endl;
}

int main()
{
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}


Measured memory_bytes: 35456
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
x=1
l=[]
for i in range(n-1):
    if i!=n-2:
        if a[i]==a[i+1]:
            x+=1
        else:
            if x>=4:
                l.append(a[i])
                l.append(a[i])
                break
            elif x==2 or x==3:
                l.append(a[i])
                x=1
                if len(l)>=2:
                    break
    else:
        if a[i]==a[i+1]:
            x+=1
            if x>=4:
                l.append(a[i])
                l.append(a[i])
                break
            elif x==2 or x==3:
                l.append(a[i])
                x=1
                if len(l)>=2:
                    break
        else:
            if x>=4:
                l.append(a[i])
                l.append(a[i])
                break
            elif x==2 or x==3:
                l.append(a[i])
                x=1
                if len(l)>=2:
                    break
#print(a,x)
if len(l)<2:
    print(0)
else:
    print(l[0]*l[1])

Measured memory_bytes: 14480
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

int main(){
  ll N, Y;
  cin >> N >> Y;
  Y /= 1000;

  // 9x + 4y + N = Y
  // 9x + 4y = Y - N
  if(Y == N){
    cout << 0 << ' ' << 0 << ' ' << N << endl;
    return 0;
  } else if(Y < N){
    cout << -1 << ' ' << -1 << ' ' << -1 << endl;
    return 0;
  }
  
  Y -= N;

  ll x = 0;
  while(Y - 9*x >= 0){
    if((Y - 9*x) % 4 > 0){
      x++;
      continue;
    }
    ll y = (Y - 9*x) / 4;
    ll z = N - x - (Y - 9*x) / 4;
    if((y >= 0) && (z >= 0)){
      cout << x << ' ' << y << ' ' << z << endl;
      return 0;
    }
    x++;
  }

  cout << -1 << ' ' << -1 << ' ' << -1 << endl;
  
  return 0;
}


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

class UFtree {
    class UFnode {
    public:
        UFnode *p;
        int rank{0};

        explicit UFnode() : p{nullptr} {}

        explicit UFnode(UFnode *pa) : p{pa} {}
    };

    std::vector<UFnode> nodes;

    UFnode *parent(UFnode *x) {
        // xの親ノードの探索
        if (x->p == nullptr)
            return x;
        return x->p = parent(x->p);
    }

public:
    explicit UFtree(std::vector<UFnode>::size_type n) : nodes{n} {};

    bool same(int a, int b) {
        // aとbが同じグループに属せばTRUE
        return this->parent(&nodes[a]) == this->parent(&nodes[b]);
    }

    void join(int a, int b) {
        // aとbの属すグループを結合
        auto ap = this->parent(&nodes[a]);
        auto bp = this->parent(&nodes[b]);
        if (ap == bp)
            return;

        if (ap->rank < bp->rank) {
            ap->p = bp;
            return;
        }
        if (ap->rank == bp->rank)
            bp->rank += 1;
        bp->p = ap;
    }
};


int main() {
    int n, m;
    std::cin >> n >> m;
    UFtree tree(n);
    std::vector<int> p;
    for (int j = 0; j < n; ++j) {
        int tmp;
        std::cin >> tmp;
        p.push_back(tmp-1);
    }
    for (int i = 0; i < m; ++i) {
        int x, y;
        std::cin >> x >> y;
        x--;
        y--;
        tree.join(x, y);
    }
    int ans = 0;

    for (int i = 0; i < n; ++i) {
        if(tree.same(i, p[i]) || i == p[i])
            ans++;
    }
    std::cout << ans << std::endl;
}

Measured memory_bytes: 2428