Oj599: sum of two numbers 1

Title Description

Given an array from small to large and a target number t, find two numbers in it, make the sum of the two numbers equal to the target number, and output the position of the two numbers in the array.

input

The first line contains two integers n,t. (1≤n≤1000000,1≤t≤20000000)

The number of n in the next line is less than 10000000.

output

Output two numbers separated by spaces to represent the position (counting from zero), and the answer has a unique solution.

sample input

6 15
1 5 6 7 10 26

sample output

1 4

Data scale and agreement

Time limit: 1 s
Memory limit: 256 M
100% data guarantee 1 ≤ n ≤ 1000000

Idea:

Note: there is a large amount of data, and there is a risk of timeout when reading in with cin. scanf is used

Three methods:
1. Brute force solution: two-layer loop traversal will timeout, time complexity O(n^2)
2. Fix one number and find the other by dichotomy. Time complexity O(nlogn)
3. Hash table: fix one number and look up the other number from the hash table. Time complexity O(n), space complexity O(n)
4. Double finger Needling: time complexity O(n)

Code demonstration (double finger acupuncture)

#include<iostream>
#include <cstdio>
using namespace std;
int n, t, num[1000005];
int main(int argc, char *grav[])
{
    scanf("%d%d", &n, &t);
    for (int i = 0; i < n; i++) {
        scanf("%d", &num[i]);
    }
    int l = 0, r = n - 1;
    while (l < r) {
        if (num[l] + num[r] == t) {
            cout << l << " " << r << endl;
            return 0;
        }
        // If the number is less than the target, move the left pointer
        if (num[l] + num[r] < t) {
            l++;
        } else {
            r--;
        }
    }
    cout << -1 << endl;
    return 0;
}

Extension:

Sum of three numbers: fix one number, and the remaining two adopt the method of sum of two numbers. The time complexity is O(n^2)

Oj600: Young's matrix

Title Description

Given a two-dimensional matrix with n rows and m columns and a target number t, the two-dimensional matrix does not fall from left to right for each row (the number on the right is greater than or equal to the number on the left), and does not fall from top to bottom for each column (the number on the lower side is greater than or equal to the number on the upper side). Now find the target number t in the array and output the number of rows and columns where it is located.

Note: the data of this question has been updated, t has been changed to input at the end, and all submission records that do not meet the requirements have been deleted.

input

The first line contains two integers n, M. (1≤n,m≤3000)

Next, a two-dimensional matrix, in which all numbers are less than 200000.

The last line is an integer t. (1≤t≤200000)

output

Output two numbers separated by spaces to represent the position (counting from the beginning). The answer has a unique solution.

sample input

3 4
1 2 3 4
5 6 15 20
7 10 20 25
15

sample output

2 3

Data scale and agreement

Time limit: 1 s
Memory limit: 256 M
100% data guarantee: 1 ≤ n,m ≤ 3000

Idea:

Time complexity is O(n + m)
The search number can be found from the lower left corner or the upper right corner.

• This problem is related to the sum of the two numbers, as shown in the figure below:
  

Code demonstration:

#include<iostream>
#include <cstdio>
using namespace std;
int n, m, t, num[3005][3005];
int main(int argc, char *grav[])
{
    scanf("%d%d", &n, &m);
    // Save from point (1,1)
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &num[i][j]);
        }
    }
    // Find from the bottom left corner
    int x = n, y = 1;
    cin >> t;
    while (1) {
        if(num[x][y] == t) {
            printf("%d %d\n", x, y);
            return 0;
        }
        if (num[x][y] > t) {
            x--;
        } else {
            y++;
        }
    }
    cout << -1 << endl;
    return 0;
}

Oj479: Table Tennis

Title Description

Since taking office, Shalala, the current president of the International Table Tennis Federation, has been determined to implement a series of reforms to promote the popularity of table tennis in the world. Among them, the 11 point system reform has caused great controversy. Some players can only choose to retire because they can't adapt to the new rules. Hua Hua is one of them. After his retirement, he embarked on the research of table tennis in order to understand the different effects of 11 point system and 21 point system on players. Before carrying out his research, he first needs to analyze the statistical data of his competitions for many years, so he needs your help.

Huahua analyzed by the following methods: first, the victory or defeat of each ball in the game was listed in a table, and then the results of the two sides under the 11 point system and 21 point system were calculated respectively (up to the end of the record).

For example, there is a record (where W means Huahua gets a point and L means Huahua's opponent gets a point):

WWWWWWWWWWWWWWWWWWWWWWLW

Under the 11 point system, the result of the game at this time is that Huahua won 11-0 in the first set and 11-0 in the second set. The third set is under way. The current score is 1-1. Under the 21 point system, Huahua won 21-0 in the first set and is in the second set, with a score of 2-1. If a game has just begun, the score is 0-0. A game does not end until the difference is greater than or equal to 2.

Your program is to input a series of game information (WL form) and output the correct results.

input

Each input file contains several lines of strings, which are composed of uppercase W, L and E. Where EE indicates the end of the competition information, and the program should ignore all contents after E.

output

The output consists of two parts, each part has several lines, and each line corresponds to the score of a game (according to the input order of game information). The first part is the result under the 11 point system, and the second part is the result under the 21 point system. The two parts are separated by a blank line.

sample input

WWWWWWWWWWWWWWWWWWWW
WWLWE

sample output

11:0
11:0
1:1

21:0
2:1

Data scale and agreement

Time limit: 1 s
Memory limit: 256 M
100% data guarantee up to 25 letters per line and up to 2500 lines

Idea:

First, determine the data range:

Code demonstration:

#include<iostream>
#include <cmath>
using namespace std;
int a11[6000][2], a21[3000][2], ind1, ind2;
void p() {
    for (int i = 0; i <= ind1; i++) {
        cout << a11[i][0] << ":" << a11[i][1] << endl;
    }
    cout << endl;
    for (int i = 0; i <= ind2; i++) {
        cout << a21[i][0] << ":" << a21[i][1] << endl;
    }
}
int main(int argc, char *grav[])
{
    char s[30];
    while (cin >> s) {
        for (int i = 0; s[i]; i++) {
            if (s[i] == 'E') {
                p();
                return 0;
            }
            if (s[i] == 'W') {
                a11[ind1][0]++;
                a21[ind2][0]++;
            } else {
                a11[ind1][1]++;
                a21[ind2][1]++;
            }
            if ((a11[ind1][0] >= 11 || a11[ind1][1] >= 11) && abs(a11[ind1][0] - a11[ind1][1]) >= 2) {
                ind1++;
            }
            if ((a21[ind2][0] >= 21 || a21[ind2][1] >= 21) && abs(a21[ind2][0] - a21[ind2][1]) >= 2) {
                ind2++;
            }
        }
    }
    return 0;
}

oj-481. Curling competition

Title Description:

In the curling game, a target point P and a specified positive integer r are given. After teams a and B throw curling 8 times in turn in each game, the game ends. At this time, the curler of that party is finally closest to the target point, and that party scores, while the other party does not score. If the distance between each top of the scoring party and the target point P is less than or equal to r, and the position is closer to the target point P than all the curlers of the other team, 1 point can be obtained.

The game can last up to 10 games. After the end of a game between the two sides, the lagging party can abstain, and the game will not go on at this time. Given the distance between each curler and the target point P and the positive integer r at the end of a game, please write a program to judge the score of each game between the two teams and the total score.

Input:

Line 1 is a positive integer r.

There are several lines (no more than 20) below, with 8 positive integers in each line;

The number J in the second line indicates the distance between the j-th curler of Party A and the target point P at the end of the 11th game;

The number J in the third line indicates the distance between the j curler of Party B and the target point P at the end of the 11th game;

......

The j-th number in line 2k indicates the distance between the j-th curler of Party A and the target point P at the end of the k-th game;

The j-th number in line 2k+1 represents the distance between Party B's j-th curler and the target point P at the end of the k-th game;

If one party abstains halfway, the last line (even line) has only an integer − 1, indicating that the waiver occurs at this time;

Output:

Output several lines, two integers in each line, separated by a colon, indicating the score of Party A and Party B in each game (Party A scores first).

There are two integers in the last line, separated by a colon in the middle, indicating the final score of Party A and Party B in the game (Party A scores first).

Sample input:

8
5 20 18 19 3 15 13 3
20 2 17 12 5 18 10 11
20 3 4 1 2 11 9 2
1 15 19 9 8 14 11 10
15 2 10 1 19 14 3 18
15 17 21 19 24 32 19 26
-1

Sample output:

0:1
0:0
3:0
3:1

Idea:

Draw a circle with the nearest point of the other party from the center of the circle as the radius. There are several balls of the other party in the circle. What points will the other party get.

Code implementation:

#include<iostream>
#include <algorithm>
using namespace std;
int r, ans[15][2];
void p(int n) {
    int a1 = 0, a2 = 0;
    for (int i = 1; i < n; i++) {
        a1 += ans[i][0];
        a2 += ans[i][1];
        cout << ans[i][0] << ":" << ans[i][1] << endl;
    }
    cout << a1 << ":" << a2 << endl;
}
int main(int argc, char *grav[])
{
    cin >> r;
    for (int i = 1; i <= 10; i++) {
        int num1[10] = {0};
        int num2[10] = {0};
        // input data
        for (int j = 0; j < 8; j++) {
            cin >> num1[j];
            // Conditions for withdrawal
            if (num1[j] == -1) {
                p(i); // Midway exit also needs to output results. i indicates the number of rounds
                return 0;
            }
        }
        for (int j = 0; j < 8; j++) {
            cin >> num2[j];
        }
        sort(num1, num1 + 8);
        sort(num2, num2 + 8);
        if (num1[0] < num2[0]) {
            for (int j = 0; j < 8; j++) {
                // Judge whether the boundary conditions are met
                if (num1[j] > r || num1[j] >= num2[0]) break;
                ans[i][0]++; // Record the score of each time
            }
        } else {
            for (int j= 0; j < 8; j++) {
                if (num2[j] > r || num2[j] >= num1[0]) break;
                ans[i][1]++;
            }
        }
    }
    p(11);
    return 0;
}

oj-484. Columnar statistical chart

Title Description:

Give some strings with a total length of no more than 1000, count the number of uppercase letters, and output them according to the given sample format.

Input:

A pile of strings. Every two strings may be separated by spaces and newlines.

Output:

Refer to the sample output columnar statistical chart. Each * indicates one occurrence. Note that there should be no redundant spaces in each line.

Sample input:

ABC ABC.DEF()G GCC XY
354342aaaCaa aaaaaaaabcdbcd

Sample output:

    *
    *
    *
* * *       *
* * * * * * *                                 * *
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Idea:

Open an array, count the number of occurrences of each character, and set the height value according to the maximum number of occurrences

Difficulty: printing

Code implementation:

#include<iostream>
using namespace std;

int num[130];
char str[1005];

int main(int argc, char *grav[])
{
    while (cin >> str) {
        for (int i = 0; str[i]; i++) {
            num[str[i]]++;
        }
    }
    int mmax = 0;
    // How many lines are there
    for (int i = 'A'; i <= 'Z'; i++) {
        mmax = max(mmax, num[i]);
    }
    for (int i = mmax; i > 0; i--) {
        int ind = 'A';
        for (int j = 'Z'; j > 'A'; j--) {
            if (num[j] >= i) {
                ind = j;
                break;
            }
        }
        for (int j = 'A'; j <= ind; j++) {
            if (j != 'A') {
                cout << " ";
            }
            if (num[j] >= i) {
                cout << "*";
            } else {
                cout << " ";
            }
        }
        cout << endl;
    }
    for (char i = 'A'; i <= 'Z'; i++) {
        if (i != 'A') {
            cout << " ";
        }
        cout << i;
    }
    cout << endl;
    return 0;
}

oj-485. Divide cards equally

Title Description:

There are N piles of cards, numbered 1, 2,..., N. There are several cards in each pile, but the total number of cards must be a multiple of N. You can take several cards from any pile and move them.

The card transfer rule is: the cards taken from the stack numbered 1 can only be moved to the stack numbered 2; Cards taken from the stack numbered N can only be moved to the stack numbered N − 1; Cards taken from other stacks can be moved to the adjacent left or right stack.

Now it is required to find a way to move with the least number of times to make the same number of cards on each pile.

For example, N=4, the number of 4 stacks of cards is:

① 9 ② 8 ③ 17 ④ 6

Move 3 times to achieve the purpose:

Take 4 cards from ③ to ④ (9,8,13,10) - > take 3 cards from ③ to ② (9,11,10,10) - > take 1 card from ② to ① (10,10,10).

Input:

The first line is an integer n. (1≤N≤100)

The second line contains N integers, A1,A2,..., An. (N stacks of cards, initial number of cards in each stack, 1 ≤ Ai ≤ 10000)

Output:

Outputs an integer representing the minimum number of moves when all heaps are equal.

Sample input:

4
9 8 17 6

Sample output:

3

Code implementation:

#include<iostream>
using namespace std;

int n, num[105], ans, sum, avg;

int main(int argc, char *grav[])
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num[i];
        sum += num[i];
    }
    avg = sum / n;
    for (int i = 0; i < n - 1; i++) {
        if (num[i] != avg) {
            ans++;
            num[i + 1] += num[i] - avg;
            num[i] = avg;
        }
    }
    cout << ans << endl;
    return 0;
}

oj-504. Deletion number

Title Description:

Enter a high-precision positive integer n (no more than 240 bits in length). After removing any s digits, the remaining digits will form a new positive integer according to the original left-right order. Now find a scheme to minimize the value of the new positive integer.

Input:

The first line is an integer n.

The second line is a positive integer s.

Output:

The output of a number represents the minimum value, and the leading zero of the number is ignored.

Sample input 1:

179566
4

Sample output 1:

15

Code demonstration:

#include<iostream>
#include <string>
using namespace std;
string str;
int n;

int main(int argc, char *grav[])
{
    cin >> str >> n;
    for (int i = 0; i < n; i++) {
        int ind = str.size() - 1;
        for (int j = 0; j < str.size() - 1; j++) {
            if (str[j] > str[j + 1]) {
                ind = j;
                break;
            }
        }
        str.replace(ind, 1, "");
    }
    int f = 0;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] != '0') {
            f = 1;
        }
        if (f == 1) {
            cout << str[i];
        }
    }
    cout << endl;
    return 0;
}

oj-505. Maximum integer

Title Description:

Now there are n positive integers. Connect them in a row to form the largest integer.

For example, there are now three integers 13312343, connected into a maximum integer of 34331213.

Input:

The first line is an integer n. (1≤n≤100000)

The second line contains n positive integers that do not exceed the int type range.

Output:

Outputs a number representing the largest integer of the composition.

Sample input:

3
121 12 96

Sample output:

9612121

Idea:

1. Read in as a string.

2. Sort strings, sort(s, s + n, cmp);

3. How to write cmp?

   bool cmp(string a, string b) {return a + b > b + a;}

Code demonstration:

#include<iostream>
#include <string>
#include <algorithm>
using namespace std;

string s[100005];
int n;

bool cmp(const string &a, const string &b) {
    return a + b > b + a;
}

int main(int argc, char *grav[])
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    sort(s, s + n, cmp);
    for (int i = 0; i < n; i++) {
        cout << s[i];
    }
    cout << endl;
    return 0;
}

oj-508. Two people cross the river

Title Description:

There are n people who want to cross a bridge at night. At any time, there can only be at most two people on the bridge, and you must carry a flashlight to cross the bridge. Now there is only one flashlight, so some order must be arranged so that the flashlight can be taken back to let more people cross the bridge. Everyone has a different time to cross the bridge. The time spent by two people crossing the bridge together is equal to that of the slower one. Now we ask everyone to cross the bridge in the shortest time.

Input:

The first line is an integer n. (1≤n≤1000)

In the next n lines, an integer in each line represents the bridge crossing time ti of the ith person. (1≤Ti≤100)

Output:

Output the shortest time for everyone to cross the bridge

Sample input:

4
1
5
2
10

Sample output:

17

Example description

Let 1 and 2 cross the bridge first, then let 1 come back, let 5 and 10 cross the bridge, and then let 2 come back and cross the bridge with 1. The time is 2 + 1 + 10 + 2 + 2 = 17.

Idea:

• First, sort everyone's time from small to large
• There are several situations as follows:

1. n == 1 ,ans = num[0]
2. n == 2 ,ans = num[1]
3. n == 3 ,ans = num[2] + num[0] + num[1]
4. n == 4 - > n can be selected in two cases: 1. Flashlight block. 2. Cross the river quickly

1. Flashlight fast: slowest and fastest – > fastest – > second slowest and fastest – > fastest

​ num[i] + num[1] + num[i - 1] + num[1]

2. Cross the river fast: fastest second fast – > fastest – > slowest second slow - > second fast

​ num[2] + num[1] + num[i] + num[2]

Code demonstration:

#include<iostream>
#include <algorithm>
using namespace std;

int n, num[1005], ans;

int main(int argc, char *grav[])
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
    }
    sort(num + 1, num + n + 1);
    for (int i = n; i > 0; i -= 2) {
        if (i == 1) {
            ans += num[1];
            break;
        } else if (i == 2) {
            ans += num[2];
        } else if (i == 3) {
            ans += num[3] + num[1] + num[2];
            break;
        } else {
            ans += min(num[i] + num[1] + num[i - 1] + num[1], num[2] + num[1] + num[i] + num[2]);
        }
    }
    cout << ans << endl;
    return 0;
}

oj-513. Floor number

Title Description

Xiao Ming travels and lives in a hotel. The hotel has a cursed number t, which will not appear in the number of floors of the hotel.

For example, when t=3, the floors of 3, 13, 31, 33 and so on do not exist, and the floor numbers are 1, 2, 4, 5,..., so in fact, the real number of floors of the fourth floor is the third floor.

It is known that Xiao Ming has booked a room on the m floor. Now find out the real number of floors on this floor (m must be the floor existing in the hotel).

input

There are two integers m,t in one line. (1≤m≤100000,0≤t≤9)

output

Output real floors.

sample input

14 3

sample output

12

Code demonstration:

#include<iostream>
using namespace std;

int func(int x, int t) {
    while (x) {
        if (x % 10 == t) return 0;
        x /= 10;
    }
    return 1;
}

int main(int argc, char *grav[])
{
    int m, t, ans = 0;
    cin >> m >> t;
    for (int i = 1; i <= m; i++) {
        if (func(i, t)) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

oj-514. Matchstick equation

Title Description

Given n matchsticks, how many equations can be spelled out, such as a+b=c.

A, B and C in the equation are integers spelled with matchsticks (no leading zeros). The number of matchsticks used for numbers and symbols is as follows:

0:6
1:2
2:5
3:5
4:4
5:5
6:6
7:3
8:7
9:6
+:2
=:2

There are the following precautions:

1. The plus sign and the equal sign each require two matchsticks

2. If a ≠ b, then a+b=c and b+a=c are regarded as different equations, and a, b and C are not less than 0.

1. All n matchsticks must be used.

input

An integer n on one line. (1≤n≤24)

output

Output the number of equations that can be composed.

sample input

14

sample output

2

Example description

The two equations are as follows:

0+1=1
1+0=1

Code demonstration:

#include<iostream>
using namespace std;

int num[15] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6, 3, 7, 6};

int sum(int x) {
    if (x == 0) {
        return num[0];
    }
    int ans = 0;
    while (x) {
        ans += num[x % 10];
        x /= 10;
    }
    return ans;
}

int func(int a, int b) {
    int x = sum(a), y = sum(b), z = sum(a + b);
    return x + y + z + 4;
}

int main(int argc, char *grav[])
{
    int n, ans = 0;
    cin >> n;
    for (int i = 0; i < 2000; i++) {
        for (int j = 0; j < 2000; j++) {
            if (func(i, j) == n) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

oj-516. Cow inscription

Title Description

John and his cows roamed the prairie and found some interesting inscriptions on a stone. The inscription seems to be a mysterious and ancient language, which only includes three capital letters C, O and W. Although John couldn't understand it, he was happy that the sequential forms of C, O and W formed his favorite COW word "COW". Now, he wants to know how many times COW appears in the text. If other characters are interspersed in the COW, John doesn't mind as long as the COW characters appear in the correct order. Even, he doesn't mind different COW sharing some letters. For example, there is one COW in CWOW, two COW in CCOW and eight COW in CCOOWW.

input

The first line is an integer n. (1≤N≤105))

The second line contains a string of N characters. The characters can only be C,O,W.

output

The number of times that the output COW appears as the string of the input string (not necessarily continuous).

The answer could be big.

sample input

6
COOWWW

sample output

6

Code demonstration:

#include<iostream>
using namespace std;

int n, num[100005], wcnt;
long long ans;
char str[100005];
int main(int argc, char *grav[])
{
    cin >> n >> &str[1];
    for (int i = 1; i <= n; i++) {
        if (str[i] == 'C') {
            num[i] = num[i - 1] + 1;
        } else {
            num[i] = num[i - 1];
        }
    }
    for (int i = n; i > 0; i--) {
        if (str[i] == 'W') {
            wcnt++;
        }
        if (str[i] == 'O') {
            ans += (long long)num[i - 1] * wcnt;
        }
    }
    cout << ans << endl;
    return 0;
}

oj-517. Number of triangles

Title Description

Input the length n of a wooden stick, divide it into three sections, the length of each section is a positive integer, and output the different number of triangles composed of these three small sections of wooden sticks.

input

The first line is an integer n. (1≤n≤104)

output

Output the number of triangles with different composition.

sample input

10

sample output

2

Example description

The side lengths of two triangles are 2,4,4 and 3,3,4 respectively.

Code demonstration:

#include<iostream>
using namespace std;

int main(int argc, char *grav[])
{
    int n, ans = 0;
    cin >> n;
    for (int i = 1; i <= n / 3; i++) {
        for (int j = i; j <= (n - i) / 2; j++) {
            if (i + j > n - i - j) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

oj-519. Elegant number

Title Description

Given two numbers L and R, find how many "elegant numbers" there are between L and R (including).

Definition of elegant number: a number is regarded as a string of length n (without leading zeros). N − 1 of the n characters are all the same, and there is only one character different. For example, 33323119 are elegant and 99992332 are not elegant.

input

Enter two integers L,R in a row. (100≤L≤R≤1016)

output

Output the number of elegant numbers between two numbers.

sample input

110 133

sample output

13

Example description

110,112,113,114,115,116,117,118,119,121,122,131,133

Code demonstration:

#include<iostream>
using namespace std;
int main(int argc, char *grav[])
{
    long long left, right;
    cin >> left >> right;
    int ans = 0;
    // Enumerate a stack of numbers
    for (int i = 0; i < 10; i++) {
        // Enumerate a number
        for (int j = 0; j < 10; j++) {
            if (i == j) {
                continue;
            }
            // Length of number
            for (int k = 3; k <= 17; k++) {
                // Position of number
                for (int l = 1; l <= k; l++) {
                    if (i == 0 && l != 1) {
                        break;
                    }
                    if (j == 0 && l == 1) {
                        continue;
                    }
                    long long t = 0;
                    // Construction elegant number
                    for (int m = 1; m <= k; m++) {
                        if (m == l) {
                            t = t * 10 + j;
                        } else {
                            t = t * 10 + i;
                        }
                    }
                    if (left <= t && t <= right) {
                        ans++;
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}