akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int s = Integer.parseInt(sc.next());
        int w = Integer.parseInt(sc.next());
        
        if(w >= s){
            System.out.println("unsafe");
        }else{
            System.out.println("safe");
        }
    }
}

Measured memory_bytes: 35696
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int main() {
    vector<int> v(4);
    for (int i = 0; i < 4; i++) {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    cout << abs((v[0] + v[3]) - (v[1] + v[2])) << endl;
    return 0;
}


Measured memory_bytes: 3172
n,m,k=map(int,input().split())
par=[-1 for i in range(n)]

# this par & rank are initialized lists
def find(x):
    if par[x]<0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
 
def size(x):
    return -par[find(x)]
 
def unite(x,y):
    x,y=find(x),find(y)
    if x==y:
        return
    if x>y:
        x,y=y,x
    par[x]+=par[y]
    par[y]=x
 
def same(x,y):
    return find(x)==find(y)

ans=[-1 for i in range(n)]

for i in range(m):
  a,b=map(int,input().split())
  unite(a-1,b-1)
  ans[a-1]-=1
  ans[b-1]-=1

for i in range(k):
  a,b=map(int,input().split())
  if same(a-1,b-1):
    ans[a-1]-=1
    ans[b-1]-=1

for i in range(n):
  ans[i]+=size(i)

print(*ans)

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

using namespace std;

using ll = long long;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int main () {
  cin.tie(0);
  cout << fixed << setprecision(10);

  int h, w; cin >> h >> w;
  vector<string> g(h);
  for(int i=0;i<h;++i) {
    cin >> g[i];
  }

  vector<vector<int>> l(h, vector<int>(w)), r(h, vector<int>(w)), u(h, vector<int>(w)), d(h, vector<int>(w));

  for(int i=0;i<h;++i) {
    l[i][0] = 0;
    for(int j=1;j<w;++j) {
      if(g[i][j-1] == '#') l[i][j] = 0;
      else l[i][j] = l[i][j-1] + 1;
    }
  }

  for(int i=0;i<h;++i) {
    r[i][w-1] = 0;
    for(int j=w-2;j>=0;--j) {
      if(g[i][j+1] == '#') r[i][j] = 0;
      else r[i][j] = r[i][j+1] + 1;
    }
  }

  for(int i=0;i<w;++i) {
    u[0][i] = 0;
    for(int j=1;j<h;++j) {
      if(g[j-1][i] == '#') u[j][i] = 0;
      else u[j][i] = u[j-1][i] + 1;
    }
  }

  for(int i=0;i<w;++i) {
    d[h-1][i] = 0;
    for(int j=h-2;j>=0;--j) {
      if(g[j+1][i] == '#') d[j][i] = 0;
      else d[j][i] = d[j+1][i] + 1;
    }
  }

  int ans = 0;
  for(int i=0;i<h;++i) {
    for(int j=0;j<w;++j) {
      if(g[i][j] == '.') ans = max(ans, l[i][j] + r[i][j] + u[i][j] + d[i][j]);
    }
  }
  cout << ans + 1 << endl;
}


Measured memory_bytes: 67200
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const ld EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

int main(){
    int K;
    cin >> K;
    ll A[K];
    rep(i, K) cin >> A[i];
    ll L = 2, R = 3;
    rep3(i, K-1, 0){
        ll l = (L+A[i]-1)/A[i], r = (R+A[i]-1)/A[i];
        if(l == r) {cout << -1 << endl; return 0;}
        L = A[i]*l, R = A[i]*r;
    }
    cout << L << ' ' << R-1 << endl;
}

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

int main() {
	int x[5], k;

	for (int i = 0; i < 5; i++) {
		cin >> x[i];
	}
	cin >> k;

	bool f = false;

	for (int i = 0; i < 5; i++) {
		for (int j = i + 1; j < 5; j++) {
			if (x[j] - x[i] > k) {
				f = true;
			}
		}
	}
	
	if (f) cout << ":(";
	else cout << "Yay!";

	return 0;
}


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

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

    if (n % k == 0)
        puts("0");
    else
        puts("1");
}

Measured memory_bytes: 256
S = gets.chomp.split('').map(&:to_i)

def yymm?(s)
  _a = s.slice(0, 2)
  b = s.slice(2, 2)

  b = b.join.to_i

  0 < b && b <= 12
end

def mmyy?(s)
  a = s.slice(0, 2)
  _b = s.slice(2, 2)

  a = a.join.to_i

  0 < a && a <= 12
end

if yymm?(S) && mmyy?(S)
  puts 'AMBIGUOUS'
elsif yymm?(S)
  puts 'YYMM'
elsif mmyy?(S)
  puts 'MMYY'
else
  puts 'NA'
end


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


def judge(ws):
    used_words = {ws[0]}
    n = len(ws)
    for i in range(1, n):
        if ws[i] in used_words or ws[i - 1][-1] != ws[i][0]:
            return False
        used_words.add(ws[i])
    return True


def main():
    ws = [input() for _ in range(int(input()))]
    print("Yes" if judge(ws) else "No")


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
import java.util.Scanner;

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

        String str = scan.nextLine();
        String result = "";
        for (int i = 0; i < str.length();i++) {
            String s = str.substring(i, i + 1);
            if (s.equals(s.toLowerCase())) {
                result += s.toUpperCase();
            } else {
                result += s.toLowerCase();
            }
        }
        System.out.println(result);
    }
}

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

int main()
{
  string a,b;
  
  cin >> a >> b;
  a+=b;

  int num = atoi(a.c_str());
  bool flag=false;
  for (int i = 0; i <= num/2; i++)
  {
    if (i*i==num)
    {
      flag=true;
      break;
    }
  }
  
  if(flag){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }

  
  
  return 0;
}

Measured memory_bytes: 256
from sys import stdin

S = stdin.readline().rstrip()

ans = [-1] * (len(S) + 1)
for i in range(len(S)):
    if i == 0 and S[i] == '<':
        ans[i] = 0
    if i > 0 and S[i - 1] == '>' and S[i] == '<':
        ans[i] = 0
if S[-1] == '>':
    ans[len(S)] = 0

for i in range(len(S) + 1):
    if ans[i] == 0:
        cnt = 0
        while i + cnt <= len(S) - 1 and S[i + cnt] == '<' and ans[i + cnt + 1] != 0:
            ans[i + cnt + 1] = max(ans[i + cnt + 1], ans[i + cnt] + 1)
            # print(ans)
            cnt += 1
        cnt = 0
        while i + cnt >= 0 and S[i + cnt - 1] == '>' and ans[i + cnt - 1] != 0:
            ans[i + cnt - 1] = max(ans[i + cnt - 1], ans[i + cnt] + 1)
            # print(ans)
            cnt -= 1

# print(ans)
print(sum(ans))


Measured memory_bytes: 49352
/**
*    author:  y_takano
*    created: 19.06.2020 16:23:42
**/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)

using namespace std;

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

  int m, f, r;

  for (;;)
  {
      cin >> m >> f >> r;
      if (m == -1 && f == -1 && r == -1)
      {
          break;
      }
      
      if (m == -1 || f == -1)
      {
          cout << 'F' << endl;
      }
      else if (80 <= m + f)
      {
          cout << 'A' << endl;
      }
      else if (65 <= m + f)
      {
          cout << 'B' << endl;
      }
      else if (50 <= m + f)
      {
          cout << 'C' << endl;
      }
      else if (30 <= m + f && 50 <= r)
      {
          cout << 'C' << endl;
      }
      else if (30 <= m + f)
      {
          cout << 'D' << endl;
      }
      else
      {
          cout << 'F' << endl;
      }
  }

  return 0;
}


Measured memory_bytes: 3152
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5, mod = 1e9 + 7, inf = 0x3f3f3f3f;
struct e{
    int l, r;
}a[maxn];
bool cmp(e a, e b){return a.r == b.r ? a.l < b.l : a.r < b.r;}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i){
        cin >> a[i].l >> a[i].r;
    }
    sort(a, a + n, cmp);
    int curt = 0;
    for (int i = 0; i < n; ++i){
        if (curt + a[i].l <= a[i].r){
            curt += a[i].l;
        }else{
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 1792
//GCD FREQUENCY COUNTER WITH INC-EXC BY ADANCITO

//WHAT DOES THIS ALGORITHM DO?
/*
 
 imagine that for every ordered pair (i, j), 0 <= i, j <= maxN, we did
 res[gcd(i, j)] += one[i] * two[j]
 
 this algorithm calculates the final value of res in O(nlgn)
 
 remember to call precalculations() at the beginning of the program
 
 */

#include <iostream>
#include <string.h>
#include <ctime>
#include <cmath>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <set>
#include <map>
#include <vector>

using namespace std;
const int maxN = 44, MOD = 1e9 + 7;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    ll a, b;
    cin >> a >> b;
    
    cout << (((a * b) & 1)? "Yes": "No") << '\n';
    
}


Measured memory_bytes: 256
#ifdef __APPLE__
#include <cassert>
#include <iostream>
#include <iomanip>
#include <ctime>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <map>
#include <set>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <cctype>
#include <list>
#include <cmath>
#include <limits>
#include <bitset>
#include <numeric>
#include <climits>
#include <complex>
#else
#include<bits/stdc++.h>
#endif // __APPLE__
using namespace std;
typedef pair<int,int>   II;
typedef vector<II>     VII;
typedef vector<int>     VI;
typedef vector< VI > 	VVI;
typedef long long int LL;
typedef  unsigned long long int ULL;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define SET(a,b) memset(a,b,sizeof(a))
#define LET(x,a) __typeof(a) x(a)
#define ALL(c) (c).begin(),(c).end()
#define si(n) scanf("%d",&n)
#define dout(n) printf("%d\n",n)
#define sll(n) scanf("%lld",&n)
#define lldout(n) printf("%lld\n",n)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define REP(i,a,b) for(int i = (int)a; i < (int)b; i++)
#define ROUNDOFFINT(d) d = (int)((double)d + 0.5)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1)	{
cerr << name << " : " << arg1 << std::endl;}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
     const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);}
#else
#define trace(...)
#endif



map<LL,LL> m;

int main()
{
	//fr;fw;
	fast_io;
    LL n;
    cin>>n;
    REP(i,0,n)
    {
        LL x;
        cin>>x;
        m[x]++;
    }
    int cnt=0;
    for(auto w:m)
    {
        if(w.S%2==0)
            w.S=2,cnt++;
        else
            w.S=1;
    }
    int tmp=SZ(m)-cnt;
    if(cnt%2==0)
    {
        cout<<tmp+cnt<<endl;
    }
    else
    {
        cout<<tmp+cnt-1<<endl;
    }



	return 0;
}






Measured memory_bytes: 6528
a=input()
b=input()
c=input()
i=0
j=0
k=0
t='a'
while 1:
    if t=='a':
        if i==len(a):
            print('A')
            break
        t=a[i]
        i+=1
    elif t=='b':
        if j==len(b):
            print('B')
            break
        t=b[j]
        j+=1
    elif t=='c':
        if k==len(c):
            print('C')
            break
        t=c[k]
        k+=1


Measured memory_bytes: 9004
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
ans = 0
for i in range(N):
    hoge = min(A[i],B[i])
    ans += hoge
    A[i] -= hoge
    B[i] -= hoge
    if B[i] != 0:
        ans += min(B[i],A[i+1])
        A[i+1] = max(A[i+1]-B[i],0)
print(ans)

Measured memory_bytes: 18624
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;
 
#define MOD 1000000007

int main(){
  string s;
  cin>>s;
  vector<string> vs;
  string s1 = "hi";
  vs.pb(s1);
  rep(i,0,10){
    s1 += "hi";
    vs.pb(s1);
  }
  ll flag = 0;
  rep(i,0,vs.sz){
    if(vs[i]==s)flag = 1;
  }
  if(flag==1){
      cout << "Yes" << endl;
  }
  else{
      cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <iomanip>
using namespace std;
 
#define f first
#define s second
 
#define pb push_back
#define pp pop_back
#define mp make_pair
 
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
#define clr(a,v) memset(a, v, sizeof(a))
 
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)
#define reflex ios_base::sync_with_stdio(false)
 
#define nl '\n'
#define ioi exit(0);
 
 
#define PI 3.14159265
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N= (int)2e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
//const int mod = 1000000007;
const ll linf = (ll)1e18 + 7;
const ll limit = 2e9;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
const int kx[] = {-1,1,2,2,1,-1,-2,-2};
const int ky[] = {2,2,1,-1,-2,-2,-1,1};
 
//const int mod = 998244353;
 
struct dsu{
	int parent[N];
	int cont;
	void make_set(int n){
		for(int i = 1; i <= n; i++)
			parent[i] = i;
		cont = n;
	}
	
	int find_set(int v){
		if(v == parent[v])
			return v;
		return find_set(parent[v]);
	}
	
	void union_sets(int a, int b){
		a = find_set(a);
		b = find_set(b);	
		if(a != b){
			parent[b] = a;
			cont--;
		}
	}
};

struct nod{
	int x, y;
	nod(int x_,int y_): x(x_), y(y_){};
};

bool operator<(nod & a, nod & b){
  return a.y < b.y;
}

int main(){
	int n; cin >> n;
	vector< nod > v;
	int x, l; 
	for(int i = 1; i <= n; i++){
		cin>> x >> l;
		v.push_back(nod(x-l,x+l));
	}
	sort(v.begin(),v.end());
	int ans = 1, left = v[0].y;
	for(int i = 1; i < n; i++){
		int curr = v[i].x;
		if( left <= curr){
			left = v[i].y;
			ans += 1;
		} 
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 1400
#include<bits/stdc++.h>
    #define LIM 1+2+4+8+16+32+64+128
    using namespace std;
    typedef long long int ll;
    int main(){
    int n,d;
    cin>>n>>d;
    int zh[n][d];
    for(int i=0;i<n;i++){
    for(int j=0;j<d;j++){
    cin>>zh[i][j];
    }
    }
    int n2[1000];
    for(int i=1;i<1000;i++){
    n2[i]=i*i;
    }
    int ans=0;
    for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
    int nn=0;
    for(int l=0;l<d;l++){
    nn+=abs(zh[i][l]-zh[j][l])*abs(zh[i][l]-zh[j][l]);
    }
    for(int q=1;q<=1000;q++){
    if(n2[q]==nn){
    ans++;
    break;
    }else if(n2[q]>nn){
    break;
    }
    }
    }
    }
    cout<<ans<<endl;
    return(0);
    }

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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> v;
  for (int i = 0; i < n; i++) {
    int input;
    cin >> input;
    v.push_back(input);
  }
  int counter = 0;
  for (int i = 1; i < (v.size() - 1); i++) {
    if ((v[i] < v[i - 1] && v[i] > v[i + 1]) ||
        (v[i] > v[i - 1] && v[i] < v[i + 1])) {
      counter++;
    }
  }
  cout << counter;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep0(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define mREP(i,a,b) for (int i = a; i > (b); --i)
#define all(x) (x).begin(),(x).end()
const int INF = 1000000007;
typedef long long ll;
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; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

int main(){
  int n,m;
  cin >> n;
  string temp;
  map<string,int>a;
  rep0(i,n){
    cin >> temp;
    a[temp]++;
  }
  cin >> m;
  rep0(i,m){
    cin >> temp;
    a[temp]--;
  }
  int ans = -1000;
  for (auto& j : a){
    ans = max(ans,j.second);
  }
  cout << max(0,ans) << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>

const int INF = 1000000009;
const long LINF = 1123456789012345678;

int n, k;
int a[100000];

int main(){
	scanf("%d%d", &n, &k);
	for(int i = 0; i < n; i++){
		scanf("%d", &a[i]);
	}
	int one = 0;
	for(int i = 0; i < n; i++){
		if(a[i] == 1){
			one = i;
			break;
		}
	}
	/*
	int dn = (one + (k-1) - 1) / (k-1);
	int up = ((n-1-one) + (k-1) - 1) / (k-1);
	int ans1 = dn + up;
	int ans2 = INF;
	if((k-1) % 2 == 1){
		dn = (one - (k-1)/2 + (k-1) - 1) / (k-1);
		up = ((n-1-one - (k-1)/2) + (k-1) - 1) / (k-1);
		ans2 = dn + up;
	}else{
		dn = (one - (k-1)/2 + (k-1) - 1) / (k-1);
		up = ((n-1-one - k/2) + (k-1) - 1) / (k-1);
		ans2 = dn + up;
		dn = (one - k/2 + (k-1) - 1) / (k-1);
		up = ((n-1-one - (k-1)/2) + (k-1) - 1) / (k-1);
		ans2 = std::min(ans2, dn+up);
	}
	//*/
	int ans = INF;
	for(int i = 0; i < k; i++){
		int st = one - i;
		if(st < 0 || st + k - 1 >= n){
			continue;
		}
		//printf("  %d\n", st);
		int dn = (st + (k-1) - 1) / (k-1);
		int up = (n-1-(st + k-1) + (k-1) - 1) / (k-1);
		//printf("    %d\n", dn + up);
		ans = std::min(ans, dn + up);
	}
	//printf("(%d %d)\n", dn, up);
	printf("%d\n", ans + 1);
	return 0;
}


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

int n;
int arr[100100];

ll dp[100100];
bool vis[100100];

ll func( int pos ) {
    if ( pos == n ) return 0;
    if ( vis[pos] ) return dp[pos];
    vis[pos] = 1;

    ll p = 2e9, q = 2e9;
    if ( pos + 1 <= n ) p = abs(arr[pos] - arr[pos + 1]) + func(pos + 1);
    if ( pos + 2 <= n ) q = abs(arr[pos] - arr[pos + 2]) + func(pos + 2);

    return dp[pos] = min(p, q);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    cout << func(1) << endl;
    return 0;
}


Measured memory_bytes: 6144
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,j,n) for(int i = j; i < n; i++)
#define RFOR(i,j,n) for(int i = j-1; i >= n; i--)
#define PREC(n) fixed << setprecision(n)
#define print_array(v) REP(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define _LIBCPP_DEBUG 0
using namespace std;
int64_t MOD = 1000000007;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, cnt = 0;
  cin >> n;
  vector<int> vec(n);
  REP(i,n) cin >> vec[i];
  FOR(i,1,n-1) {
    if(vec[i-1] < vec[i] && vec[i] < vec[i+1]) cnt++;
    if(vec[i-1] > vec[i] && vec[i] > vec[i+1]) cnt++;
  }
  cout << cnt << endl;
  return 0;
}
//templete by private_yusuke

Measured memory_bytes: 256
import java.util.*;

class DPValue {
    public DPValue(int heads, int tails, double val) {
        this.heads = heads;
        this.tails = tails;
        this.val = val;
    }

    public DPValue(DPValue dp) {
        this.heads = dp.heads;
        this.tails = dp.tails;
        this.val = dp.val;
    }

    public DPValue() {
    }

    int heads, tails;
    double val;


    @Override
    public String toString() {
        return "heads: " + heads + " tails: " + tails + " val: " + val;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        double [][]dp = new double[n + 1][2 * n + 2];     // States are 1. Number of coins.   2. Difference between heads and tails
        double []a = new double[n];
        for(int i = 0; i < n; i++) {
            a[i] = in.nextDouble();
        }

        dp[0][n] = 1;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < 2 * n + 1; j++) {
                if(dp[i][j] != 0) {
                    dp[i + 1][j + 1] += dp[i][j] * a[i];         // heads
                    dp[i + 1][j - 1] += dp[i][j] * (1 - a[i]);   // tails
                }
            }
        }
        double ans = 0;
        for(int i = n + 1; i < 2 * n + 2; i++) {
            ans += dp[n][i];
        }
        System.out.println(ans);
    }
}

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

namespace AC {
#define ll long long
#define PLL pair<ll, ll>
#define PDD pair<double, double>
#define PDPLL pair<double, PLL>
#define PLPLL pair<ll, PLL>
#define pb push_back
#define fi first
#define se second
#define ls rt << 1
#define rs rt << 1 | 1

    const ll N = 1e5 + 66;

    ll BUGS = 1;

    inline ll read(){
        ll x = 0;    bool flag = 1;   char ch = getchar();
        while(ch < '0' || ch > '9') { if(ch == '-') flag = 0; ch = getchar(); }
        while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
        if(flag) return x;  return (~(x - 1));
    }

    inline void read(ll arr[], ll s, ll e) { for(ll i = s; i <= e; ++i) arr[i] = read(); }

    inline void write(ll x){
        if(x < 0) { x = ~(x - 1); putchar('-'); }
        if(x > 9) write(x / 10); putchar(x % 10 + '0');
    }

    inline void print(ll x) { write(x); puts(""); }

    inline void print(ll arr[], ll s, ll e) {
        for(ll i = s; i <= e - 1; ++i) write(arr[i]), putchar(' ');
        write(arr[e]); puts("");
    }

    inline ll max3(ll a, ll b, ll c) { return max(a, max(b, c)); }

    inline ll min3(ll a, ll b, ll c) { return min(a, min(b, c)); }

    inline void debugNum(ll num, string ss) { cout << "BUGS" << BUGS++ << " : " << ss << " : " << num << endl; }

    inline void debugArr(ll arr[], ll s, ll e, string ss) {
        cout << "BUGS" << BUGS++ << " : " << ss << " : " << endl;
        for(ll i = s; i <= e; ++i) cout << "i : " << i << " val : " << arr[i] << endl;
    }

    inline void IO() {
        //ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
        //cout << setiosflags(ios::fixed) << setprecision(1); //保留小数点后1位
        //cout << setprecision(1); //保留1位有效数字
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
}using namespace AC;

int main() {
    //IO();
    ll x;
    while(cin >> x) {
        if(x >= 400 && x <= 599) puts("8");
        else if(x >= 600 && x <= 799) puts("7");
        else if(x >= 800 && x <= 999) puts("6");
        else if(x >= 1000 && x <= 1199) puts("5");
        else if(x >= 1200 && x <= 1399) puts("4");
        else if(x >= 1400 && x <= 1599) puts("3");
        else if(x >= 1600 && x <= 1799) puts("2");
        else if(x >= 1800 && x <= 1999) puts("1");
    }
    return 0;
}



Measured memory_bytes: 3632
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct Edge {
	int to;
	int nxt;
} e[4005];
int n, m, edgenum, head[2005], pa[2005], dep[2005], a[4005], b[4005], tot;
int d[2005], c[2005], f[2005];
bool flag[2005], used[4005];
void add(int u, int v) {
	e[++edgenum].to = v;
	e[edgenum].nxt = head[u];
	head[u] = edgenum;
}
void dfs(int node) {
	dep[node] = dep[pa[node]] + 1;
	for (int hd = head[node]; hd; hd = e[hd].nxt) {
		int to = e[hd].to;
		if (to == pa[node])continue;
		pa[to] = node;
		dfs(to);
	}
}
void solve() {
	int u = 0;
	for (int i = 1; i <= n; i++) {
		if (flag[i])continue;
		if (d[i] == 1) {
			u = i;
			break;
		}
	}
	if (u == 0)return;
	if (c[u] == 0) {
		for (int hd = head[u]; hd; hd = e[hd].nxt) {
			int to = e[hd].to;
			if (flag[to])continue;
			d[to]--;
		}
		flag[u] = 1;
		solve();
		return;
	}
	if (c[u] == 1) {
		for (int hd = head[u]; hd; hd = e[hd].nxt) {
			int to = e[hd].to;
			if (flag[to])continue;
			d[to]--;
		}
		flag[u] = 1;
		for (int i = 1; i <= tot; i++) {
			if (used[i])continue;
			if (b[i] == u)swap(a[i], b[i]);
			if (a[i] != u)continue;
			int v = 0;
			for (int hd = head[u]; hd; hd = e[hd].nxt) {
				int to = e[hd].to;
				if (!flag[to]) {
					v = to;
					break;
				}
			}
			if (b[i] != v) {
				a[i] = v;
				c[u]--, c[v]++;
				solve();
				if (a[i] == v)a[i] = u;
				else b[i] = u;
			} else {
				c[u]--, c[v]--;
				used[i] = 1;
				solve();
			}
			return;
		}
	}
	int x = 0, y = 0;
	for (int i = 1; i <= tot; i++) {
		if (used[i])continue;
		if (b[i] == u)swap(a[i], b[i]);
		if (a[i] != u)continue;
		if (!x)x = i;
		else if (!y)y = i;
		else break;
	}
	used[x] = used[y] = 1;
	if (b[x] == b[y]) {
		swap(a[y], b[y]);
		c[u] -= 2;
		c[a[y]]--, c[b[x]]--;
		solve();
	} else {
		int now = ++tot;
		a[now] = b[x];
		b[now] = b[y];
		c[u] -= 2;
		solve();
		if (a[now] == b[x])swap(a[x], b[x]);
		else swap(a[y], b[y]);
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
		d[u]++, d[v]++;
	}
	dfs(1);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &a[i], &b[i]);
		if (dep[a[i]] < dep[b[i]])swap(a[i], b[i]);
		int u = a[i], v = b[i];
		while (dep[u] > dep[v]) {
			f[u]++;
			u = pa[u];
		}
		while (u != v) {
			f[u]++, f[v]++;
			u = pa[u], v = pa[v];
		}
		c[a[i]]++, c[b[i]]++;
	}
	tot = m;
	solve();
	tot = 0;
	for (int i = 1; i <= n; i++)tot += min(2, f[i]);
	printf("%d\n", tot);
	for (int i = 1; i <= m; i++)printf("%d %d\n", a[i], b[i]);
	return 0;
}

Measured memory_bytes: 384
import java.util.*;

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

        String a = sc.next();
        String b = sc.next();

        if(a.equals("H")){
            if(b.equals("H")){
                System.out.println("H");
            }else{
                System.out.println("D");
            }
        }else{
            if(b.equals("H")){
                System.out.println("D");
            }else{
                System.out.println("H");
            }

        }

    }
}


Measured memory_bytes: 21204
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>

#include <cstdio>

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
typedef long long ll;
typedef unsigned long long ull;

int c[10][10];
int MinCost[10];
bool checked[10] = { false };

void DecideMinCost(int dest, int total)
{
	int next = -1;
	int min_tmp = 2000;

	rep(i, 10) {
		if (total + c[i][dest] < MinCost[i] && !checked[i]) {
			MinCost[i] = total + c[i][dest];
		}
	}

	rep(i, 10) {
		if (MinCost[i] < min_tmp && !checked[i]) {
			next = i;
			min_tmp = MinCost[i];
		}
	}

	if (next == -1) return;

	checked[next] = true;
	DecideMinCost(next, MinCost[next]);
}

int main()
{
	int H, W, A;
	int src = 1;
	int ans = 0;

	cin >> H >> W;

	rep(i, 10) {
		rep(j, 10) cin >> c[i][j];
		MinCost[i] = 2000;
	}
	MinCost[1] = 0;
	checked[1] = true;

	DecideMinCost(1, 0);

	rep(i, H) {
		rep(j, W) {
			cin >> A;
			if (A != -1) ans += MinCost[A];
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAXN 100006
int flag[MAXN];
int memo[MAXN];

int main(){
	int i, n, m, x, y, ans = 0;
	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++)
		memo[i] = 1, flag[i] = 0;
	flag[1] = 1;
    for (i = 0; i < m; i++) {
		scanf("%d%d", &x, &y);
		if (flag[x]) flag[y] = 1;
		memo[y] += 1, memo[x] -= 1;
        if (memo[x] == 0) flag[x] = 0;
    }
    for (i = 1; i <= n; i++) ans += flag[i];
    printf("%d\n", ans);
    return 0;
}

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

using ll = long long;

ll pate_count[51];
ll lv_length[51];



ll count_pate(ll lv, ll x) {
	if (lv == 0) {
		return x;
	}

	if (x >= lv_length[lv] - 1) {
		return pate_count[lv];
	}

	if (x == 0 || x == 1)  {
		return 0;
	}
	int ans = 0;

	if (x  <= lv_length[lv - 1] + 1) {
		return count_pate(lv - 1, x - 1);
	}

	if (x == lv_length[lv - 1] + 2) {
		return pate_count[lv - 1] + 1;
	}
	return (pate_count[lv - 1] + 1) + count_pate(lv - 1, x - 1 - lv_length[lv - 1] - 1);
}

int main() {


	pate_count[0] = 1;
	lv_length[0] = 1;
	for (int i = 1; i < 51; i++) {
		pate_count[i] = pate_count[i - 1] * 2 + 1;
		lv_length[i] = lv_length[i - 1] * 2 + 3;
	}

	ll N, X;
	cin >> N >> X;
	cout << count_pate(N, X) << endl;

	return 0;
}

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

#define ul unsigned long 
#define ull unsigned long long
#define li long long int

double di(int p1[2],int p2[2]) {
  return sqrt((double)(p2[0] - p1[0]) * (p2[0] - p1[0]) + (double)(p2[1] - p1[1]) * (p2[1] - p1[1]));
}

int fa(int a) {
  int r=1;
  for (int i=a;i>0;i--) r*=i;
  return r;
}

int main()
{
  int n;
  int p[8][2];
  int ord[8];
  cin >> n;
  double sm = 0, f = fa(n);
  vector<int> o(n);
  for (int i = 0; i < n; i++)
  {
    cin >> p[i][0];
    cin >> p[i][1];
    ord[i]=i;
  }

  do {
    for (int i=1;i<n;i++) {
      sm+=di(p[ord[i-1]],p[ord[i]])/f;
    }
  } while (next_permutation(ord,ord+n));

  std::cout << std::fixed;
  std::cout << std::setprecision(12) << sm;
  cout<<endl;

  return 0;
}


Measured memory_bytes: 256
import numpy as np
n,m = map(int, input().split())
a_list = list(map(int, input().split()))

a_list.sort(reverse=True)
sum_ = sum(a_list)
min_ = np.ceil(sum_/ (4*m))

count = 0
for i in range(n):
    if a_list[i] < min_:
        break
    count += 1

if count < m:
    print('No')
else:
    print('Yes')

Measured memory_bytes: 21656
#include <stdio.h>

void insertionSort(int *,int,int);
void shellSort(int *,int);

static int cnt=0;


int main(void){
  int A[1000000],m,n,i;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&A[i]);

  shellSort(A,n);
  printf("\n%d\n",cnt);

  for(i=0;i<n;i++)
    printf("%d\n",A[i]);
  return 0;
}

void insertionSort(int *A,int n,int g){
  int i,j,v;
  for(i=g;i<n;i++){
    v=A[i];
    j=i-g;
    while(j>=0 && A[j]>v){
      A[j+g]=A[j];
      j=j-g;
      cnt++;
    }
    A[j+g]=v;
  }
}

void shellSort(int *A,int n){
  int i,m,h;
  int G[100];
  cnt=0;
  for(h=1,i=0;;i++){
    if(h>n)break;
    G[i]=h;
    h=3*h+1;
  }
  m=i;
  printf("%d\n",m);
  for(i=m-1;i>=0;i--){
    insertionSort(A,n,G[i]);
    printf("%d",G[i]);
    if(i!=0)printf(" ");
  }
}


Measured memory_bytes: 5664
#include <bits/stdc++.h>
using namespace std;
int main() { 
  int N;
  cin >> N;
  vector<int> t(N);
  
  for(int i = 0; i < N; i++){
    cin >> t.at(i);
  }
  
  int M;
  cin >> M;

  for(int j = 0; j < M; j++){
    int a,b;
    cin >> a >> b;
    vector<int> s = t;
    s.at(a-1) = b;
    int sum = 0;
    for(int k = 0; k < N; k++){
      sum += s.at(k);
    }
    cout << sum << endl;
  }

}

Measured memory_bytes: 256
#include <iostream>
#include <iterator>
#include <cstdio>
#include <array>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <algorithm>
#include <numeric>
#include <bitset>
#include <chrono>
#include <functional>

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()
{
	int a, b;
	cin >> a >> b;
	cout << a * b - a - b + 1 << endl;
	return 0;
}

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

int main()
{
    int x,y = 0,z = 0;
    for(int i = 0; i < 3; i++){
        cin >> x;
        if(x == 5) y++;
        if(x == 7) z++;
    }
    cout << (y == 2 && z == 1 ? "YES" : "NO") << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

class Main{
    public static void main(String[] args){
        FastScanner fsc=new FastScanner();
        int n=fsc.nextInt();
        char[] c=fsc.next().toCharArray();
        fsc.close();
        for(int i=0;i<c.length;i++){
            c[i]+=n;
            if(c[i]>'Z') c[i]-=26;
        }
        for(int i=0;i<c.length;i++){
            System.out.print(c[i]);
        }
    }
    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte(){
            if(ptr<buflen) return true;
            else{
                ptr = 0;
                try{
                    buflen = in.read(buffer);
                }
                catch(IOException e){
                    e.printStackTrace();
                }
                if(buflen<=0) return false;
            }
        return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            if (!hasNext()) throw new NoSuchElementException();
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) throw new NumberFormatException();
            while(true){
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                }
                else if(b == -1 || !isPrintableChar(b)) return minus ? -n : n;
                else throw new NumberFormatException();
                b = readByte();
            }
        }
        public int nextInt() {
            long nl = nextLong();
            if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
            return (int) nl;
        }
        public double nextDouble() { return Double.parseDouble(next());}
        public void close(){
            try{in.close();}
            catch(IOException e){e.printStackTrace();}
        }
    }
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
int main(){
    cout << fixed << setprecision(11);

    int a, b, h, m;
    cin >> a >> b >> h >> m;
    double m_deg = 6*m;
    double h_deg = 30*h + (double)m/2;
    double deg_betweem = abs(h_deg-m_deg);
    if(deg_betweem > 180)
        deg_betweem = 360 - deg_betweem;
    cout << sqrt(a*a + b*b - 2*a*b*cos(deg_betweem*(3.14159265359/180))) << '\n';

    return 0;
}


Measured memory_bytes: 4172
#include <bits/stdc++.h>
#define Rep(i,j,n) for(int i=j; i<n; i++)
#define rep(i,n) for(int i=0; i<n; i++)
#define PI 3.14159265359
#define INF 1000100100//000000000
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define P pair<int, int>
#define PP pair<P,P>
#define T tuple<int,int,int> 
using namespace std;
 
int main(){
  int n; cin >> n;
  string s; cin >> s;
  int w=0;

  rep(i,n){
    if(s[i]=='.') w++;
  }

  int b=0;
  int ans=INF;

  rep(i,n){
    ans=min(ans,w+b);
    if(s[i]=='.') w--;
    else b++;
  }
  ans=min(ans,w+b);
  
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3732
import math

n, d = list(map(int, input().split(" ")))
cnt = 0
dist = lambda x, y: math.sqrt(x * x + y * y)
for i in range(n):
    xi, yi = list(map(int, input().split(" ")))
    if dist(xi, yi) <= d:
        cnt += 1

print(cnt)

Measured memory_bytes: 9180
n = int(input())
a = input()
b = input()
c = input()
ans = 0
for i in range(n):
	if a[i] == b[i]:
		if a[i] != c[i]:
			ans += 1
		
	else:
		if a[i] == c[i]:
			ans += 1
		else:
			if b[i] == c[i]:
				ans += 1
			else :
			 	ans += 2

print(ans)

Measured memory_bytes: 3064
N,M,Q = list(map(int, input().split()))
C = []
for i in range(Q):
    C.append(list(map(int, input().split())))
    
import itertools
res = 0
ls=list(range(1,M+1))
for a in itertools.combinations_with_replacement(ls, N):
    p = 0
    for c in C:
        if a[c[1]-1]-a[c[0]-1]==c[2]:
            p += c[3]
        res = max(res,p)
print(res)

Measured memory_bytes: 9240
#include<stdio.h>
int main()
{
	int i,j,a,b,c;
	for(c=1;;)
	{
		scanf("%d %d",&a,&b);
		if(a==0 && b==0)break;
		for(j=1;j<=a;j++)
		if(j%2==0)
	{
		for(i=1;i<=b;i++)
			{
				if(i%2==0)
					printf("#");
				else
					printf(".");
		}
			printf("\n");
		}
		else
		{
				for(i=1;i<=b;i++)
				{
				if(i%2==0)
					printf(".");
				else
					printf("#");
				}
					printf("\n");
		}	
			printf("\n");
	}
	return 0;
}


Measured memory_bytes: 2092
#include<stdio.h>

int main(){
  int i, cntm = 0, a;
  char ch[1200];

  for(i=0;;i++){
    scanf("%c", &ch[i]);

    if(ch[i] == '\n') break;

    cntm++;

    a = ch[i];
    if(a >= 65 && a <= 90){
      ch[i] += 32; //omoji -> komoji
    }

    if(a >= 97 && a <= 122){
      ch[i] -= 32; //komoji -> omoji
    }
  
  }
  
  for(i=0;i<cntm;i++){
    printf("%c", ch[i]);
  }
  printf("\n");

  return 0;
}


Measured memory_bytes: 2048
import sys
sys.setrecursionlimit(10 ** 9)

n = int(input())
x = input()

p = [-1 for _ in range(2*(10**5)+1)]
cnt = x.count('1')

def calc(a):
  #print('a=',a)
  if p[a] != -1:
    return p[a]
  else:
    if a == 0:
      ret = 0
    else:
      b = bin(a).count('1')
      ret = 1+calc(a%b)
    p[a] = ret
    return ret

if cnt > 1:
  x0 = int(x,2)%(cnt-1)
  xx0 = [1]
  for i in range(n):
    xx0.append((xx0[-1]*2)%(cnt-1))
x1 = int(x,2)%(cnt+1)
xx1 = [1]
for i in range(n):
  xx1.append((xx1[-1]*2)%(cnt+1))

y = list(x)  
for i in range(n):
  if y[i] == '0':
    xx = xx1[n-i-1]
    print(calc((x1+xx)%(cnt+1))+1)
  else:
    if cnt == 1:
      print(0)
    else:
      xx = xx0[n-i-1]
      print(calc((x0-xx)%(cnt-1))+1)

Measured memory_bytes: 118952
nums = [int(num) for num in input().split()]
h = nums[0]
w = nums[1]
a = []
for i in range(h):
    a.append(input())
b = []
for i in range(h):
    hoge = True
    for j in range(w):
        if a[i][j] =="#":
            hoge = False

    if not hoge:
        b.append(a[i])

# print(b)
c = []

for i in range(w):
    hoge = True
    for j in range(len(b)):
        if b[j][i] == "#":
            hoge = False
    if not hoge:
        c.append(i)

ans = []
for i in range(len(b)):
    hoge =""
    for j in range(w):
        if j in c:
            hoge = hoge+b[i][j]
    ans.append(hoge)
        

for i in range(len(ans)):
    print(ans[i])

Measured memory_bytes: 3064
#include<iostream>
#include<climits>
#include<vector>
#include<list>
#include<functional>
#include<algorithm>
#include<string>
#include<cmath>
#include<complex>
#include<set>
#include<map>
#include<stack>
#include<queue>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

class question {
public:
	ll N, P;
	ll pow(ll a, ll b) {
		if (b == 0) return 1;
		if (b % 2) return a*pow(a, b - 1);
		ll tmp = pow(a, b / 2);
		return tmp*tmp;
	}
	void ans() {
		cin >> N >> P;
		int res;
		if (N == 1) {
			cout << P << "\n";
			return;
		}
		for (int i = 1;pow(i, N) <= P && pow(i, N) > 0;i++) {
			if (P%pow(i, N) == 0) res = i;
		}
		cout << res << "\n";
	}
};

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

	question q;
	q.ans();

	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#define SIZE(array) (sizeof(array)/sizeof(array[0]))

using namespace std;

int main(){
    long x;
    long money = 100;
    long year = 0;
    cin >> x;
    while (money < x){
        money *= 1.01;
        year += 1;
    }
    cout << year << endl;
}

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

int main(){
	int n;
	cin>>n;
	vector<pair<int,int>> ab(n);
	int ta,tb;
	for (int i = 0; i < n; i++) {
		cin>>ta>>tb;
		ab[i]=make_pair(ta,tb);
	}
	sort(
		ab.begin(),
		ab.end(),
		[](const pair<int,int>& x,const pair<int,int>& y){return x.second<y.second;}
	);
	long long int time=0;
	auto itr=ab.begin();
	while(itr!=ab.end()){
		time+=(*itr).first;
		if (time<=(*itr).second) {
			itr++;
		}else {
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <queue>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

class UnionFind{
  public: 
    vector<int> par;  
    UnionFind(int N) : par(N){
      for(int i=0;i<N;i++) par[i]=i;
    }

    int root(int x){
      if(par[x]==x) return x;
      return par[x]=root(par[x]);
    }

    void unite(int x,int y){
      int rx=root(x);
      int ry=root(y);
      if(rx==ry) return;
      par[rx]=ry;
    }

    bool same(int x,int y){
      int rx=root(x);
      int ry=root(y);
      return rx==ry;
    }
};

int main(){
  int N,K,L; cin>>N>>K>>L;

  UnionFind A(N),B(N);

  for(int i=0;i<K;i++){
    int a,b; cin>>a>>b;
    A.unite(a-1,b-1);
  }
  for(int i=0;i<L;i++){
    int a,b; cin>>a>>b;
    B.unite(a-1,b-1);
  }
  map<pair<int,int>,int> s;
  for(int i=0;i<N;i++){
    s[make_pair(A.root(i),B.root(i))]++;
  }

  for(int i=0;i<N;i++){
    cout<<s[make_pair(A.root(i),B.root(i))]<<" ";
  }
  cout<<endl;
  return 0;
}


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

int main() {
    int K, S;
    cin >> K >> S;
    int ans = 0;
    for (int i = 0; i <= K; i++) {
        for (int j = 0; j <= K; j++) {
            if (i + j > S || S - (i + j) > K) continue;
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
int N, M;

struct Edge{
    int from, to;
    ll cost;
};
//ll data[1001][1001];
Edge es[2001];
// 1からの距離
ll d[1001];
const ll INF = 1LL << 50;
bool negative[1001];
/*
ll shortest_path(int s){
    for(int i = 0; i < N; ++i){
        d[i] = INF;
    }
    d[s] = 0;
    ll cnt = 0;
    while(true){
        ++cnt;
        bool update = false;
        bool gup = false;
        for(int i = 0; i < M; ++i){
            Edge e = es[i];
            if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost){
                if(e.to == s){
                    continue;
                }
                if(e.to == N - 1){
                    gup = true;
                }
                d[e.to] = d[e.from] + e.cost;
                update = true;
            }
        }
        if(cnt > N && !gup){
            break;
        }
        if(!update){
            break;
        }
    }
    return d[N - 1];
}*/
/*
bool shortest_path2(int s){
    for(int i = 0; i < N; ++i){
        d[i] = INF;
    }
    d[s] = 0;
    ll cnt = 0;
    while(true){
        ++cnt;
        bool update = false;
        for(int i = 0; i < M; ++i){
            Edge e = es[i];
            if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost){
                if(e.to == s){
                    return true;
                }
                d[e.to] = d[e.from] + e.cost;
                update = true;
            }
        }
        if(cnt > N){
            break;
        }
        if(!update){
            break;
        }
    }
    return false;
}*/

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

    cin >> N >> M;

    for(int i = 0; i < M; ++i){
        int a, b;
        ll c;
        cin >> a >> b >> c;
        --a, --b;
        //data[a][b] = -c;
        es[i] = (Edge){a, b, -c};
    }

    for(int i = 0; i < N; ++i){
        d[i] = INF;
    }
    d[0] = 0;

    for(int l = 0 ; l < N; ++l){
        for(int i = 0; i < M; ++i){
            Edge e = es[i];

            if(d[e.from] == INF) continue;

            if(d[e.to] > d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
            }
        }
    }
    ll ans = d[N - 1];

    for(int l = 0 ; l < N; ++l){
        for(int i = 0; i < M; ++i){
            Edge e = es[i];

            if(d[e.from] == INF) continue;

            if(d[e.to] > d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
                negative[e.to] = true;
            }

            if(negative[e.from]){
                negative[e.to] = true;
            }
        }
    }
    if(negative[N - 1])
        cout << "inf" << endl;
    else
        cout << -ans << endl;

    //ll x = -shortest_path(0);
    //cout << x << endl;
    //bool b = shortest_path2(N - 1);
    //cout << y << endl;
    /*if(b){
        cout << "inf" << endl;
    }
    else {
        cout << x << endl;
    }*/

    return 0;
}

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

int main() {
  
string S;
cin >> S;
  if(S=="Sunny"){
    cout << "Cloudy" << endl;
  }
  if(S=="Cloudy"){
    cout << "Rainy" << endl;
  }
  if(S=="Rainy"){
    cout << "Sunny" << endl;
  }

}

Measured memory_bytes: 256
t1, t2 = map(int, input().split())
a1, a2 = map(int, input().split())
b1, b2 = map(int, input().split())
atot1 = (a1 - b1) * t1
atot2 = (a2 - b2) * t2
if atot1 > 0:
    atot1 *= -1
    atot2 *= -1


if atot1 + atot2 < 0:
    print(0)
    exit()
if atot1 == - atot2:
    print('infinity')
    exit()
S = (-atot1) // (atot1 + atot2)
T = (-atot1) % (atot1 + atot2)
if T != 0:
    print(2 * S + 1)
else:
    print(2 * S)


Measured memory_bytes: 9204