akhauriyash/Code-Regression huggingface dataset:
var lines = [];
var reader = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
});
reader.on('line', (line) => {
    lines.push(line);
});
reader.on('close', () => {
    l = lines[0].split(' ');
    var a, b, t
    a = parseInt(l[0]);
    b = parseInt(l[1]);
    t = parseInt(l[2]);
    console.log(Math.floor(t / a) * b);
});

Measured memory_bytes: 21320
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main()
{
	int N;
	std::vector<int> L;

	std::cin >> N;
	L.resize(N);
	for (int i = 0; i < N; i++)
	{
		std::cin >> L[i];
	}

	std::sort(L.begin(), L.end());

	int answer = 0;
	for (int i = 0; i < L.size(); i++)
	{
		for (int j = i + 1; j < L.size(); j++)
		{
			if (L[i] == L[j])
			{
				continue;
			}

			for (int k = j + 1; k < L.size(); k++)
			{
				if (L[j] == L[k])
				{
					continue;
				}

				if (L[i] + L[j] > L[k])
				{
					answer++;
				}
			}
		}
	}

	std::cout << answer;

	return 0;
}


Measured memory_bytes: 3656
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main() {
    IOS; int k,a,b; cin>>k>>a>>b;
    if(a/k!=b/k || (a%k==0)||(b%k==0)) cout << "OK";
    else cout << "NG";
    return 0;
}


Measured memory_bytes: 3664
class UnionFind():
    #ｎは頂点数
    def __init__(self, n):
        self.parent = [-1]*n

    #aの属する集合の根を取得
    def root(self,a):
        if self.parent[a] < 0:return a
        self.parent[a] = self.root(self.parent[a])
        return self.parent[a]
    
    #aの属する集合の要素数を取得
    def size(self,a):
        return -self.parent[self.root(a)]

    #aとbをくっつける
    def connect(self,a,b):
        if self.root(a) == self.root(b):return False
        a = self.root(a);b = self.root(b)
        if self.size(a) < self.size(b):a,b = b,a
        self.parent[a] += self.parent[b]
        self.parent[b] = a
        return True

n,m = map(int,input().split())
uni = UnionFind(n)
for i in range(m):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    uni.connect(x,y)
ans = 0
for i in uni.parent:
    if i < 0:
        ans += 1
print(ans)

Measured memory_bytes: 80044
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[3];
signed main(){
    cin>>a[0]>>a[1]>>a[2];
    sort(a,a+3);
    int ans=a[0]*a[1]/2;
    cout<<ans<<endl;
    return 0;
}
    

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
ll dp[110][4][4][4][4];

int main(){
  ll n;
  cin >> n;
  dp[0][3][3][3][3]=1;
  for(ll i=1;i<=n;i++){
    for(ll j=0;j<4;j++){
      for(ll k=0;k<4;k++){
        for(ll l=0;l<4;l++){
          for(ll m=0;m<4;m++){
            if(k==0&&l==1&&m==2||k==0&&l==2&&m==1||k==1&&l==0&&m==2||j==0&&k==1&&m==2||j==0&&l==1&&m==2){
              dp[i][j][k][l][m]=0;
            }
            else{
              for(ll x=0;x<4;x++) dp[i][j][k][l][m]+=dp[i-1][x][j][k][l];
              dp[i][j][k][l][m]%=mod;
            }
          }
        }
      }
    }
  }
  ll ans=0;
  for(ll j=0;j<4;j++){
    for(ll k=0;k<4;k++){
      for(ll l=0;l<4;l++){
        for(ll m=0;m<4;m++){
          ans+=dp[n][j][k][l][m];
          ans%=mod;
        }
      }
    }
  }
  cout << ans << endl;
}          

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define maxn -20000000000 //negative value to break code and force you to put right constraint
#define mod 1000000007
#define md(x) (x) % mod;
#define sc scanf
#define pr printf
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ps push
#define prt(x) cout << (#x) << " is " << (x) << endl
#define EPS 1e-9
#define INF 1e16
#define INFd 1e9
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<double> vd;

string s;
ll n;
ll best(ll prev,ll ind,ll num)
{
	ll n1=0;
	if((ind+1)>=(n))
	{
		for(ll i=prev;i<=ind;i++)
		n1=n1*10+s[i]-'0';
		return n1+num;
	}
	ll res=0;
	
	for(ll i=prev;i<=ind;i++)
		n1=n1*10+s[i]-'0';
	res=best(ind+1,ind+1,num+n1);
	res+=best(prev,ind+1,num);
//	cout<<res<<endl;
	return res;
}

int main()
{
	
	cin>>s;
	n=s.length();
	cout<<best(0,0,0);
	
}



Measured memory_bytes: 256
n = int(input())
alist = list(sorted(map(int, input().split())))
maxa = alist[-1]
halfa = maxa / 2
mina = maxa
a2 = 0
for a in alist:
  if abs(halfa - a2) > abs(halfa - a):
    a2 = a
print(maxa, a2)


Measured memory_bytes: 14052
package main

import "fmt"

func main() {
	var a, b int
	fmt.Scanf("%d %d", &a, &b)
	fmt.Printf("%d\n", lcm(a, b))
}

func gcd(a int, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func lcm(a int, b int) int {
	return int(a * b / gcd(a, b))
}


Measured memory_bytes: 512
#include <iostream>
using namespace std;
int a[26];
int main() {
    string b;
    int i;
    bool flag=true;
    cin>>b;
    for(i=0;i<b.size();i++)
    {
    	switch(b[i])
    	{
    		case 'a': a[0]++; break; 
    		case 'b': a[1]++; break;
    		case 'c': a[2]++; break;
    		case 'd': a[3]++; break;
    		case 'e': a[4]++; break;
    		case 'f': a[5]++; break;
    		case 'g': a[6]++; break;
    		case 'h': a[7]++; break;
    		case 'i': a[8]++; break;
    		case 'j': a[9]++; break;
    		case 'k': a[10]++; break;
    		case 'l': a[11]++; break;
    		case 'm': a[12]++; break;
    		case 'n': a[13]++; break;
    		case 'o': a[14]++; break;
    		case 'p': a[15]++; break;
    		case 'q': a[16]++; break;
    		case 'r': a[17]++; break;
    		case 's': a[18]++; break;
    		case 't': a[19]++; break;
    		case 'u': a[20]++; break;
    		case 'v': a[21]++; break;
    		case 'w': a[22]++; break;
    		case 'x': a[23]++; break;
    		case 'y': a[24]++; break;
    		case 'z': a[25]++; break;
		}
    	
	}
	for(i=0;i<=25;i++)
	{
		if(a[i]%2!=0) flag=false;
	}
	if(flag==true) cout<<"Yes";
	else cout<<"No";
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
char a[maxn];
int n,p,x,t=1;
ll ans,cnt[maxn];
int main(){
    scanf("%d %d %s",&n,&p,a);
    if(p==2||p==5){
        for(int i=0;i<n;i++){
            if((a[i]-'0')%p==0){
                ans=ans+i+1;
            }
        }
    }else{
        cnt[0]=1;//这个特判一下
        for(int i=n-1;i>=0;i--){
            x=(x+(a[i]-'0')*t)%p;
            ans=ans+cnt[x];
            cnt[x]++;
            t=t*10%p;
//            printf("%d %lld\n",x,cnt[x]);
        }
    }
    printf("%lld",ans);
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int mo=998244353;
const int N=1e6;
int n,ans,a[N+10];
bool p[N+10];
int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    ans=a[1]%mo;
    a[1]=1;
    memset(p,1,sizeof(p));
    p[1]=0;
    for (int i=2;i<n;i++) {
        if (!p[i]) continue;
        for (int j=i*2;j<n;j+=i) p[j]=0;
        for (int j=i;j<n;j+=i) {
            int x=j,y=a[j+1];
            while (x%i==0&&y%i==0) {
                x/=i;
                y/=i;
                ans=(long long)ans*i%mo;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 1664
n = gets.to_i
sum = 0
ba_sum = 0
b_sum = 0
a_sum = 0
for i in 0...n do
  s = gets.chomp
  b = (s[0] == "B")
  a = (s[-1] == "A")
  if b && a
    ba_sum += 1
  elsif b
    b_sum += 1
  elsif a
    a_sum += 1
  end
  cnt = 0
  while !s.sub!(/AB/, "--").nil?
    cnt += 1
  end
  sum += cnt
end
if ba_sum >= 1
  sum += ba_sum - 1
  if b_sum >= 1
    sum += 1
    b_sum -= 1
  end
  if a_sum >= 1
    sum += 1
    a_sum -= 1
  end
end
sum += (b_sum < a_sum) ? b_sum : a_sum
puts sum


Measured memory_bytes: 1788
import sys

n, y = map(int, input().split())

count = 0
for i in range(n+1):
    if i < n+1:
        for j in range(n-i+1):
            if y == 10000*i+5000*j+1000*(n-i-j):
                print("{i} {j} {k}".format(i=i,j=j,k=n-i-j))
                sys.exit()

print("{i} {j} {k}".format(i=-1,j=-1,k=-1))

Measured memory_bytes: 41324
'use strict'

function main(s) {

  s = s.split('\n')[0].split(' ').map(n => Number(n));
  const A = s[0];
  const B = s[1];
  const C = s[2];
  const D = s[3];

  const lower = Math.max(A, C);
  const upper = Math.min(B, D);

  const answer = Math.max(0, upper - lower);
  console.log(answer);
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

int main(void)
{
  int a, b, c, k;
  cin >> a >> b >> c >> k;
  int ans = 0;
  if (k <= a) {
    ans = k;
  } else if (k<=a+b) {
    ans = a;
  } else {
    ans = a - (k-a-b);
  }
  cout << ans << endl;
  

  
  return 0;
}


Measured memory_bytes: 3632
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
#ifndef LOCAL
#define cerr if(0)cout
#endif
typedef long long ll;
const int mod=1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it,len;
	fastio(){it=len=0;}
	inline char get()
	{
		if(it<len)return s[it++];it=0;
		len=fread(s,1,100000,stdin);
		if(len==0)return EOF;else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while(c==' '||c=='\n')c=get();
		if(it>0)it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0;bool ng=0;char c;c=_buff.get();
	while(c!='-'&&(c<'0'||c>'9'))c=_buff.get();
	if(c=='-')ng=1,c=_buff.get();
	while(c>='0'&&c<='9')r=r*10+c-'0',c=_buff.get();
	return ng?-r:r;
}
template<class T> inline void putnum(T x)
{
	if(x<0)putchar('-'),x=-x;
	register short a[20]={},sz=0;
	while(x)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1;i>=0;i--)putchar('0'+a[i]);
}
inline char getreal(){char c=_buff.get();while(c<=32)c=_buff.get();return c;}
ll qpow(ll x,ll k){return k==0?1:1ll*qpow(1ll*x*x%mod,k>>1)*(k&1?x:1)%mod;}
int T;
ll A,B,C,D;
bool solve()
{
	A-=B;
	if(A<0)return false;
	if(D<B)return false;
	ll l=C+1,r=B-1;
	if(l>r)return true;
	A%=B;
	ll g=__gcd(D,B);
	ll lst=B-g+A%g;
	return lst<l;
}
int main()
{
	geti(T);
	while(T--)
	{
		getii(A,B);
		getii(C,D);
		if(solve())puts("Yes");
		else puts("No");
	}
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
static const int MAX=100;
static const int INFTY=(1<<21);
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;

int n,M[MAX][MAX];

int prim(){
    int u,minv;
    int d[MAX],p[MAX],color[MAX];
    
    for(int i=0;i<n;i++){
        d[i]=INFTY;
        p[i]=-1;
        color[i]=WHITE;
    }
    
    d[0]=0;
    
    while(true){
        minv=INFTY;
        u=-1;
        for(int i=0;i<n;i++){
            if(minv>d[i]&&color[i]!=BLACK){
                u=i;
                minv=d[i];
            }
        }
        if(u==-1)break;
        color[u]=BLACK;
        for(int v=0;v<n;v++){
            if(color[v]!=BLACK&&M[u][v]!=INFTY){
                if(M[u][v]<d[v]){
                    d[v]=M[u][v];
                    p[v]=u;
                    color[v]=GRAY;
                }
            }
        }
    }
    int sum=0;
    for(int i=0;i<n;i++){
        if(p[i]!=-1) sum+=M[i][p[i]];
    }
    
    return sum;
}

int main(){
    cin>>n;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int b;cin>>b;
            M[i][j]=(b==-1)? INFTY:b;
        }
    }
    
    cout << prim() << endl;
    
    return 0;
}


Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
int main() {
	int a, b, c;
	cin >> a >> b >> c;
	int x = a, y = b, z = c, count = 0;
	while(x % 2 == 0 && y % 2 == 0 && z % 2 == 0) {
		int o, p, q;
		o = y / 2 + z / 2;
		p = x / 2 + z / 2;
		q = x / 2 + y / 2;
		count++;
		if(a == o && b == p && c == q) {
			count = -1;
			break;
		}
		x = o;
		y = p;
		z = q;
	}


	cout << count << endl;

	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<char>C(N);
	for (int i = 0; i < N; i++) {
		cin >> C.at(i);
		if (C.at(i) == 'Y') {
			cout << "Four" << endl;
			return 0;
		}
	}
	cout << "Three" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
  int R,G,B,N;
  cin >> R >> G >> B >> N;
  
  int r_lim = N / R;
  
  int ans = 0;
  
  for(int i=0;i<=r_lim;i++){
    int g_lim = (N - R * i) / G;
    for(int j=0;j<=g_lim;j++){
      if((N - R * i - G * j) % B == 0)
        ans++;
    }
  }
  
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;

class B {
    public static void main(String... args) {
        final Scanner sc = new Scanner(System.in);
        final int D = sc.nextInt();
        final int N = sc.nextInt();
        final int base = new int[]{1, 100, 10000}[D];
        System.out.println(base * (N < 100 ? N : 101));
    }
}
public class Main {
    public static void main(String...args) {
        B.main();
    }
}

Measured memory_bytes: 23636
#include<stdio.h>

int main(){
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    if(a<b && b<c){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    return 0;
}


Measured memory_bytes: 1920
#include<iostream>
#include<string>
using namespace std;
int main()
{
	int c,i,j,k,l,n,ans=0;
	cin >> n;
	string s;
	cin >> s;
	
	int num[n+10];
	for (i=0;i<n;i++){
		num[i]=(int)(s[i]-'0');
	}
	
	for (i=0;i<=9;i++){
		for (j=0;j<=9;j++){
			for (k=0;k<=9;k++){
				c=0;
				for (l=0;l<n;l++){
					if (num[l]==k && c==2) c++;
					if (num[l]==j && c==1) c++;
					if (num[l]==i && c==0) c++;
				}
				ans+=(c==3);
			}
		}
	}
	
	cout << ans << endl;
	return 0;
}

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

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

typedef long long ll;
typedef long double ld;

const int INF = 1e9;
const ld EPS = 1e-8;

int main(){
  int N, K;
  cin >> N >> K;
  vector<int> D(K);
  REP(i,K) cin >> D[i];

  for(int i = N; i < 1000000; ++i) {
    string tmp = to_string(i);
    bool flag = true;
    for(char c: tmp) {
      REP(j,K) if(c - '0' == D[j]) flag = false;
    }
    if(flag) {
      cout << i << endl;
      break;
    }
  }
  return 0;
}



Measured memory_bytes: 256
import java.io.*;
import java.math.*;
import java.util.*;
 
public class Main {
	static final long MOD = 1000000007L;
	static final int INF = 50000000;
	
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		
		int N = sc.ni();
		int X = sc.ni();
		int Y = (N+X-1)/X;
		int T = sc.ni();
		pw.println(Y*T);
		
		pw.close();
	}

    static class FastScanner { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastScanner() { 
            br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
  
        String next() { 
            while (st == null || !st.hasMoreElements()) { 
                try { 
                    st = new StringTokenizer(br.readLine());
                } catch (IOException  e) { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        }
        
        int ni() { 
            return Integer.parseInt(next()); 
        }
  
        long nl() { 
            return Long.parseLong(next()); 
        } 
  
        double nd() { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() {
            String str = ""; 
            try { 
                str = br.readLine(); 
            } catch (IOException e) {
                e.printStackTrace(); 
            } 
            return str;
        }
    }
}

Measured memory_bytes: 33048
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define B begin()
#define E end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> VL;
typedef set<ll> SL;
typedef pair<ll, ll> p2;
const ll M = 1000000007;
const ll M2= 998244353;

void solve()
{
	ll x, n;cin>>x>>n;
	set<ll> s;
	for(int i=0, t;i<n;i++)cin>>t, s.insert(t);
	ll l=x, r=x;
	while(1)
	{
		if(s.find(l)==s.end())
		{
			cout<<l<<endl;
			return;
		}
		if(s.find(r)==s.end())
		{
			cout<<r<< endl;
			return;
		}
		l--;
		r++;
	}
}
 
int main()
{
    IOS
    int _=1;
    //cin>>_;
    while(_--)
    {
	    solve();
    }
    
    return 0;
}


Measured memory_bytes: 3640
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int main(){
  int a,b;
  cin>>a>>b;
  if(a*b%2==0) cout<<"Even"<<endl;
  else cout<<"Odd"<<endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
//hungcung
using namespace std;
#define int long long 
int H,W,N,a,b;
set< pair<int,int> > brd;
int dem[15];
signed main(){

	cin>>H>>W>>N;
	dem[0]=(H-2)*(W-2);
	while(N--)
	{
		cin>>a>>b;
		a--;b--;
		brd.insert({a,b});
		for(int x=max((int)0,a-2);x<=min(H-3,a);x++)
		{
			for(int y=max((int)0,b-2);y<=min(W-3,b);y++)
			{
				int cnt=0;
				for(int i=x;i<=x+2;i++)
				{
					for(int j=y;j<=y+2;j++)
					{
						if(brd.count({i,j})) cnt++;
					}
				}
				dem[cnt]++;
				dem[cnt-1]--;
			}
		}
	}
	for(int i=0;i<=9;i++)
	{
		cout<<dem[i]<<endl;
	}
	
	
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
#define ss second
#define ff first
#define all(x) x.begin(), x.end()
#define DEBUG

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

const int oo = 1e9 + 7;
const ll mod = 998244353, maxn = 200200;
const double PI = acos(-1);

bool check(ll n, ll d){
    while(n%d == 0) n/=d;
    return n%d == 1;
}

int main (){
    ll n;

    cin >> n;

    set<ll> ans;
    ans.insert(n);
    if (n != 2) ans.insert(n-1);
    for (ll i=2; i*i<=n; i++){
        ll d, nn = n-1;
        if (n%i == 0){
            d = n/i;
            if (check(n, d)) ans.insert(d);
            if (check(n, i)) ans.insert(i);
        }
        else if (nn % i == 0){
            d = nn/i;
            ans.insert(d);
            ans.insert(i);
        }
    }

    cout << ans.size() << endl;
    return 0;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fi first
#define se second
using Graph=vector<vector<int>>;
using P=pair<int,int>;
#define mp make_pair

void dfs(int u,int v,Graph graph,Graph &d,int flag)
{
	int h,w;
	h=graph.size();
	w=graph[0].size();
	int n=graph.size();
	d[u][v]=flag;
	vector<P> around={mp(u-1,v),mp(u+1,v),mp(u-1,v-1),mp(u-1,v+1),mp(u,v+1),mp(u,v-1),mp(u+1,v+1),mp(u+1,v-1)};
	for (int i=0;i<8;i++)
	{
		int x=around[i].fi,y=around[i].se;
		if (0<=x&&x<h && 0<=y&&y<w)
		{
			if (graph[x][y]==1 && d[x][y]==-1)
			{
				//cout << x << y << endl;
				dfs(x,y,graph,d,flag);
			}

		}
	}
}

int main()
{
	vector<int> ans;
	while (true)
	{
		int w,h;cin >> h >> w;
		if (w==0 && h==0) break;
		Graph graph(w,vector<int> (h,0)),d(w,vector<int> (h,0));
		for (int i=0;i<w;i++)
		{
			for (int j=0;j<h;j++)
			{
				cin >> graph[i][j];
				if (graph[i][j]==1) d[i][j]=-1;
			}
		}
		int flag=1;
		for (int i=0;i<w;i++)
		{
			for (int j=0;j<h;j++)
			{
				if (d[i][j]==-1)
				{
					dfs(i,j,graph,d,flag);
					flag++;
				}
			}
		}
		ans.push_back(flag-1);
	}
	for (int i=0;i<ans.size();i++) cout << ans[i] << endl;
	return 0;
}


Measured memory_bytes: 28776
N = int(input())
A = [int(x) for x in input().split()]
mark = 1
ans = N
pena = 1
for i in range(N):
    if A[i] == mark:
        pena = 0
        mark += 1
        ans -= 1
if pena == 1:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 25768
// :)
// "Khodaya, be man "Tagwaye setiz" biamooz ta
//  dar anbuh masuliat nalaghzam ..." -Shariati
#include <bits/stdc++.h>

using namespace std;
typedef long long int64;
typedef pair<int,int> pii;
typedef pair<int64,int64> pii64;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const int maxn = 1e5+7;
const int64 MO = 1e9+7;
const int64 IN = 1e9;

vector <int> g[maxn], gg[maxn];

int fin[maxn];
bool vis[maxn];

int N, M, cur = 0;

void dfs (int v) {
	vis[v] = true;
	for (auto u : g[v])
		if (!vis[u])
			dfs(u);
	fin[v] = cur++;
	return;
}


int main () {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	// 
	cin >> N >> M;
	for (int i = 0; i < N - 1 + M; i++) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		g[v].PB( u );
		gg[u].PB( v );
	}
	//
	int root;
	for (int i = 0; i < N; i++)
		if (gg[i].size() == 0) {
			root = i;
			dfs(root);
		}
	//
	for (int i = 0; i < N; i++) {
		if (i == root) {
			cout << 0 << "\n";
			continue;
		}
		int mnid = gg[i][0];
		for (auto u : gg[i])
			if (fin[u] < fin[mnid])
				mnid = u;
		cout << mnid + 1 << "\n";
	}
}



Measured memory_bytes: 15360
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mst(a,b) memset(a,b,sizeof(a))
#define lowbit(x) ((x)&(-x))
#define X first
#define Y second
#define lc o<<1
#define rc o<<1|1
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long LL;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 200000+10;
const int maxm = 2000+10;
const int mod = 1e9+7;
const double eps = 1e-8;
int a[maxn];
int main() {
#ifdef local
    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n; cin>>n;
    ll sum=0;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    ll ans=INF,s=0;
    for (int i=1;i<n;i++){
        s+=a[i];
        ans=min(ans,abs(sum-s-s));
    }
    cout<<ans<<"\n";
    return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include<cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include<bitset>

#define REP(i, b, n) for(int i=b;i<(int)n;i++)
#define rep(i, n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define FOR(it, o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define dbg(x) cout << __LINE__ << ' ' << #x << " = " << (x) << endl


typedef long long ll;
typedef long double ld;

using namespace std;

//ハマったらチェックリスト見ろ!!

int main() {
    ld n, m, d;

    cin >> n >> m >> d;
    if(int(d + 0.000000001) == 0){
        printf("%.10Lf\n", (m-1)/n);
    }else {
        ld tmp = 2 * n - 2 * d;
        tmp /= n;
        tmp *= (m-1);
        tmp /= n;
        printf("%.10Lf\n", tmp);
    }
    return 0;
}

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

#define Fast            ios_base::sync_with_stdio(false);cin.tie(nullptr);
#define LL              long long
#define ff              first
#define ss              second
#define pb              push_back
#define pii             pair<int,int>
#define all(a)          a.begin(),a.end()
#define MEM(a,x)        memset(a,x,sizeof(a))
#define FOR(i,a,b)      for(int i=a;i<=b;i++)
#define ROF(i,a,b)      for(int i=a;i>=b;i--)
#define REP(i,b)        for(int i=0;i<b;i++)

int main()
{
    int n,k;
    cin >> n >> k;
    int arr[n];
    REP(i,n) cin >> arr[i];

    LL dp[n];
    dp[n-1]=0;
    for(int i=n-2;i>=0;i--){
        dp[i]=0x3f3f3f3f3f3f;
        for(int j=1;j<=k and i+j<=n-1;j++){
            dp[i]=min(dp[i],dp[i+j]+abs(arr[i]-arr[i+j]));
        }
    }
    cout << dp[0];
}



Measured memory_bytes: 1408
using System;

namespace Atcoder
{
    class Program
    //AtCoder Beginner Contest 130 A - Rounding
    {
        private static void Main(string[] args)
        {
            var xa = Console.ReadLine().Split(' ');
            int x = int.Parse(xa[0]);
            int a = int.Parse(xa[1]);

            if (x < a)
            {
                Console.WriteLine(0);
            }
            else
            {
                Console.WriteLine(10);
            }

        }
    }
}


Measured memory_bytes: 11092
from itertools import permutations

def num(a_n, c):
    a_n_number = 0
    for i in range(len(a_n)):
        now = a_n[i]
        cnt= 0
        for k in range(i+1, len(a_n)):
            if a_n[k] <  now:
                cnt += 1
        
        a_n_number += c[i] * cnt
    
    return a_n_number


def main():
    n = int(input())
    p_n = list(map(int,input().split()))
    q_n = list(map(int,input().split()))
    c = [1]
    for i in range(n-1):
        c = [c[0]*(i+1)] + c
        
    p_n_num = num(p_n, c)
    q_n_num = num(q_n, c)
    
    print(abs(p_n_num - q_n_num))
        
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
S = str(input())
Q = int(input())

from collections import deque
s_list = [s for s in S]
que = deque(s_list)

mode = 1
for _ in range(Q):
  q_in = str(input())

  if q_in == '1':
    mode *= -1
    continue

  else:
    t, f_in, c = map(str, q_in.split())
    f = int(f_in)
    if mode == -1:
      if f_in == '1':
        f = 2
      else:
        f = 1
    if f == 1:
      que.appendleft(c)
    else:
      que.append(c)

if mode == -1:
  que = reversed(que)

ans = ''.join(que)
print(ans)

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

using namespace std;

int main(){

  string s;
  
  cin>>s;
  
  if(s=="Sunny") cout<<"Cloudy"<<endl;
  else if (s=="Cloudy") cout<<"Rainy"<<endl;
  else if (s=="Rainy") cout<<"Sunny"<<endl;
  
  return 0;
}

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

struct node{
	node *ch[2];
	
	node(){
		ch[0] = ch[1] = 0;
	}
	~node(){
		delete ch[0];
		delete ch[1];
	}
};

void tostr(node *nd, string &s){
	if(nd){
		s += '(';
		tostr(nd->ch[0], s);
		s += ',';
		tostr(nd->ch[1], s);
		s += ')';
	}
}

const char *p;
node *parse(){
	node *ret = new node;
	if(*++p == '('){
		ret->ch[0] = parse();
	}
	if(*++p == '('){
		ret->ch[1] = parse();
	}
	++p;
	return ret;
}

node *child(node *nd, int k){
	return nd ? nd->ch[k] : 0;
}

node *opr(char type, node *a, node *b){
	node *ret = 0;
	if(type == 'i'){
		if(a && b){
			ret = new node;
		}
	}
	else{
		if(a || b){
			ret = new node;
		}
	}
	
	if(ret){
		for(int i = 0; i < 2; ++i){
			ret->ch[i] = opr(type, child(a, i), child(b, i));
		}
	}
	return ret;
}

int main(){
	char type;
	string s, t;
	while(cin >> type >> s >> t){
		node *ns, *nt, *ret;
		p = s.c_str();
		ns = parse();
		p = t.c_str();
		nt = parse();

		ret = opr(type, ns, nt);
		
		string u;
		tostr(ret, u);
		cout << u << endl;
		
		delete ns;
		delete nt;
		delete ret;
	}
}

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

using namespace std;

#define fast_io ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define pb push_back
#define in insert
#define sz(x) (int) x.size()
#define sqr(x) ((x) * (x))
#define fi first
#define se second
#define y1 ksjdkf

template<typename T>
void vout(T x) {
    cout << x << endl;
    exit(0);
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;

const int inf = 1e9 + 1;
const ll INF = 1e18 + 1e2;
const int mod = 1e9 + 7;

void solve() {
    char c; cin >> c;
    if(isupper(c)) cout << 'A';
    else cout << 'a';
}

int main() {
    fast_io

    int q = 1;
//    cin >> q;
    while(q--) {
        solve();
    }
    return 0;
}


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

namespace agc030_a
{
    class Program
    {
        static void Main(string[] args)
        {
            var text = Console.ReadLine();
            var n = int.Parse(text);

            var tasks = new List<taskitem>();
            for (int i = 0; i < n; i++){
                text = Console.ReadLine();
                var list = text.Split(' ').Select(x => int.Parse(x)).ToList();

                var item = new taskitem();
                item.volume = list[0];
                item.limit = list[1];

                tasks.Add(item);
            }

            tasks = tasks.OrderBy(x => x.limit).ToList();

            var current = 0;
            foreach(var item in tasks){
                current = current + item.volume;
                if (current > item.limit){
                    Console.WriteLine("No");
                    return;
                }
            }

            Console.WriteLine("Yes");
            return;
        }

        public class taskitem{
            public int volume;
            public int limit;
        }

    }
}


Measured memory_bytes: 34568
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][][] dorm = new int[4][3][10];
        for (int i=0; i<n; ++i) {
            int b = sc.nextInt();
            int f = sc.nextInt();
            int r = sc.nextInt();
            int v = sc.nextInt();
            dorm[b-1][f-1][r-1] += v;
        }
        for (int i=0; i<3; ++i) {
            print_dorm(dorm, i);
            System.out.println("####################");
        }
        print_dorm(dorm, 3);
        sc.close();
    }

    private static void print_dorm(int[][][] dorm, int wing) {
        for (int i=0; i<3; ++i) {
            for (int j=0; j<10; ++j) {
                System.out.print(" " + dorm[wing][i][j]);
            }
            System.out.println("");
        }
    }
}


Measured memory_bytes: 29416
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        double r = sc.nextDouble();
        double pi = Math.PI;
        double area = pi * r * r;
        double length = 2 * pi * r;
        System.out.printf("%6f %6f\n",area, length);
        sc.close();
    }
}


Measured memory_bytes: 28324
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <vector>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
const int mod=99991;
const int maxn=200007;

char vis[maxn];

int main()
{
    int n,a,b,c,d,flag=0;
    cin>>n>>a>>b>>c>>d;
    cin>>vis+1;
    for(int i=max(a,b)-1;i<=min(c,d)-1;i++)
    {
        //cout<<vis[i]<<endl;
        if(vis[i]=='.'&&vis[i+1]=='.'&&vis[i+2]=='.')
        {
            flag=1;
            break;
        }
    }
    if(a<b&&c>d&&flag==0)
        cout<<"No";
    else
    {
        for(int i=min(a,b);i<=max(c,d)-1;i++)
        {
            if(vis[i]=='#'&&vis[i+1]=='#')
            {
                cout<<"No";
                return 0;
            }
        }
        cout<<"Yes";
    }
    return 0;

}
/*
2 11 4 4+3+4
3 22 6  11+5+6

*/


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <cmath>
using namespace std;
typedef vector<int> VI;
#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    vector<pair<double, double>> answers;

    double a, b, c, d, e, f;
    while (cin >> a >> b >> c >> d >> e >> f) {
        pair<double, double> ans;
        ans.first = (e * c - b * f) / (a * e - b * d) + 0.0;    // -0.000対策
        ans.second = (a * f - d * c) / (a * e - b * d) + 0.0;
        answers.push_back(ans);
    }

    for (auto ans : answers) {
        cout.setf(ios::fixed);
        cout.precision(3);
        cout << ans.first << " " << ans.second << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1296
N, M = map(int, input().split())
X = list(map(int, input().split()))
if N < M:
	x = sorted(X)
	B = []
	for i in range(0, M-1):
		B.append(x[i+1]-x[i])
	B.sort(reverse=True)
	for l in range(N-1):
		B.pop(0)
	print(sum(B))
else:
	print(0)

Measured memory_bytes: 13968
using System;
using System.Linq;
class A
{
    static void Main()
    {
        string s = Console.ReadLine();
        string[] A = Console.ReadLine().Split(' ');
        string[] AD = (string[])A.Distinct().ToArray();
        if (AD.Length == 4) Console.WriteLine("Four");
        else Console.WriteLine("Three");

    }
}

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

namespace ziyuutyou
{
    class Program
    {
        static void Main(string[] args)
        {
            var str = Console.ReadLine().Split(' ');
            List<int> aaa = new List<int>();
            var count5 = 0;
            var count7 = 0;
            for (var x = 0; x < str.Length; x++)
            {
                if (int.Parse(str[x]) == 5)
                {
                    count5++;
                }
                else if (int.Parse(str[x]) == 7)
                {
                    count7++;
                }
                aaa.Add(int.Parse(str[x]));
            }

            if (count5 == 2 && count7 == 1)
            {
                Console.WriteLine("YES");
            }
            else
            {
                Console.WriteLine("NO");
            }
        }
    }
}


Measured memory_bytes: 11092
fun main(args: Array<String>){
    val (n,l) = readLine()!!.split(" ").map(String::toInt)

    val apple = mutableListOf<Int>()

    var zeroflag = false
    var flag = false
    var nflag = false


    for(i in l..l+n-1){
        if(i == 0){
            zeroflag = true
        }
        else if(i == 1){
            flag = true
        }
        else if(i == -1){
            nflag = true
        }
        apple.add(i)
    }

    if(zeroflag){
        println(apple.sum())
    }
    else if(apple.sum() > 0){
        if(flag){
            println(apple.sum()-1)
        }
        else{
            println(apple.sum()-apple[0])
        }
    }
    else if(apple.sum() < 0){
        if(nflag){
            println(apple.sum()+1)
        }
        else{
            println(apple.sum()-apple[apple.size-1])
        }
    }
    else{
        println(apple.sum())
    }


}

Measured memory_bytes: 36028
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>

using namespace std;

const int MAXN = 2000000 + 1000;

int n, k;
bool rev;
deque<int> q;

int main()
{
	ios::sync_with_stdio(false);
	// freopen("1.in", "r", stdin);
	// freopen("1.out", "w", stdout);

	static char ss[MAXN];
	
	cin >> n >> k;
	cin >> (ss + 1);
	rev = false;
	for(int i = 1; i <= n; i++)
		q.push_back(ss[i] - 'A');
	k = min(k, 2 * n + (k + 2 * n) % 2);
	for(int i = 1; i <= k; i++)
	{
		int v = q.front() ^ rev;
		// cerr << rev << ' ' << v << endl;
		q.pop_front();
		if(v)
		{
			rev ^= 1;
			q.push_back(rev);
		}
		else
			q.push_front(rev ^ 1);
	}
	for(int i = 1; i <= n; i++)
		ss[i] = (q.front() ^ rev) + 'A', q.pop_front();

	cout << (ss + 1) << endl;


	return 0;
}


Measured memory_bytes: 1536
m, n = map(int, input().split())
mod = 10 ** 9 + 7


def my_pow(m, n, mod):
    # 繰り返し二乗法 偶数なら半分にして再帰でそれを返す、奇数ならmをかけてから
    if n == 1:
        return m
    if n % 2:
        return (m * my_pow(m, n // 2, mod) ** 2) % mod
    else:
        return (my_pow(m, n // 2, mod) ** 2) % mod


print(my_pow(m, n, mod))



Measured memory_bytes: 5600
#include<iostream>
using namespace std;
const int maxp=10005;
int n,q,Tree[maxp];

int GetP(int s) {
	if(Tree[s]==s) return s;
	else return Tree[s]=GetP(Tree[s]);
}

void Merge(int x,int y) {
	int px=GetP(x),py=GetP(y);
	if(px!=py) Tree[py]=px;
}

bool Check(int x,int y) {
	int px=GetP(x),py=GetP(y);
	if(px==py) return true;
	else return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin.tie(NULL);
	cin>>n>>q;
	for(int i=0; i<n; i++)
		Tree[i]=i;
	int judge,x,y;
	while(q--) {
		cin>>judge>>x>>y;
		if(judge) {
			if(Check(x,y)) cout<<"1"<<endl;
			else cout<<"0"<<endl;
		} else Merge(x,y);
	}
	return 0;
}


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

typedef long long ll;
typedef pair<int,int> P;
typedef map<int,int> M;
typedef vector<int> V;
#define push_back pb;
#define INF (int)(1e9)
#define EPS (1e-7)
#define MOD ((ll)1e9+7)
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define REP(i,n) for(int i=1;i<=(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define ALL(a)  a.begin(),a.end()
#define RALL(a) a.begin(),a.end(),greater<int>()
#define ROT(a) a.begin(),a.begin()+1,a.end()
#define RROT(a) a.begin(),a.end()-1,a.end()

/*--------------------------------------------*/
/*
int dx[4]={-1,0,1,0};//四方に移動
int dy[4]={0,-1,0,1};
*/
/*--------------------------------------------*/
/*--------------------------------------------*/
/*
ll factorial(ll n){
    if(n==1)return 1;
    return n*factorial(n-1);
}
ll lcm(ll A, ll B) {//最小公倍数
    ll a=A;
    ll b=B;
    if (a==0 || b==0) {return 0;}
    if (a<0) {a=-a;}
    if (b<0) {b=-b;}
    while(b>0) {
        ll c=a%b;
        a=b;
        b=c;
    }
    return A/a*B;
}

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

//入力はすべて正とする
bool is_prime(int n) {//素数判定o(√n)
    for (int i=2;i*i<=n;i++){
        if(n%i==0)return false;
    }
    return n!=1;//1の場合は例外
}

vector<ll> divisor(ll n){//約数の列挙o(√n)
    vector<ll> res;
    for(ll i=1;i*i<=n;i++) {
        if(n%i == 0){
        res.push_back(i);
        if(i!=n/i)res.push_back(n/i);
        }
    }
    return res;
}//vector<ll>k=divisor(n);rep(i,k.size())cout<<k[i]<<endl;//のように使う

map<ll,ll> prime_factor(ll n){//素因数分解o(√n)
    map<ll,ll>res;    
    for(ll i=2;i*i<=n;i++) {
        while (n%i==0) { 
            ++res[i];
            n/=i;
        }
    }
    if (n!=1)res[n]=1;
    return res;
}//map<ll,ll> k=prime_factor(n);for(auto i=k.begin();i!=k.end();i++){cout<<i->first<<" "<<i->second<<endl;}//みたいに使う

vector<ll> prime_list(ll n){//n以下の素数を全て見つける
    vector<ll> is_prime(n);//is_prime[i]が1ならiは素数
    for(ll i=2;i<=n;i++)is_prime[i]=1;//最初はみんな素数かも
    for(ll i=2;i*i<=n;i++){//素数の整数倍を消していく(√nまで)
        if(is_prime[i]){
            for(ll j=2*i;j<=n;j++){
                if(j%i==0){
                    is_prime[j]=0;                
                }
            }
        }
    }return is_prime;
}vector<ll>k=prime_list(n);REP(i,n){if(k[i])cout<<i<<endl;}のように使う
*/
/*--------------------------------------------*/


int main(){
    string s,t;cin>>s>>t;
    int flag=0;
    rep(i,s.size()){
        if(s==t){flag=1;break;}
        rotate(RROT(s));
        //cout<<s<<endl;
    }
    cout<<(flag?"Yes":"No")<<endl;
}




Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
int main()
{
  string s; cin >> s;
  reverse(s.begin(), s.end());
  s.push_back('0');
  int n = s.size();
  
  int inf = 1e+9;
  int dp[1000010][2];
  rep(i,n+1) rep(j,2) dp[i][j] = inf;
  dp[0][0] = 0;
  
  rep(i,n+1) {
    int x = s[i] - '0';
    rep(j,2) {
      rep(d,10) {
	if(d > x) { // i+1桁目にs[i]より真に大きい数字を選ぶ場合
	  chmin(dp[i+1][0], dp[i][j] + 2*d - x + (j ? -1 : 0) );
	}
	else if(d < x) {
	  chmin(dp[i+1][1], dp[i][j] + 2*d - x + (j ? 9 : 10) );
	}
	else {
	  chmin(dp[i+1][j], dp[i][j] + 2*d - x + (j ? 9 : 0) );
	}
      }
    }
  }

  cout << dp[n][0] << "\n";
  
  
  return 0;
}


Measured memory_bytes: 9220
#include <bits/stdc++.h>
struct Fast {Fast(){std::cin.tie(0);std::ios::sync_with_stdio(false);}} fast;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < (int)(n); i++)
#define repR(i, n) for(ll i = n; i >= 0; i--)
#define For(i, m, n) for(ll i = m; i < n; i++)

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) v.begin(), v.end()

using namespace std;

ll mod = 1e9+7;
inline ll gcd(ll a, ll b){
    ll r = a % b;
    while(r!=0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

inline ll lcm(ll x, ll y)
{
    if(x == 0 || y == 0) {
        return -1;
    }
    
    return (x * y / gcd(x, y));
}

inline ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

inline ll nCr(ll n, ll r) {
    if ( r * 2 > n ) r = n - r;
    ll dividend = 1;
    ll divisor  = 1;
    for ( ll i = 1; i <= r; ++i ) {
        dividend *= (n-i+1);
        divisor  *= i;
    }
    return (dividend / divisor);
}

// 因数分解
inline vector<pair<ll, int>>factorize(ll n){
    vector<pair<ll, int>> res;
    for(ll i = 2; i * i <= n; ++i){
        if(n % i) continue;
        res.emplace_back(i, 0);
        while(n % i == 0){
            n /= i;
            res.back().second++;
        }
    }
    if(n != 1) res.emplace_back(n, 1);
    return res;
}

inline bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

//階乗
inline ll factorialMethod(ll k){
    ll sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

inline ll vector_finder(std::vector<ll> vec, ll number) {
    auto itr = std::find(vec.begin(), vec.end(), number);
    size_t index = std::distance( vec.begin(), itr );
    if (index != vec.size()) { // 発見できたとき
        return 1;
        
        
    }
    else { // 発見できなかったとき
        return 0;
    }
}

int main(){
    ll n;
    cin >> n;
    if(n % 2 != 0){
        cout << 0 << endl;
        return 0;
    }
    
    ll count = 0;
    ll temp5 = 5;
    while(true){
        if(n < temp5){
            break;
        }
        
        count += n / temp5 / 2;
        temp5 *= 5;
    }
    
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = (ll)(1e+9) + 7;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
int d[1000][2];
vector<int> G[1000];
int a[1000];
void dfs(int id) {
    int dpb[5001], dpw[5001];
	int len = G[id].size();
	fill(dpb, dpb + a[id] + 1, (int)mod);
	dpb[0] = 0;
	fill(dpw, dpw + a[id] + 1, (int)mod);
	dpw[0] = 0;
	rep(i, len) {
		int v = G[id][i]; dfs(v);
		per(j, a[id] + 1) {
			if (dpb[j] == (int)mod)continue;
			int memo = dpb[j]; dpb[j] = (int)mod;
			if (j + a[v] <= a[id])dpb[j + a[v]] = min(dpb[j + a[v]], memo + d[v][0]);
			if (j + d[v][1] <= a[id])dpb[j + d[v][1]] = min(dpb[j + d[v][1]], memo + a[v]);
			//cout << id << " " << dpb[0] << endl;
			//cout << memo << endl;
		}
		per(j, a[id] + 1) {
			if (dpw[j] == (int)mod)continue;
			int memo = dpw[j]; dpw[j] = (int)mod;
			if (j + a[v] <= a[id])dpw[j + a[v]] = min(dpw[j + a[v]], memo + d[v][1]);
			if (j + d[v][0] <= a[id])dpw[j + d[v][0]] = min(dpw[j + d[v][0]], memo + a[v]);
		}
	}
	int mib = (int)mod;
	int miw = (int)mod;
	per(i, a[id] + 1) {
		mib = min(mib, dpb[i]);
		miw = min(miw, dpw[i]);
	}
	d[id][0] = mib; d[id][1] = miw;
	return;
}
int main() {
	int n; cin >> n;
	rep1(i, n - 1) {
		int p; cin >> p; p--;
		G[p].push_back(i);
	}
	rep(i, n) {
		cin >> a[i];
	}
	dfs(0);
	//cout << endl;
	if (d[0][0] < (int)mod&&d[0][1] < (int)mod)cout << "POSSIBLE" << endl;
	else cout << "IMPOSSIBLE" << endl;
	/*rep(i, n) {
	    rep(j, 2) {
	        cout << i << " " << j << endl;
	        cout << d[i][j] << endl;
	    }
	}*/
	return 0;
}


Measured memory_bytes: 14592
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int N;
    cin >> N;
    vector<ll> v(N);
    for (int i = 0; i < N; i++) cin >> v[i];
    map<ll, ll> mp;
    for (int i = 1; i < N; i++) mp[i - v[i]]++;
    ll ans = 0;
    for (int i = 0; i < N - 1; i++) {
        ll tmp = i + v[i];
        ans += mp[tmp];
        tmp = i + 1 - v[i + 1];
        mp[tmp]--;
    }
    cout << ans << '\n';
}


Measured memory_bytes: 27364
//InTheNameOfGod
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,j,k) for(int i=j;i<k;++i)
#define rrep(i,j,k) for(int i=j;i>=k;i--)
#define pb push_back
#define lb(i) i&(-i);
ll n,a,b;
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>n>>a>>b;
    cout<<min(a*n,b);
    return 0;
}


Measured memory_bytes: 256
H, W, K = map(int, input().split())

sheet = []

cnt = 0

def getPatterns(n):
    ans = []
    for i in range(2 ** n):
        op = ["-"] * n  # あらかじめ ["-", "-", "-"] というリストを作っておく
        for j in range(n):
            if ((i >> j) & 1):
                op[n - 1 - j] = "+"  # フラグが立っていた箇所を "+" で上書き
        ans.append(op)
    
    return ans


for i in range(H):
    s = input()
    cnt += s.count('#') 
    a = []
    for j in range(W):
        a.append(s[j])
    sheet.append(a)

H_pattern = getPatterns(H)
W_pattern = getPatterns(W)

test_sheet = []

ans = 0


for i in H_pattern:
    test_sheet = []
    for x in range(len(i)):
        if i[x] == "-":
            test_sheet.append(sheet[x])
    for j in W_pattern:
        test_cnt = 0
        for y in range(len(j)):
            if j[y] == "-":
                for z in test_sheet:
                    if z[y] == "#":
                        test_cnt += 1
        if test_cnt == K:
            ans += 1

print(ans)

Measured memory_bytes: 9220