akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
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);
  ll l, r; cin >> l >> r;
  if(r - l >= 2019) {
    cout << 0 << endl;
  } else {
    int modl = l % 2019, modr = r % 2019;
    ll mi = LINF;
    if(modl < modr) {
      for(ll i=modl;i<=modr;++i) {
        for(ll j=i+1;j<=modr;++j) {
          mi = min(mi, i * j % 2019);
        }
      }
    } else {
      for(ll i=modr;i<=modl;++i) {
        for(ll j=i+1;j<=modl;++j) {
          mi = min(mi, i * j % 2019);
        }
      }
    }
    cout << mi << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void){
	for(;;){
		int h, w;

		cin >> h >> w;
		if(h == 0 && w == 0)
			break;

		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++)
				cout << (i%(h-1) && j%(w-1) ? '.' : '#');
			cout << endl;
		}
		cout << endl;
	}
}



Measured memory_bytes: 3084
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
  int i,j,k;
  int l,n,m,x;
  while(cin>>l>>n>>m>>x,l||n||m||x){
    char s[31];
    int a[100],b[100],c[100],d[100];
    for(i=0;i<n;++i)
      cin>>s>>a[i]>>b[i];
    for(i=0;i<m;++i)
      cin>>s>>c[i]>>d[i];

    int e[1001][101]={},f[1001][101];
    for(i=0;i<n;++i){
      if(a[i]<=l)
	e[a[i]][0]=max(e[a[i]][0],b[i]);
    }
    for(i=0;i<n-1;++i){
      for(j=i+1;j<n;++j){
	if(a[i]+a[j]<=l)
	  e[a[i]+a[j]][0]=max(e[a[i]+a[j]][0],b[i]+b[j]);
      }
    }
    copy(e[0],e[0]+1001*101,f[0]);
    int mx=0;
    for(i=0;i<m;++i){
      for(j=0;j+c[i]<=l;++j){
	for(k=0;k<i+1;++k){
	  if(!e[j][k])
	    continue;
	  if(f[j+c[i]][k+1]<e[j][k]+d[i]){
	    f[j+c[i]][k+1]=e[j][k]+d[i];
	    if(k+1>=x&&mx<f[j+c[i]][k+1])
	      mx=f[j+c[i]][k+1];
	  }
	}
      }
      copy(f[0],f[0]+1001*101,e[0]);
    }
    cout<<mx<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
/**
 *    author:  otera    
**/
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cerr << #x << " = " << (x) << endl;
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; }

void solve() {
	int n; cin >> n;
    int ans = 1;
    vector<int> div;
    for(int i = 2; i * i <= (n - 1); ++ i) {
        if((n - 1) % i == 0) {
            ans ++;
            if(i * i != (n - 1)) ++ans;
        }
    }
    for(int i = 2; i * i <= n; ++ i) {
        if(n % i == 0) {
            div.pb(i);
            if(i * i != n) div.pb(n / i);
        }
    }
    for(int v: div) {
        int m = n;
        while(m % v == 0) {
            m /= v;
            if(m % v == 1) {
                ++ ans;
                break;
            } else if(m % v != 0) {
                break;
            }
        }
    }
    if(n == 2) {
        cout << 1 << endl;
        return;
    }
    cout << ans + 1 << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//int t; cin >> t; rep(i, t)solve();
	solve();
    return 0;
}

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

using namespace std;
using ll = long long int;
using P = pair<int, int>;

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

int main(void){

    int n, k;
    cin >> n >> k;

    vector<int> ch(n, 0);
    roop(i, k){
        int d;
        cin >> d;
        roop(j, d){
            int a;
            cin >> a;
            ch[a-1]++;
        }
    }

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


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

Measured memory_bytes: 3628
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i, n) for(int i=0; i < n; ++i)
#define repe(i, n) for(int i=0; i <= n; ++i)
#define repr(i, n) for(int i=n-1; i > 0; --i)
#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x)
#define eb(x,y) emplace_back(x,y)
#define PI 3.14159265359
#define vi vector<int>
#define vl vector<ll>
using namespace std;
template <class T> bool chmax(T &a, const T &b) {if (a<b) {a = b; return 1;} return 0;}
template <class T> bool chmin(T &a, const T &b) {if (b<a) {a = b; return 1;} return 0;}
template <class T> using V=vector<T>;
const int INF = 1e9;
const int MOD = 1000000007;
using Graph = vector<vector<int>>;
ll gcd(ll a, ll b) {return b ? gcd(a, a%b) : a;}
ll lcm(ll a, ll b) {return a*b/gcd(a,b);}
ll nlcm(vector<ll> a) {
    ll res;
    res = a[0];
    for(ll i=1; i<a.size(); ++i) {
        res = lcm(res, a[i]);
    }
    return res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    int sum = 0;
    vl a(n);
    rep(i,n) {
        cin >> a[i];
        sum+=a[i];
    }
    cout << sum-n << "\n";
}

Measured memory_bytes: 256
let kInf = 1 lsl 60
let n, k = Scanf.scanf " %d %d" @@ fun a b -> a, b
let hs = Array.init n @@ fun _ -> Scanf.scanf " %d" @@ (+) 0
let dp = Array.make n kInf
let _ =
  dp.(0) <- 0;
  for i = 1 to n - 1 do
    for j = 1 to k do
      if i >= j then dp.(i) <- min dp.(i) @@ dp.(i - j) + abs (hs.(i) - hs.(i - j)) done done;
  Printf.printf "%d\n" dp.(n - 1)

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

#define int long long
#define inf 1000000007LL

#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = (n) - 1LL; i >= 0; i--)
#define trep(i, n) for(int i = 0; i <= (n); i++)
#define rep1(i, n) for(int i = 1LL; i <= (n); i++)
#define mfor(i, s, t) for(int i = (s); i < (t); i++)
#define tfor(i, s, t) for(int i = (s); i <= (t); i++)
/*
class Dinic {
public:
  vector<vector<pair<int, int>>> v;
  vector<int> e;

  vector<int> k;
  vector<int> j;

  void init(int n) {
    v = vector<vector<pair<int, int>>>(n);
    e = vector<int>();
    k = vector<int>(n);
    j = vector<int>(n);
  }
  void add_edge(int a, int b, int atob, int btoa = 0) {
    v[a].push_back(make_pair(b, e.size()));
    e.push_back(atob);
    v[b].push_back(make_pair(a, e.size()));
    e.push_back(btoa);
  }
  void dyk(int s) {
    for(auto& i : k) {
      i = inf;
    }
    queue<pair<int, int>> pq;
    pq.push(make_pair(0, s));
    while(!pq.empty()) {
      int w = pq.front().first;
      int b = pq.front().second;
      pq.pop();
      if(k[b] > w) {
        k[b] = w;
        for(auto i : v[b]) {
          if(e[i.second] > 0) {
            pq.push(make_pair(w + 1LL, i.first));
          }
        }
      }
    }
  }
  int dfs(int s, int t, int p, int c) {
    if(p == t) {
      return c;
    }
    int all = 0;
    while(c > all && j[p] < v[p].size()) {
      if(k[v[p][j[p]].first] == k[p] + 1LL) {
        int r = dfs(s, t, v[p][j[p]].first, min(c - all, e[v[p][j[p]].second]));
        e[v[p][j[p]].second] -= r;
        e[v[p][j[p]].second ^ 1LL] += r;
        if(r < c - all) {
          j[p]++;
        }
        all += r;
      }
      else {
        j[p]++;
      }
    }
    return all;
  }
  int solve(int s, int t) {
    int all = 0;
    while(1LL) {
      dyk(s);
      for(auto& i : j) {
        i = 0;
      }
      int r = dfs(s, t, s, inf);
      if(r == 0) {
        return all;
      }
      all += r;
    }
  }
};
*/

map<pair<pair<int, int>, pair<int, bool>>, int> mp;

int solve(int d, int s, int b, bool fir) {
  if(mp.find(make_pair(make_pair(d, s), make_pair(b, fir))) == mp.end()) {
    int ret;
    if(s < b) {
      int w = b - s;
      if(d > w * 11 || d < w * -11) {
        ret = 0;
      }
      else {
        ret = 0;
        if(fir) {
          tfor(i, 1, 9) {
            tfor(j, 0, 9) {
              ret += solve(d - w * (j - i), s * 10, b / 10, false);
            }
          }
        }
        else {
          tfor(i, 0, 9) {
            tfor(j, 0, 9) {
              ret += solve(d - w * (j - i), s * 10, b / 10, false);
            }
          }
        }
      }
    }
    else {
      if(d == 0) {
        ret = 1;
      }
      else {
        ret = 0;
      }
      if(s == b) {
        ret *= 10;
      }
    }
    mp[make_pair(make_pair(d, s), make_pair(b, fir))] = ret;
  }
  return mp[make_pair(make_pair(d, s), make_pair(b, fir))];
}

signed main() {
  int d;
  cin >> d;
  int all = 0;
  int now = 1;
  tfor(i, 1, 20) {
    now *= 10;
    all += solve(d, 1, now, true);
  }
  cout << all << endl;
}


Measured memory_bytes: 896
#include "iostream"
#include "algorithm"
#include "string"
#include "vector"
#include "cmath"
#include "limits.h"
#include "bitset"
#define lp(n) for (int i = 0; i < n; i++)
#define lop(n,i) for (int i = 0; i < n; i++)
#define mod 1000000007
#define ll long long int
#define sp ' '
using namespace std;

int n, x, a[100000];
ll cnt;

int main(){
	cin >> n >> x;
	lp(n)
		cin >> a[i];
	cnt = 0;
	if (a[0] > x) {
		cnt += a[0] - x;
		a[0] = x;
	}
	lp(n - 1) {
		if (a[i] + a[i + 1] > x) {
			cnt += a[i] + a[i + 1] - x;
			a[i + 1] = x - a[i];
		}
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef vector<ll> vl;
typedef vector<vl> vv;
#define pb push_back
#define MOD 1000000007
#define INF 1000000000
#define endl '\n'
void fast() { ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); }

int main(){
    
    fast();
   // #ifndef ONLINE_JUDGE
	//freopen("F:\\Codes\\input.txt", "r", stdin);
	//freopen("F:\\Codes\\output.txt", "w", stdout);
	//#endif
	
	ll n,i;
	cin>>n;

	vl hgt(n),dp(n);

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

	dp[1]=abs(hgt[1]-hgt[0]);

	for(i=2;i<n;i++){
		dp[i]=min((dp[i-1]+abs(hgt[i]-hgt[i-1])),(dp[i-2]+abs(hgt[i]-hgt[i-2])));
	}
	cout<<dp[n-1]<<endl;

    
	return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cstring>
#include<algorithm>
#define db double
using namespace std;
int n; db ans;
int main()
{
  scanf("%d",&n);
  for(int i=1;i<=n;i++)
  {
    db x;scanf("%lf",&x);
    char ch[10];scanf("%s",ch);
    if(ch[0]=='J')ans+=x;
    else ans+=x*380000;
  }
  printf("%.5f\n",ans);
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
// Hey! 僕の提出を見てくれてありがとう.
// ロボ子さん可愛いぞ！！！！！君もV沼にはまろう↓
// https://www.youtube.com/channel/UCDqI2jOz0weumE8s7paEk6g
using namespace std;
/*
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
namespace mp = boost::multiprecision;// 任意長整数型
using bint = mp::cpp_int;// 仮数部長が32の浮動小数点数型
using real32 = mp::number<mp::cpp_dec_float<32>>;// 仮数部長が1024の浮動小数点数型
using real1024 = mp::number<mp::cpp_dec_float<1024>>;// ついでに有理数型
using rat = boost::rational<bint>;
*/
using ll = long long;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}//a,bの最大公約数(gcd)を求める
ll lcm(ll a,ll b){return abs(a*b)/gcd(a,b);}//a,bの最小公倍数(lcm)を求める
vector<ll> enum_div(ll n){vector<ll> ret;for(int i=1 ; i*i<=n ; i++){if(n%i == 0){ret.push_back(i);if(i!=1 && i*i!=n)ret.push_back(n/i);}}ret.push_back(n);return ret;}
//↑nの約数を求める
vector<bool> IsPrime; void sieve(size_t max){if(max+1 > IsPrime.size())IsPrime.resize(max+1,true);IsPrime[0] = false;IsPrime[1] = false;for(size_t i=2; i*i<=max; ++i)if(IsPrime[i])for(size_t j=2; i*j<=max; ++j)IsPrime[i*j] = false;}
//↑エラトステネスの篩で素数を求める
#define roundup(divisor,dividend) (divisor + (dividend - 1)) / dividend //切り上げ割り算
#define all(x) (x).begin(),(x).end() //xの初めから終わりまでのポインタ
#define size_t ll //size_tは自動でllに変換される
#define pb(x) push_back(x)
#define pri_queue priority_queue //優先度付きキュー
#define syo(x) fixed << setprecision(x) //iostreamで小数をx桁表示
//sortを降順にする時は greater<型>()
vector<ll>x;
int main(){ //srand((unsigned)time(NULL));
  for (int i = 0; i < 3; i++) {
    ll n;
    cin >> n;
    x.pb(n);
  }sort(all(x));
  for (int i = 0; i < x.size(); i++) {
    cout << x[i] << (i == x.size()-1 ? "":" ");
  }cout << endl;
}



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

int main() {
  int N;
  cin >> N;
  int t = 0, x = 0, y = 0;
  bool can = true;
  for (int i = 0; i < N; i++) {
    int t_next, x_next, y_next;
    cin >> t_next >> x_next >> y_next;
    if ((t_next - t) < (abs(x - x_next) + abs(y - y_next))) can = false;
    if (((t_next - t) - (abs(x - x_next) + abs(y - y_next))) % 2 != 0) can = false;
    t = t_next;
    x = x_next;
    y = y_next;
  }
  if (can) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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

int main(){
int N, X; cin >> N >> X;
vector<int> L(N);
vector<int> D(N + 1);
D[0] = 0;
for (int i = 0; i < N; i++){
    cin >> L[i];
    D[i + 1] = D[i] + L[i];
    }

int ans = 0;
for (int i = 0; i < N + 1; i++){
    if (D[i] <= X) {
        ans++;
    }
}
cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    long long int a, b, c;
    cin >> a >> b;

    long long int ans = a * b;

    if (a < b) {
        long long int t = a;
        a = b;
        b = t;
    }
    long long int r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }

    ans /= b;
    cout << ans;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include<functional>
#include <tuple>
#include <map>
#include<set>
#include <cmath>
#include <stack>
#include<cstdio>
#include<stdio.h>
using namespace std;

int main() {
	int n, m, c, ans=0;
	cin >> n >> m >> c;
	int a, b[100];
	for (int i = 0; i < m;i++)cin >> b[i];
	for (int i = 0;i < n;i++) {
		int cnt = 0;
		for (int j = 0; j < m;j++) {
			cin >> a;
			cnt += a * b[j];
		}
		if (cnt + c > 0)ans += 1;
	}
	cout << ans << endl;
}

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

ll mod=1e9+7 ;
ll dp[200010];
int chnum[200010];
int main(){
	int n;cin>>n;
	dp[0]=1;
	for(int i=0;i++<n;){
		int C; cin>>C;
		dp[i]=dp[i-1]+(chnum[C]!=0&&chnum[C]<i-1?dp[chnum[C]]:0);
		dp[i]%=mod;
		chnum[C]=i;
	}
	cout<<dp[n]<<endl;
}

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

typedef pair<int, int> II;
typedef vector< II > VII;
typedef vector<int> VI;

#define endl "\n"
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(a) (int)(a.size())
#define ll long long
#define fr(i,n) for(i=0;i<n;i++)

int a[110];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int i,n,cnt;
    cin>>n;
    fr(i,n)
        cin>>a[i];
    sort(a,a+n);
    cnt=1;
    for(i=1;i<n;i++)
        if(a[i]!=a[i-1])
            cnt++;
    cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 256
n,a,b= map(int,input().split())
sh = sorted([int(input()) for i in range(n)],reverse=True)
sumh = sum(sh)
def nibu(t):
    rt=0
    for i in range(n):
        temp = -1*(-1*max(0,sh[i]-t*b)//(a-b))
        if temp>0:rt+=temp
        else:break
        if rt>t:return False
    return True if t>=rt else False
l=max(sh)//a
r=max(sh)//b+1
while r-l!=1:
    m = (l+r)//2
    if nibu(m):r=m
    else:l=m
print(r)


Measured memory_bytes: 8280
N, M = map(int, input().split())

R = [0]*M

for i in range(N):
  K, *A = map(int, input().split())
  for k in range(K):
    R[A[k]-1] += 1

res = 0
for i in range(M):
  if R[i] == N:
    res += 1
    
print(res)


Measured memory_bytes: 3060
/*
Author: Fuadul Hasan(fuadul202@gmail.com)
BSMRSTU,Gopalganj
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
//#include<bits/stdc++.h>
using namespace std;
 
int         cinn()              {int x; scanf("%d", &x); return x;}
long long   scll()              {long long x; scanf("%lld", &x); return x;}
double      scd()               {double x; scanf("%lf", &x); return x;}
void        coutt(int x)        {printf("%d ", x);}
 
#define  scll                   scll()
#define  gcd(a,b)               __gcd(a,b)
#define  lcm(a,b)               (a*b)/gcd(a,b)
#define  PI                     acos(-1.0)
#define  vi                     std::vector<int>
#define  vll                    std::vector<ll>
#define  vit                    vector<int> :: iterator
#define  sit                    set<int> :: iterator
#define  mpsi                   std::map<string, int>
#define  pb                     push_back
#define  ll                     long long int
#define  ld                     long double
#define  ull                    unsigned long long int
#define  min3(a,b,c)            min(a,min(b,c))
#define  min4(a,b,c,d)          min(d,min(a,min(b,c)))
#define  max3(a,b,c)            max(a,max(b,c))
#define  max4(a,b,c,d)          max(d,max(a,max(b,c)))
#define  nl                     printf("\n");
#define  no                     printf("No");
#define  yes                    printf("Yes");
#define  F                      first
#define  S                      second
 
const int mod           = 1e9 + 7;
const int inf           = (int)2e9 + 5;
const ll  Inf           = (ll)1e18 + 5;
const int N             = 1e6 + 5;
const int nn           = 2e5 + 5;



int solve()
{
    int a,b;
    cin>>a>>b;
    if(a<b){
    	cout<<1<<endl;
    	return 0;
    }
    else{
    	int x;
    	if(a%b){
    		cout<<(a/b)+1<<endl;
    	}
    	else{
    		cout<<a/b<<endl;
    	}
    	return 0;
    }
}


int main()
{
    int test = 1, tc = 0;
    //scanf("%d", &test);
   // (void)getchar();
    //cin >> test;
    while (test--) {
        //printf("Case %d: ", ++tc);
        solve();
    }
 
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <iomanip>

using namespace std;
using ll=long long int;

template <typename T>
T powi(T a, ll n) {
    T ret = 1;
    while (n > 0) {
        if (n & 1) ret *= a; 
        a *= a;
        n >>= 1;
    }
    return ret;
}

template <ll mod>
class ModInt {
private:
    ll num;
public:
    ModInt() {};
    ModInt(ll n) { num = n % mod; }
    ModInt inv() const { return powi(*this, mod-2); }
    explicit operator ll() const { return num; }

    ModInt& operator+=(const ModInt& a) {
        num += a.num; 
        if (num >= mod) num -= mod; 
        return *this;
    }
    ModInt& operator-=(const ModInt& a) {
        if (num < a.num) num += mod;
        num -= a.num;
        return *this;
    }
    ModInt& operator*=(const ModInt& a) {
        num = num * a.num % mod;
        return *this;
    }
    ModInt& operator/=(const ModInt& a) { return *this *= a.inv(); }
    friend ModInt operator+(const ModInt& a, const ModInt& b) { return ModInt(a) += b; }
    friend ModInt operator-(const ModInt& a, const ModInt& b) { return ModInt(a) -= b; }
    friend ModInt operator*(const ModInt& a, const ModInt& b) { return ModInt(a) *= b; }
    friend ModInt operator/(const ModInt& a, const ModInt& b) { return ModInt(a) /= b; }

    friend ostream& operator<<(ostream& os, const ModInt& a) { return os << a.num; }
    friend istream& operator>>(istream& is, ModInt& a) {
        ll tmp;
        is >> tmp;
        a.num = tmp % mod;
        return is;
    }
};
using mint = ModInt<1000000007>;

mint dp[110][200010];

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

    int p;
    for (p = 1; p*p <= n; ++p) {} 
    --p;
    int m = p*2;
    vector<int> a(m+1);
    a[0] = 0;
    for (int i = 1; i <= p; ++i) {
        a[i] = i;
        a[m-i+1] = n/i;
    }
    
    for (int i = 0; i < m; ++i) {
        dp[0][i] = 1;
    }

    for (int i = 0; i < k; ++i) {
        fill(dp[i+1], dp[i+1]+m+1, 0);
        for (int j = 0; j < m; ++j) {
            mint t = dp[i][j] * (a[j+1] - a[j]);
            dp[i+1][0] += t;
            dp[i+1][m-j] -= t;
        }
        mint acc = 0;
        for (int j = 0; j < m; ++j) {
            acc += dp[i+1][j];
            dp[i+1][j] = acc;
        }
    }

    mint ans = 0;
    for (int i = 0; i < m; ++i) {
        ans += dp[k-1][i] * (a[i+1] - a[i]);
    }

    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 157056
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}
int dx[4]={0,1,-1,0};
int dy[4]={1,0,0,-1};


const int MAX = 510000;
const int mod = 1000000007;

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

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

// 二項係数計算
ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    int n;
    cin>>n;
    COMinit();
    ll ans = 0;
    ll k = n / 3;
    ll rem = n % 3;
    for(int i=k;i>=1;i--){
        ans += COM(i-1+rem,rem);
        ans %= mod;
        rem += 3;
    }
    cout << ans << endl;

}

Measured memory_bytes: 15600
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        List<Integer> dList = new ArrayList<>();
        int answer = 0;
        while (true) {
            try {
                final String line = bufferedReader.readLine();
                if (line == null || line.length() == 0) {
                    break;
                }
                dList.add(Integer.parseInt(line));
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        int n = dList.get(0);
        dList.remove(0);
        dList.sort(Collections.reverseOrder());

        int old = 101;// di <= 100
        for (Integer d : dList) {
            if (d < old) {
                old = d;
                answer++;
            }
        }
        System.out.println(answer);
    }
}

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

int main(int argc, char const *argv[])
{
	string s;
	cin>>s;
	if (s=="Sunny")
	{
		cout<<"Cloudy\n";
	}
	else if (s=="Cloudy")
	{
		cout<<"Rainy";	
	}
	else
	{
		cout<<"Sunny\n";
	}
	return 0;
}



Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include<stdio.h>
int main() {
	int n, i;
	char str[1001], *pt;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		getchar();
		scanf("%[^\n]*s", str);
		pt = str;
		while(*pt){
			if (*pt == 'H')
				if (*(pt + 1) == 'o'&&*(pt + 2) == 's'&&*(pt + 3) == 'h'&&*(pt + 4) == 'i'&&*(pt + 5) == 'n'&&*(pt + 6) == 'o')
					*(pt + 6) = 'a';
			printf("%c", pt[0]);
			pt++;
		}
		putchar('\n');
	}
	return 0;
}

Measured memory_bytes: 572
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
int a[N];
int main() {
	int n;
	scanf("%d\n",&n);
	for (int i=0;i<2*n;i++) scanf("%d",a+i);
	sort(a,a+2*n);
	int ans = 0;
	for (int i=0;i<n;i++) ans += a[2*i];
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
string S;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

int main(){
    cin>>N>>S;
    rep(i,S.size()){
        ll c = S[i] + N;
        if(c >= 91) c -= 26;
        cout<<char(c);
    }
    cout<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pint = pair<int,int>;
ll mod = 1000000007,mod2 = 998244353;

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

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; }
const long long INF = 1LL<<60;
ll gcd(ll a,ll b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}

const int MAX = 510000;
const int MOD = 1000000007;

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

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

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int a[100][2];

int main() {
    string s;
    cin >> s;
    if(s[s.size()-1] == 's'){
        cout << s+"es" << endl;
    }else{
        cout << s+ "s" << endl;
    }
    return 0;
}

Measured memory_bytes: 3624
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <map>

//#include <bits/stdc++.h>
using namespace std;
#define print(x) cout<<(x)<<endl
#define prints(x, y) cout<<(x)<<" "<<(y)<<endl
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define r_rep(i, n) for(int i = (int)n-1; i >= 0; i--)
#define ll long long int
#define pb push_back
const long long MOD = 1000000007;
const long long INF = 1LL << 60;

int main() {
  int n, M, k;
  cin >> n >> M;
  vector<vector<int> > denkyu(M);
  vector<int> p(M);

  rep(i, M){
    cin >> k;
    vector<int> s(k);
    rep(j, k){
      cin >> s[j];
      s[j]--;
    }
    denkyu[i] = s;
  }
  rep(i, M){
    cin >> p[i];
  }

  int ans = 0, cnt;
  vector<vector<int> > candidate;
  // {0, 1, ..., n-1} の部分集合の全探索
  for (int bit = 0; bit < (1<<n); ++bit)
  {
      // bit の表す集合を求める
      vector<int> S;
      for (int i = 0; i < n; ++i) {
          if (bit & (1<<i)) { // i が bit に入るかどうか
              S.push_back(i);
          }
      }

      // bit の表す集合の出力
      vector<int> c;
      rep(i, M){ // 配列を見ていく
        cnt = 0;
        rep(j, denkyu[i].size()){  
          for (int k = 0; k < (int)S.size(); ++k) {
            if(denkyu[i][j] == S[k]) {
              cnt++;
              break;
            }
          }
        }
        c.push_back(cnt%2);
      }
      candidate.push_back(c);
  }

  rep(i, candidate.size()){
    // rep(j, candidate[i].size()){
    //   cout << candidate[i][j] << " ";
    // }
    // cout << endl;
    if(p == candidate[i]) ans++;
  }
  print(ans);
}


Measured memory_bytes: 384
N=int(input())
a=input().split()
numbers=[int(b) for b in a]
kazu=0
suuji=0
for z in numbers:
    if z%2==0:
        kazu+=1
for y in numbers:
    if y%4==0:
        suuji+=1
kazu-=suuji
if kazu==N:
    print('Yes')
elif suuji>=N//2:
    print('Yes')
elif kazu>=N-suuji*2:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 14252
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF=1LL<<60;
const int inf=1<<30;
const int mod=1e9+7;
const int MOD=998244353;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,t,s;cin >> n >> t >> s;
    vector<int> a(n),b(n);
    for(int i=0;i<n;i++){
        cin >> a[i] >> b[i];
    }
    vector<vector<int>> dp(t+1,vector<int>(2,-1));
    dp[0][0]=0;
    vector<vector<int>> p(t+1,vector<int>(2,-1));
    p[0][0]=0;
    if(s==0){
        dp[0][1]=0;
        p[0][1]=0;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<=t;j++){
            for(int k=0;k<2;k++){
                if(dp[j][k]==-1){
                    continue;
                }
                chmax(p[j][k],dp[j][k]);
                if(j<=s&&k==0){
                    chmax(p[s][1],dp[j][0]);
                }
                if(j+b[i]<=t){
                    if(j+b[i]<=s&&k==0){
                        chmax(p[s][1],dp[j][0]+a[i]);
                    }
                    chmax(p[j+b[i]][k],dp[j][k]+a[i]);
                }
            }
        }
        for(int j=0;j<=t;j++){
            for(int k=0;k<2;k++){
                chmax(dp[j][k],p[j][k]);
                p[j][k]=-1;
            }
        }
    }
    int ans=0;
    for(int i=0;i<=t;i++){
        chmax(ans,dp[i][1]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 3420
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

ll f(ll x){
  ll cnt=0;
  while(x!=0){
    cnt++;
    x /=10;
  }
  return cnt;
}

int main() {
  ll n,m;
  cin >> n >> m;
  vector<tuple<ll,ll,ll>> t(m);
  rep(i,m){
    ll x,y;
    cin >> x >> y;
    t[i]=make_tuple(x,y,i);
  }
  sort(t.begin(),t.end());
  ll cnt=1;
  vector<tuple<ll,ll,ll>> a(m),b(m);
  ll z;
  rep(i,m){
    if(i==0){
      z=cnt;
    }
    if(i>=1){
      if(get<0>(t[i])==get<0>(t[i-1])){
        cnt++;
        z=cnt;
      }
      else{
        cnt=1;
        z=cnt;
      }
    }
    a[i]=make_tuple(get<0>(t[i]),z,get<2>(t[i]));
  }
  rep(i,m){
    b[i]=make_tuple(get<2>(a[i]),get<0>(a[i]),get<1>(a[i]));
  }
  sort(b.begin(),b.end());
  rep(i,m){
    ll A=get<1>(b[i]),B=get<2>(b[i]);
    ll s=f(A),t=f(B);
    string s1="",s2="";
    rep(i,6-s){
      s1+="0";
    }
    rep(i,6-t){
      s2+="0";
    }
    cout << s1 << A << s2 << B << endl;
  }
}

Measured memory_bytes: 9472
from fractions import gcd
from functools import reduce


def main():
    balls, target = map(int, input().split())
    numbers = [int(x) for x in input().split()]
    numbers.sort()
    numbers_gcd = reduce(gcd, numbers)
    print("POSSIBLE" if target % numbers_gcd == 0 and target <= numbers[-1] else "IMPOSSIBLE")


if __name__ == '__main__':
    main()



Measured memory_bytes: 16280
H,W,D = map(int, input().split())
grid_dict = {}
for i in range(H):
    for j,s in enumerate(input().split()):
        grid_dict[int(s)] = [i,j]

Q = int(input())
exam = []
for i in range(Q):
    exam.append(list(map(int, input().split())))

man = lambda x,y: abs(x[0]-y[0])+abs(x[1]-y[1])

power = [[0] for i in range(D)]
power[0].append(0)
for i in range(1,H*W+1):
    if i + D not in grid_dict:
        break
    power[i%D].append(power[i%D][-1] + man(grid_dict[i], grid_dict[i+D]))
# [print(i) for i in power]

for l,r in exam:
    if r == l:
        print(0)
        continue
    print(power[r%D][r//D]-power[r%D][l//D])


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

int main() {
  int64_t n;
  cin >> n;
  vector<string> a(n);
  rep(i,n){
    cin >> a[i];
  }
  sort(a.begin(),a.end());
  
  int64_t count=1;
  int64_t MAX=1;
  rep2(i,1,n){
    if(a[i]==a[i-1]){
      count++;
      MAX=max(MAX,count);
    }
    else count=1;
  }
  
  count=1;
  rep(i,n-1){
    if(a[i]==a[i+1]){
      count++;
      if(count==MAX) cout << a[i] << endl;
    }
    else count=1;
    if(MAX==1) cout << a[i] << endl;
  }
  if(MAX==1) cout << a[n-1] << endl;
}

Measured memory_bytes: 14336
#include<stdio.h>

int array[1000000];
int main(){
	int n;
	int i;
	int j;
	int result;
	while(scanf("%d",&n)!=EOF){
		result = 0;
		for(i=1;i<n+1;i++){
			array[i] = 1;
		}
		for(i=2;i<n+1;i++){
			if(array[i]){
				result += 1;
				for(j=2;j<n/i+1;j++){
					array[i*j] = 0;
				}
			}
		}
		printf("%d\n",result);
	}
	return 0;
}

Measured memory_bytes: 4308
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<vector>
#include<cstdio>

using namespace std;

int main()
{
	int N, M, X, input, c1 = 0, c2 = 0;
	vector<int> a;
	cin >> N >> M >> X;
	for (int i = 0; i < M; i++) {
		cin >> input;
		a.push_back(input);
	}

	for (int i = 0; i < M; i++) {
		if (a[i] < X) {
			c1++;
		}
		else {
			c2++;
		}
	}

	cout << min(c1, c2);

	char qq;
	cin >> qq;
	return 0;
}

Measured memory_bytes: 256
hoge=input()
n=len(hoge)
if(hoge!=hoge[::-1]):
  print("No")
  exit()
aaa=hoge[1+n//2:]
bbb=hoge[:n//2]
ccc=aaa[::-1]
ddd=bbb[::-1]
if(aaa==ccc and bbb==ddd):
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3060
fn main() {
    let mut nmst = String::new();
    std::io::stdin().read_line(&mut nmst).unwrap();
    let nmst: Vec<usize> = nmst.split_whitespace().map(|x|x.parse().unwrap()).collect();
    let n = nmst[0];
    let m = nmst[1];
    let s = nmst[2]-1;
    let t = nmst[3]-1;
    let mut g: Vec<Vec<(usize,usize,usize)>> = vec![vec![];n];
    for _ in 0..m {
        let mut uvab = String::new();
        std::io::stdin().read_line(&mut uvab).unwrap();
        let uvab: Vec<usize> = uvab.split_whitespace().map(|x|x.parse().unwrap()).collect();
        let u = uvab[0]-1;
        let v = uvab[1]-1;
        let a = uvab[2];
        let b = uvab[3];
        g[u].push((v,a,b));
        g[v].push((u,a,b));
    }
    let f = 1e15 as usize;
    let mut e = vec![f;n];
    let mut q = std::collections::BinaryHeap::new();
    q.push((f,n,t));
    while let Some((y,c,v)) = q.pop() {
        if e[v]<=f-y {continue;}
        e[v]=f-y;
        for &(u,_,b) in &g[v] { if e[u]>=f-(y-b) {
            q.push((y-b,c,u));
        }}
    }
    let mut d = vec![0;n];
    q.push((f,n,s));
    let mut r = vec![]; r.reserve(n);
    while let Some((y,c,v)) = q.pop() {
        if c==n {
            if d[v]>=y {continue;}
            d[v]=y;
            if r.len()<=v {
                q.push((y-e[v],v,t));
            }
            for &(u,a,_) in &g[v] { if d[u]<y-a {
                q.push((y-a,c,u));
            }}
        }
        else {
            if r.len()<=c {
                r.resize(c+1,y);
            }
        }
    }
    for y in r {
        println!("{}",y);
    }
}

Measured memory_bytes: 25568
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void)
{
  int x,n,tmp;
  int p[102]={0};

  scanf("%d %d",&x,&n);
  for(int i=0;i<n;i++)
  {
    scanf("%d",&tmp);
    p[tmp]=1;
  }

  for(int i=0;i<51;i++)
  {
    if(p[x-i]==0)
    {
      printf("%d\n",x-i);
      break;
    }
    if(p[x+i]==0)
    {
      printf("%d\n",x+i);
      break;
    }
  }

  return 0;
}

Measured memory_bytes: 1684
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)

total = 0
for i in range(n):
    total += a[i]
min = total / (4 * m)

bool = True
for i in range(m):
    if a[i] >= min:
        continue
    else:
        bool = False

if bool == True:
    print('Yes')
else:
    print('No')

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

int get(vector<int> a, int valor){
    if (a.back() <= valor) return 0;
    int l=0, r=a.size()-1, resp = 0;
    while(l <= r){
        int m = (l+r)>>1;
        if (a[m] > valor){
            resp = m;
            r = m-1;
        } else l = m+1;
    }
    return a.size() - resp;
}

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

    int n, arr[2002];
    vector<int> qtd[2002];
    cin >> n;
    for (int i=1; i<=n; i++) cin >> arr[i];
    sort(arr+1, arr+n+1);

    long long resp = 0;
    for (int i=2; i<=n; i++){
        for (int j=1; j<i; j++){
            qtd[i].push_back(arr[i] + arr[j]);
        }
    }

    for (int i=3; i<=n; i++){
        for(int j=2; j<i; j++){
            resp += get(qtd[j], arr[i]);
        }
    }
    cout << resp << endl;
}

Measured memory_bytes: 10880
x = int(input())
expotential = [0] * (x + 1)
expotential[1] = 1
for b in range(2, x+1):
	t = b * b
	while(t <= x):
		expotential[t] = 1
		t *= b
for i in range(x, 0, -1):
	if expotential[i]:
		print(i)
		break

Measured memory_bytes: 9096
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll a, b, c, a1, b1, c1, ans;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> a >> b >> c;
	while(a%2==0 && b%2==0 && c%2==0){
		if(a == b && b == c){
			cout << -1;
			return 0;
		}
		ans++;
		a1 = (b+c)/2;
		b1 = (a+c)/2;
		c1 = (a+b)/2;
		a = a1;
		b = b1;
		c = c1;
	}
	cout << ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const ll INF = 1001001001;
const ll LINF = 1001001001001001001;

void prvec(vector<ll> vec){
    ll n = vec.size();
    rep(i,n) cout << i << " " << vec.at(i) << "\n";
}

void pr2d(vector<vector<ll>> vvec){
    ll h = vvec.size();
    ll w = vvec.at(0).size();
    rep(i,h){
        rep(j,w){
            cout << vvec.at(i).at(j) << " ";
        }
        cout << "\n";
    }
}

long long modpow(long long a,long long n, long long mod){
    long long res = 1;
    while(n>0){
        if ( n & 1 ) res = (res * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return res;
}

int main(){
    ll n ; cin >> n;
    ll ans = modpow(10,n,mod);
    ll x = (modpow(9,n,mod)+modpow(9,n,mod))%mod;
    ans = (ans - x)%mod;
    if(ans<0) ans+=mod;
	ans = (ans + modpow(8,n,mod))%mod;
    cout << ans << endl;
}

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

public class Main{
	public static class FastReader {
		BufferedReader br;
		StringTokenizer root;
		
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (root == null || !root.hasMoreTokens()) {
				try {
					root = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return root.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	static long mod = (long) (1e9+7);
	static long cf = 998244353;
    static final int MAX = 100000;
   // public static List<Integer>[] edges;
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		int n = sc.nextInt();
		char[] s = sc.next().toCharArray();
		int ans = 0;
		for(int i=0;i<n;++i) {
			int j = i;
			while(j+1 < n && s[j] == s[j+1]) ++j;
			i = j;
			++ans;
		}
		out.print(ans);
	    out.close();
	}
	
}

Measured memory_bytes: 23636
#include <iostream>
#include <utility>

int selectionSort(int A[], int N){
	int ans = 0;
	for(int i = 0; i < N; i++){
		int minj = i;
		for(int j = i; j < N; j++){
			if(A[j] < A[minj]){
				minj = j;
			}
		}
		if(minj != i){
			std::swap(A[minj], A[i]);
			ans++;
		}
	}
	for(int i = 0; i < N; i++){
		if(i) std::cout << " ";
		std::cout << A[i];
	}
	std::cout << std::endl;
	return ans;
}

int main(){
	int N;
	std::cin >> N;
	int A[N];
	for(int i = 0; i < N; i++){
		std::cin >> A[i];
	}
	int ans = selectionSort(A, N);
	std::cout << ans << std::endl;
	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
constexpr long long INFL = 1LL << 60;
constexpr int INF = 1e9;

using namespace std;

int main()
{
    int a,b;
    cin >> a >> b;
    if(a > b)
        cout << a - 1 << endl;
    else
        cout << a << endl;
    return 0;
}



Measured memory_bytes: 256
=begin
－－－－－－－－－－－－－－
a, b, c = A, B, AB ピザ値段
X, Y = A, B ピザ必要枚数
dob = A+B と C*2 で安い方の値段を代入
ans = 最小合計
－－－－－－－－－－－－－－
1: dob = A+B と C*2 の安い方(Aピザ1枚 + Bピザ1枚 を作るのに安い組み合わせを探す)
2: X < Y なら
  2.1: ans += dob * X
  2.2: ans += Y - X * (B と C*2 の安い方)
3: X > Y なら
  3.1: ans += dob * Y
  3.2: ans += X - Y * (A と C*2 の安い方)
* X == Y の場合は 何もしない
4: ansを出力
=end

a, b, c, x, y = gets.split.map(&:to_i)
ans = 0
dob = [(a+b), (c*2)].min

if x < y
  min = [b, (c*2)].min
  ans += x * dob
  ans += (y-x) * min
elsif x > y
  min = [a, (c*2)].min
  ans += y * dob
  ans += (x-y) * min
else
  ans += x * dob
end

puts ans

Measured memory_bytes: 1788
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    k, t = input_int_list()
    A = input_int_list()
    _max = max(A)
    ans = (_max - (k - _max)) - 1
    if ans < 0:
        ans = 0
    print(ans)
    return


if __name__ == "__main__":
    main()


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

ll dp[100000+10];
ll h[100000+10],n,k;



int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>h[i];
    dp[1]=0;
    for(int i=2;i<=n;i++)
    {
    	dp[i]=dp[i-1]+abs(h[i]-h[i-1]);
    	for(int j=2;j<=k;j++)
    	{
    		
    	if(i-j>=1)
    	dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
    	
		}
    
	}
    cout<<dp[n];
    
	return 0;
}

Measured memory_bytes: 1792
# A - Biscuits
import numpy as np

N, P = map(int, input().split())
A = list(map(int, input().split()))
odd = len([i for i in A if i%2!=0])
if odd==0 and P==0:
    ans = 2**N
elif odd==0 and P==1:
    ans = 0
else:
    ans = 2**(N-1)
print(ans)

Measured memory_bytes: 21048
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
struct edge
{
    int u,v,w;
};
vector <edge> ans;

int n,L;

int main()
{
    //freopen("file.inp","r",stdin);
    cin >> L;
    if (L == 2)
    {
        cout << "2 2" << endl;
        cout << "1 2 0" << endl;
        cout << "1 2 1" << endl;
        return 0;
    }
    L--;
    int d = 1;
    while (4 * d <= L)
    {
        d <<= 1;
    }
    for (int i = 1; i <= 19; i++)
    {
        ans.push_back({i, i + 1, d});
        ans.push_back({i, i + 1, 0});
        d >>= 1;
        n = i + 1;
        if (d == 0) break;
    }
    d = 1;
    while (2 * d <= L)
    {
        d <<= 1;
    }
    for (int i = 1 ; n - i - 1 >= 0; i++)
    {
        if (((L >> (n - i - 1)) & 1) == 1)
        {
            ans.push_back({1, i + 1, d});
            d += 1 << (n - i - 1);
        }
    }
    ans.push_back({1, n, L});
    cout << n << " " << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i].u << " " << ans[i].v << " " << ans[i].w << endl;
    }
    return 0;
}


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

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define LL long long
#define SZ(X) X.size()
#define pii pair<int,int>
#define ALL(X) X.begin(),X.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 2e5 + 11;
int main() {
	ios::sync_with_stdio(false);
	int a,b;
	cin>>a>>b;
	if(a%b==0){
		cout<<a/b<<endl;
	}else{
		cout<<a/b+1<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define mod 924844033
#define N 4004
#define ll long long

using namespace std;

int n, k, cnt;
ll f[N][N][2], ans, fac[N], a[N];

void init();

int main(){
	cin >> n >> k;init();
	for(int i = 1; i <= k; ++i){
		for(int j = i; j <= n; j += k) a[++cnt] = j;
		for(int j = i; j <= n; j += k) a[++cnt] = j;
	}
	f[1][0][0] = 1;
	for(int i = 2; i <= (n << 1); ++i)
		for(int j = 0; j <= min(n, i / 2); ++j){
			f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1]) % mod;
			if(j > 0 && a[i] - a[i - 1] == k) f[i][j][1] = f[i - 1][j - 1][0];
		}
	for(int i = 0; i <= n; ++i){
		ll sum = (f[n << 1][i][0] + f[n << 1][i][1]) % mod;
		(ans += (sum * fac[n - i] % mod * ((i & 1) ? -1 : 1) + mod) % mod) %= mod;
	}
	cout << ans << endl;
	return 0;
}

void init(){
	fac[0] = 1;
	for(int i = 1; i <= 2000; ++i)
		fac[i] = fac[i - 1] * i % mod;
	return ;
}

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

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using iii = tuple<int, int, int>;

const int MAX { 30 };
const int oo { 1000000007 };

int found[MAX][MAX];
const vector<ii> dirs { ii(1, 0), ii(-1, 0), ii(0, 1), ii(0, -1) };

int maxdist(int x, int y, int H, int W, const vector<string>& xs)
{
    for (int i = 0; i < H; ++i)
        for (int j = 0; j < W; ++j)
            found[i][j] = false;

    queue<iii> q;
    int ans = 0;

    q.push(iii(x, y, 0));
    found[x][y] = true;

    while (not q.empty())
    {
        auto f = q.front();
        auto i = get<0>(f);
        auto j = get<1>(f);
        auto d = get<2>(f);

        q.pop();

        ans = max(ans, d);

        for (auto dir : dirs)
        {
            auto u = i + dir.first, v = j + dir.second;

            if (u >= 0 and u < H and v >= 0 and v < W and not found[u][v] and xs[u][v] == '.')
            {
                q.push(iii(u, v, d + 1));
                found[u][v] = true;
            }
        }
    }

    return ans;
}

int solve(int H, int W, const vector<string>& xs)
{
    int ans = 0;

    for (int i = 0; i < H; ++i)
        for (int j = 0; j < W; ++j)
            if (xs[i][j] == '.')
                ans = max(ans, maxdist(i, j, H, W, xs));

    return ans;
}

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

    int H, W;
    cin >> H >> W;

    vector<string> xs(H);

    for (int i = 0; i < H; ++i)
        cin >> xs[i];

    auto ans = solve(H, W, xs);

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 256