akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<limits.h>

#define MOD 1000000007


using namespace std;

long long int modpow(long long int a, int n) {

	if (n == 0)return 1;
	if (n == 1) return a;

	long long int wk = modpow(a, n / 2);

	long long int ret = 0;
	if (n % 2 == 0) {
		ret = 1;
	}
	else {
		ret = a;
	}

	return (((ret * wk) % MOD) * wk) % MOD;

}

long long int gcd(long long int a, long long int b) {
	long long int tmp;
	if (a < b) {
		tmp = a;
		a = b;
		b = tmp;
	}

	long long int r = a % b;

	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}

	return b;
}

long long int lcm(long long int a, long long int b) {

	long long int wk_int;

	wk_int = (a * b) % MOD;
	
	long long int ret;

	ret = (wk_int * modpow(gcd(a, b), MOD - 2)) % MOD;

	return ret;

}

bool isPrime(int n) {
	if (n == 1)return false;
	if (n == 2)return true;

	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}

	return true;
}








int main()
{
	
	int  n, y;
	cin >> n >> y;

	for (int itiman = 0; itiman <= y / 10000; itiman++) {
		for (int gosen = 0; gosen <= y / 5000; gosen++) {
			int nokori = y - (10000 * itiman) - (5000 * gosen);
			if (nokori < 0)break;
			int sen = nokori / 1000;

			if (itiman + gosen + sen == n) {
				cout << itiman << " " << gosen << " " << sen << endl;
				return 0;
			}

		}
	}

	cout << "-1 -1 -1" << endl;





	return 0;

}



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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,n) for(int i=(int)(n-1);i>=0;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x" = " << x << endl
#define print(x) cout << x << endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<int, P> PIP;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;
typedef set<int> S;

#define INF INT_MAX/3
#define MAX_N 1000000001

bool know[100][100];

int main(){
    cin.sync_with_stdio(false);
    int n;
    while(cin >> n, n) {
        memset(know, 0, sizeof(know));
        rep(i, n) {
            int m;
            cin >> m;
            rep(j, m) {
                int p;
                cin >> p;
                know[i][p - 1] = true;
            }
        }

        int k;
        cin >> k;
        bool possible[n];
        fill(possible, possible + n, true);
        rep(i, k) {
            int l;
            cin >> l;
            rep(j, n) {
                if (!(know[j][l - 1] && possible[j])) possible[j] = false;
            }
        }
        int cnt = 0, ans = 0;
        rep(i, n) if (possible[i]) cnt++, ans = i + 1;
        if (cnt == 1) cout << ans << endl;
        else cout << -1 << endl;
    }

    return 0;
}

Measured memory_bytes: 3152
///////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

///////////////////////////////////////////////////////////////////////////////

#define pb push_back

void intin(int &a)
{
        cin >> a;
}

void intinl1(auto &v, int count)
{
        for (int i = 0; i < count ; ++i) {
                int a;
                cin >> a;
                v.push_back(a);
        }
}

void intinl2(auto &v, int count)
{
        for (int i = 0; i < count ; ++i) {
                int a, b;
                cin >> a >> b;
                v.push_back({a, b});
        }
}

void intinl3(auto &v, int count)
{
        for (int i = 0; i < count ; ++i) {
                int a, b, c;
                cin >> a >> b >> c;
                v.push_back({a, b, c});
        }
}

void intina(auto &v, int count)
{
        intinl1(v, count);
}

///////////////////////////////////////////////////////////////////////////////

int main()
{
        int n[5], k;
        intin(n[0]); intin(n[1]); intin(n[2]); intin(n[3]); intin(n[4]); intin(k);

        for (int i = 0; i < 5; i++) {
                for (int j = i + 1; j < 5; j++) {
                        if (n[j] - n[i] > k) {
                                cout << ":(";
                                return 0;
                        }
                }
        }

        cout << "Yay!";

        return 0;
}

///////////////////////////////////////////////////////////////////////////////


Measured memory_bytes: 256
//先輩の模範解答
#include<stdio.h>

int main() {
	char s[1100];

	while(true) {
		scanf("%s",s);
		if(s[0] == '0')
			break;
		int sum = 0;

		for(int i = 0;s[i] != '\0';i++) {
			sum += s[i] - '0';
		}
		printf("%d\n",sum);
	}
}


Measured memory_bytes: 2712
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>

using namespace std;

#define ll long long
#define all(v) v.begin(),v.end()
#define bootstrap ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);


void solve() {
    long a, b, c, d;
    ll n1, n2, n3, n4;
    cin >> a >> b >> c >> d;
    n1 = a * c;
    n2 = a * d;
    n3 = b * c;
    n4 = b * d;
    ll res = max(n1, n2);
    res = max(res, n3);
    res = max(res, n4);
    cout << res;
}

int main() {
    bootstrap;
    solve();
}

Measured memory_bytes: 3648
s = input()
ans = 'NO'
t = ['dream', 'dreamer', 'erase', 'eraser']

t_t = []
for i in t:
    i = i[::-1]
    t_t.append(i)

s = s[::-1]

while s:
    if s[:len(t_t[0])] == t_t[0]:
        s = s[len(t_t[0]):]
    elif s[:len(t_t[1])] == t_t[1]:
        s = s[len(t_t[1]):]
    elif s[:len(t_t[2])] == t_t[2]:
        s = s[len(t_t[2]):]
    elif s[:len(t_t[3])] == t_t[3]:
        s = s[len(t_t[3]):]
    else:
        break
    if not s:
        ans = 'YES'

print(ans)

Measured memory_bytes: 3188
#include <iostream>
#define R(i,n) for(i=0;i<n;i++)
using namespace std;
int main()
{
long long int a[100][100],b[100][100],c[100][100]={0};
int n,m,l,i,j,k;
cin>>n>>m>>l;
R(i,n)R(j,m)cin>>a[i][j];
R(i,m)R(j,l)cin>>b[i][j];
R(i,n)R(j,l)R(k,m)c[i][j]+=a[i][k]*b[k][j];
R(i,n){R(j,l){
if (j)cout<<' ';
cout<<c[i][j]; 
}
cout<<endl;
}
}

Measured memory_bytes: 3308
n= int(input())
def func(cur,use,count):
  if cur > n:
    return
  if use == 0b111:
    count.append(1)
  func(cur*10+3,use|0b001,count)
  func(cur*10+5,use|0b010,count)
  func(cur*10+7,use|0b100,count)
res = []
func(0,0,res)
print(sum(res))

Measured memory_bytes: 3188
import sys
input = sys.stdin.readline

n = int(input())
h = list(map(int, input().split()))

def main():
    dp = [0]*n
    dp[1] = abs(h[0]-h[1])
    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[-1])
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 20456
N=int(input())
Xs=list(map(int, input().split()))
nXs=sorted(Xs)

medL=nXs[len(nXs)//2-1]
medR=nXs[len(nXs)//2]

if medL == medR:
    for i in range(N):
        print(medL)
else:
    for i in Xs:
        if i<=medL:
            print(medR)
        else:
            print(medL)

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

namespace C_sharp
{
    class Program
    {
        static void Main(string[] args)
        {
            var alp_num = new int[26];
            
            while (true)
            {
                string line = Console.ReadLine();
                if (line == null)
                {
                    break;
                }

                foreach (char c in line.ToCharArray())
                {
                    if (Char.IsLetter(c))
                    {
                        alp_num[Char.ToLower(c)-97]++;
                    }
                }
            }

            var i = 97;
            foreach (var n in alp_num)
            {
                Console.WriteLine($"{(Char)i++} : {n}");
            }
        }
    }
}



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

import numpy as np


# def input():
#     return sys.stdin.readline().rstrip()


def main():
    n, k = map(int, input().split())

    warps = list(map(int, input().split()))
    warps = [0] + warps
    # warps = np.array(warps, dtype=int)

    # order_num = np.zeros(len(warps) + 1, dtype=int)
    order_num = [0 for i in range(len(warps))]
    path_history = []

    node = 1
    while order_num[node] == 0:
        path_history.append(node)
        order_num[node] = len(path_history)
        node = warps[node]

    # print(order_num)
    # print(path_history)
    begin = order_num[node]
    # print(tail)

    if k <= begin:
        print(path_history[k])
    else:
        # path_history = path_history[tail:]
        # print(path_history)
        leng = len(path_history) - order_num[node] + 1
        # print(leng)
        index = (k - (begin - 1)) % leng
        # print(index)
        print(path_history[begin - 1 + index])


main()


Measured memory_bytes: 51080
n, m, x = map(int,input().split())
CA = [list(map(int,input().split())) for _ in range(n)]

ans = 10**9

for i in range(2**n):
    ls = [0] * m
    tmp = 0
    for j in range(n):
        if (i >> j) & 1:
            ls = [l + a for l, a in zip(ls, CA[j][1:])]
            tmp += CA[j][0]
    if all(i >= x for i in ls):
        ans = min(ans, tmp)
print(ans if ans != 10**9 else -1)

Measured memory_bytes: 9224
use std::io::{self, BufRead};
use std::cmp::{min, max};

fn main() {
  let stdin = io::stdin();
  let mut lines = stdin.lock().lines();
  let line = lines.next().unwrap();
  let vec: Vec<i32> = line.unwrap().split(' ').map(|x| x.parse().unwrap()).collect();
  let input = vec[0];

  let mut counts = vec![vec![1; 10]; 1];
  // counts[0][0] = 0;
  for i in 0..10 {
    let mut vec1 = vec![0; 10];
    for j in 0..10 {
      let beg = if j == 0 { 0 } else { j - 1 };
      let end = min(10, j + 2);
      vec1[j] = counts[i][beg..end].iter().fold(0, |x, y| x + y);
    }
    counts.push(vec1);
  }
  let mut counts2 = vec![0; 11];
  for i in 1..11 {
    counts2[i] = counts[i-1][1..].iter().fold(0, |x, y| x + y) + counts2[i-1];
  }

  let mut output = String::new();
  let mut res = input;
  let mut prev_digit: i32 = -1;
  for i in (0..11).rev() {
    if prev_digit == -1 && res < counts2[i] {
      continue;
    }
    if prev_digit == -1 {
      res -= counts2[i];
    }
    let beg = (if prev_digit == -1 { 1 } else { max(0, prev_digit - 1) }) as usize;
    let end = (if prev_digit == -1 { 10 } else { min(10, prev_digit + 2) }) as usize;
    for j in beg..end {
      if counts[i][j] >= res {
        output.push((j as u8 + 48) as char);
        prev_digit = j as i32;
        break;
      }
      res -= counts[i][j];
    }
  }

  println!("{}", output);
}

Measured memory_bytes: 4352
s=list(raw_input().split("T"))
x,y=map(int,raw_input().split())
cx,cy=len(s[0]),0
#print cx,cy
sx=s[2::2]
sy=s[1::2]
#print sx
#print sy
sx1=[len(_) for _ in sx]
sy1=[len(_) for _ in sy]
sx1.sort()
sx1.reverse()
sy1.sort()
sy1.reverse()
#print sx1
#print sy1

for i in sx1:
	if cx<x:
		cx+=i
	else:
		cx-=i

#print cx

for i in sy1:
	if cy<y:
		cy+=i
	else:
		cy-=i

#print cy
print "Yes" if cx==x and cy==y else "No"


Measured memory_bytes: 2820
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<functional>
#include<algorithm>
#include<bitset>
#include<utility>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
#define ll long long
map<ll,ll>m;
int ans=0;
int n;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++)
	{
		ll a;
		cin>>a;
		m[a]++;
	}
	for(map<ll,ll>::iterator it=m.begin();it!=m.end();it++)
		if(it->second>it->first)
			ans+=abs(it->second-it->first);
		else if(it->second<it->first)
			ans+=it->second;
	cout<<ans;
	return 0;
}


Measured memory_bytes: 6272
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define int int64_t
#define pcnt __builtin_popcount
#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define vec vector<int>
#define mat vector<vector<int>> //mat データ名(縦,vec(横));
#define F first
#define S second
int INF = 1000000000000000001; //10^18+1
int MOD = 1000000007; //10^9+7
//cout << fixed << setprecision(15); (小数点以下表示)

signed main () {
  int N;
  string S;
  cin >> N;
  N=N%10;
  if(N==0||N==1||N==6||N==8)S="pon";
  if(N==2||N==4||N==5||N==7||N==9)S="hon";
  if(N==3)S="bon";
  cout << S << endl;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

int N, M, A[100005], B[100005];

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; i++) scanf("%d", &A[i]);
	for (int i = 0; i < M; i++) scanf("%d", &B[i]);
	long long ans = 0;
	long long sum = 0;
	for (int i = 0; i < M - 1; i++) {
		long long mult = 1;
		mult *= (B[i + 1] - B[i]);
		mult %= MOD;
		mult *= (i + 1);
		mult %= MOD;
		mult *= (M - i - 1);
		mult %= MOD;
		sum += mult;
		sum %= MOD;
	}
	for (int i = 0; i < N - 1; i++) {
		long long s = 1;
		s *= (A[i + 1] - A[i]);
		s %= MOD;
		s *= (i + 1);
		s %= MOD;
		s *= (N - i - 1);
		s %= MOD;
		ans += (s * sum) % MOD;
		ans %= MOD;
	}
	printf("%lld\n", ans);
}


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

typedef long long ll;
typedef vector<ll> vl;



int main() {

    string s;
    cin >> s;
    int ans = 0;
    for(char c : s) {
	if( c == 'C' and ans == 0) {
	    ans ++;
	}
	if( c == 'F' and ans == 1) {
	    ans ++;
	}
    }
    if(ans == 2)
	cout << "Yes" << endl;
    else
	cout << "No" << endl;
    
}


Measured memory_bytes: 256
x,y,a,b,c=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
i=0
j=0
k=0
c1=(x+y)-min(c,x+y)
count=0
res=[]
s=0
while(i<x and j<y):
    if(p[i]>q[j]):
        ans=p[i]
        i+=1
    else:
        ans=q[j]
        j+=1
    if(count>=c1):
        res.append(ans)
    else:
        s+=ans
    count+=1
while(i<x):
    ans=p[i]
    i+=1
    if(count>=c1):
        res.append(ans)
    else:
        s+=ans
    count+=1

while(j<y):
    ans=q[j]
    j+=1
    if(count>=c1):
        res.append(ans)
    else:
        s+=ans
    count+=1
c1=min(c,x+y)
count=0
i=0
j=0
while(i<c1 and j<c1):
    if(count>=c1):
        break
    if(res[i]>r[j]):
        s+=res[i]
        i+=1
    else:
        s+=r[j]
        j+=1
    count+=1
print(s)









Measured memory_bytes: 23328
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define mod 1000000007
typedef long long ll;
using namespace std;

int main(){
  ll A, B;
  cin >> A >> B;
  if((A+B)%2==0){
    cout << (A+B)/2 << endl;
  }
  else cout << "IMPOSSIBLE" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
#include <sstream>
#include<map>
#include<cmath>
#include<queue>
#include <functional>
#define rep(i,n) for (int i = 0; i < n; ++i)


using namespace std;

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

	bool can = false;
	if (1 <= A && A <= 9)
	{
		if (1 <= B && B <= 9)
		{
			can = true;
		}
	}
	cout << (can? A*B : -1);
}

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

using namespace std;

int N, M, x, y;

vector<int> indeg, dist;
vector<vector<int>> graph;

int main(){
	cin >> N >> M;
	indeg.assign(N+1, 0);
	dist.assign(N+1, 0);
	graph.assign(N+1, vector<int>());
	for(int i =0 ; i < M; i++){
		cin >> x >> y;
		graph[y].push_back(x);
		indeg[x]++;
	}

	queue<int> q;
	for(int i = 1; i <= N; i++){
		if (indeg[i] == 0){
			q.push(i);
			dist[i] = 0;
		}
	}

	while(q.size() > 0){
		int u = q.front(); q.pop();
		for(int v : graph[u]){
			dist[v] = max(dist[v], dist[u] + 1);
			indeg[v]--;
			if (indeg[v] == 0){
				q.push(v);
			}
		}
	}

	int maxSol = 0;
	for(int i = 1; i <= N; i++) maxSol = max(maxSol, dist[i]);
	cout << maxSol << endl;

	return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
const ll MOD = 1000000007;
const ll INF = 1000000000000000;
#define all(v) v.begin(), v.end()

int main(){
  ll M,K;
  cin >> M >> K;
  if(M==0){
    if(K==0) cout << "0 0" << endl;
    else cout << -1 << endl;
  }else if(M==1){
    if(K==0) cout << "0 0 1 1" << endl;
    else cout << -1 << endl;
  }else{
    if((ll)pow(2,M)<=K) cout << -1 << endl;
    else{
      rep(i,(ll)pow(2,M)){
        if(i!=K) cout << i << " ";
      }
      cout << K << " ";
      for(ll i=(ll)pow(2,M)-1;i>=0;i--){
        if(i!=K) cout << i << " ";
      }
      cout << K << endl;
    }
  }
}

Measured memory_bytes: 3932
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define ll long long
#define INF (1 << 30)
#define INFLL (1LL << 60)

#define FOR(i,a,b) for(ll i = (a);i<(b);i++)
#define REP(i,a) FOR(i,0,(a))
#define MP make_pair

int main() {
	int n, a[100010], t;
	int minA[100010], maxA[100010];
	cin >> n >> t;
	for(int i = 0;i < n;i++){
		cin >> a[i];
	}

	maxA[n - 1] = a[n - 1];
	for(int i = n - 2;i >= 0;i--){
		maxA[i] = max(maxA[i + 1], a[i]);
	}

	int maxCost = 0;
	int same = 1;
	for(int i = 0;i < n;i++){
		int rieki = maxA[i] - a[i];
		if(rieki > maxCost){
			maxCost = rieki;
			same = 1;
		}else if(rieki == maxCost){
			same++;
		}
		// cout << maxA[i] << " ";
		// cout << rieki << " ";
	}
	// cout << endl;
	cout << same << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl
#define debug false

int N;
vector<int> c;
vector<int> G[214514];
vector<int> siz,countnode,Ans;

int f(int x){
    return x*(x+1)/2;
}

void dfs_s(int v, int p){
    for(int i=0;i<G[v].size();i++){
        if(G[v][i]==p)continue;
        dfs_s(G[v][i],v);
    }
    if(p!=-1)siz[p]+=siz[v];
    return;
}

void dfs(int v,int p){
    int prev = countnode[c[v]];
    for(int i=0;i<G[v].size();i++){
        if(G[v][i]==p)continue;
        countnode[c[v]] = siz[G[v][i]];
        dfs(G[v][i],v);
        Ans[c[v]]-=f(countnode[c[v]]);
    }
    countnode[c[v]] = prev - siz[v];
}



signed main(void){
    int a,b;
    cin >> N;
    REP(i,N){
        cin >> a;
        a--;
        c.push_back(a);
    }
    REP(i,N-1){
        cin >> a >> b;
        a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    siz.clear();
    REP(i,N){siz.push_back(1);}
    dfs_s(0,-1);
    //REP(i,N){cout << siz[i] << " ";}cout << endl;
    
    countnode.clear();
    REP(i,N){countnode.push_back(N);}
    Ans.clear();
    REP(i,N){Ans.push_back(f(N));}
    dfs(0,-1);
    
    //REP(i,N){cout << countnode[i] << " ";}cout << endl;
    REP(i,N){
        Ans[i]-=f(countnode[i]);
    }
    REP(i,N){
        cout << Ans[i] << endl;
    }
    
    return 0;
}



Measured memory_bytes: 33124
#include<stdio.h>

int main()
{
 int N;
 int T;
 int A;
 int H;
 int i;
 int index=-1;
 double diff;
 double mindiff=2000000;
 scanf("%d",&N);
 scanf("%d %d",&T,&A);
 for(i=0;i<N;i++) 
 {
  scanf("%d",&H);
  diff=A-(T-0.006*H);
  if(diff<0) diff=-1*diff;
  if(diff<mindiff)
  {
   mindiff=diff;
   index=i+1;
  }
 }
 printf("%d\n",index);
 return 0;
}


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

using namespace std;

#define INF 1 << 29
#define LL long long int

LL const MOD = 1000000007;

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


    string s;
    cin >> s;

    LL k;
    cin >> k;

    LL result = -1;

    LL dist = 5000000000000000;

    for(int i = 0; i < s.size() && result < 0; i++){
        LL j = (LL)(s[i] - '0');
        if(j == 1){
            k--;
            if(k <= 0){
                result = 1;
            }
        }else{
            result = j;
        }
    }

    cout << result << endl;
    
    return 0;
}

Measured memory_bytes: 256
from collections import Counter
input();a=sorted(Counter(map(int,input().split())).most_common())[::-1];c=b=0
for i in range(len(set(a))):
    if b and c:break
    if a[i][1]>3 and a[i][0]*c<a[i][0]**2:b=c=a[i][0]
    elif a[i][1]>1:b,c=c,a[i][0]
print(c*b)

Measured memory_bytes: 24104
s = list(input())
c = 0
if s[0] != "A":
    print("WA")
else:
    for i in s[2:-1]:
        if i == "C":
            c += 1
            b = i
    if c == 1:
        s.remove(s[0])
        s.remove(b)
        if "".join(s).islower():
            print("AC")
        else:
            print("WA")
    else:
        print("WA")

Measured memory_bytes: 3064
import java.util.*;

public class Main{
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		
		if(a<=b){
			System.out.println(a);
		}else{
			System.out.println(a-1);
		}
	}
}

Measured memory_bytes: 21716
sum = 0
res = []
s = []
x = 0
gets.split("").each_with_index { |v, i|
  if v == "\\"
    s << i
  elsif v == "/"
    j = s.pop()
    if !j.nil?
      a = i - j # index??????????????§?¨???????????¨??????????
      sum += a

      loop do
        k, b = res.pop
        if !k.nil?
          if j < k
            a += b
          else
            res << [k, b]
            break
          end
        else
          break
        end
      end
      res << [j, a]
    end
  end
}
puts sum
if res.size() == 0
  puts "0"
else
  puts "#{res.size()} #{res.map{|n| n[1]}.join(" ")}"
end

Measured memory_bytes: 10152
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long
using namespace std;
const int MOD = 1e9 + 7;
string str;
int dp[100010][110][2], d;
int f(int pos, int sum, int flag) {
    if(pos == (int)str.size()) return sum == 0;
    int &ans = dp[pos][sum][flag];
    if(ans == -1){
        int lim = str[pos] - '0';
        ans = 0;
        for(int i = 0; i <= 9; i++) {
            if(flag || i < lim) ans += f(pos + 1, (sum + i + d) % d, 1);
            else if(i == lim) ans += f(pos + 1, (sum + i + d) % d, 0);
            ans %= MOD;
        }
    }
    return ans;
}
int main(){
    fast;
    memset(dp, -1, sizeof dp);
    cin >> str >> d;
    cout << (f(0,0,0) - 1 + MOD) % MOD << "\n";
    return 0;
    return 0;
}


Measured memory_bytes: 90388
import heapq
n,m = map(int,input().split())
a = list(map(lambda x: int(x)*(-1),input().split()))

heapq.heapify(a)
for i in range(m):
     s = heapq.heappop(a)
     heapq.heappush(a,(-1)*(-s//2))
print(-sum(a))



Measured memory_bytes: 72216
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define MAX 510000
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;



int main(){
    ll n; cin >> n;
    ll level = 0;
    ll tmp = n;
    while(tmp > 0){
        tmp /= 2;
        level++;
    }
    rep(i,n-1){
        REP(j,i+1,n){
            rep(k,level){
                if(((i+1)&(1<<k))!=((j+1)&(1<<k))){
                    cout << k+1 << " ";
                    break;
                }
            }
        }
        cout << endl;
    }
}

Measured memory_bytes: 512
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2424

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

bool step1(string N){
	return N.length() == 1;
}

string step2(string N)
{
	int n = N.length();

	string num1,num2;
	int max_value=0;
	REP(i,1,n)
	{
		num1 = N.substr(0,i);
		num2 = N.substr(i);
		int tmp = stoi(num1) * stoi(num2);
		max_value = max(max_value, tmp);
	}

	return to_string(max_value);
}

int main()
{
	int Q;
	cin >> Q;

	string N;
	rep(nth,Q)
	{
		cin >> N;
		string tmp=N;
		int count=0;
		while(true)
		{
			if(step1(N)){ cout << count << endl; break; }
			N = step2(N);
			if(N == tmp){ cout << -1 << endl; break; }
			tmp = N;
			count++;
		}
	}

	return 0;
}

Measured memory_bytes: 1256
#include <bits/stdc++.h>
using namespace std;
int n,x,y,st,timer,Size[100005],tin[100005],tout[100005],H[100005];
vector<int> g[100005],used;
void DFS(int v,int p,int h){
    used[v]=1;
    tin[v]=timer++;
    H[v]=h;
    Size[v]=H[v];
    for(int k=0;k<g[v].size();k++){
       int to=g[v][k];
       if(used[to]==0)
            DFS(to,v,h+1);
    }
    tout[v]=timer++;
    Size[p]=max(Size[p],Size[v]);
}
bool yes(int a,int b){
    if(tin[a]<=tin[b] && tout[a]>=tout[b])
        return true;
    return false;
}
int fin=0,ind=0;
void DFS2(int v){
    used[v]=1;
    if(v==st)
        ind=1;
    int to=0;
    for(int k=0;k<g[v].size();k++){
        if(ind && used[g[v][k]]==0 && Size[to]<Size[g[v][k]])
            to=g[v][k];
    if(ind==0){
        if(used[g[v][k]]==0 && yes(g[v][k],st))
            to=g[v][k];
    }
    }
    if(to==0)
        fin=v;
    else
    DFS2(to);
}
int main(){
cin>>n>>x>>y;
for(int k=1;k<n;k++){
    int a,b;
    cin>>a>>b;
    g[a].push_back(b);
    g[b].push_back(a);
}
used.resize(0);
used.resize(n+1,0);
DFS(y,0,0);
H[0]=INT_MAX;
st=x;
for(int k=1;k<=n;k++){
   if(yes(k,x) && H[k]>H[x]-H[k]){
    if(H[st]>H[k])
        st=k;
   }
}
Size[0]=0;
used.resize(0);
used.resize(n+1,0);
DFS2(y);
cout<<max(0,H[fin]-1);
return 0;
}


Measured memory_bytes: 14080
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL) ; cout.tie(NULL);
#define MOD 998244353

int dp[100005];
int vis[100005];
vector<int> adj[100005];

void dfs(int v)
{
    vis[v]=1;
    for(int i=0;i<adj[v].size();i++)
    {
    	if(!vis[adj[v][i]])
    		dfs(adj[v][i]);

    	dp[v]=max(dp[v],dp[adj[v][i]]+1);
    }
}

int main() 
{
    int n,m,i,x,y;
    cin>>n>>m;
    
    for(i=0;i<m;i++)
    {
       cin>>x>>y;
       adj[x].push_back(y);
    }
    
    for(i=1;i<=n;i++)
    {
      if(!vis[i])
      {
         dfs(i);
      }  
    }
    
    int ans=INT_MIN;
    
    for(i=1;i<=n;i++)
    {
    	ans=max(ans,dp[i]);
    }
    
    cout<<ans<<"\n";
 	return 0;
}

Measured memory_bytes: 8576
#pragma GCC optimize ("-O3")
#include <bits/stdc++.h>  
#include <complex>
#include <queue>
#include <set>
#include <unordered_set>
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <fstream>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
ll MOD = 998244353;
#define forn(i,e) for(ll i = 0; i < e; i++)
#define forsn(i,s,e) for(int i = s; i < e; i++)
#define rforn(i,s) for(ll i = s; i >= 0; i--)
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF 1e18
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
 
ll mpow(ll a, ll b){
	if(b >= (MOD-1)) b %= (MOD-1);
	if(b==0) return 1;
	ll t1 = mpow(a,b/2);
	t1 *= t1;
	t1 %= MOD;
	if(b%2) t1 *= a;
	t1 %= MOD;
	return t1;
}
 
ll mpow(ll a, ll b, ll p){
	if(b==0) return 1;
	ll t1 = mpow(a,b/2,p);
	t1 *= t1;
	t1 %= p;
	if(b%2) t1 *= a;
	t1 %= p;
	return t1;
}
 
ll modinverse(ll a, ll m){
	ll m0 = m; 
    ll y = 0, x = 1; 
    if (m == 1) return 0; 
    while (a > 1){
        ll q = a / m; 
        ll t = m; 
        m = a % m, a = t; 
        t = y; 
        y = x - q * y; 
        x = t; 
    }
    if (x < 0) x += m0; 
    return x; 
}
 
ll range(ll l, ll r){
	return l + rand()%(r-l+1);
}
 
ll rev(ll v){
	return mpow(v,MOD-2);
}
 
void solve(){
	ll n,m,v,p;
	cin >> n >> m >> v >> p;
	ll a[n];
	ll pr[n];
	forn(i,n) {
		cin >> a[i];
	}
	sort(a,a+n);
	forn(i,n) {
		if(!i) pr[i]=a[i];
		else pr[i]=pr[i-1]+a[i];
	}
	ll s = pr[n-p];
	ll ans=0;
	forn(i,n){
		ll nv = a[i]+m;
		ll rs = s-pr[i];
		if(i>=(n-p) || (nv >= a[n-p] && (p+i >= v || rs+(v-p-i)*m <= (n-p-i)*nv))) ans++;
	}
	cout << ans << ln;
}
 
int main()
{
	fast_cin();
    ll t=1;
    // cin>>t;
    forn(i,t) {
    	// cout << "Case #" << i+1 << ": ";
    	solve();
    }
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define pb push_back
#define sz(v) (v).size()
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define mp make_pair
#define inf 1000000007
#define mod 1000000007
using namespace std;
template <typename T> T Max(T x,T y){return x>y?x:y;}
template <typename T> T Min(T x,T y){return x<y?x:y;}
template <typename T> void chmax(T &x,T y){x=x>y?x:y;return;}
template <typename T> void chmin(T &x,T y){x=x<y?x:y;return;}

long long a,b,c,d;

int main()
{
	cin>>a>>b>>c>>d;
	cout<<Max(Max(a*c,b*d),Max(a*d,b*c))<<endl;
	return 0;
}

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

int main() {
  
  vector<vector<int>> vec(3, vector<int>(3));
  
  for(int i=0; i<3; i++){
      for(int j=0; j<3; j++){
          cin >> vec.at(i).at(j);
      }
  }
  
  bool tak = true;
  int s, t, comp;
  
  for(int j=1; j<3; j++){
      for(int i=0; i<3; i++){
          s = vec.at(i).at(j) - vec.at(i).at(j-1);
          if(i == 0){
             comp = s; 
         } else{
             if(comp - s != 0){
                 tak = false;
             }
         }
      }
  }
  
  for(int i=1; i<3; i++){
      for(int j=0; j<3; j++){
          t = vec.at(i).at(j) - vec.at(i-1).at(j);
          if(j == 0){
              comp = t; 
          } else {
              if(comp - t != 0){
                  tak = false;
              }
          }
      }
  }
  if(tak){
      cout << "Yes";
  } else{
      cout << "No";
  }
 

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
#define ALL(a) a, a+sizeof(a)/sizeof(a[0])
#define all(a) a.begin(),a.end()
using namespace std;
ll gcd(ll n, ll m) {
	if (m == 0) return n;
	return gcd(m, n % m);
}
ll lcm(ll n, ll m) {
	return m / gcd(n, m) * n;
}
//各桁の和を求める
ll dig_sum(ll num) {
	int dig, sum = 0;
	while (num) {
		dig = num % 10;
		sum = sum + dig;
		num = num / 10;
	}
	return sum;
}


int main(void) {
	int x, y;
	cin >> x >> y;
	cout << x+y+1-gcd(x,y) << endl;
	return 0;
}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ld = long double;
const int INF = 1 << 29;
const ll LINF = 1l << 61;
const ld PI = abs(acos(-1));
#define pq priotity_queue
#define mp make_pair
#define P pair
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define rrep(i, a, b) for (ll i = a; i >= b; i--)
#define cbuf(buf, init) memset(buf, init, sizeof(buf))
#define modp(x, y) (((y) + (x) % (y)) % (y))
#define divd(x, y) (static_cast<double>(x) / static_cast<double>(y))

string s;
ll x, y;
ll a[30000], b[30000], dpa[30000], dpb[30000];
ll dpa2[30000], dpb2[30000];
ll A, B;

int main()
{
    //
    cin >> s;
    cin >> x >> y;

    bool isa = true;
    ll j = 0;
    rep(i, 0, s.size())
    {
        if (s[i] == 'F') {
            if (isa)
                a[j]++;
            else
                b[j]++;
        }
        else {
            isa = isa ? false : true;
            if (isa) j++;
        }
    }
    j++;

    dpa[10000] = 1;
    rep(i, 0, j)
    {
        rep(k, -10000, 10000)
        {
            if (dpa[10000 + k - a[i]])
                dpa2[10000 + k] = 1;
            else if (i != 0 && dpa[10000 + k + a[i]])
                dpa2[10000 + k] = 1;
            else
                dpa2[10000 + k] = 0;
        }
        rep(k, -10000, 10000) dpa[10000 + k] = dpa2[10000 + k];
    }

    dpb[10000] = 1;
    rep(i, 0, (isa ? j - 1 : j))
    {
        rep(k, -10000, 10000)
        {
            if (dpb[10000 + k - b[i]])
                dpb2[10000 + k] = 1;
            else if (dpb[10000 + k + b[i]])
                dpb2[10000 + k] = 1;
            else
                dpb2[10000 + k] = 0;
        }
        rep(k, -10000, 10000) dpb[10000 + k] = dpb2[10000 + k];
    }
    cout << (dpa[10000 + x] && dpb[10000 + y] ? "Yes" : "No") << endl;
}


Measured memory_bytes: 896
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
using namespace std;

int main()
{
    int k,n;
    cin >> k >> n;
    int m = 0;
    int prev = 0;
    int a0 = 0;
    for(int i=0; i<n; i++){
        int a;
        cin >> a;
        if(i == 0){
            a0 = a;
        }else{
            m = max(m, a-prev);
        }
        prev = a;
    }
    m = max(m, k-prev + a0);
    cout << k-m << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<bitset>
#include<random>
#include<time.h>
#define INF 1000000000ll
#define MOD 1000000007ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<(ll)m; i++)
#define FOR(i,n,m) for(long long i=n; i<(ll)m; i++)
#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=(ll)a.size()-1) cout<<" "; else cout<<endl; }
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v) sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef long double ld;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n,a,b;
	cin>>n>>a>>b;
	vector<ll> t(n);
	REP(i,n) cin>>t[i];
	ll ans=n;
	sort(ALL(t));
	REP(i,n) if(t[i]>=a&&t[i]<b) ans--;
	cout<<ans<<endl;
}


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

int main() {
    int a,b;
    int days[12]={31,28,31,30,31,30,31,31,30,31,30,31};
    cin>>a>>b;
    if(days[a-1]==days[b-1]){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <set>
#define rep(i,n) for (int i=0; i < (n); ++i)
#define all(a) a.begin(), a.end()
using ll = long long;
using namespace std;
 
// ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }


// const double PI = acos(-1);


int main() {
  int N,T; cin >> N >> T;
  
  vector<int> c(N), t(N);
  rep(i,N) cin >> c[i] >> t[i];

  vector<int> c_empty;
  int ans=0;
  rep(i,N) {
    if (T >= t[i]) {
      c_empty.push_back(c[i]);
      ans++;
    }
  }
  if (ans ==0){
    cout << "TLE" << endl;
    return 0;
  }
      
  int c_min = c_empty[0];
  rep(i,c_empty.size()) {

    if (c_min > c_empty[i]) {
      c_min = c_empty[i];
    }

  }
  cout << c_min << endl;
  return 0;

 
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(void)
{
  char n[200],tmp;
  int i,j,k,m,num,h;
  while(1)
  {
    scanf("%s",n);
    if(n[0]=='-')
     break;
    num=strlen(n);
  //  printf("m:");
    scanf("%d",&m);

    for(i=0;i<m;i++)
    {
    //  printf("h:");
      scanf("%d",&h);
      for(k=0;k<h;k++)
      {
        tmp=n[0];
        for(j=0;j<num;j++)
        {
          n[j]=n[j+1];
        }
        n[num-1]=tmp;
      }
    }
    printf("%s\n",n);
  }
  return 0;
}



Measured memory_bytes: 2096
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

n = k()
L = I()
p = sorted(L)
for i in range(n):
    for j in range(i+1,n):
        ans += bisect.bisect_left(p,p[i]+p[j])-(j+1)

print(ans)


Measured memory_bytes: 10608
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mm=1000000007;
struct data{
	int l,x,next;
}g[1111];
int tot,i,j,k,n,m,f[311][311][311],h[311],v[311][311][311],tmp,ans;
void adddata(int l,int r,int x){
	g[++tot].l=l;g[tot].x=x;g[tot].next=h[r];h[r]=tot;
}
int check(int x,int a,int b){
	int i,j,k;
	for (i=h[x];i;i=g[i].next){
		j=g[i].l;k=1;
		if (j<=b) k++;
		if (j<=a) k++;
		if (k!=g[i].x) return 0;
	}
	return 1;
}
void update(int x,int a,int b,int w){
	if (!v[x][a][b]) return;
	f[x][a][b]=(f[x][a][b]+w)%mm;
}
int main(){
	scanf("%d%d",&n,&m);memset(f,0,sizeof(f));memset(v,0,sizeof(v));f[0][0][0]=1;
	for (i=1;i<=m;i++) scanf("%d%d%d",&j,&k,&tmp),adddata(j,k,tmp);
	for (i=1;i<=n;i++)
	 for (j=0;j<i;j++)
	  for (k=((j==0)?0:j+1);k<i;k++) v[i][j][k]=check(i,j,k);
	for (i=0;i<=n;i++)
	 for (j=0;j<=i;j++)
	  for (k=((j==0)?0:j+1);k<=i;k++)
	   if (f[i][j][k]){
	   	update(i+1,j,k,f[i][j][k]);
	   	update(i+1,j,i,f[i][j][k]);
	   	update(i+1,k,i,f[i][j][k]);
	   }
	for (ans=0,i=0;i<n;i++)
	 for (j=((i==0)?0:i+1);j<n;j++)
	  if (v[n][i][j])ans=(ans+f[n][i][j])%mm;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 235136
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        double b=0; 
        double sum=0;
        for(int i=0; i<a;i++){
            b=sc.nextDouble();
            sum+=1/b;
        }
        System.out.println(1/sum);
    }
    
}


Measured memory_bytes: 23124
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);
	static int N;
	static int[] P, id, W;
	static ArrayList<ArrayList<Integer>> loop;
	static int MOD = 100000007;
	static double EPS = 1e-8;

	public static void main(String[] args) throws Exception {
		while (true) {
			N = sc.nextInt();
			if (N == 0) break;
			P = new int[N];
			id = new int[N];
			W = new int[N];
			for (int i = 0; i < N; ++i) {
				P[i] = nextP();
				id[i] = sc.nextInt();
				W[i] = nextP();
			}
			loop = new ArrayList<ArrayList<Integer>>();
			boolean[] used = new boolean[N];
			for (int i = 0; i < N; ++i) {
				if (used[i]) continue;
				int pos = i;
				ArrayList<Integer> chain = new ArrayList<Integer>();
				while (!used[pos]) {
					chain.add(pos);
					used[pos] = true;
					pos = id[pos];
				}
				loop.add(chain);
			}
			solve();
		}
	}

	static void solve() {
		long combination = 1;
		double exp = 0;
		for (ArrayList<Integer> chain : loop) {
			int count = 0;
			double all = 0;
			for (int i = 0; i < chain.size(); ++i) {
				all += time(W[chain.get(i)]);
			}
			double min = Double.MAX_VALUE;
			for (int i = 0; i < chain.size(); ++i) {
				double v = all - time(W[chain.get(i)]) + time(P[chain.get(i)]);
				if (v < min - EPS) {
					min = v;
					count = 1;
				} else if (v < min + EPS) {
					++count;
				}
			}
			exp += min;
			combination *= count;
			combination %= MOD;
		}
		BigInteger comb = BigInteger.ONE;
		for (int i = 1; i <= N; ++i) {
			comb = comb.multiply(BigInteger.valueOf(i));
		}
		for (ArrayList<Integer> chain : loop) {
			for (int i = 1; i <= chain.size(); ++i) {
				comb = comb.divide(BigInteger.valueOf(i));
			}
		}
		comb = comb.remainder(BigInteger.valueOf(MOD));
		System.out.println(exp + " " + (comb.longValue() * combination % MOD));
	}

	static double time(int p) {
		return 1000.0 / p;
	}

	static int nextP() {
		return Integer.parseInt(sc.next().replaceAll("\\.", ""));
	}

}

Measured memory_bytes: 13000
#include<iostream>
#include <list>
#include<stack>
#include<queue>
#include <vector>
#include <set>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include <functional>
using namespace std;

#define FOR(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define LL long long
#define CLR(a) memset((a),0,sizeof(a))
#define SZ(x) (int((x).size()))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl
const LL INF = 4000000000000000000;

//毎回変える定数
#define N_MAX 200


//変数
int N, K;
vector<vector<LL>> xy;


//サブ関数
//入力
void input() {
	cin >> N >> K;
	REP(i, N) {
		LL tmp;
		vector<LL> tmpv;
		REP(j, 2) {
			cin >> tmp;
			tmpv.push_back(tmp);
		}
		xy.push_back(tmpv);
	}
}


LL judge(LL minX, LL minY, LL maxX, LL maxY) {
	int count = 0;
	for (auto p : xy) {
		if (minX <= p[0] && p[0] <= maxX && minY <= p[1] && p[1] <= maxY) {
			count++;
		}
	}
	if (count >= K)return (maxX - minX)*(maxY - minY);
	else return INF;
}

//辺集合の生成する長方形の四辺を計算
LL calc(vector<vector<LL>> edges) {
	LL minX = INF;
	LL minY = INF;
	LL maxX = -INF;
	LL maxY = -INF;
	for (auto edge : edges) {
		if (edge[0] < minX)minX = edge[0];
		if (edge[0] > maxX)maxX = edge[0];
		if (edge[1] < minY)minY = edge[1];
		if (edge[1] > maxY)maxY = edge[1];
	}
	return judge(minX, minY, maxX, maxY);
}


//辺集合を作って、計算に回す
LL produceEdges(vector<vector<LL>> edges, int last) {
	if (edges.size() == min(4, K)) {
		return calc(edges);
	}
	LL ans = INF;
	FOR(i, last, N) {
		edges.push_back(xy[i]);
		ans = min(ans, produceEdges(edges, i + 1));
		edges.pop_back();
	}
	return ans;
}


//出力
void output() {
	DEBUGING(produceEdges(vector<vector<LL>>(), 0));
}

//デバッグ
void debug() {
	int N;
	cin >> N;
}


//メイン関数
int main() {

	input();
	output();
	debug();

	return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <iostream>
#include <string>
#include <stdexcept>
#include <algorithm>
#include <vector>
#include <functional>
#include <time.h>

using namespace std;


int main() {

	string s, t;
	int Ans = 0;
	cin >> s >> t;

	for (int i = 0; i < 3; i++) {
		if (s.substr(i, 1) == t.substr(i, 1)) {
			Ans++;
		}
	}

	cout << Ans << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[200100];
int main(){
	int n;
	cin >> n;
	int min = 0x3f3f3f3f;
	int ans = 0;
	for(int i = 1; i <= n; i++){
		scanf("%d",&a[i]);
		if(a[i] <= min){
			min = a[i];
			ans++;
		}
	}	
	cout << ans<< endl;
	return 0;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
#define int long long

using namespace std;

signed main() {
    int H, W;
    cin >> H >> W;
    if( H == 1 || W == 1)
    {
        cout << 1 << endl;
        return 0;
    }
    int ans = (H * W + 1) / 2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> T gcd(T a, T b){return !b?a:gcd(b,a%b);}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
ll n,a,b;

int main() {
	read(n);read(a);read(b);
	if(a>b)swap(a,b);
	if((b-a)%2==0)cout<<(b-a)/2;
	else cout<<min(a-1+1+(b-a)/2,n-b+1+(b-a)/2);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int a;
  int i;
  int numbers[100001] = {};
  int wa = 0;
  for(i=0;i<n;i++){
    a = 0;
    cin >> a;
    if(a>100000) wa++;
    else{
      numbers[a]++;
    }
  }
  for(i=1;i<=100000;i++){
    if(numbers[i]<i) wa+=numbers[i];
    else wa+=numbers[i]-i;
  }
  cout << wa;

  
}

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

typedef long long int ll;


int main()
{
    string sa, sb, sc;
    cin >> sa >> sb >> sc;
    ll ac = 0, bc = 0, cc = 0, t = 0;
    while(1){
        if(t == 0){
            if(sa.empty()){
                break;
            }
            if(sa[ac] == 'a'){
                t = 0;
            }
            else if(sa[ac] == 'b'){
                t = 1;
            }
            else if(sa[ac] == 'c'){
                t = 2;
            }
            sa.erase(sa.begin());
        }
        else if(t == 1){
            if(sb.empty()){
                break;
            }
            if(sb[bc] == 'a'){
                t = 0;
            }
            else if(sb[bc] == 'b'){
                t = 1;
            }
            else if(sb[bc] == 'c'){
                t = 2;
            }
            sb.erase(sb.begin());
        }
        else{
            if(sc.empty()){
                break;
            }
            if(sc[cc] == 'a'){
                t = 0;
            }
            else if(sc[cc] == 'b'){
                t = 1;
            }
            else if(sc[cc] = 'c'){
                t = 2;
            }
            sc.erase(sc.begin());
        }
    }

    if(t == 0){
        cout << 'A';
    }
    else if(t == 1){
        cout << 'B';
    }
    else{
        cout << 'C';
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using ll = long long;
#define ull unsigned ll
#define endl "\n"
#define vi vector<int>
#define vl vector<ll>
#define all(v) (v).begin(),(v).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pi pair<int,int>
#define pl pair<ll,ll>
#define ppi pair<int, pii>
#define mt make_tuple
#define eb emplace_back
using namespace std;

const ll N = 1e5 + 5, mod = 1e9 + 7;
const ll inf = 1e9;

bool cmp(const pair<ll, ll> &a, const pair<ll, ll> &b){
    if(a.F == b.F) return a.S < b.S;
    return a.F > b.F;
}

void solve(){
    int n;
    cin >> n;
    vi a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    ll ans = 1000, stock = 0;
    for(int i = 1; i < n; i++){
        while(i < n && a[i] <= a[i - 1]) i++;
        if(i == n) break;
        stock = ans / a[i - 1];
        ans %= a[i - 1];
        while(i < n && a[i] >= a[i - 1]) i++;
        i--;
        ans += stock * a[i];
    }
    cout << ans << endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);//cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ll t,p;
    t=1;
    //cin>>t;
    for(p=1;p<=t;p++){
        solve();
    }
    return 0;
}


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

class Program
{
	static void Main()
	{
		var s = Console.ReadLine();

		var answer = default(int?);
		for (var i = s.Length - 1; i > 0 && answer.HasValue == false; --i) {
			if (i % 2 == 0) {
				var num = i / 2;
				if (s.Substring(0, num) == s.Substring(num, num)) {
					answer = i;
				}
			}
		}

		Console.WriteLine(answer.Value);
	}
}


Measured memory_bytes: 11092