Edited by author 17.10.2022 09:55

Edited by author 17.10.2022 09:55

I don't know why there were so many submitted O(n^2) DP solutions. Here is a simple formula for this problem:
answer = n - (yes + yes*(yes-1) + no*(no-1))/n, where yes = s-2*n and no = n-yes are the total numbers of occurrences of corresponding strings in answer.txt.
You can easily derive this if you try to think of probability of the same verdict for two arbitrary consecutive tests.

What is the mistake?
n = int(input())
a = []
for i in range(1, n+1):
    if n % i == 0:
        a.append(i)
if n == 1:
    print("1")
    exit(0)
if n == 0:
    print("10")
    exit()
if len(a) > 2:
    for i in range(len(a) - 1):
        if a[i] * a[i + 1] == n or a[i]*a[i] == n:
            if a[i] * a[i + 1] == n:
                s = "".join(sorted(str(a[i])+str(a[i+1])))
                print(s)
            else:
                print(a[i], a[i], sep="")
else:
    print("-1")

# Alternative Solution

Valentine is a veteran of programming contests and he's been working in the program committee for many years. He is very busy this week: the bike is under repair, some problems with Indian colleagues have to be solved, and five student groups are to be examined in philosophical problems of mathematics at the university. To crown it all, the new chairman of the program committee asked Valentine to write an alternative solution for one of the problems of the forthcoming contest.

Valentine was so busy that he had no time to read the problem statement. He only glanced at the output format and understood that it was required to output either `YES`, or `NO`.

Fortunately, Valentine was well acquainted with the testing system used in the contest. The system successively runs a solution on all tests of a problem, and for each test the checking process goes as follows. The input is copied to the file input.txt. Then the solution is launched. It reads the input from the file input.txt and writes the result to the file output.txt. When it finishes, the correct answer is copied to the file answer.txt. If the contents of the files answer.txt and output.txt match, the test is assumed to be passed; otherwise, the test is not passed.

Valentine decided to write a program that would operate as follows. If the folder containing the program doesn't contain the file answer.txt (i.e. the program is run on the first test), then the program outputs `YES`. Otherwise, the program outputs the contents of the file answer.txt.

Valentine plans to tell the chairman of the program committee that there is a nontrivial mistake in his program, and this mistake, fortunately, shows itself when the program is run on the excellent hard tests prepared by the author of the problem. However, first Valentine has to estimate the number of tests that his solution won't pass. Valentine doesn't have access to the tests, but he knows the number of tests and the total size of the files with answers. He also knows that the size of the file with the answer `YES` is 3 bytes, the size of the file with the answer `NO` is $2$ bytes, and all the variants of the order of tests are equally probable. Help Valentine to calculate the average number of tests that his solution won't pass.

## Input

The only line contains two integers $n$ and $s$ ($1 \le n \le 5000$; $2n \le s \le 3n$) which are the number of tests and the total size of the files with answers, respectively. The numbers are separated with a space.

## Output

Output the average number of tests that Valentine's solution won't pass, accurate to $10^{-5}$.

## Sample

### input

```
3 7
```

### output

```
2.0000000
```

Let a=s-2n,b=3n-s.
Then the answer is (2ab+b)/n.
Try it, you won't regret it!

answer=(2s-4n+1)(3n-s)/n

we dont know use the locomotive as a carriage, like:
input:
1 1
AA
AB

output:
NO

GOOD LUCK!!!

Whats wrong with anything here?
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ui=unsigned int;
int main() {
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    ll n;cin>>n;
    if(!n){
        cout<<10;
        return 0;
    }
    else if(n<10){
        cout<<n;
        return 0;
    }
    vector<int>v;
    ll l=n;
    for(bool q=1;q;){
        q=0;
        for(ll i=9;i>1;i--){
            if(l%i==0){
                l/=i;
                v.push_back(i);
                q=1;

            }
        }
    }
    v.push_back(l);
    sort(v.begin(),v.end());
    if(v[0]==1)for(int i=1;i<v.size();i++)cout<<v[i];
    else cout<<-1;
    return 0;
}

i had wa 22 for many times , & i finally found my fault & then got AC .
my fault is that i didn't find the exact edge (with the same ci & ti & hi) it used .
remember there are many different edges between a (ui , vi) .

let me know if there is a test case in that the any first number of A , B, C is 0

Please make clear that

Edited by author 16.12.2006 14:06

Edited by author 16.12.2006 14:06

Edited by author 16.12.2006 14:07

let N be the node num of the graph.
so why the maximum cycle number is M-N+1?
where M is the edge num.

please...

I found the problem statement a little hard to understand, and I want to make some clarifications for anyone who is having difficulties.

1. We are looking for the maximum number of cycles such that each of these chosen cycles has at least one edge which is not included in any other chosen cycle.

2. The graph is not necessarily connected.

I originally thought that we had to choose the maximum number of cycles which have at least one edge not included in all other chosen cycles. Hope this can help people.

Test #30 was found to be incorrect. It has been removed. The failing solutions have been rejudged.

Подскажите, пожалуйста, что не так с кодом? Wrong answer, тест 3.

Edited by author 09.10.2022 19:48

Edited by author 09.10.2022 19:48

Amount of pieces to move, edges to make euler path(only pieces with (in[i] + out[i]) > 0) and amount of components

Try this test (if you look neighbour cells in order from -1 left -1 up (11 oclock) clockwise)
4 4
#A#.
#A!.
##.#
.*$.

dfs or bfs is the correct idea?
oh, i'm done with it (:
Edited by author 15.10.2012 15:14

Edited by author 15.10.2012 15:22