akhauriyash/Code-Regression huggingface dataset:
#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;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    for (int i = 0; i < n-1; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> c(n);
    for (auto &e: c) cin >> e;
    sort(c.begin(), c.end());

    vector<int> deg(n);
    for (int i = 0; i < n; ++i) {
        deg[i] = g[i].size();
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> que;
    for (int i = 0; i < n; ++i) {
        que.emplace(deg[i], i);
    }

    int m = 0;
    int cnt = 0;
    vector<int> d(n, 0);
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        if (p.first > deg[p.second]) continue;
        m += p.first * c[cnt];
        d[p.second] = c[cnt];
        ++cnt;
        for (auto &v: g[p.second]) {
            if (d[v] > 0) continue;
            --deg[v];
            que.emplace(deg[v], v);
        }
    }

    cout << m << endl;
    for (auto &e: d) cout << e << " ";
    cout << endl;

    return 0;
}


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

int main()
{
    ios::sync_with_stdio(false);
    int k;
    cin >> k;
    if (k % 2 == 0)
    {
        cout << (k / 2) * (k / 2) << endl;
    }
    else
    {
        cout << (((k - 1) / 2) * ((k + 1) / 2)) << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


const int N = 100010;


int a[N];


int main()
{
	int n;
	
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	
	for (int i = n-1; i >= 1; i--)
	{
		if (a[i] > a[i+1]) a[i]--;
		if (a[i] > a[i+1]) { puts("No"); return 0; }
	}
	
	puts("Yes");
	
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
int main(){
	int N, M;
	vector<string> regi;
	cin >> N;
	for( int i = 0; i < N; i++ ){
		string ID;
		cin >> ID;
		regi.push_back(ID);
	}
	cin >> M;
	int rock = 0;
	for( int i = 0; i < M; i++ ){
		string ID;
		cin >> ID;
		size_t j = 0;
		for( ; j < regi.size(); j++ ){
			if( ID == regi[j] ){
				if( rock == 0 ){
					cout << "Opened by " << regi[j] << endl;
					rock = 1;
				}else{
					cout << "Closed by " << regi[j] << endl;
					rock = 0;
				}
				break;
			}
		}
		if( j == regi.size() ) cout << "Unknown " << ID << endl;
	}
}

Measured memory_bytes: 1220
#include<iostream>
#include<vector>
#include<map>
#include<sstream>
#include<algorithm>
using namespace std;

typedef pair<int,string> P;
bool compare(P a, P b){
  if(a.first==b.first)return a.second<b.second;
  return a.first>b.first;
}

int main()
{
  int n;
  string line;
  char k;
  while(cin>>n,n){
      getline(cin,line);
    map<string,int>word;
    vector<P>ans;
    for(int i=0;i<n;i++){
      getline(cin,line);
      stringstream ss(line);
      string w;
      while(ss>>w)word[w]++;;
    }
    cin>>k;
      getline(cin,line);
    for(map<string,int>::iterator it=word.begin();it!=word.end();it++)if(it->first[0]==k)ans.push_back(P(it->second,it->first));
    sort(ans.begin(),ans.end(),compare);
    int cnt=0;
    for(int i=0;i<ans.size()&&i<5;i++){
      if(i)cout<<" ";
      cout<<ans[i].second;
      cnt++;
    }
    if(!cnt)cout<<"NA";
    cout<<endl;
  }
}

Measured memory_bytes: 948
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PI;
typedef vector<PI> vec;
const LL N=150000;
LL n;
LL du[N];
struct qq
{
	LL x,y,z;
	LL last;
}e[N];LL num,last[N];
void init (LL x,LL y,LL z)
{
	num++;
	e[num].x=x;e[num].y=y;e[num].z=z;
	e[num].last=last[x];
	last[x]=num;
}
vector<PI> t[N];
bool cmpy (PI x,PI y){return x.second<y.second;}
bool cmpx (PI x,PI y){return x.first<y.first;}
LL mn[N];
LL mid;
void Merge (vec &s1,vec &s2,vec &f)
{
	if (s1.size()>s2.size()) swap(s1,s2);
	LL tot=s1.size(),tot1=s2.size();
	if (tot==0||tot1==0) return ;
	
	sort(s1.begin(),s1.end(),cmpy);
	sort(s2.begin(),s2.end(),cmpx);
	
	mn[0]=s2[0].second;
	for (LL u=1;u<tot1;u++)	mn[u]=min(mn[u-1],s2[u].second);
	LL j=tot1-1;
	for (LL i=0;i<tot;i++)
	{
		while (j>=0&&s1[i].second+s2[j].first>mid) j--;
		if (j>=0) f.push_back(PI(s1[i].first,mn[j]));
	}
	
	sort(s1.begin(),s1.end(),cmpx);
	sort(s2.begin(),s2.end(),cmpy);
	
	mn[0]=s2[0].first;
	for (LL u=1;u<tot1;u++)	mn[u]=min(mn[u-1],s2[u].first);
	j=tot1-1;
	for (LL i=0;i<tot;i++)
	{
		while (j>=0&&s1[i].first+s2[j].second>mid) j--;
		if (j>=0) f.push_back(PI(mn[j],s1[i].second));
	}
}
void dfs (LL x)
{
	t[x].clear();
	if (du[x]==1)	{t[x].push_back(PI(0,0));return ;}
	//printf("%lld\n",x);
	LL s1=-1,s2=-1;
	LL z1,z2;
	for (LL u=last[x];u!=-1;u=e[u].last)	
	{
		dfs(e[u].y);
		if (s1==-1) {s1=e[u].y;z1=e[u].z;}
		else {s2=e[u].y;z2=e[u].z;}
	}
	vec &ls=t[s1],&rs=t[s2];
	LL tot=ls.size();
	for (LL u=0;u<tot;u++)	ls[u].first+=z1,ls[u].second+=z1;
	tot=rs.size();
	for (LL u=0;u<tot;u++)	rs[u].first+=z2,rs[u].second+=z2;
	Merge(ls,rs,t[x]);
	ls.clear();rs.clear();
}
bool check ()//这个答案行不行 
{
	//printf("%lld\n",mid);
	//for (LL u=1;u<=n;u++) t[u].clear();
	dfs(1);
	//printf("YES:%lld %lld\n",mid,t[1].size());
	if (t[1].size()!=0) return true;
	return false;
}
int main()
{
	num=0;memset(last,-1,sizeof(last));
	scanf("%lld",&n);
	LL l=0,r=0;
	for (LL u=2;u<=n;u++)
	{
		LL x,z;
		scanf("%lld%lld",&x,&z);
		du[u]++;du[x]++;
		r=r+z;init(x,u,z);
	}
	LL ans;
	while (l<=r)
	{
		mid=(l+r)>>1;
	//	printf("%lld %lld %lld\n",l,r,mid);
		if (check()) {r=mid-1;ans=mid;}
		else l=mid+1;
	}
	printf("%lld\n",ans);
	return 0;
}

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

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

const ll INF = 1LL << 60;
const int MOD = 1000000007;

bool dp[110000];

int main() {
#ifdef MYLOCAL
    ifstream in("input.txt");
    cin.rdbuf(in.rdbuf());
#endif

    int n, k; cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i){
        cin >> a[i];
    }

    for (int i = 1; i <= k; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i - a[j] >= 0) {
                dp[i] |= !dp[i - a[j]];
            }
        }
    }

    if (dp[k]){
        cout << "First" << endl;
    }
    else{
        cout << "Second" << endl;
    }
}



Measured memory_bytes: 384
from itertools import combinations_with_replacement

N, M, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(Q)]

ans = 0
for x in combinations_with_replacement(range(1, M + 1), N):
    tmp = 0
    for i in range(Q):
        if x[X[i][1] - 1] - x[X[i][0] - 1] == X[i][2]:
            tmp += X[i][3]
    ans = max(ans, tmp)

print(ans)


Measured memory_bytes: 67824
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <numeric>
#include <fstream>
#include <iomanip>

typedef long double ld;
typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

// Split
namespace util {

std::vector< std::string > split(std::string s, char delimiter)
{
  std::vector< std::string > vs;
  std::string sub;
  for (auto c : s) {
    if (c == delimiter) vs.push_back(sub), sub.clear();
    else sub += c;
  }
  vs.push_back(sub);
  return vs;
}

} // namespace util

// Minimum, Maximum
template<class T> T minimum(T head, T tail) { return std::min(head, tail); }
template<class H, class... T> H minimum(H head, T... tail) { return std::min(head, minimum(tail...)); }
template<class T> T maximum(T head, T tail) { return std::max(head, tail); }
template<class H, class... T> H maximum(H head, T... tail) { return std::max(head, maximum(tail...)); }

// Output
template<class T, class S> std::ostream& operator << (std::ostream& os, std::pair<T, S> p)
{
  return os << p.first << " " << p.second;
}

template<class T> std::ostream& operator << (std::ostream& os, std::vector< T > v)
{
  for (ll i = 0; i < (ll)v.size(); i++){ os << " [" << i << "]" << v[i]; if (i % 10 == 9) os << std::endl; }
  return os;
}

template<class T, class S> std::ostream& operator << (std::ostream& os, std::vector< std::pair<T, S> > vp)
{
  ll i = 0;
  for (auto p : vp){os << " [" << i++ << "]" << p.first << " " << p.second; if (i % 10 == 0) os << std::endl;}
  return os;
}

void print(){ std::cout << std::endl; }
template<typename H> void print(H head) { std::cout << head << std::endl; }
template<typename H, typename... T> void print(H head, T... tail){ std::cout << head << " ", print(tail...); }

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

  ll R, G, B, N;
  std::cin >> R >> G >> B >> N;

  ll ans = 0LL;
  for (ll r = 0; r <= N; r++) {
    for (ll g = 0; g <= N; g++) {
      if ((N - R * r - G * g) % B == 0 &&
	  (N - R * r - G * g) / B >= 0) {
	ans++;
	//print(r, g, (N - R * r - G * g) / B);
      }
    }
  }

  print(ans);
  return 0;
}


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

const int MAX = 301;
const long long INF = 1e18-1;
 
 
int main() {
    long long N, K; cin >> N >> K;
    long long H[MAX];
    for (int i = 0; i < N; i++) cin >> H[i];

    long long dp[MAX][MAX];

    for (int i = 0; i < MAX; i++) for (int j = 1; j < MAX; j++) dp[i][j] = INF;

    for (int i = 0; i < N; i++) dp[i][1] = H[i];

    for (int i = 1; i < N; i++) for (int k = 2; k < N - K + 1; k++) for (int l = 0; l < i; l++) {
        dp[i][k] = min(dp[i][k], dp[l][k-1]+max(0ll, H[i]-H[l]));
    }

    long long ans = INF;
    for (int i = 0; i < N; i++) ans = min(ans, dp[i][N - K]);

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

Measured memory_bytes: 896
a=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
b = int(input())
print(a[b-1])

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s="CODEFESTIVAL2016";
	string c;cin>>c;
	int cnt=0;
	for(int i=0;i<=15;i++)
	if(c[i]!=s[i])cnt++;
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 256
/*  よろしくお願いします
    LEARNING DP:    Longest Path
        + SIMPLE GRAPH
        + DIRECTED EDGES
        + NO CYCLE
    CONSTRAINT:
        +2 <= N <= 1e5
        +1 <= M <= 1e5
    QUESTION:
        + can we START at RANDOM Vertex
        + what should we memorize after done a DFS or BFS
    IF WE KNOW:
        A PATH that already done by using DFS
        we can just add it to the current one.
    PRE DP:
        ALL PATH equal 0
    TIME COMPLEXITY:
        O(|S|*|T|)
*/
#include <bits/stdc++.h>
using namespace std;

#define DB(_x)      cout << #_x << " is " << (_x) << "\n";
#define FOR(_a,_b)  for (_a = 0; _a < _b; ++_a)
#define fs          first
#define sc          second
#define pb          push_back
//#define IOFILE

using LL = long long;
using LD = long double;
using VI = vector<int>;
using PI = pair<int,int>;

int DFS(VI &dp, vector<VI> &a, int u){
    if (dp[u]) return dp[u];
    int res = 0;
    for (auto v: a[u]){
        if(dp[v]){
            res = max(res, dp[v]);
        } else {
            res = max(res,DFS(dp,a,v));
        }
    }
    return dp[u] = res + 1;
}

void Excalibur(){
    int i=0, j=0, n ,m, ans;

    while (cin >> n >> m){

        vector<VI> a(n);
        FOR(i, m){
            int x, y; cin >> x >> y; --x; --y; a[x].pb(y);
        }

        VI dp(n,0);
        ans = 0;
        FOR(i, n){
            ans = max(ans,DFS(dp, a, i));
//            DB(dp[i]);
        }
        cout << ans - 1 << "\n";
    }
}

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

#ifdef  IOFILE
    freopen("INPUT.in", "r", stdin);
    freopen("OUTPUT.out", "w", stdout);
#endif

Excalibur();
return 0;}


Measured memory_bytes: 9600
def main():

    S = input()
    count = dict()
    for c in S:
        count[c] = count.get(c, 0) + 1

    if len(count) == 1:
        if len(S) == 1:
            return "YES"
        return "NO"
    elif len(count) == 2:
        a, b = list(count.keys())
        if count[a] == 1 and count[b] == 1:
            return "YES"
        return "NO"
    else:
        lv = sorted(count.values())
        if lv[0] == lv[1] == lv[2]:
            return "YES"
        if (lv[2] == lv[1] and lv[1] == lv[0]+1):
            return "YES"
        if (lv[0] == lv[1] and lv[2] == lv[1]+1):
            return "YES"
        return "NO"

if __name__ == '__main__':
    print(main())

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

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> h(n);
	rep(i, n) cin >> h[i];
	sort(all(h));
	int ans = 1001001001;
	rep(i, n-k+1) ans = min(ans, h[i+k-1]-h[i]);
	cout << ans << endl;
	return 0;
}

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

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> B(N);
    for(int i = 0; i < N; i++){
        cin >> A[i];
        B[i] = A[i];
    }
    sort(B.begin(), B.end());
    reverse(B.begin(), B.end());
    
    for(int i = 0; i < N; i++){
        if(A[i] == B[0])cout << B[1] << endl;
        else cout << B[0] << endl;
    }
    return 0;
}

Measured memory_bytes: 3200
import bisect
def main():
    n = int(input())
    A=[int(i) for i in input().split()]
    B=[int(i) for i in input().split()]
    C=[int(i) for i in input().split()]

    A.sort()
    B.sort()
    C.sort()

    #B[i]の上に何種類乗るか調べる
    #res[i]:B[i]の上に乗るAの数
    res = [0]*(n)
    j = 0
    res2=[0]*(n)
    for i in range(n):
        res[i]=bisect.bisect_left(A, B[i])
        res2[i]=n-bisect.bisect_right(C, B[i])

    ans = 0

    for i in range(n):
        ans+=(res[i]*res2[i])
    return ans
if __name__ == '__main__':
    print(main())


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

static const int MAX = 100000;
vector<int> par(MAX);
vector<int> r(MAX);

void init(int n) {
    for (int i=0;i<n;i++) {
        par[i] = i;
        r[i] = 0;
    }
}

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

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

void unite(int x,int y) {
    x = root(x);
    y = root(y);
    if (x == y) return;
    
    if (r[x] < r[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if (r[x] == r[y]) r[x]++;
    }
}

int main() {
    int N,M;
    cin >> N >> M;
    vector<int> P(N+1);
    for (int i=1;i<N+1;i++) cin >> P[i];
    int a,b;
    init(N+1);
    for (int i=0;i<M;i++) {
        cin >> a >> b;
        unite(a,b);
    }
    int cnt = 0;
    for (int i=1;i<N+1;i++) {
        if (same(i,P[i])) cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 4268
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)

const int MOD = 1000000007;

const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

int main()
{
    int n;
    cin >> n;
    vector<int> p(n);
    REP(i, n)
    cin >> p.at(i);

    int ans = 0;
    for (int i = 1; i < n - 1; i++) {
        if (p.at(i) > p.at(i - 1) && p.at(i) < p.at(i + 1)) {
            ans++;
        } else if (p.at(i) < p.at(i - 1) && p.at(i) > p.at(i + 1)) {
            ans++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main() {
	int i,j,emp,n,m,x,y,xs[101],ms[101];
	scanf("%d%d%d%d",  &n,&m,&x,&y);
	for (i = 0; i < n; i++)scanf("%d", &xs[i]);
	for (i = 0; i < m; i++)scanf("%d", &ms[i]);

	for (i = 0; i < n; i++) {
		for (j = n - 1; j > i; j--) {
			if (xs[j - 1] < xs[j]) {
				emp = xs[j - 1];
				xs[j - 1] = xs[j];
				xs[j] = emp;
			}
			
		}
	}
	for (i= 0; i < m; i++) {
		for (j = m- 1; j > i; j--) {
			if (ms[j - 1] > ms[j]) {
				emp = ms[j - 1];
				ms[j - 1] = ms[j];
				ms[j] = emp;
			}

		}
	}
	if (y - x - 1 < 0 || ms[0] - xs[0]-1 < 0) { printf("War"); }
	else if (xs[0] <= x + 1 && ms[0] <= x + 1) {
		printf("War");
	}
	else if (xs[0] >= y && ms[0] >= y) {
		printf("War");
	}
	else {
		printf("No War");
	}
	
		return 0;
	
}

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

using namespace std;

int main()
{
    int s;
    cin >> s;
    if (s == 25)
    {
        cout << "Christmas" << endl;
    }
    else if (s == 24)
    {
        cout << "Christmas Eve" << endl;
    }
    else if (s == 23)
    {
        cout << "Christmas Eve Eve" << endl;
    }
    else if (s == 22)
    {
        cout << "Christmas Eve Eve Eve" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
N = gets
points = [1, 1]
while line = gets
  ratios = line.split.map(&:to_i)
  times = points.zip(ratios).map { |a, b| Rational(a, b).ceil }.max
  points = ratios.map {|i| i * times }
end
p (points[0] + points[1]).to_i

Measured memory_bytes: 1916
#include<stdio.h>
#include<stdlib.h>

#define MAX 100001
#define INFTY 10000000

typedef struct{
  int prev;
  int next;
  int cost;
} Edge;

Edge G[500000];
int d[MAX];

void Dijkstra(int,int);

int main(void){
  int i, j, k, n, v, u, c;
  int count=0;

  scanf("%d", &n);
  //G = (int*)malloc(sizeof(int)*n);

  /*for(i=0; i<n; i++){
    for(j=0; j<n; j++){
      G[i][j] = INFTY;
    }
    }*/

  for(i=0; i<n; i++){
    scanf("%d%d", &u, &k);
    for(j=0; j<k; j++){
      G[count].prev = u;
      scanf("%d%d", &G[count].next, &G[count].cost);
      count++;
    }
  }

  Dijkstra(n,count);

  //free(G);

  return 0;
}

void Dijkstra(int n, int count){
  int i, min = 1;
  int d[MAX];

  d[0] = 0;
  for(i=1; i<n; i++){
    d[i] = INFTY;
  }

  while(min != 0){
    min = 0;

    /*for(i=0; i<n; i++){
      if(c[i] != 1 && d[i] < min){
        j = i;
        min = d[i];
      }
      }*/

    //if(min == INFTY) break;

    for(i=0; i<count; i++){
      if(d[G[i].prev] + G[i].cost < d[G[i].next]){
        d[G[i].next] = d[G[i].prev] + G[i].cost;
        min = 1;
      }
    }
  }

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

  return;
}

Measured memory_bytes: 6464
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int x,n;
  cin>>x>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
  }
  sort(a,a+n);
  int min=999,ans,j=0;
  if(n==0)
    ans=x;
  for(int i=0;i<=a[n-1]+1&&n>0;i++)
  {
    if(i==a[j]&&j<n)
    {j++;
      continue;
    }
    else
    {
      if(min>abs(x-i))
      {
        min=abs(x-i);
        ans=i;
      }
    }
  }
  cout<<ans;
}

    
  


Measured memory_bytes: 3640
def submit():
    h, w = map(int, input().split())

    if h == 1 or w == 1:
        print(1)
        return
    
    even_c = sum(divmod(w, 2))
    odd_c = w // 2
    even_row = sum(divmod(h, 2)) * even_c
    odd_row = (h // 2) * odd_c

    print(even_row + odd_row)


if __name__ == "__main__":
    submit()

    

Measured memory_bytes: 3060
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<cmath>
#include<limits>
#define ll long long
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define int_INF 2147483647
#define pint_INF 2000000000
#define ll_INF 	9223372036854775807
#define MOD 1000000007
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define vvc vector<vector<char>>
#define vll vector<long long>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define sysp system("PAUSE")
#define pno cout << "no" << endl
#define pyes cout << "yes" << endl
#define pYes cout << "Yes" << endl
#define pNo cout << "No" << endl
using namespace std;
bool validate(vi vec, int flag_even) {
	if (flag_even) {
		for (auto e : vec) {
			if (e != 2) {
				return false;
			}
		}
	}
	else {
		for (int i = 0; i < vec.size(); i++) {
			if (vec[0] != 1) {
				return false;
			}
			if (i != 0 && vec[i] != 2) {
				return false;
			}
		}
	}

	return true;
}

ll mpow(ll x, ll n) { //x^n(mod M) ←普通にpow(x,n)では溢れてしまうため，随時mod計算
	ll ans = 1;
	while (n != 0) {
		if (n & 1) ans = ans * x % MOD;
		x = x * x % MOD;
		n = n >> 1;
	}
	return ans;
}

int main() {
	int N; cin >> N;
	vi vec(N); rep(i, N) cin >> vec[i];
	ll ans = 1;

	if (N % 2 == 0) {
		vi check(N / 2);
		for (auto e : vec) {
			check[(e-1)/2]++;
		}

		if (validate(check, 1)) {
			ans = mpow(2, N/2);
		}
		else {
			ans = 0;
		}
	}
	else {
		vi check((N+1) / 2);
		for (auto e : vec) {
			check[e/2]++;
		}
		if (validate(check, 0)) {
			ans = mpow(2, (N - 1) / 2);
		}
		else {
			ans = 0;
		}

	}

	cout << ans << endl;
}

Measured memory_bytes: 4012
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<55)+1e9; // ~ 3.6 * 1e16
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
using T = tuple<Int,Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> &a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
template<class T>void prArr(T a,string s=" "){Int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}


signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  Int n;
  cin>>n;
  vector<string> A(n);
  cin>>A;
  vector<Int> dp(30, INF);
  dp[A[0][0] - 'a'] = 1;

  for(Int i=1;i<n;i++){
    dp[ A[i][0] - 'a' ] = min(dp[ A[i][0]-'a' ], dp[ A[i-1][0]-'a' ] + 1);
  }

  Int ans = dp[ A[n-1][0]-'a' ];
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 8440
# coding: utf-8
# Your code here!
n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

tmp=99
ans=0

for i in range(n):
    ans+=B[A[i]-1]
    if tmp+1==A[i]:
        ans+=C[tmp-1]
    tmp=A[i]
    
print(ans)

Measured memory_bytes: 3064
#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 speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long 
#define ull unsigned long long
#define db double
#define vi vector<ll>
#define vvi vector<vector<int> >
#define vvii vector<vector<pii> >
#define rep(i,a,b) for(int i=a;i<b;i++)
#define endl "\n"
#define pii pair<ll,ll>
#define piii pair<ll,pair<ll,ll> >
#define mem(a,b) memset(a , b , sizeof a ) ; 
#define pb push_back
#define pf push_front
#define F first 
#define S second 
#define mp make_pair
#define all(v) v.begin(),v.end()

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}



#define deb1(a) cout<<#a<<"=*"<<a<<endl;
#define deb2(a) cout<<#a<<"=@"<<a<<endl;
#define deb3(a) cout<<#a<<"=#"<<a<<endl;
#define deb4(a,b) cout<<#a<<"="<<a<<" and "<<#b<<"="<<b<<endl;
#define deb5(a,b) cout<<#a<<"="<<a<<" and "<<#b<<"="<<b<<endl;


typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


ll mod=1000000007;
ll vis[212345]={0};
vvi v(212345);
ll d[212345]={0};


ll pow(ll a, ll b, ll m)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
			ans=(ans*a)%m;
		b/=2;
		a=(a*a)%m;
	}
	return ans;
}


ll f[1000009];


int main()
{
speed
ll c=1;
ll k;
cin>>k;
ll lr=7%k;
if(lr==0)
{
	cout<<"1\n";
	return 0;
}
lr=(lr*10+7)%k;
c++;
ll ff=0;
while(!f[lr])
{
	if(lr==0)
	{
		ff=1;
		break;
	}
	f[lr]=1;
	lr=(lr*10+7)%k;
	c++;
}

if(ff) cout<<c<<endl;
else cout<<"-1\n";

}



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

int main(){
    int N; cin >> N;
    vector<int> a(N); for(int i = 0; i < N; ++i) cin >> a[i];

    int cnt = 0;
    while(true) {
        int ret = 0;
        for(int i = 0; i < N; ++i) {
            if(a[i] % 2 == 1) {
                ret++;
            } else {
                a[i] = a[i] / 2;
                cnt++;
                break;
            }
        }

        if(ret == N) {
            break;
        }
    }

    cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
signed main()
{
    int n;
    cin >> n;
    vector<int> l(n);
    rep(i, n) cin >> l[i];
    
    int maxL = 0;
    rep(i, n) maxL = max(maxL, l[i]);
    int sum = 0;
    rep(i, n) sum += l[i];
    yorn (maxL < sum - maxL) {

    }

    return 0;
}

Measured memory_bytes: 3612
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
	int64_t x;
	cin >> x;

	int64_t res = x / 11;
	x -= res * 11;
	res *= 2;
	if (x > 0)
		res += x < 7 ? 1 : 2;
	cout << res << endl;

	return 0;
}

Measured memory_bytes: 256
n = int(input())
nn = n+4
anslist = [0]*nn

big = 0

def goukei(x,y,z):
  h =x**2 + y**2 + z**2 + x*y + y*z + z*x
  return h

for x in range(1,101):
  for y in range(1,x+1):
    for z in range(1,y+1):
      temp = goukei(x,y,z)
      if temp < n+2:
        if x == y == z:
          anslist[temp] += 1
          break
        if x == y or y == z:
          anslist[temp] += 3
        else:
          anslist[temp] += 6

for i in range(1,n+1):
  print(anslist[i])

Measured memory_bytes: 9156
N = int(input())

def cal(n):
    cnt = 0
    while n % 2 == 0:
        n = n//2
        cnt += 1
    return cnt

ans = -1
for i in range(N,0,-1):
    if ans < cal(i):
        ans = cal(i)
        ans_n = i
print(ans_n)

Measured memory_bytes: 3060
from math import ceil

N = int(input())
T, A = 1, 1
for t, a in [map(int, input().split()) for _ in range(N)]:
    n = int(max(T // t + (0 if T%t==0 else 1), A//a + (0 if A%a==0 else 1) ))
    T, A = n * t, n * a
print(T + A)


Measured memory_bytes: 3444
import scala.io.StdIn.readInt
  
object Main extends App {
  val (x,minv) = (readInt, readInt)

  val m = (1 until x).foldLeft((minv,Int.MinValue)) { (x, _) =>
      val r = readInt
      (r.min(x._1), (r-x._1).max(x._2))
    }._2
  println(m)

}


Measured memory_bytes: 72972
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main()
{

    string s;
    cin >> s;

    int best_count = s.size();

    for (char ch = 'a'; ch <= 'z'; ch++)
    {
        string t = s + ch;
        int max_count = 0;
        int count = 0;
        for (auto c : t)
        {
            if (c == ch)
            {
                max_count = max<>(max_count, count);
                count = 0;
            }
            else
            {
                count++;
            }
        }
        best_count = min(best_count, max_count);
    }
    cout << best_count << endl;
}


Measured memory_bytes: 256
/*input
10 10
3 1 4 1 5 9 2 6 5 3
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

#define rep(i,j,n) for(i=j;i<n;i++)
#define repi(i,j,n) for(i=j;i>n;i--)
#define inf 100001
#define M 998244353
#define pie 3.141592653589793238
#define ll long long
#define ld long double
#define vll vector<long long>
#define vi vector<int>
#define pll pair<long long,long long>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define vpll vector<pair<long long,long long> >
#define pb push_back
#define pf pop_front
#define F first
#define S second
#define endl '\n'

using namespace std;
using namespace __gnu_pbds; 

template<typename T>
using ordered_set=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


ll power(ll a,ll m,ll mod){
	ll ans=1;
	while(m){
		if(m%2){
			ans*=a;
			ans%=(mod);
		}
		a=(a*a)%(mod);
		m>>=1;
	}
	return ans;
}


void init(ll* a,ll n,ll val){
	for(ll i=0;i<n;i++)
		a[i]=val;
}

void solve(){
	ll i,j,k;
	ll n,s;
	cin>>n>>s;
	ll a[n];
	rep(i,0,n)cin>>a[i];
	ll dp[2][s+1];
	memset(dp,0,sizeof(dp));
	if(a[0]<=s)dp[0][a[0]]=1;
	dp[0][0]=2;
	//rep(j,0,s+1)cout<<dp[0][j]<<" ";cout<<endl;
	rep(i,1,n){
		rep(j,0,s+1){
			dp[i%2][j]+=(dp[(i+1)%2][j]*2)%M;
			dp[i%2][j]%=M;
			if(j+a[i]<=s)dp[i%2][j+a[i]]+=dp[(i+1)%2][j],dp[i%2][j+a[i]]%=M;
			dp[(i+1)%2][j]=0;
		}
		//rep(j,0,s+1)cout<<dp[i%2][j]<<" ";cout<<endl;
	}
	cout<<dp[(i+1)%2][s]<<endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);	
	ll T=1;
	//cin>>T;
	while(T--){
		solve();
	}
	return 0;
}




Measured memory_bytes: 3652
s = list(input())
t = list(input())
f = -1
for i in range(len(s)-len(t)+1):
  for j,k,l in zip(s[i:i+len(t)],t,range(len(t))):
    if j != k and j != '?':
      break
    if l == len(t) -1:
      f = i
if f != -1:
  s[f:f+len(t)] = t
  for i in range(len(s)):
    if s[i] == '?':
      s[i] = 'a'
  print(*s,sep='')
else:
  print('UNRESTORABLE')

Measured memory_bytes: 3064
use std::io::{self, BufRead};

fn main() {
  let stdin = io::stdin();
  let mut lines = stdin.lock().lines();
  let l: usize = lines.next().unwrap().unwrap().parse().unwrap();
  let mut n = 1;
  let mut temp = l;
  while temp > 1 {
    temp >>= 1;
    n += 1;
  }
  let mut beg: usize = usize::pow(2, n - 1);
  let mut ns: Vec<(usize, usize)> = Vec::new();
  for i in 0..(n-1) {
    let k = (n - i - 2) as usize;
    if l & (1 << k) != 0 {
      ns.push(((i + 2) as usize, beg));
      beg += usize::pow(2, k as u32);
    }
  }
  let m = (2 * (n - 1) as usize) + ns.len();
  println!("{} {}", n, m);
  for i in 0..(n-1) {
    println!("{} {} {}", i + 1, i + 2, 0);
    println!("{} {} {}", i + 1, i + 2, u32::pow(2, n - i - 2));
  }
  for (x, y) in ns {
    println!("{} {} {}", 1, x, y);
  }
}

Measured memory_bytes: 4352
#include <iostream>
#include <iomanip>
#include <bits/stdc++.h>
#include <vector>
#include <iterator>
#include <string>
#define pan(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define vi vector<int>
#define pb push_back
using namespace std;



int main(){
    int n;
    cin>>n;
    ll h[n];
    vector <ll> v;
    pan(i,n) cin>>h[i];
    ll count=0;
    for(int i=0;i<n-1;i++){
        // cout<<"i"<<i<<endl;
        // cout<<"h"<<h[i]<<endl;
        if(h[i]>=h[i+1]) {
            count +=1;
            // cout<<"hi"<<h[i]<<"i"<<i<<"count"<<count<<endl;
            v.pb(count);
        }
        else {
            
            count=0;
            // cout<<"i"<<i<<endl;
        }
    }
    ll siz=v.size();
    // pan(i,siz) cout<<v[i]<<endl;
    if (siz!=0) cout<<*max_element(v.begin(),v.end());
    else cout<<0;
}


Measured memory_bytes: 2168
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

import java.util.*;

public class Main{
  static int n;
  static int[] d;

  public static void main(String[] args){
    FastScanner sc = new FastScanner();
    n = sc.nextInt();
    d = new int[n];
    for(int i = 0; i < n; i++){
      d[i] = sc.nextInt();
    }

    Set< Integer > set = new HashSet< >();
    for(int i = 0; i < n; i++){
      set.add(d[i]);
    }

    int ans = set.size();

    System.out.println(ans);
  }
}

class FastScanner {
  private static final InputStream in = System.in;
  private static final PrintWriter out = new PrintWriter(System.out);
  private final byte[] buffer = new byte[2048];
  private int p = 0;
  private int buflen = 0;

  public FastScanner(){
  }

  private boolean hasNextByte() {
    if(p < buflen){
      return true;
    }
    p = 0;
    try{
      buflen = in.read(buffer);
    }catch (IOException e) {
      e.printStackTrace();
    }
    if(buflen <= 0){
      return false;
    }
    return true;
  }

  public boolean hasNext() {
    while(hasNextByte() && !isPrint(buffer[p])){
      p++;
    }
    return hasNextByte();
  }

  private boolean isPrint(int ch) {
    if(ch >= '!' && ch <= '~'){
      return true;
    }
    return false;
  }

  private int nextByte() {
    if(!hasNextByte()){
      return -1;
    }
    return buffer[p++];
  }

  public String next() {
    if(!hasNext()){
      throw new NoSuchElementException();
    }
    StringBuilder sb = new StringBuilder();
    int b = -1;
    while(isPrint((b = nextByte()))){
      sb.appendCodePoint(b);
    }
    return sb.toString();
  }

  public int nextInt() {
    return Integer.parseInt(next());
  }

  public long nextLong() {
    return Long.parseLong(next());
  }

  public double nextDouble() {
    return Double.parseDouble(next());
  }
}


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

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tiii;

const int INF = 100000000;
const ll LINF = 1e18+5;

int main() {
    string S;
    cin >> S;
    int N = S.size() + 1;
    char before = S[0];

    int stops[500000] = {};
    if(S[0]=='<') stops[0] = 1;
    else stops[0] = -1;
    REP(i, 1, S.size()) {
        if(before == '>' && S[i] == '<') {
            stops[i] = 1;
        } else if (before == '<' && S[i] == '>') {
            stops[i] = -1;
        }
        before = S[i];
    }
    if(S[N-2] == '>') stops[N-1] = 1;
    else stops[N-1] = -1;
    ll isinc = 0;
    ll nowvalue = 0;
    ll ans = 0;
    ll sbefore = 0;
    for(ll i = 0; i < N; i++) {
        //cout << stops[i] << " " << nowvalue << endl;
        ans += nowvalue;
        if(stops[i] == 1) {
            isinc = 1;
            if(nowvalue < 0) {
                ans += nowvalue * -1 * (i - sbefore + 1);
            } else if (nowvalue > 0) {
                ans -= nowvalue * (i - sbefore);
            }
            nowvalue = 0;
        } else if (stops[i] == -1) {
            isinc = 0;
            sbefore = i;
        }
        if(isinc) nowvalue++;
        else nowvalue--;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 2820
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
    int n;
    cin >> n;
    vector<int> a(n),b(n);
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    vector<int> s(n+1),t(n+1);
    for(int i=0;i<n;i++){
    	s[a[i]]++;
		t[b[i]]++;
	}
    for(int i=0;i<=n;i++)
    if(s[i]+t[i]>n){
        cout<<"No"<<endl;
        return 0;
    }
    for(int i=0;i<n;i++){
    	s[i+1]+=s[i];
		t[i+1]+=t[i];
	}
    int x=-2e5-10;
    for(int i=0;i<n;i++)x=max(x,s[i+1]-t[i]);
    cout<<"Yes"<<endl;
    for(int i=0;i<n;i++){
    	cout<<b[(i+n-x)%n];
		if(i==n-1)cout<<endl;
		else cout<<' ';
	}
    return 0;
}

Measured memory_bytes: 6400
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, f, n) for (ll i = (f); i < (n); i++)
#define repv(v) for (auto it = (v).begin(); it != (v).end(); it++)
ll const INF = 1LL << 60;
ll const MAX_N = 100000;
ll const MOD = 1000000007;

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

    ll n = N.length();
    ll dp[n + 5][2][5];
    rep(i, n + 5) rep(j, 2) rep(k, 5) dp[i][j][k] = 0;

    vector<ll> cnt(3, 0);
    int n0 = N[0] - '0';
    if (n0 == 3 || n0 == 5 || n0 == 7) {
        dp[0][0][1] = 1;
        cnt[(n0 - 1) / 2 - 1]++;
    }

    rep(i, n0) {
        if (i == 3 || i == 5 || i == 7) {
            dp[0][1][1]++;
        }
    }

    rep(i, n - 1) {
        dp[i + 1][1][1] += dp[i][1][1] + 3;
        dp[i + 1][1][2] += 2 * dp[i][1][1];
        dp[i + 1][1][2] += 2 * dp[i][1][2];
        dp[i + 1][1][3] += dp[i][1][2];
        dp[i + 1][1][3] += 3 * dp[i][1][3];

        int ni = N[i + 1] - '0';
        if (ni == 3 || ni == 5 || ni == 7) {
            cnt[(ni - 1) / 2 - 1]++;
            ll idx = 0;
            rep(j, 3) {
                if (cnt[j] != 0) idx++;
            }
            if (idx != 0) dp[i + 1][0][idx] = 1;
        }

        rep(j, ni) {
            if (j == 3 || j == 5 || j == 7) {
                if (cnt[(j - 1) / 2 - 1] == 0) {
                    dp[i + 1][1][2] += dp[i][0][1];
                    dp[i + 1][1][3] += dp[i][0][2];
                } else {
                    dp[i + 1][1][1] += dp[i][0][1];
                    dp[i + 1][1][2] += dp[i][0][2];
                    dp[i + 1][1][3] += dp[i][0][3];
                }
            }
        }
    }

    // rep(i, n) {
    //     rep(j, 2) {
    //         reps(k, 1, 4) { cout << dp[i][j][k] << " "; }
    //     }
    //     cout << endl;
    // }

    cout << dp[n - 1][0][3] + dp[n - 1][1][3] << endl;

    return 0;
}


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

int main()
{
  int q,n,i,j,max,can;

  cin>>q;
  for(i=0;i<q;i++){
    cin>>n;
    j=0;
    for(;n>9;){
      max=0;
      for(int d=10;n%d!=n;){
	can=(n%d)*(int)((n-(n%d))/d);
	if(can>max) max=can;
	d*=10;
      }
      j++; n=max;
    }
    cout<<j<<endl;
  }
}


Measured memory_bytes: 1160
#include<iostream>
#include<string>
#include <algorithm>
using namespace std;
int q;
int L[1010][1010];
string s1,s2;

void solve(){
    for(int i=0;i<=s1.size();i++)
        for(int j=0;j<=s2.size();j++){
            if(i<=0||j<=0) L[i][j]=0;
            else if(s1[i-1]==s2[j-1]) L[i][j]=1+L[i-1][j-1];
                else L[i][j]=max(L[i][j-1],L[i-1][j]);
        }
    cout<<L[s1.size()][s2.size()]<<endl;
}
int main(){
    cin>>q;
    for(int i=0;i<q;i++){
        cin>>s1>>s2;
        solve();
    }
    return 0;
}



Measured memory_bytes: 7184
#include <bits/stdc++.h>
#define FIXED_FLOAT(x) std::fixed <<std::setprecision(2)<<(x)
#define what_is(x) cerr << #x << " is " << x << endl;
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define inf std::numeric_limits<int>::max();
#define highest_2_pow(n)  __builtin_clzll((long long)0)- __builtin_clzll((long long)n) - 1
//-----------------------------------------------------------------------------------------------------
#define lli long long int 
#define int long long
#define all(x)            (x).begin(),(x).end()
#define uniq(v)           (v).erase(unique(all(v)),(v).end())
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define pii               pair<int,int>
#define vi vector<int>
#define vlli vector<long long int>
#define si set<int>
#define slli set<long long int>
#define mt make_tuple
#define mp make_pair
#define eb emplace_back
#define mem1(a)           memset(a,-1,sizeof(a))
#define mem0(a)           memset(a,0,sizeof(a))
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll
//---------------------------------------------------
using namespace std;
// GCD and LCM are available
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << " = " << a << endl;
err(++it, args...);
}

void faster(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}
void solve(){
    int n;
    cin>>n;
    int m=0;
    int sum=0;
    vector<int> v(n);
    rep(i,0,n){
        cin>>v[i];
        if(v[i]<0) m++;
        v[i] = abs(v[i]);
        sum+=v[i];
    }
    if(m%2){
        cout<<sum-2*(*min_element(all(v)))<<endl;
    }
    else cout<<sum<<endl;

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

Measured memory_bytes: 1024
n=int(input())
s=[]
l=[]
p=[]
for i in range(n):
    ss,ll,pp=map(int,input().split())
    s.append(ss)
    l.append(ll)
    p.append(pp)
m=int(input())
w=[int(input()) for i in range(m)]
w_=max(w)
dp=[[-1]*(w_+1) for i in range(n+1)]
for i in range(n):
    for j in range(s[i],min(l[i]+1,w_+1)):
        dp[i+1][j]=p[i]
for i in range(n):
    for j in range(w_+1):
        if j<s[i]:
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        elif j>=s[i]:
            if dp[i+1][j-s[i]]==-1:
                dp[i+1][j]=max(dp[i][j],dp[i+1][j])
            else:
                dp[i+1][j]=max(dp[i][j],dp[i+1][j],dp[i+1][j-s[i]]+p[i])
ans=[]
for i in range(m):
    ans.append(dp[n][w[i]])
if ans.count(-1)>=1:
    print(-1)
else:
    for a in ans:
        print(a)
    


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

int main() {
    ll l, r; cin >> l >> r;

    if (l / 2019 != r / 2019) {
        cout << 0 << endl;
        return 0;
    } else {
        ll res = 2020;
        for (ll i = l; i <= r; ++i) {
            for (ll j = i + 1; j <= r; ++j) {
                res = min(res, i * j % 2019);
            }
        }
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 256
local ior = io.read
local n = ior("*n")
local a = {}
for i = 1, n do a[i] = io.read("*n") end

local function getgcd(x, y)
  while(0 < x and 0 < y) do
    if(x < y) then y = y % x else x = x % y end
  end
  return math.max(x, y)
end

local mac = math.ceil
local mam = math.max

local mesh = 60

local groups = mac(n / mesh)
local groupgcd = {}
local group_inv_gcd = {}
for i = 1, groups do
  groupgcd[i] = 0
  group_inv_gcd[i] = 0
end

for i = 1, n do
  local g = mac(i / mesh)
  groupgcd[g] = getgcd(groupgcd[g], a[i])
end

for i = 1, groups do
  for j = 1, groups do
    if(i ~= j) then
      group_inv_gcd[i] = getgcd(group_inv_gcd[i], groupgcd[j])
    end
  end
end

local ret = 0

for i = 1, n do
  local g = mac(i / mesh)
  local stt = 1 + (g - 1) * mesh
  local last = (g == groups and n or g * mesh)
  local cand = group_inv_gcd[g]
  for j = stt, last do
    if(j ~= i) then
      cand = getgcd(cand, a[j])
    end
  end
  ret = mam(ret, cand)
end
print(ret)


Measured memory_bytes: 1280
#include <stdio.h>
#define H 500000

int parent( int );
int left( int );
int right( int );
void maxHeapify( int [], int );
void buildMaxHeap( int [] );
int n;

int main(){
    int A[H+1], i; //the reason I choose H+1 is o-origin

    //input
    scanf("%d", &n);
    for(i = 1; i<=n; i++) scanf("%d", &A[i]);
    //sort
    buildMaxHeap( A );
    //print
    for(i = 1; i<=n; i++) printf(" %d", A[i]);
    printf("\n");
    
    return 0;
}

int parent( int i ){
    return i/2;
}

int left( int i ){
    return 2*i;
}

int right( int i ){
    return 2*i+1;
}

void maxHeapify( int A[], int i ){
    int l, r, tmp, largest; //this l means the left index, r means the right index
    l = left(i);
    r = right(i);
    //compare the values
    if(l <= n && A[l] > A[i]) largest = l;
    else largest = i;
    if(r <= n && A[r] > A[largest]) largest = r;
    //check it compared the value  
    if(largest != i){
	tmp = A[i];
	A[i] = A[largest];
	A[largest] = tmp;
	maxHeapify( A, largest );
    }
}

void buildMaxHeap( int A[] ){
    int i;
    for(i = n/2; i>=1; i--)
	maxHeapify( A, i );
}



Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define rep(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()
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
const int mod = 1e9+7;
const int INF = 1e9;
const int MAX = 1e6;

struct cusum {
    int n;
    vector<long long> s;
    cusum(vector<int> &a) {
        n = a.size();
        s.resize(n+1);
        s[0] = 0;
        for (int i = 1; i <= n; i++) {
            s[i] = s[i-1] + a[i-1];
        }
    }
    long long sum(int a, int b) { // 半開区間[a,b)の和(0-indexed)
        return s[b] - s[a];
    }
};

int main() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, n) {
        cin >> a[i];
    }
    cusum s(a);
    ll ans;
    for (int i = 0; i + 1 < n ; i++) {
        ll x = s.sum(0, i + 1); 
        ll y = s.sum(i + 1, n);
        if (i == 0) ans = abs(x - y);
        else ans = min(ans, abs(x - y));
    }
    cout << ans << endl;
}

Measured memory_bytes: 5604
import sys
import math
from collections import Counter
import itertools
#from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

# ###########################################

l=[II(),II(),II(),II(),II()]
l2=[l[i] if l[i]%10==0 else l[i]//10*10+10 for i in range(5)]
m = 0
for i in range(5):
    m=max(m,l2[i]-l[i])
print(sum(l2)-m)



Measured memory_bytes: 3316
import java.util.Scanner;

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

        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();

        System.out.println(solve(a, b, c, d) ? "Yes" : "No");

        sc.close();
    }

    static boolean solve(int a, int b, int c, int d) {
        return Math.abs(a - c) <= d || (Math.abs(a - b) <= d && Math.abs(c - b) <= d);
    }
}

Measured memory_bytes: 21844
N = int(input())

for _ in range(N):
    A = list(map(int, input().split()))
    b, c = 0, 0
    flag = True
    for a in A:
        if b < a:
            b = a
        elif c < a:
            c = a
        else:
           print('NO') 
           flag = False
           break
    if flag:
        print('YES')


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



int main(void){
	ios::sync_with_stdio(false);
	string s;
	cin>>s;
	int h=0;
	for(int i=0;i<s.size();i++){
        if(s[i]=='A'&&s[i+1]=='C'){
            cout<<"Yes\n";
            return 0;
        }
    }
    cout<<"No\n";
	return 0;
}


Measured memory_bytes: 256