Time Limit so small. Solution with O(n * m) complexity passed tests with time 3.244s.

http://acm.timus.ru/status.aspx?space=1&num=1369&author=124588

Edited by author 10.01.2016 23:58

input:
7
1 1000
2 500
501 999
3 499
502 800
4 400
503 700
output:
4
6 4 2 1
or
4
7 5 3 1

Chto za xren Test 5?
Does anybody know what the hell is Test 5?

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 16500

void prime(int n)
{
    int i,j,temp,count=0;
    for(i=2;i<=MAX;i++)
    {
        temp=0;
        for(j=2;j*j<=i;j++)
        {
            if(i%j==0)
            {
                temp=1;
                break;
            }
        }
        if(temp==0)
        {
            count++;
        }
        if(count==n)
        {
            printf("%d\n",i);
            break;
        }
    }
}

int main()
{
   int n,t,i;
   scanf("%d",&t);
      while(t--)
      {
           scanf("%d",&n);
            prime(n);
      }
   return 0;
}

Why i got this TLE. I think my idea is not wrong but why its occur?
I don't understand. Pleas help me.....

Edited by author 06.09.2015 20:29

i have WA #2
#include <iostream>
#include <stdio.h>
using namespace std;

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

    int win = 0;
    for(int i = 0; i < m; i++)
    {
        int a;
        cin >> a;
        n -= a;
        if(i % 2 == 0)
            win = 2;
        else win = 1;
    }

    cout << win << endl;

    return 0;
}

First of all. If you get WA#1, check how you scan input stream, cause they've put some trash in file.

I used the following idea. The whole number with base k divisible by ( k - 1 ), if sum( div( digit[ i ] ) ) is divisible by ( k - 1 ). Where digit[ i ] is k-based digit in input number ( char from input stream ); div( digit[ i ] ) is a remainder of division digit[ i ] * k by ( k - 1 ). Let see digit on i-th position, for example, it's A. So in decimal implementation it's equal to A * k ^ i.
A * k ^ i = A * k^i - A * k^(i-1) + A * k^(i-1) = A * k^(i-1) * ( k - 1 ) + A * k^(i-1)
A * k^(i-1) * ( k - 1 ) is divisible by ( k - 1 ), so we have to check only A * k^(i-1). If we repeat the same logic to this expression (i - 2) times, we see, that we have to check division A * k / ( k - 1 ).

I tried my best to explain the main idea, sorry if it can't be understood.

input1
sd5=#124'ashds'#12#154'sah';
input 2
sd5:=#123+#12;

I got WA1 and I don't understand why. Give me some tests please.

What does it mean: "clockwise order"?
How do you define clockwise order in notconvex polygon?
For example: in picture like a snail what roundabout way is turned in the clockwise direction and what is not?

Sorry for bad Enlish...

how could it have been passed??? and with 0.031

Can anyone give me some tricky tests?

Can I get some test inputs please?

const Nmax=111111;
var
 path:array[1..Nmax] of char;
 N,M,K,pic,d,dmax,i,L,now:longint;
 ch:char;
 ans1,ans2,ans3:int64;

begin
 readln(N,M,K);
 L:=0;
 read(ch);
 while(ch='u')or(ch='d')or(ch='r')or(ch='l')or(ch='f')or(ch='b') do begin
  inc(L);
  path[L]:=ch;
  read(ch);
 end;

 pic:=1;
 d:=1;
 dmax:=1;
 now:=1;
 for i:=1 to L do begin
  if(path[i]='l') then begin
   if(now=1) then begin
    inc(d);
    if(dmax<d) then dmax:=d;
   end
   else begin
    dec(now);
    if(now=1) then begin
     d:=1;
     if(dmax<d) then dmax:=d;
    end;
   end;
  end;
  if(path[i]='r') then begin
   if(now=N) then pic:=N
   else begin
    inc(now);
    d:=0;
    if(now>pic) then pic:=now;
   end;
  end;
 end;

 ans1:=1;
 i:=2;
 while(i<=N)and(pic<N) do begin
  if(i-1>=dmax) then inc(pic);
  if(i-1>=dmax)and(pic<=N) then inc(ans1);
  inc(i);
 end;

 pic:=1;
 d:=1;
 dmax:=1;
 now:=1;
 for i:=1 to L do begin
  if(path[i]='d') then begin
   if(now=1) then begin
    inc(d);
    if(dmax<d) then dmax:=d;
   end
   else begin
    dec(now);
    if(now=1) then begin
     d:=1;
     if(dmax<d) then dmax:=d;
    end;
   end;
  end;
  if(path[i]='u') then begin
   if(now=M) then pic:=M
   else begin
    d:=0;
    inc(now);
    if(now>pic) then pic:=now;
   end;
  end;
 end;

 ans2:=1;
 i:=2;
 while(i<=M)and(pic<M) do begin
  if(i-1>=dmax) then inc(pic);
  if(i-1>=dmax)and(pic<=M) then inc(ans2);
  inc(i);
 end;


 pic:=1;
 d:=1;
 dmax:=1;
 now:=1;
 for i:=1 to L do begin
  if(path[i]='b') then begin
   if(now=1) then begin
    inc(d);
    if(dmax<d) then dmax:=d;
   end
   else begin
    dec(now);
    if(now=1) then begin
     d:=1;
     if(dmax<d) then dmax:=d;
    end;
   end;
  end;
  if(path[i]='f') then begin
   if(now=K) then pic:=K
   else begin
    d:=0;
    inc(now);
    if(now>pic) then pic:=now;
   end;
  end;
 end;

 ans3:=1;
 i:=2;
 while(i<=K)and(pic<K) do begin
  if(i-1>=dmax) then inc(pic);
  if(i-1>=dmax)and(pic<=K) then inc(ans3);
  inc(i);
 end;

 write(ans1*ans2*ans3);
end.

Рассуждения такие:
1)как только достигнуто значение верхней границы,то все последующие шаги бессмысленны,т.к. пути совпадут;
2)пока первые i точек попадают в минимум у 1-ой точки (т.е. можно построить график зависимости номера шага от его значения,причем за пределы значений нельзя выходить и потому строим график в этом случае параллельным оси шага),их всех(кроме 1-ой точки) не засчитываем,все оставшиеся(если есть) и дают ответ;
3)всё перемножаем.

6
one 7 4 5
two 6 3 10
three 5 10 9
four 7 6 7
five 2 5 8
six 3 3 3

I think : one, two, three, four, five.

Edited by author 18.03.2009 20:44

My submission get AC when i use Visual C++ 2013 and get TLE using G++ 4.9 C++11... Why?

It is guaranteed that the most often appeared letter is the right answer. Only one letter is needed.

Пишу на Dev-C++ примет ли мой код? и почему-то пишет Compilation Eror. вот код:
# include <iostream>
# include <windows.h>

using namespace std;
int main()
{
    int a, b;
    cout << "Enter your numbers ";
    cin >> a >> b;
    cout << "Answer is " << a+b << endl;

    system("pause");
    return 0;
}

#include <iostream>
using namespace std;
int main()
{
    int a,b;
    cin >>a;
    cin >>b;
    cout<<a+b;
    return 1;
}

search wikipedia for FERMAT'S LAST THEOREM and you will come to know everything about this problem.(1349 Farm)

Edited by author 01.11.2011 15:24