akhauriyash/Code-Regression huggingface dataset:
use proconio::marker::*;
use proconio::*;

fn main() {
    input! {
        h: usize,
        w: usize,
        k: usize,
        c: [Chars; h],
    };
    let mut row = vec![0; h];
    let mut col = vec![0; w];
    let mut mat = vec![vec![0; w]; h];
    let mut acc = 0;
    let mut ans = 0;

    for i in 0..h {
        for j in 0..w {
            let t = if c[i][j] == '#' { 1 } else { 0 };
            row[i] += t;
            col[j] += t;
            mat[i][j] = t;
            acc += t;
        }
    }

    let hg = 1usize << h;
    let wg = 1usize << w;

    for div_i in 0..hg {
        for div_j in 0..wg {
            let mut num = acc;
            let mut di = div_i;
            loop {
                let i = di.trailing_zeros() as usize;
                let mut dj = div_j;
                loop {
                    let j = dj.trailing_zeros() as usize;

                    if i < h && j < w {
                        num += mat[i][j];
                    }

                    if j >= w {
                        break;
                    }
                    dj &= dj - 1;
                }

                if i >= h {
                    break;
                }
                di &= di - 1;
            }

            let mut di = div_i;

            loop {
                let i = di.trailing_zeros() as usize;
                if i < h {
                    num -= row[i];
                }

                if i >= h {
                    break;
                }
                di &= di - 1;
            }

            let mut dj = div_j;
            loop {
                let j = dj.trailing_zeros() as usize;
                if j < w {
                    num -= col[j];
                }
                if j >= w {
                    break;
                }
                dj &= dj - 1;
            }

            if num == k {
                ans += 1;
            }
        }
    }

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


Measured memory_bytes: 2156
#include <iostream>

int main()
{
	int a, b;

	std::cin >> a >> b;
	
	if (a < 1 || a > 100 || b < 1 || b > 100) return 0;

	int area = a * b;
	int perimeter = a + a + b + b;
	std::cout << area << " " << perimeter << std::endl;

	return 0;
}


Measured memory_bytes: 3004
#include <stdio.h>

int N,M,P[100100],V[100100];

int find(int x)
{
	if (V[x] != x) V[x] = find(V[x]);
	return V[x];
}

int main()
{
	scanf ("%d %d",&N,&M);
	for (int i=1;i<=N;i++) scanf ("%d",&P[i]), V[i] = i;
	for (int i=0;i<M;i++){
		int x,y; scanf ("%d %d",&x,&y);
		x = find(x); y = find(y);
		V[x] = y;
	}
	
	int A = 0;
	for (int i=1;i<=N;i++) if (find(i) == find(P[i])) A++;
	printf ("%d\n",A);

	return 0;
}

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

const int mod1 = 1e9 + 7;
const int mod2 = 998244353;

struct Combination
{
	using ll = int_fast64_t;

	int mod;
	vector<ll> mfact, rfact;

	Combination(int sz, int mod) : mfact(sz + 1), rfact(sz + 1), mod(mod)
	{
		mfact[0] = 1LL;
		for (int i = 1; i < sz + 1; i++)
		{
			mfact[i] = mfact[i - 1] * i % mod;
		}

		rfact[sz] = inv(mfact[sz]);

		for (int i = sz - 1; i >= 0; i--)
		{
			rfact[i] = rfact[i + 1] * (i + 1) % mod;
		}
	}

	ll fact(int k) const
	{
		return mfact[k];
	}

	ll pow(ll x, ll n) const
	{
		ll ret = 1LL;
		while (n > 0)
		{
			if (n & 1)
				(ret *= x) %= mod;
			(x *= x) %= mod, n >>= 1;
		}
		return ret;
	}

	ll inv(ll x) const
	{
		return pow(x, mod - 2);
	}

	ll Perm(int n, int r) const
	{
		if (r < 0 || n < r)
			return 0LL;
		return mfact[n] * rfact[n - r] % mod;
	}

	ll Binom(int p, int q) const
	{
		if (q < 0 || p < q)
			return 0LL;
		return mfact[p] * rfact[q] % mod * rfact[p - q] % mod;
	}
};

int main()
{
	int N, M;
	cin >> N >> M;
	Combination comb(M, mod1);
	ll ans = comb.Perm(M, N) * comb.Perm(M, N) % mod1;
	for (int k = 1; k <= N; k++)
	{
		int sgn = k % 2 == 0 ? -1 : 1;
		ll s = (comb.Binom(N, k) * comb.Perm(M - k, N - k) % mod1) * comb.Perm(M, N) % mod1;
		ans -= sgn * s;
		(ans += mod1) %= mod1;
	}

	cout << ans << "\n";
}


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

using namespace std;

#define pb push_back
#define mp make_pair
#define MOD ((int)(1e9) + 7)
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
const int N = ((int)1e5) + 5;
const int M = ((int)1e3) + 5;
const int mod = 2019;

long long int l,r;

int main ()
{
	fast;
	cin >> l >> r;

	if (r - l >= 2019)
		return cout << 0,0;
	int a = INT_MAX;
	l = l % 2019;
	r = r % 2019;
	for (int i = l; i <= r - 1; i++)
	{
		for (int j = i + 1; j <= r; j++)
		{
			a = min(a,(i * j) % mod);
		}
	}
	cout << a;
}

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


int main()
{
 int n;
 cin>>n;
 int arr[n];
 for(int i=0; i<n; i++)
    cin>>arr[i];
 ll cost = 0, leftMax = 0;
 for(int i=0; i<n; i++){
    if(arr[i] > leftMax)
        leftMax = arr[i];
    cost += max(0LL, leftMax-arr[i]);
 }
 cout<<cost;
 return 0;
}



Measured memory_bytes: 4372
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 1000000000000000
#define endl '\n'
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;

int n;
vector<int> G[100100];
vector<int> dist;
vector<int> way;

void find_way(int v){
    way.push_back(v);
    if(v==0)return;
    rep(i,G[v].size())if(dist.at(G[v].at(i))<dist.at(v))find_way(G[v].at(i));
}

int count(int v, int u){
    if(G[v].size()==1)return 1;
    int cnt=1;
    rep(i,G[v].size())if(G[v].at(i)!=u)cnt+=count(G[v].at(i),v);
    return cnt;
}

signed main(){
    
    cin>>n;
    rep(i,n-1){
        int a,b; cin>>a>>b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    dist=vector<int>(n,-1);
    dist.at(0)=0;
    queue<int> que;
    que.push(0);
    while(que.size()){
        int p=que.front(); que.pop();
        rep(i,G[p].size()){
            if(dist.at(G[p].at(i))==-1){
                dist.at(G[p].at(i))=dist.at(p)+1;
                que.push(G[p].at(i));
            }
        }
    }
    
    find_way(n-1);
    reverse(all(way));
    int mid=way.at((way.size()-1)/2),mid2=way.at((way.size()+1)/2);
    int cnt=count(mid,mid2);
    cout<<(cnt>n-cnt?"Fennec":"Snuke")<<endl;
    
}

Measured memory_bytes: 10484
#include<bits/stdc++.h>
#define mod 1000000007
#define mx 10005
//#define y 3
using namespace std;
typedef  long long int ll;
#define  f(i, n) for(int i = 0; i < n; ++i)
#define pb push_back
struct re{
    int ind;
    string s;
    int no;
    inline bool operator < (const auto &other){
        if(s != other.s)return s < other.s;
        return no > other.no;
    }
};
void input(){
    int n;cin>>n;
 vector<re>a(n);
 f(i, n){
     string p; int q;
    cin >> p >> q;
    a[i]. ind = i + 1;
    a[i]. s= p;
    a[i]. no =q;
 }
 sort(a.begin(), a.end());
 f(i, n) cout << a[i].ind <<endl;
}
int main(){
    input();
    return 0;
}



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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } 
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#define ll long long 
#define INF 999999999
#define rep(i,n) for(int i=0;i<n;i++)
using Graph = vector<vector<int>>;
queue<int> quex,quey;
const int MOD = 1000000007;




int main(){
    
    int a,b,c;  cin >> a >> b >>c;
    if(a+b+c>=22)   cout << "bust" << endl;
    else cout << "win" << endl;


}

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] origin = new int[10];
        int[] s = new int[11];
        int[] t = new int[11];

        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            int posS = 0;
            int posT = 0;

            s[0] = -1;
            t[0] = -1;

            for (int j = 1; j < 11; j++) {
                s[j] = 0;
                t[j] = 0;
            }

            String[] line = br.readLine().split(" ");
            boolean result = true;

            for (int j = 0; j < 10; j++) {
                origin[j] = Integer.parseInt(line[j]);
            }

            for (int j = 0; j < 10; j++) {
                if (origin[j] > s[posS]) {
                    // sで受け入れ可
                    if (origin[j] > t[posT]) {
                        // sでもtでも受け入れ可
                        if (s[posS] < t[posT]) {
                            posT++;
                            t[posT] = origin[j];
                        } else {
                            posS++;
                            s[posS] = origin[j];
                        }
                    } else {
                        // sのみで受け入れ可
                        posS++;
                        s[posS] = origin[j];
                    }
                } else if (origin[j] > t[posT]) {
                    // tのみで受け入れ可
                    posT++;
                    t[posT] = origin[j];
                } else {
                    // sでもtでも受け入れ不可
                    result = false;
                    break;
                }

            }

            if (result) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }

        } // end of for

    }
}


Measured memory_bytes: 24236
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

typedef long long ll;

template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

ll solve(const ll m, const ll n) {
    queue<ll> q2;
    queue<ll> q3;
    queue<ll> q5;

    // 1 is always included.
    ll count = 0;
    q2.push(1);

    while (1) {
        ll cand;
        if (q2.size() > 0) cand = q2.front();
        if (q3.size() > 0) cand = min(cand, q3.front());
        if (q5.size() > 0) cand = min(cand, q5.front());

        if (q2.front() == cand) {
            q2.pop();
            q2.push(2 * cand);
            q3.push(3 * cand);
            q5.push(5 * cand);
        } else if (q3.front() == cand) {
            q3.pop();
            q3.push(3 * cand);
            q5.push(5 * cand);
        } else {
            q5.pop();
            q5.push(5 * cand);
        }

        if (m <= cand && cand <= n) {
            count++;
        }
        if (cand > n) {
            break;
        }
    }

    return count;
}

int main(void) {
    ll m, n;

    while (1) {
        cin >> m;
        if (m == 0) return 0;
        cin >> n;

        cout << solve(m, n) << endl;
    }
    
    return 0;
}



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

int main() {
  int N,A,B;
  cin >> N >> A >> B;
  int x,P;
  P=N*A;
  if (P >= B){
    x = B;
  }
  else {
    x = P;
  }
  cout << x << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long 
#define hell 1000000007
#define F first
#define re 15000000
#define S second
#define pb push_back
#define all(a)  (a).begin(),(a).end()
#define rep(i,a,b) for(ll int i = a;i<b;i++)
#define pi 3.1415926536
#define Mod 998244353
//char a[2000][2000];
using namespace std;
bool check(ll m,ll k,ll n,ll a ,ll b){
  ll rem = n-m;
  if( k > rem*b + a*m)
      return 1;
  else
    return 0;

}
int main()
{   
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);            
    //std::setprecision(20);    
    int tests=1;
      //freopen("input.txt", "r", stdin);   
    //cin>>tests;
  while(tests--)
    { 
        int n;
        cin>>n;
        ll a[n];
        for(int i = 0;i<n;i++)
          cin>>a[i];
        sort(a,a+n);
        //cout<<a[n/2-1]<<" "<<a[n/2];
        cout<<a[n/2]-a[n/2-1];
    }
    
}

Measured memory_bytes: 1152
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <utility>
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int MOD = 1e9 + 7;
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

int main() {
    ll x; cin >> x;
    ll ans = 0;
    int y = x % 500;
    ans = x / 500 * 1000 + y / 5 * 5;
    cout << ans << endl;
	return 0;
} 

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

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L

#define long long long int

using namespace std;

// @author: pashka

vector<vector<int>> g;
vector<int> used;
vector<pair<int, int>> res;
vector<int> par;

void dfs(int x, int p) {
    used[x] = 1;
    for (int i = 0; i < g[x].size(); i++) {
        int y = g[x][i];
        if (y == p) continue;
        if (used[y] == 1) {
            res.push_back({x, y});
            par[x] ^= 1;
        } else if (used[y] == 0){
//            cout << x << "->" << y << "\n";
            dfs(y, x);
            if (par[y]) {
                res.push_back({y, x});
                par[y] ^= 1;
            } else {
                res.push_back({x, y});
                par[x] ^= 1;
            }
        }
    }
    used[x] = 2;
}

int main() {
    std::ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    g.resize(n);
    used.resize(n);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--;y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    par.resize(n);
    for (int i = 0; i < n; i++) {
        if (used[i] == 0) {
            dfs(i, -1);
            if (par[i]) {
                cout << "-1";
                return 0;
            }
        }
    }
    for (auto e : res) {
        cout << e.first + 1 << " " << e.second + 1 << "\n";
    }
    return 0;
}

Measured memory_bytes: 17908
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <cstring>
#include <queue>
#include <iomanip>
#include <numeric>
#include <cmath>

using namespace std;

//#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

typedef long long ll;

//static const ll MOD = 1000000007;

int main() {
    ll N, answer = 0;

    // input
    cin >> N;
    vector<ll> A, B, C;
    for (ll i = 0; i < N; i++) {
        ll a;
        cin >> a;
        A.emplace_back(a - 1);
    }
    for (ll i = 0; i < N; i++) {
        ll b;
        cin >> b;
        B.emplace_back(b);
    }
    for (ll i = 0; i < N - 1; i++) {
        ll c;
        cin >> c;
        C.emplace_back(c);
    }

    // process
    for (ll i = 0; i < N; i++) {
        answer += B[A[i]];
        if (i >= 1 && A[i] == A[i - 1] + 1) {
            answer += C[A[i-1]];
        }
    }

    cout << answer << endl;

    return 0;
}

Measured memory_bytes: 256
/*??????????????????????????£???(Christmas Party)*/
#include <stdio.h>
int main(){
  int i, j, x, y, N, M;
  int A[100] = {0};
  int B[100][100] = {0};
  int data[100] = {0};
  scanf("%d %d", &N, &M);
  for (i = 1; i - 1 < M; i++) {
    scanf("%d", &A[i - 1]);
  }
  for (i = 1; i - 1 < M; i++) {
    for (j = 1; j - 1 < N; j++) {
      scanf("%d", &B[i - 1][j - 1]);
    }
  }
  for (i = 1; i - 1 < M; i++) {
    x = 0;
	y = A[i - 1];
    for (j = 1; j - 1 < N; j++) {
      if (A[i - 1] == B[i - 1][j - 1]) {
        data[j - 1]++;
          x++;
      }
    }
    data[y - 1] += N - x;
  }
  for (j = 1; j - 1 < N; j++) {
    printf("%d\n", data[j - 1]);
  }
  return 0;
}

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

using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, __VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

#define MOD 1000000007
#define INF 1000000000
#define MAX_N 100010
#define MAX_S 8010

string S;
ll X, Y;

// S を分解したもの
vector<ll> queryX;   // X 方向で処理すべき F の連続
vector<ll> queryY;

#define DP

#ifdef DP
bool dpX[MAX_S][MAX_S*2] = {};
bool dpY[MAX_S][MAX_S*2] = {};
#else
// i 番目の queryX を処理していて、現在地が pos のときたどり着けるか
bool dfsX(ll i, ll pos) {
    if(i >= queryX.size()) {
        if(pos == X) { return true; }
        else { return false; }
    }
    if(i == 0) {
        if (dfsX(i + 1, pos + queryX[i])) { return true; }
    } else {
        if (dfsX(i + 1, pos + queryX[i]) || dfsX(i + 1, pos - queryX[i])) { return true; }
    }
    return false;
}

bool dfsY(ll i, ll pos) {
    if(i >= queryY.size()) {
        if(pos == Y) { return true; }
        else { return false; }
    }
    if (dfsY(i + 1, pos + queryY[i]) || dfsY(i + 1, pos - queryY[i])) { return true; }
    return false;
}
#endif

int main()
{
    cin >> S >> X >> Y;

    // 正解と初期位置の正規化
    X += MAX_S; Y += MAX_S;

    // query の作成
    bool isX = true;
    ll len = 0;
    REP(i, S.length()) {
        if(S[i] == 'T') {
            if(isX) {
                queryX.push_back(len);
                isX = false;
            }
            else {
                queryY.push_back(len);
                isX = true;
            }
            len = 0;
        } else {
            len++;
        }
    }
    if(isX) { queryX.push_back(len); }
    else { queryY.push_back(len); }

#ifdef DP
    for(ll i = MAX_S - 1; i >= 0; --i) {
        for(ll pos = 0; pos < MAX_S * 2; ++pos) {
            // X
            if(i >= queryX.size()) {
                if(pos == X) { dpX[i][pos] = true; }
                else { dpX[i][pos] = false; }
            }
            else if(i == 0) {
                dpX[i][pos] = dpX[i + 1][pos + queryX[i]];
            } else {
                dpX[i][pos] = (dpX[i + 1][pos + queryX[i]] || dpX[i + 1][pos - queryX[i]]);
            }
            // Y
            if(i >= queryY.size()) {
                if(pos == Y) { dpY[i][pos] = true; }
                else { dpY[i][pos] = false; }
            } else {
                dpY[i][pos] = (dpY[i + 1][pos + queryY[i]] || dpY[i + 1][pos - queryY[i]]);
            }
        }
    }

    if(dpX[0][MAX_S] && dpY[0][MAX_S]) { printf("Yes\n"); }
    else { printf("No\n"); }
#else
    if(dfsX(0, MAX_S) && dfsY(0, MAX_S)) { printf("Yes\n"); }
    else { printf("No\n"); }
#endif

    return 0;
}


Measured memory_bytes: 251008
#include <iostream>

using namespace std;
using ll = long long;

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

int main() {
  string s;
  cin >> s;
  rep(i, s.length()) { cout << 'x'; }
  cout << '\n';
  return 0;
}


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

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

    ll n,m;
    cin >> n >> m;
    vector<ll> a(m);
    vector<ll> b(m);
    for (ll i = 0;i < m;i++){
        cin >> a[i] >> b[i];
    }
    bitset<200000> s;
    bitset<200000> g;

    for (ll i = 0; i < m; i++){
        if (a[i] == 1){
            s.set(b[i], 1);
        }
        if (b[i] == n){
            g.set(a[i], 1);
        }
    }
    
    if ((s&g) != 0){
        cout << "POSSIBLE" << endl;
    }
    else{
        cout << "IMPOSSIBLE" << endl;
    }
}

Measured memory_bytes: 6304
// 2008AWAnæ\IF : Traveling Cube
#include <iostream>
#include <queue>
#include <string>
#include <cstring>

using namespace std;

class Node{
public:
	int x, y, p, d0, d1, c;
	Node(int x, int y, int p, int d0, int d1, int c) : x(x), y(y), p(p), d0(d0), d1(d1), c(c) {}
};

char dx[] = {-1,1,0,0};
char dy[] = {0,0,-1,1};
// TCRÌÊÌJÚsñ
char dice[6][4] = {
	{5,2,1,4}, {1,1,3,0}, {0,3,2,2},
	{2,5,4,1}, {4,4,0,3}, {3,0,5,5}
};
char side[] = {1,2,4,5};
// ÊÔÍCãC¶C³ÊCºCECwÊÌ
char dice_color[6] = {'r','y','m','c','b','g'};

char getUpper(int a, int b){
	// a(úóÔÅã)ÊªãÉ éD
	if(a == 0) return dice_color[0];
	// b(úóÔÅ¶)ÊªãÉ éD
	if(b == 0) return dice_color[1];
	// aÊªºÉ é
	if(a == 3) return dice_color[3];
	// bÊªºÉ é
	if(b == 3) return dice_color[4];
	return (b-a+6)%6 < 3 ? dice_color[2] : dice_color[5];
}

int main(){
	int w, d;
	string path;
	string mp[30];
	while(cin >> w >> d, w){
		for(int i=0;i<d;i++) cin >> mp[i];
		cin >> path;
		int sx, sy = -1;
		for(int i=0;i<d&&sy<0;i++)
			sx = i, sy = mp[i].find('#');
		// `FbNÏÝÌóÔÌÇp
		bool visit[30][30][6][6][6];
		memset(visit, false, sizeof(visit));
		queue<Node> qu; qu.push(Node(sx,sy,0,0,1,0));
		int ans = -1;
		while(!qu.empty()){
			Node nd = qu.front(); qu.pop();
			int x = nd.x, y = nd.y, p = nd.p, d0 = nd.d0, d1 = nd.d1, c = nd.c;
			// Ft«}Xð·×ÄÊsµ½
			if(p == 6){ ans = c; break; }
			if(visit[x][y][p][d0][d1]) continue;
			visit[x][y][p][d0][d1] = true;
			for(int i=0;i<4;i++){
				int nx = x+dx[i], ny = y+dy[i], nd0 = dice[d0][i], nd1 = dice[d1][i];
				// tB[hOÉoé©C}XÉÚ®µÄµÜ¤Æ«
				if(nx<0||d<=nx||ny<0||w<=ny||mp[nx][ny]=='k') continue;
				// FÂ«}XÉæÁ½Æ«
				if(mp[nx][ny]!='w'&&mp[nx][ny]!='#'){
					// ãÊÌFÆêvµC©Â¡ÚwµÄ¢éFÅ éÆ«
					if(mp[nx][ny]==getUpper(nd0,nd1)&&mp[nx][ny]==path[p])
						qu.push(Node(nx,ny,p+1,nd0,nd1,c+1));
				}
				// }XÖÌÚ®
				else
					qu.push(Node(nx,ny,p,nd0,nd1,c+1));
			}
		}
		// ans = -1ÌÜÜÈçBÍ³
		ans==-1 ? puts("unreachable") : printf("%d\n", ans);
	}
}

Measured memory_bytes: 1204
#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{
   cout << "Sunny" <<endl;
 }
}

Measured memory_bytes: 3496
import java.util.*;

public class Main {

    private static void nCombination3(int c) {
        int count = c;
        int num = 0;
        for (int i = 0; i < count - 2; i++) {
            for (int j = i + 1; j < count - 1; j++) {
                for (int k = j + 1; k < count; k++) {
                    num++;
                }
            }
        }
    }

    public static void main(String[] args) {
        // write your code here
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        char[] S=sc.next().toCharArray();
        long ans = 0;
        for(int i=0;i<=999;i++){
            char[] temp = String.format("%03d",i).toCharArray();
            int k=0;
            for(int j=0;j<N;j++){
                if(k<3&&S[j]==temp[k]){
                    k++;
                }
            }
            if(k==3){
                ans++;
            }

        }
        System.out.println(ans);

    }
}


Measured memory_bytes: 28292
use std::io::Read;

fn main() {
    let n = get::<usize>() + 1;
    let m = get::<usize>() + 1;
    let q = get::<usize>();
    let mut s = vec![vec![0; m]; n];
    for i in 1..n {
        let t: Vec<_> = get_word().chars().map(|x| (x as u8 - 0x30) as i32).collect();
        for j in 1..m {
            s[i][j] = t[j - 1];
        }
    }
    let mut bit = vec![vec![0; m]; n];
    let mut sid = vec![vec![0; m]; n];
    let mut ver = vec![vec![0; m]; n];
    for i in 1..n {
        for j in 1..m {
            bit[i][j] = bit[i-1][j] + bit[i][j-1] - bit[i-1][j-1] + s[i][j];
            sid[i][j] = sid[i-1][j] + sid[i][j-1] - sid[i-1][j-1] + if s[i][j] == 1 && s[i][j-1] == 1 {1} else {0};
            ver[i][j] = ver[i-1][j] + ver[i][j-1] - ver[i-1][j-1] + if s[i][j] == 1 && s[i-1][j] == 1 {1} else {0};
        }
    }
    for _ in 0..q {
        let x1 = get::<usize>() - 1;
        let y1 = get::<usize>() - 1;
        let x2 = get::<usize>();
        let y2 = get::<usize>();
        let a = bit[x2][y2] - bit[x2][y1] - bit[x1][y2] + bit[x1][y1];
        let b = sid[x2][y2] - sid[x2][y1+1] - sid[x1][y2] + sid[x1][y1+1];
        let c = ver[x2][y2] - ver[x2][y1] - ver[x1+1][y2] + ver[x1+1][y1];
        println!("{}", a - b - c);
    }
}

fn get_word() -> String {
    let mut stdin = std::io::stdin();
    let mut u8b: [u8; 1] = [0];
    loop {
        let mut buf: Vec<u8> = Vec::with_capacity(16);
        loop {
            let res = stdin.read(&mut u8b);
            if res.unwrap_or(0) == 0 || u8b[0] <= b' ' {
                break;
            } else {
                buf.push(u8b[0]);
            }
        }
        if buf.len() >= 1 {
            let ret = String::from_utf8(buf).unwrap();
            return ret;
        }
    }
}

fn get<T: std::str::FromStr>() -> T { get_word().parse().ok().unwrap() }

Measured memory_bytes: 71420
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <numeric>
#include <cstdlib>
#include <map>
#include <algorithm>

using namespace std;

int main(){
    int N,M;

    map<string, int> B;
    map<string, int> R;

    cin >> N;

    for(int i = 0; i < N; i++){
        string s;
        cin >> s;
        B[s]++;
    }

    cin >> M;

    for(int i = 0; i < M; i++){
        string s;
        cin >> s;
        R[s]++;
    }

    vector<string> key;

    for(auto itr = B.begin(); itr != B.end(); itr++){
        key.push_back(itr->first);
    }

    int ans = -101;

    for(int i = 0; i < key.size(); i++){
        int now = B[key[i]] - R[key[i]];
        ans = max(ans, now);
    }

    if(ans < 0){
        cout << 0 << endl;
        return 0;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
/*
 * :(
 * You taught me so much, I'm not scared anymore
 * 	I have to left go your hands that are holding me
 * 	 Even if I'm alone, I'll go on, even if it hurts
 * 	  I'll never forget the dream, I shared with you
 * 	   I'm glad to be with everyone, I'm glad to have been with everyone
 * 	    But on the morning when I wake up, no one is there
 */
//#define opti
#ifdef opti
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#endif
#ifndef opti
#pragma GCC optimize("O3")
#endif
#include <bits/stdc++.h>
using namespace std;
#ifndef rd
//#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
#define double long double
#define pii pair<int,int>
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define all(con) con.begin(),con.end()
#define shuffle(a,b) random_shuffle(a,b,rng)
#define deb cout<<"Line: "<<__LINE__<<" pls "
typedef long long ll;
const ll mod=1000000007;
const ll inf=1e18;
//const ll mod=998244353;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll powm(ll a, ll b, ll m);

int a[101];
void solve()
{
	int n;
	cin>>n;
	int sum=0;
	fr(i,0,n-1){
		cin>>a[i];
		sum+=a[i];
	}
	int ind=0;
	for(int i=0; i<n; i++)
		if(abs(sum-a[i]*n)<abs(sum-a[ind]*n))
			ind=i;
	cout<<ind<<endl;
}
signed main()
{
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	srand(chrono::steady_clock::now().time_since_epoch().count());
	#ifdef rd
		clock_t clk = clock();
	#endif
	int t=1;
//	cin>>t;
	while(t--)
		solve();
	#ifdef rd
		clk = clock() - clk;
		cout<<endl<<endl<< "Time Elapsed: " << fixed << setprecision(10) << ((double)clk)/CLOCKS_PER_SEC <<endl;
	#endif
	return 0;
}
ll powm(ll a,ll b, ll m)
{
	ll te=1;
	while(b)
	{
		if(b&1)
			te=(te*a)%m;
		a=(a*a)%m;
		b>>=1;
	}
	return te;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
  int N, A, B, C, D;
  cin >> N >> A >> B >> C >> D;
  --A, --B, --C, --D;
  string S;
  cin >> S;
  bool cond = S.substr(A,C-A+1).find("##") == string::npos;
  cond &= S.substr(B,D-B+1).find("##") == string::npos;
  if (D < C) cond &= S.substr(B-1,D-B+3).find("...") != string::npos;
  cout << (cond ? "Yes" : "No") << endl; 
}


Measured memory_bytes: 3700
class Point
  attr_reader :x, :y

  def initialize(x, y)
    @x = x
    @y = y
  end
  def to_s
    "(#{x},#{y})"
  end

  def dist_from_origin
    x.abs + y.abs
  end

  # 腕を減算し、その腕の方向を返す
  def sub_len(len)
    x_abs = @x.abs
    y_abs = @y.abs
    if y_abs <= x_abs
      if 0 <= @x
        @x -= len
        "R"
      else
        @x += len
        "L"
      end
    else
      if 0 <= @y
        @y -= len
        "U"
      else
        @y += len
        "D"
      end
    end
  end
end

def calc_arms(dist)
  arms = []
  # 偶数は面倒なので最初に1引いておく
  arms << 1 if dist.even?
  dist -= 1

  # armは [1, 2, 4, ..., longest_arm] を取り揃える。
  #   dist = longest_arm * 2 - 1
  # までは届く。
  # 最初に追加した1を加えると,
  #   dist = longest_arm * 2
  # まで届く。
  longest_arm = 1
  arms << 1
  while true
    next_arm = longest_arm * 2
    break if dist < next_arm

    longest_arm = next_arm
    arms << longest_arm
  end
  arms
end

def main
  n = gets.chomp.to_i

  is_odd = nil  # 偶数奇数チェック ※すべての距離が偶数 or 奇数 で揃っていないとNG
  max_dist = 0  # 原点からの最長距離
  points = Array.new(n)
  n.times do |i|
    xy = Point.new *gets.split.map(&:to_i)
    dist = xy.dist_from_origin
    max_dist = dist if max_dist < dist
    if is_odd.nil?
      is_odd = dist.odd?
    elsif is_odd != dist.odd?
      puts "-1"
      return
    end

    points[i] = xy
  end
  # puts points

  # armセットを作り上げる
  arms = calc_arms(max_dist).reverse
  puts arms.length
  puts arms.join(" ")

  # 問題を解いていく
  points.each do |p|
    arm_dirs = []

    arms.each do |arm|
      arm_dirs << p.sub_len(arm)
    end

    puts arm_dirs.join
  end
end

if __FILE__ == $0
  main
end


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

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

    int n = s.size();
    int cnt = 0;

    if (n == 1) {
        cout << 1 << endl;
    }
    else {
        bool is_same = false;
        for (int i = 1; i < n; i++) {
            if (is_same == false) {
                if (s[i - 1] == s[i]) {
                    cnt++;
                    i++;
                    is_same = true;
                }
            }
            else {
                is_same = false;
            }
        }

        int k = n - cnt;

        cout << k << endl;
    }

    return 0;
}


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

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

//------------------------------------------------
int main(){
  int n,a;
  cin>>n>>a;
  if(n<a) cout<<0<<endl;
  if(n>=a) cout<<10<<endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, K, len = 0;
  cin >> N >> K;
  
  for(int i = 0; i < N; i++){
    int dis1, dis2;
    cin >> dis1;
     
    dis2 = K - dis1;
    
    if(dis1 < dis2){
      len += dis1;
    }else{
      len += dis2;
    }
  }
  
  cout << len * 2 << endl;
    
}

Measured memory_bytes: 256
while True:
  m,f,r = map(int,input().split())
  #m,f,r = 50, 40, 30
  s = m + f
  
  if m == -1 and f == -1:
  	break

  if m == -1 or f == -1:
  	grade = 'F'
  elif s >= 80:
  	grade = 'A'
  elif s >= 65 and s < 80:
  	grade = 'B'
  elif s >=50 and s < 65:
  	grade = 'C'
  elif s >=30 and s < 50:
  	grade = 'D'
  	if r >= 50:
  		grade = 'C'
  else:
  	grade = 'F'

  print(grade)



Measured memory_bytes: 5592
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main(void){
    for(;;){
        int n;
        cin>>n;
        if(n==0)break;
        int a[10010]={0};
        int b;
        for(int i=0;i<n;i++){
            cin>>b;
            a[b]++;

        }
        for(int i=0;i<10;i++){
            if(a[i]==0)cout<<"-";
            else for(int j=0;j<a[i];j++)cout<<"*";
            cout<<endl;

        }

    }
	return 0;
}

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

#define REP(i,n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> pint;
template <class T> inline void chmax(T &a, const T b) { a = max(a, b); }
template <class T> inline void chmin(T &a, const T b) { a = min(a, b); }
template <class T> void pp(T v, int n) { REP(i,n) cout<<v[i]<< ' '; cout << endl; }

void inline TorF(bool tf, const string &trueMessage, const string &falseMessage) {
  cout << (tf ? trueMessage : falseMessage) << endl;
}
void inline YESNO(bool tf) { TorF(tf, "YES", "NO"); }
void inline YesNo(bool tf) { TorF(tf, "Yes", "No"); }

int main() {
  int N, M; cin>>N>>M;
  int L, R; cin>>L>>R;
  for(int i = 2; i <= M; i++) {
    int	l, r; cin>>l>>r;
    chmax(L, l);
    chmin(R, r);
  }
  int ans = max(0, R-L+1);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define fi first
#define se second
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define rep11(i, n) for (int i = 1; i < (int)(n); ++i)
#define repo(i, o, n) for (int i = o; i < (int)(n); ++i)
#define repm(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1002000007
#define INF LONG_LONG_MAX
int main(){
    ll n,k;
    cin>>n>>k;
    ll p[n];
    double ex[n];
    double ans=0;
    rep(i,n) cin>>p[i];
    rep(i,n){
        rep1(j,p[i]){
        ex[i]+=((float)(1.0/p[i]))*float(j);
        }
    }
    
    for(int i=0; i<k; i++){
        ans+=ex[i];
    }
    ll mx_i=k-1;
    double an=ans;
    for(int i=k; i<n; i++){
        an=an+ex[i]-ex[i-k];
        ans=max(ans,an);
    }
    cout << std::fixed;
    cout << std::setprecision(12)<<ans<<endl;
    
    return 0;
}

Measured memory_bytes: 3328
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using System.IO;

namespace AtCoder.XXX.B
{ 
    public class Program
    {
        public static void Main(string[] args)
        {
            var datas = cr();
            var n = datas[0];
            var a = datas[1];
            var b = datas[2];
            var result = 0;
            for(var i = 0;i< n+1;i++)
			{
                var sum = 0;
                foreach(var s in i.ToString())
				{
                    sum += int.Parse(s.ToString());

                }

                if (sum >= a && sum <= b)
				{
                    result += i;
				}
			}
            P(result);
        }

        private static StreamReader sr;
        public static int[] Ecr()
        {
            if (sr == null)
            {
                sr = new StreamReader("input.txt", Encoding.GetEncoding("UTF-8"));
            }
            return sr.ReadLine().Split().Select(int.Parse).ToArray();
        }
        public static string Er()
        {
            if (sr == null)
            {
                sr = new StreamReader("input.txt", Encoding.GetEncoding("UTF-8"));
            }
            return sr.ReadLine();
        }
        public static string r()
        {
            return Console.ReadLine();
        }
        public static  int[] cr()
        {
            return Console.ReadLine().Split().Select(int.Parse).ToArray();
        }
        public static int cri()
        {
            return int.Parse(Console.ReadLine());
        }
        public static void P(string str)
        {
            Console.WriteLine(str);
        }
        public static void P(int num)
        {
            P(num.ToString());
        }
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long a,b,c;cin >> a >> b >> c;
    if (c==1)cout << b-a+1;
    else if (a%c==0)cout << (b/c)-(a/c)+1;
    else cout << (b/c)-(a/c);

    
}


Measured memory_bytes: 3624
#include<stdio.h>
#include<algorithm>
using namespace std;
main()
{
    long n,i,k;
    scanf("%ld",&n);
    long a[n+3],s[n+3];a[0]=0;s[0]=0;
    for(i=1;i<=n;i++)
        scanf(" %ld",&a[i]);
    sort(a,a+n+1);
    for(i=1;i<=n;i++)
        s[i]=s[i-1]+a[i];
    for(i=n-1;i>=0;i--)
    {
        if(s[i]*2<a[i+1])
        {
            printf("%ld",n-i);
            return 0;
        }
    }
}


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

N = k()
if N == 1:
    print(1)
    sys.exit()
 
for i in range(N,-1,-1):
    for j in range(1,int(N**0.5)+1):
        for k in range(2,11):
            if j**k == i:
                print(i)
                sys.exit()

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

int main(){
	int n;
    cin >> n;
	vector<string> vc_s(n);
	vector<int> vc_p(n);
	vector<int> num(n);
	for (int i=0;i<n;i++){
        cin >> vc_s[i] >> vc_p[i];
		num.at(i) = i+1;
	}

	bool flag = 1;
	for (int i=0;flag;i++){
		flag = 0;
		for (int j=n-1;j>=1;j--){
			if (vc_p[j] > vc_p[j-1]){
				swap(vc_p[j], vc_p[j-1]);
				swap(vc_s[j], vc_s[j-1]);
				swap(num[j], num[j-1]);
				flag = 1;
			}
		}
	}
	
	flag = 1;
	for (int i=0;flag;i++){
		flag = 0;
		for (int j=n-1;j>=1;j--){
			if (vc_s[j] < vc_s[j-1]){
				swap(vc_p[j], vc_p[j-1]);
				swap(vc_s[j], vc_s[j-1]);
				swap(num[j], num[j-1]);
				flag = 1;
			}
		}
	}
	for (int i=0;i<n;i++){
		cout << num.at(i) << endl;
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define endl "\n"
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
    ll n, q, val, b, c;
    cin >> n;
    unordered_map<ll, int> cnt;
    ll acc = 0;
    for(int i = 0; i < n; i++) {
        cin >> val;
        cnt[val] += 1;
        acc += val;
    }
    cin >> q;
    while(q--) {
        cin >> b >> c;
        if (cnt.count(b) == 0) {
            cout << acc << endl;
            continue;
        }
        acc += (c-b) * cnt[b];
        cnt[c] += cnt[b];
        cnt.erase(b);
        cout << acc << endl;
    }
    return 0;
}


Measured memory_bytes: 6568
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}

int main() {
	double r, g;
	cin >> r >> g;
	for (double i = -1000000; i <= 1000000; i++) {
		if (g == (r + i) / 2) {
			cout << i << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 256
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include<iomanip>

#define mod 1000000007
#define ll long long int
#define pb(x) push_back(x)
#define MP(x,y) make_pair(x,y)

using namespace std;

ll power(ll a, ll b, ll m)
{
	ll sol = power(a, b / 2, m);
	sol = (sol * sol) % m;
	if (b % 2 == 1)
		sol = (sol * a) % m;
	return(sol);
}
ll gcd(ll a, ll b)
{
	if (b == 0)
		return a;
	else
	{
		return gcd(b, a % b);
	}
}
ll d[10001], l[10001];
void solve()
{
	int n,sol=0,x;
	cin >> n>>x;
	for (int i = 1; i <= n; i++)
		cin >> l[i];
	d[1] = 0;
	for (int i = 2; i <= n+1; i++)
	{
		d[i] = d[i - 1] + l[i - 1];
		if (d[i] <= x)
			sol++;
	}
	sol = sol + 1;
	cout << sol;
}

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

Measured memory_bytes: 256
/***********************
*  Author: xuziyuan    * 
***********************/

#include <bits/stdc++.h>

#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define replet(c) for(char c='a';c<='z';c++) 
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
#define sqr(a) ((a)*(a))

using namespace std;

const LL MOD=1e9+7;

LL n,k,mx;

int main()
{
	cin>>n>>k;
	mx=((LL)pow(2,n))-1LL;
	if(k>mx)
	{
		puts("-1");
		rt0;
	}
	if(k==0)
	{
		rep(i,mx+1) cout<<i<<' '<<i<<' ';
		cout<<endl;
		rt0;
	}
	if(n==1)
	{
		puts("-1");
		rt0;
	}
	cout<<k<<' ';
	rep(i,mx+1) if(i!=k) cout<<i<<' ';
	cout<<k<<' ';
	for(int i=mx;i>=0;i--) if(i!=k) cout<<i<<' ';
	cout<<endl;
	rt0;
}

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

using namespace std;

int main() {
    int n;
    cin >> n;
    int nums[n];

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

    int cnt = 0;
    for (int i = 0; i < n; i++){
        while (nums[i] % 2 == 0) {
            nums[i] /= 2;
            cnt += 1;
        }
    }

    cout << cnt;
}

Measured memory_bytes: 256
def examA():
    A = LI()
    A.sort()
    ans = A[1] + max(A[1]-1,A[0])
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    S = SI()
    N = len(S)
    S12 = ["01"*N, "10"*N]
    ans = inf
    for s in S12:
        cnt = 0
        for i in range(N):
            if s[i]==S[i]:
                continue
            cnt += 1
        ans = min(ans,cnt)
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examC()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Measured memory_bytes: 10976
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("filed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    loop {
        let n: usize = read();
        let x: usize = read();
        if n == 0 && x == 0 {
            break;
        }
        let mut cnt = 0;
        for i in 1..n + 1 {
            for j in i + 1..n + 1 {
                for k in j + 1..n + 1 {
                    if i + j + k == x {
                        cnt += 1;
                    }
                }
            }
        }
        println!("{}", cnt);
    }
}



Measured memory_bytes: 5028
using System;
using System.Diagnostics;
using System.Linq;
using System.Text;


class Program
{
    public static void Main(string[] args)
    {
        var inval = Console.ReadLine().Split(' ').Select(n => int.Parse(n)).ToArray();
        Console.WriteLine((inval[0] == inval[1] && inval[1] == inval[2]) ? "Yes" : "No");
    }
}

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

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


#define rep(i,n) for(ll (i)=0; (i)<(ll)(n); (i)++)
#define frep(i,m,n) for(ll (i)=(m); (i)<=(ll)(n); (i)++)
#define rrep(i,n) for(ll (i)=(n)-1; (i)>-1; (i)--)
#define frrep(i,m,n) for(ll (i)=(n); (i)>(ll)(m); (i)--)
#define ALL(x) (x).begin(), (x).end()

const ll INF = 100100100100100100;
const ll MOD = 998244353;

// get abs
ll my_abs(ll a);
// a^n
ll a_n(ll a, ll n);
// get gcd
ll my_gcd(ll a, ll b);
// a^(-1) % MOD 
ll inv(ll a);
// make vector of (n!)%MOD, (n!)^(-1)%MOD
void factorial_map(vector<ll> &n, vector<ll> &ninv);

int main() {
    ll n, m, k, ans = 0;
    cin >> n >> m >> k;
    vector<ll> nfac(202020), ninv(202020);
    factorial_map(nfac, ninv);    
    
    frep(i, 0, k) {
        ll tmp = (m*a_n(m-1, n-1-i))%MOD;
        tmp *= nfac[n-1];
        tmp %= MOD;
        tmp *= ninv[n-1-i];
        tmp %= MOD;
        tmp *= ninv[i];
        tmp %= MOD;
        ans += tmp;
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}

ll my_abs(ll a) {
    if(a >= 0) return a;
    else return -1 *a;
}

ll a_n(ll a, ll n) { 
    if(n == 0) return 1;
    
    ll ret = a, count = 1;
    while(count * 2 < n) {
        ret *= ret;
        ret %= MOD;
        count *= 2;
    }
    if(count == n) return ret;
    else return (ret * a_n(a, n-count))%MOD;
}

ll my_gcd(ll a, ll b) {
    if(b == 0) return a;
    return my_gcd(b, a%b);
}

ll inv(ll a) {
    return a_n(a, MOD-2);
}


void factorial_map(vector<ll> &n, vector<ll> &ninv) {
    n[0] = 1;
    for(ll i = 1; i < n.size(); i++) n[i] = (n[i-1] * i) % MOD;
    ninv[n.size()-1] = inv(n[n.size()-1]);
    for(ll i = n.size() - 2; i > -1; i--) ninv[i] = (ninv[i+1] * (i+1)) % MOD;
}


Measured memory_bytes: 6396
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <numeric> //lcm
#include <iomanip> //double精度 setprecision

using namespace std;

#define rep(i,n) for(int i = 0; i < (int) (n); ++i)
#define rrep(i,n) for(int i = n-1; i >= 0; --i)
#define rep1(i,n) for(int i = 1; i <= (int) (n); ++i)
#define rrep1(i,n) for(int i = (n); i >= 1; --i)
#define all(vec) (vec).begin(),(vec).end()

#define debug(vec) for(auto v : vec) cerr << v << " "; cerr << endl;
#define debug2D(vec2D) for(auto vec : vec2D) { for (auto v : vec) cerr << v << " "; cerr << endl; } 
#define debugP(vec) for(auto v : vec) cerr << "(" << v.first << "," << v.second << ") "; cerr << endl;
#define debug2DP(vec2D) for(auto vec : vec2D) { for (auto v : vec) cerr << "(" << v.first << "," << v.second << ") "; cerr << endl; } 

typedef long long ll;

constexpr ll INF = 1000000000; //10^10
const ll MOD = 998244353;
//constexpr ll MOD = 1000000007;

template<class T>inline bool chmax(T& a, T b) { if (a <= b) { a = b; return true; } else return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } else return false; }




int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	ll n, k; cin >> n >> k;
	double log2k = log2(k);
	
	vector<vector<int>> a(n, vector<int>(log2k+2));
	rep(i,n) { cin >> a[i][0]; a[i][0]--;}

	rep(i,log2k+1) rep(j,n) {


		a[j][i+1] = a[a[j][i]][i];
	}

	int p = 0;
	for (int i = 0; i <= log2k; ++i) {
		if (k >> i & 1) p = a[p][i];
	}

	cout << p + 1 << endl;
}

/*		*/

Measured memory_bytes: 58032