akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdio>
#include <cassert>
using namespace std;
typedef pair<int, int> PII;
const int ALLDAY = 24 * 60;
const string WD[] = {"Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"};
double calc(int a, int n, int p){
  double pp = 1.0 - (1.0 / (double)p);
  return 1.0 - pow(pp, a*n);
}
PII get_next(int cur_min, int weekday, int step){
  int nmin = cur_min + step;
  if(nmin >= ALLDAY){
    return make_pair(nmin % ALLDAY, (weekday+1) % 7);
  }
  return make_pair(nmin, weekday);
}
int main(){
  int s, n, t, p, m;
  string weekday, time;
  while(true){
    cin >> s >> n >> t >> weekday >> time >> p >> m;
    if((s|n|t|p|m) == 0 && weekday == "None" && time == "None"){
      break;
    }
    bool flag_time[ALLDAY], flag_wd[7];
    if(time == "All"){
      fill_n(flag_time, ALLDAY, true);
    }
    else if(time == "Day"){
      fill_n(flag_time, ALLDAY, false);
      fill_n(flag_time+6*60, ALLDAY/2, true);
    }else{
      fill_n(flag_time, ALLDAY, true);
      fill_n(flag_time+6*60, ALLDAY/2, false);
    }
    if(weekday == "All"){
      fill_n(flag_wd, 7, true);
    }
    else{
      fill_n(flag_wd, 7, false);
      for(int i = 0; i < 7; ++i){
	if(weekday == WD[i]){
	  flag_wd[i] = true;
	  break;
	}
      }
    }
    int max_a = 0;
    for(int s_min = 0; s_min < ALLDAY; ++s_min){
      for(int s_wd = 0; s_wd < 7; ++s_wd){
	int a = 0;
	int c_min = s_min, c_wd = s_wd;
	for(int g = 0; g < m; ++g){
	  assert(c_min!=ALLDAY); //
	  assert(c_wd<7); //
	  PII huka = get_next(c_min, c_wd, s);
	  if(flag_time[huka.first] && flag_time[c_min] && flag_wd[c_wd] && flag_wd[huka.second]){
	    ++a;
	  }
	  PII next = get_next(c_min, c_wd, t);
	  c_min = next.first;
	  c_wd = next.second;
	}
	max_a = max(max_a, a);
      } 
    }
    //cout << max_a << endl;
    printf("%0.11f\n", calc(n, max_a, p));
  }
  return 0;
}

Measured memory_bytes: 1276
# -*- coding: utf-8 -*-
import sys
from math import gcd

N, *AB = map(int, sys.stdin.buffer.read().split())

dict_F = {}
count_0 = 0

def insert(A,B,s): # A>=0, B>0, s=0or1
  if (A,B) not in dict_F.keys():
    dict_F[(A,B)] = [0,0]
  dict_F[(A,B)][s] += 1

def make_power2(N):
  result = 1
  list_result = [1]
  for _ in range(N):
    result = (2*result)%mod
    list_result.append(result)
  return list_result

for i in range(N):
  A,B = AB[2*i], AB[2*i+1]
  if A==0 and B==0:
    count_0 += 1
    continue
  g = gcd(A,B)
  A //= g
  B //= g
  if A>=0 and B>0:
    insert(A,B,0)
  elif A>0 and B<=0:
    insert(-B,A,1)
  elif A<=0 and B<0:
    insert(-A,-B,0)
  elif A<0 and B>=0:
    insert(B,-A,1)

mod = 1000000007
power2 = make_power2(N)
answer = 1

for A,B in dict_F.values():
  answer = (answer*(power2[A]+power2[B]-1))%mod
answer = (answer+count_0-1)%mod

print(answer)

Measured memory_bytes: 92872
#include <bits/stdc++.h>
using namespace std;
 
int main() 
{
  string N;
  cin>>N;
  vector<int> num(N.size());
  for(int i=0;i<N.size();i++){
    if(N[i] == '0')
      num[i] = 0;
    if(N[i] == '1')
      num[i] = 1;
    if(N[i] == '2')
      num[i] = 2;
    if(N[i] == '3')
      num[i] = 3;
    if(N[i] == '4')
      num[i] = 4;
    if(N[i] == '5')
      num[i] = 5;
    if(N[i] == '6')
      num[i] = 6;
    if(N[i] == '7')
      num[i] = 7;
    if(N[i] == '8')
      num[i] = 8;
    if(N[i] == '9')
      num[i] = 9;
  }
  int sum=0;
  for(int i=0;i<N.size();i++){
    sum+=num.at(i);
  }
  if(sum%9 == 0)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}

Measured memory_bytes: 4456
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

n = ini()
a = inl()
ans = 0
tall = 0
for i in range(n):
    ans += max(0, tall - a[i])
    tall = max(tall, a[i])
print(ans)

Measured memory_bytes: 31412
#include<iostream>
#include<cstdio>
#include<cctype>
#include<vector>

int main(){
    char ch;
    std::vector<int> count(26);
    
    while(scanf("%c", &ch) != EOF){
        if(isalpha(ch)){
            ch = (char)tolower(ch);
            int number = ch - 'a';
            count[number]++;
        }
        
    }
    
    for(int i = 0; i < 26; i++){
        printf("%c : %d\n", i + 'a', count[i]);
    }
}


Measured memory_bytes: 3180
#!/usr/bin/env python

n = int(input())

tScore = 0
hScore = 0

for i in range(n):
    T, H = input().split()
    if T == H:
        tScore += 1
        hScore += 1
    elif T > H:
        tScore += 3
    elif H > T:
        hScore +=3
print("%d %d" % (tScore, hScore))

Measured memory_bytes: 7580
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using PP = pair<int,pair<int,int>>;
using T = tuple<string,int,int>;
const string EMP = " ";
const ll INF = 1LL<<60;
const ll MOD = 1000000007;

int main(){
  ull a; double b;
  cin >> a >> b;
  ull bb = b * 100 + 0.5;
  ull ans = a * bb;
  ans /= 100;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3732
import java.util.*;
import java.math.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int W = sc.nextInt();
    int[] w = new int[N];
    int[] v = new int[N];
    for (int i = 0; i < N; i++) {
      w[i] = sc.nextInt();
      v[i] = sc.nextInt();
    }
    sc.close();

    Map<Integer, Long> dp = new HashMap<>();
    Long ZERO = Long.valueOf(0L);
    dp.put(0, ZERO);
    for (int i = 0; i < N; i++) {
      for (int j = W; w[i] <= j; j--) {
        Integer jwi = Integer.valueOf(j - w[i]);
        if (!dp.containsKey(jwi)) continue;
        dp.put(j, Math.max(dp.getOrDefault(j, ZERO), dp.get(jwi) + v[i]));
      }
    }

    long ans = 0;
    for (long val : dp.values()) ans = Math.max(ans, val);
    System.out.println(ans);
  }
}


Measured memory_bytes: 171400
#include <stdio.h>

int main()
{
  char a, b;
  scanf("%c %c", &a, &b);
  if(a == 'H') {
    if(b == 'H') {
      printf("H\n");
    } else {
      printf("D\n");
    }
  } else {
    if(b == 'H') {
      printf("D\n");
    } else {
      printf("H\n");
    }
  }

  return 0;
}

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

int main()
{
	int i, j, n;
	cin >> n;
	int a[n][2];
	float num=0, den, ans;
	for(i=0; i<n; i+=1)
		cin >> a[i][0] >> a[i][1];
	for(i=0; i<n; i+=1)
		for(j=0; j<n; j+=1)
			num+=pow(pow(a[i][0]-a[j][0], 2)+pow(a[i][1]-a[j][1], 2), 0.5);
	den=n;
	ans=num/den;
	cout << fixed << setprecision(12) << ans << endl;
}

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

int main(void)
{
    int n; cin >> n;
    int hon[5] = {2,4,5,7,9};
    int pon[4] = {0,1,6,8};
    int bon[1] = {3};
    n = n % 10;

    for (int a:hon)
    {
        if (a == n)
        {
            cout << "hon" << endl;
            return 0;
        }
    }
    for (int a:pon)
    {
        if (a == n)
        {
            cout << "pon" << endl;
            return 0;
        }
    }
    for (int a:bon)
    {
        if (a == n)
        {
            cout << "bon" << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#ifdef LOCAL_DEBUG
#define DEBUG 1
#define CERR if(DEBUG) cerr
#define MACRO(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,NAME,...) NAME
#define pr(...) CERR<<MACRO(__VA_ARGS__,pr10,pr9,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)<<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define pr9(a,b,c,d,e,f,g,h,i) pr1(a)<<pr8(b,c,d,e,f,g,h,i)
#define pr10(a,b,c,d,e,f,g,h,i,j) pr1(a)<<pr9(b,c,d,e,f,g,h,i,j)
#define prArr(a){CERR<<(#a)<<"={";int i=0;for(auto t:(a))CERR<<(i++?", ":"")<<t;CERR<<"}"<<endl;}
#else
#define DEBUG 0
#define pr(...)
#define prArr(a)
#endif
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE


class UF{
public:
  Int V;
  vector<Int> par,rnk,sz;
  UF(){}
  UF(Int V):V(V),par(V),rnk(V,0),sz(V,1){for(Int i=0;i<V;i++)par[i]=i;}

  Int find(Int x){
    assert(x < V);
    if(par[x]==x)return x;
    return par[x]=find(par[x]);
  }

  void unite(Int x,Int y){
    x=find(x), y=find(y);
    if(x==y)return;
    if(rnk[x]<rnk[y])par[x]=y, sz[y] += sz[x];
    else{
      par[y]=x;
      sz[x] += sz[y];
      if(rnk[x]==rnk[y])rnk[x]++;
    }
  }

  bool same(Int x,Int y){return find(x)==find(y);}

  Int size(Int x){return sz[find(x)];}
};

signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  Int N, M;
  cin>>N>>M;
  UF uf(M);
  set<Int> S;
  for(Int i=0;i<N;i++){
    Int K;
    cin>>K;
    vector<Int> L(K);
    cin>>L;
    for(Int &l:L)l--;
    for(Int l:L) S.insert(l);
    for(Int i=1;i<(Int)L.size();i++) uf.unite(L[0], L[i]);
  }

  //for(Int i=0;i<M;i++) pr(i, uf.size(i));
  Int ans = uf.size(*S.begin()) == (Int)S.size();
  cout<<(ans? "YES":"NO")<<endl;
  return 0;
}


Measured memory_bytes: 5632
#include<stdio.h>
int main(void)
{
  int n,m;
  int i,j,ans;
  scanf("%d %d", &n ,&m);
    i=(n*(n-1))/2;
    j=(m*(m-1))/2;
    ans=i+j;

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


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

using namespace std;

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

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



int main(){
    cin.tie(0);
    cin.sync_with_stdio(0);

    int N;
    cin >> N;
    if(N % 2){
        cout << N * 2;
    } else {
        cout << N;
    }
}


Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;
use std::collections::*; 
/* 
The read function reads a string according to each one. 
*/
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

//main function
fn main() {
    let s: String = read();
    let ch:Vec<char> = s.chars().collect();
    let mut v:VecDeque<char> = VecDeque::new();
    let mut flag:bool = false;
    for i in 0..ch.len(){
	v.push_back(ch[i as usize]);
    }
    let q:usize = read();
    for _i in 0..q{
	let num:i8 = read();
	if num == 1{
	    flag = if flag {false} else {true};
	}else{
	    let f:i8 = read();
	    let cc:String = read();
	    let m:Vec<char> = cc.chars().collect();
	    let c:char = m[0];
	    if f==1{
		if flag{
		    v.push_back(c);
		}else {
		    v.push_front(c);
		}
	    }else {
		if flag{
		    v.push_front(c);
		}else{
		    v.push_back(c);
		}
	    }
	}
    }
    if flag{
	for i in 0..v.len(){
	    print!("{}",v[v.len() as usize - i as usize-1]);
	}
    }else {
	for i in 0..v.len(){
	    print!("{}",v[i as usize]);
	}
    }

    println!("");
    
}


Measured memory_bytes: 6652
import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=LI()

  # a1=(x1+x2)/2,a2=(x2+x3)/2,...,an=(xn+x1)/2
  # 2a1=x1+x2,2a2=x2+x3,...,2an=xn+x1
  # x1=S-(x2+x3+...+xn)
  # x1=S-2(a2+a4+...+an-1)
  # x2=2a1-x1
  # x3=2a2-x2
  # ...

  sm=sum(l)
  ans=[]
  tmp=0
  for i,x in enumerate(l):
    if i%2==1:
      tmp+=x
  x1=sm-2*tmp
  ans.append(x1)

  for ai in l[:-1]:
    xp=2*ai-x1
    ans.append(xp)
    x1=xp

  return ' '.join([str(x) for x in ans])

# main()
print(main())


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

def solve():
    N = int(input())
    testimonies = []
    for n in range(N):
        A = int(input())
        XYs = []
        for a in range(A):
            x, y = list(map(int, input().split()))
            XYs.append((x-1, y))
        testimonies.append(XYs)

    # bit全探索する
    ans = 0
    for bit in range(2**N):
        is_continue = False
        total = 0
        # bitが1のやつが正直者と仮定する
        for i in range(N):
            if bit>>i&1:
                # iが正直者の場合
                total += 1
                for testimony in testimonies[i]:
                    x, y = testimony
                    if bit>>x&1 != y:
                        # 矛盾発生
                        is_continue = True
                        break
            if is_continue:
                break
        if is_continue:
            continue
        ans = max(ans, total)

    print(ans)



if __name__ == "__main__":
    solve()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
int main(void){
    int n, m;
    cin >> n >> m;
    rep(i, m){
        int a;
        cin >> a;
        n -= a;
    }
    int ans = max(-1, n);
    cout << ans << endl;
    return 0;
}

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

int main(){
  string A,B,C;
  cin >> A >> B >> C;
  
  bool run = true;
  string turn = "a";
  while(run){
  	if (turn == "a"){
      if (A.size() == 0){
        cout << "A" << endl;
      	run = false;
      }
      else{
        turn = A[0];
        A.erase(A.begin());
      }
    }
    else if(turn == "b"){
      if(B.size() ==0){
        cout << "B" << endl;
      	run = false;
      }
      else{
        turn = B[0];
        B.erase(B.begin());
      }  
    }
    else{
      if(C.size() == 0){
        cout << "C" << endl;
        run = false;
      }
      else{
        turn = C[0];
        C.erase(C.begin());
      }
    }
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod ((int)1e9+7)
using namespace std;
typedef long long int ll;
typedef pair<int,int> pi;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

unordered_map<int,bool,custom_hash> bomb_map[(int)3e5+5];
unordered_map<int,int,custom_hash> freq_bombs_row, freq_bombs_column;
void solve() {
  int r, c, m;
  cin >> r >> c >> m;
  int max_freq_row = 0, max_freq_column = 0;
  for(int i=0,x,y;i<m;i++) {
    cin >> x >> y;
    x--, y--;
    bomb_map[x][y] = true;
    freq_bombs_row[x]++, freq_bombs_column[y]++;
    max_freq_row = max(max_freq_row, freq_bombs_row[x]);
    max_freq_column = max(max_freq_column, freq_bombs_column[y]);
  }

  vector<int> rows_with_max_freq, columns_with_max_freq;
  for(auto it : freq_bombs_row) {
    if(it.second == max_freq_row) {
      rows_with_max_freq.push_back(it.first);
    }
  }
  for(auto it: freq_bombs_column) {
    if(it.second == max_freq_column) {
      columns_with_max_freq.push_back(it.first);
    }
  }

  int ans = max_freq_row + max_freq_column - 1;
  if((ll)rows_with_max_freq.size() * columns_with_max_freq.size() > m) {
    ans++;
  }
  else {
    for(auto row : rows_with_max_freq) {
      for(auto col : columns_with_max_freq) {
        if(!bomb_map[row].count(col)) {
          ans++;
          cout << ans;
          return;
        }
      }
    }
  }
  cout << ans;
}

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

  int T=1;
  //cin>>T;
  for(int TC=1;TC<=T;TC++) {
      //cout<<"Case #"<<TC<<": ";
      solve();
      cout<<"\n";
  }
}


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

int main() {
  int n, l;
  vector<string> v;
  cin >> n >> l;
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    v.push_back(s);
  }

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

  for (auto s : v) {
    cout << s;
  }
  cout << endl;
  return 0;
}


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

namespace abc161_c
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] nk = Console.ReadLine().Split(' ');
            long n = long.Parse(nk[0]);
            long k = long.Parse(nk[1]);
            if (n % k == 0)
            {
                Console.WriteLine(0);
            }
            else
            {
                n = n % k;
                if(Math.Abs(n-k) < n)
                {
                    n = Math.Abs(n - k);
                }
                Console.WriteLine(n);
            }
        }
    }
}


Measured memory_bytes: 27344
N=int(input())
A=[int(i) for i in input().split()]
S=[0 for i in range(N+1)]
for i in range(N):
    S[i+1]=S[i]+A[i]
B=A[::-1]
T=[0 for i in range(N+1)]
for i in range(N):
    T[i+1]=T[i]+B[i]
F=[0 for i in range(N)]
G=[0 for i in range(N)]
for i in range(N):
    LS=S[i+1]
    k=0
    if i!=0:
        k=F[i-1]
    if k!=0:
        k-=1
    tmp=LS
    for j in range(k,i+1):
        L=S[j]
        R=LS-S[j]
        if abs(R-L)<=tmp:
            F[i]=j
        else:
            break
        tmp=abs(R-L)
    if F[i]<=0:
        F[i]=0
for i in range(N):
    RS=T[i+1]
    k=0
    if i!=0:
        k=G[i-1]
    if k!=0:
        k-=1
    tmp=LS
    for j in range(k,i+1):
        L=T[j]
        R=RS-T[j]
        if abs(R-L)<=tmp:
            G[i]=j
        else:
            break
        tmp=abs(R-L)
    if G[i]<=0:
        G[i]=0
ans=S[N]
for i in range(N):
    A=[0 for i in range(4)]
    k=0
    if i!=0:
        k=F[i-1]
    A[0]=S[k]
    A[1]=S[i]-S[k]
    A[2]=T[N-i]-T[G[N-i-1]]
    A[3]=T[G[N-i-1]]
    score=max(A)-min(A)
    if ans>score:
        ans=score
print(ans)


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

ll gcd(ll a,ll b){
  while(b!=0){
    a%=b;
    swap(a,b);
  }
  return a;
}

ll kaizyou(ll N){
  ll num=1;
  for(ll i=1;i<=N;i++){
  num*=i;
  }
  return num;
}

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

int main(){
  int N,M;
  cin >> N >> M;
  if(N==M){
    cout << "Yes"  <<endl;
  }
  else{
    cout << "No" << endl;
  }
}
      
  
  
  

Measured memory_bytes: 256
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
 
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <cassert>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <time.h>
#include <stack>
#include <bitset>

#define prev asasddlsa
#define rank aljds

#define rep(i, l, r) for (int i = l; i < r; i++)
#define repb(i, r, l) for (int i = r; i >= l; i++)
 
using namespace std;
 
typedef long long ll;
typedef long double dbl;
 
template<typename T>
void print(const vector<T>& s){
    for (auto x : s)
        cout << x << ' ';
    cout << endl;
}
 
template<class T>   
void print(const T* s, int n){
    for (int i = 0; i < n; i++)
        cout << s[i] << ' ';
    cout << endl;
}
 
template<class T>
void print(vector<vector<T>> s){
    for (int i = 0; i < s.size(); i++)
        print(s[i]);
}

const int maxn = 1e3 + 7;

void solve(){
    ll n, a, b;
    cin >> n >> a >> b;
    if ((b - a) & 1)
        cout << min((a - 1 + b - 1 + 1) / 2, (n - a + n - b + 1) / 2) << endl;
    else
        cout << abs(a - b) / 2 << endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}


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

public class Kadai{
    public static void Main(){
        var n = int.Parse(Console.ReadLine());
        int[] input = new int[n];
        for (int i = 0; i < n;i++){
            input[i] = int.Parse(Console.ReadLine());
        }
        int min_v = input[0];
        int max = input[1] - input[0];
        for (int j = 1; j < n;j++){
            max = Math.Max(max, input[j]-min_v);
            min_v = Math.Min(min_v, input[j]);
        }
        Console.WriteLine(max);
    }
}


Measured memory_bytes: 22100
#include <algorithm>
#include <bits/stdc++.h>
#include <bitset>
#include <cassert>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
#define REP(i, n) for (int64_t i = 0; i < (int64_t)n; i++)
#define REP_FOR(i, a, b) for (int64_t i = (int64_t)a; i < (int64_t)b; i++)
#define REP_REV(i, a, b) for (int64_t i = (int64_t)a; i > (int64_t)b; i--)
#define FORALL(v) (v).begin(), (v).end()
#define mp(a, b) make_pair(a, b)
#define eb(x) emplace_back(x)
#define F first
#define S second
typedef long long ll;
typedef long double ld;
typedef pair<int64_t, int64_t> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int64_t> vii;
typedef vector<vii> vvii;
const ll mod = 1e9 + 7;
const int64_t infi = 1147483600;
const ll infl = 4e18 + 5;
const char EOL = '\n';
//cout << fixed << setprecision(17) << res << endl;
const ll MOD = 998244353;
 
int main() {
    ll a;
    string s;
    cin >> a >> s;
    if (a >= 3200) {
        cout << s << endl;
    } else {
        cout << "red" << endl;
    }
}


Measured memory_bytes: 256
#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 li long int

#define pb push_back
#define m <i> map<int>
#define v <i> vector<int>

#define rep(i, n) for(int i=0; i<n; i++)

int main()
{
  IOS;
  int arr[3][3];
  for (int i=0; i<3; i++)
    {
      for (int j=0; j<3; j++)
	{
	  cin >> arr[i][j];
	}
    }
  int n;
  cin >> n;
  int x[n];
  for (int i=0; i<n; i++)
    {
      cin >> x[i];
    }
  bool q[3][3];
  for (int i=0; i<3; i++)
    {
      for (int j=0; j<3; j++)
	{
	  q[i][j]=false;
	  for (int k=0; k<n; k++)
	    {
	      if (x[k]==arr[i][j])
		q[i][j]=true;
	    }
	}
    }
  string ans="No";
  for (int i=0; i<3; i++)
    {
      if (q[i][0] && q[i][1] && q[i][2])
	ans="Yes";
    }
  for (int i=0; i<3; i++)
    {
      if (q[0][i] && q[1][i] && q[2][i])
	ans="Yes";
    }
  if (q[0][0] && q[1][1] && q[2][2])
    ans="Yes";
  if (q[0][2] && q[1][1] && q[2][0])
    ans="Yes";
  cout << ans << endl;
  return 0;
}


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

using namespace std;

typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli>> mat;
typedef vector<unordered_map<lli,lli>> graph;

const lli mod = 1000000007;
lli n,a,b,c,d;
mat dp;

lli factorial(lli n){
  static lli dp[100000];
  if(dp[n]) return dp[n];
  if(n == 0) return dp[n] = 1;
  return dp[n] = (n*factorial(n-1))%mod;
}

lli pow(lli x,lli r,lli mod = 1000000007){
  lli ret = 1;
  for(;r != 0;r >>= 1){
    if(r&1 != 0) ret *= x,ret %= mod;
    x *= x,x %= mod;
  }
  return ret;
}

lli inverse(lli x,lli mod = 1000000007){
  return pow(x,mod-2,mod);
}

int main(){
  cin >> n >> a >> b >> c >> d;
  dp = mat(n+1,vll(n+1));
  dp[0][0] = 1;
  for(lli i = 1;i <= n;i++){
    for(lli j = 0;j <= n;j++){
      dp[i][j] = dp[i-1][j];
      if(i < a || i > b) continue;
      for(lli k = c;k <= d;k++){
        if(j-i*k < 0) break;
        lli x = dp[i-1][j-i*k];
        x = (x*factorial(j))%mod;
        x = (x*inverse(factorial(k)))%mod;
        x = (x*inverse(pow(factorial(i),k)))%mod;
        x = (x*inverse(factorial(j-i*k)))%mod;
        dp[i][j] += x;
      }
      dp[i][j] %= mod;
    }
  }
  cout << dp[n][n] << endl;
  return 0;

}


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

using namespace std;
#define ll               long long
#define dl               double
#define ull              unsigned long long
#define ft               first
#define sd               second
#define pi               acos(-1)
#define ct(tc)           scanf("%lld",&tc)
#define scnm(n,m)        scanf("%lld %lld",&n,&m);
#define max3(a,b,c)      max(a,max(b,c))
#define max4(a,b,c,d)    max(a,max(b,max(c,d)))
#define min3(a,b,c)      min(a,min(b,c))
#define min4(a,b,c,d)    min(a,min(b,min(c,d)))


int main()
{

    ll  n,k,f,c,a,f1,c1,f2,c2,mi;
    scanf("%lld %lld",&n,&k);
    a=n%k;
    f1=abs(k-a);
    mi=min(a,f1);
    cout<<mi<<"\n";
    return 0;
}


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








int main (){

 int x;cin>>x;
string arr[x]={};

for(int i=0;i<x;i++){
    cin>>arr[i];
}
 int ac=0,tle=0,wa=0,re=0;
for(int i=0;i<x;i++){
    if(arr[i]=="AC"){
        ac++;
    }else if(arr[i]=="WA"){
        wa++;
    }else if(arr[i]=="TLE"){
        tle++;
    }else{
        re++;
    }
}
cout<<"AC"<<" "<<"x"<<" "<<ac<<endl;
cout<<"WA"<<" "<<"x"<<" "<<wa<<endl;
cout<<"TLE"<<" "<<"x"<<" "<<tle<<endl;
cout<<"RE"<<" "<<"x"<<" "<<re<<endl;
}












Measured memory_bytes: 6752
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b;cin>>a>>b;
  if(a==0||b==0){
    cout<<"Zero"<<endl;
    return 0;
  }
  if(a<0&&b>0){
    cout<<"Zero"<<endl;
    return 0;
  }
  if(a>0){
    cout<<"Positive"<<endl;
    return 0;
  }
  if(b<0){
    if((b-a)%2!=0){
      cout<<"Positive"<<endl;
    return 0;
  }
    else{
      cout<<"Negative"<<endl;
    return 0;
  }
  }
}

Measured memory_bytes: 256
S=input()
list1=list(S)
if list1[0]==list1[1]==list1[2]==list1[3]:
  print("No")
else:
  if list1[0]==list1[1] and list1[2]==list1[3]:
    print("Yes")
  elif list1[0]==list1[2] and list1[1]==list1[3]:
    print("Yes")
  elif list1[0]==list1[3] and list1[1]==list1[2]:
    print("Yes")
  else:
    print("No")

Measured memory_bytes: 3064
n = gets.to_i
a = gets.split.map(&:to_i)
yama = Array.new(n,nil)
yama[0] = a.map.with_index{|a, i|i.even? ? a : -a}.inject(&:+)
1.upto(n-1) do |i|
  yama[i] = 2 * a[i-1]- yama[i-1]
end
puts yama.join(' ')


Measured memory_bytes: 14068
#include<stdio.h>

/* prototype declaration */
void exec();
int GCD(int a, int b);
int LCM(int a, int b);

int main(int argc, const char *argv[])
{
	exec();
	return 0;
}

void exec()
{
	int a, b, gcd, lcm;
	while(scanf("%d%d",&a,&b) != EOF){
		gcd = GCD(a, b);
		lcm = LCM(a, b);
		printf("%d %d\n", gcd, lcm);
	}
}

int GCD(int a, int b)
{
	int mod;
	do{
		mod = a%b;
		a = b;
		b = mod;
	}while(mod);
	return a;
}

int LCM(int a, int b)
{
	int gcd = GCD(a, b), x = a/gcd, y = b/gcd;
	return x*y*gcd;
}

Measured memory_bytes: 0
#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
  
    int l = 0;
    long long ans = 0;

    for (int i=0; i<n; ++i) 
    {
        int x;
        cin >> x;
        if (x < l) 
            ans += l - x;
        else 
            l = x;
    }

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

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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

int main() {
    int64_t n, m, x;
    cin >> n >> m >> x;

    vector c(n, 0L);
    vector a(n, vector(m, 0L));
    for (auto i : irange(0L, n)) {
        cin >> c[i];
        for (auto j : irange(0L, m)) {
            cin >> a[i][j];
        }
    }

    int64_t ans = 1L << 30;
    for (auto u : irange(0uL, 1uL << n)) {
        bitset<12> bs(u);

        vector b(m, 0L);
        int64_t cc = 0;
        for (auto i : irange(0L, n)) {
            if (!bs[i]) {
                continue;
            }

            cc += c[i];
            for (auto j : irange(0L, m)) {
                b[j] += a[i][j];
            }
        }

        if (all_of(b.begin(), b.end(), [&](int64_t bb) { return bb >= x; })) {
            ans = min(ans, cc);
        }
    }

    if (ans == 1L << 30) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
}

Measured memory_bytes: 3632
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
  input = input.split("\n");
  
  //スペース区切り　input[0] が tmp[0], tmp[1],...
	tmp = input[0].split(" ");
  
  //この時点では全部文字列（数値に変換しないといけない）

	//文字列から10進数に変換するときはparseIntを使います
	var a = parseInt(tmp[0], 10);
    var x = Math.floor(a/100);
    var y = a- (100*x);
    if(5*x >= y){
      console.log('%d', 1);
    }else{
      console.log('%d', 0);
    }
}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
fun main(args: Array<String>) {
    abc051c()
}

private const val U = "U"
private const val D = "D"
private const val R = "R"
private const val L = "L"

fun abc051c() {
    val (sx, sy, tx, ty) = readLine()!!.split(" ").map { it.toInt() }

    val xDiff = tx - sx
    val yDiff = ty - sy


    val answer =
        U.repeat(yDiff) + R.repeat(xDiff) + D.repeat(yDiff) + L.repeat(xDiff + 1) + U.repeat(yDiff + 1) +
                R.repeat(xDiff + 1) + D + R + D.repeat(yDiff + 1) + L.repeat(xDiff + 1) + U

    println(answer)
}


Measured memory_bytes: 37440
import java.util.Arrays;
import java.util.Scanner;


public class Main {

	private static int[][] cache;
	private static char[] x;
	private static char[] y;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in); 

		int set = sc.nextInt();

		for (int k = 0; k < set; k++) {
			x = sc.next().toCharArray();
			y = sc.next().toCharArray();
			int m = x.length;
			int n = y.length;
			
			// 再帰的トップダウン型、履歴管理
			cache = new int[m + 1][n + 1];
			for (int i = 1; i <= m; i++) {
				Arrays.fill(cache[i], Integer.MIN_VALUE);
				cache[i][0] = 0;
			}
			Arrays.fill(cache[0], 0);
			
			System.out.println(lcs(m, n));
		}
		
         sc.close();
	}

	private static int lcs(int m, int n) {
		if (cache[m][n] != Integer.MIN_VALUE) {
			return cache[m][n];
		}
		
		int result;
		if (x[m - 1] == y[n - 1]) {
			result = lcs(m - 1, n - 1) + 1;
		} else {
			result = Math.max(lcs(m - 1, n), lcs(m, n - 1));
		}
		
		cache[m][n] = result;
		return result;
	}
}

Measured memory_bytes: 73656
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(vec) vec.begin(), vec.end()
#define rALL(vec) vec.rbegin(), vec.rend()
using namespace std;
using ll = long long;
// ------------------------------

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    ll money = 1000;
    ll stock = 0;
    ll i = 0;
    while (i + 1 < N) {
        if (A[i] == A[i + 1]) {
            while (i + 1 < N && A[i] == A[i + 1]) i += 1;
        } else if (A[i] < A[i + 1]) {
            stock += money / A[i];
            money = money % A[i];
            while (i + 1 < N && A[i] < A[i + 1]) i += 1;
        } else {
            money += stock * A[i];
            stock = 0;
            while (i + 1 < N && A[i] > A[i + 1]) i += 1;
        }
    }
    money += A[N - 1]*stock;
    cout << money << endl;
    return 0;
}


Measured memory_bytes: 3632
(let ((x (read)))
    (if (and (<= 400 x) (> 600 x ))
        (princ "8")
    )
    (if (and (<= 600 x) (> 800 x ))
        (princ "7")
    )
    (if (and (<= 800 x) (> 1000 x ))
        (princ "6")
    )
    (if (and (<= 1000 x) (> 1200 x ))
        (princ "5")
    )
    (if (and (<= 1200 x) (> 1400 x ))
        (princ "4")
    )
    (if (and (<= 1400 x) (> 1600 x ))
        (princ "3")
    )
    (if (and (<= 1600 x) (> 1800 x ))
        (princ "2")
    )
    (if (and (<= 1800 x) (> 2000 x ))
        (princ "1")
    )
)

Measured memory_bytes: 24228
a,b=map(int,input().split())
ans = 0
flag = True
if int(b/10)==0:
    ans+=a*10+b
elif int(b/10)>=1 and int(b/10)<=9:
    ans+=a*100+b
else:
    ans+=a*1000+b
for i in range(ans):
    tmp=i*i
    if tmp==ans:
        print("Yes")
        flag=False
        break
if flag:
    print("No")


Measured memory_bytes: 9104
import sys
input = sys.stdin.readline
#input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')
#import numpy as np

from collections import deque

def main():
	h,w=MI()
	G=["#"]*(w+2)
	for i in range(h):
		G+=["#"]+list(input().rstrip())+["#"]
	G+=["#"]*(w+2)
	ans=0
	#print(G)
	for i in range((h+2)*(w+2)):
		if G[i]==".":
			ans+=1

	Q=deque()
	Q.append((w+3,1))
	G[w+3]="#"
	f=0
	while Q:
		#print(Q)
		x,d=Q.popleft()
		if x==(w+2)*(h+2)-(w+2)-2:
			f=1
			break
		for dx in [-1,1,-w-2,w+2]:
			if G[x+dx]==".":
				Q.append((x+dx,d+1))
				G[x+dx]="#"

	if f==1:
		print(ans-d)
	else:
		print(-1)


























































if __name__ == "__main__":
	main()

Measured memory_bytes: 39408
//(・ω・)
#include <stdio.h>
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, atoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip> //setprecision
#include <limits>
#include <sstream> //istringstream
#include <stdlib.h>
#include <list>
#include <iterator>//std::advance()
using namespace std;
long long f(long long n){
    long long ans=0;
    if(n>=10){
        n/=10;
        ans+=n;
        while(n>=5){
            n/=5;
            ans+=n;
        }
    }
    return ans;
}
int main(){
   long long n;
   cin >> n;
   if(n%2==1) cout << 0 << endl;
   else{
       cout << f(n) << endl;
   }
}

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

int main()
{
  string w;
  cin >> w;
  vector<int> n(26, 0);
  for (int i = 0; i < w.size(); i++)
  {
    n.at(w.at(i) - 'a')++;
  }
  for (int i = 0; i < 26; i++)
  {
    if (n.at(i) % 2 == 1)
    {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

func COM(n, k int64) int64 {
	r := int64(1)
	for i := int64(0); i < k; i++ {
		r = ModMul(r, n-i)
		r = ModDiv(r, i+1)
	}

	return r
}

const (
	MOD = 1000000000 + 7
)

func ModAdd(a, b int64) int64 {
	return (a + b) % MOD
}

func ModMul(a, b int64) int64 {
	return a * b % MOD
}

func ModSub(a, b int64) int64 {
	r := (a%MOD - b%MOD) % MOD
	if r < 0 {
		r += MOD
	}
	return r
}

func ModDiv(a, b int64) int64 {
	return a % MOD * ModInv(b) % MOD
}

func ModPow(a, n int64) int64 {
	var r int64 = 1
	for n > 0 {
		if n&1 == 1 {
			r = r * a % MOD
		}
		a = a * a % MOD
		n >>= 1
	}
	return r
}

func ModInv(a int64) int64 {
	var b, u, v int64 = MOD, 1, 0
	for b > 0 {
		t := a / b
		a -= t * b
		a, b = b, a
		u -= t * v
		u, v = v, u
	}
	u %= MOD
	if u < 0 {
		u += MOD
	}
	return u
}

type Q struct {
	value int
	index int
	A, B  int
}

type QS []*Q

func (p QS) Len() int           { return len(p) }
func (p QS) Less(i, j int) bool { return p[i].value > p[j].value }
func (pq QS) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *QS) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Q)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *QS) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil  // avoid memory leak
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

func FactoredPrimeNumber(num int) map[int]int {
	m := map[int]int{}
	return factor(m, num, 2)
}

func factor(result map[int]int, num, pnum int) map[int]int {
	if pnum*pnum > num {
		if num != 1 {
			result[num] += 1
		}
		return result
	}

	if num%pnum == 0 {
		num /= pnum
		result[pnum]++
	} else {
		pnum++
	}
	return factor(result, num, pnum)
}

func GCD(a, b int64) int64 {
	if b == 0 {
		return a
	}
	return GCD(b, a%b)
}

func LCM(a, b int64) int64 {
	return a * b / GCD(a, b)
}

func main() {
	var N, K int
	fmt.Scanf("%d %d\n", &N, &K)
	V := make([]int, N)
	for i := 0; i < N; i++ {
		var v int
		fmt.Scan(&v)
		V[i] = v
	}
	O := K
	if O > N {
		O = N
	}
	max := 0
	for l := 0; l <= O; l++ {
		for r := 0; r+l <= O; r++ {
			v := []int{}
			sum := 0
			for i := 0; i < l; i++ {
				v = append(v, V[i])
				sum += V[i]
			}
			for i := 0; i < r; i++ {
				v = append(v, V[N-i-1])
				sum += V[N-i-1]
			}

			sort.Ints(v)
			l := K - r - l
			if l > len(v) {
				l = len(v)
			}
			for i := 0; i < l; i++ {
				if v[i] < 0 {
					sum = sum - v[i]
				}
			}
			if sum > max {
				max = sum
			}
		}

	}
	fmt.Println(max)
}

func Reverse(runes []rune) []rune {
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return runes
}


Measured memory_bytes: 2896
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int i,n,c=0;
    string s;
    cin>>s;
    n=s.size();
    for(i=0;i<n/2;i++)
    {
        if(s[i]!=s[n-1-i])c++;
    }
    cout<<c<<endl;
    return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    vn = vk = vn_k = 1
    for i in range(1, n+1):
        vn = vn * i % modp
        if i == k:
            vk = vn
        if i == n-k:
            vn_k = vn
    return vn * get_inv(vk, modp) * get_inv(vn_k, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

def main():
    NS = input()
    K = ii()
    dp = {
        'now_same': [0]*(K+1),
        'now_under': [0]*(K+1),
        'next_same': [0]*(K+1),
        'next_under': [0]*(K+1),
    }
    dp['now_same'][0] = 1
    for s in NS:
        for k in range(K+1):
            for d in map(str, range(10)):
                nk = k if d=='0' else k+1
                if nk > K:
                    continue
                dp['next_under'][nk] += dp['now_under'][k]
                if d == s:
                    dp['next_same'][nk] += dp['now_same'][k]
                elif d < s:
                    dp['next_under'][nk] += dp['now_same'][k]
        dp['now_same'] = dp['next_same']
        dp['now_under'] = dp['next_under']
        dp['next_same'] = [0]*(K+1)
        dp['next_under'] = [0]*(K+1)
    print(dp['now_same'][K] + dp['now_under'][K])

main()


Measured memory_bytes: 5296
#include <stdio.h>
#define N 1000

int main(void)
{
	int i , n;
	scanf("%d",&n);
	double a[n];
	
	for(i = 0; i < n; i++)
	{
		scanf("%lf",&a[i]);
	}
	double b[n+1];
	for(i = 0; i <= n; i++)
	{
		scanf("%lf",&b[i]);
	}
	double c[n+1][n+1];
	double d[n+1];
	c[0][0]=b[0];
	d[0]=a[0]+b[0];
	
	for(i = 1; i <= n; i++)
	{
		c[i][i] = b[i];
		c[i-1][i] = a[i-1]+(b[i-1]+b[i])*2;
		d[i] = d[i-1]+a[i]+b[i];
	}
	int j , k;
	double s , t;
	for(i = 1;i < n; i++)
	{
		for(j = 0; j < n-i; j++)
		{
			s = c[j][j] + c[j+1][i+j+1];
			for(k = j; k <i+j; k++)
			{
				t = c[j][k+1]+c[k+2][i+j+1];
				if(s>t) s = t;
			}
			c[j][i+j+1] = s + d[i+j] - d[j-1] + b[i+j+1];
		}
	}
	printf("%lf\n",c[0][n]);
	return 0;
}


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

using namespace std;

vector<int> ps;

int intpow(int b, int p)
{
    if (p == 1)
        return b;

    int res = intpow(b, p / 2);
    res *= res;

    return p % 2 ? res * b : res;
}

void precomp()
{
    for (int b = 2; b <= 1000; ++b)
    {
        int p = 2, x;

        while ((x = intpow(b, p)) <= 1000)
        {
            ps.push_back(x);
            ++p;
        }
    }

    ps.push_back(1);
    sort(ps.begin(), ps.end());
}

int main()
{
    precomp();

    int X;
    cin >> X;

    auto it = lower_bound(ps.begin(), ps.end(), X);

    if (*it > X)
        --it;

    cout << *it << '\n';

    return 0;
}


Measured memory_bytes: 256
# aoj 1313
import sys
input = sys.stdin.readline


# the width of the polygon sliced at x
def width(X, Y, x):
    n = len(X)
    lb, ub = float('inf'), -float('inf')
    for i in range(n):
        x1, y1, x2, y2 = X[i], Y[i], X[(i+1) % n], Y[(i+1) % n]
        if (x1-x)*(x2-x) <= 0 and x1 != x2:
            y = y1 + (y2-y1) * (x-x1) / (x2-x1)
            lb = min(lb, y)
            ub = max(ub, y)
    return max(0, ub-lb)


while True:
    m, n = map(int, input().split())
    if m == n == 0:
        break
    X1 = [0] * m
    Y1 = [0] * m
    X2 = [0] * n
    Z2 = [0] * n
    for i in range(m):
        X1[i], Y1[i] = map(int, input().split())
    for i in range(n):
        X2[i], Z2[i] = map(int, input().split())
    min1, max1 = min(X1), max(X1)
    min2, max2 = min(X2), max(X2)
    X = X1 + X2
    X.sort()
    ans = 0
    for i in range(len(X)-1):
        a, b = X[i], X[i+1]
        c = (a+b) / 2
        if min1 <= c <= max1 and min2 <= c <= max2:
            fa = width(X1, Y1, a) * width(X2, Z2, a)
            fb = width(X1, Y1, b) * width(X2, Z2, b)
            fc = width(X1, Y1, c) * width(X2, Z2, c)
            ans += (b-a) / 6 * (fa+4*fc+fb)
    print(ans)



Measured memory_bytes: 5652
#include <iostream>
#include <string>
#include <sstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <list>
#include <stack>
#include <vector>

using namespace std;
	stack<int> st;

	vector<string> split(const string &s, char delim) {
		vector<string> elems;
		stringstream ss(s);
		string item;
		while (getline(ss, item, delim)) {
			if (!item.empty()) {
				elems.push_back(item);
			}
		}
		return elems;
	}



	int main(){
	string line;
	getline(cin, line);
	for(string s : split(line, ' ')){
		if (s == "+" || s == "-" || s == "*"){
			int a = st.top();
			st.pop();
			int b = st.top();
			st.pop();
			if (s == "+"){
				st.push(a + b);
			}
			else if (s == "-"){
				st.push(b - a);
			}
			else{
				st.push(a * b);
			}
		}
		else{
			st.push(stoi(s));
		}
	}
	cout << st.top() << endl;
	return 0;
}

Measured memory_bytes: 1228
#include <bits/stdc++.h>
#define fi first
#define se second
#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)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define pb push_back
#define sz(x) (int)(x).size()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;


int main() {
  int n;
  cin >> n;
  vi v(n);
  int sum = 0;
  rep(i, n){
    cin >> v[i];
    sum += v[i];
  }
  sort(rng(v));
  if (sum-v[n-1] > v[n-1]){
    cout << "Yes" << endl;
    return 0;
  }
  cout << "No" << endl;
  return 0;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 2*asin(1)
#define int long long
#define mod 1000000007
#define all(a) begin(a),end(a)
#define fore(i, j, n) for(long long i = j; i < n;i++)
using namespace std;

int32_t main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n; cin >> n;
    int a,b;
    for(int i = 1; i *i <= n;i++){
        if(n%i == 0){
            a = i; b = n/i;
        }
    }
    cout << a + b - 2;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

  public static void main (String[] args) {

    Scanner sc = new Scanner(System.in);
    
    String N = sc.next();

    sc.close();
    
    String[] arr = N.split("");

    int n = Integer.valueOf(N);

    int sn = 0;

    for (int i = 0; i < arr.length; i++) {
      sn += Integer.valueOf(arr[i]);
    }

    if (n % sn == 0) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }

  }

}

Measured memory_bytes: 21716
#include<iostream>
#include<algorithm>
#define r(i,n) for(int i=0;i<n;i++)
#define z 100
using namespace std;
int n,a,b,q[z*z],l[z],la,be,an,ct[z],c[z][z];bool v[z],s[z];void d(int x,int len){if(len>be){la=x;be=len;}v[x]=1,s[x]=1;for(int i=0;i<ct[x];i++)if(!v[c[x][i]]){d(c[x][i],len+1);v[c[x][i]]=0;}}int main(){while(1){cin>>n;if(!n)break;r(i,z)ct[i]=0;r(i,n){cin>>a>>b;a--,b--;c[a][ct[a]]=b,c[b][ct[b]]=a;ct[a]++,ct[b]++;}r(i,z)s[i]=0;an=0;for(int i=0;i<z;i++)if(!s[i]){r(i,z)v[i]=0;be=0;d(i,1);r(i,z)v[i]=0;be=0;d(la,1);an=max(an,be);}cout<<an<<endl;}return 0;}

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

const int MOD = 1000000007;

ll powmod(ll a, ll b, int MOD) {
    if (b == 0) return 1;
    if (b == 1) return a;
    if (b == 2) return a * a % MOD;
    return powmod(powmod(a, 2, MOD), b >> 1, MOD) * powmod(a, b & 1, MOD) % MOD;
}
void solve() {
    string Zaki, O;
    int N;
    cin >> Zaki >> O >> N;
    ll ans = 1;
    if (N < 400000) {
        string S;
        rep(i, N) S += '0';
        S += Zaki;
        rep(i, N) S += '0';
        S += O;
        for (int i = 0;i < N;++ i) S[i] = S[i + N + Zaki.size()] = S[S.size() - i - 1];
        for (int i = N + Zaki.size();i < Zaki.size() + 2 * N;++ i) {
            if (S[i] == '0') S[i] = S[i - Zaki.size() - N] = S[S.size() - 1 - i];
            else if (S[i] != S[S.size() - 1 - i]) ans = 0;
        }
        //cout << S << endl;
        int count = 0;
        rep(i, S.size()) if (S[i] == '0') ++ count;
        count >>= 1;
        ans *= powmod(26, count, MOD);
    } else {
        string check = Zaki;
        rep(i, O.size()) check += O[O.size() - 1 - i];
        for (int i = 0;i < check.size() >> 1;++ i) {
            if (check[i] != check[check.size() - 1 - i]) ans = 0;
        }
        int count = N - O.size();
        ans *= powmod(26, count, MOD);
    }
    cout << ans << endl;
}

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



    solve();

    return 0;
}


Measured memory_bytes: 3884