Out of all shortest path I am finding min of maximum distance I have to travel for every level.





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

void bfs(int u,vector<int> &d,const vector<vector<int>> adj){
    d[u] = 0;
    queue<int> q;
    q.push(u);

    while(!q.empty()){
        int u = q.front();
        q.pop();

        for(auto v:adj[u]){
            if(d[v]>d[u]+1){
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> adj(n);

    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u-1].push_back(v-1);
        adj[v-1].push_back(u-1);
    }

    vector<int> ds(n,1e9),df(n,1e9),dr(n,1e9);
    int s,f,r;
    cin>>s>>f>>r;
    s--,f--,r--;
    bfs(s,ds,adj);
    bfs(f,df,adj);
    bfs(r,dr,adj);

    vector<vector<int>> l(ds[f]+1);

    for(int i=0;i<n;i++){
        if(ds[i]+df[i]==ds[f]){
            l[ds[i]].push_back(i);
        }
    }
    int ans = INT_MAX;
    for(int i=0;i<=ds[f];i++){
        int a = INT_MIN;
        for(auto x: l[i]){
            a = max(a,dr[x]);
        }
        ans = min(a,ans);
    }

    cout<<ans;

    return 0;
}

Just think of an increasing sequence. The program caculates n+1 times for an increasing sequence with n elements. And then divide it into two subsequences. One is the leftmost element, and anthoer is the left elements. It ends at the length of sequence is 2. Thus, the sum is (n+1) + n + (n-1) + ... + 3 = (n+4)(n-1)/2 = (n*n + 3*n - 4)/2. So output 1 to n is ok.

union message
{
    char bytes[4];
    unsigned value;
    void reverse()
    {
        swap(bytes[0], bytes[3]);
        swap(bytes[1], bytes[2]);
    }
};

Consider the case in which n < i, j
That helped me to get AC

Is the first test from conditions? If answer is "yes", then why the system say "WA1"? The program works correctly on my computer. Maybe, I misunderstood something important, and my output has wrong format? Help me, please.


Edited by author 05.01.2013 15:42

Prime Divisor of b - Prime Divisor of a

You must find the first team that may go final if q wil be q+1. You mustn't output the team after q th finalist.
Example:
2012 6 3
SPBU ITMO # 1   (finalist)
URAL SU # 1    (finalist)
SPBU ITMO # 2
SARATOV SU # 3  (finalist)
URAL SU # 2   (not finalist !!!)
SPBU SU # 1   (answer)

Edited by author 03.12.2011 13:18

3 3
2
3
1

Ans: 2

How do I get an unlimited length array from the console so that the test starts? What is the end character of the input?

сколько у кого на тесте
6
60 30 20 10 0 0 ??

Any one yes test?

how about this one sample

5
5 3 3 3 3

? this ans right 76 5 5 5 5?

Edited by author 15.10.2011 14:59

Why is this happening ... according to websites that can be trusted, the answers are different -

https://mathworld.wolfram.com/CirclePacking.html

http://hydra.nat.uni-magdeburg.de/packing/cci/

In other words, these are not the optimal values,
i.e. for test 8
the value using the simpler (and not accurate formula) - 3.6131259 is accepted,
when the optimal value is less than that - 3.3047648

easy

10
+ 24
+ 27
+ 9
+ 24
+ 12
- 24
- 24
- 12
- 27
- 9
24
3
3
3
3
3
3
9
9
1

5
+ 8
+ 6
+ 8
- 8
- 8
8
2
2
2
6


9
+ 10
+ 10
+ 10
- 10
- 10
+ 5
- 10
- 5
+ 123
10
10
10
10
10
5
5
1
123

I have two solutions!
Time: 1.15 solution:
numbers = []

for i in range(int(input())):
    numbers.append(int(input()))

print_s = ''

for n in numbers:
    if len(print_s) > 0:
        print_s += ' '
    number = int((n * 2) ** 0.5)
    y = (number * (number - 1)) // 2
    y2 = y + number
    y += 1
    if n <= y2:
        print_s += '1' if n == y  else '0'
    else:
        print_s += '1' if n == y + number else '0'
print(print_s)

Time: 1.15 solution:
numbers = []

for i in range(int(input())):
    numbers.append(int(input()))

print_s = ''

for n in numbers:
    if len(print_s) > 0:
        print_s += ' '
    length = 1
    while n > length:
        n -= length
        length += 1
    print_s += '1' if n == 1 else '0'
print(print_s)
Help me pls!!

Edited by author 13.08.2022 10:14

:)

For those who use KMP, and get a WA -

I can confirm that this is a good implementation of KMP -
https://www.tutorialspoint.com/c-program-for-kmp-algorithm-for-pattern-searching
(I use Plain C)

Edited by author 29.11.2022 21:40

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

int main(){
    int n, half, votes, q[101];
    cin >> n;
    half = (n/2) + 1;
    for (int i=0; i < n;i++)
        cin >> q[i];

    sort(q,q+n);

    for (int i =0;i<half;i++)
        votes += (q[i]/2) + 1;


    cout << votes;
    return 0;
}

Every time I submit a super-efficient solution that is accepted, in the rating list there are more efficient solutions written in languages that are not supported now.

Everybody knows that older compilers like Intel C++ 7 generate code that takes less RAM and is a little faster than any supported C++ compiler.

It would be fair, if the Solutions rating list support an option to filter only solutions, implemented in currently supported languages and compilers.

Administrators, please consider it.

Cheers!

If you look at the statement, it says "Triviality of a natural number N is the ratio of the sum of all its proper divisors to the number itself. Recall that a proper divisor of a natural number is the divisor that is strictly less than the number.". Therefore, triviality of 1 should be 0 / 1 == 0, since 1 doesn't have any divisor strictly less than itself. However, I couldn't get an AC (WA4) until I changed the line
if (I == 1) ans = 0
to
if (I == 1) ans = 1.
So, either the statement or the tests are broken.

Edited by author 05.08.2022 19:55

Edited by author 05.08.2022 19:55