Beautiful Arrangement

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 ≤ i ≤ N) in this array:

  1. The number at the ith position is divisible by i.
  2. i is divisible by the number at the ith position.

Now given N, how many beautiful arrangements can you construct?

Example 1:

Input: 2
Output: 2
Explanation:
The first beautiful arrangement is [1, 2]:
Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).
Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).
The second beautiful arrangement is [2, 1]:
Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).
Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.

Note:

  1. N is a positive integer and will not exceed 15.
 1 public class Solution {
 2     private int count = 0;
 3
 4     public int countArrangement(int N) {
 5         helper(N, 1, new boolean[N]);
 6         return count;
 7     }
 8
 9     private void helper(int N, int level, boolean[] visited) {
10         if (level > N) {
11             count++;
12             return;
13         }
14
15         for (int i = 1; i <= N; i++) {
16             if ( !visited[i - 1] && (level % i == 0 || i % level == 0) ) {
17                 visited[i - 1] = true;
18                 helper(N, level + 1, visited);
19                 visited[i - 1] = false;
20             }
21         }
22     }
23 }
时间: 02-25

Beautiful Arrangement的相关文章

过中等难度题目.0310

  .   8  String to Integer (atoi)    13.9% Medium   . 151 Reverse Words in a String      15.7% Medium     . 288 Unique Word Abbreviation      15.8% Medium     . 29 Divide Two Integers      16.0% Medium     . 166 Fraction to Recurring Decimal      17.

[Python]HTML/XML解析器Beautiful Soup

[简介] Beautiful Soup是一个可以从HTML或XML文件中提取数据的Python库.即HTML/XMLX的解析器. 它可以很好的处理不规范标记并生成剖析树(parse tree). 它提供简单又常用的导航(navigating),搜索以及修改剖析树的操作.它可以大大节省你的编程时间. [安装] 下载地址:点击打开链接 Linux平台安装: 如果你用的是新版的Debain或ubuntu,那么可以通过系统的软件包管理来安装: $ apt-get install Python-bs4 B

python标准库Beautiful Soup与MongoDb爬喜马拉雅电台的总结

Beautiful Soup标准库是一个可以从HTML/XML文件中提取数据的Python库,它能够通过你喜欢的转换器实现惯用的文档导航,查找,修改文档的方式,Beautiful Soup将会节省数小时的工作时间.pymongo标准库是MongoDb NoSql数据库与python语言之间的桥梁,通过pymongo将数据保存到MongoDb中.结合使用这两者来爬去喜马拉雅电台的数据... Beautiful Soup支持Python标准库中的HTML解析器,还支持一些第三方的解析器,其中一个是

[2016-03-08][651][codeforces][B][Beautiful Paintings]

[2016-03-08][651][[codeforces]][B][Beautiful Paintings] 题目编号:CF 651 B 题目大意:画展有n个画,每个画beauty值已知,客人每经过一个比之前一个画更美的,客人会变得beauty,重新安排画的顺序,求客人开心时间的最大值 输入:n 和每个话的beauty 输出:时间 分析: 如果beauty为a的画,数量为 k,那么beaty小于或者大于a的k个,总能安排让客人开心,所以,除了数量k最大的那个beauty之外,每个beauty总

Codeforces 55D Beautiful Number

Codeforces 55D Beautiful Number a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. Input The first line of the input contains the number of cases t (1 ≤ t ≤ 10). Each of the next t lines contains two

ACM-ICPC国际大学生程序设计竞赛北京赛区(2015)网络练习赛 题目4 : Beautiful String

We say a string is beautiful if it has the equal amount of 3 or more continuous letters (in increasing order.) Here are some example of valid beautiful strings: "abc", "cde", "aabbcc", "aaabbbccc". Here are some exa

Instrction Arrangement (hdu 4109 差分约束)

Instrction Arrangement Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1395    Accepted Submission(s): 584 Problem Description Ali has taken the Computer Organization and Architecture course th

Codeforces Beta Round #51---D. Beautiful numbers(数位dp, 巧妙)

Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. We will not argue with this and just count the quantity of beautiful num

HDU 4782 Beautiful Soup(模拟)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4782 Problem Description Coach Pang has a lot of hobbies. One of them is playing with "tag soup" with the help of Beautiful Soup. Coach Pang is satisfied with Beautiful Soup in every respect, except