akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<bitset>
#include<unordered_map>

using namespace std;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep(i,j,n) for(ll (i)=(j);(i)<(n);(i)++)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long
#define ull unsigned long long
#define all(hoge) (hoge).begin(),(hoge).end()
typedef pair<ll, ll> P;
const long long INF = 1LL << 60;
const long long MOD = 1e9 + 7;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


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

//グラフ関連
struct Edge {//グラフ
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
		to = _to; cap = _cap; rev = _rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

//最大公約数
ll gcd(ll m, ll n) {
	if (n == 0)return m;
	return gcd(n, m % n);
}//gcd

//最小公倍数
ll lcm(ll m, ll n) {
	return m / gcd(m, n) * n;
}


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

	ll n,m;
	cin >> n >> m;
	Array a(n,0);
	REP(i, n) cin >> a[i];

	
	ll min = a[0] / 2;
	ll di = min % 2;

	REP(i, n) {
		ll p = a[i] / 2;
		if (p % 2 != di) {
			cout << 0 << endl;
			return 0;
		}
		min = lcm(min, p);
	}

	REP(i, n) {
		ll p = a[i] / 2;
		if ((min - p) % a[i] != 0) {
			cout << 0 << endl;
			return 0;
		}
	}
	

	if (min > m) {
		cout << 0 << endl;
		return 0;
	}
	else {
		cout << (m-min)/(2*min) + 1 << endl;
	}

	return 0;
}

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

using namespace std;

#define ll long long

int main() {
    int n; cin >> n;
    map<int, int> rec;
    for(int i=1; i<=n; i++) {
        if(i==1) continue;
        int ai; cin >> ai;
        rec[ai]++;
    }
    for(int i=1; i<=n; i++) {
        if(rec.count(i)>0) {
            cout << rec[i] << endl;
        } else {
            cout << 0 << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 13012
import sys

n = int(sys.stdin.readline())
lst = [list(map(int, i.split())) for i in sys.stdin.readlines()]
a, b = lst[0]
for i, j in lst[1:]:
  if i >= a and j >= b:
    a, b = i, j
  else:
    tmp1 = (a // i) + (a % i != 0)
    tmp2 = (b // j) + (b % j != 0)
    if i < a and j >= b:
      a, b = tmp1 * i, tmp1 * j
    elif i >= a and j < b:
      a, b = tmp2 * i, tmp2 * j
    else:
      if tmp1 > tmp2:
        a, b = tmp1 * i, tmp1 * j
      else:
        a, b = tmp2 * i, tmp2 * j
print(a + b)

Measured memory_bytes: 3316
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def INT_(n): return int(n)-1


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


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():

    class BigCombination(object):

        def __init__(self, mod: int = 10**9+7, max_n: int = 10**6):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_n+1):
                fac_append(fac[-1] * i % mod)

                inv_append(pow(fac[-1], mod-2, mod))

            for i in range(max_n, 0, -1):
                inv_append(inv[-1] * i % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def get_combination(self, n, r):
            return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod

        def get_permutation(self, n, r):
            return self.factorial[n] * self.inverse[n-r] % self.mod
    N, M, K = MI()
    comb = BigCombination(max_n=N*M)
    get_comb = comb.get_combination

    ans = 0
    for distansssss in range(N):
        ans += distansssss * (M ** 2) * (N - distansssss)
        ans %= mod
    for distansssss in range(M):
        ans += distansssss * (N ** 2) * (M - distansssss)
        ans %= mod
    ans *= get_comb(N*M-2, K-2)
    print(ans % mod)


if __name__ == '__main__':
    main()


Measured memory_bytes: 66288
def include?(a, b)
  (0..(a.length - b.length)).each do |i|
    (0..(a[0].length - b[0].length)).each do |j|
      pp = true
      (0..b.length - 1).each do |k|
        pp &= b[k] == a[i + k].slice(j, b[0].length)
      end
      return true if pp
    end
  end
  false
end

tmp = gets.chomp.split(' ')
N = tmp[0].to_i
M = tmp[1].to_i

pic_a = []
pic_b = []

N.times do
  pic_a << gets.chomp.split('')
end

M.times do
  pic_b << gets.chomp.split('')
end

puts include?(pic_a, pic_b) ? 'Yes' : 'No'


Measured memory_bytes: 2172
#include <algorithm>
#include <iterator>
#include <iostream>
#include <sstream>
#include <bitset>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <time.h>
#include <limits>
#include <math.h>
#include <climits>
#include <numeric>
#include <utility>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <functional>
#include<unordered_map>

using namespace std;
const double pi=acos(-1.0);
//memset ( a , 0 , n * sizeof(ll) ) ;

#define 	boost  		ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); // don't use if small inpts
#define 	endl 		'\n'
#define 	sl(n) 		scanf("%lld",&n)
#define		mp 			make_pair
#define 	pb 			push_back
#define 	ppb 		pop_back
#define 	fi 			first
#define 	se 			seconchutd
#define 	ll 			long long
#define 	ull 		unsigned long long
#define 	pii 		pair<int, int>
#define 	f(i,a,b) 	for(ll i = (ll)(a); i < (ll)(b); i++)
#define 	rf(i,a,b) 	for(ll i = (ll)(a); i > (ll)(b); i--)
#define 	ms(a,b) 	memset((a),(b),sizeof(a))
#define 	max(a,b) 	((a>b)?(a):(b))
#define 	min(a,b) 	((a<b)?(a):(b))
#define 	vec(g1) 	int temp;cin>>temp;g1,push_back(temp);
#define 	abs(x) 		((x<0)?(-(x)):(x))
#define 	MAX 		1000005
#define 	inf 		LLONG_MAX
#define 	MIN 		INT_MIN

//typedef
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int,int> MPII;
typedef set<int> SETI;
typedef multiset<int> MSETI;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;


int mod = 1e9 + 7 ;
ll gcd(ll a , ll b){return b==0?a:gcd(b,a%b);}
ll powmod(ll a,ll b) {ll res=1;if(a>=mod)a%=mod;for(;b;b>>=1){if(b&1)res=res*a;if(res>=mod)res%=mod;a=a*a;if(a>=mod)a%=mod;}return res;}// ll fac[200005];
// ll inverse(ll n){return powmod(n, mod-2);}
// ll nCr(ll n, ll r){return (fac[n] * inverse(fac[r]) % mod * inverse(fac[n-r]) % mod) % mod;}

/**.................................................................................................................................*/

int main() {

  boost;
  int n,m;
  cin>>n>>m;
  char a[n][m];
  for(int i=0;i<n;i++){
  	for(int j=0;j<m;j++)cin>>a[i][j];
  }
  ll dp[n][m];
   for(int i=0;i<n;i++)for(int j=0;j<m;j++)dp[i][j]=0;
   for(int i=0;i<n;i++){
  	 if(a[i][0]== '#')break;
  	 else dp[i][0]=1;
  }
   for(int i=0;i<m;i++){
  	 if(a[0][i]== '#')break;
  	 else dp[0][i]=1;
  }
  for(int i=1;i<n;i++){
  	for(int j=1;j<m;j++){
  		if(a[i][j]!='#'){
  			 dp[i][j]= (dp[i-1][j]%mod + dp[i][j-1]%mod)%mod;
  		}
  	}
  }
  cout<<dp[n-1][m-1]<<endl;




    return 0;
}


Measured memory_bytes: 9088
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
int main()
{
  lli n;
  cin>>n;
  if(n%2==0 || n%5==0)
    	cout<<-1;
  else
  {
  	lli val = 7;
    for(int i=1;i<=1e6;i++)
    {
      if(val%n==0)
      {	cout<<i;
      	return 0;}
      val = (val*10+7)%n;
    }
    cout<<-1;
  }
return 0;
}


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

int main() {
  vector<vector<vector<int> > > vc(4, vector<vector<int> >(3, vector<int>(10)));

  int b, f, r, v, n;
  cin >> n;

  for(int i = 0; i < n; ++i) {
    cin >> b >> f >> r >> v;
    vc.at(b - 1).at(f - 1).at(r - 1) += v;
  }

  for(int i = 0; i < 4; ++i) {
    for(int j = 0; j < 3; ++j) {
      for(int k = 0; k < 10; ++k) {
        cout << " " << vc.at(i).at(j).at(k);
      }
      cout << endl;
    }
    if(i != 3) cout << "####################" << endl;
  }
}



Measured memory_bytes: 3176
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>

using namespace std;
typedef long long ll;

int main(){
  int x;cin>>x;
  if(x==7||x==5||x==3){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }

}

Measured memory_bytes: 256
import sys
n = int(input())
p = list(map(int, input().split()))

p2 = sorted(p)

if p2 == p:
    print('YES')
    sys.exit()


for i in range(n-1):
    for j in range(i+1, n):
        new = list(p)
        temp = p[i]
        new[i] = p[j]
        new[j] = temp
        if new == p2:
            print('YES')
            sys.exit()

print('NO')




Measured memory_bytes: 39792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7, mx=1e+7;
ll binpow(ll a, ll exp){
	ll res=1;
	while(exp>0){
		if(exp&1) res=res*a%mod;
		a = a*a%mod;
		exp>>=1;
	}
	return res;
}
int main(){
	ll x,y,k,xk,ans; cin>>x>>y;
	k=(x+y)/3;
	xk= x-k;
	if((x+y)%3||min(x,y)<k||max(x,y)>2*k) {cout<<0<<endl; return 0;}
	vector<ll>fact(mx);
	fact[0]=1;
	for(int i=1;i<mx;i++) fact[i]=(fact[i-1]*i)%mod;
	ans=fact[k];
	ans *= binpow(fact[xk], mod-2);
	ans %= mod;
	ans *= binpow(fact[k-xk], mod-2);
	ans %= mod;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 78336
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF = -10000;

int main(){
  ll N,M;
  cin >> N >> M;
  ll x = (N-M)*100 + 1900*M;
  ll q = 1;
  for(int i = 0;i<M;i++){
    q = q*2;
  }
  cout << x*q << endl;
 
}

Measured memory_bytes: 256
def is_Palindrome(S):
    T=""
    for s in S:
        T=s+T

    return T==S

S=input()
L=len(S)
if is_Palindrome(S) and is_Palindrome(S[:(L-1)//2]) and is_Palindrome(S[(L-1)//2+1:]):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 38412
#include<iostream>
using namespace std;
int kai_check(int a){
  int i=0,b[4];
  b[0]=a%10; a/=10;
  b[1]=a%10; a/=10; a/=10;
  b[2]=a%10; a/=10;
  b[3]=a;
  if(b[0]==b[3]&&b[1]==b[2]) return 1;
  else return 0;
}
int main(){
  int a,b,cnt=0;
  cin >> a >> b;
  for(int i=a;i<=b;i++){
    cnt+=kai_check(i);
  }
  cout << cnt << endl;
}


Measured memory_bytes: 256
from fractions import Fraction
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

def judge(a,c,d):
  x = a//c
  y = a//d
  z = a//lcm(d,c)
  return a-x-y+z


w,h,x,y = map(int,input().split())
print(w*h/2, end="")
if w/2 == x and h/2 == y:
  print(" 1")
else:
  print(" 0")

Measured memory_bytes: 5076
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;

#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

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

struct UnionFind{
    v: Vec<usize>
}

impl UnionFind{
    fn new(n: usize) -> UnionFind{
        let mut v: Vec<usize> = Vec::new();
        for i in 0..n{
         v.push(i);
        }
        UnionFind{v:v}
    }

    fn find(&mut self, i: usize) -> usize{
        if self.v[i] == i{
            i
        }else{
            let ni = self.v[i];
            self.v[i] = self.find(ni);
            self.v[i]
        }
    }

    fn union(&mut self, i: usize, j: usize){
        let root_i = self.find(i);
        let root_j = self.find(j);
        self.v[root_i] = root_j;
    }

}

struct CombMod{
    fac: Vec<u64>,
    inv: Vec<u64>,
    finv: Vec<u64>,
    mmod: u64,
}

impl CombMod{
    pub fn new(max: u64, m: u64) -> CombMod{
        let max: usize = max as usize;
        let mut fac: Vec<u64> = vec![0;max+1];
        let mut finv: Vec<u64> = vec![0;max+1];
        let mut inv: Vec<u64> = vec![0;max+1];

        fac[0] = 1;
        fac[1] = 1;
        finv[0] = 1;
        finv[1] = 1;
        inv[1] = 1;

        for i in 2..max+1{
            fac[i] = fac[i-1] * i as u64 % m;
            inv[i] = m - inv[m as usize %i] * (m/(i as u64)) % m;
            finv[i] = finv[i-1] * inv[i] % m;
        }

        CombMod{
            fac: fac,
            finv: finv,
            inv: inv,
            mmod: m,
        }
    }

    fn get(&self, n: u64, m: u64) -> u64{
        assert!(n >= m && n != 0 && m != 0);
        self.fac[n as usize] * self.finv[m as usize] % self.mmod
            * self.finv[(n-m) as usize] % self.mmod
    }
}

fn custom_abs(n: i64, r: i64) -> i64{
    cmp::min((n/2-r).abs(),
             ((n+1)/2-r).abs())
}

fn main(){
    let n: usize = read_as_vec()[0];
    let mut a = read_as_vec::<i64>();
    a.sort();
    let mut ans: (i64, i64) =(*a.last().unwrap(), 0);
    a.pop();
    a.sort_by_key(|x| custom_abs(ans.0, *x));
    ans.1 = *a.first().unwrap();
    //println!("{:?}", a);
    println!("{} {}", ans.0, ans.1);
}


Measured memory_bytes: 6396
import Data.List

func::Int->Int->Int->Int
func x y z = x - (div x y) - (div x z) + (div x (lcm y z))

main::IO ()
main = do
    [a,b,c,d] <- map read . words <$> getLine
    print $ (func b c d) - (func (a-1) c d)

Measured memory_bytes: 508
using System;
 
namespace Application
{
	class Solution
	{
		static void Main(string[] args)
		{
			var inputWords = Console.ReadLine().Split(' ');
 
			var a = int.Parse(inputWords[0]);
			var b = int.Parse(inputWords[1]);
 
			var product = a * b;
 
			var result = "Odd";
 
			if(product % 2 == 0)
			{
				result = "Even";
			}
 
			Console.WriteLine(result);
		}
	}
}

Measured memory_bytes: 11092
#include <stdio.h>
#include <stdlib.h>

int main()
{
  int a,d,s=0;
  scanf("%d",&a);
  while(a>=5)
  {
      if(a>=500)
      {
          d=a/500;
          s=s+d*1000;
          a=a%500;
      }
      else if(a>=5)
      {
          d=a/5;
          s=s+d*5;
          a=a%5;
      }
  }
  printf("%d",s);
}

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

namespace B{
    class Problem{
        static void Main(){
            var _ = Console.ReadLine().Split().Select(i=>int.Parse(i)).ToList();
            var N = _[0];
            var X = _[1];
            var ms = new List<int>();
            for (int i = 0; i < N; i++)
            {
                var m = int.Parse(Console.ReadLine());
                ms.Add(m);
            }
            int count = 0;
            foreach (var m in ms)
            {
                X -= m;
                count++;
            }
            count += X / ms.Min();
            Console.WriteLine(count);
        }
    }
}

Measured memory_bytes: 13396
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

string s;
char dpn;
int n, a, b, ans;

int main() {
  cin >> s;
  s = '2' + s + '2';
  n = s.size();
  // if(n == 2) {
  //   if(s == "01" || s == "10") {
  //     printf("1\n");
  //   } else {
  //     printf("2\n");
  //   }
  //   return 0;
  // }
  dpn = s[(n - 1) / 2];
  // printf("--- %d %d %d %d ---\n", n, (n - 1) / 2, (n - 1) / 2 - 1, (n + 1) / 2);
  
  for(int i = (n - 1) / 2 - 1; i >= 0; i--) {
    if(s[i] != dpn) {
      a = i + 1;
      break;
    }
  }
  for(int i = (n + 1) / 2; i < n; i++) {
    if(s[i] != dpn) {
      b = i - 1;
      break;
    }
  }
  // printf("-- %d %d --\n", a, b);
  // if(a == n - 1 && b == 0) {
  //   ans = n - 1;
  // } else if(b == 0) {
  //   ans = n - a;
  // } else if(a == n - 1) {
  //   ans = b + 1;
  // } else {
    ans = min(n - a - 1, b);
  // }
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 512
pos=[0,4,6,8]
S=gets.chomp
0.upto(15) do |i|
  s = "AKIHABARA".split("")
  0.upto(3) do |j|
    if (i >> j) & 1 == 1 then
      s[pos[j]] = "" 
    end
  end

  if s.join("") == S
    puts "YES"
    exit
  end
end
puts "NO"

Measured memory_bytes: 1788
#include<stdio.h>

int dp[50];

int fib(int n){
  if(n==0 || n==1) return dp[n]=1;
  if(dp[n]!=-1) return dp[n];

  return dp[n] = fib(n-1)+fib(n-2);
}

int main(){

  int  i,n;

  for(i=0;i<50;i++) dp[i]=-1;

  scanf("%d",&n);
  printf("%d\n",fib(n));

  return 0;
}
/*
#include<stdio.h>
 
int dp[50];
 
int fib(int n){
  if(n==0 || n==1) return dp[n]=1;
  if(dp[n]!=-1) return dp[n];
 
  return dp[n] = fib(n-1)+fib(n-2);
}
 
int main(){
 
  int  i,n;
 
  for(i=0;i<50;i++) dp[i]=-1;
 
  scanf("%d",&n);
  printf("%d\n",fib(n));
 
  return 0;
}
*/



Measured memory_bytes: 2104
import qualified Data.ByteString.Char8 as B
import Data.List

main = do
    n <- readLn :: IO Int
    xs <- sort . (zipWith (-)  [1..n]) . map read . words . B.unpack <$> B.getLine
    let y = xs !! (n `quot` 2)
    print $ foldl' (\a x -> a + (abs $ x-y)) 0 xs

Measured memory_bytes: 32120
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
	vector<long long> dam, sol;
	long long tot = 0, sub = 0;
	int n, i;
	long long input;

	scanf("%d", &n);

	for (i = 0; i < n; i++)
	{
		scanf("%lld", &input);

		dam.push_back(input);

		tot += input;
	}

	for (i = 1; i < n; i += 2)
	{
		sub += dam[i];
	}

	sol.push_back(tot - sub * 2);

	for (i = 1; i < n; i++)
	{
		sol.push_back(dam[i - 1] * 2 - sol[i - 1]);
	}

	for (i = 0; i < n; i++)
	{
		printf("%lld ", sol[i]);
	}

	return 0;
}

Measured memory_bytes: 3060
N, X = gets.split.map(&:to_i)
ans = 0

size_table = Array.new(N + 1)
size_table[0] = 1
(1..N).each do |n|
  size_table[n] = 3 + size_table[n - 1] * 2
end

def dfs(n, i, size_table)
  return 1 if n == 0
  return 0 if i < n
  size = size_table[n]
  return 2 ** (n + 1) - 1 if i >= size - n - 1
  if i == (size - 1) / 2
    # center
    1 + dfs(n - 1, size_table[n - 1] - 1, size_table)
  elsif i < (size - 1) / 2
    # left
    dfs(n - 1, i - 1, size_table)
  else
    # right
    dfs(n - 1, size_table[n - 1] - 1, size_table) + \
      1 + \
      dfs(n - 1, i - 2 - size_table[n - 1], size_table)
  end
end

ans = dfs(N, X - 1, size_table)
puts ans


Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
int n,k,ans;
int main(){
	scanf("%d %d",&n,&k);
	int mx=(n-1)*(n-2)/2;
	if(k>mx){
		puts("-1");
		return 0;
	}
	printf("%d\n",n-1+mx-k);
	for(int i=2;i<=n;i++){
		printf("%d %d\n",1,i);
	}
	for(int i=2;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(mx==k){
				return 0;
			}
			mx--;
			printf("%d %d\n",i,j);
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n;i>=0;i--)
#define MAX 100001
#define B 100
#define dpb push_back
#define fi first
#define se second
typedef pair<int, int> P;
typedef long long ll;
const int inf = 1e9;
const ll INF = 1e16;
//__gcd(a,b), __builtin_popcount(a);

vector<int> G[MAX];
ll C[MAX], cost[MAX];
int main(){
	int n, m, k, s, t1, t2;
	int a, b;
	queue<P> que;
	fill(cost, cost+MAX, INF);
	scanf("%d%d%d%d", &n, &m, &k, &s);
	scanf("%d%d", &a, &b);
	rep(i,k){
		scanf("%d", &t1);
		C[t1] = s+1;
		que.push(P(s+1, t1));
	}
	rep(i,m){
		scanf("%d%d", &t1, &t2);
		G[t1].push_back(t2);
		G[t2].push_back(t1);
	}
	
	while(!que.empty()){
		P p = que.front();que.pop();
		if(C[p.se] < p.fi)continue;
		for(int i = 0;i < G[p.se].size();i++){
			int from = p.se, to = G[p.se][i];
			if(C[to] < p.fi-1){
				C[to] = p.fi-1;
				que.push(P(C[to], to));
			}
		}
	}
	
	ll tmp;
	priority_queue<P, vector<P>, greater<P> > q;
	q.push(P(0, 1));
	cost[1] = 0;
	while(!q.empty()){
		P p = q.top();q.pop();
		if(cost[p.se] < p.fi)continue;
		for(int i = 0;i < G[p.se].size();i++){
			int from = p.se, to = G[p.se][i];
			if(C[to] == 0)tmp = a;
			else tmp = b;
			if(to == n)tmp = 0;
			if(C[to] == s+1)tmp = INF;
			if(cost[to] > cost[from]+tmp){
				cost[to] = cost[from]+tmp;
				q.push(P(cost[to], to));
			}
		}
	}
	
	//for(int i = 1;i <= n;i++)printf("%lld ", cost[i]);
	printf("%lld\n", cost[n]);
	return 0;
}

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

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

    long long N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    vector<long long> ruiseki(N + 1);
    vector<long long> revRuiseki(N + 1);
    for (int i = 0; i < N; i++) {
        ruiseki[i + 1] = A[i] + ruiseki[i];
    }
    reverse(A.begin(), A.end());
    for (int i = 0; i < N; i++) {
        revRuiseki[i + 1] = A[i] + revRuiseki[i];
    }
    reverse(revRuiseki.begin(), revRuiseki.end());

    long long ans = 100000000000007;
    for (int i = 1; i < ruiseki.size() - 1; i++) {
        ans = min(abs(ruiseki[i] - revRuiseki[i]), ans);
    }
    cout << ans << endl;
}

Measured memory_bytes: 4992
#define  _CRT_SECURE_NO_WARNINGS
#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-11L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144*2LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

unsigned long xor128() {
	static unsigned long x = 123456789, y = 362436069, z = 521288629, w = time(NULL);
	unsigned long t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

void init() {
	iostream::sync_with_stdio(false);
	cout << fixed << setprecision(20);
}

#define int ll

void solve() {
	while (true) {
		int h, w;
		cin >> h >> w;
		if (h == 0) return;
		vector<string> inputs;
		REP(i, h) {
			string s;
			cin >> s;
			inputs.push_back(s);
		}
		map<string, int> cnter;
		REP(i, h) {
			REP(q, w) {
				int dx[3] = { 1,0,-1 };
				REP(j, 3) {
					REP(t, 3) {
						if (j == 1 && t == 1) continue;
						pair<int, int> now = mp(i, q);
						string s;
						while (true) {
							s.push_back(inputs[now.first][now.second]);
							now.first += dx[j];
							now.second += dx[t];
							now.first += h;
							now.second += w;
							now.first %= h;
							now.second %= w;
							cnter[s]++;
							if (now.first == i && now.second == q) break;
						}
					}
				}
			}
		}
		//cout << cnter["ABRACADABRA"] << endl;
		string ans = "0";
		for (auto x : cnter) {
			if (x.second >= 2) {
				if (ans.length() < x.first.length()) {
					ans = x.first;
				}
			}
		}
		cout << ans << endl;
	}
}

#undef int
int main() {
	init();
	solve();
}


Measured memory_bytes: 38004
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#define MAX_N 100010
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
vector<ll> G[MAX_N];
ll a[MAX_N];
bool used[MAX_N]={};
void dfs(int v,vector<ll>& vals){
  if(used[v]) return;
  used[v] = true;
  vals.push_back(a[v]);
  for(auto i:G[v]){
    dfs(i,vals);
  }
}
signed main(){
  ll n,m,ans=0,need;
  cin >> n >> m;
  ll x[m],y[m];
  priority_queue<ll,vector<ll>,greater<ll>> que;
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  for(int i=0;i<m;i++){
    cin >> x[i] >> y[i];
    G[x[i]].push_back(y[i]);
    G[y[i]].push_back(x[i]);
  }
  if(m==n-1){
    cout <<"0\n";
    return 0;
  }
  need = 2*(n-m-1);
  for(int i=0;i<n;i++){
    vector<ll> vt;
    if(!used[i]){
      dfs(i,vt);
      sort(vt.begin(),vt.end());
      ans += vt[0];
      need--;
      for(int j=1;j<vt.size();j++){
        que.push(vt[j]);
      }
    }
  }
  if(need<0){
    cout <<"Impossible\n";
    return 0;
  }
  for(int i=0;i<need;i++){
    if(que.empty()){
      cout <<"Impossible\n";
      return 0;
    }
    ans += que.top();
    que.pop();
  }
  cout << ans << endl;
}


Measured memory_bytes: 10996
package main

import (
	"fmt"
)

func main() {
	type pair struct {
		a int
		b int
	}

	var pairList []pair
	var a, b int
	for {
		fmt.Scan(&a, &b)
		if a == 0 && b == 0 {
			break
		}
		pairList = append(pairList, pair{a: a, b: b})
	}

	for _, pair := range pairList {
		for i := 0; i < pair.a; i++ {
			for j := 0; j < pair.b; j++ {
				if i == 0 || i == pair.a-1 || j == 0 || j == pair.b-1 {
					fmt.Print("#")
					continue
				}
				fmt.Print(".")
			}
			fmt.Println()
		}
		fmt.Println()
	}
}



Measured memory_bytes: 1120
Module Program
  Sub Main
    Dim s = GetInts()
    Dim a=s(0),b=s(1)
    Dim ans=If(a<=8 And b<=8,"Yay!",":(")
    Console.WriteLine(ans)
  End Sub
  
  '/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/
  Function Gets() As String()
    Gets = Console.ReadLine().Split(" "c)
  End Function
  Function GetInts() As Integer()
    Dim s = Gets(), r(UBound(s)) As Integer
    For i As Integer=0 To UBound(s): r(i)=s(i): Next i
    GetInts = r
  End Function
End Module

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

class Dice{
    public:
    int f[6];
    Dice(){};
    void rollS(){roll(0,1,5,4);}
    void rollE(){roll(0,2,5,3);}
    void rollR(){roll(1,2,4,3);}
    void roll(int a, int b, int c, int d){
        int e = f[a]; f[a] = f[b]; f[b] = f[c]; f[c] = f[d]; f[d] = e;
    }
};

bool check(Dice d1,Dice d2){
    for (int i = 0; i < 6; i++){
        if (d1.f[i] != d2.f[i]) return false;
    }
    return true;
}

bool fullcheck(Dice d1, Dice d2){
    for (int i = 0; i < 6; i++){
        for (int j = 0; j < 4; j++){
            if (check(d1,d2)) return true;
            d1.rollR();
        }
        if (i % 2 == 0) d1.rollS();
        else d1.rollE();
    }
    return false;
}

Dice D[100]; int n;
bool allcheck(){
    for(int i = 0; i < n-1; i++){
        for (int j = i+1; j < n; j++){
            if (fullcheck(D[i],D[j])) return false;
        }
    }
    return true;
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < 6; j++){
            cin >> D[i].f[j];
        }
    }
    if (allcheck()) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3100
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

struct Point{
  double x, y;
};

int main(){
  int n;
  Point P[51];
  int cs = 0;
  while(cin >> n, n){
    for(int i = 0 ; i < n ; i++){
      cin >> P[i].x >> P[i].y;
    }

    double area = 0;
    
    for(int i = 0 ; i < n-1 ; i++){
      area += P[i].x * P[i+1].y - P[i].y * P[i+1].x;
    }
    area += P[n-1].x * P[0].y - P[n-1].y * P[0].x;

    printf("%d %.1f\n", ++cs, abs(area)/2);
  }
  return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<climits>
#include<set>
#include<map>
#define ll long long
using namespace std;

int main() {
	ll a, b, c;
	cin >> a >> b >> c;
	cout << ((c >= a && c <= b) ? "Yes" : "No")<<endl;

}

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

#pragma warning(disable : 4996)

using namespace std;

int H, W, N, r[1000][1000], dp[1001][1001];

int main()
{
	while (true)
	{
		scanf("%d", &H);
		scanf("%d", &W);
		scanf("%d", &N);

		if (H == 0 && W == 0 && N == 0) { break; }

		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				scanf("%d", &r[i][j]);
			}
		}

		memset(dp, 0, sizeof(dp));

		dp[0][0] = N;

		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				if (dp[i][j] % 2 == 0)
				{
					dp[i + 1][j] += dp[i][j] / 2;
					dp[i][j + 1] += dp[i][j] / 2;
				}
				else
				{
					if (r[i][j] == 0)
					{
						dp[i + 1][j] += dp[i][j] / 2 + 1;
						dp[i][j + 1] += dp[i][j] / 2;
					}
					else
					{
						dp[i + 1][j] += dp[i][j] / 2;
						dp[i][j + 1] += dp[i][j] / 2 + 1;
					}
				}
			}
		}

		int x = 0, y = 0;

		while (x != W && y != H)
		{
			int dir = (r[y][x] + dp[y][x] + 1) % 2;

			if (dir == 0)
			{
				y++;
			}
			else
			{
				x++;
			}
		}

		printf("%d %d\n", y + 1, x + 1); // 1 - indexed
	}

	return 0;
}

Measured memory_bytes: 10992
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

typedef unsigned long long int ulint;
typedef long long int lint;

template<typename T>
T nPermute(vector<T> str) 
{
  // cout << "str=" << str[0] << endl;
  ulint n = str.size();
  vector<T> str0;
  for (int i = 1; i <= n; ++i) {
    str0.push_back(i);
  }
  
  // Keep iterating until 
  // we reach nth position 
  ulint i = 0;

  if (equal(str.begin(), str.end(), str0.begin())) {
    return 0;
  }
  
  do { 
    // for (int j = 0; j < n; ++j) {
    //   cout << str0[j] << " ";
    // }
    // cout << endl;
    
    next_permutation(str0.begin(), str0.end());
    i++;
  } while (!equal(str.begin(), str.end(), str0.begin())); 
  
  // print string after nth iteration 
  return i; 
} 
  

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

  vector<ulint> P;
  for (int i = 0; i < N; ++i) {
    ulint p;
    cin >> p;
    //--p;
    P.push_back(p);
  }
  
  vector<ulint> Q;
  for (int i = 0; i < N; ++i) {
    ulint q;
    //--q;
    cin >> q;
    Q.push_back(q);
  }

  
  ulint pp = nPermute(P);
  ulint pq = nPermute(Q);

  // cout << "pp=" << pp << endl;
  // cout << "pq=" << pq << endl;

  cout << max(pp, pq) - min(pp, pq) << endl;
}


Measured memory_bytes: 888
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
//#include <intrin.h>

#define fore(i,a,b) for(int i = a; i < (b); i++)
#define fr(i,a,b) for(int i = a - 1; i >= b; i--)
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define N 300005
#define inf 2000000000
#define EPS 1e-6
#define MOD 998244353ll
#define __builtin_popcount(x) __popcnt(x)

using namespace std;

typedef long long ll;

inline void solve()
{
	int n, m;
	cin >> n >> m;
	cout << (n * (n - 1)) / 2 + (m * (m - 1)) / 2;
}

int main()
{
	fast;
#if defined(_DEBUG)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int q = 1;
	//cin >> q;
	while (q--)
	{
		solve();
		cout << '\n';
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <utility>
#include <set>
#include <map>
#include <tuple> 
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <list>
using namespace  std;
typedef pair<long long , long long> P;
typedef long long ll;
typedef long long lint;
#define REP(i, n) for(long long (i)=0; (i)<(n); ++i)
#define FOR(i, a, b) for(long long (i)=(a); (i)<(b); ++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
const long long MOD = static_cast<long long>(1e9) + 7LL;
const long long INF = 1234567891234567890LL;


ll N;
vector<ll> A, res;
ll rec(ll x){
    //cout << "------" << endl;
    //cout << res << endl;
    //cout << "------" << endl;
    if(res[x-1]!= -1) return res[x-1];
    if(x>N/2){
        return res[x-1] = A[x-1];
    }
    int par = 0;
    for(ll j=2; x*j<=N; j++){
        par += rec(j*x);
    }
    if(A[x-1]==1){
        if(par%2==1) return res[x-1] = 0;
        else return res[x-1] = 1;
    }
    else {
        if(par%2==1) return res[x-1] = 1;
        else return res[x-1] = 0;
    }
}
signed main(){
    cin>>N;
    A.resize(N), res.resize(N+1, -1);
    REP(i, N) cin>>A[i];
    bool exists = true;
    rec(1LL);
    if(exists){
        cout << count(ALL(res), 1) << endl;
        REP(i, N) if(res[i]) cout << i+1 << endl; 
    }
    else cout << -1 << endl;
    //cout << res << endl;
    return 0;
}

Measured memory_bytes: 3968
#include <iostream>
#include <string>
using namespace std;
int main(){
  long N,D,X,i,j,total=0;
  int A[100],count[100];
  cin>>N>>D>>X;
  for(i=0;i<N;i++)cin>>A[i];

  for(i=0;i<N;i++){
    count[i]=0;
    for(j=0;;j++){
      if (j*A[i]+1<=D) count[i]++;
      else break;
  }
}
  for(i=0;i<N;i++){
    total=total+count[i];
  }
  cout <<total+X;
}

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

typedef pair<int, int> state;
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    const int INF = 1.0e9;
    bitset<20000> bs;
    for(int N, M; cin >> N >> M && N;) {
        vector<vector<tuple<int, int, int>>> G(N);
        vector<int> edgecost(M);
        rep(i, M) {
            int u, v, d, c;
            cin >> u >> v >> d >> c;
            --u; --v;
            G[u].emplace_back(v, d, i);
            G[v].emplace_back(u, d, i);
            edgecost[i] = c;
        }
        vector<int> mdist(N, INF), preE(N, -1);
        mdist[0] = 0;
        priority_queue<state, vector<state>, greater<state>> que;
        que.emplace(0, 0);
        vector<int> useEdge(M, 0);
        while(!que.empty()) {
            int dis, cur;
            tie(dis, cur) = que.top(); que.pop();
            if(mdist[cur] < dis) continue;
            for(const auto& e : G[cur]) {
                int nv, ndis, num;
                tie(nv, ndis, num) = e;
                int costdec = 0;
                if(preE[nv] != -1) {
                    costdec -= edgecost[preE[nv]];
                    if(useEdge[num] == 0) costdec += edgecost[num];
                }
                if(mdist[nv] > dis + ndis || (mdist[nv] == dis + ndis && costdec < 0)) {
                    mdist[nv] = dis + ndis;
                    if(preE[nv] != -1) --useEdge[preE[nv]];
                    preE[nv] = num; ++useEdge[num];
                    que.emplace(mdist[nv], nv);
                }
            }
        }
        int ans = 0;
        rep(i, M) if(useEdge[i] > 0)
          ans += edgecost[i];
        cout << ans << endl;
    }
    return 0;
}

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

int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a % b); }

#define CIN(T, x) T x; cin >> x;
#define CINS(T, x, N) vector<T> x(N); for(int i = 0; i < (N); i++) { cin >> x[i]; }
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << " "; } cout << "\n";
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << "\n";

ll MOD = 1e9+7;
int MAX = 2005;
vector<vector<ll>> nCk(MAX, vector<ll>(MAX, 0));

void calc_nCk() {
    nCk[0][0] = 1;
    for (int i = 1; i < MAX; i++) {
        nCk[i][0] = 1;
        for (int j = 1; j < MAX; j++) {
            nCk[i][j] = (nCk[i - 1][j - 1] + nCk[i - 1][j]) % MOD;
        }
    }
}

int main() {

    CIN(int, N);
    CIN(int, K);
    calc_nCk();

    int R = N - K;
    int B = K;

    for (int i = 1; i <= K; i++) {
        cout << ((nCk[R+1][i] * nCk[B-1][i-1]) % MOD) << "\n";
    }

    return 0;
}

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

int main(){
    int N, M; cin >> N >> M;
    string A[N]; rep(i,N) cin >> A[i];
    string B[M]; rep(i,M) cin >> B[i];

    bool a[N][N], b[M][M];
    rep(i,N){
        rep(j,N){
            if(A[i][j] == '#') a[i][j] = false;
            else a[i][j] = true;
        }
    }
    rep(i,M){
        rep(j,M){
            if(B[i][j] == '#') b[i][j] = false;
            else b[i][j] = true;
        }
    }

    bool tmp;
    rep(i,N-M+1){
        rep(j,N-M+1){
            tmp = true;
            for(int k=i; k<M+i; k++){
                for(int l=j; l<M+j; l++){
                    tmp = tmp & (a[k][l] == b[k][l]);
                }
            }
            if(tmp) break;
        }
        if(tmp) break;
    }
    if(tmp) cout << "Yes" << endl;
    else cout << "No" << endl;


}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define MAX 2222
ll mystoi(string s){
  if(s=="+") return 1;
  if(s=="-") return -1;
  return stoi(s);
}
signed main(){
  string s;
  cin>>s;
  ll n=s.length();
  ll k=s[2]-'0';
  vector<ll> v;
  string tmp;
  vector<string> vs;
  for(ll i=0;i<n;i++){
    if(s[i]=='+'||s[i]=='-'){
      vs.push_back(tmp);
      tmp=s[i];
    }else tmp+=s[i];
  }
  vs.push_back(tmp);
  vector<P> vp;
  for(ll i=0;i<(ll)vs.size();i++){
    //cout<<vs[i]<<endl;
    ll x=vs[i].find("x"),y=vs[i][vs[i].size()-1]-'0';
    if(x==-1){
      vp.push_back(P(mystoi(vs[i]),0));
      continue;
    }
    if((ll)vs[i].find("^")==-1) y=1;
    if(x==0) vp.push_back(P(1,y));
    else vp.push_back(P(mystoi(vs[i].substr(0,x)),y));
  }
  /*/
  for(ll j=0;j<(ll)vp.size();j++)
    cout<<vp[j].first<<" "<<vp[j].second<<endl;
  //*/
  for(ll i=-MAX;i<MAX;i++){
    ll res=0;
    for(ll j=0;j<(ll)vp.size();j++){
      ll t=1;
      for(ll l=0;l<vp[j].second;l++) t*=i;
      res+=vp[j].first*t;
    }
    //cout<<i<<" "<<res<<endl;
    if(!res) v.push_back(i);
  }
  reverse(v.begin(),v.end());
  for(ll i=0;i<k;i++) printf("(x%+lld)",-v[i]);
  puts("");
  return 0;
}

    

Measured memory_bytes: 3296
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args)throws Exception {
    	InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);

        while(true){
        	String[] input = br.readLine().split(" ");
        	int H = Integer.parseInt(input[0]);
        	int W = Integer.parseInt(input[1]);
        	if(H == 0 && W == 0){
        		break;
        	}
        	for(int x = 0 ; x < H ; x++){
        		for(int y = 0; y < W ; y++){
        			if((x + y) % 2 == 0 ){
        				System.out.print("#");
        			}else{
        				System.out.print(".");
        			}
        		}
        		System.out.println();
        	}
        	System.out.println();
        }
    }
}

Measured memory_bytes: 35228
#include<bits/stdc++.h>
using namespace std;
using lint = long long;
using itn = int;
template<class T>
using vec = vector<T>;

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

int GetF(lint a,lint b){
  int da=1,db=1;
  while(a){
    a /= 10;
    if(a) ++da;
  }
  while(b){
    b /= 10;
    if(b) ++db;
  }

  return max(da,db);
}


int main(){


  lint n;
  cin >>n;

  int ans=10;
  for(lint i=1;i<int(sqrt(n))+1;i++){
    if(n%i == 0){
      ans = min(ans,GetF(n/i,i));
    }
  }

  cout <<ans <<endl;

}


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

typedef long long int ll;

 ll func(vector<ll>&nums,ll start,ll end,vector<vector<ll> >&dp){
        
        if(start==end)return dp[start][end]=nums[start];
        if(start+1==end)return dp[start][end]= max(nums[start],nums[end]);
        
        if(dp[start][end]!=-1)return dp[start][end];
        
    return dp[start][end]=
        max(nums[start]+
            min(func(nums,start+2,end,dp),func(nums,start+1,end-1,dp)),
        nums[end]+
            min(func(nums,start+1,end-1,dp),func(nums,start,end-2,dp)));
        
    }
    

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll n;
    cin>>n;

    vector<ll>nums(n);
    for(ll &x:nums)cin>>x;
        
    ll sum=0;
                
    for(ll x:nums)sum+=x;
                
    vector<vector<ll> >dp(n+1,vector<ll>(n+1,-1));
                
    ll first=func(nums,0,n-1,dp);

    cout<<2*first - sum;

    return 0;

}

Measured memory_bytes: 73868
#include <stdio.h>
#include <string.h>
int main() {
  char S[15];
  scanf("%s", S);
  int i,count=0;
  for(i=0;i<15;i++){
    if(S[i] == 'x'){
      count++;
    }
  }

  if(count < 8){
    printf("YES");
  }
  else{
    printf("NO");
  }
  return 0;
}


Measured memory_bytes: 128
from collections import defaultdict
from heapq import heappop, heappush


class Graph():

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra():

    def __init__(self, graph, start):
        self.g = graph.graph

        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0

        self.prev = defaultdict(lambda: None)

        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            dist_u, u = heappop(self.Q)

            if self.dist[u] < dist_u:
                continue

            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):

        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal

        while node is not None:
            path.append(node)
            node = self.prev[node]

        return path[::-1]


import sys
input=sys.stdin.readline
n,m=map(int,input().split())
g=Graph()

for _ in range(m):
    l,r,c=map(int,input().split())
    g.add_edge(l,r,c)
for i in range(2,n+1):
    g.add_edge(i,i-1,0)


d = Dijkstra(g,1)
ans=d.shortest_distance(n)
print(ans if ans!=float("inf") else -1)


Measured memory_bytes: 73368
#include<iostream>
#include<algorithm>
using namespace std;
static const int MAX=200000;

int main(){
  int R[MAX], n;

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

  int maxv=-2000000000;
  int minv=R[0];

  for (int i=1; i<n; i++){
    maxv=max(maxv, R[i]-minv);
    minv=min(minv, R[i]);
  }

  cout << maxv << endl;

  return 0;
}

Measured memory_bytes: 3872
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	vector<int> a(n+1, 1);
	ll ans = 0;
	for (ll i=2; i<=n; i++) {
		a[i]++;
		ans += i*a[i];
		for (ll j=i+i; j<=n; j+=i) {
			a[j]++;
		}
	}
	cout << ans+1 << '\n';
}

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

int n,a[100009];
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}

bool Dfs(int x)
{
	int odd=0,even=0,flag=1;
	for (int i=1; i<=n; ++i)
		if (a[i]%2) {a[i]--; break;}
	int g=a[1];
	for (int i=2; i<=n; ++i) g=gcd(g,a[i]);
	for (int i=1; i<=n; ++i)
	{
		a[i]/=g;
		if (!(a[i]%2)) even++;
		else odd++;
		if (a[i]==1) flag=0;
	}
	if (even%2) return !x;
	if (odd!=1 || !flag) return x;
	return Dfs(x^1);
}

int main()
{
	int odd=0,even=0,flag=1;
	scanf("%d",&n);
	for (int i=1; i<=n; ++i)
	{
		scanf("%d",&a[i]);
		if (a[i]%2) odd++;
		else even++;
		if (a[i]==1) flag=false;
	}
	if (even%2) puts("First");
	else if (odd!=1 || !flag) puts("Second");
	else if (Dfs(1)) puts("First");
	else puts("Second"); 
}

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

int main()
{
    ios_base::sync_with_stdio(false);	
    
    int k;
    cin >> k;
    long long sum = 0;
    for(int a = 1; a <=k; a++)
    {
		for(int b = 1; b <=k; b++)
		{
			for(int c = 1; c <=k; c++)
			{
				int gcd = __gcd(a,b);
				sum += __gcd(gcd, c);
			}
		}
	}
    cout << sum;
    return 0;
}



Measured memory_bytes: 3652
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n,a[100001],m,b[100001];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;++i)
		if(a[i]!=a[i-1])b[++m]=1;
		else ++b[m];
	n=unique(a+1,a+n+1)-a-1;
	int x=0,y=0;
	for(int i=n;i;--i)
	    if(b[i]>=2){b[i]-=2,x=a[i];break;}
	for(int i=n;i;--i)
	    if(b[i]>=2){y=a[i];break;}
	printf("%lld\n",1LL*x*y);
}

Measured memory_bytes: 1024
n = int(input())
aa = [
    list(map(int, input().split()))
    for _ in range(2)
]

if n == 1:
    print(aa[0][0] + aa[1][0])
    exit(0)

for i in range(1, n):
    aa[1][-i - 1] += aa[1][-i]
for i in range(1, n):
    aa[0][-i - 1] += max(aa[1][-i - 1], aa[0][-i])
print(aa[0][0])

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

int main() {
	int a, b, c, d, e, f, g = 0;
	std::cin >> a >> b >> c >> d >> e >> f;
	g += a + b + c + d - std::min({ a, b, c, d });
	g += std::max(e, f);
	std::cout << g << std::endl;
}


Measured memory_bytes: 3100
class Data:
    def __init__(self,n):
        self.n = n
        self.abc = []
        self.dp = [[0,0,0]]

    def input_abc(self):
        for i in range(self.n):
            self.abc.append(list(map(int,input().split())))
    
    def chmax(self,i,j,k):
        a = self.dp[i-1][j] + self.abc[i-1][k]
        b = self.dp[i][k]
        if (a>b):
            self.dp[i][k] = a
        #print("j",j,"k",k,a,b,"\n",self.dp)
def main():
    n = int(input())
    data = Data(n)
    data.input_abc()
    for i in range(1,n+1):
        data.dp.append([0,0,0])
        for j in range(3):
            for k in range(3):
                if j != k:
                    data.chmax(i,j,k)
    print(max(data.dp[i]))

if __name__ == "__main__":
    main()


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

int main() {
    int N, K;
    int num=0;
    cin >> N >> K;
    while(pow(K, num) <= N) {
        num += 1;
    }
    cout << num << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
  int N;
  long long ans=1;
  cin>>N;
  for(int i=1;i<=N;i++){
    ans*=i;
    if(ans>1000000007) ans%=1000000007;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
import math
import sys
def input(): return sys.stdin.readline().strip()

def main():
    n,d=map(int,input().split())
    xx=[]
    for _ in range(n):
        xx.append(list(map(int,input().split())))
    c = 0
    for i in range(n):
        for j in range(i+1,n): 
            dist=math.sqrt(sum((xx[j][k]-xx[i][k])**2 for k in range(d)))
            if dist-int(dist) == 0:
                c+=1
    print(c)

main()

Measured memory_bytes: 3064
N=int(input())
P=10**9+7
A=[int(i) for i in input().split()]
B=[-1 for i in range(N)]
s=(-1,-1)
for i in range(N+1):
    if B[A[i]-1]==-1:
        B[A[i]-1]=i
    else:
        s=(B[A[i]-1],i)
        break
M=N-s[1]+s[0]+1
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
Fact=[0 for i in range(N+2)]
Finv=[0 for i in range(N+2)]
Fact[0]=1
Finv[0]=1
for i in range(1,N+2):
    Fact[i]=(i*Fact[i-1])%P
    Finv[i]=inv(Fact[i])%P
def C(n,k):
    return (((Fact[n]*Finv[k])%P)*Finv[n-k])%P
ans=[0 for i in range(N+1)]
for i in range(1,N+2):
    if i<=M:
        ans[i-1]=(C(N+1,i)-C(M-1,i-1))%P
    else:
        ans[i-1]=C(N+1,i)%P
for i in ans:
    print(i)


Measured memory_bytes: 23944
N = int(input())
li = input().rstrip().split()

le =[0]*N
le2 = [0]*N

for i in range(0,N):
    le[i]=int(li[i])


for i in range(0,N):
    le2[i]=le[i]-i-1
le2.sort()


b = le2[int(N/2)]
sum = 0
for i in range(0,N):
    sum = sum + abs(le[i]-i-1-b)

print(sum)


Measured memory_bytes: 34292