NewAge's Blog: tháng 4 2019

Thứ Bảy, 27 tháng 4, 2019

Link hay

https://sites.google.com/site/indy256/algo_cpp/diametr
https://www.geeksforgeeks.org/angular-sweep-maximum-points-can-enclosed-circle-given-radius/

Thứ Hai, 22 tháng 4, 2019

SCHOOLWAY - Đường đến trường

Dữ liệu vào: standard input

Dữ liệu ra: standard output

Giới hạn thời gian: 1.0 giây

Giới hạn bộ nhớ: 128 megabyte

Đăng bởi: middlest

Khu phố Dũng sống có n ngôi nhà được đánh số từ 1 đến n và m con đường nối trực tiếp giữa hai ngôi nhà. Tuy là một học sinh lười biếng nhưng dạo này Dũng rất thích đi học, đơn giản là Dũng vừa tán được một bạn nữ gần nhà nên ngày nào cũng phải chở bạn ấy đến trường. Vì là lần đầu tiên có bạn gái nên Dũng rất cưng chiều bạn mình. Và bạn gái Dũng cũng là một người có sở thích kì lạ: Vào những ngày thứ chẵn (thứ Hai, thứ Tư và thứ Sáu), bạn ấy muốn được đưa đến trường qua một số chẵn các con đường, và ngược lại, vào những ngày thứ lẻ (thứ Ba, thứ Năm, thứ Bảy), bạn ấy lại muốn được đưa đến trường qua một số lẻ các con đường. Đặc biệt, bạn gái của Dũng cho biết rằng nhà bạn ấy không phải là trường, đồng thời có thể đi đến trường theo sở thích của bạn ấy. Yêu cầu này khá khó cho Dũng vì cậu ấy rất lười học và tính toán, nhưng cả nguồn sống của Dũng bỗng chốc thu bé lại vừa bằng một cô gái, Dũng muốn nhờ các bạn NTUCoders giúp đỡ mình xem liệu có thể chở bạn gái đến trường theo sở thích của bạn ấy hay không? Hãy giúp Dũng nhé các bạn!
Dữ liệu vào
Dòng đầu là số T - số lượng test trong file input
T nhóm dòng tiếp theo tương ứng với dữ liệu của T test, có cấu trúc như sau:
Dòng thứ nhất ghi 2 số n và m
m dòng tiếp theo, mỗi dòng ghi 2 số u và v với ý nghĩa có đường nối trực tiếp giữa 2 ngôi nhà u và v
Dữ liệu ra
Gồm T dòng, mỗi dòng tương ứng với kết quả của một test: Xuất ra YES nếu tồn tại ít nhất một cách chở bạn gái của Dũng theo sở thích của bạn ấy và NO trong trường hợp ngược lại (trong trường hợp này bạn gái Dũng đã nói dối )
Giới hạn
T <= 100
1 <= n, m <= 10⁴

Ví dụ

input

1
8 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5

output

YES

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

#include <bits/stdc++.h>

using namespace std;

long n, m, T;
int s;
int trace[10007];
vector <int>a[10007];
void DFS(int u, int v)
{
    trace[u]=v;
    for(int i=0; i<a[u].size(); i++)
    {
        int j=a[u][i];
        if(trace[j]) s|= trace[j]==v;
        else DFS(j,3-v);
    }
}
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        int x,y;
        for(int i=1; i<=n; i++)a[i].clear(),trace[i]=0;
        for(int i=1; i<=m; i++)
        {
            cin>>x>>y;
            a[x].push_back(y);
            a[y].push_back(x);
        }
        s=0;
        for(int i=1; i<=n; i++)
        {
            if(!trace[i])
            DFS(i,1);
        }
        cout<<(s ? "YES" : "NO")<<endl;

    }
    return 0;
}

DAYSO6 - Dãy số (OLP Không chuyên 2009)

Dữ liệu vào: standard input

Dữ liệu ra: standard output

Giới hạn thời gian: 1.0 giây

Giới hạn bộ nhớ: 128 megabyte

Đăng bởi: admin

Cho dãy số gồm n số nguyên a₁, a₂, …, a_n. Tìm giá trị lớn nhất của hàm f(i, j, k) = a_i + 2×a_j + 3×a_k với 1≤ i < j < k ≤ n.
Ví dụ: với dãy gồm 5 số -1, 2, -2, -3, 5 thì f(1, 2, 5)= -1 + 2×2 + 3×5 = 18 là lớn nhất.
Dữ liệu nhập:
- Dòng thứ nhất là số nguyên n (3 ≤ n ≤ 10⁵).
- Dòng thứ hai là n số nguyên a₁, a₂, …, a_n mỗi số cách nhau một khoảng trắng (|a_i| ≤ 10⁹)
Dữ liệu xuất:
- Là giá trị lớn nhất của hàm f(i, j, k) tìm được.

Ví dụ

input

5
-1 2 -2 -3 5

output

18

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

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a),_b=(b);i<_b;++i)
using namespace std;
const int maxn = 10 + 1e5;
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int,int> II;

#define fi first
#define se second
long long a[maxn], ma1[maxn], ma2[maxn], ma3[maxn];
int main()
{
#ifndef ONLINE_JUDGE
#define TASK "ABC"
    freopen(TASK".inp","r",stdin);
    freopen(TASK".out","w",stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    ma1[0] = LONG_LONG_MIN;
    for(int i = 1 ;i <= n; ++i)
    {
        cin >> a[i];
        ma1[i] = max(ma1[i-1], a[i]);
    }
    ma2[1] = LONG_LONG_MIN;
    for(int i = 2; i <= n; ++i)
    {
        ma2[i] = ma2[i-1];
        ma2[i] = max(ma2[i], ma1[i-1] + 2 * a[i]);
    }
    ma3[2] = LONG_LONG_MIN;
    for(int i = 3; i <= n; ++i)
    {
        ma3[i] = ma3[i-1];
        ma3[i] = max(ma3[i], ma2[i-1] + 3 * a[i]);
    }
    cout << ma3[n];
    return 0;
}

Cho 1 mang, cac phan tu xuat hien 3 lan, 1 phan tu xuat hien 1 lan. In ra 1 phan tu do

- chuyển các số sang cơ số 3
- định nghĩa phép XOR_base3 (x,y) = (x+y)%3 , với x,y là bit trong base 3 ( gồm 0,1,2 )
- cuối cùng XOR_base3 tất cả các số trong dãy, thu được số cần tìm
/*************************/



#include <bits/stdc++.h>


using namespace std;


 


int Solution(const vector<int> &A)


{


    int ones = 0, twos = 0;


    for(int i = 0; i < A.size(); i++)


    {


        ones = (ones ^ A[i]) & ~twos;


        twos = (twos ^ A[i]) & ~ones;


    }


    return ones;


}


 


int main()


{


 vector<int> a = {6, 1, 3, 3, 3, 6, 6};


 cout << Solution(a);


 return 0;


}

Cho mot mang so nguyen, tim gia tri lon nhat cua A(i)%A(j)

Chef and Dhyey have become friends recently. Chef wants to test Dhyey's intelligence by giving him a puzzle to solve.

The puzzle contains an integer sequence

A_{1}, A_{2}, \dots, A_{N}

. The answer to the puzzle is the maximum of

A_{i} % A_{j}

, taken over all valid

i

j

Help Dhyey solve this puzzle.

Input

The first line of each test case contains a single integer $N$

The second line contains

N

space-separated integers

A_{1}, A_{2}, \dots, A_{N}

Output

For each test case, print a single line containing one integer — the answer to the puzzle.

Constraints

$2 \leq N \leq 10^{5}$

1 \leq A_{i} \leq 10^{9}

for each valid

i

Subtasks

Subtask #1 (30 points):

2 \leq N \leq 1, 000

Subtask #2 (70 points):

2 \leq N \leq 10^{5}

Example Input 1

5  
1 2 3 4 5

Example Output 1

Example Input 2

6  
5 5 5 2 3 8

Example Output 2

Author: 5★raj1238

Editorial: https://discuss.codechef.com/problems/MAXREM

Tags: april19, cakewalk, raj1238

Date Added: 23-03-2019

Time Limit: 1 secs

Source Limit: 50000 Bytes

Languages: C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS

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

#include <algorithm>
#include <cstdio>

int n = 0;
int a[1000005];

using namespace std;

int main() {
    scanf ("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf ("%d", &a[i]);
    }

    struct {
        bool operator()(int a, int b) const {
            return a > b;
        }
    } uporedi;
    sort (a, a + n, uporedi);

    bool help = true;
    int temp = a[0];
    //printf("%d", temp);

    for (int i = 0; i < n; i++) {
        if (a[i] != temp) {
            help = false;
            printf("%d", a[i]);
            break;
        }
    }

    if (help) {
        printf("0");
    }

    return 0;
}

Cho mot so nhi phan, tim luy thua cao nhat cua 2 la uoc cua so nay

Given a binary number (of

N

bits)

X

. Find the highest power of 2 that divides this number.

Note: If the binary number is "100" then the highest power of 2 that divides it is 2 (as

2^{2}

= 4)

Input:

The first line contains N the number of bits in the number
The next line contains a binary number of N bits

Output:

The first and only line contains the max power of 2 that divides the given number

Constraints:

$1 \leq N \leq 10^{5}$

1 \leq X

Sample Input:

5
10100

Sample Output:

Author: 5★kalpitk

Tags: kalpitk

Date Added: 7-04-2019

Time Limit: 1 secs

Source Limit: 50000 Bytes

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

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

int main()
{
    int a;
    cin>>a;
    string s;
    int ans,i;
    cin>>s;
    for(i=s.length()-1;i>=0;i--)
    {
        // cout<<i<<endl;
        if(s[i] == '1')
        {
            // cout<<"specific i"<<i<<endl;
            ans = s.length() - i-1;
            break;
        }
    }
    cout<<ans;
    return 0;
}

Them va xoa 1 phan tu trong cay nhi phan (BST)

Write a program that processes the following queries on a Binary Search Tree:
i x: Insert x in the BST
d x: Delete x from the BST

Input format

Line 1 contains an integer Q, the number of queries
The next Q lines are of the form i x or d x

Output format

For each query, print the position of x in the BST
If the position of a node is p, the positions of its left and right children are 2*p and 2*p+1 respectively
Position of the root node is 1

Test data

1 ≤ N ≤ 10³
-10⁹ ≤ x ≤ 10⁹
1 ≤ position(x) ≤ 2³² - 1
It is guaranteed that there will be no duplicates in the BST

Sample Input


5
i 1
i 2
i 0
d 2
i 3

Sample Output

Explanation


On inserting 1,

1

On inserting 2:

1
 \
  2

On inserting 0:

   1
  / \
 0   2

After deleting 2:

  1
 /
0

On inserting 3:

   1
  / \
 0   3

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

#include <iostream>
using namespace std;
typedef long long ll;


struct node{
    
    ll data, pos;
    struct node *left, *right;
};

node *insert(node *root, ll data, ll pos);
node *deletenode(node *root, ll data);
node *findMax(node *);
node *findMin(node *);
void inorder(node *);
int main() {
 ll q,num;
 char op;
 
 node *root = NULL;

    // root = insert(root, 1, 1);
    // root = insert(root, 2, 1);
    // root = insert(root, 3, 1);
    // root = insert(root, 4, 1);
    // //inorder(root);
    // root = deletenode(root,4);
    //cout<<endl;
    //inorder(root);
    cin>>q;

 while(q-->0){
         
        cin>>op>>num;
        if(op=='i')
           root = insert(root,num,1);
         else
             root = deletenode(root,num);
  }
 
 return 0;
}


node* insert(node *root, ll data, ll pos){

    if(!root){
        cout<<pos<<endl;
        root = new node;
        root->data = data;
        root->pos = pos;
        root->left = root->right = NULL;
        return root;        
    }
    else{
        if(data > root->data){

            root->right = insert(root->right, data, 2*pos+1);
        }
        else{

            root->left = insert(root->left, data, 2*pos);
        }
    }
    
    return root;
}


node* deletenode(node *root, ll data){

 if(!root)
  return root;
 if(root->data >  data){

  root->left = deletenode(root->left, data);
 }
 else if(data > root->data){

  root->right = deletenode(root->right, data);
 }
 else{
        
        cout<<root->pos<<endl;
  if(root->left && root->right){
   node *temp = findMin(root->right);
   root->data = temp->data;
   root->right = deletenode(root->right, temp->data);
  }
  else{
            
   node *temp;
   if(root->left){

    temp = root->left;
       delete root;
       return temp;
   }
   else if(root->right){

    temp =root->right;
    delete root;
    return temp;
   }
   else{
    
    temp = root;
    delete temp;
    return NULL;
   }
   
   
  }

 }


return root; 
 
}




node *findMax(node *root){
    while(root->right)   
    root = root->right;
    return root;
}

void inorder(node *root){

    if(root){

        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);

    }
}

node *findMin(node *root){
    while(root->left)   
    root = root->left;
    return root;
}

Cho một mảng các số nguyên và tìm ước chung nhỏ nhất lớn hơn 1 của mảng

The Little Elephant from the Zoo of Lviv has an array A that consists of N positive integers. Let A[i] be the i-th number in this array (i = 1, 2, ..., N).

Find the minimal number x > 1 such that x is a divisor of all integers from array A. More formally, this x should satisfy the following relations:

A[1] mod x = 0, A[2] mod x = 0, ..., A[N] mod x = 0,

where mod stands for the modulo operation. For example, 8 mod 3 = 2, 2 mod 2 = 0, 100 mod 5 = 0 and so on. If such number does not exist, output -1.

Input

The first line of the input contains a single integer T, the number of test cases. T test cases follow. The first line of each test case contains a single integer N, the size of the array A for the corresponding test case. The second line contains N space separated integers A[1], A[2], ..., A[N].

Output

For each test case output a single line containing the answer for the corresponding test case.

Constraints

1 ≤ T ≤ 100000

1 ≤ N ≤ 100000

The sum of values of N in each test file does not exceed 100000

1 ≤ A[i] ≤ 100000

Example

Input:
2
3
2 4 8
3
4 7 5

Output:
2
-1

Explanation

Case 1. Clearly 2 is a divisor of each of the numbers 2, 4 and 8. Since 2 is the least number greater than 1 then it is the answer.

Case 2. Let's perform check for several first values of x.

x	4 mod x	7 mod x	5 mod x
2	0	1	1
3	1	1	2
4	0	3	1
5	4	2	0
6	4	1	5
7	4	0	5
8	4	7	5
9	4	7	5

As we see each number up to 9 does not divide all of the numbers in the array. Clearly all larger numbers also will fail to do this. So there is no such number x > 1 and the answer is -1.

Author: 4★witua

Editorial: http://discuss.codechef.com/problems/LEDIV

Tags: cook28, simple, simple-math, witua

Date Added: 20-10-2012

Time Limit: 2 secs

Source Limit: 50000 Bytes

Languages: C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS

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

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;cin>>t;
    int s[100005];
    memset(s,0,sizeof(s));
    for(int i=2;i<=100000;i++){
        if(s[i]==0){
            int j=i;
            while(j<=100000){
                if(s[j]==0){
                    s[j]=i;
                }
                j+=i;
            }
        }
    }

    while(t--){
        int n;cin>>n;
        int a[n];
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        int g=a[0];
        for(int i=1;i<n;i++){
            g=__gcd(g,a[i]);
        }
        if(g==1){
            cout<<-1<<endl;
        }
        else{
            cout<<s[g]<<endl;
        }

    }

    return 0;
}

Cho ba tọa độ của một tam giác, tính diện tích

long double area(ll x0,ll y0,ll x1,ll y1,ll x2,ll y2){
long double res=(long double)abs((x0 - x2) * (y1 - y0) - (x0 - x1) * (y2 - y0) ) / 2;
return res;
}

Tính diện tích một đa giác dùng định thức và xác định tính cùng chiều đồng hồ của các đỉnh

#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
using namespace std;
long double determind(ll x1,ll y1,ll x2, ll y2){
   long double res=(x1*y2)-(x2*y1);
   return res;
}
typedef pair<ll,ll> pi;
pi luu[110];
int main(){
ll n,i,x,y;
cin>>n;
long double res=0;
for(i=1;i<=n;i++){
     cin>>x>>y;
     luu[i]=mp(x,y);
}
luu[n+1]=luu[1];
for(i=1;i<=n;i++) res+=determind(luu[i].first,luu[i].second,luu[i+1].first,luu[i+1].second);
if(res>=0){
    cout<<"CCW"<<' ';
    cout<<fixed<<setprecision(1)<<res/2;}
    else {
      cout<<"CW"<<' ';
    cout<<fixed<<setprecision(1)<<-res/2;
    }
    return 0;
}

Convex Hull+ Diện tích bao lồi

struct Point{
long double x,y;
};
long double determind(ld x1,ld y1,ld x2, ld y2){
   long double res=(x1*y2)-(x2*y1);
   return res;
}

Point p0;

Point nextToTop(stack<Point> &S)
{
    Point p = S.top();
    S.pop();
    Point res = S.top();
    S.push(p);
    return res;
}

int swap(Point &p1, Point &p2)
{
    Point temp = p1;
    p1 = p2;
    p2 = temp;
}

int distSq(Point p1, Point p2)
{
    return (p1.x - p2.x)*(p1.x - p2.x) +
          (p1.y - p2.y)*(p1.y - p2.y);
}

int orientation(Point p, Point q, Point r)
{
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);

    if (val == 0) return 0;
    return (val > 0)? 1: 2;
}

int compare(const void *vp1, const void *vp2)
{
   Point *p1 = (Point *)vp1;
   Point *p2 = (Point *)vp2;
   int o = orientation(p0, *p1, *p2);
   if (o == 0)
     return (distSq(p0, *p2) >= distSq(p0, *p1))? -1 : 1;

   return (o == 2)? -1: 1;
}

void convexHull(Point points[], long long n)
{
   int ymin = points[0].y, min = 0;
   for (int i = 1; i < n; i++)
   {
     int y = points[i].y;

     if ((y < ymin) || (ymin == y &&
         points[i].x < points[min].x))
        ymin = points[i].y, min = i;
   }

   swap(points[0], points[min]);

   p0 = points[0];
   qsort(&points[1], n-1, sizeof(Point), compare);

   int m = 1;
   for (int i=1; i<n; i++)
   {

       while (i < n-1 && orientation(p0, points[i],
                                    points[i+1]) == 0)
          i++;

       points[m] = points[i];
       m++;
   }

   if (m < 3) return;

   stack<Point> S;
   S.push(points[0]);
   S.push(points[1]);
   S.push(points[2]);

   for (int i = 3; i < m; i++)
   {

      while (orientation(nextToTop(S), S.top(), points[i]) != 2)
         S.pop();
      S.push(points[i]);
   }

   long double a,b;
   long long cnt=0;
   while (!S.empty())
   {
       Point p = S.top();
       a=p.x;b=p.y;

      luu1[cnt++]=make_pair(a,b);
       S.pop();
}

long double res=0;
luu1[cnt]=luu1[0];
cnt++;
for(int i=0;i<cnt;i++) res+=determind(luu1[i].first,luu1[i].second,luu1[i+1].first,luu1[i+1].second);

res_ngoai=abs(res)/2;
}

(a^b)%c

long long power(long long x,int y)
{
   if (!y)
   return 1;
   long long ret=power(x,y/2);
   ret=(ret*ret)%mod;
   if (y%2)
   ret=(ret*x)%mod;
   return ret;
}

Sàn nguyên tố

void SieveOfEratosthenes(int n) 

{ 

    // Create a boolean array "prime[0..n]" and initialize 

    // all entries it as true. A value in prime[i] will 

    // finally be false if i is Not a prime, else true. 

    bool prime[n+1]; 

    memset(prime, true, sizeof(prime)); 

    for (int p=2; p*p<=n; p++) 

    { 

        // If prime[p] is not changed, then it is a prime 

        if (prime[p] == true) 

        { 

            // Update all multiples of p greater than or  

            // equal to the square of it 

            // numbers which are multiple of p and are 

            // less than p^2 are already been marked.  

            for (int i=p*p; i<=n; i += p) 

                prime[i] = false; 

        } 

    } 

    // Print all prime numbers 

    for (int p=2; p<=n; p++) 

       if (prime[p]) 

          cout << p << " "; 

}