akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;

#define N 100
#define rep(i, n) for(int i=0; i<n; ++i)

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

bool inRange(int x, int a, int b) {
	return a<=x && x<=b;
}

void drawSpiral(int n) {
	char mat[N][N];
	rep(i, n) rep(j, n) mat[i][j] = ' ';
	int x = 0, y = n-1, dir = 1, s = 0, mv = n;
	mat[y][x] = '#';
	while(1) {
		for(int i=0; i<mv-1; ++i) {
			x += dx[dir]; y += dy[dir];
			mat[y][x] = '#';
		}
		if(mv<=2 && s>0) break;
		if(s>0 && s%2==0) {
			mv -= 2;
			if(mv<=1) break;
		}
		dir = (dir + 1) % 4;
		++s;
	}
	rep(i, n) {
		rep(j, n) cout << mat[i][j];
		cout << endl;
	}
}

int main() {
	int d, n, count = 0;
	cin >> d;
	while(d--) {
		if(count++>0) cout << endl;
		cin >> n;
		drawSpiral(n);
	}
	return 0;
}

Measured memory_bytes: 1156
#include <stdio.h>

int main(void) {
    int n;
    scanf("%d", &n);
    double a[n];
    double total = 0;
    for(int i = 0; i < n; i++) {
        scanf("%lf", &a[i]);
        total += 1/a[i];
    }
    printf("%f\n", 1/total);
    return 0;
}


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

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

#define loop(i, n) for(int i = 0;i < n;i++)
#define IINF 2e9
#define MOD 1e9+7

int main(void){

    int n, x, t;
    cin >> n >> x >> t;

    cout << ((n+x-1)/x)*t << endl;

    return 0;
}

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

int main(){
  int n; string a, b;
  cin >> n >> a >> b;
  for(int i = n ; i >=0 ; i--){
    int ck = 1;
    for(int j = 0 ; j < i ; j++){
      if(a[n-i+j]!=b[j]) ck = 0;
    }
    if(ck){
      cout << 2*n-i;
      return 0;
    }
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    if (a == b || b == c || a == c)
    {
        if (a == b && b == c)
        {
            cout << "No" << endl;
        }
        else
        {
            cout << "Yes" << endl;
        }
    }
    else
    {
            cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  	int A, B, res;
  	cin >> A >> B;
  	if(A >= B){
    	res += A;
      	A--;
    }else{
    	res += B;
      	B--;
    }
  
  	if(A >= B){
    	res += A;
      	A--;
    }else{
    	res += B;
      	B--;
    }
  
  	cout << res << endl;
	return 0;
}

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

using namespace std;

using ll = long long;
using ull = unsigned long long;

string acgt = "ACGT";
int main(int argc, char const *argv[]) {
	string s;
	std::cin >> s;

	int count,ans;
	count = ans = 0;

	bool flag;

	for (size_t i = 0; i < s.size(); i++) {
		flag = false;
		for (size_t j = 0; j < acgt.size(); j++) {
			if (s[i] == acgt[j]) {
				count++;
				flag = true;
			}
		}
		if (!flag) {
			ans = max(ans,count);
			count = 0;
		}
	}

	if (flag) {
		ans = max(ans,count);
	}


	std::cout << ans << '\n';

	return 0;
}


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

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        if((int)((double)i * 1.08) == n){
            cout << i << endl;
            return 0;
        }
    }
    cout << ":(" << endl;
    return 0;
}

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

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

bool used[51][51][51][51];
string roomL[51], roomR[51];

int main() {
  // use scanf in CodeForces!
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  while (true) {
    int R, C;
    cin >> C >> R;
    if (R == 0 && C == 0) break;
    REP(i, R) cin >> roomL[i] >> roomR[i];

    int slr = 0, slc = 0, elr = 0, elc = 0, srr = 0, src = 0, err = 0, erc = 0;
    REP(r, R) REP(c, C) {
      if (roomL[r][c] == 'L') slr = r, slc = c;
      else if (roomL[r][c] == '%') elr = r, elc = c;
      if (roomR[r][c] == 'R') srr = r, src = c;
      else if (roomR[r][c] == '%') err = r, erc = c;
    }
    //cout << slr << ' ' << slc << ' ' << elr << ' ' << elc << ' ' << srr << ' ' << src << ' ' << err << ' ' << erc << endl;
    REP(i, R) REP(j, C) REP(k, R) REP(l, C) used[i][j][k][l] = false;
    
    queue<P> que;
    que.push(P(slr * C + slc, srr * C + src));

    bool flag = false;
    while (!que.empty()) {
      P p = que.front(); que.pop();
      int lr = p.first / C, lc = p.first % C, rr = p.second / C, rc = p.second % C;
      //cout << lr << ' ' << lc << ' ' << rr << ' ' << rc << endl;
      if (lr == elr && lc == elc && rr == err && rc == erc) {
	flag = true;
	break;
      } else if (used[lr][lc][rr][rc] || (lr == elr && lc == elc) || (rr == err && rc == erc)) {
	continue;
      }

      used[lr][lc][rr][rc] = true;
      REP(i, 4) {
	int nlr = lr + dr[i], nlc = lc + dc[i], nrr = rr + dr[(i+2*(i&1))%4], nrc = rc + dc[(i+2*(i&1))%4];
	if (nlr < 0 || nlr >= R || nlc < 0 || nlc >= C || roomL[nlr][nlc] == '#') nlr = lr, nlc = lc;
	if (nrr < 0 || nrr >= R || nrc < 0 || nrc >= C || roomR[nrr][nrc] == '#') nrr = rr, nrc = rc;
	if (!used[nlr][nlc][nrr][nrc]) que.push(P(nlr * C + nlc, nrr * C + nrc));
      }
    }
    cout << (flag ? "Yes" : "No") << endl;    
  }
  return 0;
}

Measured memory_bytes: 10356
#define LOCAL
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rrep(i, n) for(int i=(n-1); i>=0; --i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)
#define ALL(v) (v).begin(), (v).end()
#define memr(dp, val) memset(dp, val, sizeof(dp))
using namespace std;
typedef long long ll;
static const int INTINF = (INT_MAX >> 1); // 10^9 + 10^7
static const ll LLINF = (LLONG_MAX >> 1);
static const int MAX = 1e5+1;
static const ll MOD = 1e9+7;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> inline bool int_ceil(T a, T b) { T res = a / b; if(a % b != 0) res++; return res; }
template<typename T>
using min_priority_queue = priority_queue<T, vector<T>, greater<T> >;
string to_string(string s) { return '"' + s + '"'; }
string to_string(bool b) { return b ? "true" : "false"; }
template <size_t N> string to_string(bitset<N> bs) {
  string res;
  for (size_t i = 0; i < N; ++i) res += '0' + bs[i];
  return res;
}
string to_string(vector<bool> v) {
  string res = "{";
  for (bool e : v) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U> string to_string(pair<T, U> p);
template <class C> string to_string(C c) {
  string res = "{";
  for (auto e : c) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U> string to_string(pair<T, U> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
void debug() { cerr << '\n'; }
template <class Head, class... Tail> void debug(Head head, Tail... tail) {
  cerr << '\t' << to_string(head), debug(tail...);
}
#ifdef LOCAL
#define print(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
#else
#define print(...)
#endif

int main(int argc, const char * argv[]) {
	std::cout << std::fixed << std::setprecision(15);

	ll N; cin >> N;
	vector<ll> A(N);
	rep(i, N) cin >> A[i];

	ll idx = 0;
	ll ma = 0;
	rep(i, N){
		if(ma < abs(A[i])){
			ma = abs(A[i]);
			idx = i;
		}
	}

	vector<pair<ll, ll> > ans;
	if(A[idx] < 0){
		// minus
		rrep(i, N){
			if(i == N-1) continue;
			if(A[i] > A[i+1]){
				while(A[i] > A[i+1]){
					A[i] += A[idx];
					ans.push_back(make_pair(idx, i));
				}
				idx = i;
			}
		}
	}
	else if(A[idx] == 0){
		cout << 0 << endl;
		return 0;
	}
	else{
		// plus
		rep(i, N){
			if(i == 0) continue;
			if(A[i] < A[i-1]){
				while(A[i] < A[i-1]){
					A[i] += A[idx];
					ans.push_back(make_pair(idx, i));
				}
				idx = i;
			}
		}
	}

	cout << ans.size() << endl;
	rep(i, ans.size()){
		cout << ans[i].first + 1<< " " << ans[i].second + 1 << endl;
	}

	// print(A);

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;

using PII = pair<int, int>;
const int MAXN = 1e3 + 50;
int H, W, N, res, cnt, cur;
char mat[MAXN][MAXN];
std::queue<PII> que;

int vis[MAXN][MAXN];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
void bfs(int& x, int& y){
    
    while (!que.empty()) que.pop(); // clear all
    memset(vis, 0, sizeof(vis));

    que.push({x, y});

    int lop, dep = 0;
    // cout << "Counter is: --> " << cnt << endl;
    while (!que.empty()){
        lop = que.size();
        // cout << "Depth: " << dep << endl;
        for (int i = 0; i < lop; ++ i){
            auto pf = que.front(); que.pop();
            int cx = pf.first, cy = pf.second;
            if (vis[cx][cy]) continue;
            vis[cx][cy] = 1;
            // cout << cx << " " << cy << endl;
            if (mat[cx][cy] - '0' >= 0 && mat[cx][cy] - '0' <= 9 && mat[cx][cy] - '0' <= cur){
                mat[cx][cy] = '.';
                ++ cnt, ++ cur; // find one, add one to cur
                res += dep;
                x = cx, y = cy;
                return;
            }

            for (int i = 0; i < 4; ++ i){
                int nx = cx + dx[i], ny = cy + dy[i];
                if (nx < 0 || nx >= H || ny < 0 || ny >= W || mat[nx][ny] == 'X') continue;
                que.push({nx, ny});
            }
        }
        ++ dep;
    }


}

int main(){
    cin >> H >> W >> N;

    cur = 1;
    res = cnt = 0;
    int cx, cy;
    for (int i = 0; i < H; ++ i){
        for (int j = 0; j < W; ++ j){
            cin >> mat[i][j];
            if (mat[i][j] == 'S') cx = i, cy = j;
        }
    }

    while (cnt < N){
        bfs(cx, cy);
    }

    cout << res << endl;
    return 0;
}


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

l = list(map(int,input().split()))

flag = 0
ans = 0

for i in range(1,n):
	#print(i,flag)
	
	if flag == 0:
		if l[i] > l[i-1]:
			flag = 1
		elif l[i] < l[i-1]:
			flag = -1
		else:
			pass
						
	elif flag == 1:
		if l[i] > l[i-1]:
			pass
		elif l[i] == l[i-1]:
			pass
		elif l[i] < l[i-1]:
			ans = ans + 1
			flag = 0
			
	elif flag == -1:
		if l[i] < l[i-1]:
			pass
		elif l[i] == l[i-1]:
			pass
		elif l[i] > l[i-1]:
			ans = ans + 1
			flag = 0		

print(ans+1)


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

typedef long long ll;

using namespace std;

int main() {
	int n; cin >> n;
	int sub[n+1] = {0};
	for (int i = 0; i < n-1; i++) {
		int temp; cin >> temp;
		sub[temp]++;
	}
	
	for (int i = 1; i <= n; i++) {
		cout << sub[i] << endl;
	}
		
}





Measured memory_bytes: 4352
n = int(input())
p = list(map(int, input().split()))
ans = 0

for i in range(1, n - 1):
    larger = max(p[i-1], p[i+1])
    smaller = min(p[i-1], p[i+1])
    if p[i] > smaller and p[i] < larger:
        ans += 1

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define int ll

const int BINF = 1e18;

map<int, int> opt;
int c[3], D;
vector<int> kek = {2, 3, 5};
void go(int ost) {
  if (opt.find(ost) != opt.end()) {
    return;
  }
  int rez = BINF;
  for (int i = 0; i < 3; i++) {
    if (ost % kek[i] == 0) {
      go(ost / kek[i]);
      rez = min(rez, opt[ost / kek[i]] + c[i]);
    }
    else {
      int val1 = ost % kek[i], val2 = kek[i] - val1;
      go((ost - val1) / kek[i]);
      go((ost + val2) / kek[i]);
      if (ost - val1 == 0) {
        rez = min(rez, D * val1);
      }
      else {
        rez = min(rez, opt[(ost - val1) / kek[i]] + c[i] + D * val1);  
      }
      rez = min(rez, opt[(ost + val2) / kek[i]] + c[i] + D * val2);
    }
  }
  if (log2(D) + log2(ost) < 63) {
    rez = min(rez, D * ost);  
  }
  opt[ost] = rez;
  return;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    cin >> c[0] >> c[1] >> c[2] >> D;
    opt = {};
    opt[0] = 0;
    opt[1] = D;
    go(n);
    cout << opt[n] << '\n';
  }
}

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

using namespace std;
typedef long long ll;

int main() {
	ll n, k, q;
	cin >> n >> k >> q;
	vector<ll> count(n, 0);

	
	for (int i = 0; i < q; ++i) {
		ll ai;
		cin >> ai;
		ai--;
		count.at(ai)++;
	}
	for (int i = 0; i < n; ++i) {
		if (k - q + count.at(i) > 0) {
			cout << "Yes" << endl;
		}
		else {
			cout << "No" << endl;
		}
	}
	
	return 0;
}


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

int main()
{
    int a, b;

    cin >> a >> b;
    if ((a * b) == 15)
    {
        cout << "*" << endl;
    }
    else if ((a + b) == 15)
    {
        cout << "+" << endl;
    }
    else
    {
        cout << "x" << endl;
    }
}

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

int main(){
	int mountain[10];
	
	for(int i=0; i<=9; i++){
		cin >> mountain[i];
	}
	
	sort(mountain,mountain+10);
	
	cout << mountain[9] << endl;
	cout << mountain[8] << endl;
	cout << mountain[7] << endl;	
	
	return 0;
}

Measured memory_bytes: 0
N=int(input())
A=list(map(int,input().split()))
count=0
F=0
B=0
SUM=0



while F<N:
    while True:
        SUMtest=SUM+A[B]
        XORtest=SUM^A[B]

        if SUMtest==XORtest:
            if B==N-1:
                for i in range(F,N):
                    count=count+(N-i)
                F=N
                break
                
            else:
                B+=1
                SUM=SUMtest

        else:
            count=count+(B-F)
            SUM=SUM-A[F]
            F+=1
            break


print(count)

Measured memory_bytes: 24712
#include<cstdio>

char s[501][501];int n;

int main()
{
	int i,j;bool f;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%s",s[i]);

	for(i=0,f=true;i<n&&f;i++)
		for(j=0;j<n;j++)
			if(s[i][j]!='.')
			{ f=false;break; }
	if(f)return puts("-1"),0;

	for(i=0,f=true;i<n&&f;i++)
		for(j=0;j<n;j++)
			if(s[i][j]!='#')
			{ f=false;break; }
	if(f)return puts("0"),0;

	int c=0;
	for(j=0;j<n;j++)
	{
		for(i=0;i<n;i++)
			if(s[i][j]!='#')
				break;
		c+=i==n;
	}

	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
			if(s[i][j]!='#')
				break;
		if(j==n)return printf("%d\n",n-c),0;
	}

	int ans=0,d;
	for(i=0;i<n;i++)
	{
		for(j=d=0;j<n;j++)
			if(s[j][i]=='#')
				break;
		if(j==n)d=-1;
		for(j=0;j<n;j++)
			d+=s[i][j]=='#';
		if(d>ans)ans=d;
	}

	printf("%d\n",n*2-ans-c);
	return 0;
}

Measured memory_bytes: 384
# https://atcoder.jp/contests/abc141/submissions/7548484

n = int(input())
S = input()
N = [0]*n
j = 0
 
for i in range(n):
  while S[i:j] in S[j:n]:
    N[i] = j-i
    j += 1
    
print(max(N))


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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    while (b<=a && k>0) {
        b*=2;
        k--;
    }
    while (c<=b && k>0) {
        c*=2;
        k--;
    }
    if (a < b && b < c) cout << "Yes";
    else cout << "No";
}

Measured memory_bytes: 3652
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(void)
{
	int N[31]={0},a=0;
	for(int i=1;i<31;i++)
	{
		scanf("%d",&a);
		N[a]=1;
	}
	for(int i=1;i<31;i++)
	{
		if(N[i]!=1){printf("%d\n",i);}
	}
	return 0;
}
//前回記録31:37.770クリア


Measured memory_bytes: 3184
# coding:utf-8

import sys

input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


N = int(input())
A = inpl()
m = sum(A)/N
tmp = INF
min_num = A[0]
for b in A:
    if abs(b - m) < tmp:
        tmp = abs(b - m)
        min_num = b

print(A.index(min_num))


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
  
  int A, B;
  cin >> A >> B;

  int ans = A + B;

  if (ans <= A - B) { ans = A - B; }
  if (ans <= A * B) { ans = A * B; }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,n) for (int64_t i=0; i<(n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()
#define chmax(x,y) x=max(x,y)

const int inf=2e9+5;


int main(){
    int n; cin>>n;
    vector<vector<int>> f(n, vector<int>(10,0));
    rep(i,n){
        rep(j,10){
            cin>>f[i][j];
        }
    }
    vector<vector<int>> p(n, vector<int>(11,0));
    rep(i,n) rep(j,11) cin>>p[i][j];
    int ans=-inf;
    for(int i=1; i<1<<10; ++i){
        int karians=0;
        rep(j,n){
            int kari=0;
            rep(kk,10){
                if(f[j][kk]==1 && i>>kk&1){
                    kari++;
                }
            }
            karians+=p[j][kari];
        }
        ans=max(ans, karians);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3644
#include <stdio.h>
#include <string.h>
#include <math.h>

int main(void){
  int sx,sy,tx,ty,i;
  int a,b;
  char x[100001];
  scanf("%d %d %d %d",&sx,&sy,&tx,&ty);
  a=tx-sx; b=ty-sy;
  for(i=0;i<a;i++){
    x[i]='R';
  }
  for(i=a;i<a+b;i++){
    x[i]='U';
  }
  for(i=a+b;i<2*a+b;i++){
    x[i]='L';
  }
  for(i=2*a+b;i<2*(a+b);i++){
    x[i]='D';
  }
  x[2*(a+b)]='D';
  for(i=2*(a+b)+1;i<3*a+2*b+2;i++){
    x[i]='R';
  }
  for(i=3*a+2*b+2;i<3*a+3*b+3;i++){
    x[i]='U';
  }
  x[3*(a+b+1)]='L'; x[3*a+3*b+4]='U';
  for(i=3*a+3*b+5;i<4*a+3*b+6;i++){
    x[i]='L';
  }
  for(i=4*a+3*b+6;i<4*a+4*b+7;i++){
    x[i]='D';
  }
  x[4*a+4*b+7]='R';
  printf("%s",x);
  return 0;
}

Measured memory_bytes: 256
n,x,y=map(int,input().split())
x-=1
y-=1
inf=1<<30
d=[[inf]*n for _ in range(n)]
for i in range(n):
    for j in range(i+1,n):
        d[i][j]=min((j-i,abs(x-i)+1+abs(y-j),abs(y-i)+1+abs(x-j)))
from collections import Counter
c=Counter()
for i in range(n):
    c+=Counter(d[i])
for k in range(1,n):
    print(c[k])


Measured memory_bytes: 120284
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define black_tree tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define pair_black_tree tree<pair<ll,ll>,null_type,less<pair<ll,ll> >,rb_tree_tag,tree_order_statistics_node_update>
#define gp __gnu_pbds
#define INF 1000000000
#define MOD 1000000007
#define MAX 1000001
#define endl '\n'
#define ll long long
#define ld long double
#define lli long long int
#define ull unsigned long long
#define ulli unsigned long long int
#define pb push_back
#define pf push_front
#define ook order_of_key
#define fbo find_by_order
#define np next_permutation
#define mp make_pair
#define eb emplace_back
#define mae max_element
#define mie min_element
#define lb lower_bound 
#define ub upper_bound
#define bs binary_search
#define ff first
#define ss second
using namespace std;
using namespace gp;
ll n;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    cout<<360/__gcd(360LL,n);
}

Measured memory_bytes: 3600
#include <stdio.h>          // printf(), scanf()
#include <stdbool.h>

int
main(int argc, char **argv)
{
	int n;
	int i;

	while (true)
	{
		scanf("%d", &n);
		if (n == 0)
			break;

		unsigned long f = 2;
		int count = 0;
		for (i = 3; i <= n; ++i)
		{
			f = (f * i) % 100000000000000;
			while (f % 10 == 0)
			{
				f /= 10;
				count++;
			}
		}

		printf("%d\n", count);
	}

	return 0;
}

Measured memory_bytes: 600
#include <stdio.h>
int a[1000000];
long long int ans=0;
void mergesort(int l,int r){
	if(l==r)return;
	if(l==r-1){
		if(a[r]<a[l]){
			int temp;
			temp=a[l];
			a[l]=a[r];
			a[r]=temp;
			ans++;
		}
		return;
	}
	int mid=(l+r)/2,now=0,b[r-l+1];
	mergesort(l,mid-1);
	mergesort(mid,r);
	for(int i=0;i<=r-l;i++){
	if(a[l+i-now]<a[mid+now]){
		b[i]=a[i+l-now];
		if(i+l-now==mid-1){
			for(i++;i<=r-l;i++)b[i]=a[i+l];
		}
	}
	else{
		ans+=mid-i+now-l;
		b[i]=a[mid+now];
		now++;
		if(mid+now>r){
			for(i++;i<=r-l;i++){
				b[i]=a[i+l-now];
			}
		}
	}
	}
	for(int i=0;i<=r-l;i++)a[i+l]=b[i];
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	mergesort(0,n-1);
	printf("%lld\n",ans);
}

Measured memory_bytes: 5044
#include <bits/stdc++.h>
#define pb push_back
#define ll long long 
#define mp make_pair
#define si short int
#define speed ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pill pair<ll,ll>
#define f first
#define s second
#define pilc pair<ll,char>
#define all(a) (a).begin(),(a).end()
#define rep(s,e,step) for(int i = (s); i < (e) ; i += step)
#define vrep(s,e,step) for(int j = (s); j < (e) ; j += step)
#define ex exit(0) 
#define sz(a) (a).size()
#define triple pair<pill, ll>
#define pinode pair<node*, node*>
#define quadra pair<pill, pill>
using namespace std;

/*
 tips :
 Sqrt opt
 Binary search
 Try to find the easiest solution
 Recursiya
 FUCK YOU pishi kod akuratnee daun yobani
 sdohni v adu nahui blyat' y ub'uy tebya
 esli ti blyad' budesh pisat' kod gryaznim
 to ya tebya v rot viebu
*/

const ll N = 2e5 + 10;
const ll big = 1e18;
const ll shift = 1000;
const ll block = 500;
const long long mod = 1e9 + 7;

ll dp[N];

int main() {	
	ll n;
	cin >> n;
	dp[0] = 1;
	for(int i = 1; i <= n; i++) {
	 	for(int j = i; j >= 3; j--) {
	 		dp[i] = (dp[i] + dp[i - j]) % mod;
	 	}
	}
	cout << dp[n];
}             

/*

*/          

Measured memory_bytes: 3636
n = int(input())
a = []
b = n
d = 0
for i in range(2, int(n**0.5)+2):
    if b%i == 0:
        c = 0
        while b%i == 0:
            c += 1
            b //= i
        a.append(c)
if b != 1:
    a.append(1)
for i in range(len(a)):
    for j in range(1, 100):
        if a[i] >= j:
            d += 1
            a[i] -= j
        else:
            break;
print(d)

Measured memory_bytes: 9460
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define infin ll (pow(10,9)+7);
typedef unsigned int ui;
int main()
{
    int n;
    cin>>n;
    double p[n+1][n+1];
    double given[n+1];
    for(int i=1;i<=n;i++)
        cin>>given[i];
    p[1][0]=1-given[1];
    p[1][1]=given[1];
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if (j==0)
               p[i][j]=p[i-1][j]*(1-given[i]);
            else if(i-1<j)
              p[i][j]=p[i-1][j-1]*given[i];

            else
            {
                p[i][j]=p[i-1][j]*(1-given[i])+(p[i-1][j-1]*given[i]);
            }
            
        }
    }
    // for(int i=1;i<=n;i++)
    // {
    //     for(int j=0;j<=i;j++)
    //     cout<<i<<" "<<j<<"  "<<p[i][j]<<endl;
    // }
    double answer=0.0;
    for(int i=floor(n/2)+1;i<=n;i++)
    {
        answer=answer+p[n][i];
    }   
    cout<<setprecision(10)<<answer<<endl;
}

Measured memory_bytes: 49864
from collections import deque

n,m = map(int,input().split())

adj = [[] for i in range(n+1)]
dist = [-1]*(n+1)

for i in range(m):
    a,b = map(int,input().split())
    adj[a].append(b)
    adj[b].append(a)

d = deque([[1,0]])

while len(d) > 0:
    x,y = d.popleft()
    if dist[x] != -1:
        continue
    
    dist[x] = y
    
    for n in adj[x]:
        if dist[n] == -1:
            d.append([n,x])

print("Yes")

for i in dist[2:]:
    print(i)

Measured memory_bytes: 41732
n=input()
print(n+': ',end='')
n=int(n);d=2
while n%d==0 and n>3:
    print(d,end=' ')
    n//=d
d+=1
m=n//d
while m>=d:
    if(n%d==0):
        print(d,end=' ')
        n=m
    else:d+=2
    m=n//d
print(n)




Measured memory_bytes: 5592
def wantp(n):

    l = []
    while p[n] != n:
        l.append(n)
        n = p[n]

    for i in l:
        p[i] = n

    return n



N,M = map(int,input().split())

dic = {}

for i in range(N):

    kl = list(map(int,input().split()))

    for j in range(kl[0]):

        j += 1
        if kl[j] not in dic:
            dic[kl[j]] = []

        dic[kl[j]].append(i)

p = [i for i in range(N)]
rank = [1] * N

for i in dic:

    if i not in dic:
        continue

    for j in range(len(dic[i]) - 1):

        a = dic[i][j]
        b = dic[i][j+1]

        ap = wantp(a)
        bp = wantp(b)

        if ap != bp:

            if rank[ap] > rank[bp]:
                p[bp] = ap
            elif rank[ap] < rank[bp]:
                p[ap] = bp
            else:
                p[ap] = bp
                rank[bp] += 1

n = 0
for i in range(N):
    if i == wantp(p[i]):
        n += 1

#print (p,dic)
if n == 1:
    print ("YES")
else:
    print ("NO")


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

int main() {
  int n, k;
  cin >> n >> k;
  int num = 1;
  
  for (int i = 0; i < n; i++) {
    if (num < k)
      num *= 2;
    else
      num += k;
  }
  
  cout << num << endl;
}


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

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int) a.size()
#define ALL(a) a.begin(),a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

string minShift(string s)
{
	string res = s;
	FOR (it, 0, SZ(s))
	{
		s += s[0];
		s.erase(s.begin());
		res = min(res, s);
	}
	return res;
}

string getString(vector<string> v)
{
	string res;
	FOR (i, 0, SZ(v))
	{
		res += v[i];
	}
	return res;
}

string solveSmall(int a, int b, int c, string A, string B, string C)
{
	vector<string> v;
	FOR (i, 0, a)
	{
		v.PB(A);
	}

	FOR (i, 0, b)
	{
		v.PB(B);
	}

	FOR (i, 0, c)
	{
		v.PB(C);
	}
	sort(ALL(v));

	string res = getString(v);

	do
	{
		res = max(res, minShift(getString(v)));
	}while(next_permutation(ALL(v)));

	return res;

}

string getString(int cnt, string s)
{
	string res;
	FOR (i, 0, cnt)
	{
		res += s;
	}
	return res;
}

string solveLarge(int a, int b, int c, string A, string B, string C)
{
	if (a + b + c <= 3) return solveSmall(a, b, c, A, B, C);

	if (a == 0)
	{
		a = b;
		A = B;
		b = c;
		B = C;
		c = 0;
		C = "";
	}

	if (b == 0)
	{
		b = c;
		B = C;
		c = 0;
		C = "";
	}

	if (b == 0 && c == 0)
	{
		return getString(a, A);
	}

	if (c >= a)
	{
		c -= a;
		A += C;
		return solveLarge(a, b, c, A, B, C);
	}

	C = A + C;
	a -= c;

	if (b >= a)
	{
		A += B;
		b -= a;
		swap(b, c);
		swap(B, C);
	}
	else
	{
		a -= b;
		B = A + B;
	}

	return solveLarge(a, b, c, A, B, C);



}

int main()
{
	//freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);

	int x, y, z;

	cin>>x>>y>>z;
	string res = solveLarge(x, y, z, "a", "b", "c");
	cout<<res<<endl;

//	FOR (a, 0, 5)
//	{
//		FOR (b, 0, 5)
//		{
//			FOR (c, 0, 5)
//			{
//				string r = solveSmall(a, b, c, "a", "b", "c");
//				string s = solveLarge(a, b, c, "a", "b", "c");
//				cout<<r<<endl<<s<<endl;
//				if (r != s)
//				{
//					cout<<"!! "<<endl;
//					cout<<a<<' '<<b<<' '<<c<<endl;
//					throw -1;
//				}
//			}
//		}
//	}
//
//	cout<<"Done"<<endl;

}


Measured memory_bytes: 256
n,m = map(int,input().split())
l = [list(map(int,input().split())) for i in range(m)]

left = [i[0] for i in l]
right = [i[1] for i in l]

max_left = max(left)
min_right = min(right)

ans = min_right - max_left

if ans < 0:
    print(0)

else:
    print(ans+1)

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

using namespace std;

#define fore(i, s, e) for(int i = s; i < e; i++)

const int N = 300;
const int W = 1e5 + 100;

typedef long long ll;

int n, w;
ll dp[N][W];

ll ww[N], v[N];
int main() {
    cin >> n >> w;
    
    fore(i, 1, n + 1) {
        cin >> ww[i] >> v[i];
    }

    fore(j, 0, w + 1) dp[0][j] = 0;
    fore(i, 0, n + 1) dp[i][0] = 0;

    fore(i, 1, n + 1) {
        fore(j, 1, w + 1) {
            dp[i][j] = dp[i - 1][j];
            if(ww[i] <= j) dp[i][j] = max(dp[i][j], v[i] + dp[i - 1][j - ww[i]]);
        } 
    }
    cout << dp[n][w] << endl;
}

Measured memory_bytes: 80128
(function main(){
  const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
  lines.shift();
  const arr = lines.shift().split(' ').map(Number);
  buildMaxHeap(arr);
  console.log(arr.reduce((s, e) => s += ` ${e}`, ''));
})();

function buildMaxHeap(arr) {
  const n = arr.length;
  const maxHeapify = (i) => {
    let left, right, largest;
    left = 2 * i + 1;
    right = 2 * i + 2;
    largest = left < n && arr[left] > arr[i] ? left : i;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest != i) {
      arr[largest] = [arr[i], arr[i] = arr[largest]][0];
      maxHeapify(largest);
    }
  };

  for (let i = Math.floor(n / 2); i >= 0; i--) maxHeapify(i);
}



Measured memory_bytes: 140156
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>

using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;
typedef pair<ll, ll> PLL;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

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

  cin >> n;

  ll x = 1, y = 1;

  REP(i, n) {
    int t, a;
    cin >> t >> a;

    ll left = 0, right = LLINF /max(a, t);
    while(right - left > 1) {
      ll mid = (right + left) / 2;
      if(mid * t >= x && mid * a >= y) right = mid;
      else left = mid;
    }

    x = right * t; y = right * a;
  }

  cout << (x + y) << endl;
}


Measured memory_bytes: 256
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n = I()
    span = [None for _ in range(n)]
    for i in range(n):
        x, l = LI()
        span[i] = [x-l, x+l]
    span.sort(key=lambda x: x[1])
    choice = [[-float("inf"),-float("inf")]]
    for each_span in span:
        if choice[-1][1] <= each_span[0]:
            choice.append(each_span)
    
    ans = len(choice)-1
    print(ans)
main()


Measured memory_bytes: 95052
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <deque>
#include <utility>

int main(){
  std::string s;
  std::cin >> s;
  bool find=false;
  int a, b;
  int n=s.length();
  for (int i=0; i<n-1; i++){
    if (s[i]==s[i+1]){
      find=true;
      a=i;
      b=i+1;
      break;
    }
  }
  for (int i=0; i<n-2; i++){
    if (s[i]==s[i+2]){
      find = true;
      a=i;
      b=i+2;
      break;
    }
  }
  if (find){
    printf("%d %d\n", a+1, b+1);
  } else {
    printf("-1 -1\n");
  }
  return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

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

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

	ll sum = 0;
	rep(i, n) {
		int a, b;
		char c;

		cin >> a >> c >> b;

		if(c == '(') sum += b;
		else sum -= b;

		if(sum == 0) cout << "Yes" << endl;
		else cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define inf 1000000007
#define LINF 100000000000000007LL
#define ll long long
using namespace std;
signed main(){
	int n;
	cin>>n;
	vector<int> vec;
	int cur = -1;
	for(int i=40;i>=1;i--){
		if( n >= ( 1LL<<i ) - 1 ){	
			for(int j = 1; j <= i; j ++){
				vec.pb(j);
			}
			n -= ( 1LL<< i ) -1;
			cur = i+1;
			break;
		}
	}
	for(int i=40;i>=0;i--){
		if( n >= (1LL<<i) ){
			vec.insert( vec.begin()+i, cur );
			cur++;
			n -= 1LL<<i;
		}
	}
	for(int i=1;i<cur;i++){
		vec.pb(i);
	}
	cout<<vec.size()<<endl;
	for(int i=0;i<vec.size();i++)cout<<vec[i]<<" "; cout<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long n,t,b1[200005],f[200005],max1,tot1,tot2;
struct hzy{
	long long a,b;
}b2[200005];
bool mycmp(hzy a,hzy b){
	return a.a*(b.b+1)>b.a*(a.b+1);
}
int main(){
	scanf("%lld%lld",&n,&t);
	for(long long i=1;i<=n;i++){
		long long x,y;
		scanf("%lld%lld",&x,&y);
		if(x==0){
			b1[++tot1]=y+1;
		}
		else{
			b2[++tot2]=(hzy){x,y};
		}
	}
	sort(b1+1,b1+tot1+1);
	sort(b2+1,b2+tot2+1,mycmp);
	for(int i=1;i<=35;i++){
		f[i]=t+1;
	}
	for(long long i=1;i<=tot2;i++){
		for(long long j=35;j>=1;j--){
			f[j]=min(f[j],(f[j-1]+1)*(b2[i].a+1)+b2[i].b);
		}
	}
	for(long long i=1;i<=tot1;i++){
		b1[i]+=b1[i-1];
	}
	for(long long i=0;i<=35;i++){
		if(f[i]>t)continue;
		long long x=0;
		if(tot1) x=upper_bound(b1+1,b1+tot1+1,t-f[i])-(b1+1);
		max1=max(max1,i+x);
	}
	printf("%lld\n",max1);
	return 0;
}


Measured memory_bytes: 6812
#include <stdio.h>

int js(int n, int k) {
  int p=0,st=0,cnt=0,K=k,N=n;
  int tmp[n];
  for(int i=0;i<n;i++){tmp[i]=0;}
  
  while(p<=n-2){
    cnt=0;
    int c=0;
    if(k%N==0)K=N;else K=k%N;
    do{
      if(tmp[(st+c)%n]==0)cnt++;
      if(cnt==K)break;
      c++;
    }while(cnt<=K);
    
    tmp[(st+c)%n]=1;
    st=(st+c)%n;
    p++;N--;
  }
  int ret=0;
  for(int i=0;i<n;i++){if(tmp[i]==0)ret=i+1;}
  return ret;
}

int main(void){

int n=1,m=1;

while(n!=0 && m!=0){
scanf("%d %d",&n,&m);
if(n==0 && m==0)break;
printf("%d\n",js(n,m));

}

return 0;
}



Measured memory_bytes: 2052
#include <bits/stdc++.h>
using namespace std;
struct edge {
    int to;     // 辺の行き先
    int weight; // 辺の重み
    edge(int t, int w) : to(t), weight(w) { }
};
using Graph = vector<vector<int>>;
using dou =long double;
string Yes="Yes";
string YES="YES";
string NO="NO";
string No="No";
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; }
#define rep(i, n)         for(int i = 0; i < (int)(n); i++)
#define brep(n)           for(int bit=0;bit<(1<<n);bit++)
#define erep(i,container) for (auto i : container)
#define irep(i, n)        for(int i = n-1; i >= (int)0; i--)
#define rrep(i,m,n) for(int i = m; i < (int)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define all(x) (x).begin(),(x).end()
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define res resize
#define as assign
#define fi first
#define se second
#define itn int
#define mp make_pair
#define sum(a) accumulate(all(a),0)
#define keta fixed<<setprecision
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<t>(n,a)));
#define vvvvector(name,t,k,l,m,n,a) vector<vector<vector<vector<t> > > > name(k,vector<vector<vector<t> > >(l, vector<vector<t> >(m, vector<t>(n,a)) ));
 
typedef long long ll;
const int INF = 2000000000;
const ll INF64 = 922337203685477580ll;
const int mod = 1000000007ll;
const ll  MOD = 1000000007LL;
const double pi=3.1415926535897932384626;

int main(){
    string s;
    std::cin >> s;
    int c=0,cc=0;
    int n=s.size();
    rep(i,n){
        if(i%2==0){
            if(s[i]=='0')c++;
        }
        else{
            if(s[i]=='1')c++;   
        } 
    }
    rep(i,n){
        if(i%2==0){
            if(s[i]=='1')cc++;
        }
        else{
            if(s[i]=='0')cc++;   
        } 
    }
    
    std::cout << min(cc,c) << std::endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <cmath>

using namespace std;

int main(int argc, char *argv[]) {
  string s;
  while (cin >> s) {
    int loc = 0, res = 0;
    while ((loc = s.find("JOI", loc)) != string::npos) {
      res++;
      loc += 3;
    }
    cout << res << endl;
    loc = 0;
    res = 0;
    while ((loc = s.find("IOI", loc)) != string::npos) {
      res++;
      loc += 2;
    }
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 1200
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		String input = sc.next();
		String[] inputSplit = input.split("");
		for (String string : inputSplit) {
			if (string.equals("?")) {
				System.out.print("D");
			} else {
				System.out.print(string);
			}
		}
	}

}


Measured memory_bytes: 68396
s = input()
k = int(input())
if s == '1' * len(s):
  print(1)
  exit()
for i in range(len(s)):
  if s[i] != '1':
    idx = i
    num = s[i]
    break
if idx >= k:
  print(1)
else:
  print(num)

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

ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}

ll combi(ll n, ll k) {
	assert(k >= 0 && k <= n);
	k = min(k, n - k);
	ll res = 1;
	for (int i = 1; i <= k; i++) {
		res = res * (n - k + i) / i;
	}
	return res;
}

int main()
{
	int N, A, B;
	cin >> N >> A >> B;
	vector<long long> v(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	ll sum = 0, cnt = 0, res = 0;
	ll r1 = 0, r2 = 1;
	for (int i = 0; i < A - 1; i++) {
		sum += v[N - i - 1];
		cnt++;
	}
	for (int i = A - 1; i < B; i++) {
		sum += v[N - i - 1];
		cnt++;
		if (sum * r2 > cnt * r1) {
			res = 0;
			r1 = sum;
			r2 = cnt;
			ll tmp = gcd(r1, r2);
			sum /= tmp;
			cnt /= tmp;
		}
		if (sum * r2 == cnt * r1) {
			res += combi(count(v.begin(), v.end(), v[N - i - 1]), (upper_bound(v.begin(), v.end(), v[N - i - 1]) - v.begin()) - (N - i - 1));
		}
	}
	cout << fixed << setprecision(7) << (long double)r1 / r2 << endl;
	cout << (long long)res << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main(){
    char S[3]; int count{};
    for (auto& r : S) {
        std::cin >> r;
        if (r == 'R') ++count;
    }

    if (S[0] == 'R' && S[1] == 'S' && S[2] == 'R') std::cout << 1 << std::endl;
    else std::cout << count << std::endl;
}

Measured memory_bytes: 3536
n, k = list(map(int, input().split()))
a_list = list(map(int, input().split()))

START = 1
# 訪れたタイミング
town_with_i = {START: 0}
# 現在地
current = START
# 既に訪れたことある街(巡回の判定に使う)
known_towns = set([START])
i = 0
for _ in range(k):
    i += 1
    # 現在地
    current = a_list[current - 1]

    # 既に来たことがあるということは巡回している
    if current in known_towns:
        break

    # メモ
    town_with_i[current] = i
    known_towns.add(current)

# 巡回までのステップ数
first_step = town_with_i[current]
# 1周するのに必要なステップ数
r = i - town_with_i[current]

# print(town_with_i)
# print(current)
# print(i)
# print(r)

loop_num = (k - first_step) % r if r > 0 else (k - first_step)

for i in range(loop_num):
    current = a_list[current - 1]

print(current)


Measured memory_bytes: 40960
#include<iostream>
#include<set>
#include<vector>
#include<cmath>
#include<list>
#include<algorithm>

#define ll long long

using namespace std;

int main() {
	ll a, b, n;
	ll fx;
	ll res = 0;
	cin >> a >> b >> n;
/*	for (int x = 0; x <= (n<b?n:b); ++x) {
		cout << "x = " << x << ends;
		fx = floor(a * x / b) - a * floor(x / b);
		cout << "f(x) = " << fx << endl;
		res = max(res, fx);
	}
	*/
	if (n < b) 
	fx = floor(a * n / b) - a * floor(n / b);
	else 
		fx = floor(a * (b-1) / b) - a * floor((b-1) / b);
	cout << fx << endl;
	return 0; 
}

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

using namespace std;

int main(void)
{
  string s;
  string tmp;
  int j=0;

  cin>>s;

  reverse(s.begin(), s.end());
  while(1)
  {
    if(s.substr(0,5) == "maerd")
    {
      s.erase(0,5);
    }
    else if(s.substr(0,7) == "remaerd")
    {
      s.erase(0,7);
    }
    else if(s.substr(0,5) == "esare")
    {
      s.erase(0,5);
    }
    else if(s.substr(0,6) == "resare")
    {
      s.erase(0,6);
    }
    else
    {
      cout<<"NO"<<endl;
      return 0;
    } 
    if(s.size() == 0)
    {
      cout<<"YES"<<endl;
      return 0;
    }
   }
  return 0;
}


Measured memory_bytes: 512
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])



#UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m = inpm()
AB = inplt(m)

uf = UnionFind(n)
for a,b in AB:
    uf.union(a-1,b-1)

print(-min(uf.parents))

Measured memory_bytes: 42108
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;
const int INF=1e9;
using namespace std;

int main(){
    string s;
    cin>>s;
    cout<<s[0]<<s.size()-2<<s.back()<<endl;
}


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

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define debug(x) cout << #x << ": " << x << endl
using ll = long long;
//#define int ll

//**********

signed main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int h, w, d;
    cin >> h >> w >> d;
    int a[h][w];

    int num = h*w;
    int x[num+1];
    x[0] = 0;
    int y[num+1];
    y[0] = 0;
    
    int temp;
    REP(i,h){
    REP(j,w){
        cin >> temp;
        a[i][j] = temp;
        x[temp] = i;
        y[temp] = j;
    }}
    int q;
    cin >> q;
    int l,r;

    int memo[num+1];
    REP(i,d+1) memo[i]=0;
    FOR(i,d+1,num+1){
    memo[i]= memo[i-d] + abs(x[i]-x[i-d])+abs(y[i]-y[i-d]);
    }
    REP(i,q){ 
        cin >> l >> r;
        printf("%d\n",memo[r]-memo[l]);
    }

    return 0;
    
}



Measured memory_bytes: 2560
# -*- coding: utf-8 -*-
import numpy as np

N = int(input())
A = [input() for _ in range(N)]

def count(a):
  if '.' in a:
    c = a.split('.')
    n = int(c[0]+c[1])
    count2 = 9 - len(c[1])
    count5 = 9 - len(c[1])
  else:
    n = int(a)
    count2 = 9
    count5 = 9
  while n%2 == 0 and count2<18:
    n //= 2
    count2 += 1
  while n%5 == 0 and count5<18:
    n //= 5
    count5 += 1
  return count2,count5

Z = np.zeros((19,19), dtype=np.int64)
answer = 0
for a in A:
  c2,c5 = count(a)
  if max(c2,c5)>18 or min(c2,c5)<0:
    print(a,c2,c5)
  answer += Z[18-c2,18-c5]
  Z[:c2+1,:c5+1] += 1

print(answer)

Measured memory_bytes: 41160
using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.IO;
using System.Text;
using System.Diagnostics;

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        int[][] csf = Enumerable.Repeat(0, n - 1).Select(_ => Console.ReadLine().Split(' ').Select(int.Parse).ToArray()).ToArray();
        
        for(int i = 0; i < n; i++)
        {
            long time = 0;
            for (int j = i; j < n - 1; j++)
            {
                if (time < csf[j][1])
                {
                    time = csf[j][1];
                }
                long tmp = time / csf[j][1];
                time = tmp * csf[j][1] + ((time - tmp * csf[j][1] + csf[j][2] - 1) / csf[j][2]) * csf[j][2];
                time += csf[j][0];
            }
            Console.WriteLine(time);
        }
    }
}

Measured memory_bytes: 13524
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
#include <limits.h>
using namespace std;
vector<int> v[101];
int d[101];
queue<int> q;
bool flag[101];
int main(){
	int n, u, k; scanf("%d", &n);
	for (int i = 0; i < n; ++i){
		scanf("%d %d", &u, &k);
		for (int j = 0; j < k; ++j){
			int tmp; scanf("%d", &tmp);
			v[u].push_back(tmp);
		}
	}
	memset(d, -1, sizeof(d));
	d[1] = 0;
	q.push(1); flag[1] = true;
	while (!q.empty()){
		int m = q.front(); q.pop();
		for (int i = 0; i < v[m].size(); ++i){
			int tmp = v[m][i];
			if (!flag[tmp]){
				flag[tmp] = true;
				d[tmp]=d[m]+1;
				q.push(tmp);
			}
		}
	}
	for (int i = 1; i <= n; ++i){
		cout << i << ' ' << d[i] << '\n';
	}
}

Measured memory_bytes: 1232
#include <stdio.h>
#include <string>
    #include <iostream>
    #include <cstdio>
    using namespace std;
    int main(){
      char m[4];
      int d = 0;
      cin >> m;
      if(m[0] == '1') d += 1;
      if(m[1] == '1') d += 1;
      if(m[2] == '1') d += 1;
      cout << d << endl;
      return 0;
    }

Measured memory_bytes: 256
N = int(input())
S = input()

a = 0
i = 0
j = 1

while j<N:
    if S[i:j] in S[j:]:
        a = max(a, len(S[i:j]))
        j += 1
    else:
        i += 1
    if i==j:
        i += 1
        j += 2

print(a)


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define Would
#define you
#define please

int main() {

	int N, x, a[100];
	cin >> N >> x;
	long long goukei = 0;
	rep(i, N) {
		cin >> a[i];
		goukei += a[i];
	}
	sort(a, a + N);

	if (x > goukei) {
		cout << N - 1 << "\n";
	}
	else {
		int kotae = 0;
		rep(i, N) {
			x -= a[i];
			if (x >= 0) kotae++;
			else break;
		}
		cout << kotae << "\n";
	}
	Would you please return 0;
}

Measured memory_bytes: 256