deleted:

Edited by author 24.12.2014 23:56

What is test 4, there is a question about it but I don't understand the answer.
All the eigenvalues are positive integers not exceeding 10^9. Does it mean they are non-zeros? My solution assumes there are not zeros, maybe that's the cause of WA.
And why do I get compilation error using Visual C 2010? It's ignoring semicolons.

#include <iostream>
using namespace std;
int main()
{
    int a=1, b=5, sum=0;
    sum=a+b;
    cout<<sum<<endl;
    return 0;
}

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.