Domino Principle

http://codeforces.com/problemset/problem/56/E

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Vasya is interested in arranging dominoes. He is fed up with common dominoes and he uses the dominoes of different heights. He put n dominoes on the table along one axis, going from left to right. Every domino stands perpendicular to that axis so that the axis passes through the center of its base. The i-th domino has the coordinate x_i and the height h_i. Now Vasya wants to learn for every domino, how many dominoes will fall if he pushes it to the right. Help him do that.
Consider that a domino falls if it is touched strictly above the base. In other words, the fall of the domino with the initial coordinate x and height h leads to the fall of all dominoes on the segment [x + 1, x + h - 1].

Input

The first line contains integer n (1 ≤ n ≤ 10⁵) which is the number of dominoes. Then follow n lines containing two integers x_i and h_i ( - 10⁸ ≤ x_i ≤ 10⁸, 2 ≤ h_i ≤ 10⁸) each, which are the coordinate and height of every domino. No two dominoes stand on one point.

Output

Print n space-separated numbers z_i — the number of dominoes that will fall if Vasya pushes the i-th domino to the right (including the domino itself).

Sample test(s)

Input

4
16 5
20 5
10 10
18 2

Output

3 1 4 1 

Input

4
0 10
1 5
9 10
15 10

Output

4 1 2 1 

 
Code:
 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
struct node{
    int x,y,p;
}a[maxn];
int n;
int f[maxn],ans[maxn];
bool cmp(node i,node j)
{
    return i.x<j.x;
}
int main()
{
    int i,x,y;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
    scanf("%d%d",&x,&y);
    a[i].x=x;a[i].y=x+y-1;
    a[i].p=i;
    }
    sort(a+1,a+n+1,cmp);
    for(i=n;i>=1;i--){
    f[i]=1;
    for(int j=i+1;j<=n;j+=f[j]){
        if (a[i].y>=a[j].x) f[i]+=f[j];
        else break;
    }
    ans[a[i].p]=f[i];
    }
    for(i=1;i<=n;i++) printf("%d ",ans[i]);
    printf("\n");
    return 0;
}

Corporation Mail

http://codeforces.com/problemset/problem/56/C

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

The Beroil corporation structure is hierarchical, that is it can be represented as a tree. Let's examine the presentation of this structure as follows:

• employee ::= name. | name:employee₁,employee₂, ... ,employee_k.
• name ::= name of an employee

That is, the description of each employee consists of his name, a colon (:), the descriptions of all his subordinates separated by commas, and, finally, a dot. If an employee has no subordinates, then the colon is not present in his description.
For example, line MIKE:MAX.,ARTEM:MIKE..,DMITRY:DMITRY.,DMITRY... is the correct way of recording the structure of a corporation where the director MIKE has subordinates MAX, ARTEM and DMITRY. ARTEM has a subordinate whose name is MIKE, just as the name of his boss and two subordinates of DMITRY are called DMITRY, just like himself.
In the Beroil corporation every employee can only correspond with his subordinates, at that the subordinates are not necessarily direct. Let's call an uncomfortable situation the situation when a person whose name is s writes a letter to another person whose name is also s. In the example given above are two such pairs: a pair involving MIKE, and two pairs for DMITRY (a pair for each of his subordinates).
Your task is by the given structure of the corporation to find the number of uncomfortable pairs in it.

Input

The first and single line contains the corporation structure which is a string of length from 1 to 1000 characters. It is guaranteed that the description is correct. Every name is a string consisting of capital Latin letters from 1 to 10 symbols in length.

Output

Print a single number — the number of uncomfortable situations in the company.

Sample test(s)

Input

MIKE:MAX.,ARTEM:MIKE..,DMITRY:DMITRY.,DMITRY...

Output

3

Input

A:A..

Output

1

Input

A:C:C:C:C.....

Output

6

Code:

#include<iostream>
using namespace std;
    char a;
    int n,res;
    string s[1001];
int main()
{
    while(cin>>a)
    {
 if(a=='.')
 {
     for(int i=0;i<n;i++)
  if(s[i]==s[n])
      res=res+1;
     s[n]="";
     n--;
 }
 else
 {
     if(a==':')
  n=n+1;
     else
     {
  if(a==',')
      n++;
  else
      s[n]+=a;
     }
 }
    }
    cout<<res<<endl;
    return 0;
} 

Spoilt Permutation

http://codeforces.com/problemset/problem/56/B

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Vasya collects coins: he has exactly one coin for every year from 1 to n. Naturally, Vasya keeps all the coins in his collection in the order in which they were released. Once Vasya's younger brother made a change — he took all the coins whose release year dated from l to r inclusively and put them in the reverse order. That is, he took a certain segment [l, r] and reversed it. At that the segment's endpoints did not coincide. For example, if n = 8, then initially Vasya's coins were kept in the order 1 2 3 4 5 6 7 8. If Vasya's younger brother chose the segment [2, 6], then after the reversal the coin order will change to 1 6 5 4 3 2 7 8. Vasya suspects that someone else could have spoilt the permutation after his brother. Help him to find that out. Check if the given permutation can be obtained from the permutation 1 2 ... n using exactly one segment reversal. If it is possible, find the segment itself.

Input

The first line contains an integer n (1 ≤ n ≤ 1000) which is the number of coins in Vasya's collection. The second line contains space-separated n integers which are the spoilt sequence of coins. It is guaranteed that the given sequence is a permutation, i.e. it contains only integers from 1 to n, and every number is used exactly 1 time.

Output

If it is impossible to obtain the given permutation from the original one in exactly one action, print 0 0. Otherwise, print two numbers l r (1 ≤ l < r ≤ n) which are the endpoints of the segment that needs to be reversed to obtain from permutation 1 2 ... n the given one.

Sample test(s)

Input

8
1 6 5 4 3 2 7 8

Output

2 6

Input

4
2 3 4 1

Output

0 0

Input

4
1 2 3 4

Output

0 0

Code:

 #include<iostream>
using namespace std;
int main()
{
    int x,y,n,a[1001];
    cin>>n;
    for(int i=0;i<n;i++)
    {
 cin>>a[i];
    }
    x=0;
    y=n-1;
    while(a[x]==x+1)
    {
 x++;
    }
    while(a[y]==y+1)
    {
 y--;
    }
    if(x>y)
    {
 cout<<"0 0\n";
    }
    else
    {
 for(int i=x;i<=y;i++)
 {
     if(a[i]!=y+x+1-i)
     {
  cout<<"0 0\n";
  return 0;
     }
 }
 cout<<x+1<<" "<<y+1<<endl;
    }
    return 0;
}

A. Bar

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

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

According to Berland laws it is only allowed to sell alcohol to people not younger than 18 years. Vasya's job is to monitor the law's enforcement. Tonight he entered a bar and saw n people sitting there. For every one of them Vasya happened to determine either the age or the drink the person is having. Vasya can check any person, i.e. learn his age and the drink he is having at the same time. What minimal number of people should Vasya check additionally to make sure that there are no clients under 18 having alcohol drinks?
The list of all alcohol drinks in Berland is: ABSINTH, BEER, BRANDY, CHAMPAGNE, GIN, RUM, SAKE, TEQUILA, VODKA, WHISKEY, WINE

Input

The first line contains an integer n (1 ≤ n ≤ 100) which is the number of the bar's clients. Then follow n lines, each describing one visitor. A line either contains his age (an integer from 0 to 1000) or his drink (a string of capital Latin letters from 1 to 100 in length). It is guaranteed that the input data does not contain spaces and other unnecessary separators.
Only the drinks from the list given above should be considered alcohol.

Output

Print a single number which is the number of people Vasya should check to guarantee the law enforcement.

Sample test(s)

Input

5
18
VODKA
COKE
19
17

Output

2

Note

In the sample test the second and fifth clients should be checked.

Code:
a=["ABSINTH", "BEER", "BRANDY", "CHAMPAGNE", "GIN", "RUM", "SAKE", "TEQUILA", "VODKA", "WHISKEY", "WINE"]
x=input()
n=0
for i in range(x):
    y=raw_input()
    if y in a:
    n=n+1
    else:
    j=0;
    for i in y:
        if (i<'0'or i>'9'):
        j=1
    if j==0:
        if(int(y)<18):
        n=n+1
print n

 

The Probability Of Winning

Refer:
http://www.codechef.com/problems/PROB

Proof:
assumption:p(t1,t2,t3)=t1/(t1+t2)
There are two parts to the proof .
1. Coins of type 3 don't matter .
2. Initial draw doesn't matter .

You can prove both the claims by mathematical induction
Proof 1 :
p(t1,t2,t3) = t1/(t1+t2+t3) + t3 / ( t1+t2+t3) * p(t1,t2,t3-1) . ( Statement 1 )
By induction hypothesis ,
p(t1,t2,t3-1) = t1/(t1+t2) .
which proves Statement 1 gives us assumed formula

Proof 2 :
p(t1,t2,t3,t4) = t1/(t1+t2+t3) * p(t1-1,t2,t3,t4-1) + t2/(t1+t2+t3) * p(t1,t2-1,t3,t4-1) + t3/(t1+t2+t3) * p(t1,t2,t3-1,t4-1) . (statement 2)
By induction hypothesis ,
p(t1-1,t2,t3,t4-1) = (t1-1)/(t1-1+t2)
p(t1,t2-1,t3,t4-1) = (t1)/(t1+t2-1)
p(t1,t2,t3-1,t4-1) = (t1)/(t1+t2)
which proves statement 2 gives us assumed formula.

alternative solution:
the logic is split in two parts:

1. t4 has no significance : Note that these tickets are removed randomly, so in some cases the prob of winning will increase and in others it will decrease. Overall, it will have no effect. I was satisfied with this intuition.
2. t3 has no significance : I actually worked this out mathematically. Let r denote the total number of tickets then we can get,
   P[win] = (t1/r)(1 + t3/(r-1) + t3 (t3-1)/((r-1)(r-2)) + ...
   P[loss] = (t2/r)(1 + t3/(r-1) + t3 (t3-1)/((r-1)(r-2)) + ...

Note that the big multiplicative term is same in both and can be replaced by L.
Also P[win] + P[loss] = 1
So, we have
P[win] + P[loss] = (t1/r + t2/r) * L
1 = (t1/r + t2/r) * L
L = r/(t1 + t2)
We can substitute this value of L back in P[win],
P[win] = (t1/r)* (r/(t1+t2))
P[win] = t1 / (t1+t2)

Program:
#include<stdio.h>
#include<math.h>

int main(){
    long long t,a,b,c,d;
 double ans;
 scanf("%lld",&t);
 while(t--){
  scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
  ans = a/(double)(a+b);
  ans = round(ans*10000000)/10000000;
  printf("%0.7f\n",ans);
 }
 return 0;
}


 

Chef and Walking on the rectangle

Refer http://www.codechef.com/problems/CHRECT/

 

Solution:

/*Chef and Walking on the rectangle*/

#include<stdio.h>

int main()
{
    int K,M,N,T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d %d",&N,&M,&K);
        if(((N==1) && (M<=2)) || ((N<=2) && (M==1)))
            printf("0\n");
        else if((N==1) || (M==1))
            printf("%d\n",K);
        else
            printf("%d\n",(K/2)+(K&1));
    }
    return 0;
}

How to check if a given point lies inside or outside a polygon?

Given a polygon and a point ‘p’, find if ‘p’ lies inside the polygon or not. The points lying on the border are considered inside.


Following is a simple idea to check whether a point is inside or outside.

1)Draw a horizontal line to the right of each point and extend it to infinity.
2) Count the number of times a line intersects the polygon. We have:
    even number ---> point is outside
    odd number ----> point is inside

If point is same as one of the vertices of polygon, then it intersects with two lines.  We explicitly handle it by comparing the point with n vertices of the polygon.

Following is C++ implementation of the above idea.

// A C++ program to check if a given point lies inside a given polygon #include <iostream> #include <limits.h> using namespace std; struct Point { int x; int y; }; // Given three colinear points p, q, r, the function checks if // point q lies on line segment 'pr' bool onSegment(Point p, Point q, Point r) { if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) && q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y)) return true; return false; } // To find orientation of ordered triplet (p, q, r). // The function returns following values // 0 --> p, q and r are colinear // 1 --> Clockwise // 2 --> Counterclockwise 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; // colinear return (val > 0)? 1: 2; // clock or counterclock wise } // The function that returns true if line segment 'p1q1' // and 'p2q2' intersect. bool doIntersect(Point p1, Point q1, Point p2, Point q2) { // Find the four orientations needed for general and // special cases int o1 = orientation(p1, q1, p2); int o2 = orientation(p1, q1, q2); int o3 = orientation(p2, q2, p1); int o4 = orientation(p2, q2, q1); // General case if (o1 != o2 && o3 != o4) return true; // Special Cases // p1, q1 and p2 are colinear and p2 lies on segment p1q1 if (o1 == 0 && onSegment(p1, p2, q1)) return true; // p1, q1 and p2 are colinear and q2 lies on segment p1q1 if (o2 == 0 && onSegment(p1, q2, q1)) return true; // p2, q2 and p1 are colinear and p1 lies on segment p2q2 if (o3 == 0 && onSegment(p2, p1, q2)) return true; // p2, q2 and q1 are colinear and q1 lies on segment p2q2 if (o4 == 0 && onSegment(p2, q1, q2)) return true; return false; // Doesn't fall in any of the above cases } // Returns true if the point p lies inside the polygon[] with n vertices bool isInside(Point polygon[], int n, Point p) { // There must be at least 3 vertices in polygon[] if (n < 3) return false; // Create a point for line segment from p to infinite Point extreme = {INT_MAX, p.y}; // Count intersections of the above line with sides of polygon int count = 0; for (int i = 0; i < n-1; i++) { // If p is same as one of the vertices if (p.x == polygon[i].x && p.y == polygon[i].y) return true; // Otherwise check for intersection if (doIntersect(polygon[i], polygon[i+1], p, extreme)) count++; } // If p is same as last vertex if (p.x == polygon[n-1].x && p.y == polygon[n-1].y) return true; // Last side (from last to first point) is missed in the // above loop, consider it now if (doIntersect(polygon[n-1], polygon[0], p, extreme)) count++; // Return true if count is odd, false otherwise return count&1; // Same as (count%2 == 1) } // Driver program to test above functions int main() { Point polygon[] = {{0, 0}, {10, 0}, {10, 10}, {0, 10}}; int n = sizeof(polygon)/sizeof(polygon[0]); Point p = {20, 20}; isInside(polygon, n, p)? cout << "Yes \n": cout << "No \n"; p = {5, 5}; isInside(polygon, n, p)? cout << "Yes \n": cout << "No \n"; return 0; }

Output:

No
Yes

Time Complexity: O(n) where n is the number of vertices in the given polygon.
Source:
http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
 

How to check if two given line segments intersect?

Given two line segments (p1, q1) and (p2, q2), find if the given line segments intersect with each other.
Before we discuss solution, let us define notion of orientation. Orientation of an ordered triplet of points in the plane can be
–counterclockwise
–clockwise
–colinear
The following diagram shows different possible orientations of (a, b, c)

Note the word ‘ordered’ here. Orientation of (a, b, c) may be different from orientation of (c, b, a).
How is Orientation useful here?
Two segments (p1,q1) and (p2,q2) intersect if and only if one of the following two conditions is verified
1. General Case:
- (p1, q1, p2) and (p1, q1, q2) have different orientations and
- (p2, q2, p1) and (p2, q2, q1) have different orientations
2. Special Case
- (p1, q1, p2), (p1, q1, q2), (p2, q2, p1), and (p2, q2, q1) are all collinear and
- the x-projections of (p1, q1) and (p2, q2) intersect
- the y-projections of (p1, q1) and (p2, q2) intersect
Examples of General Case:


Examples of Special Case:

Following is C++ implementation based on above idea.

// A C++ program to check if two given line segments intersect #include <iostream> using namespace std; struct Point { int x; int y; }; // Given three colinear points p, q, r, the function checks if // point q lies on line segment 'pr' bool onSegment(Point p, Point q, Point r) { if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) && q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y)) return true; return false; } // To find orientation of ordered triplet (p, q, r). // The function returns following values // 0 --> p, q and r are colinear // 1 --> Clockwise // 2 --> Counterclockwise 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; // colinear return (val > 0)? 1: 2; // clock or counterclock wise } // The main function that returns true if line segment 'p1q1' // and 'p2q2' intersect. bool doIntersect(Point p1, Point q1, Point p2, Point q2) { // Find the four orientations needed for general and // special cases int o1 = orientation(p1, q1, p2); int o2 = orientation(p1, q1, q2); int o3 = orientation(p2, q2, p1); int o4 = orientation(p2, q2, q1); // General case if (o1 != o2 && o3 != o4) return true; // Special Cases // p1, q1 and p2 are colinear and p2 lies on segment p1q1 if (o1 == 0 && onSegment(p1, p2, q1)) return true; // p1, q1 and q2 are colinear and q2 lies on segment p1q1 if (o2 == 0 && onSegment(p1, q2, q1)) return true; // p2, q2 and p1 are colinear and p1 lies on segment p2q2 if (o3 == 0 && onSegment(p2, p1, q2)) return true; // p2, q2 and q1 are colinear and q1 lies on segment p2q2 if (o4 == 0 && onSegment(p2, q1, q2)) return true; return false; // Doesn't fall in any of the above cases } // Driver program to test above functions int main() { struct Point p1 = {1, 1}, q1 = {10, 1}; struct Point p2 = {1, 2}, q2 = {10, 2}; doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; p1 = {10, 0}, q1 = {0, 10}; p2 = {0, 0}, q2 = {10, 10}; doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; p1 = {-5, -5}, q1 = {0, 0}; p2 = {1, 1}, q2 = {10, 10}; doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; return 0; }

Output:

No
Yes
No

Sources:
http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf

Given a set of numbers, find the Length of the Longest Arithmetic Progression (LLAP) in it.

Example:

set[] = {1, 7, 10, 15, 27, 29}
output = 3
The longest arithmetic progression is {1, 15, 29}

For simplicity, we have assumed that the given set is sorted. We can always add a pre-processing step to first sort the set and then apply the below algorithms.

A simple solution is to one by one consider every pair as first two elements of AP and check for the remaining elements in sorted set. To consider all pairs as first two elements, we need to run a O(n^2) nested loop. Inside the nested loops, we need a third loop which linearly looks for the more elements in Arithmetic Progression (AP). This process takes O(n³) time.

Dynamic  Programming algorithm:
Refer the paper http://www.cs.uiuc.edu/~jeffe/pubs/pdf/arith.pdf
Let us first look at
Given a sorted set, find if there exist three elements in Arithmetic Progression or not

algorithm-
The answer is true if there are 3 or more elements in AP, otherwise false.
To find the three elements, we first fix an element as middle element and search for other two (one smaller and one greater). We start from the second element and fix every element as middle element. For an element set[j] to be middle of AP, there must exist elements ‘set[i]‘ and ‘set[k]‘ such that set[i] + set[k] = 2*set[j] where 0 <= i < j and j < k <=n-1.
How to efficiently find i and k for a given j? We can find i and k in linear time using following simple algorithm.
1) Initialize i as j-1 and k as j+1
2) Do following while i >= 0 and j <= n-1
..........a) If set[i] + set[k] is equal to 2*set[j], then we are done.
……..b) If set[i] + set[k] > 2*set[j], then decrement i (do i–-).
……..c) Else if set[i] + set[k] < 2*set[j], then increment k (do k++).

Program:
#include <iostream>
using namespace std;

// The function returns true if there exist three elements in AP
// Assumption: set[0..n-1] is sorted
bool arithmeticThree(int set[], int n)
{
    // One by fix every element as middle element
    for (int j=1; j<n-1; j++)
    {
        // Initialize i and k for the current j
        int i = j-1, k = j+1;

        // Find if there exist i and k that form AP
        // with j as middle element
        while (i >= 0 && k <= n-1)
        {
            if (set[i] + set[k] == 2*set[j])
                return true;
            (set[i] + set[k] < 2*set[j])? k++ : i--;
        }
    }

    return false;
}
 int main()
{
    int set1[] = {1, 7, 10, 15, 27, 29};
    int n1 = sizeof(set1)/sizeof(set1[0]);
    arithmeticThree(set1, n1)? cout << "Yes\n" : cout << "No\n";

    int set2[] = {1, 7, 10, 15, 27, 28};
    int n2 = sizeof(set2)/sizeof(set2[0]);
    arithmeticThree(set2, n2)? cout << "Yes\n" : cout << "No\n";
    return 0;
}
How to extend the above solution for the original problem? algorithm-
If the given set has two or more elements, then the value of LLAP is at least 2.The idea is to create a 2D table L[n][n]. An entry L[i][j] in this table stores LLAP with set[i] and set[j] as first two elements of AP and j > i. The last column of the table is always 2. Rest of the table is filled from bottom right to top left. To fill rest of the table, j (second element in AP) is first fixed. i and k are searched for a fixed j. If i and k are found such that i, j, k form an AP, then the value of L[i][j] is set as L[j][k] + 1. Note that the value of L[j][k] must have been filled before as the loop traverses from right to left columns.

Program:

// C++ program to find Length of the Longest AP (llap) in a given sorted set. #include <iostream> using namespace std; // Returns length of the longest AP subset in a given set int lenghtOfLongestAP(int set[], int n) {     if (n <= 2) return n; //Only valid entries are the entries where j>i     int L[n][n];     int llap = 2; // Initialize the result // Fill entries in last column as 2. There will always be // two elements in AP with last number of set as second // element in AP     for (int i = 0; i < n; i++)         L[i][n-1] = 2; // Consider every element as second element of AP     for (int j=n-2; j>=1; j--)     { // Search for i and k for j         int i = j-1, k = j+1;         while (i >= 0 && k <= n-1)         {             if (set[i] + set[k] < 2*set[j])                 k++; // Before changing i, set L[i][j] as 2             else if (set[i] + set[k] > 2*set[j])             {                 L[i][j] = 2, i--;             }             else             { // Found i and k for j, LLAP with i and j as first two // elements is equal to LLAP with j and k as first two // elements plus 1. L[j][k] must have been filled // before as we run the loop from right side                 L[i][j] = L[j][k] + 1; // Update overall LLAP, if needed                 llap = max(llap, L[i][j]); // Change i and k to fill more L[i][j] values for // current j                 i--;                 k++;             }         } // If the loop was stopped due to k becoming more than // n-1, set the remaining entties in column j as 2         while (i >= 0)         {             L[i][j] = 2;             i--;         }     }     return llap; } int main() {     int set1[] = {1, 7, 10, 13, 14, 19};     int n1 = sizeof(set1)/sizeof(set1[0]);     cout << lenghtOfLongestAP(set1, n1) << endl;     int set2[] = {1, 7, 10, 15, 27, 29};     int n2 = sizeof(set2)/sizeof(set2[0]);     cout << lenghtOfLongestAP(set2, n2) << endl;     int set3[] = {2, 4, 6, 8, 10};     int n3 = sizeof(set3)/sizeof(set3[0]);     cout << lenghtOfLongestAP(set3, n3) << endl;     return 0; }

Output:

4
3
5

Time Complexity: O(n²)
Auxiliary Space: O(n²)

 

Ciel and Dancing

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

Fox Ciel and her friends are in a dancing room. There are n boys and m girls here, and they never danced before. There will be some songs, during each song, there must be exactly one boy and one girl are dancing. Besides, there is a special rule:

• either the boy in the dancing pair must dance for the first time (so, he didn't dance with anyone before);
• or the girl in the dancing pair must dance for the first time.

Help Fox Ciel to make a schedule that they can dance as many songs as possible.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 100) — the number of boys and girls in the dancing room.

Output

In the first line print k — the number of songs during which they can dance. Then in the following k lines, print the indexes of boys and girls dancing during songs chronologically. You can assume that the boys are indexed from 1 to n, and the girls are indexed from 1 to m.

Sample test(s)

Input

2 1

Output

2
1 1
2 1

Input

2 2

Output

3
1 1
1 2
2 2

Note

In test case 1, there are 2 boys and 1 girl. We can have 2 dances: the 1st boy and 1st girl (during the first song), the 2nd boy and 1st girl (during the second song).
And in test case 2, we have 2 boys with 2 girls, the answer is 3.


Program:
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    cout<<n+m-1<<endl;
    for(int i=1;i<=m;i++)
    {
        cout<<"1 "<<i<<endl;
    }
    for(int i=2;i<=n;i++)
    {
        cout<<i<<" 1"<<endl;
    }
    return 0;
}