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 sx = sc.nextInt();
		int sy = sc.nextInt();
		int tx = sc.nextInt();
		int ty = sc.nextInt();
		int lx = 0;
		int ly = 0;
		
		lx = Math.abs(tx - sx);
		ly = Math.abs(ty - sy);
		
		for(int i = 0; i < ly; i++){System.out.print("U");}
		for(int i = 0; i < lx; i++){System.out.print("R");}
		for(int i = 0; i < ly; i++){System.out.print("D");}
		for(int i = 0; i < lx + 1; i++){System.out.print("L");}
		for(int i = 0; i < ly + 1; i++){System.out.print("U");}
		for(int i = 0; i < lx + 1; i++){System.out.print("R");}
		System.out.print("D");
		System.out.print("R");
		for(int i = 0; i < ly + 1; i++){System.out.print("D");}
		for(int i = 0; i < lx + 1; i++){System.out.print("L");}
		System.out.println("U");
		
	}}

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> v;
  for (int i = 0; i < N; i++) {
    v.push_back(i+1);
  }

  int a, b;
  map<int, set<int>> Mp;
  for (int i = 0; i < M; i++) {
    cin >> a >> b;
    Mp[a].insert(b);
    Mp[b].insert(a);
  }

  int ans = 0;
  do {
    if (v[0] != 1) continue;
    int x = 1;
    for (int i = 0; i < N-1; i++) {
      a = v[i];
      b = v[i+1];
      if (Mp[a].count(b) == 0) {
        x = 0;
        break;
      }
    }
    ans += x;
  } while (next_permutation(v.begin(), v.end()));
  cout << ans << endl;
}

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

#define f(i,a,b) for(int i=a;i<b;i++)
#define f1(i,a,b) for(int i=a;i<=b;i++)
#define int long long
using namespace std;
#define mod 1000000007

signed main(){
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL); cout.tie(NULL);
  
  string s;
  cin>>s;
  vector<int>arr;
  int count=0;
  for(int i=0;i<s.length();i++){
      if(s[i]=='R'){
          count++;
      }
      else{
          arr.pb(count);
          count=0;
      }
  }
  arr.pb(count);
  cout<<*max_element(arr.begin(),arr.end())<<endl;
  return 0;
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;

int main() {
    int K;
    cin >> K;
    vector<ll> a(K);
    rep(i, K) cin >> a[i];
    reverse(a.begin(), a.end());

    ll L = 2, R = 2;
    rep(i, K) {
        L = a[i] * ceil(L / (a[i] + .0));
        R = a[i] * (R / a[i]) + a[i] - 1;
    }

    if (L > R) cout << -1 << endl;
    else cout << L << " " << R << endl;
}

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

ll countPrimes(ll n)
{
  map<ll,int> m;
   for (ll i=2;i*i<=n;i++)
   {
     while (n%i==0)
     {
       m[i]++;
       n/=i;
     }
   }
  if (n != 1) m[n]++;
  return (m.size());
}

int main()
{
  ll a,b;cin>>a>>b;
  ll g = __gcd(a,b);  
  cout<<countPrimes(g)+1<<endl;
}

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

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define repr(i,n) for(int i=(n);i>=0;--i)
#define cinv(n,a) VL a(n);rep(i,n)cin>>a[i]
#define int long long
#define itn int
#define pb push_back
#define m_p make_pair
#define m_t make_tuple
#define p_p(a,b) pb(m_p(a,b))
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(all(a));reverse(all(a))
#define UNIQUE(a) a.erase(unique(all(a)),a.end())
#define SZ(a) (ll)(a.size())
#define ENDL cout<<endl
#define debg(a) cout<<#a<<" "<<a<<endl;
#define debgp(a) cout<<#a<<" "<<a.fi<<" : "<<a.se<<endl
#define call(a) for(auto i:a)cout<<i<<" ";cout<<endl
#define show(a) for(cont &y:a){for(cont &x:y){cout<<x<<" ";}cout<<endl;}
#define out(a) cout<<(a)<<endl
#define cont const auto
#define fi first
#define se second
#define V vector
#define P pair
#define VV(type,name,y,x,a) vector<vector<type>> name = vector<vector<type>>(y,vector<type>(x,a))
#define PQ priority_queue
typedef long long ll;
typedef double D;
typedef long double LD;
typedef string str;
typedef vector<ll> VL;
typedef pair<ll,ll> PL;
typedef vector<PL> VP;
const long long INF = 1LL<<60;
const long long MOD = 1e9+7;
void Yes(){cout<<"Yes"<<endl;}
void No(){cout<<"No"<<endl;}
void YN(bool b){cout<<(b?"Yes":"No")<<endl;}
template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T>inline bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}

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

  int n;
  cin>>n;
  cinv(n,a);
  
  int eve=1,res=pow(3,n);
  rep(i,n)if(a[i]%2==0)eve*=2;
  res-=eve;
  out(res);
  

  
  return 0;
}



Measured memory_bytes: 384
/******************************************
*    AUTHOR:         CHIRAG AGARWAL       *
*    INSTITUITION:   BITS PILANI, PILANI  *
******************************************/
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL; 
typedef long double LD;
 
const int MAX = 2e5 + 5;
const int inf = 1e9;
 
set<int> g[MAX], g2[MAX];
vector<int> tree[MAX];
bool vis[MAX];
int dis[MAX], pre[MAX];
 
void dfs(int u) {
	vis[u] = 1;
	for(auto v : g[u]) {
		if (!vis[v]) {
			tree[u].push_back(v);
			tree[v].push_back(u);
			dfs(v);
		}
	}
}
 
int main() {
	int n, m, x, y;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		scanf("%d %d", &x, &y);
		g[x].insert(y);
		g[y].insert(x);
		g2[x].insert(y);
		g2[y].insert(x);
	}
	dfs(1);
	queue<int> q;
	q.push(1);
	fill(dis, dis+MAX, inf);
	dis[1] = 0;
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(auto v : tree[u]) {
			if (dis[v] == inf) {
				dis[v] = dis[u] + 1;
				pre[v] = u;
				q.push(v);
			}
		}
	}
	int s = 1;
	for(int i = 1; i <= n; ++i) {
		if (dis[i] < inf && dis[i] > dis[s]) {
			s = i;
		}
	}
	q.push(s);
	fill(dis, dis+MAX, inf);
	dis[s] = 0;
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		for(auto v : tree[u]) {
			if (dis[v] == inf) {
				dis[v] = dis[u] + 1;
				pre[v] = u;
				q.push(v);
			}
		}
	}
	int t = s;
	for(int i = 1; i <= n; ++i) {
		if (dis[i] < inf && dis[i] > dis[t]) {
			t = i;
		}
	}
	fill(vis, vis+MAX, 0);
	vector<int> path;
	x = t;
	while(x > 0 && x != s) {
		path.push_back(x);
		x = pre[x];
	}
	path.push_back(x);
	for(auto it : path) {
		vis[it] = 1;
	}
	assert(path.size() >= 2);
	bool check = true;
	for(auto v : g[path[0]]) {
		check &= vis[v];
	}
	for(auto v : g[path.back()]) {
		check &= vis[v];
	}
	if (check) {
		printf("%d\n", (int)path.size());
		for(auto it : path) {
			printf("%d ", it);
		}
		printf("\n");
		return 0;
	}
	while(1) {
		int c = path.size();
		for(auto v : g[path.back()]) {
			if (!vis[v]) {
				path.push_back(v);
				vis[v] = 1;
				break;
			}
		}
		if (path.size() == c) {
			break;
		}
	}
	reverse(path.begin(), path.end());
	while(1) {
		int c = path.size();
		for(auto v : g[path.back()]) {
			if (!vis[v]) {
				path.push_back(v);
				vis[v] = 1;
				break;
			}
		}
		if (path.size() == c) {
			break;
		}
	}
	set<int> go;
	for(auto it : path) {
		assert(it >= 1);
		go.insert(it);
	}
	assert(path.size() >= 2);
	assert(path.size() == go.size());
	for(auto it : g[path[0]]) {
		assert(go.find(it) != go.end());
	}
	for(auto it : g[path.back()]) {
		assert(go.find(it) != go.end());
	}
	printf("%d\n", (int)path.size());
	for(auto it : path) printf("%d ", it);
	printf("\n");
	return 0;
}

Measured memory_bytes: 52344
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;

typedef long long LL;

int n,k,A[20];
bool vis[20];
LL Ans = 1E16;

void Check()
{
	LL now = 0; int Max = 0;
	for (int i = 1; i <= n; i++)
	{
		if (!vis[i]) {Max = max(Max,A[i]); continue;}
		if (A[i] <= Max)
		{
			now += 1LL * (Max - A[i] + 1);
			++Max;
		}
		else Max = A[i];
	}
	Ans = min(Ans,now);
}

void Dfs(int x,int tot)
{
	if (tot + n - x + 1 < k) return;
	if (tot == k) {Check(); return;}
	vis[x] = 1; Dfs(x + 1,tot + 1);
	vis[x] = 0; Dfs(x + 1,tot);
}

int main()
{
	#ifdef DMC
		freopen("DMC.txt","r",stdin);
	#endif
	
	cin >> n >> k;
	for (int i = 1; i <= n; i++) scanf("%d",&A[i]);
	Dfs(1,0); cout << Ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
char str[50] ,str2[50] ;
scanf("%s%s",&str,&str2);
    if(str[0] == str2[2] && str[2]==str2[0] && str[1] ==str2[1]){

    printf("YES");
    }else{
        printf("NO");
    }
}


Measured memory_bytes: 128
#include <iostream>
#include <string>

using namespace std;

int main()
{
  int N;
  string S;
  cin >> N >> S;

  int rE = 0;
  for (int i = 0; i < N; i++) {
    if (S[i] == 'E') rE++;
  }

  int lW = 0, lE = 0;
  int ans = 1100000000;
  for (int i = 0; i < N; i++) {
    if (S[i] == 'E') lE++;
    ans = min(ans, lW + (rE - lE));
    if (S[i] == 'W') lW++;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 900
#include<bits/stdc++.h>
using namespace std;
int const nax = 3e5 + 10;

int main () {
    int a, b, c;

    cin >> a >> b >> c;

    swap(a, b);
    swap(a, c);

    printf("%d %d %d\n", a, b, c);
}
/*
    Good Luck
        -Lucina
*/


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
	int a[3];
	for (int i=0; i<3; i++) cin >> a[i];
	for (int i=0; i<3; i++) {
		for (int j=0; j<i; j++) {
			if (a[i] < a[j]) {
				int tmp = a[j];
				a[j] = a[i];
				a[i] = tmp;
			}
		}
	}
	cout << a[0];
	for (int i=1; i<3; i++) cout << " " << a[i];
	cout << endl;
	return 0;
}

Measured memory_bytes: 3084
import java.util.Scanner;

public class Main {

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

        int count = 1;
        int a = scanner.nextInt();
        while( a > 0 ){
            System.out.println("Case "+count+": "+a);
            a = scanner.nextInt();
            count++;
        }
    }
}



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

struct Node{
    int key;
    Node *right, *parent, *left;
};

Node *root;
Node *NIL;

Node* treeMinimum(Node *x){
    while(x->left != NIL){
        x = x->left;
    }
    return x;
}

Node* find(Node *u, int x){
    while(u != NIL && u->key != x){
        if(u->key < x){
            u = u->right;
        }else{
            u = u->left;
        }
    }
    return u;
}

Node* treeSuccessor(Node *x){
    if(x->right != NIL){
        return treeMinimum(x->right);
    }

    Node *y = x->parent;
    while(y != NIL && x == y->right){
        x = y;
        y = y->parent;
    }

    return y;
}

void treeDelete(Node *z){
    Node *y; // 削除対象のノード
    Node *x; // y の子

    if(z->left == NIL || z->right == NIL){
        y = z;
    }else{
        y = treeSuccessor(z);
    }

    if(y->left != NIL){
        x = y->left;  // x has a left child
    }else{
        x = y->right; // x has a right child, or no child
    }

    if(x != NIL){
        x->parent = y->parent;
    }

    if(y->parent == NIL){
        root = x;
    }else{
        if(y == y->parent->left){
            y->parent->left = x;
        }else{
            y->parent->right = x;
        }
    }

    if(y != z){
        z->key = y->key;
    }

    free(y);
}

void insert(int k){
    Node *y = NIL;
    Node *x = root; // 走査用
    Node *z;

    z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;

    while(x != NIL){
        y = x;
        if(x->key > z->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }

    z->parent = y;
    if(y == NIL){
        root = z;
    }else if(y->key > z->key){
        y->left = z;
    }else{
        y->right = z;
    }
}

void inorder(Node *u){
    if(u == NIL)    return;
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);
}

void preorder(Node *u){
    if(u == NIL)    return;
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
}

int main(){
    int n, i, x;
    string com;
    scanf("%d", &n);
    
    for(i = 0; i < n; i++){
        cin >> com;
        if(com == "insert"){
            scanf("%d", &x);
            insert(x);
        }else if(com == "print"){
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }else if(com == "find"){
            scanf("%d", &x);
            if(find(root, x) != NIL) printf("yes\n");
            else               printf("no\n");
        }else if(com == "delete"){
            scanf("%d", &x);
            treeDelete(find(root, x));
        }
    }

    return 0;
}


Measured memory_bytes: 22040
#include<bits/stdc++.h>
#define MOD 1000000007
#define MOD2 1000000006
#define TEMPMOD1 998244353
#define TEMPMOD2 998244352
#define INF 1000000000000000007
#define NEGINF -1000000000000000007
#define vll vector<ll> 
#define vvll vector<vector<ll>>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define plll pair<ll,pll>
#define vpll vector<pll>
using namespace std;
typedef long long int ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    ll n,k;
    cin>>n>>k;
    ll val=(n+1)/2;
    if(val>=k)
    {
        cout<<"YES";
    }
    else
    {
        cout<<"NO";
    }
    return 0;
}

Measured memory_bytes: 256
import collections
import numpy as np

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0 for _ in range(Q)]
C = [0 for _ in range(Q)]
for i in range(Q):
  B[i], C[i] = map(int, input().split())
  
a = collections.Counter(A)
S = np.sum(A)
for i in range(Q):
  S += (C[i]-B[i]) * a[B[i]]
  a[C[i]] += a[B[i]]
  a[B[i]] = 0

  print(S)

Measured memory_bytes: 47768
////////////////////////// Author
////////////////////////// Nasim Hossain Rabbi
////////////////////////// JU-CSE28
////////////////////////// CF - imnasim3.1415
////////////////////////// UVA - imnasim3.1415
////////////////////////// Mail - imnasim3.1415@gmail.com
#include<bits/stdc++.h>
using namespace std;
#define E end()
#define B begin()
#define sz size()
#define EM empty()
#define clr clear()
#define sqr(a) (a*a)
#define mk make_pair
#define pb push_back
string en="\n";
string t="hello";
string Y="YES\n";
string N="NO\n";
#define rep(i,n) for(i=0;i<n;i++)
#define Rep(i,n) for(i=1;i<=n;i++)
#define per(i,n) for(i=n-1;i>=0;i--)
#define peR(i,n) for(i=n;i>0;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define all(cont) cont.begin(),cont.end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define pi 3.1415926535897932384626433832795
#define vi vector<int>
#define vl vector<long long>
#define vs vector<string>
#define vp(vi,x) cin>>x; vi.pb(x);
#define srch(a,x) binary_search(all(a),x)
#define LB(a,x) (lower_bound(all(a),x)-a.B)
#define UB(a,x) (upper_bound(all(a),x)-a.B)
typedef long long LL;
typedef unsigned long long ULL;
bool isprm(LL a){for(LL i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
bool isVowel(char ch){ ch=toupper(ch); if(ch=='A'||ch=='U'||ch=='I'||ch=='O'||ch=='E') return true; return false;}
int toInt(string s){int sm;stringstream ss(s);ss>>sm;return sm;}
template<typename T>inline T gcd(T a,T b){if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<typename T>inline T lcm(T a,T b) {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
int main()
{
//    fast;
    LL i,j,k,n,m,l,s=0,x,y,tc=1,c=0;
    string a,b;
    while(cin>>a>>b)
    {
        s=0;
        rep(i,a.sz)
    {
        if(a.at(i)==b.at(i)) s++;
    }
    cout<<s<<en;
    }
}



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++)
using P = pair<int, int>;
#define LARGE 1000000007

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

	ll a[n];
    ll sa=0;
	rep(i, n) {
        ll A=0;
        cin >> A;
        a[i] = A;
        sa += A;
        sa = sa % LARGE;
    }

	ll sum=0;
	for(int i=0; i<n-1; i++) {
        sa -= a[i];
        if(sa < 0) sa += LARGE;
        ll d = (sa * a[i]) % LARGE;
        sum += d;
        sum = sum % LARGE;
	}

	cout << sum << endl;
	return 0;
}


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

int main() {
  int x, n;
  cin >> x >> n;
  vector<bool> p(100, true);
  for(int i=0; i<n; i++) {
    int a;
    cin >> a;
    p.at(a-1) = false;
  }
  int abs = 101;
  int ans;
  for(int i=x; i<100; i++) {
    if(p.at(i)) {
      abs = i - (x-1);
      ans = i+1;
      break;
    }
  }
  for(int i=x-1; i>=0; i--) {
    if(p.at(i)) {
      int temp = (x-1) - i;
      if(temp <= abs) {
        abs = temp;
        ans = i+1;
        break;
      }
    }
  }
  if(101-x < abs) {
    abs = 101-x;
    ans = 101;
  }
  if(x <= abs) {
    ans = 0;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3632
/**
 *      author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *      created : 2019-11-22:17:27:25
**/

#include <iostream>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
#include <bitset>
#include <cassert>
#include <cctype>
#include <functional>
#include <iomanip>
#include <random>
#include <utility>

using namespace std;

using int64 = long long;
#define debug(_) cerr << #_ << ": " << (_) << '\n'
template<typename T> inline void chmin(T &a, T b) { if (a > b) a = b; return; }
template<typename T> inline void chmax(T &a, T b) { if (a < b) a = b; return; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& vec) { os << '{'; for (size_t i = 0; i < vec.size(); ++i) { os << vec[i]; if (i != vec.size() - 1) os << ','; } os << '}'; return os; }
template<typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) { return os << '{' << p.first << " " << p.second << '}'; }

constexpr int INF = 2e9;

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

  int n; cin >> n; int k; cin >> k;
  vector<int> h(n);
  for (int i = 0; i < n; ++i) cin >> h[i];

  vector<int> dp(n + 5, INF);
  dp[0] = 0;

  for (int i = 1; i < n; ++i) {
    for (int j = 1; j <= k; ++j) {
      if (i - j >= 0) {
        chmin(dp[i], dp[i - j] + abs(h[i] - h[i - j]));
      }
    }
  }
  //debug(dp);

  cout << dp[n - 1] << endl;

  return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>

#include <map>
#include <queue>
 
#define mem(a, b) memset(a, (b), sizeof(a))
 
using namespace std;
typedef long long ll;
 
const int N = 3e4 + 10;
const int Max = 1e9 + 10;
#define MAXN 40005  

int main(){
	ll a, b , c, k;
	while(~scanf("%lld %lld %lld %lld", &a, &b, &c, &k)){
		if(k % 2 == 1)
			printf("%lld\n", b - a);
		else
			printf("%lld\n", a - b);
	}
}


Measured memory_bytes: 256
"use strict";

const Main = (input) => {
    input = input.split("\n");
    let nums = input[1].split(" ");
  	let count = 0;
  
  	for(let i = 0; i < nums.length; i++){
    	nums[i] = parseInt(nums[i]);
    }
  
	while(true){
    let oddFlag = false;
    for(let i = 0; i < nums.length; i++){
		if(nums[i] % 2 == 1){
        	oddFlag = true;
        }
    }
    
      if(oddFlag){
     	 break;
      }
      
      for(let i = 0; i< nums.length; i++){
      	nums[i] = nums[i] / 2;
      }
    count++;

    }
  
console.log(count);  




}

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


Measured memory_bytes: 7372
M,*a=10**9+7;
*I=r=j=1;
n,*z=`dd`.split.map &:to_i;
(0..n).map{|i|a[k=z[i]]?X=a[k]+n-i:a[k]=i};
(0..n).map{|i|I<<s=i<1?1:(M-M/-~i)*I[M%-~i];p ((r=r*(n+1-i)*s%M)-j)%M;j=j*(X-i)*s%M}

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

#define FOR(i,a,b) for(int i=(a);i<(int)(b);i++)
#define rep(i,n) FOR(i,0,n)
#define ZERO(a) memset(a,0,sizeof(a))

int n,m;
int a[120];

int main() {
    while(cin>>n>>m && n) {
        ZERO(a);
        rep(i,n) rep(j,m) {
            int t;
            scanf("%d", &t);
            if(t == 1) ++a[j];
        }
        int b[120] = {0};
        rep(i,m) b[i] = i+1;

        rep(i,m) rep(j,m-1) if(a[j] < a[j+1]) {
            swap(a[j], a[j+1]);
            swap(b[j], b[j+1]);
        }

        rep(i,m) {
            cout << b[i];
            if(i != m-1) cout << " ";
        }
        puts("");
    }

    return 0;
}

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

const ll MOD = 1000000007LL;

int main(){
    int n;
    cin >> n;
    int sum = 0;
    rep(i, n){
        int a;
        cin >> a;
        sum += a;
    }
    cout << sum-n << endl;
}

Measured memory_bytes: 3588
#include<stdio.h>
#include<math.h>
int main()
{
  int N,i,j;
  scanf("%d",&N);
  
  if(N%2==0){
    printf("%d\n",N*(N-2)/2);
    
    for(i=1;i<=N-1;i++){
      for(j=i+1;j<=N;j++){
        if((i+j)!=(N+1)){
          printf("%d %d\n",i,j);
        }
      }
    }
    
  } else {
        printf("%d\n",((N-1)*(N-3)/2 + (N-1)));
    
    for(i=1;i<=N-2;i++){
      for(j=i+1;j<=N-1;j++){
        if((i+j)!=N){
          printf("%d %d\n",i,j);
        }
      }
    }
    for(i=1;i<=N-1;i++){
      printf("%d %d\n",i,N);
    }
  }
  
  return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define _abs(x)((x) < 0 ? (x) * -1 : (x))
#define _max(x, y)(max(0, max((x), (y))))
#define _min(x, y)(max(0, min((x), (y))))

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    //freopen("debug.txt", "w", stderr);

    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;

    cin >> n;

    vector<int> v(n);
    stack<int> data;
    int sum = 0;
    int ans = 0;
    int s;

    int i;

    for (i = 0; i < n; i++) {
        cin >> v[i];

        sum += v[i];
    }

    if (sum % 10 == 0) {
        for (i = 0; i < n; i++) {
            s = v[i];

            if ((sum - s) % 10 != 0) ans = max(ans, sum - s);
        }
    } else {
        ans = sum;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std; 
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define int long long int
#define rep(i,a,b) for(int i=a;i<b;i++)
#define reprev(i,a,b) for(int i=b-1;i>=a;i--)
#define all(c) c.begin(),c.end()
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define vin(a,n) vi a(n); rep(i,0,n) cin>>a[i];
#define vout(a,n) rep(i,0,n) cout<<a[i]<<" "; cout<<endl;
#define mapp map<int,int>
#define pb push_back
#define mp  make_pair
#define mod 1000000007
#define mod2 998244353
#define tr(container, it) \
for(auto it = container.begin(); it != container.end(); it++)
 
bool comps(const pair<int,int> &a, const pair<int,int> &b) {return (a.second<b.second);} 

int fac[100001];
int power(int x, unsigned int y)
{ 
    int temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2); 
    if (y%2 == 0) 
        return temp*temp; 
    else
        return x*temp*temp; 
}

int powerp(int x, unsigned int y, int p)  
{  
    int res = 1;     // Initialize result  
  
    x = x % p; // Update x if it is more than or  
                // equal to p 
   
    if (x == 0) return 0; // In case x is divisible by p; 
  
    while (y > 0)  
    {  
        // If y is odd, multiply x with result  
        if (y & 1)  
            res = (res*x) % p;  
  
        // y must be even now  
        y = y>>1; // y = y/2  
        x = (x*x) % p;  
    }  
    return res;  
}

int binomialCoeff(int n, int k)
{  
    // Base Cases  
    if (k == 0 || k == n)  
        return 1;  
  
    // Recur  
    return binomialCoeff(n - 1, k - 1) +  
                binomialCoeff(n - 1, k);  
}
void precomp()
{ 
    fac[0] = 1; 
    for (int i=1 ; i<=100000; i++) 
        fac[i] = fac[i-1]*i%mod;
}
int modInverse(int n, int p) {return powerp(n, p-2, p);}
int nCrModPFermat(int n, int r, int p) 
{ 
   // Base case 
   if (r==0) 
      return 1; 
  
    // Fill factorial array so that we 
    // can find all factorial of r, n 
    // and n-r   
    return (fac[n]* modInverse(fac[r], p) % p * 
            modInverse(fac[n-r], p) % p) % p; 
} 
signed main()
{
    
    IOS
    int n;
    cin>>n;
    vin(a,n);
    mapp m;int res=0;m[a[0]]=1;
    rep(j,1,n)
    {
        if(m.find(j-a[j])!=m.end()) res+=m[j-a[j]];
        m[j+a[j]]++;
    }
    cout<<res;
    return 0;
}

Measured memory_bytes: 17104
N = [0] + list(map(int, input()))
K = int(input())
n = len(N)

DP = [
      [[0] * (5) for _ in range(2)] for _ in range(n)
]

# 0桁目(0)で最大値を取っていてk=0の要素は1個。
DP[0][0][0] = 1

for i in range(1, n):
  for k in range(4):
    if N[i] != 0:
      DP[i][0][k+1] += DP[i-1][0][k]
      DP[i][1][k] += DP[i-1][0][k]
      DP[i][1][k+1] += DP[i-1][0][k] * (N[i] - 1)
    else:
      DP[i][0][k] += DP[i-1][0][k]
    DP[i][1][k] += DP[i-1][1][k]
    DP[i][1][k+1] += DP[i-1][1][k] * 9
print(DP[n-1][1][K] + DP[n-1][0][K])

Measured memory_bytes: 3064
from collections import deque
H,W=map(int,input().split())
stack=deque()
c=[input() for i in range(H)]
ans=0
for ci in c:
    for j in ci:
        if j==".":
            ans+=1
reached=[[0]*W for i in range(H)]
stack.append((0,0))
dydx=[(1,0),(-1,0),(0,1),(0,-1)]
while(stack):
    Y,X=stack.popleft()
    for dy,dx in dydx:
        y=Y+dy
        x=X+dx
        if y<0 or y>=H or x<0 or x>=W or c[y][x]=="#":
            continue
        if reached[y][x]!=0:
            continue
        stack.append((y,x))
        reached[y][x]=reached[Y][X]+1
if reached[H-1][W-1]==0:
    print(-1)
else:
    print(ans-(reached[H-1][W-1]+1))


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

using namespace std;


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

    int n;
    cin >> n;
    int a;
    cin >> a;
    n %= 500;
    if (n <= a) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
#define P pair<int, int>
#define F first
#define S second
#define mod 1000000007
#define INF 9000000000000000000
signed main() {
    static const double pi = 3.141592653589793;
    long double a,b,x;cin>>a>>b>>x;
    cout << fixed<<setprecision(10);
    long double f=0.0,e=pi/2,t;
    rep(i,10000){
        t=(f+e)/2;
        if(b*tan(t)>a){
            //cout<<i<<' ';
            if(a*a*b-a*(a/tan(t)*a/2)>=x)e=t;
            else f=t;
        }
        else{
            //cout<<a*b*tan(t)*b/2<<' '<<x<<' ';
            if(a*b*tan(t)*b/2>=x){e=t;}
            else f=t;
        }
        //cout<<b*tan(t)<<' '<<f*180/pi<<' '<<t*180/pi<<endl;
    }
    cout<<(long double)90-(long double)180*t/pi<<endl;
}

Measured memory_bytes: 384
def crt(R, M):
    def exEuclid(a, mod):
        b = mod
        s, u = 1, 0
        while b:
            q = a // b
            a, b = b, a % b
            s, u = u, s - q * u
        return a, s % mod
    assert len(R) == len(M)
    r0, m0 = 0, 1
    for r, m in zip(R, M):
        assert m >= 1
        r %= m
        if m0 < m:
            r0, r = r, r0
            m0, m = m, m0
        if m0 % m == 0:
            if r0 % m != r:
                return (0, 0)
            continue
        g, im = exEuclid(m0, m)
        u = m // g
        if (r - r0) % g:
            return (0, 0)
        x = (r - r0) // g % u * im % u
        r0 += x * m0
        m0 *= u
        if r0 < 0:
            r0 += m0
    return (r0, m0)


def atcoder_acl1_b():
    N = int(input())
    def divisor(n):
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                yield i
                if i != n // i:
                    yield n // i

    ans = 10**20
    for x in divisor(2*N):
        kc, _ = crt([0, -1], (x, 2*N//x))
        if kc != 0:
            ans = min(ans, kc)
    print(ans)


if __name__ == '__main__':
    atcoder_acl1_b()


Measured memory_bytes: 68932
#include <bits/stdc++.h>
#define rep1(i,s,e,c) for(int i=s;i<e;i=i+c)
#define rep2(i,s,e,c) for(int i=s;i<=e;i=i+c)
#define rep3(i,e,s,c) for(int i=e;i>=s;i=i-c)
using namespace std;
typedef long long ll;
const int MAX=1e5+5;
const int MOD=1e9+7;
map<string,int> Map;
char str[15];
int main()
{    
    int n;
    cin>>n;
    ll ans=0;
    for(int i=1;i<=n;i++){
    	scanf("%s",&str);
    	sort(str,str+10);
    	string s="";
    	for(int i=0;i<10;i++){
    		s+=str[i];
		}
		Map[s]++;
		ans+=Map[s]-1;
	}
	cout<<ans<<"\n";
    return 0;
}

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

const int MAX_N = 110000;

int memo[MAX_N];
int rec(int n) {
    if (n == 0) return 0;
    if (memo[n] != -1) return memo[n];

    int res = n;

    for (int pow6 = 1; pow6 <= n; pow6 *= 6) res = min(res, rec(n - pow6) + 1);
    for (int pow9 = 1; pow9 <= n; pow9 *= 9) res = min(res, rec(n - pow9) + 1);
    return memo[n] = res;
}

int main() {
    int N; cin >> N;
    for (int i = 0; i < MAX_N; ++i) memo[i] = -1;
    cout << rec(N) << endl;
}


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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

std::string N;
int K;
int len;
ll dp[120][2][120];

ll rec(int i, int s1, int s2){
    if(i == len){
        return s2 == K;
    }

    if(dp[i][s1][s2] != -1){
        return dp[i][s1][s2];
    }

    int d = N[i] - '0';
    ll res = rec(i + 1, s1 || (d > 0), s2);
    
    int mx = s1 ? 9 : d;
    for(int j=1;j<=mx;++j){
        res += rec(i + 1, s1 || (d > j), s2 + 1);
    }

    return dp[i][s1][s2] = res;
}

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

  std::cin >> N >> K;
  len = N.size();

  memset(dp, -1, sizeof(dp));

  ll res = rec(0, 0, 0);
  std::cout << res << std::endl;
}


Measured memory_bytes: 512
N = int(input())
A = list(map(int, input().split()))

tmp = 0
A.sort(reverse=True)
for i in A:
    tmp ^= i

flag = False
if N % 3 == 0:
    if tmp == 0:
        flag = True
elif N % 3 == 1:
    if tmp == A[-1]:
        flag = True
elif N % 3 == 2:
    if tmp == (A[-1] ^ A[-2]):
        flag = True

print('Yes' if flag else 'No')

Measured memory_bytes: 14212
let solve x =
    let rec _solve x n i =
        if x >= i
        then _solve x ((n lsl 1) lor 1) (i + 1)
        else (n - 1) in
    _solve x 3 1

let () =
    let x = read_int () in
    print_int (solve x);
    print_newline ();;


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    ll n,a,b;
    cin>>n>>a>>b;
    ll var1=n%(a+b);
    ll var2=n/(a+b);
    ll ans=var2*a + min(var1,a);  
	cout<<ans; 
	return 0;
}

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

int main(){
  int m;
  cin >> m;
  ll d[m], c[m];
  ll sum = 0, digit = 0;
  rep(i,m) {
    cin >> d[i] >> c[i];
    digit += c[i];
    sum += c[i] * d[i];
  }
  cout << digit - 1 + (sum - 1)/9 << endl;
  return 0;
}

Measured memory_bytes: 3328
from queue import Queue
n,q = map(int,input().split())
qe = Queue()
current = 0
for i in range(n):
    name, time = input().split()
    time = int(time)
    qe.put((name, time))

while not qe.empty():
    item = qe.get()
    if item is None:
        break
    name, time = item
    c = min(q, time)
    current += c
    time -= c
    if time > 0:
        qe.put((name, time))
    else:
        print(name + ' ' + str(current))

Measured memory_bytes: 15032
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
  int N, A, B;
  cin >> N >> A >> B;
  
  if(N < 1 || N > 20)
  {
    cout << "N(first input) must be between 1 and 20" << endl;
  	exit(1);
  }
  
  if(A < 1 || A > 100)
  {
    cout << "A(second input) must be between 1 and 100" << endl;
  	exit(1);
  }
  
  if(B < 1 || B > 2000)
  {
    cout << "B(third input) must be between 1 and 2000" << endl;
  	exit(1);
  }
  
  cout << min(A * N, B) << endl;
}

Measured memory_bytes: 256
N = int(input())
koma = list(map(int,input().split()))
M = int(input())
a = list(map(int,input().split()))

for i in a:
    if i == N:
        koma[i-1] = min(koma[i-1]+1, 2019)
    else:
        koma[i-1] = min(koma[i-1]+1, koma[i]-1)
        
for i in koma:
    print(i)



Measured memory_bytes: 5604
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug1: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug2: "<<x<<" "<<y<<endl;
#define bug3(x, y, z) cout<<"zdongdebug3: "<<x<<" "<<y<<" "<<z<<endl;
using namespace std;
typedef long long ll;
const int maxn = 2005;

int d[maxn][maxn];

void bfs(int st, int sx, int sy, int n) {
  queue<int>q;
  q.push(st);
  while(!q.empty()){
    int x = q.front();
    q.pop();
    if(x < n && d[st][x + 1] == -1) {
      d[st][x+1] = d[st][x] + 1;
      q.push(x+1);
    }
    if (x > 1 && d[st][x - 1] == -1) {
      d[st][x - 1] = d[st][x] + 1;
      q.push(x - 1);
    }
    int y = -1;
    if(x == sx) y = sy;
    else if(x==sy)y = sx;
    if(y!=-1&&d[st][y]==-1){
      d[st][y] = d[st][x] + 1;
      q.push(y);
    }
  }
}

int c[maxn];

int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
  int n, x,y;
  cin>>n>>x>>y;
  memset(d, -1, sizeof(d));
  for(int i=1;i<=n;i++)d[i][i] = 0;
  for(int i=1;i<=n;i++)bfs(i, x, y, n);
  for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++){
      c[d[i][j]]++;
    }
  for(int i=1;i<n;i++)cout<<c[i]<<endl;
  return 0;
}

Measured memory_bytes: 16000
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const ll MOD = 1e9 + 7;

int main(){
	double a,b,h,m; cin>>a>>b>>h>>m;
	double rada = h*30 + 0.5*m;
	double radb = 6*m;
	double rad = abs(rada-radb);
	rad = min(rad, 360-rad);
	if(rad == 180){cout<<a+b<<endl; return 0;}
	double ans = sqrt(a*a + b*b - 2*a*b*cos(rad/180*3.14159265358979));
	cout<<fixed<<setprecision(10)<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4212
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   for(int i=0;i<(n);++i)
#define SORT(c)    sort((c).begin(),(c).end())
#define CLR(a)     memset((&a), 0 ,sizeof(a))//clear memory
#define dump(x)    cerr << #x << " = " << (x) << endl;//debug
#define debug(x)   cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define EPS        1e-10//sample:if((double)>=(double)+EPS)
//cin,cout release
//std::cin.tie(0);
//ios::sync_with_stdio(false);

using namespace std;
int n;
int d[100000];
int color[100000];
vector<pair<int,int> > adj[100000];
#define WHITE 0
#define BLACK 2
#define GRAY 1
void dijkstra(){
  rep(i,n)d[i]=INT_MAX;
  priority_queue< pair<int,int> > PQ;
  rep(i,n)color[i]=WHITE;
  d[0]=0;
  PQ.push(make_pair(0,0));
  color[0]=GRAY;
  while(!PQ.empty()){
    pair<int,int> f=PQ.top();
    PQ.pop();
    int u=f.second;
    color[u]=BLACK;
    if(d[u]<f.first*(-1))continue;
    rep(j,(int)adj[u].size()){
      int v=adj[u][j].first;
      if(color[v]==BLACK)continue;
      if(d[v]>d[u]+adj[u][j].second){
	d[v]=d[u]+adj[u][j].second;
	PQ.push(make_pair(d[v]*(-1),v));
	color[v]=GRAY;
      }
    }
  }
  rep(i,n)cout<<i<<" "<<(d[i]==INT_MAX?-1:d[i])<<endl;
}


int main(){
  int a,b,c,d;
  cin>>n;
  rep(i,n){
    cin>>a>>b;
    rep(j,b){
      cin>>c>>d;
      adj[a].push_back(make_pair(c,d));
    }
  }
  dijkstra();
  return 0;
}


Measured memory_bytes: 10204
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 3010
using namespace std;
int n,v,x;
typedef long long ll;
ll dp[MAXN][MAXN];
int main(){
	SF("%d%d",&n,&x);
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		SF("%d",&v);	
		for(int j=i;j>=1;j--)
			for(int k=3000;k>=v;k--){
				dp[j][k]+=dp[j-1][k-v];
			}
	}
	ll ans=0;
	for(int i=1;i<=n;i++)
		ans+=dp[i][x*i];
	PF("%lld",ans);
}

Measured memory_bytes: 1408
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio>
#include<stdio.h>
#include<cmath>
#include<math.h>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<sstream>
#include<iomanip>
#define forn(i,n) for(int (i)=0;i<(n);i++)
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int>pii;
typedef long long ll;
typedef pair<ll,ll> pll;
const int MAXN=100005;
const int INF=2147483647;
const ll LINF=9223372036854775807;
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int n,a[105],ans;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	forn(i,n)cin>>a[i];
	sort(a,a+n);
	forn(i,n)for(int j=i+1;j<n;j++)for(int k=j+1;k<n;k++)
		if(a[i]+a[j]>a[k]&&a[i]!=a[j]&&a[j]!=a[k])ans++;
	cout<<ans;
	return 0;
}


Measured memory_bytes: 3604
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

N, k = map(int, input().split())
prev_arr = list(map(int, input().split()))

# N = k = 200000
# prev_arr = [0]*N

count = 0
for i in range(min(k, 3*int(math.log(N))+5)):
    que = []
    arr = [0]*N
    for j in range(N):
        heapq.heappush(que, j+prev_arr[j])
        while que[0] < j:
            heapq.heappop(que)
        arr[j] += len(que)
    # print(arr)

    que = []
    for j in reversed(range(N)):
        heapq.heappush(que, -(j-prev_arr[j]))
        while -que[0] > j:
            heapq.heappop(que)
        arr[j] += len(que) - 1

    prev_arr = arr
    count += 1

# print(count)
print(*prev_arr)


Measured memory_bytes: 185864
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1001001001LL;
constexpr long long LINF = 1001001001001001001;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
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; }


int main(){ 
    int h, w; cin >> h >> w;
    vector<string> grid(h); rep(i, h)cin >> grid[i];

    vector<vector<int>> DP(h, vector<int>(w, INF));
    DP[0][0] = 0;
    if(grid[0][0] == '#')DP[0][0]++;
    rep(i, h){
        rep(j, w){
            int num = DP[i][j];
            if(i<h-1){
                if(grid[i][j]== '.' && grid[i+1][j] == '#')chmin(DP[i+1][j], num + 1);
                else chmin(DP[i+1][j], num);
            }
            if(j<w-1){
                if(grid[i][j]== '.' && grid[i][j+1] == '#')chmin(DP[i][j+1], num + 1);
                else chmin(DP[i][j+1], num);
            }
        }
    }

    cout << DP[h-1][w-1] << ln;
}



Measured memory_bytes: 3672
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

typedef long long ll;

#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
#define INF 10e12
#define MOD 1000000000 + 7
#define MAX 51000
#define all(x) (x).begin(), (x).end()
#define MX(x) *max_element(all(x))
#define MN(x) *min_element(all(x))

using namespace std;

int main(void)
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<ll> p(n);
    rep(i, n) cin >> p[i];
    int ans = 0;
    for (int i = 1; i < n - 1; ++i)
    {
        if ((p[i - 1] < p[i] && p[i] < p[i + 1] || (p[i] < p[i - 1] && p[i + 1] < p[i])))
            ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 18;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<n;i++)
#define Se second
#define Fi first

int main() {
	int N, K, i, j;
	scanf("%d %d", &N, &K);

	int mn = INF;
	for (i = 0; i <= N; i++) {
		int v = 1;
		for (j = 1; j <= i; j++) v *= 2;
		for (j = 1; j <= N - i; j++) v += K;
		mn = min(mn, v);
	}
	return !printf("%d\n", mn);
}

Measured memory_bytes: 256
n,m=map(int, input().split())
s = [0]*m
c = [0]*m
for i in range(m):
    s[i], c[i] = map(int, input().split())

ans=-1
if n==1:
    start=0
else:
    start=10**(n-1)
for i in range(start,10**n):
    for j in range(m):
        i=str(i)
        if int(i[s[j]-1])!=c[j]:
            break
    else:
        ans=i
        break
print(ans)

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

using namespace std;

int main(){
    string S;
    cin >> S;
    
    int cnt = 0;
    int len = S.length();
    int pa = 0; int pb = len - 1;
    while(pb >= pa){
        if(S[pa] == S[pb]){
            pa++; pb--;
            continue;
        } else if(S[pa] == 'x'){
            cnt++;
            pa++;
        } else if(S[pb] == 'x'){
            cnt++;
            pb--;
        } else {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << cnt << endl;
}


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

using namespace std;

int main()
{
  int N,M,X,Y;
  cin >> N >> M >> X >> Y;
  vector<int> x(N);
  vector<int> y(M);
  for(int i=0;i<N;i++)
    cin >> x[i];
  
  for(int i=0;i<M;i++)
    cin >> y[i];

  sort(x.begin(), x.end());
  sort(y.begin(), y.end());

  int Z = min(y.front(), Y);
  if( max(x.back(),X) < Z )
    cout << "No War" << endl;
  else
    cout << "War" << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
typedef struct l{
  int T;
  int C;
  struct l *N;
}L;
L *g[100001],*t;
int i,j,m,n,l,r,d,x[100001],e[100001];
void dfs(int a){
  L *k=g[a];
  while(k!=NULL){
    if(e[k->T]){e[k->T]=0;x[k->T]=x[a]+k->C;dfs(k->T);}
    else if(x[k->T]!=x[a]+k->C){printf("No");exit(0);}
    k=k->N;
  }
}
int main(){
  scanf("%d%d",&n,&m);
  for(i=0;i<=n;i++){g[i]=NULL;x[i]=0;e[i]=1;}
  for(j=0;j<m;j++){
    scanf("%d%d%d",&l,&r,&d);
    t=malloc(sizeof(L));t->T=r;t->C=-d;t->N=g[l];g[l]=t;
    t=malloc(sizeof(L));t->T=l;t->C=d;t->N=g[r];g[r]=t;
  }
  for(i=1;i<=n;i++)if(e[i]){e[i]=0;dfs(i);}
  printf("Yes");
}


Measured memory_bytes: 18560
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


x, y = map(int, input().split())
if 4*x-y>=0 and y>=2*x and (4*x-y)%2==0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9180
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
int INF = 100100101;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int a,b;
  cin>>a>>b;
  int one[] = {1,3,5,7,8,10,12};
  int two[] = {4,6,9,11};
  if(a == 2 || b == 2) {
    cout << "No" << endl;
    return 0;
  }
  if(find(begin(one), end(one), a) != end(one) && find(begin(one), end(one), b) != end(one)){
    cout << "Yes" << endl;
    return 0;
  }
  if(find(begin(two), end(two), a)!= end(two) && find(begin(two), end(two), b)!= end(two)) {
    cout << "Yes" << endl;
    return 0;
  }
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
from numpy import sqrt

N = int(input())
for _ in range(N):
    a, b = map(int, input().split())
    score = a*b
    ans = 2*int(sqrt(score))
    if (ans//2) ** 2 == a*b:
        ans -= 2
    if a == b:
        ans = 2*a - 2
    else:
        if a > b:
            a, b = b, a

        if b - a == 1:
            ans = 2*a - 2
        elif ans//2 * (ans//2+1) >= a*b:
            ans -= 2
        else:
            ans -= 1
    print(ans)

Measured memory_bytes: 20464
import sys
input = sys.stdin.buffer.readline

MOD = 10 ** 9 + 7
INF = 2 * 10**18

in_n = lambda: int(input())
in_nn = lambda: map(int, input().split())
in_s = lambda: input().rstrip().decode('utf-8')
in_map = lambda: [s == ord('.') for s in input() if s != ord('\n')]


def main():
    k = in_n()
    print("ACL" * k)


if __name__ == '__main__':
    main()


Measured memory_bytes: 61920
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
#define w1 first
#define w2 second
#define ls (x<<1)
#define rs (x<<1|1)
#define pb push_back
#define mid ((l+r)>>1)
#define SZ(x) ((x).size())
#define All(x) (x).begin(),(x).end()
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)])
template<class T>void read(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
int power(int x,int k,int p){int res=1;for(;k;k>>=1,x=1ll*x*x%p)if(k&1)res=1ll*res*x%p;return res;}
const int maxn=1e6+5;
char str[maxn];
int a[maxn];
int main(){
	scanf("%s",str+1);
	int len=strlen(str+1);
	rep(i,1,len)a[i]=str[i]-'0';
	reverse(a+1,a+len+1);
	a[0]=len;
	rep(i,1,len)a[i]*=9;
	rep(i,1,len)a[i+1]+=a[i]/10,a[i]%=10;
	while(a[len+1])len++,a[len+1]+=a[len]/10,a[len]%=10;
	int cnt=0;
	rep(i,1,len)cnt+=a[i];
	int ans=0;
	while(1){
		if(cnt<=9*ans){
			printf("%d\n",ans);
			return 0;
		}
		a[1]+=9;cnt+=9;
		rep(i,1,len){
			if(a[i]<10)break;
			cnt-=(a[i]/10)*10,cnt+=a[i]/10,a[i+1]+=a[i]/10,a[i]%=10;
		}
		while(a[len+1])len++,cnt-=(a[len]/10)*10,cnt+=a[len]/10,a[len+1]+=a[len]/10,a[len]%=10;
		ans++;
	}
	return 0;
}

Measured memory_bytes: 4608