akhauriyash/Code-Regression huggingface dataset:
//ABC146B.cpp
#import <iostream>
#import <string>
#import <stdio.h>
using namespace std;


int cha2num(char input){
	switch(input){
		case 'A':
			return 1;
			break;
		case 'B':
			return 2;
			break;
		case 'C':
			return 3;
			break;
		case 'D':
			return 4;
			break;
		case 'E':
			return 5;
			break;
		case 'F':
			return 6;
			break;
		case 'G':
			return 7;
			break;
		case 'H':
			return 8;
			break;
		case 'I':
			return 9;
			break;
		case 'J':
			return 10;
			break;
		case 'K':
			return 11;
			break;
		case 'L':
			return 12;
			break;
		case 'M':
			return 13;
			break;
		case 'N':
			return 14;
			break;
		case 'O':
			return 15;
			break;
		case 'P':
			return 16;
			break;
		case 'Q':
			return 17;
			break;
		case 'R':
			return 18;
			break;
		case 'S':
			return 19;
			break;
		case 'T':
			return 20;
			break;
		case 'U':
			return 21;
			break;
		case 'V':
			return 22;
			break;
		case 'W':
			return 23;
			break;
		case 'X':
			return 24;
			break;
		case 'Y':
			return 25;
			break;
		case 'Z':
			return 26;
			break;
		default:
			return 0;
			break;
	}
}
char num2cha(int input){
	switch(input){
		case 1:
			return 'A';
			break;
		case 2:
			return 'B';
			break;
		case 3:
			return 'C';
			break;
		case 4:
			return 'D';
			break;
		case 5:
			return 'E';
			break;
		case 6:
			return 'F';
			break;
		case 7:
			return 'G';
			break;
		case 8:
			return 'H';
			break;
		case 9:
			return 'I';
			break;
		case 10:
			return 'J';
			break;
		case 11:
			return 'K';
			break;
		case 12:
			return 'L';
			break;
		case 13:
			return 'M';
			break;
		case 14:
			return 'N';
			break;
		case 15:
			return 'O';
			break;
		case 16:
			return 'P';
			break;
		case 17:
			return 'Q';
			break;
		case 18:
			return 'R';
			break;
		case 19:
			return 'S';
			break;
		case 20:
			return 'T';
			break;
		case 21:
			return 'U';
			break;
		case 22:
			return 'V';
			break;
		case 23:
			return 'W';
			break;
		case 24:
			return 'X';
			break;
		case 25:
			return 'Y';
			break;
		case 26:
			return 'Z';
			break;
		default:
			return 'a';
			break;
	}
}
int sum26(int a,int b){
	int sum = a+b;
	if(sum<=26)return sum;
	else return sum-26;
}

int main(){
	int N;
	string s;
	cin>>N>>s;
	int len=s.length();
	char char_temp;
	int num;
	for(int i=0;i<len;i++){
		char_temp = s[i];
		num = cha2num(char_temp);
		num = sum26(num,N);
		s[i] = num2cha(num);
	}
	cout<<s<<endl;
	return 0;
}

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

int main(){
    priority_queue<double> pq;
    int n;
    cin >> n;
    rep(i,n){
        double v;
        cin >> v;
        v *= -1;
        pq.push(v);
    }
    while( pq.size() > 1 ) {
        double a = pq.top(); pq.pop();
        double b = pq.top(); pq.pop();
        double c = (a + b) / 2;
        pq.push(c);
    }
    double ans = (-1) * pq.top();
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define FORq(i, m, n) for(int i = m;i <= n;i++)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef long long ll;
//////////////////////////////////////////////////////

int main(){
	set<int>S;
	S.insert(1);
	static int box[100003];
	int N,M;
	SCD2(N,M);
	
	FORq(i,1,N){
		box[i] = 1;
	}
	
	REP(i,M){
		int x,y;
		SCD2(x,y);
		
		if (S.count(x) != 0){
			S.insert(y);
		}
		
		if (box[x]==1){
			S.erase(x);
		}
		
		box[x] = box[x] - 1;
		box[y] = box[y] + 1;
		
	}
	PRINTD(S.size());
	
	return 0;
}


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

int main()
{
  int n, k, s;
  cin >> n >> k >> s;
  int m = s == 1000000000 ? 1 : s + 1;
  for (int i = 0; i < n; i++) {
    cout << ' ' << (i < k ? s : m);
  }
  cout << endl;
}


Measured memory_bytes: 1280
import Control.Applicative ((<$>))
import Control.Monad (replicateM)
import Data.ByteString.Char8 (ByteString)
import qualified Data.ByteString.Char8 as B

main :: IO ()
main = do
  solve <$> replicateM 4 (getl $ readi B.readInt) >>= print

solve :: [Int] -> Int
solve [a, b, c, x] = sum $ [1 | i <- [0..a], j <- [0..b], k <- [0..c], i * 500 + j * 100 + k * 50 == x]

getl :: (ByteString -> a) -> IO a
getl f = f <$> B.getLine

readi :: Integral a =>  (ByteString -> Maybe (a, ByteString)) -> ByteString -> a
readi f s = let Just (n, _) = f s in n


Measured memory_bytes: 380
import sys


def main():
    N = int(input())

    for i in range(1, 3501):
        for j in range(1, 3501):
            if(4*i*j-N*(i+j) > 0):
                if((N*i*j)%(4*i*j-N*(i+j)) == 0):
                    print(i, j, int((N*i*j/(4*i*j-N*(i+j)))))
                    sys.exit()
                    
main()

Measured memory_bytes: 3060
<?php
/*
    Problem URL : http://abc048.contest.atcoder.jp/tasks/abc048_a

    Score  :
    Result :
    Time   : ms
    Memory : KB
 */

fscanf(STDIN, "%s %s %s", $a, $x, $c);

echo $a[0] . $x[0] . $c[0] . PHP_EOL;

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

int main(){
    ll N, K; cin >> N >> K;
    vector<ll> a(N);
    for(int i=0; i<N; i++) cin >> a[i];

    ll ans = 0LL;
    vector<ll> bitcnt(45, 0); // 右からi番目のビットが立ってるaは何個あるか
    for(int i=0; i<40; i++){
        for(int j=0; j<N; j++) if(a[j]&(1LL<<i)) bitcnt[i]++;
    }

    for(int m=0; m<40; m++){
        if((K&1LL<<m) == 0) continue;

        ll tmp = 0LL;
        for(int i=39; i>m; i--){
            if((K&1LL<<i) == 0) tmp += bitcnt[i]*(1LL<<i);
            else tmp += (N-bitcnt[i])*(1LL<<i);
        }
        tmp += bitcnt[m]*(1LL<<m);
        for(int i=m-1; i>=0; i--){
            tmp += max(bitcnt[i], N-bitcnt[i])*(1LL<<i);
        }
        ans = max(ans, tmp);
    }

    ll tmp = 0;
    for(int i=39; i>=0; i--){
        if((K&1LL<<i) == 0) tmp += bitcnt[i]*(1LL<<i);
        else tmp += (N-bitcnt[i])*(1LL<<i);
    }
    ans = max(ans, tmp);

    cout << ans << endl;
}

Measured memory_bytes: 1024
import java.util.Scanner;

class Main {

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

        while (n > 0) {
            int m = -1;
            int s = -1;
            for (int i = 0; i < n; i++) {
                int p = scan.nextInt();
                int d1 = scan.nextInt();
                int d2 = scan.nextInt();
                if (d1 + d2 > m) {
                    m = d1 + d2;
                    s = p;
                }
            }
            System.out.println(s + " " + m);
            n = scan.nextInt();
        }
    }
}



Measured memory_bytes: 161700
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define int long long
int32_t main(){

	int n;
	cin>>n;
	vector<int> a;
	a.resize(n);
	int sum=0;
	
	unordered_map<int,int> freq;
	
	for(int i=0;i<n;++i){
		
		cin>>a[i];
		sum+=a[i];
		freq[a[i]]++;
	}

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

	int q;
	cin>>q;
	vector<pair<int,int>> b;
	for(int i=0;i<q;++i){

		int x;cin>>x;
		int y;cin>>y;
		b.push_back(make_pair(x,y));
	}

	for(int i=0;i<q;++i){

		int f = freq[b[i].first];
		sum+=(b[i].second - b[i].first)*f;
		freq[b[i].second]+=f;
		freq[b[i].first]=0;
		cout<<sum<<'\n';
	}

	return 0;
}

Measured memory_bytes: 9336
#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部変数
static FILE *szpFpI;											// 入力

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// １行出力
int
fOutLine(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// 実行メイン
int
fMain(
)
{
	char lc1Buf[1024];

	// 入力値 - 取得
	long long llN, llK;
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%lld%lld", &llN, &llK);

	// 最小値 - 取得
	llN %= llK;
	long long llMin = llN;
	long long llVal = llK - llN;
	if (llMin > llVal) {
		llMin = llVal;
	}

	// 出力
	sprintf(lc1Buf, "%lld\n", llMin);
	fOutLine(lc1Buf);

	return 0;
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	liRet = fMain();

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}



Measured memory_bytes: 128
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define SORT(v) sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define REV(v) reverse(v.begin(), v.end())
#define ITER(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define LB(v, x) (lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (upper_bound(v.begin(), v.end(), x) - v.begin())
#define SZ(v) (int)v.size()
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

    int N;
    cin >> N;
    map<P, int> mp;
    vector<int> x(N), y(N);
    REP(i, N) cin >> x[i] >> y[i];
    REP(i, N - 1) {
        FOR(j, i + 1, N) {
            mp[P(x[i] - x[j], y[i] - y[j])]++;
            mp[P(x[j] - x[i], y[j] - y[i])]++;
        }
    }
    int mx = 0;
    for (auto &t : mp) { mx = max(mx, t.second); }
    cout << N - mx << endl;

    return 0;
}

Measured memory_bytes: 384
X = input()

count = 0
count_s = 0
i = 0
while i < len(X):
    if i < len(X) - 1 and X[i] == 'S' and X[i+1] == 'T':
        count += 1
        i += 1
    elif X[i] == 'S':
        count_s += 1
    elif X[i] == 'T' and count_s > 0:
        count_s -= 1
        count += 1
    else:
        count_s = 0
    i += 1

count = min(count, 10 ** 10000)
print(len(X) - count * 2)


Measured memory_bytes: 3500
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int main() {
	ull k;
	cin >> k;
	ull c = k / 100;
	ull l = k - c * 100;
	ull c1 = l / c;
	ull sum = 100;
	c = 0;
	while (sum < k) {
		sum += sum / 100;
		c++;
	}
	cout << c << endl;
	return 0;
}

Measured memory_bytes: 3648
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <numeric>
#define fi first
#define se second
using namespace std;
bool value(int y,int x,int R,int C){return 0<=y&&y<R&&0<=x&&x<C;}
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long > vll;
typedef vector< vi > vvi;
double pie=acos(-1);
int INF=10000009;
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1,0,1,0 };
double det(double x1,double y1,double x2,double y2){
	return x1*y2-x2*y1;
}
int main() {
	long double s1,t1,s2,t2,s3,t3,sp,tp;
	while(true){ 
		cin>>s1>>t1>>s2>>t2>>s3>>t3>>sp>>tp;
		if (cin.eof())break;
		double X=det(s1-sp,t1-tp,s2-sp,t2-tp);
		double Y=det(s2-sp,t2-tp,s3-sp,t3-tp);
		double Z=det(s3-sp,t3-tp,s1-sp,t1-tp);		
		if((X>0&&Y>0&&Z>0)||(X<0&&Y<0&&Z<0)){
			cout<<"YES"<<endl;
		}
		else{
			cout<<"NO"<<endl;
		}
	}	
}

Measured memory_bytes: 3220
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mx 1
 
int main()
{	
	ios_base::sync_with_stdio(0);
	#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	#endif
    string str;
    int len;
    cin>>len;
    cin>>str;
    ll totalR=0, totalG=0, totalB=0;
    for(int i=len-1; i>=0; i--){
    	if(str[i]=='R') totalR++;
    	else if(str[i]=='G') totalG++;
    	else totalB++;
    }
    ll currentR=0, currentG = 0, currentB = 0;
    ll ans = 0;
    for(int i=len-1; i>=0; i--){
    	ll res;
    	if(str[i]=='R'){
    		res = currentB*(totalG - currentG);
    		res += currentG*(totalB - currentB);
    		currentR++;
    	}
    	else if(str[i]=='G') {
    		res = currentB*(totalR - currentR);
    		res += currentR*(totalB - currentB);
    		currentG++;
    	}
    	else{
    		res = currentG*(totalR  - currentR);
    		res += currentR*(totalG - currentG);
    		currentB++;
    	}
    	for(int j = i-1, k = i+1; j>=0 && k<len; j--, k++){
    		if(str[k]!=str[i] && str[j]!=str[i] && str[j]!=str[k]){
    			res--;
    		}
    	}
    	ans+=res;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3596
#include <stdio.h>

int main() {
  long long int N;
  long long int A[100];
  int i;
  scanf("%lld", &N);
  for (i = 0; i < N; i++) {
    scanf("%lld", &A[i]);
  }
  long long int min = A[0];
  long long int max = A[0];

  for (i = 0; i < N; i++) {
    if (min > A[i]) {
      min = A[i];
    }
     if (max < A[i]) {
      max = A[i];
    }
  }

  printf("%lld\n", max - min);
  return 0;
}


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

const int MAX = 500; 

bool is_operand(string s)
{
  return '0' <= s[0] && s[0] <= '9';
}

int main()
{
  vector<string> ss;
  while (!cin.eof()) {
    string str; cin >> str;
    ss.push_back(str);
  }
  ss.pop_back();

  stack<int> stk;
  for (int i = 0; i < ss.size(); i++) {
    string s = ss[i];
    if (is_operand(s)) {
      stk.push(atoi(s.c_str()));
    } else {
      int a, b;
      b = stk.top(); stk.pop();
      a = stk.top(); stk.pop();
      switch (s[0]) {
      case '+': stk.push(a+b); break;
      case '-': stk.push(a-b); break;
      case '*': stk.push(a*b); break;
      default:
        cerr << "error" << endl;
        return EXIT_FAILURE;
      }
    }
  }
  cout << stk.top() << endl;

  return EXIT_SUCCESS;
}




Measured memory_bytes: 3176
import java.util.Scanner;

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

		int n = sc.nextInt();
		int tmp;

		for (int i = 1; i <= n; i++) {
			if (i % 3 == 0 || i % 10 == 3) {
				System.out.print(" " + i);
			} else if (i >= 30) {
				tmp = i;
				while (tmp >= 30) {
					tmp /= 10;

					if (tmp == 3 || tmp % 10 == 3) {
						System.out.print(" " + i);
						break;
					}
				}

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

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

//#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#define LL long long

int main() {
	int n;
	int c1, c2, c3, c4;
	c1 = c2 = c3 = c4 = 0;
	cin >> n;
	string s;
	for(int i=0;i<n;i++) {
		cin >> s;
		if(s == "AC") c1++;
		if(s == "WA") c2++;
		if(s == "TLE") c3++;
		if(s == "RE") c4++;
	}
	cout << "AC x " << c1 << endl; 
	cout << "WA x " << c2 << endl; 
	cout << "TLE x " << c3 << endl; 
	cout << "RE x " << c4 << endl; 

	return 0;
}


Measured memory_bytes: 3628
def readinput():
    a,b,x=list(map(int,input().split()))
    return a,b,x
 
def main(a,b,x):
    ans = b//x - (a-1)//x
    return ans
 
if __name__=='__main__':
    a,b,x=readinput()
    ans=main(a,b,x)
    print(ans)

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

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

// Greatest Common Divisor
ll gcd(ll a, ll b){ return b ? gcd(b,a%b) : a; }
// Least Common Multiple
ll lcm(ll a, ll b){ return a/gcd(a,b)*b; }



void solve(long long n, std::vector<long long> p){
    int cnt = 0;
    for(int i = 1; i < (int)n-1; ++i){
        if((p[i] >= p[i-1] && p[i] <= p[i+1]) || (p[i] <= p[i-1] && p[i] >= p[i+1])) cnt++;
    }
    cout << cnt << endl;
}


int main(){
    long long n;
    scanf("%lld",&n);
    std::vector<long long> p(n);
    for(int i = 0 ; i < n ; i++){
        scanf("%lld",&p[i]);
    }
    solve(n, std::move(p));
    return 0;
}


Measured memory_bytes: 256
#include <cassert>

#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
//#include <boost/foreach.hpp>
//#include <boost/range/algorithm.hpp>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define ll long long
#define Sort(v) sort(all(v))
#define INF 1e9
#define LINF 1e18
#define END return 0
#define pb push_back
#define se second
#define fi first
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define MP make_pair
#define MOD 1000000007LL
#define int long long
using namespace std;
int day[12]={31,28,31,30,31,30,31,31,30,31,30,31};
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
struct edge{int to,cost;};
typedef pair<int,int> P;

bool isupper(char c){if('A'<=c&&c<='Z')return 1;return 0;}
bool islower(char c){if('a'<=c&&c<='z')return 1;return 0;}
bool isPrime(int x){if(x==1)return 0;if(x==2)return 1;if(x%2==0)return 0;for(int i=3;i*i<=x;i++)if(x%i==0)return 0;return 1;}
bool iskaibun(string s){for(int i=0;i<s.size()/2;i++)if(s[i]!=s[s.size()-i-1])return 0;return 1;}
bool isnumber(char c){return ('0'<=c&&c<='9');}
bool isalpha(char c){return (isupper(c)&&islower(c));}

signed main (){
    double a,b;
    cin>>a>>b;
    cout<<fixed<<setprecision(10);
    cout<<a/b<<endl;

}
/*
1 2 0 6 7
*/


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define Endl '\n'
typedef long long int lli;
/*
created on: 19/4/2020
*/
void solve();
int main(int argc, char const *argv[]){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  solve();
}
void solve(){
  int N;
  cin>>N;
  map<int, int> mp;
  for(int i=1;i<N;i++){
    int t;
    cin>>t;
    t--;
    mp[t]++;
  }
  for(int i=0;i<N;i++)
    cout<<mp[i]<<Endl;
}


Measured memory_bytes: 13024
<?php
fscanf(STDIN, "%d%d%d", $N, $M, $R);
$rArray = array_map("intval", explode(" ", trim(fgets(STDIN))));

for($i = 1; $i <= $N; $i++){
  for($j = 1; $j <= $N; $j++){
    $d[$i][$j] = 10**10;
  }  
}

for($i = 0; $i < $M; $i++){
  fscanf(STDIN, "%d%d%d", $a, $b, $c);
  $d[$a][$b] = $c;
  $d[$b][$a] = $c;
}

for($k = 1; $k <= $N; $k++){
  for($i = 1; $i <= $N; $i++){
    for($j = 1; $j <= $N; $j++){
      if($d[$i][$j] > $d[$i][$k] + $d[$k][$j]){
        $d[$i][$j] = $d[$i][$k] + $d[$k][$j];
      }
    }
  }
}
echo dfs($rArray, -1);
function dfs($rArray, $current){
  global $d;
  if(!$rArray)return 0;
  $min = 10**10;
  foreach($rArray as $i => $p){
    $array = $rArray;
    unset($array[$i]);
    $dist = dfs($array, $p);
    if($current != -1){
      $dist += $d[$current][$p];
    }
    if($dist < $min){
      $min = $dist;
    }
  }
  return $min;
}

Measured memory_bytes: 6776
N = int(input())
button = []
for i in range(0, N):
	button.append(int(input())-1)
memo = []
for i in range(0, N):
	memo.append(False)
cnt = 0
now = 0
while not memo[now]:
	memo[now] = True
	if now == 1: break
	now = button[now]
	cnt += 1
if memo[1]: print(cnt)
else: print(-1)

Measured memory_bytes: 55512
#include <stdio.h>

int main(void)

{
	int w, h, n;
	int fx, fy, x, y;
	int sum = 0;
	int i, j;
	int dx, dy;

	scanf("%d %d %d", &w, &h, &n);

	scanf("%d %d", &fx, &fy);
	for (i = 1; i < n; i++){
		scanf("%d %d", &x, &y);
		dx = fx - x;
		dy = fy - y;

		if (dx < 0){
			dx *= -1;
		}
		if (dy < 0){
			dy *= -1;
		}

		if (fx > x && fy > y){
			
			sum += (dx + dy);
			if (dx < dy){
				sum -= dx;
			}
			else {
				sum -= dy;
			}
		}
		else if (fx < x && fy < y){
			sum += (dx + dy);
			if (dx < dy){
				sum -= dx;
			}
			else {
				sum -= dy;
			}
		}
		else {
			sum += (dx + dy);
		}
		fx = x;
		fy = y;
	}
	printf("%d\n", sum);

	return (0);
}

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

int main() {
  int N, A, B;
  cin >> N >> A >> B;

  if (A > B) { 
    cout << B << ' ';
  } else {
    cout << A << ' ';
  }

  if (A + B - N > 0) {
    cout << (A + B - N) << endl;
  } else {
    cout << 0 << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <set>
#include <vector>
#include <utility>
#include <algorithm>
#define llint long long

using namespace std;
typedef pair<llint, llint> P;

llint n, m;
vector<llint> G[1005];
int g[1005][1005];
int used[1005];
llint depth[1005], parent[1005];
vector<pair<P, P> > vec;
vector<int> ans;

int dfs(int v, int p, int d, int r)
{
	//cout << v << d << endl;
	used[v] = 1;
	depth[v] = d, parent[v] = p;
	for(int i = 0; i < G[v].size(); i++){
		if(used[G[v][i]] == 2) continue;
		if(used[G[v][i]] == 1){
			vec.push_back(make_pair(make_pair(depth[v] - depth[G[v][i]], r), make_pair(v, G[v][i])));
			continue;
		}
		dfs(G[v][i], v, d+1, r);
	}
	used[v] = 2;
	return 0;
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	llint u, v, t;
	for(int i = 1; i <= m; i++){
		cin >> u >> v;
		g[u][v] = 1;
		G[u].push_back(v);
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1;  j<= n; j++) used[j] = 0;
		//vec.clear();
		dfs(i, -1, 0, i);
	}
	if(vec.size() == 0){
		cout << -1 << endl;
		return 0;
	}
	
	sort(vec.begin(), vec.end());
	v = vec.front().second.first, t = vec.front().second.second;
	//cout<< vec.front().first.second << " " << v << " " << t << endl;
	
	for(int j = 1;  j<= n; j++) used[j] = 0;
	dfs(vec.front().first.second, -1, 0, 0);
	while(v != t){
		//cout << v << " " << t << endl;
		ans.push_back(v);
		v = parent[v];
	}
	ans.push_back(t);
	cout << (int)ans.size() << endl;
	for(int j = 0; j < ans.size(); j++) cout << ans[j] << endl;
	
	return 0;
}

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

int main() {
  int a, s1, s2, s3;
  cin >> a;
  
  s1 = a*0.01;
  s2 = a*0.1 - s1*10;
  s3 = a - s1*100 - s2*10;
  cout << s1 + s2 + s3 << endl;
}


Measured memory_bytes: 256
#include <iostream>
#define llint long long
#define mod 998244353

using namespace std;

llint n;
llint cnt[100005];

llint modpow(llint a, llint n)
{
	if(n == 0) return 1;
	if(n % 2){
		return ((a%mod) * (modpow(a, n-1)%mod)) % mod;
	}
	else{
		return modpow((a*a)%mod, n/2) % mod;
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	llint mx = 0, x;
	for(int i = 1; i <= n; i++){
		cin >> x;
		if(i == 1 && x != 0){
			cout << 0 << endl;
			return 0;
		}
		cnt[x]++;
		mx = max(mx, x);
	}
	
	for(int i = mx; i >= 0; i--){
		if(cnt[i] == 0){
			cout << 0 << endl;
			return 0;
		}
	}
	if(cnt[0] > 1){
		cout << 0 << endl;
		return 0;
	}
	
	llint ans = 1;
	for(int i = 1; i <= mx; i++){
		ans *= modpow(cnt[i-1], cnt[i]), ans %= mod;
	}
	cout << ans << endl;
	
	return 0;
}

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

    class Wa
    {
        static void Main()
        {
            //            int a = int.Parse(Console.ReadLine());
             string str = Console.ReadLine();
             int a = int.Parse(str);
            Console.WriteLine("{0}:{1}:{2}",a/3600, (a%3600)/60,a%60);

        }
    }

Measured memory_bytes: 5624
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
#define rep(i, s, n) for(int i = s; i < n; i++)
#define ll long long

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    vector<pair<int, int>> direction_w;
    vector<pair<int, int>> direction_e;

    int w_count = 0;
    int e_count = 0;
    rep(i, 0, n) {
        if(s[i] == 'W') {
            w_count++;
        }
        else if(s[i] == 'E') {
            e_count++;
        }
        direction_w.push_back(make_pair(w_count, e_count));
    }

    w_count = 0;
    e_count = 0;
    for(int i = s.size()-1; i > -1; i--) {
        if(s[i] == 'W') {
            w_count++;
        }
        else if(s[i] == 'E') {
            e_count++;
        }
        direction_e.push_back(make_pair(w_count, e_count));
    }

    int ans = n;
    rep(i, 0, n) {
        if(s[i] == 'W') {
            //cout << "w :" << direction_w[i].first << " " << direction_e[n-i-1].second << endl;
            ans = min(direction_w[i].first+direction_e[n-i-1].second-1, ans);
        }
        else {
            //cout << "e :" << direction_w[i].first << " " << direction_e[n-i-1].second << endl;
            ans = min(direction_w[i].first+direction_e[n-i-1].second-1, ans);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 11764
INF = 10 ** 9

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

    dp = [INF] * N
    dp[0] = 0
    dp[1] = abs(H[1] - H[0])
    for i in range(2, N):
        dp[i] = min(dp[i-1]+abs(H[i]-H[i-1]), dp[i-2]+abs(H[i]-H[i-2]))

    print(dp[N-1])


if __name__ == "__main__":
    main()

Measured memory_bytes: 13924
#include <bits/stdc++.h>
#define dbug(x) cout<<#x<<"="<<x<<endl
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while ('0'>ch||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do {(t*=10)+=ch-'0';ch=getchar();} while ('0'<=ch&&ch<='9'); t*=f;
}
typedef long long ll;
int n,m,q,ans[10];
map<ll,bool> M;
ll haxi(int i,int j) {
	return (ll)(i-1)*m+j;
}
int main() {
	//freopen("1.txt","r",stdin);
	read(n); read(m); read(q); int x,y,cnt;
	while (q--) {
		read(x); read(y);
		for (int i=max(1,x-2);i<=x;i++) {
			if (i+2>n) break;
			for (int j=max(1,y-2);j<=y;j++) { cnt=0;
				if (j+2>m) break;
				for (int k1=0;k1<=2;k1++)
				for (int k2=0;k2<=2;k2++)
					cnt+=M[haxi(i+k1,j+k2)];
				ans[cnt]--; ans[cnt+1]++;
			}
		} M[haxi(x,y)]=1;
	} cnt=0;
	for (int i=1;i<=9;i++) cnt+=ans[i];
	printf("%lld\n",(ll)(n-2)*(m-2)-cnt);
	for (int i=1;i<=9;i++) printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 156544
#include<stdio.h>


int main(void){

	int lh,lw;
	int h,w;
	int min;

	int b,mas;

	scanf("%d %d",&lh,&lw);
	scanf("%d %d",&h,&w);

	printf("%d\n",(lh-h)*(lw-w));

	

	return 0;
}

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

#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, m, n) for(int i = (m); i < (int)(n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define INF 2000000000

#ifdef LOCAL
  #define eprintf(...) fprintf(stdout, __VA_ARGS__)
#else
  #define eprintf(...) 0
#endif

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int uint;

int main() {
  int h, w;
  cin >> h >> w;

  if(h % 3 == 0 || w % 3 == 0) {
    cout << 0 << endl;
    return 0;
  }

  

  LL minsize = INF;
  LL pmin, pmax;
  FOR(tw, 1, w/2+1) {
    LL p1 = (LL)tw * h;
    LL p2 = (LL)(h/2) * (w-tw);
    LL p3 = (LL)w*h - p1 - p2;
    LL p4 = (LL)(w-tw)/2 * h;
    LL p5 = (LL)w*h - p1 - p4;
    pmin = min({p1, p2, p3});
    pmax = max({p1, p2, p3});
    minsize = min(minsize, abs(pmax-pmin));
    pmin = min({p1, p4, p5});
    pmax = max({p1, p4, p5});
    minsize = min(minsize, abs(pmax-pmin));
    //minsize = min(minsize, abs(p1-p2));
    eprintf("t,p1,p2,minsize:%d,%lld,%lld,%lld\n", tw,p1,p2,minsize);
  }
  eprintf("minsize:%lld\n", minsize);
  FOR(th, 1, h/2+1) {
    LL p1 = (LL)w * th;
    LL p2 = (LL)(w/2) * (h-th);
    LL p3 = (LL)w*h - p1 - p2;
    LL p4 = (LL)(h-th)/2 * w;
    LL p5 = (LL)w*h - p1 - p4;
    pmin = min({p1, p2, p3});
    pmax = max({p1, p2, p3});
    minsize = min(minsize, abs(pmax-pmin));
    pmin = min({p1, p2, p3});
    pmax = max({p1, p4, p5});
    minsize = min(minsize, abs(pmax-pmin));
    eprintf("t,p1,p2,minsize:%d,%lld,%lld,%lld\n", th,p1,p2,minsize);
  }
  cout << minsize << endl;


  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) (a).begin(),(a).end()
#define print(A,x,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i]x;}cout<<endl;
#define pprint(A,y,m,n) rep(j,0,m){print(A[j],y,n);}
const long mod=1e9+7;
const int size=1e5;
const int inf=1e9;
int main(){
	int L;cin>>L;
	int n = 0;int cnt = 0;
    int temp = L;
	while(temp){
        n++;
        cnt += temp % 2;
        temp /= 2;
    }
    cout<<n<<" "<<2 * (n - 1) + cnt - 1<<endl;
	rep(i,1,n){
		cout<<i<<" "<<i + 1<<" "<<0<<endl;
		cout<<i<<" "<<i + 1<<" "<<(1<<i-1)<<endl;
	}
	int t = (1<<n-1);
	for(int i = n-2; i>=0; i--){
		if(L & (1<<i)){
			cout<<i + 1<<" "<<n<<" "<<t<<endl;
			t += (1<<i);
		}
	}
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

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

//                 0 1   2   3
//                 L  D   U  R
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};

// Self settings
// clang-format off
#define MAX_N 100000
#define MAX_W 4000
#define MAX_H 4000
#define INF 1000000000
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
// clang-format on

int H, W;
bool S[MAX_H][MAX_W];
int memo[MAX_H][MAX_W][4];

// L: 0
// D: 1
// U: 2
// R: 3
int dfs(int i, int j, int d)
{
  // 範囲外なら 0 を返す
  if (j < 0 || j >= W || i < 0 || i >= H) return 0;

  // 壁の場合 0 を返す
  if (!S[i][j]) return 0;

  // すでに訪問済みならそれを返す
  if (memo[i][j][d] != INF) {
    return memo[i][j][d];
  }

  // 自分自身を数える
  int sum = 1;
  // ある方向dのすべてのマスを順番に数えていく
  sum += dfs(i + dy[d], j + dx[d], d);
  return memo[i][j][d] = sum;
}

void solve()
{
  // Init
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      for (int k = 0; k < 4; k++) memo[i][j][k] = INF;
    }
  }

  int ans = 0;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (!S[i][j]) continue;
      int sum = 0;
      for (int k = 0; k < 4; k++) {
        // 各方向の成分を足す
        sum += dfs(i, j, k);
      }
      // 自分自身を４回数えてるので3減らす
      sum -= 3;
      ans = max(ans, sum);
    }
  }

  cout << ans << endl;
}

int main(void)
{
  cin >> H >> W;
  REP(i, H) REP(j, W)
  {
    char c;
    cin >> c;
    S[i][j] = (c == '.');
  }
  solve();
  return 0;
}


Measured memory_bytes: 135424
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>

using namespace std;

int main() {
	int n, k;
	scanf("%d%d", &n, &k);

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

	const int mod = 1e9+7;
	int dp[n][k+1];
	int sum_dp[n][k+1];
	memset(dp, 0, sizeof dp);
	for(int j=0; j<=a[0]; j++) {
		dp[0][j] = 1;
	}
	sum_dp[0][0] = dp[0][0];
	for(int j=1; j<=k; j++) {
		sum_dp[0][j] = sum_dp[0][j-1]+dp[0][j];
	}
	for(int i=1; i<n; i++) {
		for(int j=k; j>=0; j--) {
			dp[i][j] = sum_dp[i-1][j] + mod - ( j-a[i]-1>=0 ? sum_dp[i-1][j-a[i]-1] : 0);
			if(dp[i][j]>=mod) dp[i][j]-=mod;
		}
		sum_dp[i][0] = dp[i][0];
		for(int j=1; j<=k; j++) {
			sum_dp[i][j] = sum_dp[i][j-1]+dp[i][j];
			if(sum_dp[i][j]>=mod) sum_dp[i][j]-=mod;
		}
	}
	printf("%d\n", dp[n-1][k]);
    return 0;
}

Measured memory_bytes: 78336
#include<cstdio>
#include<cctype>
#include<cstring>
inline int getint() {
	register char ch;
	register bool neg=false;
	while(!isdigit(ch=getchar())) if(ch=='-') neg=true;
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return neg?-x:x;
}
const int N=10001,M=20001;
char s[N];
int op[N]={1};
bool f[2][M],tmp[M];
int main() {
	scanf("%s",s);
	const int x=getint(),y=getint();
	op[1]=s[0]=='F';
	for(register int i=1;s[i];i++) {
		if(s[i]=='T'&&s[i-1]=='T') op[++op[0]]=0;
		if(s[i]=='F') {
			if(s[i-1]=='T') op[0]++;
			op[op[0]]++;
		}
	}
	f[0][N]=f[1][N]=true;
	bool first=true;
	for(register int i=1;i<=op[0];i++) {
		memset(tmp,0,sizeof tmp);
		for(register int j=0;j<M-op[i];j++) tmp[j+op[i]]|=f[i&1][j];
		if(!first) {
			for(register int j=op[i];j<M;j++) tmp[j-op[i]]|=f[i&1][j];
		} else {
			first=false;
		}
		memcpy(f[i&1],tmp,sizeof tmp);
	}
	puts(f[0][N+y]&&f[1][N+x]?"Yes":"No");
	return 0;
}

Measured memory_bytes: 384
#include <stdio.h>

int main(void) {

  int l,r,d;
  scanf("%d %d %d", &l, &r, &d);
  int count = 0;
  for (int i = l; i <= r; i++) {
    if (i%d == 0) {
      count++;
    }
  }
  printf("%d\n", count);

  return 0;
}

Measured memory_bytes: 1724
# AOJ 1029: Traffic Analysis
# Python3 2018.7.6 bal4u

import sys
from sys import stdin
input = stdin.readline

while True:
	n, m = map(int, input().split())
	if n == 0 and m == 0: break
	if n > 0: a = list(map(int, input().split()))
	if m > 0: b = list(map(int, input().split()))
	ans = i = j = 0
	s, t = 0, -1
	while i < n or j < m:
		if i < n:
			if s == a[i]: i += 1
			if i < n: t = a[i]
		if j < m:
			if s == b[j]: j += 1
			if j < m and (t < 0 or b[j] < t): t = b[j]
		if t >= 0:
			if i < n and t == a[i]: i += 1
			if j < m and t == b[j]: j += 1
			ans = max(ans, t-s)
			s, t = t, -1
	if t >= 0: ans = max(ans, t-s)
	print(ans)


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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int64 n,t;
  cin >> n >> t;
  vector<int64> a(n);
  REP(i,n)cin >> a[i];
  int64 earn = 0;
  int64 mn = LLINF;
  REP(i,n){
    mn = min(mn,a[i]);
    earn = max(earn, a[i] - mn);
  }
  mn = LLINF;
  int64 ans = 0;
  REP(i,n){
    mn = min(mn,a[i]);
    if(earn == a[i] - mn)ans++;
  }
  ANS(ans);
  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
using namespace std;
  
int main () {
  int a, b, c;
  cin >> a >> b >> c;
  if(a+b+c >= 22)
    cout << "bust";
  else cout << "win";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[200007];
int main(){
    int n;
    cin>>n;
    int mx=0,mxx=0;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        if(a[i]>mx){
            mxx=mx;
            mx=a[i];
        }
        else if(a[i]>mxx){
            mxx=a[i];
        }
    }
    for(int i=1;i<=n;++i){
        if(a[i]!=mx)
            cout<<mx<<"\n";
        else
            cout<<mxx<<"\n";
    }
    return 0;
}


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

#define ll long long

int mod(string num, int a) {
    int res = 0;
    for (int i = 0; i < num.length(); i++)
         res = (res*10 + (int)num[i] - '0') %a;
    return res;
}

string k;
ll d;
ll n;

ll M = 1e9+7;

ll dp[10002][2][102];

ll f(ll cur, bool b, ll sum){
    if(cur==n){
        if(sum%d==0) return 1;
        else return 0;
    }

    if(dp[cur+1][b][sum]!=-1) return dp[cur+1][b][sum]%M;

    if(b){
        ll ans=0;
        for(ll i=0;i<=9;i++){
            ans+=(f(cur+1, b, (sum+i)%d))%M;
            ans%=M;
        }
        ans%=M;
        return dp[cur+1][b][sum] = ans%M; // dp[cur][b][sum] =
    }

    else{
        ll z = k[cur]-'0';
        ll ans=0;
        for(ll i=0;i<z;i++){
            ans+=(f(cur+1, true, (sum+i)%d))%M;
            ans%=M;
        }
        ans%=M;
        ans+=(f(cur+1, false, (sum+z)%d))%M;
        ans%=M;
        return dp[cur+1][b][sum] = ans%M; //
    }
}

int main(){
    // cout<<(-1+M)%M;
    memset(dp, -1, sizeof(dp));
    cin>>k>>d;
    n=k.length();
    cout<<(f(0, false, 0) - 1 + M) % M<<endl;
    return 0;
}

Measured memory_bytes: 17024
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1LL<<60
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<P, bool> PI;

int w, h, k;
vector<P> X[200005], Y[200005];
vector<P> xy;
// map<int, vector<int> > X;
// map<int, vector<int> > Y;
map<pair<int, int>, int > id;
// map<int, pair<int,int> > xy;
ll d[200005][2];

// PI f(int a, int b, int c) {
// 	return mp(mp(a, b), c);
// }

void dijkstra() {
	rep(i, 200005) {
		d[i][0] = INF;
		d[i][1] = INF;
	}

	// cost id (0 or 1)
	priority_queue<PI, vector<PI>, greater<PI> > que;

	rep(i, X[1].size()) {
		int y = X[1][i].first;
		int to = X[1][i].second;
		// int to = id[mp(y, 1)];

		d[to][1] = y;
		// que.push(f(y, to, 1));
		que.push(mp(mp(y, to), 1));
	}

	while(que.size()) {
		PI p = que.top(); 
		que.pop();

		int c = p.first.first;
		int v = p.first.second;
		int state = p.second;

		if(d[v][state] < c) continue;

		int y = xy[v].first;
		int x = xy[v].second;

		// cout << " ------ : (" << y << "," << x << "," << state << ") :" << v << " " << c << endl;

		if(state == 0) {
			rep(i, X[x].size()) {
				int ny = X[x][i].first;
				int to = X[x][i].second;
				// int to = id[mp(ny, x)];

				if(ny == y) continue;

				if(d[to][1] > d[v][state] + abs(ny - y) + 1) {
					d[to][1] = d[v][state] + abs(ny- y) + 1;
					// que.push(f(d[to][1], to, 1));
					que.push(mp(mp(d[to][1], to), 1));
				}
			}
		} else {
			rep(i, Y[y].size()) {
				int nx = Y[y][i].first;
				int to = Y[y][i].second;
				// int to = id[mp(y, Y[y][i])];

				if(nx == x) continue;

				if(d[to][0] > d[v][state] + abs(nx - x) + 1) {
					d[to][0] = d[v][state] + abs(nx - x) + 1;
					// que.push(f(d[to][0], to, 0));
					que.push(mp(mp(d[to][0], to), 0));
				}
			}
		}
	}
}

int main() {
	cin >> w >> h >> k;

	xy.resize(k);
	rep(i, k) {
		int x, y;
		cin >> x >> y;

		xy[i] = mp(y, x);
		X[x].push_back(mp(y, i));
		Y[y].push_back(mp(x, i));
	}

	dijkstra();

	// rep(i, k) {
	// 	cout << "k:" << i << " (" << xy[i].first << "," << xy[i].second << ") :" << d[i][0] << " : " << d[i][1] << endl;
	// }

	ll ans = INF;
	rep(i, k) {
		int y = xy[i].first;
		int x = xy[i].second;

		if(y == h) {
			ans = min(ans, d[i][1] + abs(w - x));
		}

		if(x == w) {
			ans = min(ans, d[i][0] + abs(h - y));
		}
	}

	if(ans == INF) cout << -1 << endl;
	else cout << ans << endl;


	return 0;
}

Measured memory_bytes: 28868
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

int selection_sort(int *data, int n)
{
	int change = 0;
	for(int i = 0; i < n-1; i++) {
		int min_j = i;
		for(int j = i+1; j < n; j++) {
			if(data[min_j] > data[j]) {
				min_j = j;
			}
		}
		swap(data[i], data[min_j]);
		if(min_j != i) change++;
	}

	return change;
}

int main(void)
{
	int *data;
	int n;

	cin >> n;
	data = new int[n];

	for(int i = 0; i < n; i++) {
		cin >> data[i];
	}

	int change = selection_sort(data, n);

	for(int i = 0; i < n; i++) {
		if(i) cout << " ";
		cout << data[i];
	}
	cout << endl;
	cout << change << endl;

	delete data;
	return 0;
}


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

using namespace std;

int main(){
  int pair[100];
  int input;
  vector<int> inputs;
  
  for(int i = 0; i < 10; i++)
    for(int j = 0; j < 10; j++)
      pair[i * 10 + j] = i + j;


  while(cin >> input) inputs.push_back(input);

  for(int k = 0; k < (int)inputs.size(); k++){
    int input = inputs[k];
    int count = 0;
    
    if(input <= 36){
      for(int i = 0; i < 100; i++){
	int cd = input - pair[i];
	
	if(cd <= 18 && cd >= 0){
	  for(int j = 0; j < 100; j++) if(pair[j] == cd)
	      count++;
	}
      }
    }
    
    cout << count << endl;
  }

  return 0;
}

Measured memory_bytes: 3040
open Batteries
module EnumL = Enum.Labels
module ListL = List.Labels
module ArrayL = Array.Labels

let dbg0 x = Printf.eprintf "[debug]%s\n" @@ dump x
let dbg1 x = dbg0 x; x

let id = identity

let (++) n m = List.range n `To m
let (++-) n m = if n >= m then List.range n `Downto m else []
let (++^) n m = if n < m then List.range n `To (pred m) else []

let scan fmt = Scanf.sscanf (read_line ()) fmt

let scan_lines n fmt f =
  if n = 0 then []
  else List.map (fun _ -> scan fmt f) (1 ++ n)

let scan_list sep cnv =
  let line = read_line () in
  (match sep with
   | None -> List.map String.of_char @@ String.to_list line
   | Some sep -> String.split_on_char sep line)
  |> List.map cnv

let scan_array ?sep cnv = Array.of_list @@ scan_list sep cnv

let scan_matrix n m e ?sep conv =
  let arr = Array.make_matrix n m e in
  ListL.iter (0 ++^ n)
    ~f:(fun i -> arr.(i) <- Array.of_list @@ scan_list sep conv);
  arr

let rec powerset e =
  match Enum.get e with
  | None -> Enum.singleton @@ Enum.empty ()
  | Some v ->
    let f = powerset e in
    let g = Enum.clone f in
    EnumL.map f ~f:(fun x -> let y = Enum.clone x in push y v; y)
    |>  Enum.append g

let permutations l =
  let rec aux l =
    let rec interleave x = function
      | [] -> [[x]]
      | (hd::tl) as lst ->
        (x::lst) ::
        (ListL.map ~f:(List.cons hd)  @@ interleave x tl)
    in
    match l with
    | [] -> [[]]
    | hd::tl -> List.concat @@ List.map (interleave hd) @@ aux tl in
  let l = List.sort (List.compare Int.compare) @@ aux @@ List.of_enum l in
  List.enum % ListL.map ~f:List.enum @@ l

let intersection l =
  EnumL.filter ~f:(fun x -> EnumL.exists ~f:((=) x) @@ Enum.clone l)

let zip l m =
  let n = min (List.length l) (List.length m) in
  List.combine (List.take n l) (List.take n m)

let lower_bound n f =
  let rec aux l u =
    if u - l > 1 then
      let m = (l + u) / 2 in
      if f m then aux l m
      else aux m u
    else u in aux (-1) n

let between n x m = n <= x && x < m

let n = scan "%d" id

let () =
  Printf.printf "%d\n" (n*(n-1)/2)


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

const int maxn = 1e7+7;
const int INF=0x3f3f3f3f;
int isP[maxn];
int pri[maxn];
int cnt;
void getP()
{
    for(int i=2; i<maxn; i++)isP[i]=1;
    memset(pri,INF,sizeof(pri));
    pri[0]=0;
    cnt=0;
    for(int i=2; i<maxn; i++)
        if(isP[i])
        {
            pri[++cnt]=i;
            for(int j=i+i; j<maxn; j+=i)
            {
                isP[j]=0;
            }
        }
}

int main()
{
    getP();
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int l=0,r=cnt+1;
        while(r-l>1){
            int mid=(r+l)>>1;
            if(pri[mid]<=n){
                l=mid;
            }else {
                r=mid;
            }
        }
        printf("%d\n",l);
    }
    return 0;
}



Measured memory_bytes: 81328
N,M,X,Y=map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A.append(X)
B.append(Y)
A.sort()
B.sort()
if A[-1]>=B[0]:
  print("War")
else:
  print("No War")

Measured memory_bytes: 9176
// AOJ 2575: D's Ambition
// 2017.10.13 bal4u@uu

#include <stdio.h>
#include <string.h>

char d[1010], *p;
char z[1002], *q;
char gg['Z'+10], *g = gg + 'A';
char ff['Z'+10], *f = ff + 'A';

int aizunyan()
{
	int i;
	char *pp = p;

	memset(f, 0, 26);
	for (i = 0; i < 8 && *pp >= 'A'; i++) ff[*pp++]++;
	if (i < 8 || memcmp(f, g, 26)) return 0;
	memcpy(q, "AIZUNYAN", 8);
	p += 8, q += 8;
	return 1;
}

int main()
{
	gg['A'] = 2, gg['D'] = 1, gg['I'] = 1, gg['U'] = 1, gg['N'] = 2, gg['Y'] = 1;
	fgets(d, 1005, stdin);
	p = d, q = z;
	while (*p >= 'A') if (!aizunyan()) *q++ = *p++;
	*q = 0;	puts(z);
	return 0;
}

Measured memory_bytes: 1712
#include<iostream>

using namespace std;

int main(void)
{
	while(1){
		int n[10][10];
		long long int t;
		cin>>t;
		if(cin.eof())break;
		for(int i=0;i<10;i++){
			n[0][i]=t%10;
			t/=10;
		}
		for(int i=1;i<10;i++)
		{
			for(int j=0;j<10-i;j++)
			{
				n[i][j]=(n[i-1][j]+n[i-1][j+1])%10;
			}
		}
		cout<<n[9][0]<<endl;
	}
}

Measured memory_bytes: 1156
// arock - 2019-02-09

#include <iostream>

int main() {
    // 1, 3, 5, 7
    int N, K;
    std::cin >> N >> K;
    if (2 * K - 1 <= N) {
        std::cout << "YES" << std::endl;
    } else {
        std::cout << "NO" << std::endl;
    }
}


Measured memory_bytes: 256
n,m=map(int, input().split())
value=sorted(list(map(int,input().split())), reverse=True)
weight=[0,2,5,5,4,5,6,3,7,6]
dp=[-1]*(n+1)
dp[0]=0
for i in range(n+1):
    for j in value:
        if i + weight[j] < n+1:
            dp[i+weight[j]] = max(dp[i+weight[j]],dp[i]*10+j)
print(dp[n])

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

int main(void){
  
  long i,A,B,K;
  char str[100],*p;
  
  fgets(str,sizeof(str),stdin);
  p=strtok(str," \n");
  A=atol(p);
  p=strtok(NULL," \n");
  B=atol(p);
  p=strtok(NULL," \n");
  K=atol(p);
  
  if(A+K-1>=B-K+1){
   for(i=A;i<=B;i++){
     printf("%ld\n",i);
   }
     return 0;
  }
  
  for(i=A;i<A+K;i++){
   printf("%ld\n",i); 
  }
  
  for(i=B-K+1;i<=B;i++){
   printf("%ld\n",i); 
  }
  
  return 0;
}

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

int main(void){
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    int dp[n];
    dp[0]=0;
    dp[1]=abs(arr[1]-arr[0]);
    for(int i=2;i<n;i++){
        dp[i]=min(dp[i-2]+abs(arr[i-2]-arr[i]), dp[i-1]+abs(arr[i]-arr[i-1]));
    }
    cout<<dp[n-1]<<endl;

    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  int x=n%10;
  if(x==3){
    cout<<"bon"<<endl;
  }
  else if(x==0||x==1||x==6||x==8){
    cout<<"pon"<<endl;
  }
  else{
    cout<<"hon"<<endl;
  }
}

Measured memory_bytes: 3592
lm,tm=[],[]
while gets.chomp!=""
  lm<<$_.split(",").map(&:to_i)[0]
end
while gets
  tm<<$_.split(",").map(&:to_i)[0]
end
lm.uniq.sort.each do |n|
  puts "#{n} #{(lm+tm).count(n)}" if tm.include?(n)
end

Measured memory_bytes: 8580