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

I managed to get rid of WA using these two test cases:

in:
1
dcbbbdbdbbacaaaddbdcbbbdbbdbbadacbbaaddbaddbddacaa
out:
15577

in:
1
abcccacccbcabaaaacbbabbcaaaaacaaaaacaacacbbacbcaba
out:
15236

In test #23 it seems that n is large. So, to pass TLE #23, make sure your code is running fast enough for n = 100 000 and each test contains a single letter.

I used ternary search for this problem
limits
-50000:50000  leads to wa18
-100000:100000 got wa1
-90000:90000 was AC

is there a normal solution without finding such segment?

If you have WA #5 try below test:
2 5
2 3 9 2 100
1 2 5 4 100
2 1
1 5

Correct answer is 0.

Can someone provide a test, that makes the following code get TLE?

// ITNOA
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n;
    cin >> n;
    int cnt = 0;
    for (ll i = 2;i*i <= min((ll)1e18, n);i++)
        while (n%i == 0)
        {
            n /= i;
            cnt++;
        }
    if (n > 1)
        cnt++;
    if (cnt == 20)
        cout << "Yes\n";
    else
        cout << "No\n";
}

Graph can have loops and multiple edges.

Edited by author 28.10.2019 20:10

var
a:integer;
begin
read(a);
if a=0 then write(5);
if a=1 then write(21);
if a=2 then write(12);
if a=3 then write(2);
if a=4 then write(1);
if a=5 then write(4);
if a=6 then write(6);
if a=7 then write(1);
if a=8 then write(4);
if a=9 then write(4);
if a=10 then write(1);
if a=11 then write(0);
if a=12 then write(1);
if a=13 then write(1);
end.

Edited by author 28.10.2019 15:01

Because of p*=(i%m) was WA. When I wrote p=(p*i)%m instead of p*=(i%m) then  I got AC
Why???

What is in 3 test ?

MY CODE IS:

#include<bits/stdc++.h>
using namespace std;

vector < int > heap;

/////MINHEAP

void ADD( int m )
{
  heap.push_back(m);
  int j = heap.size()-1;

  while( j != 1 &&  heap[j] < heap[j/2] )
  {
    //SWAP
    int carry = heap[j/2];
    heap[j/2] = heap[j];
    heap[j] = carry;

      j /= 2;
  }
  return;
}

void REMOVEMIN()
{
  heap[1] = heap[heap.size()-1];
  heap.pop_back();

  int j = 1;

  while( ( 2*j < heap.size() &&  heap[j] > heap[2*j] ) || ( 2*j+1 < heap.size() && heap[j] > heap[2*j+1] ) )
  {
      if( 2*j+1 < heap.size() && heap[2*j] > heap[2*j+1] )
      {
       //SWAP
       int carry = heap[j];
       heap[j] = heap[2*j+1];
       heap[2*j+1] = carry;
       j = 2*j+1;
      }
      else
      {
       //SWAP
       int carry = heap[j];
       heap[j] = heap[2*j];
       heap[2*j] = carry;
       j = 2*j;
      }
  }
  return;
}

int GETMIN()
{
  return heap[1];
}

int n, a;

int main()
{
  ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);

  heap.push_back(-1);

  cin >> n;
 if( n % 2 == 0 )
 {
     int m = n/2 + 1;
      while(n--)
      {
         cin >> a;
         ADD(a);

        if( heap.size() - 1 > m )
        {
          REMOVEMIN();
        }
      }
  int mid1 = GETMIN();
  REMOVEMIN();
  int mid2 = GETMIN();
  bool f = 0;

  if( mid1 % 2 == 0 && mid2 % 2 == 0 )
    cout << mid1/2 + mid2/2;
  else if( ( mid1 % 2 == 1 && mid2 % 2 == 0 ) || ( mid1 % 2 == 0  && mid2 % 2 == 1 ) )
    cout << mid1/2 + mid2/2 << ".5";
  else
    cout << mid1/2 + mid2/2 + 1;
 }
 else
 {
     int m = n/2 + 1;
      while(n--)
      {
         cin >> a;
         ADD(a);
         if( heap.size() - 1 > m )
        {
          REMOVEMIN();
        }
      }
     cout << GETMIN();
 }


  return 0;
}
BUT WHY MLE? ?:'(

Edited by author 26.10.2019 00:08

Edited by author 26.10.2019 00:09

Edited by author 26.10.2019 00:09

Edited by author 26.10.2019 00:09

I got WA4. Can somebody help?
And RE 16...

Edited by author 25.10.2019 21:31

hello, can u sentme the right code of this programm? thank you very much
coloteroritata@gmail.com

Do not forget case for "Ask Shiftman for help"

?????

Edited by author 19.10.2019 23:42

I use c++,my code is behind. But there is a weird problem . When i define n as int and use cin>>n,the program can't receive the name have more than two word or have symbols like '-'. So i have to define n as a string and transfer the string into a int,why this strange thing happen?

#include<iostream>
#include<string.h>
#include<cstring>
using namespace std;

int main()
{
    char room[4][1000][210];
    memset(room,0,sizeof(room));
    int k=0,nth[4]={0};
    char n[10];
    cin.getline(n,10,'\n');
    int len=10;
    while(n[len]=='\0'){len--;}
    int temp=1;
    for(int i=len;i>=0;i--)
    {
        k+=(n[i]-48)*temp;
        temp*=10;
    }

    for(int i=0;i<k;i++)
    {
        char temp[210],temp1[20];
        cin.getline(temp,210,'\n');
        cin.getline(temp1,20,'\n');

        if(temp1[0]=='S')
        {
            strcpy(room[0][nth[0]],temp);
            nth[0]++;
        }
        else if(temp1[0]=='H')
        {
            strcpy(room[1][nth[1]],temp);
            nth[1]++;
        }
        else if(temp1[0]=='G')
        {
            strcpy(room[2][nth[2]],temp);
            nth[2]++;
        }
        else {
            strcpy(room[3][nth[3]],temp);
            nth[3]++;
        }
    }
    /* omit so this is not a correct solution*/
}

Hello!
Seems there is a duplication in english statement of the problem:
>> We know that there are more than P% conductors and less than Q% conductors of all citizens of Ekaterinburg.

>>By percentage, we know that there are more than P% conductors and less than Q% conductors of all Russian citizens in this city

In the 21st test there are ships with the same azimuth.

Edited by author 29.10.2010 23:26

1104 Task
Help me please, I cant understand how can i do my calculations faster?
I think that problem with slow input, but how else can i write it?

p.s. using stdin, stdout get Time Limit as well


maximal = 0
max_digit = -1

arr = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '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']

for s in input():
    number = arr.index(s)
    if max_digit < number:
        max_digit = number
    maximal += number

if max_digit == 0:
    print(2)
else:
    answer = ''
    for k in range(max_digit, 37):
        if not maximal % k:
            answer = k + 1
            break

    if answer == '':
        print('No solution.')
    else:
        print(answer)

Edited by author 14.10.2019 07:30

Edited by author 14.10.2019 07:41

m = []
g = []
d, b = map(int, input().split(' '))
for i in range(1, b+1):
    n = int(input())
    m.append(n)
for i in range(1, d+1):
    g.append(i)
for i in range(d):
    f = 0
    for y in range(b):
        if m[y] == g[i]:
            f += 1/b*100
    f = round(f, 2)
    a = str(f)
    if len(a) == 4:
        print(a+'0%')
    else:
        print(a+'%')