Programming Solution

Monday, 5 February 2018

http://codeforces.com/problemset/problem/69/A

A guy named Vasya attends the final grade of a high school. One day Vasya decided to watch a match of his favorite hockey team. And, as the boy loves hockey very much, even more than physics, he forgot to do the homework. Specifically, he forgot to complete his physics tasks. Next day the teacher got very angry at Vasya and decided to teach him a lesson. He gave the lazy student a seemingly easy task: You are given an idle body in space and the forces that affect it. The body can be considered as a material point with coordinates (0; 0; 0). Vasya had only to answer whether it is in equilibrium. "Piece of cake" — thought Vasya, we need only to check if the sum of all vectors is equal to 0. So, Vasya began to solve the problem. But later it turned out that there can be lots and lots of these forces, and Vasya can not cope without your help. Help him. Write a program that determines whether a body is idle or is moving by the given vectors of forces.

Input

The first line contains a positive integer n (1 ≤ n ≤ 100), then follow n lines containing three integers each: the xi coordinate, the yicoordinate and the zi coordinate of the force vector, applied to the body ( - 100 ≤ xi, yi, zi ≤ 100).

Output

Print the word "YES" if the body is in equilibrium, or the word "NO" if it is not.

Examples

input
3
4 1 7
-2 4 -1
1 -5 -3

output
NO

input
3
3 -1 7
-5 2 -4
2 -1 -3

output
YESPython 3 code:n=int(input())
aa=bb=cc=0for i in range(n):
    a,b,c=map(int,input().split())
    aa+=a
    bb+=b
    cc+=c
if(aa==bb==cc==0):
    print("YES")
else:
    print("NO")

Saturday, 3 February 2018

codeforces.com/problemset/problem/4/ A. Watermelon

One hot summer day Pete and his friend Billy decided to buy a watermelon. They chose the biggest and the ripest one, in their opinion. After that the watermelon was weighed, and the scales showed w kilos. They rushed home, dying of thirst, and decided to divide the berry, however they faced a hard problem.

Pete and Billy are great fans of even numbers, that's why they want to divide the watermelon in such a way that each of the two parts weighs even number of kilos, at the same time it is not obligatory that the parts are equal. The boys are extremely tired and want to start their meal as soon as possible, that's why you should help them and find out, if they can divide the watermelon in the way they want. For sure, each of them should get a part of positive weight.

Input

The first (and the only) input line contains integer number w (1 ≤ w ≤ 100) — the weight of the watermelon bought by the boys.

Output

Print YES, if the boys can divide the watermelon into two parts, each of them weighing even number of kilos; and NO in the opposite case.

Examples

input
8

output
YES

Note

For example, the boys can divide the watermelon into two parts of 2 and 6 kilos respectively (another variant — two parts of 4 and 4 kilos).

Python 3 Code:

a=int(input())
if(a%2==0 and a>2):
    print("YES")
else:
    print("NO")

Saturday, 11 November 2017

A. Local Extrema / Educational Codeforces Round 32








A. Local Extrema


time limit per test
1 second


memory limit per test
256 megabytes


input
standard input


output
standard output



You are given an array a. Some element of this array ai is a local minimum iff it is strictly less than both of its neighbours (that is, ai < ai - 1and ai < ai + 1). Also the element can be called local maximum iff it is strictly greater than its neighbours (that is, ai > ai - 1 and ai > ai + 1). Since a1 and an have only one neighbour each, they are neither local minima nor local maxima.

An element is called a local extremum iff it is either local maximum or local minimum. Your task is to calculate the number of local extrema in the given array.



Input

The first line contains one integer n (1 ≤ n ≤ 1000) — the number of elements in array a.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1000) — the elements of array a.



Output

Print the number of local extrema in the given array.



Examples



input
3
1 2 3



output
0



input
4
1 5 2 5



output
2

#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
    long long n,a,b,i,c;
    long long ar[1000];
    while(cin>>n)
    {
        for(i=0; i<n; i++)
        {
            cin>>ar[i];
        }
        c=0;

        for(i=0; i<n; i++)
        {
            //cout<<ar[i]<<endl;
            if(i>0&&i<n-1)
            {
                if((ar[i]>ar[i-1]&&ar[i]>ar[i+1])||((ar[i]<ar[i-1]&&ar[i]<ar[i+1])))
                {
                    c++;
                    //cout<<ar[i]<<" "<<ar[i+1]<<" "<<ar[i-1]<<" "<<i<<endl;
                }
            }
        }
        cout<<c<<endl;
    }
    return 0;
}

Thursday, 20 July 2017

UVA 439 - Knight Moves

Problem:

A friend of you is doing research on the Traveling Knight Problem (TKP)where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy. Of course you know that it is vice versa. So you offer him to write a program that solves the ”difficult” part. Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b

Input

The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a..h) representing the column and a digit (1..8) representing the row on the chessboard.

Output

For each test case, print one line saying ‘ To get from xx to yy takes n knight moves.’.

Sample Input

e2 e4

a1 b2

b2 c3

a1 h8

a1 h7

h8 a1

b1 c3

f6 f6

Sample Output

To get from e2 to e4 takes 2 knight moves.

To get from a1 to b2 takes 4 knight moves.

To get from b2 to c3 takes 2 knight moves.

To get from a1 to h8 takes 6 knight moves.

To get from a1 to h7 takes 5 knight moves.

To get from h8 to a1 takes 6 knight moves.

To get from b1 to c3 takes 1 knight moves.

To get from f6 to f6 takes 0 knight moves.

Code:
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int ,int>
int ar[]= {1, -1, 1, -1, 2, 2, -2, -2};
int br[]= {2, 2, -2, -2, 1, -1, 1, -1};
int vis[20][20];
int cost[20][20];
char c1[10],c2[10];
int bsf(int a1,int b1,int a2,int b2)
{
queue<pii>q;
memset(vis,0,sizeof vis);
// memset(cost,0,sizeof vis);
q.push(pii(a1,b1));
vis[a1][b1]=1;
cost[a1][b1]=0;
while(!q.empty())
{
pii top=q.front();
q.pop();
if(top.first==a2&&top.second==b2)
{
cout<<"To get from "<<c1<<" to "<<c2<<" takes "<<cost[a2][b2]<<" knight moves."<<endl;
return 0;
}
for(int i=0; i<8; i++)
{
int x=top.first+ar[i];
int y=top.second+br[i];
if(x>0&&x<=8&&y>0&&y<=8&&vis[x][y]==0)
{
q.push(pii(x,y));
vis[x][y]=1;
cost[x][y]=cost[top.first][top.second]+1;
}
}
}
}
int main()
{
int i,j,a1,a2,b1,b2;

while(cin>>c1>>c2)
{
a1=c1[0]-96;
b1=c1[1]-'0';
a2=c2[0]-96;
b2=c2[1]-'0';
bsf(a1,b1,a2,b2);
//cout<<a1<<" "<<b1<<" "<<a2<<" "<<b2<<endl;
}
return 0;
}

Monday, 17 July 2017

UVA 10305 - Ordering Tasks

John has n tasks to do. Unfortunately, the tasks are not independent and the execution of one task is only possible if other tasks have already been executed.

Input

The input will consist of several instances of the problem. Each instance begins with a line containing two integers, 1<=n<=100 and

m.n is the number of tasks (numbered from 1 to n) and m is the number of direct precedence relations between tasks. After this, there will be

m lines with two integers i and j , representing the fact that task i must be executed before task j . An instance with n = m= 0 will nish the input.

Output

For each instance, print a line with n integers representing the tasks in a possible order of execution.
Sample Input

5 4

1 2

2 3

1 3

1 5

0 0

Sample Output

1 4 2 5 3

MY accepted code Code:

#include<bits/stdc++.h>

using namespace std;

long long visited[100];

vector <int> grp[200];

map<int,int>vis;

stack<int>st;

int n;

int topologicalSortUtill(int v)

{

vis[v] = 1;

int l=grp[v].size();

int u;

for(int i=0; i<l; i++)

{

u=grp[v][i];

if (!vis[u])

topologicalSortUtill(u);

}

st.push(v);

}

int topologicalSort()

{

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

vis[i]=0;

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

if(vis[i]==0)

topologicalSortUtill(i);

int c=0;

while(st.empty()==0)

{

c++;

cout<<st.top();

if(c<n)

cout<<" ";

st.pop();

}

cout<<endl;

}

int main()

{

int m,i,j,a,b;

while(cin>>n>>m)

{

if(n==0&&m==0)

break;

for(i=1; i<=m; i++)

{

cin>>a>>b;

grp[a].push_back(b);

}

//for(i=0;i<n;i++)

topologicalSort();

}

return 0;

}

6 6

5 2

5 0

4 0

4 1

2 3

3 1

Friday, 14 July 2017

Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals)/B. Keyboard Layouts

Problem:

There are two popular keyboard layouts in Berland, they differ only in letters positions. All the other keys are the same. In Berland they use alphabet with 26 letters which coincides with English alphabet.

You are given two strings consisting of 26 distinct letters each: all keys of the first and the second layouts in the same order.

You are also given some text consisting of small and capital English letters and digits. It is known that it was typed in the first layout, but the writer intended to type it in the second layout. Print the text if the same keys were pressed in the second layout.

Since all keys but letters are the same in both layouts, the capitalization of the letters should remain the same, as well as all other characters.

Input

The first line contains a string of length 26 consisting of distinct lowercase English letters. This is the first layout.

The second line contains a string of length 26 consisting of distinct lowercase English letters. This is the second layout.

The third line contains a non-empty string s consisting of lowercase and uppercase English letters and digits. This is the text typed in the first layout. The length of s does not exceed 1000.

Output

Print the text if the same keys were pressed in the second layout.

Examples

input
qwertyuiopasdfghjklzxcvbnm
veamhjsgqocnrbfxdtwkylupzi
TwccpQZAvb2017

output
HelloVKCup2017

input
mnbvcxzlkjhgfdsapoiuytrewq
asdfghjklqwertyuiopzxcvbnm
7abaCABAABAcaba7

output
7uduGUDUUDUgudu7

My accepted code is given below:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    char ar[50],br[50];
    string cr;
    long long i,j;
    while(cin>>ar>>br)
    {
        map<char,char>mp;
        for(i=0; i<strlen(ar); i++)
        {
            mp[ar[i]]=br[i];
            mp[ar[i]-32]=br[i]-32;
        }
        /*for(int c=0;c<=25;c++)
        {
            cout<<mp[ar[c]]<<" "<<mp[ar[c]-32]<<endl;
        }*/
        getchar();
        getline(cin,cr);
       //cout<<"x="<<cr<<endl;
//cout<<"x="<<cr<<endl;
long long ll=cr.length();
//cout<<"l="<<ll<<endl;
        for(i=0; i<ll; i++)
        {
            //cout<<i<<endl;
            if((cr[i]>='a'&&cr[i]<='z')||(cr[i]>='A'&&cr[i]<='Z'))
            cout<<mp[cr[i]];
            else
                cout<<cr[i];
        }
        cout<<endl;
    }
    return 0;
}
//abcdefghijklmnopqrstuvwxyz

Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals)/A. Unimodal Array

Problem:

Array of integers is unimodal, if:

it is strictly increasing in the beginning;
after that it is constant;
after that it is strictly decreasing.

The first block (increasing) and the last block (decreasing) may be absent. It is allowed that both of this blocks are absent.

For example, the following three arrays are unimodal: [5, 7, 11, 11, 2, 1], [4, 4, 2], [7], but the following three are not unimodal: [5, 5, 6, 6, 1], [1, 2, 1, 2], [4, 5, 5, 6].

Write a program that checks if an array is unimodal.

Input

The first line contains integer n (1 ≤ n ≤ 100) — the number of elements in the array.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1 000) — the elements of the array.

Output

Print "YES" if the given array is unimodal. Otherwise, print "NO".

You can output each letter in any case (upper or lower).

Examples

input
6
1 5 5 5 4 2

output
YES

input
5
10 20 30 20 10

output
YES

input
4
1 2 1 2

output
NO

input
7
3 3 3 3 3 3 3

output
YES

Note

In the first example the array is unimodal, because it is strictly increasing in the beginning (from position 1 to position 2, inclusively), that it is constant (from position 2 to position 4, inclusively) and then it is strictly decreasing (from position 4 to position 6, inclusively).

My accepted Code is given below:

#include<bits/stdc++.h>
using namespace std;
int main()
{
long long ar[1009],i,j,n,x,temp,f,ff,fff;
while(cin>>n)
{
f=0;
ff=0;
fff=0;
for(i=0;i<n;i++)
{
cin>>x;
if(i==0)
temp=x;
else
{
if((f==-1&&temp<x)||(fff==-1&&temp<x)||(f==-1&&temp==x))
ff=1;
//if()
else if(temp>x)
f=-1;
else if(temp==x)
fff=-1;
// cout<<f<<" "<<ff<<" "<<temp<<" "<<x<<endl;
temp=x;
}

}
if(ff==1)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;

}
return 0;
}

Programming Solution

Monday, 5 February 2018

http://codeforces.com/problemset/problem/69/A

Saturday, 3 February 2018

codeforces.com/problemset/problem/4/ A. Watermelon

Saturday, 11 November 2017

A. Local Extrema / Educational Codeforces Round 32

Thursday, 20 July 2017

UVA 439 - Knight Moves

Monday, 17 July 2017

UVA 10305 - Ordering Tasks

Friday, 14 July 2017

Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals)/B. Keyboard Layouts

Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals)/A. Unimodal Array

Blog Archive

About Me