The problem suggests
"The set of angles αi satisfies a condition that the sum of angles in any of its nonempty subsets is not aliquot to 360 degrees."

However the sample gives "90 90 90"...

Any hints on how to solve this problem??

Edited by author 09.04.2011 01:59

Hi all, i've used segment tree to solve this problem and got stuck with TLE 11.
Maybe someone have idea of how to improve this solution to fit in time. Or one can provide test data that will get TLE locally.

import java.util.Scanner;

public class P1147 {

    private static final int MAX_COLORS = 2501;
    private static final short UNKNOWN = 0;
    private static long c[] = new long[MAX_COLORS];
    private static final int TREE_SIZE = 1<<22;
    private static final int PARTITION_FACTOR = 10;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        short a = scanner.nextShort();
        short b = scanner.nextShort();
        short n = scanner.nextShort();
        short[] tree = new short[TREE_SIZE];
        Rectangle[] rectangles = new Rectangle[n + 1];
        rectangles[0] = new Rectangle(0, 0, a, b, 1);
        for (short i = 1; i <= n; i++) {
            rectangles[i] =  new Rectangle(scanner.nextShort(), scanner.nextShort(), scanner.nextShort(), scanner.nextShort(), scanner.nextShort());
        }
        for (double iPartition = 0; iPartition < PARTITION_FACTOR - 1e-6; iPartition++) {
            for (double jPartition = 0; jPartition < PARTITION_FACTOR - 1e-6; jPartition++) {
                Rectangle partition = new Rectangle((int) (a * (iPartition / PARTITION_FACTOR)), (int) (b * (jPartition / PARTITION_FACTOR)), (int) (a * ((iPartition + 1) / PARTITION_FACTOR)), (int) (b * ((jPartition + 1) / PARTITION_FACTOR)));
                for (Rectangle rectangle : rectangles) {
                    insert(tree, 0, rectangle, partition);
                }
                countColors(tree, 0, partition);
            }
        }
        for (int i = 0; i < MAX_COLORS; i++) {
            if (c[i] != 0) {
                System.out.println(i + " " + c[i]);
            }
        }
    }

    static void insert(short[] tree, int node, Rectangle rect, Rectangle region) {
        if (!rect.intersects(region) || !rect.isValid() || !region.isValid()) return;
        if (rect.contains(region)) {
            tree[node] = rect.color;
        } else {
            if (tree[node] == UNKNOWN) {
                int xMid = (region.x1 + region.x2) / 2;
                int yMid = (region.y1 + region.y2) / 2;
                insert(tree, node * 4 + 1, rect, new Rectangle(region.x1, region.y1, xMid, yMid));
                insert(tree, node * 4 + 2, rect, new Rectangle(xMid,  region.y1, region.x2, yMid));
                insert(tree, node * 4 + 3, rect, new Rectangle(xMid, yMid, region.x2, region.y2));
                insert(tree, node * 4 + 4, rect, new Rectangle(region.x1, yMid, xMid, region.y2));
            } else {
                if (tree[node] == rect.color) return;
                Rectangle bottom = new Rectangle(region.x1, region.y1, region.x2, rect.y1, tree[node]);
                Rectangle top = new Rectangle(region.x1, rect.y2, region.x2, region.y2, tree[node]);
                Rectangle left = new Rectangle(region.x1, rect.y1, rect.x1, rect.y2, tree[node]);
                Rectangle right = new Rectangle(rect.x2, rect.y1, region.x2, rect.y2, tree[node]);
                tree[node] = UNKNOWN;
                insert(tree, node, rect, region);
                insert(tree, node, bottom, region);
                insert(tree, node, top, region);
                insert(tree, node, left, region);
                insert(tree, node, right, region);


        }
    }

    private static void countColors(short[] tree, int node, Rectangle region) {
        if (!region.isValid()) return;
        if (node >= TREE_SIZE) return;
        if (tree[node] != UNKNOWN) {
            c[tree[node]] += region.area();
        } else {
            int xMid = (region.x1 + region.x2) / 2;
            int yMid = (region.y1 + region.y2) / 2;
            countColors(tree, node * 4 + 1, new Rectangle(region.x1, region.y1, xMid, yMid));
            countColors(tree, node * 4 + 2, new Rectangle(xMid, region.y1, region.x2, yMid));
            countColors(tree, node * 4 + 3, new Rectangle(xMid, yMid, region.x2, region.y2));
            countColors(tree, node * 4 + 4, new Rectangle(region.x1, yMid, xMid, region.y2));
        }
    }

    static class Rectangle {
        short x1, y1, x2, y2, color;

        Rectangle(int x1, int y1, int x2, int y2, int color) {
            this.x1 = (short) x1;
            this.y1 = (short) y1;
            this.x2 = (short) x2;
            this.y2 = (short) y2;
            this.color = (short) color;
        }

        public Rectangle(int x1, int y1, int x2, int y2) {
            this(x1, y1, x2, y2, UNKNOWN);
        }

        boolean intersects(Rectangle other) {
            return other.x1 < this.x2 && other.x2 > this.x1 && other.y1 < this.y2 && other.y2 > this.y1;
        }

        boolean contains(Rectangle other) {
            return (other.x1 >= this.x1) && (other.x2 <= this.x2) && (other.y1 >= this.y1) && (other.y2 <= this.y2);
        }

        boolean isValid() {
            return x1 < x2 && y1 < y2;
        }

        long area() {
            return (x2 - x1) * (y2 - y1);
        }
    }
}

Many thanks,

Vitaliy

I need more samples... I thought I understood, but when I submitted the task, I got WA, so, can you give some more samples, for me to get an idea?

I do calculations on a ring of integers modulo (big prime). If i change the prime number sometimes i get WA on test 9.

Any suggestions?
.....

Got AC.
Edit: Found a silly mistake. I thought is about the prime, but it wasn't.


Edited by author 08.04.2011 06:41

KISS! There is no TA even if you use:
from.find(to.substr(to_position, length), from_position)

I checked the code, and all the test given here, and it gives true answers, but I don't know why I get WA on 17... Can you give some more tests that are similar to 17 so I can see where is my mistake?

My program works well, but I have WA on test 6
please give some tests

What's wrong?


program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  i,n:integer;
  data:string;
  tmp:array of string;

begin
  readln(data);
  n:=0;
  SetLength(tmp,length(data)+1);

  for i:= 1 to length(data) do
    begin
      if not(data[i]=' ')then
        tmp[n]:=tmp[n]+data[i];
      if (data[i]=' ')and (data[i+1]<>' ')then
        n:=n+1;
    end;
  for i:=n downto 1 do
    writeln(sqrt(StrToFloat(tmp[i])):0:4);

  readln;
end.

could you test it again? i've no idea whats wrong

Why output to syserr cause wa#1?
Is it working as intended?

In the final loop, when you count the number of circles which the given line touches, use only + and * operations (without divisions and - OMG - square roots) - this will speed your code up several times.

Edited by author 13.10.2010 21:13

I wrote a solution with complexity of O(n^3 log n) and got AC for 0.75 sec. Is there a solution for O(n^3) or O(n^2 log n)?

I got WA on Test 15 :(

Why this code have WA on test13?
Please give me a test when this program fail.

var N,K:longint;
begin
  readln(N,K);
  if k>N then n:=k;
  N:=2*N;
  if N mod K = 0 then writeln(N div K)
                 else writeln(N div K + 1);
end.

need some test plz. no idea whats wrong. thanks.

Is the radiation between two consecutive caves zero?

Edited by author 05.04.2011 03:43