Codeforces #199前三题

先写下总结，当时第三题被黑了是好事情。自己当时想到了那种三个圆相切的局面，但后来又被自己给否定了，应该多画画图就出来了，不应该那样老是空想。而且需要搞个圆规了！

A. Xenia and Divisorstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Xenia the mathematician has a sequence consisting of n (n is divisible by 3) positive integers, each of them is at most 7. She wants to split the sequence into groups of three so that for each group of three a,?b,?c the following conditions held:

• a?<?b?<?c;
• a divides b, b divides c.

  Naturally, Xenia wants each element of the sequence to belong to exactly one group of three. Thus, if the required partition exists, then it has groups of three.

  Help Xenia, find the required partition or else say that it doesn't exist.

  Input

  The first line contains integer n (3?≤?n?≤?99999) — the number of elements in the sequence. The next line contains n positive integers, each of them is at most 7.

  It is guaranteed that n is divisible by 3.

  Output

  If the required partition exists, print groups of three. Print each group as values of the elements it contains. You should print values in increasing order. Separate the groups and integers in groups by whitespaces. If there are multiple solutions, you can print any of them.

  If there is no solution, print -1.

  Sample test(s)input

  61 1 1 2 2 2

  output

  -1

  input

  62 2 1 1 4 6

  output

  1 2 41 2 6

  
  题目大意：那个divides是整除的意思，开始看了一段时间，小数除以大数什么意思？给你1-7很多数，分成很多组，每组有a,b,c，a<b<c且a|b,b|c。解题思路就很简单了，因为只能a<b<c，并且有整除关系只有1 2 4 ，1 2 6， 1 3 6三组。假设1,2,4的个数为a个，1, 2, 6的个数为b个，1, 3, 6的个数为c个。1就有a+b+c，2就有a+b，3就有c，4就有a，6就有b+c，5和7是0。这样判断即可。详见代码。

  
  

  题目地址：A. Xenia and Divisors

  
  

  AC代码：

  B. Xenia and Spiestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
  Xenia the vigorous detective faced n (n?≥?2) foreign spies lined up in a row. We'll consider the spies numbered from 1 to n from left to right.
  Spy s has an important note. He has to pass the note to spy f. Xenia interrogates the spies in several steps. During one step the spy keeping the important note can pass the note to one of his neighbours in the row. In other words, if this spy's number is x, he can pass the note to another spy, either x?-?1 or x?+?1 (if x?=?1 or x?=?n, then the spy has only one neighbour). Also during a step the spy can keep a note and not pass it to anyone.
  But nothing is that easy. During m steps Xenia watches some spies attentively. Specifically, during step ti (steps are numbered from 1) Xenia watches spies numbers li,?li?+?1,?li?+?2,?...,?ri (1?≤?li?≤?ri?≤?n). Of course, if during some step a spy is watched, he can't do anything: neither give the note nor take it from some other spy. Otherwise, Xenia reveals the spies' cunning plot. Nevertheless, if the spy at the current step keeps the note, Xenia sees nothing suspicious even if she watches him.
  You've got s and f. Also, you have the steps during which Xenia watches spies and which spies she is going to watch during each step. Find the best way the spies should act in order to pass the note from spy s to spy f as quickly as possible (in the minimum number of steps).
  Input
  The first line contains four integers n, m, s and f (1?≤?n,?m?≤?105; 1?≤?s,?f?≤?n; s?≠?f; n?≥?2). Each of the following m lines contains three integers ti,?li,?ri (1?≤?ti?≤?109,?1?≤?li?≤?ri?≤?n). It is guaranteed that t1?<?t2?<?t3?<?...?<?tm.
  Output
  Print k characters in a line: the i-th character in the line must represent the spies' actions on step i. If on step i the spy with the note must pass the note to the spy with a lesser number, the i-th character should equal "L". If on step i the spy with the note must pass it to the spy with a larger number, the i-th character must equal "R". If the spy must keep the note at the i-th step, the i-th character must equal "X".
  As a result of applying the printed sequence of actions spy s must pass the note to spy f. The number of printed characters k must be as small as possible. Xenia must not catch the spies passing the note.
  If there are miltiple optimal solutions, you can print any of them. It is guaranteed that the answer exists.
  Sample test(s)input
  3 5 1 31 1 22 2 33 3 34 1 110 1 3
  output
  XXRR
  
            题目大意：给你n个人，每次只能往左走一步，或往右走一步。从s走到f问你最小走的路径，但是有m个规定，规定在第ti步的时候，从li到ri的位置都不能动。我的想法就是每次要么停着X，要么往右走。开始把if(s>f) swap(s,f)。开始犯2了。那样的话，需要输出往左走就只能哭瞎了！如果s<f要么停着X，要么往右走，如果s>f要么停着X，要么往左走。具体见代码。
  
   AC代码：
  C. Cupboard and Balloonstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
  A girl named Xenia has a cupboard that looks like an arc from ahead. The arc is made of a semicircle with radius r (the cupboard's top) and two walls of height h (the cupboard's sides). The cupboard's depth is r, that is, it looks like a rectangle with base r and height h?+?r from the sides. The figure below shows what the cupboard looks like (the front view is on the left, the side view is on the right).
  Xenia got lots of balloons for her birthday. The girl hates the mess, so she wants to store the balloons in the cupboard. Luckily, each balloon is a sphere with radius . Help Xenia calculate the maximum number of balloons she can put in her cupboard.
  You can say that a balloon is in the cupboard if you can't see any part of the balloon on the left or right view. The balloons in the cupboard can touch each other. It is not allowed to squeeze the balloons or deform them in any way. You can assume that the cupboard's walls are negligibly thin.
  Input
  The single line contains two integers r,?h (1?≤?r,?h?≤?107).
  Output
  Print a single integer — the maximum number of balloons Xenia can put in the cupboard.
  Sample test(s)input
  1 1
  output
  3
  input
  1 2
  output
  5
  input
  2 1
  output
  2
  
    题目大意：题目意思很简单，左边的是正面图，右边的图片是左视图。问你放半径为r/2.0的球最多能放多少个。由于半径是r/2.0，直接可以转换为二维平面上能含最多的圆。这个题目主要需要分类讨论，详见代码，开始只分了两类。但是结果被黑了，待会儿下面有图解，主要是有一种情况没有看到。在最后的十分钟的时候看到这个问题，当时没有认真想三圆相切，而是直接飘过了。。没有动笔画图的缺点暴露了。。
  
  
  详见AC代码：
  打开网络中心--网络适配器。。ip可以自动获取没得问题。主要是dns服务器地址。当你可以上网的时候就按此处操作：点击左下角“开始”——“运行”—— 输入“cmd”确定——在命令提示符中输入“ipconfig/all”,之后就会显现DMS服务器地址，记住那个地址，把那个dns地址在本地连接的属性中写入就不会断网了。（开始上网时候都是自动获取的） 。