akhauriyash/Code-Regression huggingface dataset:
def b166(n, k):

    count = []
    for i in range(k):
        d = int(input())
        al = []
        a = 0
        if d == 1:
            a = int(input())
            count.append(a)
        else:
            al = list(map(int, input().split()))
            for w in al:
                count.append(w)

    return n - len(set(count))

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

if __name__ == '__main__':
    main()

Measured memory_bytes: 67728
S = list(input())
T = list(input())

min = 10000
for i in range(len(S)-len(T)+1):
  count = 0
  for j in range(len(T)):
    if T[j] != S[i+j]:
      count += 1
  
  if min > count:
    min = count

print(min)
      

Measured memory_bytes: 65176
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const int INF=1e9;

ll N,A,B;

int main(){

cin>>N>>A>>B;

if(N==1){
    if(A==B) cout<<1<<endl;
    else cout<<0<<endl;
    return 0;
}
if(A>B){
    cout<<0<<endl; return 0;
}

ll x=(N-2)*A,y=(N-2)*B;

cout<<y-x+1<<endl;

return 0;
 
}

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

int main(){

	int N, M;
	scanf("%d %d", &N, &M);

	std::priority_queue<long long> q;

	for(int i = 0; i < N; i++){
		long long A;
		scanf("%lld", &A);
		q.push(A);
	}

	for(int i = 0; i < M; i++){
		q.push((q.top() / 2));
		q.pop();

	}

	long long sum = 0;
	for(int i = 0; i < N; i++){
		sum = sum + q.top();
		q.pop();
	}

	printf("%lld\n", sum);



}

Measured memory_bytes: 1400
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long LL;

template<typename T>
istream& operator >> (istream& is, vector<T>& vs){
  for(T& v: vs) is >> v;
  return is;
}

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


Measured memory_bytes: 3960
#include <cstdio>
#include <algorithm>
#define ll long long
#define C (c=getchar())
using namespace std;
const int N=100005;
inline void read(int &a)
{
	a=0;int f=1;char c;C;
	while (c<'0'||c>'9') c=='-'?f=-1,C:C;
	while (c>='0'&&c<='9') a=(a<<3)+(a<<1)+(c-48),C;
	a*=f;
}
int n;
int a[N];
int abs(int x)
{
	if (x<0) return -x;
	return x;
}
int ans;
int main()
{
	register int i,j;
	read(n);
	for (i=1;i<=n;i++) read(a[i]),ans+=abs(a[i]-a[i-1]);ans+=abs(a[n]-0);
	for (i=1;i<=n;i++)
	{
		int o=ans;
		o-=abs(a[i]-a[i-1]);
		o-=abs(a[i+1]-a[i]);
		o+=abs(a[i+1]-a[i-1]);
		printf("%d\n",o);
	}
}

Measured memory_bytes: 1536
#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;

int main()
{
	int h1, m1, h2, m2, k;
	cin >> h1 >> m1 >> h2 >> m2 >> k;
	int time1 = h1 * 60 + m1, time2 = h2 * 60 + m2;
	if (time1 > time2)time2 += 60 * 24;
	cout << (time2 - time1) - k;
}

Measured memory_bytes: 3628
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<utility>
#include<numeric>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<tuple>
#include<stack>
#include<queue>
#include<tuple>
#include<functional>
#include<iterator>
#include<cmath>
#include<cctype>

using namespace std;

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

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = INF+7;

struct edge{int to,cost;};

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

	string n;
	cin >> n;

	for(int i=0;i<3;i++){
		if(n[i] == '1') cout << "9";
		else if(n[i]=='9') cout << "1";
		else cout << n[i];
	}
	cout << "\n";
	
	return 0;
}

Measured memory_bytes: 256
using System;
 
class Program
{
    static void Main()
    {
    	while(true) {
    		string[] s = Console.ReadLine().Split(' ');
    		int m = int.Parse(s[0]);
    		int f = int.Parse(s[1]);
    		int r = int.Parse(s[2]);
    		
    		if( (m == -1) && (f == -1) && (r == -1) ) break;
    		
    		int sum = m + f;
    		if( (m == -1) || (f == -1) ) {
    			Console.WriteLine("F");
    		} else if (sum >= 80) {
    			Console.WriteLine("A");
    		} else if (sum >= 65) {
    			Console.WriteLine("B");
    		} else if (sum >= 50) {
    			Console.WriteLine("C");
    		} else if (sum >= 30) {
    			if(r >= 50) Console.WriteLine("C");
    			else Console.WriteLine("D");
    		} else {
    			Console.WriteLine("F");
    		}
    	}
    }
}

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

using namespace std;


int a,b,c;

typedef vector<int> vint;
typedef vector<long long> vll;
typedef vector<double> vdb;
typedef vector<bool> vbol;
typedef vector<string> vstr;

#define vvll(a,b,c) vector<vector<long long>> c(a,vector<long long>(b,0))
#define vvit(a,b,c) vector<vector<int>> c(a,vector<int>(b,0))
#define vvstr(a,b,c) vector<vector<string>> c(a,vector<string>(b,0))
#define vvbol(a,b,c) vector<vector<bool>> c(a,vector<bool>(b,0))
#define vvdb(a,b,c) vector<vector<double>> c(a,vector<double>(b,0))
#define fi(a,b) for(int i=a;i<b;i++)
#define fj(a,b) for(int j=a;j<b;j++)
#define f_i(a,b) for(int i=0;i<=b;i++)
#define f_j(a,b) for(int j=0;j<=b;j++)

long long eratstenes(long long n)
{
    vbol num(n*n+10,true);
    f_i(2,n)
    {
        if(num.at(i)==true)
        {
            f_j(2,n*n)
            {
                num.at(j*i)=false;
            }
        }
    }
    fi(0,n+1)
    {
        cout << num.at(i) << endl;
    }
    int count=0;
    fi(2,n+1)
    {
        if(num.at(i)==true&&i%2==1)
        {
            count++;
        }
    }
    return(count);
}

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

    int k;
    cin >> k;
    fi(0,k)
    {
        cout << "ACL";
    }
    cout << endl;
    return(0);

}

Measured memory_bytes: 3600
package main
 
import "fmt"
 
var n int
var s string
func main() {
	fmt.Scan(&n)
	m := make(map[string]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&s)
		m[s] = 1
	}
	fmt.Println(len(m))
}

Measured memory_bytes: 17804
n,a,b,c = map(int,input().split())

abc = [a,b,c]

def get_index(ch):
    if (ch == "A"):return 0
    elif (ch == "B"):return 1
    else:return 2

ans = ["Yes"]
S = [input() for _ in range(n)]

for i in range(n):
    s = S[i]
    s1 = get_index(s[0])
    s2 = get_index(s[1])
    
    if abc[s1] == 0 and abc[s2] == 0:
        ans[0] = "No"
    
    elif abc[s1] == 0 or abc[s2] == 0:
        if abc[s2] == 0:
            abc[s1] -= 1
            abc[s2] += 1
            ans.append(s[1])
        else:
            abc[s1] += 1
            abc[s2] -= 1
            ans.append(s[0])
    
    elif abc[s1] + abc[s2] == 2 and i != n-1:
        if S[i] != S[i+1]:
            next_s = S[i+1]
            next_s1 = get_index(next_s[0])
            next_s2 = get_index(next_s[1]) 
            if s1 == next_s1 or s1 == next_s2:
                abc[s1] += 1
                abc[s2] -= 1
                ans.append(s[0])
            else:
                abc[s1] -= 1
                abc[s2] += 1
                ans.append(s[1])
        else:
            abc[s1] += 1
            abc[s2] -= 1
            ans.append(s[0])
    
    elif abc[s1] == 1:
        abc[s1] += 1
        abc[s2] -= 1
        ans.append(s[0])

    elif abc[s2] == 1:
        abc[s1] -= 1
        abc[s2] += 1
        ans.append(s[1])

    else:
        abc[s1] -= 1
        abc[s2] += 1
        ans.append(s[1])

for a in ans:
    print(a)
    if a == "No":
        break
 

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

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i <= (ll)(n); i++)
#define INF 10000000000
#define MOD 1000000007
using ll = long long;
using Graph = vector<set<ll>>;

int main(){
  int N; cin>>N;
  vector<ll> A(N); rep(i,N)cin>>A.at(i);
  vector<ll> R(N);
  ll tmp = 0, s = 0;
  rep(i,N){
    s += A.at(i);
    if(i%2==1)tmp += A.at(i);
  }
  R.at(0) = s - 2*tmp;
  rep1(i,N-1)R.at(i) = -R.at(i-1) + 2*A.at(i-1);
  rep(i,N)cout<<R.at(i)<<endl;
} 

Measured memory_bytes: 2944
N, M = gets.split.map(&:to_i)
ABCs = N.times.map{gets.split.map(&:to_i)}
DEFs = M.times.map{gets.split.map(&:to_i)}
INF = 10**10

require 'set'

xs, ys = SortedSet.new, SortedSet.new
ABCs.each{ys << _1[2]}
DEFs.each{xs << _1[0]}
ys = [-INF] + ys.to_a + [INF]
xs = [-INF] + xs.to_a + [INF]
n, m = xs.size - 1, ys.size - 1
wx, wy = Array.new(n){Array.new(m, false)}, Array.new(n){Array.new(m, false)}
ABCs.each do |a, b, c|
  x1 = xs.bsearch_index{_1 >= a}
  y1 = ys.bsearch_index{_1 >= c}
  x2 = xs.bsearch_index{_1 > b} - 1
  (x1 ... x2).each{wy[_1][y1] = true}
end
DEFs.each do |d, e, f|
  x1 = xs.bsearch_index{_1 >= d}
  y1 = ys.bsearch_index{_1 >= e}
  y2 = ys.bsearch_index{_1 > f} - 1
  (y1 ... y2).each{wx[x1][_1] = true}
end
cs = Array.new(n){Array.new(m, false)}
cx, cy = xs.bsearch_index{_1 > 0} - 1, ys.bsearch_index{_1 > 0} - 1
cs[cx][cy] = true
q, ans = [[cx, cy]], 0
while !q.empty?
  x, y = q.pop
  (puts 'INF'; exit) if x.zero? || y.zero?
  ans += (xs[x + 1] - xs[x])*(ys[y + 1] - ys[y])
  (cs[x - 1][y] = true; q << [x - 1, y]) if !x.zero? && !wx[x][y] && !cs[x - 1][y]
  (cs[x][y - 1] = true; q << [x, y - 1]) if !y.zero? && !wy[x][y] && !cs[x][y - 1]
  (cs[x + 1][y] = true; q << [x + 1, y]) if x + 1 < n && !wx[x + 1][y] && !cs[x + 1][y]
  (cs[x][y + 1] = true; q << [x, y + 1]) if y + 1 < m && !wy[x][y + 1] && !cs[x][y + 1]
end
puts ans

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

int main(){
  string S;
  cin >> S;
  int N=S.size();
  for(int i=0;i<N;i++){
    if(i%2==0){
      cout << S.at(i);
    }
  }
  cout << endl;
}

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

using namespace std;
using lli = long long int;
using ulli = unsigned long long int;

namespace atcoder {
	void judge_outer(bool judge_exp, string ok = "Yes", string ng = "No")
	{
		if (judge_exp) {
			cout << ok << endl;
		}
		else {
			cout << ng << endl;
		}
	}

	int ncr(int left, int right)
	{
		right = min(left - right, right);
		int ans = 1;
		for (int i = 1; i <= right; i++) {
			ans = ans * (left - right + i) / i;
		}
		return ans;
	}

	const int LIMIT = 1000000256;
	const int tenfive = 100100;
}

using namespace atcoder;

int main()
{
	lli N;
	cin >> N;
	vector<lli>A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	lli now = 1;
	for (int i = 0; i < N; i++) {
		now = now / __gcd(now, A[i]) * A[i];
	}
	cout << now << endl;
}



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

int main() {
  int N; cin>>N; 
  long long sum=0;
  for(int i=0; i<N; i++){
    long long a;
    cin>>a;
    sum=sum+a-1;
  }
  cout<<sum<<endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	int n; cin>>n;
	int a[110];
	for(int i=0; i<n; i++) cin>>a[i];
	bool ok=1;
	for(int i=0; i<n; i++){
		if(a[i]%2==1) continue;
		if(a[i]%3!=0 && a[i]%5!=0) ok=0;
	}
	if(ok) cout<<"APPROVED"<<endl;
	else cout<<"DENIED"<<endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication34
{
    class Program
    {
        static void Main()
        {
            long a = 1;int s = int.Parse(Console.ReadLine());
            for(int b = 1; b <= s; b++)
            {
                a *= b;
            }
            Console.WriteLine(a);
        }
    }
}

Measured memory_bytes: 9040
#include <stdio.h>

int gcd(int x, int y)
{
    if (x == 0){
        return (y);
    }
    return (gcd(y % x, x));
}

int main(void)
{
    int x, y;

    scanf("%d %d", &x, &y);
    printf("%d\n", gcd(x, y));

    return (0);
}

Measured memory_bytes: 592
import math

def factorial(n):
    val = 1
    for i in range(2, n + 1):
        val =  val * i % 1000000007
    return val

n,m= (int(i) for i in input().split())

if n==m:
    a = factorial(n)
    print(2 * a * a % 1000000007)
elif abs(n-m) == 1:
    a = factorial(min(m,n))
    print(a * a * max(m,n) % 1000000007)
else:
    print(0)


Measured memory_bytes: 3060
N = int(input())
A = []
x = []
y = []
for i in range(N):
    A.append(int(input()))
    x2 = []
    y2 = []
    for j in range(A[i]):
        xy = input().split()
        x2.append(int(xy[0]))
        y2.append(int(xy[1]))
    x.insert(i, x2)
    y.insert(i, y2)

ans = 0
for i in range(pow(2, N)):
    flag = True
    for j in range(N):
        if not(i & (1<<j)):
            continue
        else:
            for k in range(A[j]):
                if (((i>>(x[j][k]-1))&1) ^ y[j][k]):
                    flag = False
    count = 0
    if flag:
        count = bin(i).count('1')
    if ans < count:
        ans = count
print(ans)



Measured memory_bytes: 3064
s = input()

year = int(s[0:4])
month = int(s[5:7])
day = int(s[8:10])

if year <= 2018:
    print('TBD')
    exit()
elif 2020 <= year:
    print('Heisei')
    exit()
else:
    if month <= 4:
        print('Heisei')
    else:
        print('TBD')


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll         = long long;
constexpr ll MOD = 1000000007;
#define REP(i, n) for (ll i = 0; i < (n); i++)
#define REP2(i, x, n) for (ll i = x; i < (n); i++)
#define PR(x) cout << (x) << "\n"
#define PS(x) cout << (x) << " "
const long long INF = numeric_limits<long long>::max();

vector<ll> isPrimes;

vector<ll> sieve(ll N) {
    // エラトステネスのふるい
    // int N = 101010;くらい
    vector<ll> isPrimes(N + 1, 1);
    isPrimes[0] = 0;
    isPrimes[1] = 0;
    for (ll i = 2; pow(i, 2) <= N; i++) {
        if (isPrimes[i])
            for (ll j = 2; i * j <= N; j++) isPrimes[i * j] = 0;
    }
    return isPrimes;
}

bool isLike2017(ll N) {
    if (N % 2 == 0) return false;
    if (!isPrimes[N]) return false;
    return isPrimes[(N + 1) / 2];
}

void dumpVector(const vector<ll>& vec) {
#ifdef SOURCE_TEST
    for (ll i = 0; i < vec.size(); ++i) {
        cout << vec[i] << ",";
    }
    cout << endl;
#endif
}
int main() {
    isPrimes = sieve(1000000 + 100);
    dumpVector(isPrimes);
    ll MAX = 1000000 + 100;
    vector<ll> values(MAX, 0);
    REP(i, values.size()) {
        values[i] = isLike2017(i) ? 1 : 0;
    }
    dumpVector(values);

    vector<ll> sums(MAX + 1, 0);
    REP(i, values.size()) {
        sums[i + 1] = values[i] + sums[i];
    }
    dumpVector(sums);
    ll Q;
    cin >> Q;
    REP(i, Q) {
        ll l, r;
        cin >> l >> r;
        PR(sums[r + 1] - sums[l]);
    }
    return 0;
}

Measured memory_bytes: 26568
N = int(input())
n = N*2
k = 1
while k * (k+1) < n:
	k += 1
if k * (k+1) != n:
	print('No')
	exit()
ans = [[0 for i in range(k)] for j in range(k+1)]
n = 1
for i in range(k+1):
	for j in range(i, k):
		ans[i][j] = n
		ans[j+1][i] = n
		n += 1
print('Yes')
print(k+1)
for a in ans:
	print(' '.join([str(k)] + [str(i) for i in a]))

Measured memory_bytes: 9076
#include <cstdio>

int k,n;
inline int val(const int &i,const int &j){
	int v=(i+n-j)%n+1+(i%2)*n;
	return v>k?v-n:v;
}
int main(){
	scanf("%d",&k);
	if(k==1){puts("1\n1");return 0;}
	n=(k+1)>>1;
	n+=(n%2);
	printf("%d\n",n);
	for(int i=1;i<=n;i++,putchar('\n'))
		for(int j=1;j<=n;j++)
			printf("%d ",val(i,j));
}

Measured memory_bytes: 1152
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;



int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);


    int n, m;
    int X;
    cin >> n >> m >> X;

    vector<int> C(n, 0);
    vector<vector<int>> A(n, vector<int>(m, 0));

    for (int i = 0; i < n; ++i) {
        cin >> C[i];
        for (int j = 0; j < m; ++j) {
            cin >> A[i][j];
        }
    }

    const long long INF = 1LL << 40;
    long long res = INF;

    auto ok = [&](int mask) {
        vector<long long> L(m, 0);

        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                for (int j = 0; j < m; ++j) {
                    L[j] += A[i][j];
                }
            }
        }

        bool res = true;
        for (int i = 0; i < m; ++i) {
            if (L[i] < X) {
                res = false;
                break;
            }
        }

        return res;
    };

    auto cost = [&](int mask) {
        long long res = 0;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                res += C[i];
            }
        }
        return res;
    };

    int N = 1 << n;
    for (int i = 0; i < N; ++i) {
        if (ok(i)) {
            res = min(res, cost(i));
        }   
    }


    if (res >= INF) {
        res = -1;
    }

    cout << res << '\n';

    return 0;
}

Measured memory_bytes: 3664
/*

Mouse hunt

author : Rohit Kulkarni

Approach : DP

Space comp :
Time comp : 

*/

#include<bits/stdc++.h>
using namespace std;

#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
typedef long long int ll;
const ll MAX=3e3+3;
const ll INF=1e9+3; 

ll dp[MAX][MAX];
string res;

int main()
{
    faster;
    string s1,s2;
    cin>>s1>>s2;
    ll pos_x,pos_y;
    ll max_val=-INF;
    for(int i=0;i<s1.length();i++)
    {
        for(int j=0;j<s2.length();j++)
        {
            if(s1[i]==s2[j])
            {
                dp[i+1][j+1]=1+dp[i][j];
                
            }
            else 
            {
                dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
                
            }
        }
    }
    pos_x=s1.length();
    pos_y =s2.length();
    while(pos_x>0 && pos_y >0)
    {
        if(dp[pos_x][pos_y]==dp[pos_x][pos_y-1])
            pos_y--;
        else if(dp[pos_x][pos_y]==dp[pos_x-1][pos_y])    
            pos_x--;
        else 
        {
            pos_x--;
            pos_y--;
            res+=s2[pos_y];
        }
    }
    for(int j=res.length()-1;j>=0;j--)
        cout<<res[j];
}


Measured memory_bytes: 70656
import Foundation
 
let input_line: String = readLine()!
let split: [String] = input_line.components(separatedBy: " ")
 
let a = Int(split[0])!
let b = Int(split[1])!
let c = Int(split[2])!
let d = Int(split[3])!
let e = Int(split[4])!

if (a==0){
    print(1)
}else if (b==0){
    print(2)
}else if (c==0){
    print(3)
}else if (d==0){
    print(4)
}else if (e==0){
    print(5)
}

Measured memory_bytes: 14108
# 問題読んでやったことないと思って解こうとした（ログみたら以前に解いてたらしいが一切覚えてない）
# 自分より後ろにあるやつは優先度低い
n, x = map(int, input().split())
arr = list(map(int, input().split()))
c = 0
for i in range(1, n):
    if arr[i - 1] + arr[i] > x:
        dif = arr[i - 1] + arr[i] - x
        if arr[i] >= dif:
            # 自分だけ犠牲になればいい
            arr[i] -= dif
        else:
            # 自分だけじゃ足りないぶん
            new_dif = dif - arr[i]
            arr[i] = 0
            arr[i - 1] -= new_dif
        c += dif
print(c)


Measured memory_bytes: 14540
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
	int n; cin >> n;
	int num; cin >> num;
	int maxv = -1000000001;
	int minv = num;
	for (int i = 1; i  < n; i++){
		cin >> num;
		maxv = max(maxv , num - minv);
		minv = min(minv , num);
	}
	cout << maxv << endl;

return 0;
}

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

using namespace std;

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

const int INF = 1000000000;
const ll LINF = (ll) 4000000000000000000;
const ll MOD = (ll) 1000000007;
const double PI = acos(1.0);
const int limit = 100010;

#define REP(i,m,n) for(ll i = m; i < (ll)(n); i++)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define NP(v) next_permutation(v.begin(),v.end())
#define smaller_queue  priority_queue <ll, vector<ll>, greater<ll> >

//------------------------------------------------------

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

    int Min = INF;

    REP(a, 1, n) {
        int b = n - a;
        int sum = 0;
        string sa = to_string(a);
        string sb = to_string(b);
        for (auto c : sa) sum += (int) (c - '0');
        for (auto c : sb) sum += (int) (c - '0');
        Min = min(Min, sum);
    }

    cout << Min << endl;
    return 0;
}


Measured memory_bytes: 256
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define Vd vector<double>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int gcd(int a,int b){return b?gcd(b,a%b):a;} //最小公倍数

// デフォルト変数定義
int n,m,a,b,c,x,y,z;
double d,e,f;
string s,t;
//

signed main() {
  RAPID;
  IN(s);
  SORT(s);
  Yes((s[0]==s[1])&&(s[1]!=s[2])&&(s[2]==s[3]));
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		long A = sc.nextLong();
		long V = sc.nextLong();
		long B = sc.nextLong();
		long W = sc.nextLong();
		long T = sc.nextLong();
		if (Math.abs(B - A) <= (V - W) * T) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}

Measured memory_bytes: 35820
A,B,K = map(int,input().split())

if B - A + 1 < K * 2:
    for i in range(A,B+1):
        print(i)
else:
    for i in range(A,min(B,A + K)):
        print(i)

    for i in range(max(B - K + 1,A + K),B + 1):
        print(i)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
char *ft_strrev(char *str)
{
    int count;
    int i;
    char c;

    count = 0;
    while (str[count] != '\0')
        count++;
    count = count - 1;
    i = 0;
    while (i < ((count + 1) / 2)){
        c = str[i];
        str[i] = str[count - i];
        str[count - i] = c;
        i++;
    }
    return (str);
}
int main(){
  int N,M=0;
  char p[20]={0};
  char ans[20]={0};
  cin >> N;
  char *adr;
  for(int a=0;a<=9;a++){ 
    p[11]=a;
    if(abs(p[12]-p[11])>1)
        continue;
    for(int b=0;b<=9;b++){ 
      p[10]=b;
      if(abs(p[11]-p[10])>1 && a)
        continue;
      for(int c=0;c<=9;c++){ 
        p[9]=c;
        if(abs(p[10]-p[9])>1 && a+b)
                continue;
        for(int d=0;d<=9;d++){ 
          p[8]=d;
          if(abs(p[9]-p[8])>1 && a+b+c)
                continue;
          for(int e=0;e<=9;e++){
            p[7]=e;
            if(abs(p[8]-p[7])>1 && a+b+c+d)
                continue;
            for(int f=0;f<=9;f++){ 
              p[6]=f;
              if(abs(p[7]-p[6])>1 && a+b+c+d+e)
                continue;
              for(int g=0;g<=9;g++){ 
                p[5]=g;
                if(abs(p[6]-p[5])>1 && a+b+c+d+e+f)
                        continue;
                for(int h=0;h<=9;h++){ 
                  p[4]=h;
                  if(abs(p[5]-p[4])>1 && a+b+c+d+e+f+g)
                        continue;
                  for(int i=0;i<=9;i++){ 
                    p[3]=i;
                    if(abs(p[4]-p[3])>1 && a+b+c+d+e+f+g+h)
                        continue;
                    for(int j=0;j<=9;j++){ 
                      p[2]=j;
                      if(abs(p[3]-p[2])>1 && a+b+c+d+e+f+g+h+i)
                        continue;
                      for(int k=0;k<=9;k++){ 
                        p[1]=k;
                        if(abs(p[2]-p[1])>1 && a+b+c+d+e+f+g+h+i+j)
                          continue;
                        for(int l=0;l<=9;l++){ 
                          p[0]=l;
                          if(abs(p[0]-p[1])>1 && a+b+c+d+e+f+g+h+i+j+k)
                            continue;
                          if(M++==N){
                            int ss[12]={a,b,c,d,e,f,g,h,i,j,k,l};
                            for(int uu=0;uu<12;uu++){
                              if(ss[uu]){
                                for(int ansp=uu;uu<12;uu++){
                                  ans[uu-ansp]=p[11-uu]+='0';
                                }
                            goto endend;
                              }
                            }
                          }
                        }
                      }
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
  endend:
  puts(ans);
}

Measured memory_bytes: 256
use std::io::{stdin, BufRead};

fn main() {
    // stdin()のロックを取得
    let stdin = stdin();
    let mut stdin = stdin.lock();
    let stdin = &mut stdin;

    let mut buf = String::new();
    stdin.read_line(&mut buf).unwrap();
    let mut input = buf.split_whitespace();
    let n = input.next().unwrap().parse::<usize>().unwrap();
    let m = input.next().unwrap().parse::<usize>().unwrap();

    let mut matrix_n_m: Vec<Vec<i32>> = Vec::new();
    for _ in 0..n {
        let mut matrix_m: Vec<i32> = Vec::new();
        let mut buf = String::new();
        stdin.read_line(&mut buf).unwrap();
        let mut input = buf.split_whitespace();
        for _ in 0..m {
            matrix_m.push(input.next().unwrap().parse::<i32>().unwrap());
        }
        matrix_n_m.push(matrix_m)
    }

    let mut matrix_1_m: Vec<i32> = Vec::new();
    for _ in 0..m {
        let mut buf = String::new();
        stdin.read_line(&mut buf).unwrap();

        matrix_1_m.push(buf.trim().parse::<i32>().unwrap());
    }

    for index in 0..n {
        let mut output = 0;
        for element in 0..m {
            output += matrix_n_m[index][element] * matrix_1_m[element];
        }
        println!("{}", output);
    }
}



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

using namespace std;
typedef long long ll;

ll ans = 1e9;

void perform(ll p1, ll pa, ll pb){
  //pa < pb
  ll mn = pa * p1;
  ll mx = pa * p1;
  if(pb * p1 % 2 == 0){
    ll u = pb * p1 / 2;
    mn = min(mn, u);
    mx = max(mx, u);
    ans = min(ans, mx - mn);
    return;
  }
  else{
    if(pb > p1) swap(pb, p1);
    // so pb <= p1
    ll e = p1 / 2;
    ll u1 = e * pb; mn = min(mn, u1);
    ll u2 = (p1 - e) * pb; mx = max(mx, u2);
    ans = min(ans, mx - mn);
    return;
  }
}

int main(){
  ll h,w; cin >> h >> w;
  for(int i = 0; 2 * i <= h; i++){
    perform(w, i, h-i);
  }
  swap(h,w);
  for(int i = 0; 2 * i <= h; i++){
    perform(w, i, h-i);
  }
  cout << ans << "\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;

int n, m;
int a[305][305], b[305], c[305];
bool used[305];

bool C(int x) {
	fill(b, b+m+1, 0);
	fill(c, c+n, 0);
	fill(used, used+m+1, false);
	FOR(i, n) b[a[i][c[i]]]++;
	while (true) {
		bool ok = true;
		FOR(i, n) {
			if (b[a[i][c[i]]] > x) {
				used[a[i][c[i]]] = true;
				ok = false;
			}
		}
		if (ok) break;
		FOR(i, n) {
			if (used[a[i][c[i]]]) {
				while (used[a[i][c[i]]]) c[i]++;
				if (c[i] >= m) return false;
				b[a[i][c[i]]]++;
			}
		}
	}
	return true;
}

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	FOR(i, n) {
		FOR(j, m) cin >> a[i][j];
	}
	for (int i = 1; i <= n; i++) {
		if (C(i)) {
			cout << i << endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e5 + 5;
const ll LINF = 1e18 + 5;

int main()
{
 	ios::sync_with_stdio(false);
 	cin.tie(0);
 	string s;
	cin >> s;
	int a = s[0]-'0', b = s[1]-'0';
	int c = s[2]-'0', d = s[3]-'0';
	bool x = 0, y = 0;
	if(a*10+b<=12 && a*10+b>0) x = 1;
	if(c*10+d<=12 && c*10+d>0) y = 1;
	if(x&&y) cout << "AMBIGUOUS\n";
	else if(x) cout << "MMYY\n";
	else if(y) cout << "YYMM\n";
	else cout << "NA\n";
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <cmath>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
using P = pair<int, int>;

int main(){
  int n;
  cin >> n;
  vector<vector<int>> G(n);
  vector<P> vp;
  rep(i, n-1){
    int a, b;
    cin >> a >> b;
    a--, b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
    vp.emplace_back(a, b);
  }
  
  int k = 0;
  map<P, int> I;
  vector<int> cs(n, 0);
  
  vector<int> used(n, 0);
  queue<int> que;
  used[0] = 1;
  que.emplace(0);
  while(!que.empty()){
    int v = que.front(); que.pop();
    if (k < (int)G[v].size()) k = G[v].size();
    int cur = 1;
    for(int u : G[v]){
      if (used[u]) continue;
      if (cur == cs[v]) cur++;
      cs[u] = I[make_pair(u, v)] = I[make_pair(v, u)] = cur++;
      used[u] = 1;
      que.emplace(u);
    }
  }
  
  cout << k << endl;
  for(auto p : vp) cout << I[p] << endl;
  return 0;
}

Measured memory_bytes: 22932
n = int(input())
A = []
for ni in range(n):
    tmp = [int(i) for i in input().split()]
    A.append([[i, t] for i, t in enumerate(tmp) if t != -1])

INF = 2001
V = [i for i in range(n)]
T = [0]
ans = 0
while len(T) != n:
    w = [-1, INF]
    for t in T:
        for a in A[t]:
            if a[1] < w[1]:
                w = a
                p = t
    ans += w[1]
    T.append(w[0])
    for ni in range(n):
        for i in range(len(A[ni])):
            if w[0] == A[ni][i][0]:
                del A[ni][i]
                break
    for ni in range(n):
        for i in range(len(A[ni])):
            if A[ni][i][0] == p:
                del A[ni][i]
                break

print(ans)


Measured memory_bytes: 6448
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); i++)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
 
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
        return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

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

        vector<int> d(k);
        map<int, int> mp;
        rep (i, k) {
                int d; cin >> d;
                rep (j, d) {
                        int x; cin >> x;
                        mp[--x]++;
                }
        }

        int ans = 0;
        rep (i, n) {
                if (mp[i] == 0) ans++;
        }

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


Measured memory_bytes: 3632
N,M = list(map(int,input().split()))
H = list(map(int,input().split()))

good_ob = set(range(N))
for j in range(M):
    A,B = list(map(int,input().split()))
    A = A-1
    B = B-1
    if H[A]<H[B]:
        if A in good_ob:
            good_ob.remove(A)
    elif H[A]==H[B]:
        if A in good_ob:
            good_ob.remove(A)
        if B in good_ob:
            good_ob.remove(B)
    else:
        if B in good_ob:
            good_ob.remove(B)
    

print(len(good_ob))


Measured memory_bytes: 22320
n,m=map(int,input().split())
ac=0
wa=0

acl=[0]*n
wal=[0]*n

for i in range(m):
    p,s=input().split()
    p=int(p)-1
    
    if s=="AC":
        if acl[p]==0:
            acl[p]=1
            wa+=wal[p]
            ac+=1
        
    else:
        wal[p]+=1
        
print(ac, wa)

Measured memory_bytes: 4596
import math
n=int(input())
a=list(map(int,input().split()))

sum_a=sum(a)
left_a=0
right_a=sum_a
ans=200002*2020202020

for i in range(n):
    left_a+=a[i]
    right_a-=a[i]
    if(ans>abs(left_a-right_a)):
        ans=abs(left_a-right_a)
print(ans)

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

int main(){
  int N;
  double tmp;
  scanf("%d", &N);
  vector<double> material;
  while(cin >> tmp)
    material.push_back(tmp);

  sort(material.begin(), material.end());                //最も大きい値に対する/2の影響を最小に

  for(int i = 0; i < N-1; i++)                                             //試行回数はN(=material.size()) - 1　一致
    material[i+1] = (material[i] + material[i+1]) / 2;

  cout << material[N-1] << endl; 

}

Measured memory_bytes: 256
import sys
from collections import defaultdict
INF = 998244353
N = int(input())
dl = list(map(int, input().split()))
if dl[0] != 0:
    print(0)
    sys.exit()
d = defaultdict(int)

for i in range(N):
    d[dl[i]] += 1

d = sorted(d.items(), key=lambda x: x[0])

if d[0][1] != 1:
    print(0)
    sys.exit()

ans = 1
for i in range(len(d) - 1, 0, -1):
    if d[i][0] - 1 == d[i - 1][0]:
        ans *= (d[i - 1][1] ** d[i][1])
        ans = ans % INF
    else:
        print(0)
        sys.exit()

print(ans)

Measured memory_bytes: 21980
#include <stdio.h>

using namespace std;

int main(){
	int a,b;
	char op;
	while(true){
		scanf("%d %c %d",&a,&op,&b);
		if(op == '?') break;
		switch(op){
		case '+':
			printf("%d\n",a+b);
			break;
		case '-':
			printf("%d\n",a-b);
			break;
		case '/':
			printf("%d\n",a/b);
			break;
		case '*':
			printf("%d\n",a*b);
			break;
		}
	}
}



Measured memory_bytes: 2768
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(10);
}
signed main(){
  init_io();
  ll A,B,m,ans=100000000000,ma=100000000000,mb=1000000000000;
  cin >> A >> B >> m;
  vector<ll> a(A),b(B),x(m),y(m),c(m);
  for(int i=0;i<A;i++){
    cin >> a[i];
    ma = min(a[i],ma);
  }
  for(int i=0;i<B;i++){
    cin >> b[i];
    mb = min(b[i],mb);
  }
  ans = ma+mb;
  for(int i=0;i<m;i++){
    cin >> x[i] >> y[i] >> c[i];
    x[i]--;
    y[i]--;
    ll tmp = a[x[i]]+b[y[i]]-c[i];
    ans =min(tmp,ans);
  }
  cout << ans << endl;
}


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

int main() {
  double abs(double x);
  int n;
  cin >> n;
  int ain[n];
  vector<int> a;
  for (int i = 0; i < n; i++) {
    cin >> ain[i];
    a.push_back(ain[i]);
  }
  sort(a.begin(), a.end());
  double k = a[a.size() - 1] / 2.0;
  double sa = 3 * k;
  int temp;
  for (int i = 0; i < n; i++) {
    if (abs(a[i] - k) < sa) {
      temp = i;
      sa = abs(a[i] - k);
    }
  }
  cout << a[a.size() - 1] << " " << a[temp] << endl;
}

double abs(double x) {
  if (x > 0) {
    return x;
  } else {
    return -x;
  }
}


Measured memory_bytes: 1148
N,X = map(int,input().split())
towns = list(map(int,input().split()))
towns.append(X)
towns.sort()
town_diff = [0]*(len(towns)-1)
for i in range(len(towns)-1):
    town_diff[i] = towns[i+1]-towns[i]
town_diff.sort()
if(len(town_diff) == 1):
    gcd = town_diff[0]
elif(len(town_diff) == 2):
    a = town_diff[0]
    b = town_diff[1]
    while(True):
            t = b%a
            if(t == 0):
                gcd = a
                break
            b = a
            a = t
else:
    a = town_diff[0]
    b = town_diff[1]
    for i in range(len(town_diff)-2):
        while(True):
            t = b%a
            if(t == 0):
                gcd = a
                break
            b = a
            a = t
        a = gcd
        b = town_diff[i+2]
print(gcd)

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

int main(void) {
    int n,pm,pe,pj;
    while (cin>>n) {
        if (n==0) {
            break;
        } else {
            for (int i=0;i<n;i++) {
                cin>>pm>>pe>>pj;
                if (pm==100||pe==100||pj==100) {
                    cout<<"A"<<endl;
                } else if ( (pm+pe)/2>=90 ) {
                    cout<<"A"<<endl;
                } else if ( (pm+pe+pj)/3>=80 ) {
                    cout<<"A"<<endl;
                } else if ( (pm+pe+pj)/3>=70 ) {
                    cout<<"B"<<endl;
                } else if ( (pm+pe+pj)/3>=50 && (pm>=80||pe>=80) ) {
                    cout<<"B"<<endl;
                } else {
                    cout<<"C"<<endl;
                }
            }
        }
    }
}



Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
int main() {
   int n;
   cin >>n;
   vector<string>v;
   for(int i=1;i<=n;i++){
       string s;
       cin >>s;
     v.push_back(s);
   }
   sort(v.begin(),v.end());
   int cnt=n;
   for(int i=1;i<n;i++){
     //  cout << v[i] << endl;
       if(v[i]==v[i-1])cnt--;
   }
   //for(int i=1;i<=n;i++)cout << v[i] << endl;
   cout << cnt << endl;
    return 0;
}


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

int main() {
  string s1, s2, s3;
  cin >> s1 >> s2 >> s3;
  string ans = "";
  ans += toupper(s1.at(0));
  ans += toupper(s2.at(0));
  ans += toupper(s3.at(0));
  cout << ans << endl;
}


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

int main() {
  int N,K;
  cin >> N>>K;
  int c=1;//初期値

  for (int i = 0; i < N; i++) {
    if(c<K){//c=２倍する際の増加値
      c+=c;
  }
  else if(c>=K){
    c+=K;
  }
  }
    cout << c << endl;
}

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

signed main(){
	int A,B,M; cin>>A>>B>>M;
	vector<int> a(A),b(B);
	for(int i=0;i<A;i++)cin>>a[i];
	for(int i=0;i<B;i++)cin>>b[i];
	int ans=INT_MAX;
	for(int i=0;i<M;i++){
		int x,y,c; cin>>x>>y>>c; x--; y--;
		ans=min(ans,a[x]+b[y]-c);
	}
	ans=min(ans,*min_element(a.begin(),a.end())+*min_element(b.begin(),b.end()));

	cout<<ans<<endl;
}

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

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

   const double EPS = (1e-7);
   const ll INF =(1e13);
   const double PI = (acos(-1));
   const ll MOD = ll(1e9) + 7;

   #define REP(i, n) for(ll i = 0; i < (ll)(n); i++)
   #define REPR(i, n) for(ll i = n; i > -1; i--)
   #define FOR(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
   #define ALL(x) (x).begin(),(x).end()
   #define SORT(x) sort((x).begin(), (x).end())
   #define REVERSE(x) reverse((x).begin(), (x).end())
   #define SZ(x) ((ll)(x).size())
   #define pb push_back
   #define mp make_pair

   //chmax(a, b): a>bならaをbで更新　更新したときにtrueを返す
   //chmin(a, b): a<bならaをbで更新　更新したときにtrueを返す
   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 (b<a) { a=b; return 1; } return 0; }

   #define dump(x) cerr<< #x << "= " << (x) << endl;

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

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

int H, W, K;
vector<int> Fib = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55};

ll f(ll x){
    if (x >= 0) return Fib[x];
    else return 1;
}
ll S[10][10] = {};
ll ans[101][10] = {};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> H >> W >> K;
    FOR(i, 1, W + 1){
        S[i][i] = f(i - 1) * f(W - i);
        S[i][i - 1] = f(i - 2) * f(W - i);
        S[i][i + 1] = f(i - 1) * f(W - i - 1);
    }
    ans[0][1] = 1;
    REP(k, H){
        FOR(i, 1, W + 1){
            ans[k + 1][i] = ans[k][i - 1] * S[i-1][i] + ans[k][i] * S[i][i] + ans[k][i+1] * S[i+1][i];
            ans[k+1][i] %= MOD;
        }
    }
    cout << ans[H][K] << endl;


    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	private enum COLOR {WHITE,GRAY,BLACK};
	private static final int INFINITY = 1 << 30;
	
	public static void main(String[] args) throws IOException {
		new Main().run();
	}
	
	private void run() throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(reader.readLine());
		int[][] m = new int[n][n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			for (int j = 0; j < n; j++) {
				int weight = Integer.parseInt(st.nextToken());
				m[i][j] = weight==-1?INFINITY:weight;
			}
		}
		reader.close();
		System.out.println(prim(n, m));
	}

	private int prim(int n, int[][] m) {
		
		COLOR[] colors = new COLOR[n];
		int[] d = new int[n];
		int[] p = new int[n];
		for (int i = 0; i < n; i++) {
			colors[i] = COLOR.WHITE;
			d[i] = INFINITY;
			p[i] = -1;
		}
		
		d[0] = 0;
		while (true) {
			int minv = INFINITY;
			int u = -1;
			for (int i = 0; i < n; i++) {
				if (colors[i] == COLOR.BLACK) continue;
				if (minv > d[i]) {
					minv = d[i];
					u = i;
				}
			}
			if (u == -1) break;
			colors[u] = COLOR.BLACK;
			for (int v = 0; v < n; v++) {
				if (colors[v] == COLOR.BLACK) continue;
				if (m[u][v] == INFINITY) continue;
				if (d[v] > m[u][v]) {
					d[v] = m[u][v];
					p[v] = u;
				}
			}
		}
		int cost = 0;
		for (int i = 0; i < n; i++) {
			if (p[i] != -1) cost += m[i][p[i]];
		}
		return cost;
	}
}


Measured memory_bytes: 26932
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ull INF = (1LL << 63);
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)





int main() {
    ull n, k;
    cin >> n >> k;
    
    vector<ull> w(n), d(n);
    REP(i, n){
        cin >> w[i] >> d[i];
    }
    
    ull l = 0, r = INF, c = (l + r) / 2;
    while(r - l > 1){
        ull sum = 0;
        REP(i, n){
            if(w[i] <= c){
                sum += (c - w[i]) / d[i] + 1;
            }
        }
        if(sum < k){
            l = c;
        }
        else{
            r = c;
        }
        c = (l + r) / 2;
    }
    
    cout << c + 1 << endl;
}

Measured memory_bytes: 1792
// Date: 2020-03-13

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii;
#define FIO ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
#define per(i, b, a) for(int i = int(b); i >= int(a); --i)
#define mem(x, y) memset(x, y, sizeof(x))
#define all(x) (x).begin(),(x).end()
#define mk make_pair
#define pb push_back
#define fi first
#define se second
const LL INF = 1e18;
const LL mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10;
template <typename T> void chkmax(T &x, T y) { x = max(x, y); }
template <typename T> void chkmin(T &x, T y) { x = min(x, y); }
LL qpow(LL x, LL y, LL MOD) {LL a=1; while(y){ if(y&1) a=a*x%MOD; x=x*x%MOD; y>>=1; } return a;}

int a[N], dp[N];
int main() {
    FIO;
    int n, k;
    cin >> n >> k;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, k) rep(j, 1, n) {
        if(i < a[j]) break;
        if(!dp[i-a[j]]) {
            dp[i] = 1;
            break;
        }
    }
    if(dp[k]) cout << "First";
    else cout << "Second";

    return 0;
}

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

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

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod 1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

int main() {
  int ans[10001] = {};
  int z = 1000000;
  dep(i, 10000, 0) {
    int f = 0;
    dep(j, i - 1, 2) {
      if(i % j == 0) {
        f = 1;
        break;
      }
    }
    if(!f) {
      if(z - i == 2) ans[z] = 1;
      z = i;
    }
  }
  int n;
  while(cin >> n) {
    if(!n) return 0;
    dep(i, n, 0) {
      if(ans[i]) {
        cout << i - 2 << " " << i << endl;
        break;
      }
    }
  }
}

Measured memory_bytes: 3168
n = int(input())
l = []
for i in range(n):
    l.append([int(_) for _ in input().split()])
l = sorted(l, key=lambda x:x[1], reverse=True)
# print(l)
t = 0
ans = 'Yes'
for i in range(n):
    a,b  = l.pop()
    t += a
    if t > b:
        ans = 'No'
print(ans)

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

int N, M;

int main() {
    cin >> N >> M;
    bool from_one[N], to_N[N];
    for (int i = 0; i < N; i++) {
        from_one[i] = false;
        to_N[i] = false;
    }
    for (int i = 0; i < M; i++) {
        int a_in, b_in;
        cin >> a_in >> b_in;
        if (a_in == 1) from_one[b_in - 1] = true;
        if (b_in == N) to_N[a_in - 1] = true;
    }

    bool f = false;
    for (int i = 0; i < N; i++) {
        if (from_one[i] && to_N[i]) {
            f = true;
            break;
        }
    }

    if (f) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;

    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m;
	while(cin >> n >> m,n){
		int a,b,c,d;
		int co[m][m];
		int ti[m][m];
		for(int i = 0; i < m; i++)
			for(int j = 0; j < m; j++){
				co[i][j] = 100000000;
				ti[i][j] = 100000000;
			}
		for(int i = 0; i < n; i++){
			cin >> a >> b >> c >> d;
			a--; b--;
			co[a][b] = c;
			co[b][a] = c;
			ti[a][b] = d;
			ti[b][a] = d;
		}
		vector <int> used;
		vector <int> dist;
		int k,p,q,r;
		cin >> k;
		for(int i = 0; i < k; i++){
			cin >> p >> q >> r;
			p--; q--;
			used = vector <int> (m,100000000);
			dist = vector <int> (m,100000000);
			dist[p] = 0;
			while(1){
				int va = -1;
				for(int j = 0; j < m; j++)
					if(used[j] == 100000000 && (va == -1 || dist[va] > dist[j]))
						va = j;
				if(va == -1)
					break;
				used[va] = 1;
				for(int j = 0; j < m; j++)
					dist[j] = min(dist[j] , (r == 0 ? co[j][va] : ti[j][va]) + dist[va]);
			}
			cout << dist[q] << endl;
		}
	}
	return 0;
}

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

#define N_MAX 100
int N;
int D[N_MAX][2];

int input(){
    cin >> N;
    for (int i=0;i<N;i++){
        cin >> D[i][0] >> D[i][1];
    }
    return 0;
}

int solve(){
    int count = 0;
    for (int i=0;i<N-2;i++){
        if (D[i][0]==D[i][1]){
            if (D[i+1][0]==D[i+1][1]){
                if (D[i+2][0]==D[i+2][1]){
                    count = 1;
                }
            }
        }
    }

    if (count == 0){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
    return 0;
}

int main(){
    input();
    solve();
    return 0;
}

Measured memory_bytes: 3124
hN = {}
hM = {}
N,_=gets.chomp.split(' ').map{|n| n.to_i}
gets.chomp.split(' ').map{|n| n.to_i}.each{|n|
	hN[n].nil? ? hN[n]=1 : hN[n]+=1
}
M,_=gets.chomp.split(' ').map{|n| n.to_i}
gets.chomp.split(' ').map{|n| n.to_i}.each{|n|
	hM[n].nil? ? hM[n]=1 : hM[n]+=1
}
hM.each{|k,v|
	if(hN[k].nil? || hN[k] < hM[k])
		puts "NO"
		exit(0)
	end
}
puts "YES"


Measured memory_bytes: 57332