I got time limit in test#5 and I can't find out why

I get TLE on 22 test. What can you advise?

Each number maps to several letters of the alphabet. However, notice that several letters map to a single digit. If you can't go to the mountain, bring the mountain to you. Convert the words found in the dictionary for each case into digits, using the given map. Looking up which digit a letter maps to can be done in constant time if you use the right data structure. Then all that is left is to compare against the phone number given.

I got AC! It's nice problem!
My algo works at O(3*N)=O(N).
1)BFS from any vertex and find the most remote vertex (let V);
2)BFS from V and find the most remote vertex (let U);
3)Create path from U and V; vertex(vertexes) in the middle is answer.

Edited by author 04.08.2015 12:56

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    char name[20];
    int N;
    scanf("%d", &N);
    int cost=200;
    int $=0;
    for(int i=0; i<N; i++)
    {
        scanf("%s", name);
        if(name[strlen(name)-4]=='+'&&name[strlen(name)-3]=='o'&&name[strlen(name)-2]=='n'&&name[strlen(name)-1]=='e')
        {
            cost=cost+200;
        }
        else
        {
            cost=cost+100;
        }
    }
    $=$+cost;
    if($==1300)
    {
        $=$+100;
    }
    printf("%d", $);
    return 0;
}

I got my code running due to the solutions posted.. But i want to understand the logic behind the division.. Any one?

int main()
{
    int n , m;
    cin >> n >> m;

    int *counter = new int [n];

    for ( int i = 0 ; i < m ; i++ )
    {
        int temp;
        cin >> temp;
        counter[temp-1]++;
    }

    for ( int i = 0 ; i < n ; i++ )
    {
        float result = (float)counter[i] * (float)100 / (float)m;
        printf ("%.2f%%\n" , result);
    }

    delete[] counter;

    return 0;
}

(WA On Test 1)

Give me please 37 test.

a,b=input('Введите числа через пробел: ').split(" ")
a=int(a)
b=int(b)
print(a+b)

test 1, wrong answer :(

#include <iostream>

using namespace std;

int prime[15001];
bool num[163848];
void sieve() {
    num[2]=true;
    prime[1]=2;
    long int i,j,k;
    for(i=3;i<163848;i+=2) num[i]=1;
    for(i=2,j=3;i<=15000;j+=2) {
        if(num[j]) {
            for(k=j;k*j<=163848;k+=2) num[k*j]=0;
            prime[i]=j;
            i++;
        }
    }
}

int main() {
    sieve();
    int t;
    cin>>t;
    while(t--) {
        int m;
        cin>>m;
        cout<<prime[m]<<endl;
    }
}


Why am I getting RTE in test #1?

Edited by author 13.09.2019 08:33

does anybody know anything about WA on that test?

I got AC in 0.125s and 284KB!!!
If you want my AC code,post me:happyzeyu@163.com

Edited by author 25.12.2006 17:30

Edited by author 25.12.2006 17:30

If you have problems with test case 6, then please check the following:


If you have wrong anwer at test 6, try this test:
4 3
3 4 5

Correct answer: 1
Because at ith minute, there is only a[i] cars come to the traffic jam. Good luck to you!

Thanks to sign_in158.

n=2984210864
21975
21818
11974
11967
11964
11964
11964
11907
11707

n=120
22
53
23
22
22
22
22
22
22
22

n=1000000000
788888898
900000001
900000000
900000000
900000000
900000000
900000000
900000000
900000000
900000000

n=1595999
887689
1594800
998800
998800
998800
994800
897800
897800
897800
893800

n=2009999
1112889
2204000
1214000
1204000
1204000
1204000
1204000
1204000
1204000
1204000

n=123456789
96021948
130589849
100589849
96589849
96089849
96029849
96022849
96022049
96021959
96021949

n=10000
2893
4001
4000
4000
4000
4000
4000
4000
4000
4000

n=20000
6893
18000
8001
8000
8000
8000
8000
8000
8000
8000

n=30000
10893
22000
22000
12001
12000
12000
12000
12000
12000
12000

n=9999
10893
22000
22000
12001
12000
12000
12000
12000
12000
12000

#include <iostream>
#include <math.h>
#include <iomanip>
#include <vector>
#include <map>
#include <string>
#include <algorithm>


using namespace std;


int main()
{
    int n;
    cin >> n;
    vector<int> vec;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        vec.push_back(num);
    }
    int max = 0;
    int sum = 0, seredina = 0;
    int index = 0;
    multimap<int, int> index_sum;
    for (int i = 2; i < vec.size(); i++) {
        sum = 0;
        if (vec[i] >= vec[i - 1] && vec[i - 1] >= vec[i - 2]) {
            sum += vec[i] + vec[i-1] + vec[i-2];
            index_sum.insert(pair<int, int>(i, sum));
        }
    }
    for (auto it = index_sum.begin(); it != index_sum.end(); it++) {
        if (it->second > max) {
            max = it->second;
            sum = max;
            seredina = it->first;
        }
    }
    cout << sum << " " << seredina;
    return 0;
}

Edited by author 30.10.2019 21:02

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
#include <string>
#include <cstdlib>

using namespace std;

void optimization() {
     cin.tie(nullptr);
     ios_base::sync_with_stdio(false);
}


int main() {
     optimization();

     string s;
     int k = -1;
     cin >> s;
     char c[200000];

     for (char & i : c) {
          i = ' ';
     }

     for (char i : s) {
          if (k > -1) {
               if (c[k] == i) {
                    c[k] = ' ';
                    k--;
               } else {
                    k++;
                    c[k] = i;
                    continue;
               }
          }
          else {
               k++;
               c[k] = i;
          }
     }
     for (char i : c) {
          if (i != ' ') {
               cout << i;
          }
     }

     return 0;
}

You can use Disjoint-set data structure.

Please, help.

Solution is Minimum spanning tree (Kruskal or Prim Algorithm). Put low cost on tunnels, and much higher one on bridges with using priority queue ;)

Used bfs instead dfs