Problem——50A. Domino piling——Codeforces

/*

ou are given a rectangular board of M × N squares. Also you are given an unlimited number of standard domino pieces of 2 × 1 squares. You are allowed to rotate the pieces. You are asked to place as many dominoes as possible on the board so as to meet the following conditions:

Each domino completely covers two squares.
No two dominoes overlap.
Each domino lies entirely inside the board. It is allowed to touch the edges of the board.

Find the maximum number of dominoes, which can be placed under these restrictions.

Input

In a single line you are given two integers M and N — board sizes in squares (1 ≤ M ≤ N ≤ 16).

Output

Output one number — the maximal number of dominoes, which can be placed.

*/

#include <bits/stdc++.h>

using namespace std;

int main(){

long int n,m;

while(cin >> n >> m){

cout << n*m/2 << endl;

}

return 0;

}

Next Round(codeforces)

/*

"Contestant who earns a score equal to or greater than the k-th place finisher's score will advance to the next round, as long as the contestant earns a positive score..." — an excerpt from contest rules.

A total of n participants took part in the contest (n ≥ k), and you already know their scores. Calculate how many participants will advance to the next round.

Input

The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 50) separated by a single space.

The second line contains n space-separated integers a1, a2, ..., an (0 ≤ ai ≤ 100), where ai is the score earned by the participant who got the i-th place. The given sequence is non-increasing (that is, for all i from 1 to n - 1 the following condition is fulfilled: ai ≥ ai + 1).

Output

Output the number of participants who advance to the next round.

Examples

*/

#include <bits/stdc++.h>

using namespace std;

int main(){

int n,k,i,cnt = 0;

scanf("%d %d",&n,&k);

int arr[n];

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

scanf("%d",&arr[i]);

}

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

if(arr[i] == 0)

continue;

if(arr[i] >= arr[k-1])

cnt++;

}

printf("%d",cnt);

return 0;

}

Team(codeforces)

/*

One day three best friends Petya, Vasya and Tonya decided to form a team and take part in programming contests. Participants are usually offered several problems during programming contests. Long before the start the friends decided that they will implement a problem if at least two of them are sure about the solution. Otherwise, the friends won't write the problem's solution.

This contest offers n problems to the participants. For each problem we know, which friend is sure about the solution. Help the friends find the number of problems for which they will write a solution.

Input

The first input line contains a single integer n (1 ≤ n ≤ 1000) — the number of problems in the contest. Then n lines contain three integers each, each integer is either 0 or 1. If the first number in the line equals 1, then Petya is sure about the problem's solution, otherwise he isn't sure. The second number shows Vasya's view on the solution, the third number shows Tonya's view. The numbers on the lines are separated by spaces.

Output

Print a single integer — the number of problems the friends will implement on the contest.

*/

#include <bits/stdc++.h>

using namespace std;

int main(){

int n,petya,vasya,tonya;

scanf("%d",&n);

int cnt = 0;

while(n--){

int count = 0;

scanf("%d %d %d",&petya,&vasya,&tonya);

if(petya == 1)

count++;

if(vasya == 1)

count++;

if(tonya == 1)

count++;

if(count >= 2)

cnt++;

}

printf("%d\n",cnt);

return 0;

}

Way Too Long Words(codeforces)

/*

Sometimes some words like "localization" or "internationalization" are so long that writing them many times in one text is quite tiresome.

Let's consider a word too long, if its length is strictly more than 10 characters. All too long words should be replaced with a special abbreviation.

This abbreviation is made like this: we write down the first and the last letter of a word and between them we write the number of letters between the first and the last letters. That number is in decimal system and doesn't contain any leading zeroes.

Thus, "localization" will be spelt as "l10n", and "internationalization» will be spelt as "i18n".

You are suggested to automatize the process of changing the words with abbreviations. At that all too long words should be replaced by the abbreviation and the words that are not too long should not undergo any changes.

Input

The first line contains an integer n (1 ≤ n ≤ 100). Each of the following n lines contains one word. All the words consist of lowercase Latin letters and possess the lengths of from 1 to 100 characters.

Output

Print n lines. The i-th line should contain the result of replacing of the i-th word from the input data.

*/

#include <bits/stdc++.h>

using namespace std;

int main(){

int n;

char line[100];

scanf("%d",&n);

while(n--){

scanf("%s",line);

int t = strlen(line);

if(t<=10)

printf("%s\n",line);

else

printf("%c%d%c\n",line[0],t-2,line[t-1]);

}

return 0;

}

Theatre Square(codeforces)

/*

Theatre Square in the capital city of Berland has a rectangular shape with the size n × m meters. On the occasion of the city's anniversary, a decision was taken to pave the Square with square granite flagstones. Each flagstone is of the size a × a.

What is the least number of flagstones needed to pave the Square? It's allowed to cover the surface larger than the Theatre Square, but the Square has to be covered. It's not allowed to break the flagstones. The sides of flagstones should be parallel to the sides of the Square.

Input

The input contains three positive integer numbers in the first line: n, m and a (1 ≤ n, m, a ≤ 109).

Output

Write the needed number of flagstones.

*/

Source code:

#include <bits/stdc++.h>

using namespace std;

int main(){

unsigned long long n, m, a = 1;

unsigned long long na, ma, res = 0;

scanf("%llu %llu %llu", &n, &m, &a);

na = n/a;

if (n%a != 0)

na++;

ma = m/a;

if (m%a != 0)

ma++;

res = na * ma;

printf("%llu", res);

return 0;

}

first codeforces(A. Watermelon)

#include <bits/stdc++.h>

using namespace std;

int main()

{

int w;

scanf("%d",&w);

if(w%2==0 && w!=2)

{

printf("YES");

}

else

{

printf("NO");

}

return 0;

}

Sieve Of Eratosthenes

#include <bits/stdc++.h>

using namespace std;

//Sieve of Eratosthenes
/**
1  Create a list of consecutive integers from 2 to n: 
   (2, 3, 4, …, n).
2  Initially, let p equal 2, the first prime number.
3  Starting from p2, count up in increments of p and mark 
  * each of these numbers greater than or equal to p2 itself
  * in the list. These numbers will be 
  * p(p+1), p(p+2), p(p+3), etc..
4  Find the first number greater than p in the list that 
  * is not marked. If there was no such number, stop. 
  * Otherwise, let p now equal this number 
  * (which is the next prime), and repeat from step 3.

**/
// C++ program to print all primes smaller than or equal to n
// using Sieve of Eratosthenes 

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 << " "; 
} 
  
// Driver Program to test above function 
int main() 
{ 
    int n = 30; 
    cout << "Following are the prime numbers smaller "
         << " than or equal to " << n << endl; 
    SieveOfEratosthenes(n); 
    return 0; 
} 

Padovan Sequence

#include <bits/stdc++.h>

using namespace std;
/* Padovan Sequence
Padovan Sequence similar to Fibonacci sequence with 
similar recursive structure. The recursive formula is,
  P(n) = P(n-2) + P(n-3)
  P(0) = P(1) = P(2) = 1  
Padovan Sequence: 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21..
For Padovan Sequence:
P(0) = P1 = P2 = 1 ,
P(7) = P(5) + P(4)
     = P(3) + P(2) + P(2) + P(1)
     = P(2) + P(1) + 1 + 1 + 1
     = 1 + 1 + 1 + 1 + 1 
     = 5
  
*/
int P_S(int n){
int n1 = 1,n2 = 1,n3 = 1,next = 1;
for(int i = 3;i<=n ;i++){
    next = n1 + n2;
    n1 = n2;
    n2 = n3;
    n3 = next;
}
return next;
}
int main()
{
 int n;
 cin >> n;
 cout << P_S(n) << endl;
    return 0;
}

Euclid’s lemma

#include <bits/stdc++.h>

using namespace std;
/* If p divides x*y and p is relatively prime to x,
then p must divide y. In the above example, 
5 is relatively prime to 6, therefore it must divide 15.
 */
int main()
{
int a,b,ab,p;
cin >> a >> b >> p;
ab = a*b;
if(ab%p == 0){
    if(a%p == 0 || b%p == 0)
    cout << "YES\n";
    else
    cout << "NO\n";
}
    
    return 0;
}

Catalan Numbers

#include <bits/stdc++.h>

using namespace std;
unsigned long int catalan(unsigned int n){
    //Base Case
    if(n<=1)
    return 1;
    // catalan(n) is the sum of
    // catalan(i)*catalan(n-i-1)
    unsigned long int res = 0;
    for(int i= 0;i<n;i++)
    res += catalan(i) * catalan(n-i-1);
    return res;
}
int main()
{
    for(int i = 0;i<10;i++){
        cout << catalan(i) << " ";
    }
    return 0;
}

Prime_Factors of two numbers in c++.

#include <bits/stdc++.h>

using namespace std;
void primefactors(int n){
    while(n%2 == 0){
        cout << 2 << " ";
        n/=2;
    }
    for(int i=3;i<=sqrt(n);i+=2)
    while(n%i == 0){
        cout << i << " ";
        n/=i;
    }
    if(n>2)
    cout << n << " ";
}
int main()
{
    int n ;
    cin >> n;
    primefactors(n);
    return 0;
}

Uri 1828

#include <stdio.h>

#include <string.h>

int main()

{

int n,i,c;

char aa[]="tesoura", bb[]="papel", cc[]="pedra", dd[]="lagarto", ee[]="Spock";

char a[15],b[15];

scanf("%d",&n);

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

scanf("%s %s",a,b);

if(0 == strcmp(a,b))

printf("Caso #%d: De novo!\n",i);

else if(0== strcmp(a,aa)){

if((0==strcmp(b,bb)) || (0==strcmp(b,dd)))