akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for (ll i=0; i<n; ++i)
#define all(c) begin(c),end(c)
template<typename T1, typename T2>
bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
template<typename T1, typename T2>
bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
/*
)
(()

1 0
0 1

)(
()

1 1
0 0 うちけしあったときに1 1でNG

4
((()))
((((((
))))))
()()()
0 0
0 6
6 0
0 0

3
(((
)
)
0 3
1 0
1 0

)(
)(
1 1
1 1 )()(でNG

どれかは0が必要か

3
(
)
))((

0 1
1 0
2 2

01
10
22

01
22 21
10 11


01 02 03 
6
10 20 20
5
HP6と HP5みたいな

01 = -1
10 = +1
12 = -1
16 = -5
21
21
...

0のやつだけHP管理。
それ以外は差分を入れる

01を先頭に、10を最後尾にする。

3     R L
))    2 0 ...Lが2個余裕ある。＝LのHPが2
)()(( 1 2 tupleで保存。((2-1), 1, 2)
　　　　　　　　//差分がプラス＝Lが対処しなきゃいけない
        　　　　　　　　　　　＝Rにとっては回復
        　　　 //差分がマイナスだと、Rが対処

)))))(((( 5 4 = 1
))(       2 1 = 1


((())
))(((

(((((

))))))((((((((((
)((


RのHP１から開始。
攻撃(1, 1, 2)
R -= get<1>(A[i])
このとき、Rが1回でも負になった時点で"No"


(     0 1...Rが1個余裕ある　＝RのHPが1


->
123210 = min=0
((())) [0] 0
->
-1-2-3 -2-1 0 min=-3
)))((( [3] 3

-> -1 0 -1
)() 1 [0]
1 0 1<- min = [0]
01
12
20

【Yesになるべき。NoでもACしたパターン】
4
(
)((
))((((
))))

*/

int main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  
  ll N; cin >> N;
  ll zL=0, zR=0, zLR=0, L=0, R=0;
  vector<pair<ll,ll>> plus(0, {0,0}), minus(0, {0,0});
  rep(i, N){
    string S; cin>>S;
    ll j=0, tmp=0, q=0, p=0;
    while (S[j]){
      if (S[j] == ')'){//qpで管理
        tmp--;
        chmin(q,tmp);
      }
      else
        tmp++;
      j++;
    }
    j--;
    tmp = 0;
    while (j>=0){
      if (S[j] == '('){
        tmp--;
        chmin(p, tmp);
      }
      else
        tmp++;
      j--;
    }
//cout<<"q:"<<q<<" p:"<<p<<" i:"<<i<<endl;    
    if (q==0 && p==0)
      zLR++;
    else if (q==0){
      zR++;
      R -= p;
    }
    else if (p==0){
      zL++;
      L -= q;
    }
    else{
      ll tmp = -(p-q);
      p = -p;
      q = -q;
      if (tmp > 0)
        plus.push_back({q, p});
      else
        minus.push_back({q, p});
    }
  }
  if (N==1 && zLR == 1){
    cout << "Yes" << endl;
    return 0;
  }
  bool ans = true;
  if (zL==0 && zR==0 && zLR < 2)
    ans = false;
  if ((zL==0 || zR==0) && zLR == 0)
    ans = false;
  sort(all(plus));
  sort(all(minus));
  reverse(all(minus));
  ll psz = plus.size();
//cout <<"startR:"<<R<<" L:"<<L<<endl;    
  //まず回復パターン。弱い攻撃から受ける
  rep(i, psz){
    R -= plus[i].first;
    if (R < 0){
      ans = false;
      break;
    }
    R += plus[i].second;
  }
  //防御パターン。大きい攻撃から受ける
  ll msz = minus.size();
  rep(i, msz){
    R -= minus[i].first;
    if (R < 0){
      ans = false;
      break;
    }
    R += minus[i].second;
  }
//cout <<"lastR:"<<R<<" L:"<<L<<endl;    
  R -= L;
  if (R != 0)
    ans = false;
  if (ans)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}


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

const int DIM = 17;
const int MOD = 1e9 + 7;

vector<int> lst[3];
bitset<DIM> oki[1 << DIM];

int msb[1 << DIM], dp[2][1 << DIM];

int main( void ) {
    
    int n, x, y, z;
    cin >> n >> x >> y >> z;
    
    for( int msk = 1; msk < (1 << (x + y + z)); msk ++ ) {
        int msb = 0;
        for( int i = 0; i < x + y + z; i ++ )
            if( msk & (1 << i) )
                msb = i + 1;
    
        if( msb == x )
            lst[0].push_back( msk );
        if( msb == y )
            lst[1].push_back( msk );
        if( msb == z )
            lst[2].push_back( msk );
    }
    
    for( int _x : lst[0] )
    for( int _y : lst[1] )
    for( int _z : lst[2] )
        oki[(((_x << y) + _y) << z) + _z] = true;
    
    int ans = 1;
    for( int i = 1; i <= n; i ++ )
        ans = ( 10LL * ans ) % MOD;
    
    dp[0][0] = 1;
    for( int i = 1, t = 1; i <= n; i ++, t = 1 - t ) {
        memset( dp[t], 0, sizeof(dp[t]) );
        
        for( int msk = 0; msk < (1 << (x + y + z)); msk ++ ) {
            for( int j = 1; j <= 10; j ++ ) {
                int axm = ( (msk << j) ^ (1 << (j - 1)) ) & ((1 << (x + y + z)) - 1);
                
                if( oki[axm] == false )
                    dp[t][axm] = ( dp[t][axm] + dp[1 - t][msk] ) % MOD;
            }
        }
    }
    
    for( int msk = 0; msk < (1 << (x + y + z)); msk ++ )
        ans = ( ans - dp[n & 1][msk] + MOD ) % MOD;
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1536
import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

X = int(read())

ans = 0
ans += (X // 500) * 1000
X %= 500
ans += (X // 5) * 5

print(ans)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
int main() {
  string s; cin >> s;
  for (int i = 0; i < s.size()-1; i++) {
    if (s[i] == 'A' && s[i+1] == 'C') {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}

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

/*bool subseq(string s,string t){
    ll y=0;
    for(ll i=0;y<s.size()&& i<t.size();i++){
        if(s[y]==t[i]){
            y++;
        }
    }
        if(y==s.size())
            return true;
        else  return false;
}*/




int main(){
    ll n,x;
    cin>>n;
    x=n%10;
    if(x==2||x==4||x==5||x==7||x==9)
        cout<<"hon";
    else if(x==0||x==1||x==6||x==8)
        cout<<"pon";
    else
        cout<<"bon";

}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
char a[1000005];
int len,k;
int main()
{
	cin>>len>>a>>k;
	for(int i=0;i<len;i++){
		if(a[i]!=a[k-1])
			a[i]='*';
		cout<<a[i];
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	s := nextStr()
	l := make([]byte, 30)

	nowidx := 0
	for i := 0; i < len(s); i++ {
		if s[i] == 'B' {
			l[nowidx] = 'B'
			nowidx = max(0, nowidx-1)
		} else {
			l[nowidx] = s[i]
			nowidx++

		}
	}
	for i := 0; i < nowidx; i++ {
		fmt.Printf("%c", l[i])
	}

}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// ---- readfunc
func scanInit() {
	const cap = 200 * 1024 // default=64*1024
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 1780
#include <stdio.h>

#define MAX 8
#define TRUE 2
#define FALSE -2
#define FREE -1
#define NOT_FREE 1

void initialize();
void printBoard();
void recursive(int);

int row[MAX];
int col[MAX];
int dpos[2 * MAX - 1];
int dneg[2 * MAX - 1];
int judge[MAX][MAX];

int main(){
  int i,j,k;
  int c,r;
  
  initialize();

  for (i = 0;i < MAX;i++)
    for (j = 0;j < MAX;j++)
      judge[i][j] = FALSE;

  scanf("%d",&k);
  
  for (i = 0;i < k;i++){
    scanf("%d %d",&r,&c);
    judge[r][c] = TRUE;
  }

  recursive(0);
  
  return 0;
}

void initialize(){
  int i,j;

  for (i = 0;i < MAX;i++){
    row[i] = FREE;
    col[i] = FREE;
  }

  for (i = 0;i < 2 * MAX - 1;i++){
    dpos[i] = FREE;
    dneg[i] = FREE;
  }
}

void printBoard(){
  int i,j;

  for (i = 0;i < MAX;i++)
    for (j = 0;j < MAX;j++)
      if (judge[i][j] == 2)
	if (row[i] != j)
	  return;
  
  for (i = 0;i < MAX;i++){
    if (i)
      printf("\n");
    
    for (j = 0;j < MAX;j++)
      if (row[i] == j)
	printf("Q");

      else
	printf(".");
  }

  printf("\n");
}

void recursive(int i){
  int j;
  
  if (i == MAX){
    printBoard();
    return;
  }

  for (j = 0;j < MAX;j++){
    if (NOT_FREE == col[j] || NOT_FREE == dpos[i + j]
	|| NOT_FREE ==dneg[i - j + MAX - 1])
      continue;

    row[i] = j;
    col[j] = NOT_FREE;
    dpos[i + j] = NOT_FREE;
    dneg[i - j + MAX - 1] = NOT_FREE;

    recursive(i + 1);

    row[i] = FREE;
    col[j] = FREE;
    dpos[i + j] = FREE;
    dneg[i - j + MAX -1] = FREE;
  }
}



Measured memory_bytes: 2112
#include <cstddef>
#include <complex>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <limits>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <valarray>
#include <utility>
#include <tuple>
#include <cmath>
#include <memory>
#include <random>
#include <fstream>
#include <locale>

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

//vector
template <class T>
using vec = std::vector<T>;

template <class T>
using vvec = vec<vec<T>>;

constexpr std::size_t operator""_sz(ull n) { return std::size_t(n); }

int main()
{
	using namespace std;

	string s, t;
	cin >> s >> t;
	
	int ans{};

	for (int i = 0; i < 3; ++i)
	{
		if (s[i] == t[i])
			++ans;
	}

	cout << ans << endl;



	return 0;
}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  if (s.back() == 's')
    cout << s << "es\n";
  else
    cout << s << "s\n";   
  return 0;
}

Measured memory_bytes: 3604
from sys import stdin, stdout
read = stdin.readline
write = stdout.write
flush = stdout.flush
xr = xrange

def main():
	x,n = map(int,read().split())
	a = list(map(int,read().split()))
	if x not in a:
		ans = x
	else:
		for i in xr(1,100):
			if x - i not in a:
				ans = x - i
				break
			elif x + i not in a:
				ans = x + i
				break
	print ans

if __name__ == "__main__":
	main()

Measured memory_bytes: 85044
#include <iostream>

using namespace std;

int main()
{
 int a, b , c ;
 cin >> a >> b >> c ;
 if((a + b) == c)
    cout << "Yes";
 else if((a + c) == b)
    cout << "Yes";
 else if ((b + c) == a)
    cout << "Yes";
 else
    cout << "No";


  return 0;
}



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

#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;
// typedef priority_queue<int, vector<int>, greater<int>> min_pq;

std::random_device rd_device;
std::mt19937 rng(rd_device());

template<typename T>
void printVec(vector<T> &vec) {
    for (auto &v : vec) cout<<v<<" ";
    cout<<endl;
}

void sleep(int ms) {
    std::this_thread::sleep_for(std::chrono::milliseconds(ms));
}

int main() {
    std::srand(std::time(0));
    ios::sync_with_stdio(false);
//    cin.exceptions(ios_base::failbit);
    cin.tie(NULL);
    cout.tie(NULL);
    cout.precision(10);
    cout<<fixed;
    
    int h, w, n;
    cin>>h>>w>>n;
    int r, c;
    cin>>r>>c;
    r--;c--;
    string s, t;
    cin>>s>>t;
    vector<int> d(4);
    bool good = true;
    for (int i=0;i<n;i++) {
        if (s[i]=='L') d[0]++;
        if (s[i]=='R') d[1]++;
        if (s[i]=='U') d[2]++;
        if (s[i]=='D') d[3]++;

        if (c - d[0] < 0) good = false;
        if (c + d[1] >= w) good = false;
        if (r - d[2] < 0) good = false;
        if (r + d[3] >= h) good = false;
        if (!good) break;

        if (t[i]=='L' && c+d[1]>0) d[1]--;
        if (t[i]=='R' && c-d[0]<w-1) d[0]--;
        if (t[i]=='U' && r+d[3]>0) d[3]--;
        if (t[i]=='D' && r-d[2]<h-1) d[2]--;
    }
    
    if (good) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}


Measured memory_bytes: 920
// abc045 - b
#include <stdio.h>
#include <stdint.h>

int main(void)
{
  char s[3][101];
  uint32_t i;
  uint32_t turn=0;
  uint32_t ptr[3];
  uint32_t len[3];
  for (i=0;i<3;i++) {
    scanf("%s", s[i]);
    ptr[i]=0;
    len[i]=strlen(s[i]);
  }
  while(1){
    uint32_t p=ptr[turn];
    ptr[turn]++;
    turn=s[turn][p]-'a';
    if(len[turn]==ptr[turn]){
      printf("%c\n", 'A'+turn);
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 128
n,K,L = gets.chomp.split(" ").map(&:to_i)
roadmori = Array.new(n){|i|i}
roadfore = Hash.new
railmori = Array.new(n){|i|i}
railfore = Hash.new
rr = Hash.new{|h,k|h[k] = Hash.new(0)}
ans = Array.new(n)
n.times do |i|
  roadfore[i] = [i]
  railfore[i] = [i]
end
K.times do
  p,q = gets.chomp.split(" ").map{|i|i.to_i-1}
  if roadmori[p] != roadmori[q]
    if roadfore[roadmori[p]].size < roadfore[roadmori[q]].size
      j,k = p,q
    else
      j,k = q,p
    end
    roadfore[roadmori[j]].each do |l|
      roadmori[l] = roadmori[k]
      roadfore[roadmori[k]] << l
    end
  end
end
L.times do
  p,q = gets.chomp.split(" ").map{|i|i.to_i-1}
  if railmori[p] != railmori[q]
    if railfore[railmori[p]].size < railfore[railmori[q]].size
      j,k = p,q
    else
      j,k = q,p
    end
    railfore[railmori[j]].each do |l|
      railmori[l] = railmori[k]
      railfore[railmori[k]] << l
    end
  end
end
for i in 0..n-1
  rr[roadmori[i]][railmori[i]] += 1
end
for i in 0..n-1
  ans[i] = rr[roadmori[i]][railmori[i]]
end
puts ans.join("\s")

Measured memory_bytes: 123388
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()

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

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

int main() {
  int n,a,b;
  cin >>n>>a>>b;
  
  cout << min(n*a,b) <<endl;
  
  return 0;
}

Measured memory_bytes: 256
from sys import exit

H, W, M = map(int, input().split())

r = [0] * H
c = [0] * W
l = []
for _ in range(M):
    h, w = map(int, input().split())
    l.append([h-1, w-1])
    r[h-1] += 1
    c[w-1] += 1

set_r = set()
set_c = set()
max_r, max_c = max(r), max(c)

for i in range(H):
    if r[i] == max_r:
        set_r.add(i)

for i in range(W):
    if c[i] == max_c:
        set_c.add(i)

cnt = 0
for x, y in l:
    if x in set_r and y in set_c:
        cnt += 1

if cnt == len(set_r) * len(set_c):
    print(max_r + max_c - 1)
else:
    print(max_r + max_c)

Measured memory_bytes: 216356
import sys
n=int(input())
lst=[]
for i in range(n):
  T,X,Y=map(int,input().split())
  lst.append([T,X,Y])
if (abs(lst[0][1])+abs(lst[0][2]))%2==lst[0][0]%2:
  if abs(lst[0][1])+abs(lst[0][2])<=lst[0][0]:
    pass
  else:
    print('No')
    sys.exit()
else:
  print('No')
  sys.exit()

for j in range(n-1):
  if (abs(lst[j][1]-lst[j+1][1])+abs(lst[j][2]-lst[j+1][2]))%2==(lst[j+1][0]-lst[j][0])%2:
    if abs(lst[j][1]-lst[j+1][1])+abs(lst[j][2]-lst[j+1][2])<=(lst[j+1][0]-lst[j][0]):
      pass
    else:
      print('No')
      sys.exit()
  else:
    print('No')
    sys.exit()
print('Yes')

























Measured memory_bytes: 19572
#include<iostream>

using namespace std;

int main(){
 int d,n;
  cin >> d >> n;
  
  if(n<100){
  if(d==0) cout << n << endl;
  else if(d==1) cout << 100*n << endl;
  else cout << 10000*n << endl;
  }
  else{
  if(d==0) cout << n+1 << endl;
  else if(d==1) cout << 100*(n+1) << endl;
  else cout << 10000*(n+1) << endl;
  }
  }


Measured memory_bytes: 256
class DisjointSets

  def initialize(n)
    @p = Array.new(n)
    @rank = Array.new(n)
    n.times do |i|
      make_set(i)
    end
  end

  def make_set(x)
    @p[x] = x
    @rank[x] = 0
  end

  def same?(x, y)
    find_set(x) == find_set(y)
  end

  def find_set(x)
    if x != @p[x]
      @p[x] = find_set(@p[x])
    end
    @p[x]
  end

  def unite(x, y)
    link(find_set(x), find_set(y))
  end

  def link(x, y)
    if @rank[x] > @rank[y]
      @p[y] = x
    else
      @p[x] = y
      if @rank[x] == @rank[y]
        @rank[y] += 1
      end
    end
  end
end

def kruskal(n, edges)
  edges.sort!
  total_cost = 0
  s = DisjointSets.new(n)
  edges.each do |edge|
    unless s.same?(edge.source, edge.target)
      s.unite(edge.source, edge.target)
      total_cost += edge.weight
    end
  end
  total_cost
end


class Edge
  attr_accessor :source, :target, :weight
  def initialize(source:, target:, weight:)
    @source = source
    @target = target
    @weight = weight
  end

  def <=>(other)
    @weight - other.weight
  end
end

v, e = gets.split.map(&:to_i)
edges = []
e.times do
  s, t, w = gets.split.map(&:to_i)
  edges << Edge.new(source: s, target: t, weight: w)
end

puts kruskal(v, edges)


Measured memory_bytes: 15900
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/




int a, b;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> a >> b;

    if (a + b == 15) printf("+\n");
    else if (a * b == 15) printf("*\n");
    else printf("x\n");
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>
#include <ios>
#include <cctype>
#include <cstdio>
#include <functional>
#include <cassert>
#include <fstream>
#include <ctime>

using namespace std;
using ll = long long;

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define FORR(i,a,b) for(int i = (a) - 1;i >=(b);--i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).sizeT()
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())
#define ASSERT(cond,mes) assert(cond && mes)

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'050'000'000;

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2>& p) {
    os << p.first << p.second;
    return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    REP(i, (int)v.size())is >> v[i];
    return is;
}

template <typename T>
T clamp(T& n, T a, T b) {
    if (n < a)n = a;
    if (n > b)n = b;
    return n;
}

template <typename T>
static T GCD(T u, T v) {
    T r;
    while (v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

template <typename T>
static T LCM(T u, T v) {
    return u / GCD(u, v) * v;
}

std::vector<int> enum_div(int n) {
    std::vector<int> ret;
    for (int i = 1; i*i <= n; ++i) {
        if (n%i == 0) {
            ret.push_back(i);
            if (i != 1 && i*i != n) {
                ret.push_back(n / i);
            }
        }
    }
    return ret;
}

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

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

struct ToUpper {
    char operator()(char c) { return toupper(c); }
};

struct ToLower {
    char operator()(char c) { return tolower(c); }
};

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

    int A, B;
    cin >> A >> B;

    int ans = 0;
    int num = 1;
    while (num < B) {
        num--;
        num += A;
        ans++;
    }

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

Measured memory_bytes: 256
k,n = map(int,input().split())
a= list(map(int,input().split()))
maxN= k-a[n-1]+a[0]
for i in range(0,n-1):
    if maxN<a[i+1]-a[i]:
        maxN=a[i+1]-a[i]

print(k-maxN)

Measured memory_bytes: 26444
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vout(x) rep(i,x.size()) cout << x[i] << " "
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll,int>;
const int inf = 1e9;
const ll inf_l = 1e18;
const int MAX = 1e5;

int main() {
    int n, m; cin >> n >> m;
    set<int> a_1, a_n;
    rep(i,m) {
        int a, b; cin >> a >> b;
        if (a == 1) a_1.insert(b);
        else if (b == n) a_n.insert(a);
    }
    bool ok = false;
    for (auto itr = a_1.begin(); itr != a_1.end(); itr++) {
        auto f = a_n.find(*itr);
        if (f != a_n.end()) ok = true;
    }
    printf(ok?"POSSIBLE\n":"IMPOSSIBLE\n");
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template < typename T > string tost( const T& n ) { ostringstream stm; stm << n; return stm.str();}
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;}
int const INF = 1001001001;


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

int N,L;
cin >> N >> L;
vector<string> S(N);
rep(i,N) cin >> S[i];
sort(all(S));
string ans = "";
rep(i,N) ans += S[i];
cout << ans << endl;
return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
#include <tuple>
#include<iomanip>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
#define MOD 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9
#define LLINF 1LL<<60


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

	int N; cin >> N;
	cout << N * N * N << endl;

	return 0;
}

Measured memory_bytes: 256
using System;
 
namespace aizu
{
    class OnlineJudge
    {
        const int Max = 1000000;
        static void Main()
        {
            int[] p = new int[Max];
            int count = 1;
            for(int i=3; i < Max; i += 2) {
                if(p[i] == 0) {
                    ++count;
                    if(i <= 1000) {
                        for(int l = i; i * l < Max; ++l) {
                            p[l * i] = -1;
                        }
                    }
                }
                p[i] = count;
            }
            p[2] = 1;
            string num;
            while((num = Console.ReadLine()) != null) {
                int v = int.Parse(num);
                if(v != 2 && (v & 1) == 0) {
                    --v;
                }
                Console.WriteLine(p[v]);
            }
        }
    }
}

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

int main()
{
	int n;
	char c1,c2;
	double w,h;
	while(cin >> n >> c1 >> w >> c2 >> h)
	{
		if(25.0 <= w/(h*h))
		{
			cout << n << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1232
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;

const int MaxN = 2e5;
int n;
LL k, a[MaxN + 5];

int main() 
{
	scanf("%d%lld", &n, &k);
	for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	LL t = 0, ans = 0;
	for(int i = 1; i <= n; i++) {
		if(t <= a[i]) ans += k, t = a[i] + k;
		else ans += (a[i] + k - t), t = a[i] + k;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<math.h>
using namespace std;
#define mod (1000000000+7)
#define N (998244353)
#define INF 1e16
typedef long long ll;
typedef pair<ll,ll> P;


int main(void){
    int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    bool flag=true;
    for(int i=0;i<n;i++){
        if(a[i]%2==1)flag=false;
    }
    if(flag)cout<<"second"<<endl;
    else cout<<"first"<<endl;

    return 0;
}


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

int main()
{
    long long N,sum=0;
    cin >> N;
    int A[N+1];
    for(int i=1;i<=N;i++)
    {
        if((i%3!=0) && (i%5!=0))
        {
            sum += i;
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>

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

int main() {
  double L;
  cin >> L;
  L /= 3;
  
  cout << setprecision(10) << pow(L, 3) << endl;

}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for(int i = (a); i < (int)(b); i++)
#define pw(x) (1LL<<(x))
static const int fast_io = [](){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);return 0;}();
static const int precise_doubles = [](){cout<<fixed<<setprecision(20);return 0;}();
typedef pair<int, int> PII;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// find_by_order(k) - iterator to kth largest, order_of_key(k) - #things < k
typedef long double LD;
typedef long long LL;
#define EVAL(x) x
#define SPA(x) EVAL({cout << #x" = " << x << ' ';})
#define NEWL EVAL({cout << '\n';})
#define SPAR(a, b) EVAL({cout<<#a" = ";for(auto it=a;it!=b;)cout<<*(it++)<<" ";cout<<'\n';})
#define SPAV(v) EVAL({cout<<#v" = ";for(auto it=v.begin();it!=v.end();)cout<<*(it++)<<" ";cout<<'\n';})
const int INF = 0x3f3f3f3f; // 1.0e9
const LL LINF = 0x3f3f3f3f3f3f3f3fll; // 4.5e18
const LD eps = 1e-20;
const int mod = 3;
inline int msum(int x, int y) {return (x+y<mod ? x+y : x+y-mod);}
inline int mdif(int x, int y) {return (x>=y ? x-y : x-y+mod);}
inline int mprod(int x, int y) { return (1ll*x*y) % mod; }
inline int mpow(int x, LL y) {LL r=1;while(y){if(y&1)r=mprod(r,x);x=mprod(x,x);y>>=1;}return r;}
inline int minv(int x) { return mpow(x, mod-2); }
#define DIE EVAL({cout << -1 << '\n'; exit(0);})
//------------------------------------------------------------------------------------------------------

const int N = 3e5 + 10;
const int M = 1e5 + 10;

int ans[M];
int n, m;
struct Interval {
    int l, r, len;
};
vector<Interval> intervals;

const int base = 1<<17;
int seg[base<<1];

void update(int pos, int val) {
    for(int i = base+pos; i >= 1; i >>= 1) seg[i] += val;
}
int query(int l, int r, int u = 1, int L = 0, int R = base-1) {
    if(l == L and r == R) return seg[u];
    int mid = (L+R)>>1;
    if(r <= mid) return query(l, r, u<<1, L, mid);
    if(l > mid) return query(l, r, u<<1|1, mid+1, R);
    return query(l, mid, u<<1, L, mid) + query(mid+1, r, u<<1|1, mid+1, R);
}

int main() {
    cin >> n >> m;
    REP(i, n) {
        int l, r; cin >> l >> r;
        intervals.push_back({l, r, r-l+1});
    }
    sort(intervals.begin(), intervals.end(),
        [&](const Interval& i1, const Interval& i2) {
            return i1.len < i2.len;
        });
    int nex = 0;
    FOR(d, 1, m+1) {
        while(nex < (int)intervals.size() && intervals[nex].len < d) {
            update(intervals[nex].l, 1);
            update(intervals[nex].r+1, -1);
            nex++;
        }
        ans[d] = n-nex;
        for(int x = d; x <= m; x += d) {
            ans[d] += query(0, x);
        }
    }
    FOR(d, 1, m+1) cout << ans[d] << '\n';
}






























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

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

const int INF=1e9;
const int MOD=1e9+7;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

int main()
{
	for(int h,w,m;cin>>h>>w>>m && h|w|m;){
		vector<string> grid(h);
		rep(i,h) cin>>grid[i];
		
		static int vis[100][100][4][11][11];
		memset(vis,0,sizeof vis);
		
		const int di[]={-1,1,0,0},dj[]={0,0,-1,1};
		
		queue<tuple<int,int,int,int,int>> q; // (i,j,dir,used p,used q)
		rep(i,h) rep(j,w) if(grid[i][j]=='S')
			q.emplace(i+1,j,1,0,0);
		
		while(q.size()){
			int ci,cj,cd,cp,cq; tie(ci,cj,cd,cp,cq)=q.front(); q.pop();
			if(ci<0 || h<=ci || cj<0 || w<=cj ||
			   grid[ci][cj]=='#' || cp>m || cq>m || vis[ci][cj][cd][cp][cq])
				continue;
			if(grid[ci][cj]=='S' && cd==0) continue; // Sを北向きに通過することはできない
			vis[ci][cj][cd][cp][cq]=1;
			
			q.emplace(ci+di[cd],cj+dj[cd],cd,cp,cq);
			if(grid[ci][cj]=='S') continue;
			int nd=3-cd; q.emplace(ci+di[nd],cj+dj[nd],nd,cp+1,cq);
			nd=(cd+2)%4; q.emplace(ci+di[nd],cj+dj[nd],nd,cp,cq+1);
		}
		
		int res=INF;
		rep(i,h) rep(j,w) if(grid[i][j]=='G')
			rep(d,4) rep(p,m+1) rep(q,m+1) if(vis[i][j][d][p][q])
				res=min(res,p+q);
		cout<<(res<INF?res:-1)<<endl;
	}
}

Measured memory_bytes: 20508
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string a;
  cin >> a;
  int r = 1;
for(int i = 0;i < a.size();i++){
  if((i%2==0 && a.at(i)=='L') || (i%2==1 && a.at(i)=='R'))r = 0;
}
  if(r==1)cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
const int MOD = 1000000007;

void solve() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  vi e(n);
  vi w(n);
  e[n-1] = 0;
  w[0] = 0;
  int ans = INF;
  rep(i, n-1) {
    char c1 = s[i];
    char c2 = s[n - 1 - i];
    w[i+1] = w[i] + ((c1 == 'W') ? 1 : 0);
    e[n - 1 - i - 1] = e[n - 1 - i] + ((c2 == 'E') ? 1 : 0);
  }
  rep(i,n) {
    chmin(ans, e[i] + w[i]);
  }
  cout << ans << endl;
}

int main() {
  solve();
  return 0;
}

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

#define int long long

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

  int N;
  int H, W;  
  string s;

  cin >> N;

  int M;
  cin >> M;
  
  vector<int> A(N, 0);
  vector<int> B(N, 0);  
  int ans = 0;

  map<int, int> c;
  for ( int i = 0; i < N; i++ ) {
    int a;
    cin >> a;
    c[a]++;
  }
  for ( int i = 0; i < M; i++ ) {
    int a;
    cin >> a;
    c[a]++;
  }

  int ans1 = 0, ans2 = 0;  
  for ( pair<int, int> a : c ) {
    if ( a.second == 2 ) ans1++;    
  }

  for ( pair<int, int> a : c ) {
    if ( a.second >= 1 ) ans2++;    
  }

  cout << ans1 << " " << ans2 << endl;
  for ( pair<int, int> a : c ) {
    if ( a.second == 2 ) cout << a.first << endl; 
  }

  for ( pair<int, int> a : c ) {
    if ( a.second >= 1 ) cout << a.first << endl;
  }
  
  return 0;
}



Measured memory_bytes: 18108
/*
AizuOnline A0256
Title
@kankichi573
*/
#include <stdio.h>

main()
{
        int i,pts,sum;
        for(i=0,sum=0;i<10;i++)
        {
                scanf("%d",&pts);
                sum += pts;
        }
        printf("%d\n",sum);
        return(0);
}

Measured memory_bytes: 596
map$q[$_]+=$q[$N]/@$N,@{/ /,push@
$`,$' for<>;$N=$_}for++$q[1]..<>;$e[$N]=1+${$b=0;$b+=$_/@@for@@=@e[@$N];b},$a<($~=$q[$N]*=$#@&&($b-(sort@@)[-1])/$#@)or$a=$~while--$N;print"@e"+$a

Measured memory_bytes: 42368
#include<iostream>
using namespace std;
int main () {
  long long a, b, c, d;
  cin >> a >> b >> c >> d;
  if ((a*c>=a*d)&&(a*c>=b*d)&& (a*c>=b*c)) {
    cout << a*c << endl;
  }
  else if ((a*d>=a*c)&&(a*d>=b*d)&& (a*d>=b*c)){
    cout << a*d << endl;
  }
  else if ((b*d>=a*c)&&(b*d>=a*d)&& (b*d>=b*c)){
    cout << b*d << endl;
  }
  else {
  cout << b*c << endl;
  }
return 0;
}


Measured memory_bytes: 3620
#include <stdio.h>

int gcd(int x, int y)
{
  if(y == 0) {
    return x;
  }
  else {
    return gcd(y, x%y);
  }
}

int main(void)
{
  long long int a, b;

  scanf("%lld %lld", &a, &b);

  printf("%lld\n", a*b/gcd(a,b));

  return 0;
}

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

A = [[] for _ in range(8)]
a,b,c,d,e,f,g = list("abcdefg")
o = "."
A[3] = [[o,a,a],
        [b,o,o],
        [b,o,o]]
A[4] = [[a,a,b,c],
        [d,d,b,c],
        [b,c,a,a],
        [b,c,d,d]]
A[5] = [[o,o,a,b,c],
        [o,o,a,b,c],
        [a,a,d,d,e],
        [b,b,f,o,e],
        [c,c,f,g,g]]
A[6] = [[o,a,a,c,c,d],
        [b,o,o,e,o,d],
        [b,o,o,e,f,f],
        [c,c,d,o,a,a],
        [e,o,d,b,o,o],
        [e,f,f,b,o,o]]
A[7] = [[o,o,o,o,a,b,a],
        [o,o,o,o,a,b,a],
        [o,o,o,o,b,a,b],
        [o,o,o,o,b,a,b],
        [a,a,b,b,o,c,c],
        [b,b,a,a,d,o,o],
        [a,a,b,b,d,o,o]]


if N == 2:
  print(-1)
  exit()
if N == 3:
  for i in range(3):
    print("".join(A[3][i]))
  exit()

D = [[o] * N for _ in range(N)]
div, mod = divmod(N, 4)

for i in range(div - 1):
  x = i * 4
  for j in range(4):
    for k in range(4):
      D[x + j][x + k] = A[4][j][k]

x = (div - 1) * 4
for i in range(4 + mod):
  for j in range(4 + mod):
    D[x + i][x + j] = A[4 + mod][i][j]

for i in D:
  print("".join(i))

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

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

typedef long long ll;
typedef pair<int, int> p;

long long comb(int n, int r) {
  if(r > n - r) r = n - r; // because C(n, r) == C(n, n - r)
  long long ans = 1;

  for(int i = 1; i <= r; i++) {
    ans *= n - r + i;
    ans /= i;
  }

  return ans;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<ll> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }
  vector<ll> sum(n+1, 0);

  map<ll, ll> mp;
  mp[0]++;
  for (int i = 0; i < n; i++) {
    sum[i+1] = v[i] + sum[i];
    mp[sum[i+1]]++;
  }

  ll res = 0;
  for(auto a : mp){
    if(a.second >= 2) res += comb(a.second, 2);
  }
  cout << res << endl;

}


Measured memory_bytes: 15872
#include<bits/stdc++.h>
using namespace std;
const long long INF=1000000000;
typedef long long ll;
int main(){
    string s,t;
    cin >> s >> t;
    int rs[26],rt[26];
    for (int i = 0; i < 26;i++){
        rs[i]=-1;
        rt[i] = -1;
    }
    for (int i = 0; i < s.size();i++){
        rs[s[i] - 'a']++;
        rt[t[i] - 'a']++;
    }
    sort(begin(rs),end(rs));
    sort(begin(rt), end(rt));
    for (int i = 0;i<26;i++){
        if(rs[i]!=rt[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

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

int main(){
    int a,b;
    cin>>a>>b;
    if(a==1)a=14;
    if(b==1)b=14;
    if(a<b){
     cout<<"Bob"<<endl;   
    }else if(a==b){
     cout<<"Draw"<<endl;   
    }else{
       cout<<"Alice"<<endl;
    }
    return 0;
}

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

int main() {

    long N;

    cin >> N;

    // N = A * B
    // B = N / A
    
    // A , B 桁数大きい方の、最小値
    long ans = 100000000;

    double d = sqrt(N) + 1;
    //cout << "d: " << d << endl;

    for (long i = 1; i < d ; i++) {
        long a = i;

        //整数チェック
        if (N % a != 0){
            continue;
        }
        long b = N / a;

        //cout << "a: " << a << "   b: " << b << endl;
        string s_a = to_string(a);
        int k_a = s_a.size();
        string s_b = to_string(b);
        int k_b = s_b.size();

        int m = max(k_a, k_b);

        if (ans > m){
            ans = m;
        }
    }

    cout << ans << endl;

    return 0;

}

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

#define rep(i, n) for(long long i=0;i<(long long)(n);i++)
#define rep2(i, s, n) for(long long i=(s);i<(long long)(n);i++)
#define repi(i, n) for(int i=0;i<(int)(n);i++)
#define rep2i(i, s, n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(), v.end()

#define deg2rad(deg) (((deg)/360)*2*M_PI)
#define rad2deg(rad) (((rad)/2/M_PI)*360)

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

const ll INF = (1LL<<60);
const int INFi = (1<<29);

/*素数判定*/
bool is_prime(ll n){
    if(n==1) return false;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0) return false;
    }
    return true;
}

/*約数列挙*/
vll enum_divisors(ll n){
    vll l;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            l.push_back(i);
            if(n/i != i) l.push_back(n/i);
        }
    }
   sort(all(l));
   return l;
}

/*素因数分解*/
vector<P> prime_factorize(ll n){
    vector<P> l;
    for(ll i=2;i*i<=n;i++){
        if(n%i!=0) continue;
        ll e = 0;
        while(n%i==0){
            e++;
            n /= i;
        }
        l.push_back({i, e});
    }
    if(n!=1) l.push_back({n, 1});
    return l;
}

/*最小公倍数*/
ll lcm(ll a, ll b){
    return a*b/__gcd(a,b);
}

/*最大公約数*/
ll gcd(ll a, ll b){
    return __gcd(a,b);
}

int main(){

    ll n, m; cin >> n >> m;
    vll to_1, to_n;
    ll a, b;
    rep(i, m){
        cin >> a >> b;
        if(a==1){
            to_1.push_back(b);
        }
        if(b==1){
            to_1.push_back(a);
        }
        if(a==n){
            to_n.push_back(b);
        }
        if(b==n){
            to_n.push_back(a);
        }
    }

    sort(all(to_1));
    sort(all(to_n));

    for(auto x:to_1){
        if(binary_search(all(to_n), x)){
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;
    return 0;
}

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

typedef long long ll;
typedef pair<int, int> ii;

double a, b, h, m;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> a >> b >> h >> m;

  double pi = atan(1) * 4;
  double tp = pi * 2;
  double ang1 = m / 60 * tp;
  double ang2 = h / 12 * tp + tp / 12 * m / 60;
  double ang = fabs(ang1 - ang2);
  ang = min(ang, tp - ang);
  double c = sqrt(a * a + b * b - 2 * a * b * cos(ang));
  cout << setprecision(20) << fixed << c << endl;
  
  return 0;
}


Measured memory_bytes: 4216
n, m = map(int, input().split())
p = 1 << n
dp = [float('inf')] * p
dp[0] = 0
for i in range(m):
  a, b = map(int, input().split())
  c = sum([1 << j - 1 for j in list(map(int, input().split()))])
  for k in range(p):
    if dp[k|c] > dp[k] + a:
      dp[k|c] = dp[k] + a
      
if dp[-1] == float('inf'):
  print(-1)
else:
  print(dp[-1])

Measured memory_bytes: 3188
import fractions
def prime_factorize(n):
	a = []
	while n % 2 == 0:
		a.append(2)
		n //= 2
	f = 3
	while f * f <= n:
		if n % f == 0:
			a.append(f)
			n //= f
		else:
			f += 2
	if n != 1:
		a.append(n)
	return a

a, b = map(int, input().split())
ab = prime_factorize(fractions.gcd(a, b))
AB = []
for i in ab :
	if i in AB : continue
	AB.append(i)
print(len(AB) + 1)

Measured memory_bytes: 5048
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
int main()
{
    long long int n,a=1,b,i,j,sum=0;
    //string s,s1;
    cin>>n;
    int nm[n+2],nm2[n+2];
    for(i=1;i<=n;i++)
    {
        cin>>b;
        nm[i]=b;
        nm2[b]=i;
    }
   // sort(nm2,nm+n);
    for(i=1;i<=n ;i++)
    {
        cout<<nm2[i]<<" ";
    }
   // sort(nm2,nm+n);

    return 0;
}


Measured memory_bytes: 1536
function main(input) {
  var N = input[0].split(" ")[0]-0;
  var K = input[0].split(" ")[1]-0;

  var map = {};
  var maxsame = 0;
  var min = max = input[1];
  for(var i=1;i<=N;i++){
    var t = input[i]-0;
    if(!map[t])map[t] = 1;
    else map[t]++;
    maxsame = Math.max(maxsame, map[t]);
    min = Math.min(t, min);
    max = Math.max(t, max);
  }
  if(maxsame>=K) console.log(0);
  else{
    var ans = max-min;
    var keys = Object.keys(map).sort((a,b)=>a-b);
    var nummap = [];
    nummap[-1] = 0;
    nummap[0] = map[keys[0]];
    for(var i=1;i<keys.length;i++){
      nummap[i] = map[keys[i]] + nummap[i-1];
    }
    start:for(var i=0;i<keys.length;i++){
      var first = keys[i];
      var tmpnum = map[first];
      var lastIdx = bsearch(nummap, K+nummap[i-1], i);
      if(lastIdx>=keys.length) continue;
      var last = keys[lastIdx];
      ans = Math.min(last-first, ans);
    }
    console.log(ans);
  }
}

function bsearch(arr, targ, min, max){
  var min=min||0,max=max||arr.length;
  var mid = ~~((min+max)/2);
  while(min<max){
    mid = ~~((min+max)/2);
    if(arr[mid]<targ){
      min = mid+1;
    }else if(arr[mid]>targ){
      max = mid-1;
    }else{
      return mid;
    }
  }
  return max;
}

main(require('fs').readFileSync('/dev/stdin', 'utf8').trim().split("\n"))


Measured memory_bytes: 40856
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		int a;
		int b = 0;
		int c = 0;
		int s = 0;
		Scanner scan = new Scanner(System.in);
		a = scan.nextInt();
		b = scan.nextInt();
		c = scan.nextInt();

		if(a>b){
			s = a;
			a = b;
			b = s;
		}
		if(b>c){
			s = b;
			b = c;
			c = s;
		}
		if(a>b){
			s = a;
			a = b;
			b = s;
		}
		System.out.println(a + " " + b + " " + c);
	}

}

Measured memory_bytes: 26160
/**
 *		author:  zvm
 *		created: 25.09.2020 17:10:36
**/

#include <bits/stdc++.h>

using namespace std ;

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

	string s ;
	cin >> s ;
	
	int max_consecutive = 0 ;

	for( int i = 1, now = 1 ; i < s.size() ; ++i ) {
		now = ( s[i] == s[i-1] ? now+1 : 1 );
		max_consecutive = max( max_consecutive, now );
	}

	cout << ( max_consecutive >= 3 ? "Yes" : "No" ) << endl ;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

void solve() {
	int n;
	map<int, bool> m;
	cin >> n;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (m[a]) {
			m[a] = false;
		}
		else {
			m[a] = true;
		}
	}
	for (auto x : m) {
		cnt += (x.second);
	}
	cout << cnt;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
	int T = 1; 
    //cin >> T;
    while(T--) solve();
}

Measured memory_bytes: 4992
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

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

    static class TaskC {
        public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            int[] cnt = new int[100001];

            for (int i = 0; i < n; ++i) {
                int x = in.nextInt();
                cnt[x]++;
                if (x > 0)
                    cnt[x - 1]++;
                cnt[x + 1]++;
            }

            int ans = 0;
            for (int i = 0; i <= 100000; ++i) {
                ans = Math.max(ans, cnt[i]);
            }

            out.println(ans);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

    }
}



Measured memory_bytes: 33812
A = int(input())
B = int(input())
C = int(input())
X = int(input())


count = 0
for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if(500*i + 100*j + 50*k == X):
                count += 1
print(count)


Measured memory_bytes: 3060
from itertools import accumulate

N, *A = map(int, open(0).read().split())

S = list(accumulate(A))

ans = 1
cur = 1
for a, s in zip(A, S):
    if (cur := min(2 * (cur - a), S[-1] - s)) < 0:
        print(-1)
        quit()

    ans += cur

print(ans)

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

int n, k, a[200004], ans;

int main(){
	cin >> n >> k;
	for (int i=0;i<n;i++) cin >> a[i];
	int l=1, r=1e9;
	while (l<=r){
		int mid=(l+r)/2;
		int cnt=0;
		for (int i=0;i<n;i++) cnt+=(a[i]+mid-1)/mid-1;
//		cout << "(length,cut)=(" << mid << "," << cnt << ")\n";
		if (cnt<=k){
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	cout << ans << "\n";
}

Measured memory_bytes: 4356
#include<iostream>
using namespace std;
int main(){
	int n;
	cin >> n;
	for (int i = 1; i < n + 1; i++){
		int x = i;
		if (x % 3 == 0){
			cout << " " << i;
		}
		else{
			while (true){
				if (x % 10 == 3){
					cout << " " << i;
					break;
				}
				x /= 10;
				if (x == 0){
					break;
				}
			}
		}
	}
		cout << endl;
}


Measured memory_bytes: 3084