The algorithm is not hard but this problem is very poorly stated.

1. Use 3 decimal places.
2. Consider using ints and longs rather than doubles.

The problem is rejudged, one author have lost AC. Thanks to Erop [USU]

This problem is one based on number theory. After solving this problem, I found it very beautiful in mathematics.

Here are some facts that holds for all cases. Proof is ignored for each fact. If you are interest on it, just try to prove that using number theory.

Fact.1 For any (a, b), where a = 1 and GCD(b, m) = 1, it is always the solution.
(The most trivial fact...)
Let's denote the set: B = {b | GCD(b, m) = 1}.

Fact.2 For any a0 != 1, if there exists some b0 such that (a0, b0) is a solution, then:
(1) b0 is an element of B, and
(2) for all b in B, (a0, b) is a solution.
(Hence, to check some a0 for validity, you need only to check (a, 1). But it will still cost you O(N) time for a single a0, and O(N^2) for a0 in the range [0, m - 1].)

Fact.3 For any m, factorize it into product of primes. There exists some solution (a0, 1), where a0 != 1, iff one of the power of primes in m is larger than 1 (at least 2). Specially, if the prime is 2, the power must be at least 3.
e.g. for this fact:
4 = 2^2 -- No solution for a != 1.
8 = 2^3 -- Exists solution for a != 1 (a = 5).
15 = 3 * 5 -- No solution for a != 1.
20 = 2^2 * 5 -- No solution for a != 1.
18 = 2 * 3^2 -- Exists solution for a != 1 (a = 7, 13).

Fact.4 For any m, denote A = {a | there exists solution for a}. Then all the numbers in A form an arithmetic sequence. The common difference of the sequence, d, equals to m, divided by all the redundant power of the factorized primes. Here, redundant power is 1 for those primes p (p != 2) with power at least 2, and is 2 for prime 2 with power at least 3. For those primes without enough power, the redundant power is 0.
e.g. for this fact:
8 = 2^3 -- d = 2^1 = 2.
18 = 2 * 3^2 -- d = 2 * 3 = 6.
100 = 2^2 * 3^2 -- d = 2^2 * 5 = 20.
72 = 2^3 * 3^2 -- d = 2^2 * 3 = 12.

Obviously, Fact.3 and Fact.4 could be combined together. For those m without solutions that a != 1, the common difference, d, for m, is m itself.

Now, the problem could be solved quickly. The only work remaining is to factorize m, which is very easy in practise. However, proving these facts in number theory could be more interesting than solving this problem itself.

Good luck.

Maybe, someone can help with test? =)

Вот представь, в нашу мастерскую пришли из компании строящей новую гостиницу и принесли эскиз.
->
Вот представь, в нашу мастерскую пришли из компании, строящей новую гостиницу, и принесли эскиз.

а так как ЭТО будет стоять у меня в мастерской.
->
а так, как ЭТО будет стоять у меня в мастерской.

i define the const variables like that:
const int N = 110;
const int M = 510;
but it should be
const int N = 110;
const int M = 510;

If you have WA7 then check up: the point is inside the polygon or not.

test:
31 12 2400

be careful of the ']'

What's wrong with it? I tried every test in previous topics and everything is fine, but Timus system does not accept my program.

#include <stdio.h>

int fact(int n, int k){
    int res = 1;
    if (n == 0)
        return res;
    while (n > k) {
         res *= n;
         n -= k;
    }
    if (n % k)
        res *= (n % k);
    else
        res *= k;
    return res;
}

int main () {
    char sym;
    int n = 0;
    int symCount = 0;
    scanf("%d ", &n);
    while (scanf("%1[!]", &sym) == 1) {
            symCount++;
    }
    printf("%d\n", fact(n, symCount));
    return 0;
}

Hello,

Could anyone provide me with some hint about the test 22? I keep getting WA#22.

In fact, it cost me 4 submissions to get accepted. However, I still think that this is a problem with simple geometry. However, some confusion in the problem statement rather made a big trouble for me.

The problem statement said that the plates had the shape of truncated cones. However, it still remains a problem, that which bottom of the truncated cone is larger. By the common sense, the upper bottom of the cone should be larger, and it is indeed so in the testdata (I have submitted a checker for this), but the fact does not appear in the statements.
PS: even if the lower bottom is larger, my program could still give the correct results.

Secondly, the height of the tray need NOT be larger than (or equal with) the height of the cones. If the height of tray is smaller, the plates could still fit in the tray, and in this situation, some part of the plates could even be outside the tray. So important the condition is, it doesn't appear in the problem statements at all! I could not understand this.

And, at last, I want to give the last hint to all authors: try to solve this problem by 64-bit integers. Floating point numbers might bring in errors, which you don't want to see.

My AC (accepted) program (numbers of submits: 3740606 or 2776983) has BIG Time Limit at home on this test:
100000
2 3 [...] 99999 100000 0
0
[... number "0" repeatedly 99999 times]
0
1

This test may be got by this simple program (on Pascal):
var
  I, N: Longint;
begin
  N := 100000;
  Writeln(N);
  for I := 2 to N do
    Write(I, ' ');
  Writeln('0');
  for I := 2 to N do
    Writeln('0');
  Write('1');
end.

Please, add this test and its analogs to test base.

Edited by author 22.08.2011 13:52

Here my algo:


#include<iostream>
using namespace std;
int main(){
    char c; int i=0;
#ifndef ONLINE_JUDGE
   freopen("input.txt", "rt", stdin);
   freopen("output.txt", "wt", stdout);
#endif
while(cin.get(c)){
if(i==0&&c>='A'&&c<='Z'){cout<<c; i=1;}else{
if(c>='A'&&c<='Z')cout<<char(c-'A'+'a');
else cout<<c;
}
if(c=='.'||c=='!'||c=='?')i=0;
}
return 0; }

In this game "Heroes of Might and Magic", the amount for "pack" is from 10 to 24, and amount for "lots" is from 25 to 50, just different with the statement.

A joke.

string s,t;
int main(){
    cin>>s;
    bgn:
    bool b=0;
    s=s+'_';
    Repi(s.sz-1){
        if(s[i]==s[i+1]){i++;b=1;}
        else t=t+s[i];
    }
    s=t;t="";
    if(b==1)goto bgn;
    cout<<s<<endl;
    system("pause");
    return 0;
}

Any idea where's the problem?

Can you tell me plz what is test #3?

this is my solution, why it is false??? :)



# include <stdio.h>
int main ()
{
 int a,b,c;
 printf ("a:");
 scanf ("%d",&a);
 printf ("b:");
 scanf ("%d",&b);
 c=a+b;
 printf ("a+b=%d",c)
 return 0 ;
 }

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int cmp(const void *a, const void *b);

int main()
{
    long num,i;
    double k=0,*ms;
    scanf("%ld",&num);
    ms = (double*)malloc(num*sizeof(double));
    for(i=0; i<num; i++)
        scanf("%lf",&ms[i]);
    qsort(ms,num,sizeof(double),cmp);
    for(i=0; i<num; i++){
        k -= ms[i];
        if(k<0)
            k=-k;
    }
    printf("%.0lf",k);
    return 0;
}
int cmp(const void *a, const void *b)
{
    return -(*(double*)a-*(double*)b);
}

Edited by author 29.08.2011 22:27