akhauriyash/Code-Regression huggingface dataset:
n = int(input())
s = input()
t = input()
ans = n
for i in range(n):
    for j in range(n):
        if s[i + j] == t[j]:
            if i + j == n - 1:
                print(ans)
                exit()
        else:
            ans += 1
            break
print(2 * n)

Measured memory_bytes: 3060
#include<iostream>
#include<string>
using namespace std;
struct dice{
  int s[6];
  void roll(char c){
    int b;
    if(c=='E'){
      b=s[0];
      s[0]=s[3];
      s[3]=s[5];
      s[5]=s[2];
      s[2]=b;
    }
    if(c=='W'){
      b=s[0];
      s[0]=s[2];
      s[2]=s[5];
      s[5]=s[3];
      s[3]=b;
    }
    if(c=='N'){
      b=s[0];
      s[0]=s[1];
      s[1]=s[5];
      s[5]=s[4];
      s[4]=b;
    }
    if(c=='S'){
      b=s[0];
      s[0]=s[4];
      s[4]=s[5];
      s[5]=s[1];
      s[1]=b;
    }
    if(c=='R'){
      b=s[1];
      s[1]=s[2];
      s[2]=s[4];
      s[4]=s[3];
      s[3]=b;
    }    
  }
  int top() {
    return s[0];
  }
  int right(){
    return s[2];
  }
  int left(){
    return s[3];
  }
  int front(){
    return s[1];
  }
};
bool same(dice a,dice b){
  for(int i=0;i<6;i++) if(a.s[i]!=b.s[i]) return false;
  return true;
}
int main(){
  dice d[100];
  int n;cin >> n;
  for(int j=0;j<n;j++) 
    for(int i=0;i<6;i++)
      cin >> d[j].s[i];
  
  bool ff = true;
  for(int k=0;k<n-1;k++){
    for(int l=k+1;l<n;l++){
      bool f=false;
      for(int i=0;i<4;i++){
	d[l].roll('R');
	for(int j=0;j<4;j++){
	  d[l].roll('N');
	  if(same(d[k],d[l])) f=true;
	}
      }
      d[l].roll('E');
      for(int j=0;j<4;j++){
	d[l].roll('N');
	if(same(d[k],d[l])) f=true;
      }
      
      d[l].roll('W');
      d[l].roll('W');
      for(int j=0;j<4;j++){
	d[l].roll('N');
	if(same(d[k],d[l])) f=true;
      }
      if(f) ff=false;
    }
  }
  if(ff==true){
      cout << ("Yes") << endl;
  }
  else if(ff==false){
      cout<<("No")<<endl;
  }
  return 0;
}



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

using namespace std;

int main()
{
  string str;
  cin>>str;
  string str2;
  int chk=0;
  int n=str.size();
  
  for(int i=0;i<n/2;i++)
  {
    if(str.at(i)!=str.at(n-1-i))
      chk++;
  }
  for(int i=0;i<(n-1)/4;i++)
  {
    if(str.at(i)!=str.at((n-1)/2-1-i))
      chk++;
  }
  for(int i=((n+3)/2-1);i<((n+3)/2+n)/2;i++)
  {
    if(str.at(i)!=str.at(n-1-i))
      chk++;
  }
  
  if(chk==0)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
const ll INF = 1LL<<60;
const ll M = pow(10,9)+7;
/*template*/

int main()
{
  ll n;cin>>n;
  ll a=n/3,b=n/5,c=n/15;
  a=3*a*(a+1)/2;
  b=5*b*(b+1)/2;
  c=15*c*(c+1)/2;
  n=n*(n+1)/2;
  cout<<n-a-b+c<<endl;
  return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
const int MOD = 1000000007;
using namespace std;
void solve(void)
{
    int n;
    cin >> n;
    vector<int> a(n + 2);
    rep(i, n) cin >> a[i + 1];
    a[0] = 0, a[n + 1] = 0;
    int res = 0;
    rep(i, n + 1) res += abs(a[i] - a[i + 1]);
    rep(i, n)
    {
        int x = abs(a[i] - a[i + 1]) + abs(a[i + 1] - a[i + 2]);
        int y = abs(a[i] - a[i + 2]);
        cout << res - x + y << endl;
    }
}
int main(void)
{
    solve();
}


Measured memory_bytes: 3764
#include <iostream>
using namespace std;
 
int P, Q, A, N;
int res;

void solve(int a, int n, int sum, int b) {
    if(P * a == Q * sum){
        res++;
        return;
    }
    if(P * a < Q * sum || n >= N)
        return;
 
    for(int i = b; a*i <= A; i++)
        solve(a * i, n + 1, sum * i + a, i);
}
 
int main() {
    while(cin >> P >> Q >> A >> N, P | Q | A | N) {
        res = 0;
        for(int i = 1; i <= A; i++) {
            solve(i, 1, 1, i);
        }
        cout << res << endl;
    }
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#define ll long long 
#define MM(arr,x) memset(arr,x,sizeof(arr))
#define INF 0x3f3f3f3f
#define Maxn 1e5+10;
using namespace std;
int a[205];
int main()
{
	ios::sync_with_stdio(0);
	ll x,k,d,ans;
	cin>>x>>k>>d;
	ll cnt=abs(x)/d;
	if(k<=cnt) cout<<abs(x)-k*d;
	else
	{
		ll t=abs(x)-d*cnt;
		if((k-cnt)%2==1) cout<<abs(t-d);
		else cout<<t;
	}
	return 0;
} 

Measured memory_bytes: 3620
import java.util.Scanner;

class Main {

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

        String a=stdIn.next();
        String b=stdIn.next();
        int sum=0;

        String []c=a.split("");
        String []d=b.split("");
        for(int i=0; i<c.length; i++){
            if(c[i].equals(d[i])){
                sum++;
            }
        }
        
        if(d.length-1==sum){
            System.out.println("Yes");
            
        }
        else{
            System.out.println("No");
            
        }
        
        
        
    }

}

Measured memory_bytes: 35752
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
char maze[25][25];
bool visited[25][25];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int W,H,ans;

void init()
{
	rep(i,25)
	{
		rep(j,25)
		{
			visited[i][j] = false;
		}
	}
}

void dfs(int x, int y)
{
	visited[x][y] = true;
	ans++;
	for (int i = 0; i < 4; ++i)
	{
		int x2 = x + dx[i];
		int y2 = y + dy[i];

		if (x2 >= 0 && x2 < H && y2 >= 0 && y2 < W)
		{
			if (!visited[x2][y2] && maze[x2][y2] != '#')
			{
				dfs(x2,y2);
			}
		}
	}
}

int main()
{
	while(1)
	{
		ans = 0;
		int si,sj;
		cin >> W >> H;
		if (W == 0 && H == 0) return 0;
		rep(i,H)
		{
			rep(j,W)
			{
				cin >> maze[i][j];
				if (maze[i][j] == '@')
				{
					si = i;
					sj = j;
				}
			}
		}

		init();

		dfs(si,sj);

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


Measured memory_bytes: 3104
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   all(a) (a.begin(),a.end())
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;

bool vis[100005];

inline void solve(){
    int n,ans=0; cin>>n; 
    int a[n+1],idx=1;
    for (int i=1;i<=n;i++) {
        cin>>a[i]; 
    }
    bool ok=false;
    while (true){
        ans++;
        if (vis[a[idx]]) break;
        if (a[idx]==2) { ok=true; break; }
        vis[a[idx]]=true;
        idx=a[idx]; 
    }
    if (ok) cout << ans << endl;
    else cout << -1 << endl;
}

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


Measured memory_bytes: 4516
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

#define REP(i, n) for (int i=0; i<(n); ++i)
#define FOR(i, a, n) for (int i=(a); i<(n); ++i)

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl;

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "[";
  REP(i, SZ(v)) {
    if (i) os << ", ";
    os << v[i];
  }
  return os << "]";
}

template<class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  return os << "(" << p.first << " " << p.second << ")";
}

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

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;

const ll MOD = 1e9 + 7;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const ld eps = 1e-9;

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

  int n, q; cin >> n >> q;

  fenwick_tree<ll> bit(n);
  REP(i, n) {
    ll a; cin >> a;
    bit.add(i, a);
  }

  REP(_, q) {
    int t; cin >> t;
    if(t == 0) {
      int p, x; cin >> p >> x;
      bit.add(p, x);
    } else {
      int l, r; cin >> l >> r;
      cout << bit.sum(l, r) << endl;
    };
  }

  return 0;
}

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

int main() {
    int64_t n, k; cin >> n >> k;
    int64_t ans = 0;

    while (k <= n + 1) {
        int64_t min = k * (k - 1) / 2;
        int64_t max = k * (2 * n - k + 1) / 2;
        ans = (ans + (max - min + 1)) % 1000000007;
        ++k;
    }

    cout << ans << endl;
}



Measured memory_bytes: 3612
using System;

namespace ITP1_2_C
{
    class Program
    {
        static void Main(string[] args)
        {
            //??\???
            int a, b, c;
            Read(out a, out b, out c);

            //??????
            SortedList list = new SortedList(a, b, c);
            list.Sort();

            //??????
            list.Write();
        }

        // ?????????????????\??????????????????????????????
        public static void Read(out int a, out int b, out int c)
        {
            string line = Console.ReadLine();
            var inputs = line.Split(' ');
            a = int.Parse(inputs[0]);
            b = int.Parse(inputs[1]);
            c = int.Parse(inputs[2]);
        }
    }
}


namespace ITP1_2_C
{
    class SortedList
    {
        private int[] array;

        public SortedList(params int[] array)
        {
            this.array = array;
        }

        public void Sort()
        {
            for (int i = 0; i < array.Length - 1; i++)
            {
                loop(i);
            }
        }

        public void loop(int i)
        {
            for (int j = array.Length - 1; j > i; j--)
            {
                Change(j);
            }
        }

        public void Change(int j)
        {
            if (array[j] < array[j - 1])
            {
                int buf = array[j];
                array[j] = array[j - 1];
                array[j - 1] = buf;
            }
        }

        public void Write()
        {
            Console.WriteLine(array[0] + " " + array[1] + " " + array[2]);
        }
    }
}

Measured memory_bytes: 9056
// Justice will be served
// شهید حاج قاسم سلیمانی

#include<bits/stdc++.h>
using namespace std ;

int main() {
  string s , t ;
  cin >> s >> t ;
  int ans = 0 ;
  if (s[0] == t[0])
    ans ++ ;
  if (s[1] == t[1])
    ans ++ ;
  if (s[2] == t[2])
    ans ++ ;
  cout << ans ;
}

Measured memory_bytes: 764
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <functional>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#include <cmath>
#include <cctype>
#include <cstdio>
#define ll long long
#define INF 1e+9
#define MOD 1000000007
using namespace std;



int main(){
    int N;
    cin >> N;
    int K;
    cin >> K;
    ll h[N];
    for(int i=0; i<N; i++){
        cin >> h[i];
    }
    sort(h,h+N);
    
    ll ans=INF;
    for(int i=0; i+K<=N; i++){
        ans=min(ans,h[i+K-1]-h[i]);
    }
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(void) {
	int i;
	int a, b, c, d;
	int s1, s2;
	char buf[128], *ch;

	fgets(buf, sizeof(buf), stdin);
	ch = strtok(buf, " ");
	a = atoi(ch);
	ch = strtok(NULL, " ");
	b = atoi(ch);
	ch = strtok(NULL, " ");
	c = atoi(ch);
	ch = strtok(NULL, " ");
	d = atoi(ch);

	s1 = a * b;
	s2 = c * d;

	if(s1 > s2) {
		printf("%d\n", s1);
	} else {
		printf("%d\n", s2);
	}

	return 0;
}


Measured memory_bytes: 2132
#include <bits/stdc++.h>
//---------------------------
using namespace std;
//---------------------------
#define REP(i,n) for(int i = 0; i < (n); i++)
#define P(x) cout << (x) << "\n"
#define fcout cout << fixed << setprecision(18)

#define MOD 1000000007 // 1e9+7
#define PI 3.1415926535
/*
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679
*/
#define ll long long int // 10^18
#define INF 1000000001 // 1e9+1
#define LINF 1000000000000000001 // 1e18+1

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

ll C[51][51];

void comb_table(int N) {
  for(int i=0;i<=N;i++){
    for(int j=0;j<=i;j++){
      if(j==0 or j==i){
        C[i][j]=1LL;
      }else{
        C[i][j]=(C[i-1][j-1] + C[i-1][j]);
      }
    }
  }
}

ll v[100];
int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  // ifstream in("input.txt");
  // cin.rdbuf(in.rdbuf());

  int n,a,b;cin>>n>>a>>b;
  REP(i,n){
    cin>>v[i];
  }
  sort(v,v+n);
  reverse(v,v+n);
  ll summ=0LL;
  for(int i=0;i<a;i++){
    summ+=v[i];
  }
  double ave=(double)summ/a;
  ll pos=0,num=0;
  for(int i=0;i<n;i++){
    if(v[i]==v[a-1]){
      num++;
      if(i<a){
        pos++;
      }
    }
  }
  ll cnt=0LL;
  comb_table(n);
  if(pos==a){
    // 全部同じ数、個数変化
    for(pos=a;pos<=b;pos++){
      cnt+=C[num][pos];
    }
  }else{
    // すべて同じでなく、個数一定
    cnt+=C[num][pos];
  }
  fcout<<ave<<endl;
  cout<<cnt<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

#define MOD 1000000007

struct mint {
    int n;
    mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; }
mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; }
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }

mint dp[1 << 21];
int N, A[21][21];

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &A[i][j]);
        }
    }
    dp[0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < (1 << N); j++) if (__builtin_popcount(j) == i) {
            for (int k = 0; k < N; k++) if ((~j >> k & 1) && A[i][k]) {
                dp[j | 1 << k] += dp[j];
            }
        }
    }
    printf("%d\n", dp[(1 << N) - 1].n);
    return 0;
}



Measured memory_bytes: 8320
#include <bits/stdc++.h>
using namespace std;
int h[100005];
vector<int>adj[100005];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	for(int i=0;i<m;i++){
		int x, y;
		cin>>x>>y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		for(int x:adj[i]){
			if(h[x]>=h[i]){
				goto hell;
			}
		}
		cnt++;
		hell:;
	}
	cout<<cnt;
}

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

typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;

int main(){
    int n;  cin >> n;
    vector<ll> dp(n+1, 1e+15);
    dp[0] = 0;
    for(int i=1; i<=n; i++){
        for(int p6=1; p6<=i; p6*=6)
            dp[i] = min(dp[i], dp[i-p6]+1);
        for(int p9=1; p9<=i; p9*=9)
            dp[i] = min(dp[i], dp[i-p9]+1);
    }
    cout << dp[n] << endl;
    

}

Measured memory_bytes: 1024
n = int(input())

n_li = [n]
while True:
    if n%2==0:
        n = n/2
    elif n%2!=0:
        n = 3*n+1

    if n in n_li:
        break
    else:
        n_li.append(n)
print(len(n_li)+1)
    


Measured memory_bytes: 2940
N, K = map(int, input().split())
A = [0] * N
for i in range(K):
    d = int(input())
    tmp = [int(i) for i in input().split()]
    for j in range(d):
        A[tmp[j]-1] += 1
ans = 0
for i in range(N):
    if A[i] == 0:
        ans += 1
print(ans)

Measured memory_bytes: 67696
# include <algorithm>
# include <iostream>
# include <cmath>
# include <string>
# include <vector>

using namespace std;

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

    vector<long long> blackSum;
    vector<long long> whiteSum;
    long long blackCount=0;
    long long whiteCount=0;

    for(long long i=0; i<N; i++){
        if (S[i]=='#'){
            blackCount ++;
        }else{
            whiteCount ++;
        }
        blackSum.push_back(blackCount);
        whiteSum.push_back(whiteCount);
    }

    vector<long long> numberOfFlips;
    for(long long i=0; i<N; i++){
        if(i==0){
            if (S[i]=='#'){
                numberOfFlips.push_back(whiteSum[N-1] - whiteSum[0]);
            }
        }else{
            if ( (S[i]=='#' && S[i-1]=='.') || (S[i]=='.' && S[i-1]=='#') || i==N-1 ){
                // cout << "i = " << i << "のとき " << blackSum[i-1] + (whiteSum[N-1] - whiteSum[i]) << endl;
                numberOfFlips.push_back( blackSum[i-1] + (whiteSum[N-1] - whiteSum[i]) );
            }
        }
    }
    // cout << blackSum[1] << endl;

    if (numberOfFlips.size()==0){
        cout << 0 << endl;
    }else{
        cout << *min_element(numberOfFlips.begin(), numberOfFlips.end()) << endl;
    }

    return 0;
}


Measured memory_bytes: 6632
#include <bits/stdc++.h>
    using namespace std;
     
    int main(){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        cout << ( abs(a-c) <= d || ( abs(a-b) <= d && abs(b-c) <= d ) ? string{"Yes"}:string{"No"}) << std::endl;
    }

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <stdio.h>
#include <vector>
#define int long long
#define endre getchar();getchar();return 0
#define moder 1000000007
#define inf 1000000000000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define P pair<int,int>
#define all(v) v.begin(),v.end()
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;
bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x%mod;
		}
		x = x * x%mod;
		y >>= 1;
	}
	return res;
}

/*--------Library Zone!--------*/

int h, w, d, q;
P memo[90005];
vector<int>vec[90005];
void solve() {
	rep(i, d) {
		int me = i;
		vec[i].push_back(0);
		while (1) {
			me += d;
			if (me >= h * w)break;
			int cnt = abs(memo[me].first - memo[me - d].first) + abs(memo[me].second - memo[me - d].second);
			vec[i].push_back(vec[i].back() + cnt);
		}
	}
}
signed main() {
	cin >> h >> w >> d;
	rep(i, h)rep(j, w) {
		int a;
		cin >> a;
		a--;
		memo[a] = { i,j };
	}
	solve();
	cin >> q;/*
	rep(i, d) {
		rep(j, vec[i].size()) {
			cout << vec[i][j] << " ";
		}
		cout << endl;
	}*/
	rep(i, q) {
		int le, ri;
		cin >> le >> ri;
		cout << vec[(le - 1) % d][(ri - 1) / d] - vec[(le - 1) % d][(le - 1) / d] << endl;
	}
	endre;
}


Measured memory_bytes: 6784
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int diff = b - a;
        int sum = 0;
        for(int i = 1; i <= diff; i++)
        	sum += i;
        System.out.println(sum - b);
    }
}


Measured memory_bytes: 21716
/****************************************************
*   Template for coding contests                    *
*   Author    :    Sanjeev Sharma                   *
*   Email     :    thedevelopersanjeev@gmail.com    *
*****************************************************/
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
#pragma GCC target ("sse4")
#pragma comment(linker, "/stack:200000000")

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

using namespace __gnu_pbds;
using namespace std;

#define deb(x) cout << #x << " is " << x << "\n";
#define int long long
#define mod 1000000007

const double PI = 2 * acos(0.0);
const long long INF = 1e18L + 5;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string s;
	cin >>s;
	int n = s.size();
	int x = 0, y = 0;
	for(int i = 0; i < n; i++) {
		x += (s[i] != '0' + i % 2);
		y += (s[i] != '1' - i % 2);
	}
	cout <<min(x, y);
	return 0;
}


Measured memory_bytes: 512
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstring>
#include <forward_list>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

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

struct edge {
    int from, to;
};

const ll MOD = 1E+09 + 7;
const ll INF = 1E18;
const int MAX_N = 1E+05;

int N, M;

vector<edge> G[MAX_N + 1];

int dp[MAX_N + 1];
int dag(int s);

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

    cin >> N >> M;

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

    for (int i = 0; i < M; i++) {
        int s, t;
        cin >> s >> t;
        edge e = { s, t };
        G[s].push_back(e);
    }

    int ans = 0;

    for (int i = 1; i <= N; i++) {
        ans = max(ans, dag(i));
    }

    cout << ans << "\n";

    return 0;
}

int dag(int s)
{
    if (dp[s] != -1) {
        return dp[s];
    }
    if (G[s].size() == 0) {
        return dp[s] = 0;
    }
    int maxc = 0;
    for (int i = 0; i < G[s].size(); i++) {
        maxc = max(maxc, dag(G[s][i].to));
    }
    return dp[s] = maxc + 1;
}

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

int n;
int main(){
    cin >> n;
    long long l0=2,l1=1;
    long long temp;
    for(int i=0;i<n-1;i++){
        temp=l1+l0;
        l0=l1;
        l1=temp;
    }
    cout << l1 << endl;
}

Measured memory_bytes: 764
#include<stdio.h>
#include<string.h>

int main(){
  int a,b,c,s,m,temp;
  scanf("%d %d %d",&a,&b,&c);
  
  if(c<a){
    temp=a;
    a=c;
    c=temp;
  }
  
  if(c<b){
    temp=c;
    c=b;
    b=temp;
  }
  
  if(b>a){
    temp=b;
    b=a;
    a=temp;
  }
  
  s=(c-a)/2+(c-b)/2;
  
  m=a%2+b%2+c%2;
  
  if(m==0 || m==3)
    printf("%d",s);
  else if((a-b)%2==0)
    printf("%d",s+1);
  else printf("%d",s+2);
  
}

Measured memory_bytes: 128
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
using namespace std;

typedef pair<int,int> Pii;

int main(int argc, char const *argv[]) {
  int n;cin>>n;
  vector<int> a(n);
  vector<Pii> mem(n);
  // unordered_set<int> mem;
  for(int i=0;i<n;++i){
    cin>>a[i];
    a[i]--;
    mem[i] = Pii(a[i],i);
    // mem.insert(a[i]);
  }
  sort(mem.begin(),mem.end());
  vector<long long> res(n*n,-1);
  for(int i=0;i<n;++i){
    res[a[i]] = i+1;
  }
  long long tmp = 0;
  for(int i=0;i<n;++i){
    int ii = mem[i].second;
    for(int j=0;j<ii;++j){
      while(tmp<n*n&&res[tmp]!=-1)tmp++;
      if(tmp>=a[ii]){
        cout<<"No"<<endl;
        return 0;
      }
      res[tmp] = ii+1;
    }
  }
  // for(int i=0;i<n*n;++i)cout<<res[i]<<" ";
  tmp = n*n-1;
  for(int i=0;i<n;++i){
    int ii = mem[n-i-1].second;
    for(int j=0;j<n-ii-1;++j){
      while(tmp>-1&&res[tmp]!=-1)tmp--;
      if(tmp<=a[ii]){
        cout<<"No"<<endl;
        return 0;
      }
      res[tmp] = ii+1;
    }
  }
  cout<<"Yes"<<endl;
  for(int i=0;i<n*n;++i)cout<<res[i]<<" ";
  cout<<endl;
  return 0;
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
using namespace std;
#define NewNode (ListNode *)malloc(sizeof(ListNode))
#define Mem(a,b) memset(a,b,sizeof(a))
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-10;
const unsigned long long mod = 998244353;
const double II = 3.1415926535;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> piil;
map<int,int> mp;
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ll ans = 0,n;
    scanf("%lld",&n);
    for(int i = 1;i <= n;i++)
    {
        ll a;
        scanf("%lld",&a);
        ans += mp[a-i];
        mp[-1*a-i]++;
    }
    printf("%lld\n",ans);
}

Measured memory_bytes: 20680
#include<bits/stdc++.h>
using namespace std;
int h,w,cnt=0;
char a;
int main(){
    scanf("%d%d",&h,&w);
    for (int i = 1; i <= h*w; i++)
    {
            cin>>a;
            if (a=='#')
            {
                cnt++;
            }
    }
    if (cnt==h+w-1)
    {
        printf("Possible");
    }
    else
    {
        printf("Impossible");
    }
    return 0;
}

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;

int main(){
    int d, g;
    cin >> d >> g;
    vector<int> p(d), c(d);
    for (int i = 0; i < d; ++i) {
        cin >> p[i] >> c[i];
    }

    int res = INF;
    int score;
    int cnt;
    for (int i = 0; i < (1<<d); ++i) {
        score = 0;
        cnt = 0;
        for (int j = 0; j < d; ++j){
            if(i & (1<<j)){
                score += c[j];
                score += 100 * (j+1) * p[j];
                cnt += p[j];
            }
        }
        if(score >= g){
            res = min(res, cnt);
            continue;
        }

        for (int j = d-1; j >= 0; --j) {
            if (!(i & (1 << j))) {
                if (100 * (j + 1) * (p[j] - 1) < g - score) {
                    score += 100 * (j + 1) * (p[j] - 1);
                    cnt += (p[j] - 1);
                } else {
                    cnt += (g - score + 100 * (j + 1) - 1) / 100 / (j + 1);
                    res = min(res, cnt);
                    break;
                }
            }
        }
        if(score < g) continue;
        res = min(res, cnt);
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int A[45] = {};
int B[45];

int fib(int n);

int main() {
	
	int n;
	
	while(cin >> n) {
		
		for(int i=0;i<n;i++)
			B[i] = 0;
		
		cout << fib(n) << "\n";
		
	}

	return 0;
}

int fib(int n) {
	
	A[0] == A[1] == 1;
	
	if(n == 0 || n == 1) 
		return 1;
	
	else if(B[n])
		return A[n];
		
	else {
		A[n] = fib(n-1) + fib(n-2);
		B[n] = 1;
		return A[n];
}

}


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

int main() {
    long long a; 
    cin >> a;
    string s;
    int x;
    cin >> x;
    char rubbish;
    cin >> rubbish;
    int y;
    cin >> y;
    x = x * 100 + y;
    cout << a * x / 100 << endl; 
    return 0;
}


Measured memory_bytes: 3624
import java.util.Scanner;

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

        int[] dam = new int[N];

        for (int i = 0; i < N; i++) {
            dam[i]=sc.nextInt();
        }
        int r02 = 0;
        for (int i = 0; i <N ; i++) {
            r02 += dam[i] * ((i%2==1)? -1 : 1);
        }

        System.out.print(r02+" ");
        int r = r02/2;
        for (int i = 0; i <N-1 ; i++) {
            r = dam[i]-r;
            System.out.print(r*2+" ");
        }


    }

}


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

int main() {
  int N, M;
  cin >> N>>M;
  vector<int> H(N);
  vector<bool> J(N);
  rep(i, N) {
    cin >> H.at(i);
    J.at(i) = true;
  }

  rep(i, M){
    int A, B;
    cin >> A >> B;
    if(H.at(A-1) >= H.at(B-1)) J.at(B-1) = false;
    if(H.at(A-1) <= H.at(B-1)) J.at(A-1) = false;
  }
  int ans = 0;
  rep(i, N){
    if(J.at(i)) ans++;
  }
  cout << ans << endl;
}


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

using namespace std;
#define ll long long int

int main(){
    ll n , k;
    cin >> n >> k;
    ll height[n];
    ll dp[n];
    for(int i =0 ; i  < n ; i ++)
    {
        cin >> height[i];
        dp[i] = INT_MAX;
    }
    
    dp[0] =0 ;
    for(int i = 0; i < n - 1 ; i ++)
    {
        for(int j = 1; j <= min(k , n - 1) ; j ++)
        dp[i + j] = min(dp[i + j] , dp[i] + abs(height[i + j] - height[i]));
        //dp[i + 2] = min(dp[i + 2] , dp[i] + abs(height[i + 2] - height[i]));
    }
    cout << dp[n - 1] << endl;
}

Measured memory_bytes: 1792
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n=sc.nextInt();
    Set<String> set= new HashSet<>();
    for(int i=0;i<n;i++)set.add(sc.next());
    System.out.println(set.size());
  }
}


Measured memory_bytes: 78228
import java.util.Scanner;

//AtCoder Beginner Contest 153
//D - Caracal vs Monster
public class Main {

	public static long attack(long H) {
		if (H <= 1) return 1;
		else {
			long ans = 1;
			if (H % 2 == 0) {
				ans += attack(H / 2) * 2;
			} else {
				ans += attack((H - 1) / 2) * 2;
			}
			return ans;
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long H = Long.parseLong(sc.next());
		sc.close();

		long ans = attack(H);
 		System.out.println(ans);
	}
}


Measured memory_bytes: 23124
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << #x << " = " << x << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 305


int main(){
  int n,max_p=-INF;
  int p[SIZE][SIZE] = {};
  int p_h[SIZE][SIZE] = {},p_v[SIZE][SIZE] = {};

  scanf("%d",&n);
  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      scanf("%d",p[i]+j);
      p_h[i][j] = p_v[i][j] = p[i][j];
      max_p = max(p[i][j],max_p);
    }
  }

  if(max_p <= 0){
    printf("%d\n",max_p);
    return 0;
  }

  for(int i=0;i<=n;i++){
    for(int j=1;j<=n;j++){
      p_h[i][j] += p_h[i][j-1]; 
    }
  }
  for(int i=0;i<=n;i++){
    for(int j=1;j<=n;j++){
      p_v[j][i] += p_v[j-1][i]; 
    }
  }

  int v[SIZE];
  int ans = 0;
  
  for(int i=1;i<=n;i++){
    
    for(int j=1;j<=n;j++){
      for(int k=j;k<=n;k++){
        ans = max(ans, p_v[k][i]-p_v[j-1][i]);
      }
    }
    
    for(int j=i+1;j<=n;j++){
      //[i,j]

      for(int k=0;k<=n;k++){
        v[k] = p_h[k][j-1]-p_h[k][i]; //[i+1,j-1]
      }

      int s = 0;

      for(int k=0;k<=n;k++){
        s += p[k][j] + p[k][i];

        v[k] += s;
      }

      for(int k=n;k>0;k--){
        v[k-1] = max(v[k],v[k-1]);
      }

      s = 0;
      
      for(int k=1;k<=n;k++){
        if(k<n){
          ans = max(ans, v[k+1]+(p_h[k][j-1]-p_h[k][i])+s);
        }
        
        ans = max(ans, p_h[k][j]-p_h[k][i-1]);

          s -= p[k][j]+p[k][i];
      }
    }
  }

  printf("%d\n",ans);
  
  return 0;
}

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

 int main(){

  int S;
  int h,m,s;

  cin >> S ;


  h = S / 3600;
 
  m= ( S % 3600 ) / 60 ;

  s= ( S % 3600 % 60 );

 
  cout << h << ":" << m << ":" << s << endl;



 return 0;
}

Measured memory_bytes: 3072
import fractions
A, B, C, D = tuple([int(x) for x in input().split(' ')])

A -= 1
c = B // C - A // C
d = B // D - A // D

x = (C * D) // fractions.gcd(C, D)

cd = B // x - A // x

print(B-A-c-d+cd)

Measured memory_bytes: 5048
INF=10**30
def Belman_Ford(s,N,Edge):
    dist=[INF]*N
    neg=[False]*N
    dist[s]=0
    for i in range(N-1):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=min(dist[t],dist[f]+c)
    for i in range(N):
        for f,t,c in Edge:
            if dist[t]>dist[f]+c and dist[f]!=INF:
                dist[t]=dist[f]+c
                neg[t]=True
            if neg[f]:
                neg[t]=True
    return dist,neg
                
N,M,P=map(int,input().split())
Edge=[]
for i in range(M):
    a,b,c=map(int,input().split())
    Edge.append((a-1,b-1,-(c-P)))
dist,neg=Belman_Ford(0,N,Edge)

if(neg[N-1]):
    print(-1)
else:
    ans=-dist[N-1]
    print(max(0,ans))

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

int main() {
	int n, m;
	::std::cin >> n >> m;
	::std::vector<int> cnt(m, n);
	while (n--) {
		int k;
		::std::cin >> k;
		while (k--) {
			int a;
			::std::cin >> a;
			--cnt[a - 1];
		}
	}
	int ans = 0;
	for (const auto &e : cnt) {
		if (!e) {
			++ans;
		}
	}
	::std::cout << ans << ::std::endl;
}


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


int main()
{
    ios::sync_with_stdio(false);
    ll t;
    string s;
    cin>>s;
    ll tot=0;
    char r=s[s.length()-1];
    for(int i=s.length()-1;i>=0;i--)
    {
        if(s[i]!=r){tot++;
            r=s[i];
        }
    }
    cout<<tot<<endl;
}








Measured memory_bytes: 512
// SeeAlso: https://arc061.contest.atcoder.jp/tasks/arc061_a

#include <bits/stdc++.h> 

typedef long long ll;
using namespace std;

int cnt = 0;
int rec(long long x){
    if(x == 0) return cnt;
    else{
        x /= 10;
        cnt++;
        return rec(x);
    }
}
 
int main(void){
   ll S;
   cin >> S;

   int b = rec(S);
   ll ans = 0;
   vector<bool> vec(b-1);

   for(int i = 0; i < pow(2, b - 1); i++){
       ll I = i;
       for(int j = 0; j < b - 1; j++){
           vec.at(j) = I % 2;
           I /= 2;
       }
    
        vector<int> array(0);
        for(int j = 0; j < b-1; j++){
            if(vec.at(j) == 1) array.push_back(j);
        }
        int x = array.size();
    
        ll current = S;
        for(int j = 0; j < x; j++){
            ans += current / ll(pow(10, b-1-array.at(j)));
            current -= ll(current / int(pow(10, b-1-array.at(j)))) * pow(10, b-1-array.at(j));
        }
        ans += ll(current);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = [I() for _ in range(n)]
    if a[0] > 0:
        return -1
    for i in range(n-1):
        if a[i] < a[i+1] - 1:
            return -1
    r = a[-1]
    for i in range(n-2,-1,-1):
        if a[i] == a[i+1] - 1:
            continue
        r += a[i]

    return r




print(main())



Measured memory_bytes: 14092
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
struct pair_hash {
    template <class T1, class T2>
    size_t operator () (const pair<T1,T2> &p) const {
        auto h1 = hash<T1>{}(p.first);
        auto h2 = hash<T2>{}(p.second);
        return h1 ^ h2;  
    }
};
using Vote = pair<ll,ll>;
using Unordered_map = unordered_map<Vote, int, pair_hash>;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define FORD(i,a,b) for(ll i=a;i>=b;i--)
#define showvec(arr,a,b) for(ll i=a;i<b;i++) cout<<arr[i]<<" ";
#define read_input(arr,a,b) for(ll i=a;i<b;i++) cin>>arr[i];
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define endl '\n'
#define SmooothOperatorrrrr()                 \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                    \
    cout.tie(0);                   
#define deci(n) cout<<fixed<<setprecision(n)
const int mod=998244353;
const int mod2=1000000007;
#define M_PI 3.14159265358979323846
#define LL_MAX 9223372036854775807
#define MAXN 2000001
/**************************************************************************************************/
int main()
{
    SmooothOperatorrrrr();
    ll X, K, D;
    cin >> X >> K >> D;
    X = abs(X);
 
    ll straight = min(K, X / D);
    K -= straight;
    X -= straight * D;
 
    if (K % 2 == 0) {
        cout << X << endl;
    } else {
        cout << D - X << endl;
    }
 
    return 0;
}       

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
int a[1000010], b[1000010];
int main(){
  int n, k;
  while(cin>>n>>k){
    ll ans=0;
    for(int i=0; i<n; ++i){
      scanf("%d%d",&a[i],&b[i]);
      if((a[i]|k)==k)
        ans+=b[i];
    }
    ll tmp;
    for(int i=0; i<31; ++i){
      if((1<<i)&k){
        k=k&(~(1<<i));
        k|=(1<<i)-1;
        tmp=0;
        for(int j=0; j<n; ++j){
          if((a[j]|k)==k)
            tmp+=b[j];
        }
        ans=max(ans, tmp);
      }
    }
    printf("%lld\n",ans);
  }
  return 0;
}



Measured memory_bytes: 4736
#include<iostream>
#include<string>
#include<vector>
#include <algorithm>
#include<math.h>

using namespace std;
int main() {
	int h, a;
	cin >> h >> a;
	int cou = 0;
	while (h > 0) {
      cou++;
      h -= a;
		
	}
  cout << cou;
}


Measured memory_bytes: 256
#define loop(i,j,k) for(long long i = j;i < k;i++)

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <list>
#include <stack>
#include <set>
#include <map>

using namespace std;

typedef long long int int64;

int main(void) {
    int n,a[2][100];
    cin >> n;
    loop(i,0,2) {
        loop(j,0,n) {
            cin >> a[i][j];
        }
    }
    int maxc = 0;
    loop(i,0,n) {
        int res = 0;
        loop(j,0,i + 1) {
            res += a[0][j];
        }
        loop(j,i,n) {
            res += a[1][j];
        }
        maxc = max(maxc,res);
    }
    cout << maxc;
}


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

struct Node{
    int a, b, c, d;
};

int mat[505][505];

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin >> mat[i][j];
        }
    }

    vector<Node> res;

    for(int i = 0; i < n - 1; ++i){
        for(int j = 0; j < m; ++j){
            if(mat[i][j] % 2 == 1){
                mat[i][j]--;
                mat[i + 1][j]++;
                res.push_back(Node{i + 1, j + 1, i + 2, j + 1});
            }
        }
    }

    for(int i = 0; i < m - 1; ++i){
        if(mat[n - 1][i] % 2 == 1){
            mat[n - 1][i]--;
            mat[n - 1][i + 1]++;
            res.push_back(Node{n, i + 1, n, i + 2});
        }
    }

    cout << res.size() << "\n";
    for(auto x : res){
        cout << x.a << " " << x.b << " " << x.c << " " << x.d << "\n";
    }
    return 0;
}


Measured memory_bytes: 5104
#include <bits/stdc++.h>
#define D(x) cout << #x << "=" << x <<endl; 
using namespace std; 

//int _; 

string s;

int main()
{
	//for(scanf("%d",&_);_;_--)
	cin >> s;
	s=s.substr(0,3);
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 3632
#
# Yet I'm feeling like
# 	There is no better place than right by your side
# 		I had a little taste
# 			And I'll only spoil the party anyway
# 				'Cause all the girls are looking fine
# 					But you're the only one on my mind


import sys
inf = float("inf")
#sys.setrecursionlimit(1000000)


# abc='abcdefghijklmnopqrstuvwxyz'
# abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod,MOD=1000000007,998244353
# vow=['a','e','i','o','u']
# dx,dy=[-1,1,0,0],[0,0,1,-1]

#from cmath import sqrt
#from collections import deque, Counter, OrderedDict,defaultdict
#from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
# from math import ceil,floor,log,sqrt,factorial,pow,pi,gcd,log10
#from bisect import bisect_left,bisect_right
#import numpy as np

def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

n=int(input())
mydict=dict()
for i in range(n):
    string=list(input())
    string.sort()
    string=''.join(string)
    if string not in mydict:
        mydict[string]=1
    else:
        mydict[string]+=1
total=0
for i in mydict:
    total+=((mydict[i])*(mydict[i]-1))//2
print(total)


Measured memory_bytes: 17928
n = int(input())
s = [input() for i in range(n)]
import collections

counted = collections.Counter(s)

m = max(counted.values())

chars = []
for key, value in counted.items():
    if value == m:
        chars.append(key)
chars=sorted(chars)

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


Measured memory_bytes: 35476
#!/usr/bin/env python
# -*- coding: utf-8 -*-

input = raw_input().split(" ")
A = int(input[0])
B = int(input[1])
K = int(input[2])


for i in range(0, K):
    if i % 2 == 0:#高橋君のとき
        if A % 2 == 1:
            A -= 1
            A_save = A
        else:
            A_save = A
        A = A_save / 2
        B += A_save / 2
    else:#青木君のとき
        if B % 2 == 1:
            B -= 1
            B_save = B
        else:
            B_save = B
        A += B_save / 2
        B = B_save / 2



print str(A) + " " + str(B)

Measured memory_bytes: 2568
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
#include <list>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

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;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
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;
}
//最大公約数
long long gcd(long long x, long long y){
    if(y==0) return x;
    else return gcd(y,x%y);
}
//最小公倍数
long long lcm(long long x, long long y){
    return x / gcd(x, y) * y;
}
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    string S; cin >> S;
    cout << count(S.begin(),S.end(),'1') << endl;
    return 0;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s,t;
    cin>>s>>t;
    bool a=true;
    if(s.size()+1!=t.size()) a=false;
    for(int i=0;i<s.size();i++){
        if(s.at(i)!=t.at(i)) a=false;
    }
    if(a) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 3628
mod = 10**9 + 7
def iip(listed = False):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def inv(n, mod):
    return power(n, mod-2)

def conbination(n, r, mod, test=False):
    if n <=0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0

    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    #if test:
    #    print(f"{n}C{r} = {ret}")
    return ret

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret

N, K = iip()
A = iip(listed=True)
A.sort(reverse=True)



def main():
    plus = 0
    minus = 0

    a1Ck1 = conbination(N, K-1, mod) % mod
    for i, Ai in enumerate(A):
        if N-i < K:
            break
        a1Ck1 *= (N-K-i+1)
        a1Ck1 *= inv(N-i, mod)
        a1Ck1 %= mod

        plus += a1Ck1 * Ai

    A.sort(reverse=False)
    a1Ck1 = conbination(N, K-1, mod) % mod
    for i, Ai in enumerate(A):
        if N-i < K:
            break
        a1Ck1 *= (N-K-i+1)
        a1Ck1 *= inv(N-i, mod)
        a1Ck1 %= mod

        minus += a1Ck1 * Ai

    ans = plus-minus
    ans %= mod
    print(ans)


main()

Measured memory_bytes: 66600
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <numeric>
#include <string>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

	for (int i = 0; i < t.size(); i++) {
		if (t[i] == '?') {
			t[i] = 'D';
		}
	}

	cout << t;
	return 0;
}

Measured memory_bytes: 3752
import sys

# import bisect
# map(int, sys.stdin.read().split())
from collections import Counter
import heapq
from collections import deque

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


def main():
    N,M = map(int,input().split())
    A =[]
    for i in range(N):
        a,b = map(int,input().split())
        A.append((a,-b))
    A.sort()
    A = deque(A)

    h = []
    ans =0
    for i in range(1,M+1):

        while A:
            if A[0][0] ==i:
                temp = A.popleft()
                heapq.heappush(h,temp[1])
            else:
                break

        if len(h)==0:
            continue
        else:
            ans += heapq.heappop(h)


    print(-ans)







if __name__ == "__main__":
    main()


Measured memory_bytes: 84672
//Fence
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
#define ll long long
//#define d double
//#define int long long
#define F first
#define S second
#define FastIO ios_base::sync_with_stdio(false),cin.tie(0)
#define fix std::fixed<<setprecision(10)
#define M 100000000
#define f(n) for(int i=0;i<n;i++)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define vi vector<int>
#define pb push_back
#define si set<int>
#define cl(n,m) (ceil(double(n)/double(m)))
#define T() int t; cin>>t; while(t--)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ll n;
    cin>>n;
    ll x,a,b,c;
    cin>>a>>b>>c;
    long long dpa[n],dpb[n],dpc[n];
    dpa[0]=a,dpb[0]=b,dpc[0]=c;
    for(int i=1;i<=n-1;i++)
    {
        cin>>a>>b>>c;
        dpa[i]=a+max(dpb[i-1],dpc[i-1]);
        dpb[i]=b+max(dpa[i-1],dpc[i-1]);
        dpc[i]=c+max(dpb[i-1],dpa[i-1]);
    }
long long ans=max(dpa[n-1],max(dpb[n-1],dpc[n-1]));
cout<<ans;



}


Measured memory_bytes: 2560