Time limit exceeded
Test №3
С#


using System;

public class Test
{
    private static void Main()
    {
        ushort n = ushort.Parse(Console.ReadLine());
        string result = "";
        int t;
        for (ushort i = 0; i < n; i++)
        {
            t = int.Parse(Console.ReadLine());
            if (Math.Sqrt((8 * t) - 7) % 1 == 0)
                result += " 1";
            else
                result += " 0";
        }
        Console.WriteLine("{0}", result);
    }
}


Whats wrong?

[code deleted]

Edited by moderator 19.11.2019 22:49

#include <stdio.h>
__int64 n, i, a[200002], b[200002], mx;
void solve(){
    a[1] = b[1] = mx = 1;
    for(i = 1 ; i < 100001 ; i ++){
       a[i << 1] = a[i];
       a[i << 1 | 1] = a[i] + a[i + 1];
       if(mx < a[i]) mx = a[i];
       b[i] = mx;
    }
    while(~scanf("%I64d", &n)){
       if(!n)  break;
       printf("%I64d ", b[n]);
    }
}
int main(){
    solve();
}

my code:
#include<iostream>
#include<cmath>
using namespace std;
main()
{
    unsigned int n,temp,nc;
    cin>>n;
    nc=n;
    temp=sqrt(n);
    if(n==0)
    cout<<0;
    else if(temp*temp==n)
    cout<<1;
    else
    {
        unsigned int x=-1,m=0,q=4,t;
        for(unsigned int i=temp;i>=1;i--)
        {
            t=i;
            while(x!=0)
            {
                x=n-t*t;
                n=x;
                t=sqrt(x);
                m++;
            }
        if(m<q)
            q=m;
        if(m==2)
            break;
        x=-1;
        m=0;
        n=nc;
        }
        cout<<q;
    }
}

Accepted...
public class CipherMessage1654_Accepted {
    public static void main(String[] args) {
        Stack<Character> stack = new Stack<Character>();
        Scanner x = new Scanner(System.in);
        String s = x.nextLine();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) >= '`' && s.charAt(i) <= '9' || s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {
                if (stack.isEmpty()) {
                    stack.push('`');
                }
                if (s.charAt(i) != stack.peek()) stack.push(s.charAt(i));
                else stack.pop();
            }
        }
        for (int i = 0; i < stack.size(); i++) {
            if (stack.get(i) != '`')
                System.out.print(stack.get(i));
        }
    }
}

Edited by author 16.12.2014 09:49

Who can give test 2. In some topic was given some and my programm gives right result.

cycle for,no more.

import java.util.Scanner;
public class easys {
 public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int sum = 0;
        int curr = 0;
        double result = 0.0;
        for(int i=0;i<N;i++){
            curr = in.nextInt();
            sum = sum + curr;

        }
     result = (double)sum/N;
        System.out.printf("%.6f",result);

    }

}

.....и что объявление произнесли на каждом языке не более одного раза.

третий вариант
3
zulu
zulu
zulu

ответ 1 язык

My solution runs in O(N logN) and it uses heap data structure. The discussion forums hint that there may be a O(N) time solution. Is there a linear time algorithm?

 As I said before I think java programs should get higher time limit. My java program gets TLE on test #4 or #5 285ms.
In my opinion my program runs in O(nlogn). Below I gave the code that gets TLE:



import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> lst = new ArrayList<>();
        int[] sorted;
        PriorityQueue<Integer>[] g;

        int[] degree = new int[8000];
        Arrays.fill(degree, 0);

        // O(n)
        while (sc.hasNextInt()) {
            int tt = sc.nextInt() - 1;
            lst.add(tt);
            degree[tt]++;
        }

        g = new PriorityQueue[lst.size() + 1];
        sorted = new int[lst.size() + 1];
        // O(n)
        for (int i = 0; i < lst.size() + 1; i++) {
            sorted[i] = i;
            g[i] = new PriorityQueue<>();
        }

        // find initial leaves O(nlogn)
        PriorityQueue<Integer> leaves = new PriorityQueue<>();
        for (Integer y : sorted) {
            if (degree[y] == 0) {
                leaves.add(y);
            }
        }

        // O(nlogn)
        for (int x : lst) {
            degree[x]--;

            int y = leaves.poll();

            g[x].add(y);
            g[y].add(x);

            if(degree[x] == 0){
                leaves.add(x);
            }

        }

        // O(nlogn)
        for (int i = 0; i < g.length; i++) {
            System.out.print((i + 1) + ":");
            while (!g[i].isEmpty()) {
                System.out.print(" " + (g[i].poll() + 1));
            }
            System.out.println("");
        }

    }
}





Edited by author 12.12.2014 23:17

Please? can I see 19 test&

What is WA 3 Test. Give me please some example

Could you give me some tests please?

#include<iostream>

using namespace std;

int arr[500005];

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

    long long int a;
    int p = 0;

    arr[0] = -1;
    for (int i = 0; i < n; i++)
    {

        cin >> a;

        if (a == arr[p] || p == 0)
        {
            p++;
            arr[p] = a;
        }
        else
            p--;
    }

    cout << arr[1] << endl;

}

Edited by author 12.12.2014 12:48

Edited by author 12.12.2014 12:48

program p1079;
  var
    a:array[0..100000] of longint;
    m:array[1..100000] of longint;
    n,max,i:longint;
  begin
    max:=1;
    a[1]:=1;
    m[1]:=1;
    readln(n);
    while n<>0 do
      begin
        if n<=max then writeln(m[n])
          else
            begin
              for i:=max+1 to n do
                begin
                 if odd(i) then a[i]:=a[i div 2]+a[i div 2+1]
                   else a[i]:=a[i div 2];
                 if a[i]>=m[i-1] then m[i]:=a[i] else m[i]:=m[i-1];
                end;
            end;
        writeln(m[n]);
        readln(n);
      end;
  end.

Finally I got AC.

The English statement is so confused that I feel it necessary to make something clear here.

1 What does SURFACE mean?
The surface means the uppermost row, in the other word, the row above the first input row. ONLY this row could be regarded as the surface. It means, the water could only pour in from these 'holes', and the man will rescue if he could reach the uppermost row.

2 What does the STARTING POINT mean?
The starting point could be ANYWHERE in the cave, even could be a BLOCKED cube (the cube with '#')(Test #22).
When we got the coordinate of the starting point, first notice that the Y-coordinate begins from the bottom. Then, you should do searching. Here:
(1) DO NOT think a blocked starting point means "rescue operation required". Just regard it as a empty cell and continue.
(2) When the man starts, he is at the starting point. Now he have just D-cube breaths, not D-1. That means the following testcase is correct:
3 3 2 1 3
#.#
#.#
#.#
Can be rescued by himself.
SO, IN ONE WORD, the starting point, although may be blocked or flooded with water, we can regard it as a place to breath as if it is empty without water.

3 How long could he stay in water?
Through D cubes. If you look at the samples carefully, you will get the answer, without the mistake of D and D-1.

4 What does "Here only the paths having no downward segments are considered" in statement mean?
It means the water could only flow lower and lower, not higher in any cases. So, in the sample data, the (5,3) cube will not be flooded with water and this cube can be used to breathe.

5 What does "It is known that a speleologist can reach the surface while cave is not filled with water." in statement mean?
It means there exist a path from the starting point to the surface. If there is no water, or the man has infinite breathe, he could reach the surface.

6 What is the time complexity of the problem?
O(W*H) could be achieved, though O(W*H*D) might have AC, too.

Hope the instructions above could help someone in trouble.

When n = 3 and k = 2, the output should be 4 because for the first 2 steaks, it would take 2 minutes (1 + 1 for both the sides) and for the remaining 1 steak again 2 minutes (1 + 1 for both the sides)
then 2 + 2 = 4. That's what I think the output should be. So, what's wrong here, can somebody answer please?

It's not clear if each word must be found in the grid only once. Maybe task should be edited.

Can there be two persons that have the same Specialization and the same rank??