akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

constexpr int inf = 1e9;

void warshall_floyd(vector<vector<int>>& d){
	
	for(int k = 0; k < d.size(); k++){
		for(int i = 0; i < d.size(); i++){
			for(int j = 0; j < d.size(); j++){
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}

int main(){
	
	while(true){
		int n, m, c, s, g;
		vector<vector<vector<int>>> d;
		vector<int> p;
		
		cin>>n>>m>>c>>s>>g;
		
		if(!n) break;
		
		s--, g--;
		
		d.resize(c+1, vector<vector<int>>(n, vector<int>(n, inf)));
		p.resize(c);
		
		for(int i = 0; i < m; i++){
			int x, y, D, c;
			
			cin>>x>>y>>D>>c;
			
			x--, y--, c--;
			
			d[c][y][x] = d[c][x][y] = min(d[c][x][y], D);
		}
		
		
		for(int i = 0; i < c; i++){
			cin>>p[i];
		}
	
		for(int i = 0; i < c; i++){
			vector<int> q(p[i]+1), r(p[i]), v((n+1)*200);
			
			for(int j = 1; j < p[i]; j++){
				cin>>q[j];
			}
			
			q.back() = inf;
			
			for(int j = 0; j < p[i]; j++){
				cin>>r[j];
				if(q[j]+1 < v.size()) v[q[j]+1] += r[j];
				if(q[j+1]+1 < v.size()) v[q[j+1]+1] -= r[j];
			}
			
			for(int j = 1; j < v.size(); j++){
				v[j] += v[j-1];
			}
			
			for(int j = 1; j < v.size(); j++){
				v[j] += v[j-1];
			}
			
			warshall_floyd(d[i]);
			
			for(int j = 0; j < n; j++){
				for(int k = 0; k < n; k++){
					if(d[i][j][k] < inf) d[i][j][k] = v[d[i][j][k]];
				}
			}
		}
		
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				for(int k = 0; k < c; k++){
					d[c][j][i] = d[c][i][j] = min(d[c][i][j], d[k][i][j]);
				}
			}
		}
		
		warshall_floyd(d[c]);
		
		if(d[c][s][g] >= inf) cout<<-1<<endl;
		else cout<<d[c][s][g]<<endl;
	}
}


Measured memory_bytes: 4036
#include<iostream>
#include<vector>
#include <cmath>
#include <map>
#include <set>
#include <algorithm>
#include <string>
using namespace std;
int main(void){
  int N, M, a, b;
  cin >> N >> M;
  vector<set<int>> v(N + 1);
  for (int i = 0; i != M; ++i) {
    cin >> a >> b;
    v[a].insert(b);
    v[b].insert(a);
  }
 
  cout << (any_of(begin(v[1]), end(v[1]), [&](int s) { return v[s].count(N); })
               ? "POSSIBLE"
               : "IMPOSSIBLE")
       << endl;
}

Measured memory_bytes: 31508
/*

                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                    prayer
*/

// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(long long i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) {rep(_,v.size())cout<<" "<<v[_];cout<<endl;}
#define show2d(v) {rep(__,v.size())show1d(v[__]);}
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
#define yes cout<<"Yes\n"
#define no cout<<"No\n"


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

	int n;
	cin>>n;
	vvi in(n,vi(2));
	rep(i,n)rep(j,2)cin>>in[i][j];

	int out=n;
	rep(i,n)rep(j,n){
		int x=in[i][0]-in[j][0],y=in[i][1]-in[j][1];
		if(!x&&!y)continue;
		int c=n;
		rep(k,n)rep(l,n)if(in[k][0]-in[l][0]==x&&in[k][1]-in[l][1]==y)
			c--;
		cmin(out,c);
	}
	cout<<out<<endl;
}


Measured memory_bytes: 256
package main

import "fmt"

func main() {
    var n int
    var s string
    fmt.Scan(&n, &s)

    r_cnt := 0
    b_cnt := 0

    for i := 0; i < n; i++ {
        if s[i:i+1] == "R" {
            r_cnt++
        } else {
            b_cnt++
        }
    }
    if r_cnt > b_cnt {
        fmt.Println("Yes")
    } else {
        fmt.Println("No")
    }
}

Measured memory_bytes: 512
#include<stdio.h>

int main(void)
{
   int a,b,c,k,x;
   x=0;
   scanf("%d%d%d%d", &a, &b, &c, &k);

   while(k>0){
      if(a>0)       {while((a>0)&&(k>0)) {a--; x++; k--;}}
      else if(b>0)  {while((b>0)&&(k>0)) {b--; k--;}}
      else if(c>0)  {while((c>0)&&(k>0)) {x--; c--; k--;}}
   }
   printf("%d\n",x);
   return 0;
}


Measured memory_bytes: 1732
<?php
$input = fgets(STDIN); 
$input_array = str_split( $input);
$ans="";
foreach($input_array as $i => $char){

// if($char==="?"&&($input_array[$i-1]==="P")){

//     $ans = $ans+"D";

// }elseif($char==="?"&&($input_array[$i-1]==="D")){

//     $ans = $ans+$char;
if($char==="?"){
    $ans = $ans."D";
}else{
    $ans = $ans.$char;
}

}
echo $ans;

Measured memory_bytes: 29436
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    int A, B, m;
    cin >> A >> B >> m;
    vector<int> a(A), b(B);
    rep(i, A)cin >> a[i];
    rep(i, B)cin >> b[i];
    ll ans = *min_element(all(a)) + *min_element(all(b));
    rep(i, m){
        int x, y, c;
        cin >> x >> y >> c;
        x--; y--;
        ll now = a[x] + b[y] - c;
        ans = min(ans, now);
    }
    cout << ans << endl;
}   


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

using namespace std;

int main()
{
    double S, x, h;
 
    while (cin >> x >> h, (x != 0 || h != 0)) {
        S = (sqrt(h * h + x * x / 4) * 2 + x) * x;
        printf("%.6f\n" ,S);
    }
    return 0;
}

Measured memory_bytes: 3108
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <chrono>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef double db;

#define fr first
#define sc second
#define pb push_back
#define rep(i,x) for(ll i=0;i<x;i++)
#define rep1(i,x) for(ll i=1;i<=x;i++)
#define rrep(i,x) for(ll i=x-1;i>=0;i--)
#define rrep1(i,x) for(ll i=x;i>0;i--)
ll N,A,B,x[100000];
ll dp[100000];
int main()
{
	cin>>N>>A>>B;
	rep(i,N){
		cin>>x[i];
	}
	dp[0]=0;
	rep(i,N-1){
		dp[i+1]=dp[i]+min(B,A*(x[i+1]-x[i]));
	}
	
	cout<<dp[N-1]<<endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <cstdint>
#include <sys/time.h>

typedef std::int_fast32_t  s32;
typedef std::uint_fast32_t u32;
typedef std::int_fast64_t  s64;
typedef std::uint_fast64_t u64;

typedef std::pair<int, int> P;

int main(void) {

  for(;;) {
    int W, H;
    std::cin >> W >> H;
    if( W == 0 and H == 0 ) break;
    
    std::string str[32];
    for(int i = 0; i < H; ++i) {
      std::cin >> str[i];
    }

    P begin;
    for(int i = 0; i < H; ++i) {
      for(int j = 0; j < W; ++j) {
        if( str[i][j] == '@' ) {
          begin = P(i, j);
          str[i][j] = '.';
        }
      }
    }
    
    std::queue<P> q;
    q.push(begin);
    while( not q.empty() ) {
      P p = q.front(); q.pop();
      if( not ( 0 <= p.first and p.first < H and 0 <= p.second and p.second < W ) ) continue;
      if( str[p.first][p.second] != '.' ) continue; 

      str[p.first][p.second] = '*';

      int dx[4] = {1, 0, -1, 0};
      int dy[4] = {0, 1, 0, -1};
      for(int i = 0; i < 4; ++i) {
        q.push( P(p.first + dx[i], p.second + dy[i]) );
      }
    }

    int res = 0;
    for(int i = 0; i < H; ++i) {
      for(int j = 0; j < W; ++j) {
        if( str[i][j] == '*' ) {
          res += 1;
        }
      }
    }

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

Measured memory_bytes: 1232
import sys

# sys.stdin = open('d1.in')


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


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def solve(n, r):
    for a0 in range(2):
        for a1 in range(2):
            a = [a0, a1] + [-1] * (n - 2)
            for i in range(2, n):
                if r[i - 1] == 'o':
                    t = a[i - 2]
                else:
                    t = 1 - a[i - 2]
                if a[i - 1] == 1:
                    t = 1 - t
                a[i] = t

            ok = True
            for i in range(-1, n - 1):
                if a[i - 1] != a[i + 1]:
                    s = 1
                else:
                    s = 0
                if a[i] == 1:
                    s = 1 - s
                if s == 1:
                    expected = 'x'
                else:
                    expected = 'o'
                ok &= r[i] == expected
            if ok:
                l = map(lambda j: 'SW'[j], a)
                res = ''.join(l)
                return res
    return -1


def main():
    n = read_int()
    r = read_str()
    res = solve(n, r)
    print(res)


main()


Measured memory_bytes: 5588
L,R,d=map(int,input().split())
if d==1:
    print(R-L+1)
else:
    G=0
    A=0
    for i in range(0,100):
        i=i+1
        G=d*i
        if G>=L:
            if G<=R:
                A=A+1
            else:
                print(A)
                break
            
            
                


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

#define pb push_back
#define mp make_pair

typedef long long LL;
typedef pair<int,int> pii;

int a, x;

int main(){
	a = 0;
	for(int i=0; i<5; i++){
		scanf("%d", &x);
		a += x;
	}
	printf("%d\n", 15 - a);
	return 0;
}

Measured memory_bytes: 3680
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
using namespace std;

int main(){

    int N;
    cin >> N;

    vector<int> c(N);
    vector<int> s(N);
    vector<int> f(N);

    for(int i = 0; i < N - 1; i++){
        cin >> c[i] >> s[i] >> f[i];
    }

    //vector<long long> time_need(N); //駅iから駅Nに到達する時間
    //time_need[N-1] = 0;
    /*
    for(i = N-2; i>= 0; i--){
        time_need[i] = time_need[i+1] + c[i+1];
    }
    */

   for(int i_start = 0; i_start < N - 1; i_start++){
       int time = 0;
       for(int i_station = i_start; i_station < N - 1; i_station++){
           if(time < s[i_station]){
               time = s[i_station];
            }
            if(time % f[i_station] != 0){
                time = time + (f[i_station] - time % f[i_station]);
            }
            time = time + c[i_station];
       }
       cout << time << endl;
   }
    cout << 0 << endl;

}

Measured memory_bytes: 256
n,m = map(int,input().split())
a = [input() for _ in range(n)]
b = [input() for _ in range(m)]
for i in range(n-m+1):
    for j in range(n-m+1):
        cnt = 0
        for k in range(m):
            if a[i+k][j:j+m] == b[k]:
                cnt += 1
            if cnt == m:
                print("Yes")
                exit()
print("No")

Measured memory_bytes: 9060
#include<bits/stdc++.h>
using namespace std;
int n,A[9],B[9],arr[9];
int temp=0,cnta=0,cntb=0,flag1,flag2;
void findPermutations(int a[], int n)
{
    sort(a, a + n);
    do {
    	flag1=flag2=0;
    	temp++;
		for(int i=0;i<n;i++){
			if(a[i]!=A[i]){
				flag1=1;
				break;
			}
		}
		for(int i=0;i<n;i++){
			if(a[i]!=B[i]){
				flag2=1;
				break;
			}
		}
		if(!flag1)cnta=temp;
		if(!flag2)cntb=temp;
    } while (next_permutation(a, a + n));
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++)arr[i]=i+1;
	for(int i=0;i<n;i++)cin>>A[i];
	for(int i=0;i<n;i++)cin>>B[i];
	findPermutations(arr, n);
	cout<<abs(cnta-cntb);
	return 0;
}


Measured memory_bytes: 256
C[6],F[6][6][6][6][6];T="RYBMGC";s[2],i,*p,r,m;void R(a,b,c,d){int t;t=C[a];C[a]=C[b];C[b]=C[c];C[c]=C[d];C[d]=t;}main(n){for(;scanf("%d",&n),n;printf("%d\n",r))for(memset(F,r=0,31104);n--;*p=1){for(i=6;i--;C[i]=strchr(T,*s&127)-T)scanf("%s",s);for(;!C[1]|!C[4];)R(1,2,4,3);for(;*C;)R(0,2,5,3);for(m=i=1;++i<5;)C[i]<C[m]?m=i:0;for(m=C[m];C[1]-m;)R(1,2,4,3);p=&F[C[1]][C[2]][C[3]][C[4]][C[5]];r+=*p;}exit(0);}

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

using namespace std;

// Repetitions
#define FOR(i,a,n) for(ll i = ((ll) a); i < ((ll) n); ++i)
#define FORR(i, s, g) for(ll i = ((ll)s - 1); i >= ((ll) g); --i)
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) FORR(i, n, 0)

// Container Utils
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define SORTALL(v) sort(ALL(v))
#define SZ(a) int((a).size())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())

// For Debug
#define DMP(x)  cerr << #x << " = " << (x) << endl
#define DBG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

// Aliases
#define PB push_back
#define MP make_pair
typedef long long ll;
typedef string str;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

// I/O Asynchronizing
struct aaa{
    aaa(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);
    };
}aaaaaaa;

int main() {
    char a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << (((a == b && b == c) || (b == c && c == d)) ? "Yes" : "No") << "\n";

    return 0;
}


Measured memory_bytes: 256
def sol(lis,K):
    import sys
    dp = [sys.maxsize]*len(lis)
    dp[0] = 0
    for i in range(len(lis)):
        for j in range(i+1,i+K+1):
            if j<len(lis):
                dp[j] = min(dp[j],dp[i]+abs(lis[j]-lis[i]))
    print(dp[-1])
n,k = list(map(int,input().split(' ')))
lis = list(map(int,input().split(' ')))
sol(lis,k)

Measured memory_bytes: 84680
my @arr = <STDIN>;
@arr = map { chomp; [ split(/\s+/, $_) ] } @arr;
print main(@arr);

sub main {
    my ($ln) = shift->@*;
    my ($str) = shift->@*;
    my $sfx = length($str) <= $ln ? '' : '...';
    $str = substr($str, 0, $ln);
    return "$str$sfx"
}

Measured memory_bytes: 4864
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CHSI solver = new CHSI();
        solver.solve(1, in, out);
        out.close();
    }

    static class CHSI {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            int n = Integer.parseInt(in.next());
            int m = Integer.parseInt(in.next());
            int ans = (int) ((1900 * m + 100 * (n - m)) * Math.pow(2, m));

            // 出力
            out.println(ans);

        }

    }
}



Measured memory_bytes: 35528
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <cctype>
 
using namespace std;
 
int main(void) {
    char c;
    while (true){
        scanf("%c", &c);
        if (c == '\n') break;
        if (isupper(c)) printf("%c", tolower(c));
        else if (islower(c)) printf("%c", toupper(c));
        else printf("%c", c);
    }
    cout << endl;
}

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

int main() {
  int a, b;
  cin >> a >> b;
  if (a >= 13) {
    cout << b << endl;
  } else if (a <= 12&&a>=6) {
    cout << b / 2 << endl;
  } else {
    cout << 0 << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
#define mod 1000000007;
using namespace std;
int main(){
    int n,count=0;
    int p[30];
    cin >> n;
    rep(i,n){
        cin >> p[i];
    }
    rep(i,n-2){
        if(p[i]<p[i+1] && p[i+1]<p[i+2]){
            count++;
        }
        if(p[i]>p[i+1] && p[i+1]>p[i+2]){
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 888
import sys
readline = sys.stdin.readline
T = int(readline())
Ans = [None]*T
for qu in range(T):
    N = int(readline())
    A = list(map(int, readline().split()))
    S = list(map(int, readline().strip()))
    
    if len(set(A)) == 1:
        Ans[qu] = S[-1]
        continue
    
    if S[-1] == 1:
        Ans[qu] = 1
        continue
    
    stack = [0]*61
    for i in range(N-1, -1, -1):
        a = A[i]
        for j in range(60, -1, -1):
            if a&(1<<j):
                a ^= stack[j]
        
        if S[i] == 0:
            if a:
                stack[a.bit_length()-1] = a
            else:
                continue
        else:
            if a:
                Ans[qu] = 1
                break
    else:
        Ans[qu] = 0

print('\n'.join(map(str, Ans)))


Measured memory_bytes: 68432
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String[] str = in.readLine().split(" ");
    int a = Integer.parseInt(str[0]);
    int b = Integer.parseInt(str[1]);
    System.out.println((a+b)%2==0?(a+b)/2:"IMPOSSIBLE");
  }
}

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

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    int x[3]={a,b,c};
    sort(x,x+3);
    for(int i=0; i<3; ++i){
        if(i!=2)cout<<x[i]<<" ";
        else cout<<x[i]<<endl;
    }
    return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define B 10007
#define mod 1000000007L

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

ll N;
string S;
ll h[1000010],hr[1000010];
ll p[1000010],invp[1000010];

ll calchash1(ll l,ll r){
  return (h[r]-h[l]+mod)*invp[l]%mod;
}
ll calchash2(ll l,ll r){
  return (hr[r]-(hr[l]*p[r-l]%mod)+mod)%mod;
}

bool same(ll l1,ll r1,ll l2,ll r2,bool f){
  ll mnlen=min(r1-l1,r2-l2);
  if(!f){
    return calchash1(l1,l1+mnlen)==calchash1(l2,l2+mnlen);
  }else{
    return calchash1(r1-mnlen,r1)==calchash2(l2,l2+mnlen);
  }
}

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

  p[0]=1;
  rep(i,1000000)p[i+1]=p[i]*B%mod;
  rep(i,1000001)invp[i]=mod_pow(p[i],mod-2);

  cin>>N;
  cin>>S;

  {
    bool same=true;
    rep(i,N){
      if(S[i]!=S[0])same=false;
    }
    if(same){
      cout<<2<<endl;
      return 0;
    }
  }

  rep(i,N){
    h[i+1]=(h[i]+p[i]*S[i]%mod)%mod;
    hr[i+1]=((hr[i]*B%mod)+S[i])%mod;
  }

  rep(l,N-1){
    bool f=false;
    bool ok=true;
    for(ll i=0;i<N;i+=l+1){
      if(!f){
        if(S[i]!=S[0]){
          ok=false; break;
        }
      }else{
        if(S[i]!=S[l+1]){
          ok=false; break;
        }
      }
      if(!same(1,1+l,i+1,min(i+1+l,N),f)){
        ok=false; break;
      }
      f^=true;
    }

    if(ok){
      cout<<l+2<<endl;
      return 0;
    }
  }

  return 0;
}



Measured memory_bytes: 35272
#include <bits/stdc++.h>
#define ll long long

using namespace std;

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

	ll n, m=1000;
	cin >> n;
	vector<ll> v(n);
	for(ll i=0; i<n; i++)
        cin >> v[i];
    for(ll i=1; i<n; i++){
        if(v[i]>v[i-1])
            m+=(ll)(m/v[i-1])*(v[i]-v[i-1]);
    }
    cout << m << endl;
	return 0;
}


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

#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>
#define pll     pair<long long, long long>
#define ll      long long

vector<int> g[101010];

int color[101010]; //initialized to -1

int bipartite_graph(int v, int prev, int c) {
        color[v] = c;
        int cnt = c;
        bool ok = true;
        for (auto u : g[v]) if (u != prev) {
                if (color[u] == -1) {
                        int get = bipartite_graph(u, v, 1 - c);
                        if (get == -1) ok = false;
                        cnt += get;
                } else if (color[u] != 1 - c) {
                        ok = false;
                }
        }
        if (!ok) return -1;
        return cnt;
}

int main() {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < m; i ++) {
                int a, b;
                scanf("%d%d", &a, &b);
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        long long cntA = 0, cntB = 0, cntC = 0;
        for (int i = 0; i < n; i ++) color[i] = -1;
        for (int i = 0; i < n; i ++) {
                if (color[i] == -1) {
                        if (g[i].size() == 0) cntA ++;
                        else if (bipartite_graph(i, -1, 0) != -1) cntB ++;
                        else cntC ++;
                }
        }
        long long ans = cntA * cntA + (n - cntA) * cntA * 2 + cntB * cntB * 2 + cntB * cntC * 2 + cntC * cntC;
        printf("%lld\n", ans);
        return 0;
}



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

bool Panel_de_PON(int h, int w, int n, vector<string> fields){
    for (;;) {
        for(int i = h - 2; i >= 0; --i) rep(j, w) {
            if (fields[i][j] == '.') continue;
            int k = i + 1;
            for(; k < h && fields[k][j] == '.'; ++k);
            swap(fields[i][j], fields[k - 1][j]);
        }
        vector<string> t = fields;
        rep(j, w) for (int i = 0; i < h;) {
            if (fields[i][j] == '.') { i++; continue; }
            int k = i;
            for (; i < h && fields[i][j] == fields[k][j]; ++i);
            if (i - k < n) continue;
            for (; k != i; ++k) t[k][j] = '.';
        }
        rep(i, h) for (int j = 0; j < w;) {
            if (fields[i][j] == '.') { j++; continue; }
            int k = j;
            for (; j < w && fields[i][j] == fields[i][k]; ++j);
            if (j - k < n) continue;
            for (; k != j; ++k) t[i][k] = '.';
        }
        fields.swap(t);
        if (all_of(all(fields), [&](string& s) { return count(all(s), '.') == w; })) return true;
        if (t == fields) break;
    }
    return false;
}

bool solve(int h, int w, int n, vector<string>& fields){
    for (int i = h - 1; i >= 0; --i) rep(j, w - 1) {
        if (fields[i][j] == fields[i][j + 1]) continue;
        swap(fields[i][j], fields[i][j + 1]);
        if (Panel_de_PON(h, w, n, fields)) return true;
        swap(fields[i][j], fields[i][j + 1]);
    }
    return false;
}

int main(){
    int h, w, n; cin >> h >> w >> n;
    vector<string> fields(h);
    for (auto& e : fields) cin >> e;
    cout << (solve(h, w, n, fields)? "YES": "NO") << endl;
    return 0;
}

Measured memory_bytes: 3184
n = int(input())
tarou = 0
hanako = 0
for i in range(n):
    w1, w2 = input().split()
    if w1 == w2:
        tarou += 1
        hanako += 1
    elif w1 > w2:
        tarou += 3
    else:
        hanako += 3

print(tarou, hanako)

Measured memory_bytes: 7620
n = int(input())
ra = []
for i in range(n):
    x,l = map(int,input().split())
    ra.append([x-l,x+l])

ra.sort(key=lambda x:x[1])
t = ra[0][1]
ans = 1
for i in range(1,n):
    if ra[i][0] >= t:
        ans += 1
        t = ra[i][1]

print(ans)

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

int a[12][12];

int main(){
  int n,m,x;
  cin >>n >>m >>x;
  vector<int> c(n);
  rep(i,n) {
    cin >>c[i];
    rep(j,m) cin >>a[i][j];
  }

  int ans = 1001001001;
  rep(s,1<<n){
    int cost = 0;
    vector<int> d(m);
    rep(i,n){
      if (s>>i&1){
        cost += c[i];
        rep(j,m) d[j] += a[i][j];
      }
    }
    bool ok = true;
    rep(j,m) if(d[j]<x) ok = false;
    if(ok) ans = min(ans, cost);
  }
  if(ans == 1001001001) cout << -1 << endl;
  else cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define rep(x, y) for(int x = 0; x < (y); x++)
#define REP(x, z, y) for(int x = (z); x < (y); x++)
#define all(x) x.begin(), x.end()
#define len(x) (sizeof(x) / sizeof(x[0]))
#define split_str(str, sp_word) istringstream stream(str); string res; for(int cnt = 0; getline(stream,res,sp_word); cnt++)
#define scanln(x) fgets(x, sizeof x, stdin)
#define down_queue(x) priority_queue<x>
#define up_queue(x) priority_queue<x, vector<x>, greater<x>>
#define i_str(x) atoi(x.c_str())
#define digit(x) ((int)log10((double)(x)) + 1)
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
using namespace std;
const int MOD = 1000000007; 
typedef long long ll;
typedef string str;
 
int main(){
  int n;
  ll x;
  cin >> n >> x;
  getchar();

  str line;
  getline(cin,line);
  int a[n];
  split_str(line,' ') a[cnt] = i_str(res);

  ll ans = 0;
  if(a[0] > x){
    ans = a[0] - x;
    a[0] = x;
  }

  rep(i,n - 1){
    if(a[i] + a[i + 1] > x){
      ll t = (a[i] + a[i + 1]) - x;
      ans += t;
      a[i + 1] -= t;
    }
  }

  cout << ans;
  return 0;
}

Measured memory_bytes: 3844
def Y(flag):
    if flag:
        print('YES')
    else:
        print('NO')
 
def y(flag):
    if flag:
        print('Yes')
    else:
        print('No')
 
a,b = map(int,input().split())
l = [a,b,a-1,b-1]
l = sorted(l)
print(l[-1] + l[-2])

Measured memory_bytes: 3060
=begin
S
=end
S = gets.chomp
N = S.length


left = S[0...((N-1) /2)]
right = S[((N+1) /2)...N]

def kai(s)
  s == s.reverse
end

if (kai(S) && kai(left) && kai(right))
  puts "Yes"
else
  puts "No"
end  

Measured memory_bytes: 1788
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef pair<int, int>P;
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
typedef vector<vector<ll>> mat;
typedef vector<int> vec;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
const ll mod = 1000000007;
const ll INF = mod * mod;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
ll qp(ll a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

void solve() {
    ll a, b, c, d, n, k, x;
    string s, t;
    ll ans = 0;
    double dans = 0;
    string sans = "YES";



    cin  >> n >> d ;

    ans = (n + (2 * d)) / (2*d + 1);




    std::cout << ans << endl; 
    // std::cout << sans << endl; 
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    solve();
    // stop
        return 0;
}

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

long long dp[110][100010];

int main()
{
	int n,m;
	int v[110], w[110];
	cin >> n >> m;
	for(int i=1; i<=n ; i++)
		cin >> w[i] >> v[i];
		
	for(int i=1; i<=n ; i++)
	{
		for(int j=1; j<=m ; j++)
		{
			dp[i][j] = dp[i-1][j];
			if(w[i] <= j)
				dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
			
		}
	}
	cout << dp[n][m];
}

Measured memory_bytes: 81748
#include <bits/stdc++.h>
#define ii pair <int, int>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;
#define _ << " _ " <<

using namespace std;

const int N = 107;
const int V = 1e5 + 7;
const long long oo = 1e18 + 7;

int n, c;
int w[N], v[N];
long long dp[V];

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

	if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);

	cin >> n >> c;
	for (int i = 1; i <= n; i++)
		cin >> w[i] >> v[i];

	for (int i = 0; i < V; i++)
		dp[i] = oo;
	dp[0] = 0;

	for (int i = 1; i <= n; i++)
		for (int val = V; val > 0; val--)
			if (val >= v[i])
				dp[val] = min(dp[val], dp[val - v[i]] + w[i]);

	int res = 0;

	for (int i = 0; i < V; i++)
		if (dp[i] <= c)
			res = i;
	cout << res;
}

Measured memory_bytes: 1024
//BISMILLAHIR RAHMANIR RAHIM
#include <bits/stdc++.h>
#define mem(a, b) (memset(a, b, sizeof(a)))
#define pb push_back
#define mk make_pair
#define ff first
#define ss second
#define PI acos(-1)
#define INF 2147483647
#define MOD 1000000007
#define MAX 200005
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;
typedef vector<ii> vii;
typedef priority_queue<int,vector<int>,greater<int> > PQ;

int Set(int mask, int pos){return mask = mask | (1<<pos);}
bool check(int mask, int pos){return (bool)(mask & (1<<pos));}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int ans;

    for(int i = 1; i <= 5; i++) {
        int val;
        cin>>val;
        if(val == 0) {
            ans = i;
        }
    }

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 3536
#include <bits/stdc++.h>
#define ll long long
#define fastIO cout << fixed << setprecision(12), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;

int main() {
	fastIO;
#ifdef LOCAL
	freopen("input.in", "rt", stdin);
#endif
	string str;
	cin >> str;
	if(str.back() == '3') {
		cout << "bon";
	} else if(str.back() == '0' || str.back() == '1' || str.back() == '6' || str.back() == '8')
		cout << "pon";
	else
		cout << "hon";
	return 0;
}


Measured memory_bytes: 3648
n ,k = map(int, input().split())

ans = 0
twol = [0]*20
for i in range(1,n+1): 
    two = 0
    curr_i = i
    for i in range(20):
        if curr_i >= k: break
        curr_i *= 2
        two += 1
    twol[two] += 1

ans = 0
for two, cnt in enumerate(twol):
    ans += cnt/pow(2,two)
    
ans /= n
print(ans)
# for i in range(20):
#     if pow(2,i) * n >= k:


Measured memory_bytes: 66028
#include <bits/stdc++.h>
 
#define rep(i,n) for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

using namespace std;
using ll  = long long;
using pll = pair<ll, ll>;

const ll MOD  = 1e9 + 7;
const ll LINF = 1LL << 62;
const int INF = 1e9 + 7;


int main(){
    ll a;
    cin >> a;

    cout << a + a*a + a*a*a << endl;

}


Measured memory_bytes: 3628
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

int main(){
	ll k;
	ll a[100010];
	cin >> k;
	rep(i,k){
		scanf("%lld",&a[i]);
	}
	
	if(a[k-1] != 2){
		puts("-1");
		return 0;
	}
	ll ret_min = 2, ret_max = 3;
	rrep(i,k-1){
		ret_min += a[i]-1;
		ret_min -= ret_min%a[i];
		ret_max -= ret_max%a[i];
		ret_max += a[i]-1;
		if(ret_min > ret_max){
			puts("-1");
			return 0;
		}
	}
	
	cout << ret_min << " " << ret_max << endl;
}



Measured memory_bytes: 1024
/*
ID: i_love_7
LANG: C++
TASK: 
*/
#include <iostream> 
#include <cstdio> 
#include <fstream> 
#include <algorithm> 
#include <cmath> 
#include <deque> 
#include <vector> 
#include <queue> 
#include <string> 
#include <cstring> 
#include <map> 
#include <stack> 
#include <set> 
#define INF 0x3f3f3f3f
typedef long long ll;
//orz yht
using namespace std;
string i_s(int x){
	if(x==0)
	return "0";
	string ret="";
	while(x){
		ret=ret+(char)(x%10+'0');
		x/=10;
	}
	reverse(ret.begin(),ret.end());
	return ret;
}
string add(string a,string b){
	if(a=="")
	a="0";
	if(b=="")
	b="0";
	if(a.length()<b.length())
	swap(a,b);
	while(b.length()<a.length()){
		b='0'+b;
	}
	for(int i=0;i<a.length();i++){
		a[i]=a[i]+(b[i]-'0');
	}
	bool big=false;
	for(int i=a.length()-1;i>=0;i--){
		if(big){
			a[i]++;
		}
		big=false;
		if(a[i]>'9'){
			a[i]=a[i]-10;
			big=true;
		}
	}
	if(big)
	a='1'+a;
	return a;
}
string mul(string a,string b){
	vector<int> va,vb;
	if(a=="0" || b=="0")
	return "0";
	string ans;
	for(int i=0;i<a.length();i++){
		va.push_back(a[i]-'0');
	}
	for(int i=0;i<b.length();i++){
		vb.push_back(b[i]-'0');
	}
	reverse(va.begin(),va.end());
	reverse(vb.begin(),vb.end());
	vector<int> res;
	res.clear();
	res.resize(1005);
	for(int i=0;i<a.length();i++){
		for(int j=0;j<b.length();j++){
			res[i+j]+=(va[i]*vb[j]);
		}
	}
	for(int i=0;i<1005;i++){
		if(res[i]>9){
			res[i+1]+=(res[i]/10);
			res[i]%=10;
		}
	}
	for(int i=0;i<1005;i++){
		ans+=(res[i]+'0');
	}
	reverse(ans.begin(),ans.end());
	int k=0;
	while(ans[k]=='0'){
		k++;
	}
	ans=ans.substr(k);
	return ans;
}
int n,a[25],b[25],c[25],ans;
int main(){
	//freopen("inout.in","r",stdin);
	//freopen("output.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n;i++){
    	int x;
    	cin>>x;
    	ans+=x;
	}
	for(int i=1;i<=n-1;i++){
		cin>>c[i];
	}
	for(int i=1;i<=n-1;i++){
		if(a[i+1]==a[i]+1)
		ans+=c[a[i]];
	}
	cout<<ans;
	//system("pause");
	return 0;
}

Measured memory_bytes: 256
/*                          The four Truths of Life

                                    CKMKB
                                    PKMKB

                                    CKMKC
                                    PKMKC
*/


#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <climits>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
using namespace std;
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define ye cout<<"YES";
#define no cout<<"NO";
#define ln cout<<"\n";
// cout<<"Case #"<<ts<<": “;
//priority_queue < pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;




ll mod(ll x, ll m) {
	return (x % m + m) % m;
}

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

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ll t = 1, r, n, a, d, c, b, x, y, sum, cnt, i, j, k, m, l, q, maxx, minn, temp, ans, flag, g, ts;
	ll mod = 1000000007;
	char ch, chh;
	double dans;
	string str, ttr;

	//cin >> t;


	for (ts = 1; ts <= t; ts++)
	{
		flag = 0; sum = 0; cnt = 0; ans = 0; k = 0; maxx = 0; minn = 0; a = 0; b = 0; temp = 0;

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

		temp = 1000;
		for (i = 0; i < n; i++)
		{
			if (i + 1 < n && arr[i + 1] > arr[i])
			{
				x = arr[i];
				while (i + 1 < n && arr[i + 1] > arr[i])
				{
					i++;
				}
				y = arr[i];

				maxx = temp / x;
				temp -= (maxx * x);
				temp += (maxx * y);
			}
		}

		cout << temp;




		ln
	}
	return 0;
}


Measured memory_bytes: 3648
#include <iostream>
using namespace std;
int main(){
  int n;
  cin >> n;
  int a[n], b[n], c[n-1], sum=0;
  for(int i=0; i<n; i++) cin >> a[i];
  for(int i=0; i<n; i++) {cin >> b[i]; sum+=b[i];}
  for(int i=0; i<n-1; i++) cin >> c[i];
  for(int i=0; i<n; i++){
    if(a[i+1]-a[i]==1) sum+=c[a[i]-1];
  }
  cout << sum;
  return 0;
}


Measured memory_bytes: 256
//#include <tourist>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <iomanip>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <tuple>
#include <deque>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
//setprecision(15)有効数字15桁
//-std=c++14
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}
struct edge {
    int to, cost;
};
int n, h, w;
vector<int> a;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> h>>w>>n;
    int ans=0;
    int count=0;
    int counth=0;
    int countw=0;
    cout<<(n+max(h,w)-1)/max(h,w)<<"\n";
}



Measured memory_bytes: 256
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {n: usize, a: [usize; n]};

    let mut a_even: Vec<usize> = vec![];

    for &a_iter in a.iter() {
        if a_iter % 2 == 0 {
            a_even.push(a_iter);
        }
    }

    let mut t = true;
    for &a_even_iter in a_even.iter() {
        if !(a_even_iter % 3 == 0 || a_even_iter % 5 == 0) {
            t = false;
        }
    }

    if t {
        println!("APPROVED")
    } else {
        println!("DENIED")
    }
}


Measured memory_bytes: 2180
#include <algorithm>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <numeric>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// using namespace std;

using ll = long long;

void Main() {
  int N;
  std::cin >> N;
  int A[N];
  ll Asum = 0;
  ll A2sum = 0;

  for (int i = 0; i < N; ++i) {
    std::cin >> A[i];
    Asum += A[i];
    if (i % 2 == 1) {
      A2sum += A[i];
    }
  }

  int m[N];
  m[0] = Asum - 2 * A2sum;

  for (int j = 0; j < N; ++j) {
    m[j + 1] = (A[j] - (m[j] / 2)) * 2;
  }
  if ((m[0] + m[N - 1]) / 2 == A[N - 1]) {
    for (int k = 0; k < N; ++k) {
      std::cout << m[k] << std::endl;
    }
    return;
  }
}

int main() {
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}


Measured memory_bytes: 2048
import java.util.*;

public class Main{
   public static void main(String args[] ) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x[] = new int[n];
        for (int i = 0 ; i < n;i++)
        	x[i] = sc.nextInt();
        for(int i = 0 ; i < n;i++){
        	if(i != 0)
        	System.out.print(" ");
        	System.out.print(x[n-i-1]);
          }
        System.out.println();
    }
}



Measured memory_bytes: 26236
# D - Flipping Signs
# https://atcoder.jp/contests/abc125/tasks/abc125_

import sys
sys.setrecursionlimit(1000000)

N = int(input())
A = list( map(int, raw_input().split()) )

visit = dict()

def dp(pos, sign):
    # terminal condition
    if pos == N-1:
        if sign == 0:
            return A[pos]
        else:
            return -A[pos]

    if (pos, sign) in visit:
        return visit[(pos, sign)]

    elif sign == 0:
        # memorize
        visit[(pos, sign)] = max( dp(pos+1, 0) + A[pos], dp(pos+1, 1) - A[pos])
        return visit[(pos, sign)]

    else: # st == 1
        # memorize
        visit[(pos, sign)] = max( dp(pos+1, 0) -  A[pos], dp(pos + 1, 1) + A[pos])
        return visit[(pos, sign)]

print '{}'.format( dp(0,0) )


Measured memory_bytes: 114172
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
    LL a, b,c;
    cin >> a >> b >> c;
    if(a < c) c -= a,a = 0;
    else a -= c,c = 0;
    if(b < c) c -= b,b = 0;
    else b -= c,c = 0;
    cout << a <<' ' << b;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
int N;
ll fact(int k)
{
    if (k == 1)
    {
        return 1;
    }
    return k * fact(k - 1);
}
double dist(int x1, int x2, int y1, int y2)
{
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int main()
{
    cin >> N;
    vector<int> x(N);
    vector<int> y(N);
    double f = fact(N) / N * 2;
    // cout << fact(N) << endl;
    // cout << f << endl;
    rep(i, 0, N)
    {
        cin >> x[i] >> y[i];
    }
    double sum = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = i; j < N; j++)
        {
            sum += dist(x[i], x[j], y[i], y[j]) * f;
        }
    }
    // cout << sum << endl;
    cout << fixed << setprecision(10) << (sum) / fact(N) << endl;
    return 0;
}

Measured memory_bytes: 3824
from math import ceil
n = int(input())
#a,b = map(int,input().split())
T=1
A=1

for i in range(n):
    a,b = map(int,input().split())
    num = max(ceil((T)//a)+(T%a!=0),ceil((A)//b)+(A%b!=0))
    T = a*(num)
    A = b*(num)
    #print(T,A)
print(T+A)


Measured memory_bytes: 3060
N,A = map(int,input().split())
x = list(map(int,input().split()))
X = N*max(max(x),A)
dp = [[[0 for i in range(X+1)] for j in range(N+1)] for k in range(N+1)]
dp[0][0][0] = 1
for k in range(1,N+1):
    for j in range(k+1):
        for i in range(X+1):
            if i - x[k-1] >= 0 and k >= 1:
                dp[k][j][i] = dp[k-1][j-1][i-x[k-1]] + dp[k-1][j][i]
            else:
                dp[k][j][i] = dp[k-1][j][i]
ans = 0
for j in range(1,N+1):
    for i in range(X+1):
        if i%j == 0 and i//j == A:
            ans += dp[-1][j][i]
print(ans)

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

int N;
string S; 

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

    map<char, int> mp;
    rep(i, N) {
        mp[S[i]]++;
    }

    // cout << mp['W'] << endl;
    // cout << mp['E'] << endl;

    map<char, int> current;
    int ans = N;
    rep(i, N) {
        // 左側は E
        int left_e = current['E'];
        int left_w = current['W'];

        current[S[i]]++;

        // 右側は W
        int right_e = mp['E'] - current['E'];
        int right_w = mp['W'] - current['W'];
        // printf("l e: %d l w: %d r e: %d r w: %d\n", 
        //     left_e, left_w,
        //     right_e, right_w
        // );

        ans = min(ans, left_w + right_e);
    }

    cout << ans << endl;
}

Measured memory_bytes: 900
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); //N回じゃんけん
        int K = sc.nextInt(); //K回前と同じ手を出せない
        int R = sc.nextInt(); //グーの得点
        int S = sc.nextInt(); //チョキの得点
        int P = sc.nextInt(); //パーの得点
        int sum = 0; //合計得点
        String T = sc.next(); //相手の出し手
        String[] enemy = T.split(""); //相手の出し手配列
        String[] me = new String[N]; //自分の出し手配列
        
        for(int i = 0; i < N; i++) {
            //K+1回目以降
            if(i-K>=0) {
                if(me[i-K] == null) {
                    me[i-K] = "z";
                }
                if(enemy[i].equals("r")) {
                    if(me[i-K].equals("p")) {
                        continue;
                    }else {
                        me[i] = "p";
                    sum += P;
                    }
                }else if(enemy[i].equals("s")) {
                    if(me[i-K].equals("r")) {
                        continue;
                    }else {
                        me[i] = "r";
                    sum += R;
                    }
                }else if(enemy[i].equals("p")) {
                    if(me[i-K].equals("s")) {
                        continue;
                    }else {
                        me[i] = "s";
                    sum += S;
                    }
                }
            //1~K回目
            }else {
                if(enemy[i].equals("r")) {
                    me[i] = "p";
                    sum += P;
                }else if(enemy[i].equals("s")) {
                    me[i] = "r";
                    sum += R;
                }else if(enemy[i].equals("p")) {
                    me[i] = "s";
                    sum += S;
                }
            }
        }
        System.out.println(sum);
        
    }
}

Measured memory_bytes: 33520